- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
6.5 Алгоритм составления кольцевого двусвязного списка
Задача. Имеется файл, состоящий из записей. Одно из полей - некоторый признак (ключ). Из всех записей, обладающих нужным значением признака, составить динамический двусвязный кольцевой список в последовательности следования в наборе данных. Записать сведения из динамических списков в два набора данных(НД): один - от начала списка к его концу - НД1, другой - в обратной последовательности - НД2.
Попробуем составить алгоритм, используя принцип пошаговой детализации. Выделим главные этапы.
Этап 1. Построить двойной кольцевой динамический список из записей НД1, обладающих требуемым значением признака.
Этап 2. Путем просмотра списка от начала к концу вывести информацию из списка в НД2.
Этап 3. Просмотром списка от конца к началу вывести информацию из обратного списка в НД2.
Детализируем этап 1.
Создать первый фиктивный элемент. Адресовать ему указатель начала списка F и указатель конца списка R. Прямой и обратный указатели фиктивного элемента сделать пустыми.
Ввести значение признака выборки в программу.
Пока не конец файла:
Читать запись
Если в записи содержится нужное значение признака, то 1.3.2.1. Включить её в прямой и обратный списки
Исключить фиктивный элемент из списка переадресацией указателей.
Замкнуть прямой и обратный списки в кольцо. Этапы 2, 3 в детализации не нуждаются. Приведем описание переменных.
TYPE ZAP = RECORD
PR : T;
END; PTR = ASP; SP = RECORD
INF : ZAP; LI : PTR; L2 : PTR END; VAR K, J, F, R : PTR; REC : ZAP; FZ1, FZ2, FZ3 : FILE OF ZAP; N : INTEGER; счетчик элементов списка
PZ : T; Детализируем п.1.1 - 1.5.
1.1. NEW(K);
KA.L1 := NIL; KA.L2 := NIL; F := K; R := K;
READLN(PZ);
WHILE NOT EOF(fzl) DO BEGIN
READ(FZ1, REC);
IF REC.PR = PZ THEN BEGIN 1.3.2.1 J := K; NEW(K);
KMNF := REC; KA.L1 := NIL; KA.L2 := J; JA.L1 := K; R := K; N := N + 1
END; 1.4. K := F;
F := F^.L1;
F^.L2 := nil;
DISPOSE(K); 1.5 R^.L1 := F;
F^.L2 := R;
Теперь программа: PROGRAM SOSTSPIS; { раздел описаний } BEGIN
WRITELN (' программа создания и вывода двойного кольцевого списка '); { 1.1 – создание фиктивного элемента } WRITE (' введите признак выборки '); { 1.2 – ввод значения признака }
ASSIGN (FZ1,'ND1'); ASSIGN (FZ2,'ND2'); ASSIGN (FZ3,'ND3'); RESET (FZ1); REWRITE (FZ2); REWRITE (FZ3); N := 0;
{ 1.3 – создание списка } IF n > 0 THEN BEGIN
{ 1.4 – удаление фиктивного элемента }
{ 1.5 – замыкание прямого и обратного кольца }
{ 2 – просмотр списка от начала к концу }
{ 3 – просмотр списка от конца а началу } END ELSE
WRITELN (' список пуст ');
CLOSE(FZ1); CLOSE(FZ2); CLOSE(FZ3); END.
Контрольные вопросы
Динамическое распределение памяти.
Указатели и работа с ними.
Представление стека с помощью указателей.
Операции, выполняемые над стеком.
Программная реализация операций, выполняемых над стеком.
Представление очереди с помощью указателей.
Операции, выполняемые над очередью.
Программная реализация операций, выполняемых над очередью.
Представление односвязного списка с помощью указателей.
Основные операции, определенные над списками.
Программная реализация формирования списка.
Программная реализация добавления элемента в конец списка.
Программная реализация удаления элемента из списка.
Просмотр списка.
Списки с двумя связями.
Алгоритм составления кольцевого двусвязного списка.