Logo GenDocs.ru

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

Загрузка...

Лекции - Структуры и алгоритмы компьютерной обработки данных - файл 10.Линейные списки. Очередь. Стек..doc


Лекции - Структуры и алгоритмы компьютерной обработки данных
скачать (1611 kb.)

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

10.Линейные списки. Очередь. Стек..doc1129kb.01.07.2007 15:51скачать
11.Деревья поиска. Случайные (рандомизованные) бинарные деревья..doc373kb.01.07.2007 16:05скачать
12.Генерация комбинаторных объектов. Перестановки. Размещения. Сочетания..doc53kb.01.07.2007 16:16скачать
13.Перебор с возвратом. Общая схема перебора.doc36kb.01.07.2007 16:25скачать
14.Методы сокращения перебора. Эвристические алгоритмы. Метод ветвей и границ..doc28kb.01.07.2007 16:28скачать
15.Динамическое программирование.doc60kb.01.07.2007 16:36скачать
16.Алгоритмы на графах. Графы и различные способы их представления. Поиск в глубину..doc79kb.01.07.2007 16:57скачать
17.Поиск в ширину. Построение эйлерова цикла..doc31kb.01.07.2007 16:59скачать
18.Построение минимального остовного дерева (алгоритмы Прима и Крускала)..doc50kb.01.07.2007 17:05скачать
19.Нахождение кратчайших путей во взвешенном графе, алгоритмы Флойда и Дейкстры..doc38kb.01.07.2007 17:10скачать
1.Введение в анализ алгоритмов. Понятие сложности алгоритмов. Классы сложности алгоритмов..doc2902kb.01.07.2007 14:36скачать
20.Алгоритмы построения максимального потока. Максимальный поток минимальной стоимости.doc76kb.01.07.2007 17:33скачать
21.Построение максимального паросочетания в двудольном графе.doc42kb.01.07.2007 17:33скачать
22.NP-полные задачи. Полиномиальная сводимость. Типичные NP задачи..doc81kb.01.07.2007 17:43скачать
2.Методы анализа рекуррентных алгоритмов.doc39kb.01.07.2007 14:45скачать
3.Числовые алгоритмы. Длинная арифметика. Теоретико-числовые алгоритмы. Проверка чисел на простоту..doc43kb.01.07.2007 14:55скачать
4.Задача сортировки. Устойчивость. Алгоритмы внутренней сортировки. Простейшие алгоритмы..doc29kb.01.07.2007 15:03скачать
5.Сортировка слиянием. Быстрая сортировка Хоара..doc37kb.01.07.2007 15:06скачать
6.Пирамидальная сортировка и очередь с приоритетом.doc120kb.01.07.2007 15:17скачать
7.Сортировка подсчетом. Цифровая сортировка. Порядковые статистики. Внешняя сортировка.doc31kb.01.07.2007 15:22скачать
8.Динамические множества. Поиск в неупорядоченном массиве. Двоичный поиск в упорядоченном массиве..doc34kb.01.07.2007 15:27скачать
9.Хеширование. Методы устранения коллизий. Хеширование с открытой адресацией.doc203kb.01.07.2007 15:38скачать

содержание

10.Линейные списки. Очередь. Стек..doc

Линейные списки

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

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

type

PList = ^List;

List = record

Data: DataType;

Next: PList;

end;

Var L: PList;

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






^ 4 шага добавления

New (Q);

Q^.Data:=D;

Q^.Next:=L;

L:=Q


Добавление элемента в середину списка

после T^

New(Q);

Q^.Data:=D;

Q^.Next:=T^.Next;

T^.Next:=Q;

перед T^

New(Q);

Q^:=T^;

T^.Data:=D;

T^.Next:=Q;

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

Q:=L


L:=Q^.Next;

Dispose(Q);

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

Просмотр элементов списка осуществляется последовательно, начиная с первого элемента (головы).

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

T:=L;

while (T<>nil) do begin

writeln(T^.data);

T:=T^.next;

end;


^ Анализ списков

Быстро (с константной сложностью) выполняются операции добавления, удаления, объединения списков.

Медленно (с линейной) – обход списка. Перебор элементов возможен только в одном направлении. Если нужен перебор в обратном направлении, используются двунаправленные списки.



^ Стек и очередь

Стек - структура данных, в которой удалить можно только тот элемент, который был добавлен последним (LIFO).

Для реализации стека можно использовать линейный список, у которого сохранен указатель на голову списка. Операции добавления и удаления производятся в голове списка. У пустого стека указатель равен nil.

Очередь - структура данных, в которой удалить можно только тот элемент, который был добавлен первым (FIFO). Для реализации очереди используется линейный список с двумя указателями: на голову и хвост. Добавление происходит в хвост, а удаление - из головы списка.

^ Реализация стека массивом

Массив A[0..N-1]. Для стека требуется один указатель на голову h.

При добавлении элемента в голову стека записываем значение и увеличиваем указатель h.

A[h]:=k;

h:=(h+1) mod N;

Для удаления из головы стека требуется обратная операция:

h:=(h -1+N) mod N;

k:=A[h];

^ Реализация очереди массивом

Указатель на голову – h, на хвост – t.

Добавление в хвост очереди:

A[t]:=k;

t:=(t+1) mod N;


Удаление из головы очереди:

k:=A[h];

h:=(h+1) mod N;


Очередь пуста, если h=t.


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

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

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