Списковые структуры

1. Тема: Списковые структуры.

ТЕМА:
СПИСКОВЫЕ СТРУКТУРЫ.

2. Указатель:

УКАЗАТЕЛЬ:
Обычно переменная хранит некоторые данные, но
существуют переменные, которые хранят ссылки
на другие переменные и называются указателями.
Переменная-указатель хранит адрес другой
переменной:

3. Переменная-указатель,

ПЕРЕМЕННАЯ-УКАЗАТЕЛЬ,
как и любая другая переменная программы, должна
быть объявлена в разделе объявления переменных:
Имя:^Тип
где Имя – имя переменной-указателя;
Тип – тип переменной, на которую может указывать
переменная-указатель Имя.
Например:
p1:^integer;
p2:^real;
p1 - указатель на переменную типа integer;
p2 - указатель на переменную типа real.
В начале работы программы переменная-указатель ни
на что не указывает, ее значение равно NIL (это
зарезервированное слово используется для
обозначения значения переменной-указателя, которая
ни на что не указывает).

4. Динамические переменные:

ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ:
Это переменные, память для которых
выделяется во время выполнения
программы. Выделение памяти
осуществляется вызовом процедуры
new.
Для освобождения памяти,
занимаемой динамической
переменной, используется процедура
Dispose.

5. Связанные списки:

СВЯЗАННЫЕ СПИСКИ:
Указатели и динамические переменные позволяют
создавать сложные динамические структуры:
стек – простейшая динамическая структура, в
которой добавление элементов в стек и выборка из
него выполняются из одного конца, называемого
вершиной стека. Говорят, что стек реализует
принцип обслуживания LIFO (last in – first out,
последним пришел, первым – обслужен).
очередь - динамическая структура, добавление
элементов в которую выполняется в один конец, а
выборка – из другого конца. Очередь реализует
принцип обслуживания FIFO (first in – first out,
первым пришел, первым – обслужен).

6. линейные списки:

ЛИНЕЙНЫЕ СПИСКИ:
линейные списки – каждый элемент списка связан
со следующим, а возможно и с предыдущим:
односвязный - каждый элемент списка связан со
следующим элементом списка. Включает: поле INF информационное поле, данные, NEXT - указатель
на следующий элемент списка. Каждый список
должен иметь особый элемент, называемый
указателем начала списка или головой списка,
который обычно по формату отличен от остальных
элементов. В поле указателя последнего элемента
списка находится специальный признак nil,
свидетельствующий о конце списка.

7. Link = ^Auto; {Указатель на элемент списка} Auto = record Name : String; {Поле данных} Next : Link; {Указатель на следующий

СТРУКТУРА ЭЛЕМЕНТА ОДНОСВЯЗНОГО ЛИНЕЙНЫОГО
СПИСКА:
LINK = ^AUTO;
{УКАЗАТЕЛЬ НА ЭЛЕМЕНТ СПИСКА}
AUTO = RECORD
NAME : STRING; {ПОЛЕ ДАННЫХ}
NEXT : LINK;
{УКАЗАТЕЛЬ НА СЛЕДУЮЩИЙ
ЭЛЕМЕНТ СПИСКА}
END;

8. Type NameStr = String [20]; Link = ^Auto; Auto = record Name : NameStr; {Марка автомобиля} Speed : real; {Скорость} Next :

ПРИМЕР:
TYPE
NAMESTR = STRING [20];
LINK = ^AUTO;
AUTO = RECORD
NAME : NAMESTR; {МАРКА АВТОМОБИЛЯ}
SPEED : REAL;
{СКОРОСТЬ}
NEXT : LINK;
{ПОЛЕ ДЛЯ СВЯЗИ СО СЛЕДУЮЩИМ
ОБЪЕКТОМ В СПИСКЕ}
END;
VAR
P,FIRST : LINK;
{УКАЗАТЕЛИ НА ЗАПИСЬ:
ТЕКУЩУЮ,ПЕРВУЮ}

9. procedure InpAvto; begin New(P); {Создать очередной объект типа Auto} Write('Введите марку автомобиля:'); Readln(P^.Name) ;

ПРИМЕР: {Ввести данные об объекте}
PROCEDURE INPAVTO;
BEGIN
NEW(P);
{СОЗДАТЬ ОЧЕРЕДНОЙ ОБЪЕКТ ТИПА AUTO}
WRITE('ВВЕДИТЕ МАРКУ АВТОМОБИЛЯ:');
READLN(P^.NAME) ;
WRITE('МАКСИМАЛЬНАЯ СКОРОСТЬ:');
READLN(P^.SPEED);
ADDFIRST(P);{ВЫЗОВ ПРОЦЕДУРЫ ДОБАВЛЕНИЯ ЗАПИСИ, НА КОТОРУЮ
ССЫЛАЕТСЯ УКАЗАТЕЛЬ}
END;
{КОНЕЦ INPAVTO}

10. procedure MyList; var Curr : Link; {Локальная переменная – указатель на очередной объект} begin Curr:=First; {Установить

ПРИМЕР: {Вывести на экран все объекты из
связанного списка}
PROCEDURE MYLIST;
VAR
CURR : LINK; {ЛОКАЛЬНАЯ ПЕРЕМЕННАЯ – УКАЗАТЕЛЬ НА ОЧЕРЕДНОЙ
ОБЪЕКТ}
BEGIN
CURR:=FIRST; {УСТАНОВИТЬ УКАЗАТЕЛЬ НА ПЕРВЫЙ ОБЪЕКТ В СПИСКЕ}
{ПОВТОРЯТЬ, ПОКА НЕ ДОЙДЕМ ДО КОНЦА СПИСКА}
WHILE CURR <> NIL DO
BEGIN
WRITELN( 'МАРКА: ' , CURR^. NAME,' СКОРОСТЬ : ',
CURR^. SPEED) ;
CURR:=CURR^.NEXT; {ПЕРЕЙТИ К ОЧЕРЕДНОМУ ОБЪЕКТУ СВЯЗАННОГО
СПИСКА}
END ;
WRITE('ВЫВОД СПИСКА ОКОНЧЕН. НАЖМИТЕ ENTER');
READLN;
END;
{КОНЕЦ MYLIST}

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

ПРИМЕНЕНИЕ ЛИНЕЙНЫХ СПИСКОВ
ПРИЛОЖЕНИЯ, ГДЕ НЕПРЕДСКАЗУЕМЫ
ТРЕБОВАНИЯ НА РАЗМЕР ПАМЯТИ,
НЕОБХОДИМОЙ ДЛЯ ХРАНЕНИЯ ДАННЫХ;
БОЛЬШОЕ ЧИСЛО СЛОЖНЫХ ОПЕРАЦИЙ НАД
ДАННЫМИ, ОСОБЕННО ВКЛЮЧЕНИЙ И
ИСКЛЮЧЕНИЙ.
НА БАЗЕ ЛИНЕЙНЫХ СПИСКОВ
МОГУТ СТРОИТСЯ СТЕКИ, ОЧЕРЕДИ
И ДЕКИ.

12. Вставка элемента в середину 1-связного списка

ВСТАВКА ЭЛЕМЕНТА
В СЕРЕДИНУ 1-СВЯЗНОГО СПИСКА

13. Удаление элемента из 1-связного списка

УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ 1-СВЯЗНОГО СПИСКА

14. Линейный двунаправленный список

ЛИНЕЙНЫЙ
ДВУНАПРАВЛЕННЫЙ СПИСОК

15. линейный двусвязный списоки:

ЛИНЕЙНЫЙ ДВУСВЯЗНЫЙ СПИСОКИ:
каждый элемент списка связан со следующим и
предыдущим элементами списка. Включает: поле
NEXT - указатель на следующий элемент, поле
PREV - указатель на предыдущий элемент. В
крайних элементах соответствующие указатели
должны содержать nil.

16. Вставка элемента в середину 2-связного списка

ВСТАВКА ЭЛЕМЕНТА
В СЕРЕДИНУ 2-СВЯЗНОГО СПИСКА

17. Удаление элемента из 2-связного списка

УДАЛЕНИЕ ЭЛЕМЕНТА ИЗ 2-СВЯЗНОГО СПИСКА

18. кольцевой список -

КОЛЬЦЕВОЙ СПИСОК
разновидность рассмотренных видов линейных
списков, при этом в односвязном списке указатель
последнего элемента должен указывать на первый
элемент; в двухсвязном списке в первом и последнем
элементах соответствующие указатели
переопределяются.

19. стек

СТЕК

20. Стек (stack) -

СТЕК (STACK) - линейный последовательный список, в котором
доступ, включение и исключение элементов
выполняется только с одного конца: т.е. доступен
только последний элемент.
Дисциплина обслуживания элементов стека
выражается аббревиатурой
LIFO (Last – In – First – Out) –
"последний пришел – первым вышел".
Доступна единственная позиция стека - вершина
стека – это позиция, в которой находится последний
по времени поступления в стек элемент.

21. Реализация стека:

РЕАЛИЗАЦИЯ СТЕКА:

22. Элемент стека:

ЭЛЕМЕНТ СТЕКА:
Type
TStack = ^TElementSt;
TElementSt = record
info:string;
Next:TStack
end;
var
….
ist: TStack;

23. очереди

ОЧЕРЕДИ

24. Очередь (Queue) -

ОЧЕРЕДЬ (QUEUE) Структура данных, представляющая собой
последовательность элементов, образованная в
порядке их поступления.
Дисциплина обслуживания элементов очереди
выражается аббревиатурой
FIFO (First Input – First Output) –
«первым пришел – первым вышел".
Доступны две позиции очереди- начало и конец
очереди– добавление элементов очереди – в конец
очереди, извлечение – из начала очереди..

25. Реализация очереди:

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:

26. Элемент очереди:

ЭЛЕМЕНТ ОЧЕРЕДИ:
Type
TQ = ^TElementQueue;
TElementQueue = record
info:string;
Next:TQ
end;
TQueue = record
head:TQ;
tail:TQ
end;

27.

ПОВТОРЕНИЕ:

28.

ПРИМЕНЕНИЕ ЛИНЕЙНЫХ СПИСКОВ ?

29. Правильно?

ПРАВИЛЬНО?
1.
Односвязный список
2.
Двусвязный список
List = record
Data : string;
Next, Prev : plist;
end;
Auto = record
Name : NameStr;
Speed : real;
Next : Link;
end;

30. Тесты:

ТЕСТЫ:
Вопрос 1. Какие из указанных ниже
структур данных относятся к
встроенным:
1) списки;
2) целый тип;
3) дерево;
4) стек.

31. Тесты:

ТЕСТЫ:
Вопрос 2. Какая из ниже
перечисленных структур данных
отличается наличием вершины:
1) дерево;
2) множество;
3) стек;
4) массив.

32. Тесты:

ТЕСТЫ:
Вопрос 4. Упорядоченная совокупность
элементов некоторого типа,
адресуемых при помощи одного или
нескольких индексов, называется:
1) массив;
2) дерево;
3) стек;
4) список.

33. Тесты:

ТЕСТЫ:
Вопрос 5. Структура данных,
объединяющая элементы данных
разных типов, называется:
1) массив;
2) дерево;
3) стек;
4) запись.

34.

Что такое стек?
Как обслуживается стек?
Сколько позиций в стеке доступно?
С использованием каких структур
можно в программе реализовать
стек?