6.5 Алгоритм составления кольцевого двусвязного списка

Задача. Имеется файл, состоящий из записей. Одно из полей - некоторый признак (ключ). Из всех записей, обладающих нужным значением признака, составить динамический двусвязный кольцевой список в последова­тельности следования в наборе данных. Записать сведения из динамических списков в два набора данных(НД): один - от начала списка к его концу - НД1, другой - в обратной последовательности - НД2.

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

Этап 1. Построить двойной кольцевой динамический список из записей НД1, обладающих требуемым значением признака.

Этап 2. Путем просмотра списка от начала к концу вывести информацию из списка в НД2.

Этап 3. Просмотром списка от конца к началу вывести информацию из обратного списка в НД2.

Детализируем этап 1.

Создать первый фиктивный элемент. Адресовать ему указатель начала списка F и указатель конца списка R. Прямой и обратный указатели фиктивного элемента сделать пустыми.

2. Ввести значение признака выборки в программу.

3. Пока не конец файла:

1. Читать запись

2. Если в записи содержится нужное значение признака, то 1.3.2.1. Включить её в прямой и обратный списки

4. Исключить фиктивный элемент из списка переадресацией указателей.

5. Замкнуть прямой и обратный списки в кольцо. Этапы 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);

K^A.L1 := NIL; K^A.L2 := NIL; F := K; R := K;

2. READLN(PZ);

3. WHILE NOT EOF(fzl) DO BEGIN

1. READ(FZ1, REC);

2. IF REC.PR = PZ THEN BEGIN 1.3.2.1 J := K; NEW(K);

KMNF := REC; K^A.L1 := NIL; K^A.L2 := J; J^A.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.

Контрольные вопросы

1. Динамическое распределение памяти.

2. Указатели и работа с ними.

3. Представление стека с помощью указателей.

4. Операции, выполняемые над стеком.

5. Программная реализация операций, выполняемых над стеком.

6. Представление очереди с помощью указателей.

7. Операции, выполняемые над очередью.

8. Программная реализация операций, выполняемых над очередью.

9. Представление односвязного списка с помощью указателей.

10. Основные операции, определенные над списками.

11. Программная реализация формирования списка.

12. Программная реализация добавления элемента в конец списка.

13. Программная реализация удаления элемента из списка.

14. Просмотр списка.

15. Списки с двумя связями.

16. Алгоритм составления кольцевого двусвязного списка.