Logo GenDocs.ru


Поиск по сайту:  


Лекции по информатике - файл all lec.doc


Лекции по информатике
скачать (398.8 kb.)

Доступные файлы (1):

all lec.doc1495kb.21.01.2007 21:18скачать

содержание

all lec.doc

1   ...   6   7   8   9   10   11   12   13   14
Реклама MarketGid:

Стек


Стеком называется структура данных, элементы которой органи­зованы таким образом, что их удаление будет осуществляться противоположно тому порядку, в котором производилось добав­ление.

Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок и т.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелки снимаются со стопки в порядке, обратном их добавлению. Доступна только верхняя тарелка, т.е. тарелка на вершине стека.

Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет их следующая цель: нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимости переключения на другую задачу. Стек используется для временного сохранения состояния, не выполненного до конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании ее выполнения состояние отложенного задания восстанавливается из стека, и компьютер продолжает прерванную работу.

Почему именно стек используется для сохранения состояния прерванного задания? Предположим, что компьютер выполняет задачу A. В процессе ее выполнения возникает необходимость выполнить задачу B. Состояние задачи A запоминается, и компьютер переходит к выполнению задачи B. Но ведь и при выполнении задачи B компьютер может переключиться на другую задачу C, и нужно будет сохранить состояние задачи B, прежде чем перейти к C. Позже, по окончании C будет сначала восстановлено состояние задачи B, затем, по окончании B, — состояние задачи A. Таким образом, восстановление происходит в порядке, обратном сохранению, что соответствует дисциплине работы стека.

Стек можно представить в виде вертикального массива с одним указателем на верхний элемент, традиционно называе­мый вершиной стека (тор). В текущий момент времени вершина стека является доступной. Новый элемент можно добавлять в вершину стека, он же первый подлежит обработке. Стек часто обозначают аббревиатурой LIFO (Last In, First Out — последний зашел, первый вышел).

Элементы стека хранятся в массиве следующим образом: элемент на дне стека располагается в начале массива, т.е. в ячейке с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится в ячейке с индексом 1, и так далее. Вершина стека хранится где-то в середине массива. Индекс элемента на вершине стека хранится в специальной переменной, которую обычно называют указателем стека (по-английски Stack Pointer или просто SP).

Если стек содержит только один элемент, и этот элемент удаляется, то в результате выполнения операции в данный стек больше не смо­жет быть занесен ни один элемент. Такой стек называется пустым.

Допустим, имеется стек из элементов А, В и С. Если элемент А был первым занесен в стек, а элемент С — последним, то стек будет выглядеть так, как показано на рис. 1.

Если удалить из стека элемент с, доступный для операций, пере­местив указатель тор на один элемент вниз, то стек будет выгля­деть, как показано на рис. 2.

Теперь добавим в стек некоторый элемент D. Для этого запишем его в вершину стека, сместив указатель тор на один элемент вниз (рис. 3).


1.Содержимое стека 2.Удаление элемента из стека



3.Добавление элемента в стек

^

Операции над стеками


Для реализации операций над стеками будем использовать сле­дующие функции:
добавление элемента в стек

void Push(LIFO, Top, Number)
проверка пустоты стека

void Empty(Top)
удаление элемента из стека

void Pop(Top)
^ Добавление элемента в стек

Пусть размер стека равен maxstack. Чтобы поместить элемент в стек, необходимо указать сам элемент и индекс (адрес) верши­ны стека.
void Push(int Top, int Element)

{

if (Top= =maxstack) exit(l); // Стек заполнен

Stack[Top]=Element; // Добавляет элемент Element в стек

Тор++; // Сдвигает указатель Тор на один элемент вверх

}
^ Проверка стека на наличие элементов

Данная процедура возвращает р=1, если стек пуст, и р=2, если в стеке есть элементы.
void Empty(int Top)

{

if (Top= =0) p=l; // Стек пуст

else p=2; // Стек не пуст

}
^ Удаление элемента из стека

Функция удаления элементов из стека такова:
void Remove(int Top)

{

if (Top==0) exit(l); // Стек пуст

Top—; // Сдвигает указатель Top на один элемент вниз

}
^ Стековый калькулятор и обратная польская запись формулы

В 1920 г. польский математик Ян Лукашевич предложил способ записи арифметических формул, не использующий скобок. В привычной нам записи знак операции записывается между аргументами, например, сумма чисел 2 и 3 записывается как 2 + 3. Ян Лукашевич предложил две другие формы записи: префиксная форма, в которой знак операции записывается перед аргументами, и постфиксная форма, в которой знак операции записывается после аргументов. В префиксной форме сумма чисел 2 и 3 записывается как + 2 3, в постфиксной — как 2 3 +. В честь Яна Лукашевича эти формы записи называют прямой и обратной польской записью.

В польской записи скобки не нужны. Например, выражение
(2+3)*(15-7)
записывается в прямой польской записи как
* + 2 3 - 15 7,
в обратной польской записи — как
2 3 + 15 7 - *.

Если прямая польская запись не получила большого распространения, то обратная оказалась чрезвычайно полезной. Неформально преимущество обратной записи перед прямой польской записью или обычной записью можно объяснить тем, что гораздо удобнее выполнять некоторое действие, когда объекты, над которыми оно должно быть совершено, уже даны.

Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя стек как запоминающее устройство для хранения промежуточных результатов. Такой стековый калькулятор был впервые выпущен фирмой Hewlett Packard. Обычные модели калькуляторов не позволяют вычислять сложные формулы без использования бумаги и ручки для записи промежуточных результатов. В некоторых моделях есть скобки с одним или двумя уровнями вложенности, но более сложные выражения вычислять невозможно. Также в обычных калькуляторах трудно понять, как результат и аргументы перемещаются в процессе ввода и вычисления между регистрами калькулятора. Калькулятор обычно имеет регистры X, Y и регистр памяти, промежуточные результаты каким-то образом перемещаются по регистрам, каким именно — запомнить невозможно.

В отличие от других калькуляторов, устройство стекового калькулятора вполне понятно и легко запоминается. Калькулятор имеет память в виде стека. При вводе числа оно просто добавляется в стек. При нажатии на клавишу операции, например, на клавишу +, аргументы операции сначала извлекаются из стека, затем с ними выполняется операция, наконец, результат операции помещается обратно в стек. Таким образом, при выполнении операции с двумя аргументами, например, сложения, в стеке должно быть не менее двух чисел. Аргументы удаляются из стека и на их место кладется результат, то есть при выполнении сложения глубина стека уменьшается на единицу. Вершина стека всегда содержит результат последней операции и высвечивается на дисплее калькулятора.

Для вычисления выражения надо сначала преобразовать его в обратную польскую запись (при некотором навыке это легко сделать в уме). В приведенном выше примере выражение (2+3)*(15-7) преобразуется к
2 3 + 15 7 - *
Затем обратная польская запись просматривается последовательно слева направо. Если мы видим число, то просто вводим его в калькулятор, т.е. добавляем его в стек. Если мы видим знак операции, то нажимаем соответствующую клавишу калькулятора, выполняя таким образом операцию с числами на вершине стека.

Изобразим последовательные состояния стека калькулятора при вычислении по приведенной формуле. Сканируем слева направо ее обратную польскую запись:
2 3 + 15 7 - *
Стек вначале пуст. Последовательно добавляем числа 2 и 3 в стек.
| | вводим число 2 | 2 | вводим число 3 | 3 |

| 2 |
Далее читаем символ + и нажимаем на клавишу + калькулятора. Числа 2 и 3 извлекаются из стека, складываются, и результат помещается обратно в стек.
| 3 | выполняем сложение | 5 |

| 2 |
Далее, в стек добавляются числа 15 и 7.
| 5 | вводим число 15 | 15 | вводим число 7 | 7 |

| 5 | | 15 |

| 5 |
Читаем символ - и нажимаем на клавишу - калькулятора. Со стека при этом снимаются два верхних числа 7 и 15 и выполняется операция вычитания. Причем уменьшаемым является то число, которое было введено раньше, а вычитаемым — число, введенное позже. Иначе говоря, при выполнении некоммутативных операций, таких как вычитание или деление, правым аргументом является число на вершине стека, левым — число, находящееся под вершиной стека.
| 7 | выполняем вычитание | 8 |

| 15 | | 5 |

| 5 |
Наконец, читаем символ * и нажимаем на клавишу * калькулятора. Калькулятор выполняет умножение, со стека снимаются два числа, перемножаются, результат помещается обратно в стек.
| 8 | выполняем умножение | 40 |

| 5 |

Число 40 является результатом вычисления выражения. Оно находится на вершине стека и высвечивается на дисплее стекового калькулятора.
^

Ссылочные реализации структур данных


Большинство структур данных реализуется на базе массива. Все реализации можно разделить на два класса: непрерывные и ссылочные. В непрерывных реализациях элементы структуры данных располагаются последовательно друг за другом в непрерывном отрезке массива, причем порядок их расположения в массиве соответствует их порядку в реализуемой структуре. Рассмотренные выше реализации очереди и стека относятся к непрерывным.

В ссылочных реализациях элементы структуры данных хранятся в произвольном порядке. При этом вместе с каждым элементом хранятся ссылки на один или несколько соседних элементов. В качестве ссылок могут выступать либо индексы ячеек массива, либо адреса памяти.

Ссылочные реализации обладают двумя ярко выраженными недостатками: 1) для хранения ссылок требуется дополнительная память; 2) для доступа к некоторому элементу структуры необходимо сначала добраться до него, проходя последовательно по цепочке других элементов. Казалось бы, зачем нужны такие реализации?

Все недостатки ссылочных реализаций компенсируются одним чрезвычайно важным достоинством: в них можно добавлять и удалять элементы в середине структуры данных, не перемещая остальные элементы.

^ Массовые операции

Массовые операции — это операции, затрагивающие значительную часть всех элементов структуры данных. Пусть нужно добавить или удалить один элемент. Если при этом приходится, например, переписывать значительную часть остальных элементов с одного места на другое, то говорят, что добавление или удаление приводит к массовым операциям. Массовые операции — это бедствие для программиста, то, чего он всегда стремится избежать. Хорошая реализация структуры данных — та, в которой массовых операций либо нет совсем, либо они происходят очень редко. Например, добавление элемента должно выполняться за ограниченное число шагов, независимо от того, содержит ли структура десять или десять тысяч элементов.

В непрерывных реализациях добавление или удаление элементов в середине структуры неизбежно приводит к массовым операциям. Поэтому структуры, в которых можно удалять или добавлять элементы в середине, обязательно должны быть реализованы ссылочным образом.

Списки


Классический пример структуры данных последовательного доступа, в которой можно удалять и добавлять элементы в середине структуры, — это линейный список.

Списком называется некоторая последовательность элементов, связанных при помощи указателей.

Различают однонаправленный и двунаправленный списки (иногда говорят односвязный и двусвязный).

Элементы списка как бы выстроены в цепочку друг за другом. У списка есть начало и конец. Имеется также указатель списка, который располагается между элементами. Если мысленно вообразить, что соседние элементы списка связаны между собой веревкой, то указатель — это ленточка, которая вешается на веревку. В любой момент времени в списке доступны лишь два элемента — элементы до указателя и за указателем.



В однонаправленном списке указатель можно передвигать лишь в одном направлении — вперед, в направлении от начала к концу. Кроме того, можно установить указатель в начало списка, перед его первым элементом. В отличие от однонаправленного списка, двунаправленный абсолютно симметричен, указатель в нем можно передвигать вперед и назад, а также устанавливать как перед первым, так и за последним элементами списка.

В двунаправленном списке можно добавлять и удалять элементы до и за указателем. В однонаправленном списке добавлять элементы можно также с обеих сторон от указателя, но удалять элементы можно только за указателем.

Удобно считать, что перед первым элементом списка располагается специальный пустой элемент, который называется головой списка. Голова списка присутствует всегда, даже в пустом списке. Благодаря этому можно предполагать, что перед указателем всегда есть какой-то элемент, что упрощает процедуры добавления и удаления элементов.

В двунаправленном списке считают, что вслед за последним элементом списка вновь следует голова списка, т.е. список зациклен в кольцо.



Можно было бы точно так же зациклить и однонаправленной список. Но гораздо чаще считают, что за последним элементом однонаправленного списка ничего не следует. Однонаправленный список, таким образом, представляет собой цепочку, начинающуюся с головы списка, за которой следует первый элемент, затем второй и так далее вплоть до последнего элемента, а заканчивается цепочка ссылкой в никуда.



Список, который не содержит ни одного элемента, называется пустым.

Каждый элемент списка (иногда называемый узлом) состоит из двух частей. Первая часть содержит данные, принадлежащие элемен­ту, и является информационной. Вторая часть содержит указатель и является справочной. Указатель определяет местоположение элемента списка, связанного с данным элементом. На рисунке приведен пример списка с элементами А, В, С и D.


Стрелка в данном списке обозначает связь элементов списка. Указатель (т. е. вторая часть элемента списка) элемента А опреде­ляет номер следующего элемента списка. Указатель элемента В показывает, что за ним следует элемент С и т. д. Отсутствие или нулевое значение указателя означает, что данный элемент явля­ется последним в списке.

Элементы в списке могут быть связаны посредством разных ука­зателей.

В однонаправленных списках для каждого элемента указатель задает местоположение следующего

В отли­чие от однонаправленных списков, в двунаправленных списках для каждого элемента задаются два указателя, которые опреде­ляют местоположение как предыдущего элемента, так и после­дующего.

При работе со списками используется, как правило, еще один Указатель, который определяет первый элемент списка.

Для представления однонаправленного списка в памяти компью­тера можно использовать двумерный массив List [2][maxlist], где maxlist — это количество элементов в списке. В данном двумерном массиве любой элемент List[0] [i] содержит значе­ние элемента списка, а в List[i] [i] находится указатель на сле­дующий элемент.

Двунаправленный список так же представляется в виде двумер­ного массива List[3] [maxlist]. В этом случае элемент списка расположен в List[0] [i], а в List[1] [i] и List[2] [i] находятся указатели, которые указывают соответственно на предыдущий и последующий элементы списка.

^

Операции над списками


Основными операциями над списками являются:

  • переход к очередному элементу списка;

  • добавление в список нового элемента;

  • поиск заданного элемента;

  • удаление элемента из списка.

Выполнение этих операций основывается на использовании и изменении указателей.

В отличие от очередей и стеков, элемент в список может быть до­бавлен в любое место.

^ Создание пустого списка

Определим значение указателей для пустого списка. Пусть пере­менная us будет задавать адрес первого элемента списка свобод­ных мест, а переменная UN — адрес первого элемента списка. Для пустого списка US=1, un=0. Приведем пример создания пустого списка при помощи функции New.
void New()

{for (i=l; i<maxlist-l; i++)

List[1][i]=i+1;

List[1][maxlist]=0;

US=1;

UN=0;

}
Для точного и правильного использования операций над списками будем считать, что индексация элементов массива начинается с единицы, а не с нуля.

Вид пустого списка приведен в таблице.
Таблица 1. Вид пустого списка



^ Добавление в список нового элемента

Для добавления элемента х в список необходимо в переменную Pos запомнить адрес первого элемента списка свободных мест. Затем нужно поместить по этому адресу элемент х и в качестве указателя на следующий элемент списка записать номер первого элемента списка. Теперь указателем первого элемента списка бу­дет указатель us, т. к. по его адресу записан новый элемент. Он из разряда свободных элементов переходит в разряд занятых. Ука­зателем списка свободных мест будет Pos, т. е. элемент, который следует в списке свободных мест за только что исключенным из него элементом.

Приведем пример кода функции Insert (int, int, int), которая добавляет элемент х в список.
void Insert{int US, int UN, int X)

{

if (Sp= =O) exit{l); // Список не содержит элементов

Pos=List[1][US]; // Находит адрес первого элемента // списка свободных мест

List[0][US]=X; // Помещает по этому адресу значение X

List[1][US]=UN; // В качестве указателя

//на следующий элемент помещает

// номер первого элемента списка

UN=US;

US=POS;

}
Рассмотрим подробно операцию добавления элемента х в список. Сначала указатель списка свободных мест US=1, а первый элемент списка UN=0. Добавим в список элемент а, используя функцию Insert (int, int, int). Вид обновленного списка приведен в таблице. Зна­чит, US = 2, a UN=A.
Таблица 2. Добавление в список элемента А


Добавим в список элемент в, используя функцию Insert(int, int, int). US=3, UB=B (таблица).
Таблица 3. Добавление в список элемента В



Аналогичным образом добавим в таблицу элементы C и d US=5, a UN=D.
Таблица 4. Список после добавлениям в него элементов C и D



Теперь список свободных позиций содержит элементы с индек­сами 5, 6, 7, 8, 9, 10, а первым элементом списка является эле­мент d. Логическое расположение элементов в списке будет d, с, B, A. Этот порядок определяется указателями.


^ Поиск элемента в списке

Поиск элемента х в списке осуществляется следующим образом. Пе­ременной Lop присваиваем значение указателя первого элемента списка. Далее просматриваем список до тех пор, пока не найдем нужный элемент, либо не достигнем конца списка. Если по оконча­нию процедуры Lop=0, значит, в списке нет элемента со значением х.

Далее приведен пример функции Find (int, int, int), которая организовывает поиск в заданном списке элемента со значением х.
void Find(int X, int UN)

{

Lop=UN;

while (List[0][Lop]!=X && Lop!=0)

Lop=List[1][Lop]; // Присваивает переменной Lop ссылку

// на следующий элемент

}
^ Удаление элемента из списка

Чтобы удалить элемент х из списка, необходимо сначала найти его в списке, например, при помощи функции Find (int, int, int).

При удалении изменяется указатель записи элемента, идущего в списке перед элементом х таким образом, чтобы он указывал на элемент, идущий в списке после элемента х. Пусть Pos — индекс элемента массива, который необходимо уда­лить, а к — индекс элемента массива, который следует за элементом List[1] [POS].

Функция Delete (int, int, int) удаляет элемент х из списка. Далее приведен ее код.
void Delete (int K, int Pos, int US)

{

List[1][K]=List[1][Pos];

List[1][Pos]=US;

US=Pos;

}
Проследим удаление элемента х на примере списка из таблицы 4. Удалим элемент C из списка при помощи функции Delete (int, int, int).
Таблица 5. Удаление элемента из списка



После проделанных операций указатель списка свободных мест us=3, а первым элементом списка un=d.
^ Добавление элемента в список после заданного элемента

Необходимо сначала найти заданный элемент х, а затем вставить после него новый элемент е. При добавлении нового элемента в список после элемента х по адресу первого элемента списка свободных мест записывается значение нового элемента. Указатель но­вого элемента принимает значение, равное адресу следующего за ним элемента списка, а указатель предшествующего ему элемента списка принимает значение адреса нового элемента.

Эти операции реализует функция Insert_after(int, int, int). Далее приведен ее код.
void Insert_after (int Pos, int US, int E)

{

List[0][US]=E;

List[1][US]=List[1][Pos];

List[1][Pos]=US;

}
Здесь pos — это индекс элемента х.

После добавления элемента е после элемента в в предыдущей таблице получим список, приведенный в таблице 6.
Таблица 6. Добавление элемента D после элемента A


Сортировка списков

При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка, и для ее решения сущест­вуют различные методы.

Если в задаче требуется отсортировать все элементы списка, то он сортируется как обычный массив, любым из ранее предло­женных методов (например, табл. 7, 8).
Таблица 7. Исходный список



Таблица 8. Отсортированный список


В некоторых задачах возникает необходимость сортировки спи­ска таким образом, чтобы по указателям можно было восстано­вить исходный список (например, табл. 9, 10).
Таблица 9. Исходный список



Таблица 10. Отсортированный список



В данном случае при сортировке необходимо менять местами не только элементы списка, но и их указатели. Обмен значениями можно организовать функцией swap(x,у), которая будет менять местами элементы и указатели списка в позициях х и у. Далее приведен код данной функции.
void Swap (int x, int y)

{

int Temp;

Temp=List[0][x];

List[0][y]=Temp;

Temp=List[1][x];

List[1][x]=List[1][y];

List[1][y]=Temp;

}
Данная сортировка списка необходима для того, чтобы на неко­тором i-ом шаге можно было вернуться на шаг под номером j и выполнить другие действия.
^ Слияние списков

Упорядоченные списки List_1 и List_2 длиной M и N сливаются в один упорядоченный список List_res длины M+N, если каж­дый элемент из List_1 и List_2 входит в List_res ровно один раз. В табл. 11—13 приведен пример слияния списков.
Таблица 11. Упорядоченный список List_1


Таблица 12. Упорядоченный список List_2




Таблица 13. Упорядоченный список List_res


Алгоритм слияния двух списков прост. Его основная идея выгля­дит следующим образом. Для слияния списков List_1 и List_2 список List_res сначала полагается пустым, а затем к нему по­следовательно приписывается первый узел из List_1 или List_2, оказавшийся меньшим и отсутствующий в List_res.
1   ...   6   7   8   9   10   11   12   13   14

Реклама:





Скачать файл (398.8 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru