Лекции - Структуры и алгоритмы компьютерной обработки данных
скачать (1611 kb.)
Доступные файлы (22):
скачатьсодержание
- Смотрите также:
- Ответы на ГОС экзамены по дисциплине Структуры и алгоритмы обработки данных [ документ ]
- Алгоритм Крускала (Краскала). Нахождение остовного дерева [ документ ]
- Режимы компьютерной обработки данных [ документ ]
- Информационные технологии [ документ ]
- Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных [ документ ]
- Алгоритмизация [ документ ]
- Структуры данных и алгоритмы [ реферат ]
- Алгоритмизация [ документ ]
- Девянин П.Н., Михальский О.О., Правиков Д.И., Щербаков А.Ю. Теоретические основы компьютерной безопасности [ документ ]
- по компьютерной графике [ документ ]
- Базы Данных [ документ ]
- по компьютерной графике [ документ ]
10.Линейные списки. Очередь. Стек..doc
Линейные спискиСписком называется структура данных, каждый элемент которой связывается со следующим элементом посредством указателя. Элемент списка представлен записью, содержащей поле с данными Data и указатель Next на следующую запись.
Указатель у последнего элемента списка считаем равным nil Для работы со списком используется указатель на его первый элемент.
type
PList = ^List;
List = record
Data: DataType;
Next: PList;
end;
Var L: PList;
Добавление элемента в начало списка
^
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.)