16839

Связанные структуры

Лекция

Информатика, кибернетика и программирование

Лекция 11 8. Связанные структуры Основные понятия Записи содержащие указатели позволяют формировать в ОП линейные и нелинейные связанные структуры. К линейным связанным структурам относят например стеки очереди и списки. К нелинейным деревья и сети. Эти структур

Русский

2013-06-26

682 KB

0 чел.

Лекция 11

8. Связанные структуры

Основные понятия

Записи, содержащие указатели, позволяют формировать в ОП линейные и нелинейные связанные структуры. К линейным связанным структурам относят, например, стеки, очереди и списки. К нелинейным - деревья и сети. Эти структуры имеют множество приложений и являются фундаментальными понятиями в программировании. Рассмотрим линейные связанные структуры: стеки, очереди и списки. Они реализуют линейные бесприоритетные дисциплины по организации накопления, чтения данных и удаления элементов связанной структуры.

Линейные структуры имеют много общего:

все элементы связанных структур представляют собой последовательность
элементов, связанных между собой в цепь с помощью указателей;

максимальное количество элементов структур ограничивает объем ОП;

ОП для элементов структур выделяется и освобождается динамически, например с помощью подпрограмм New, GetMem, FreeMem и Dispose;

последовательность  элементов  имеет  начало  цепи  (его  указатель  имеет
значение
Nil)  и конец (вершину),  которую обычно адресует указатель
стека, очереди или списка.

Схематично связь элементов линейных структур представлена на рис. 19. Различие названных линейных структур состоит в том, что включение и исключение элементов из связанных структур разных типов производится по-разному:

  1.  в стеке  включение  и  исключение  элементов стека  производится только
    с одного конца: с его вершины;
  2.  в очереди:

а) включение элементов производится с одного конца цепи: только в конец
очереди;

б) исключение  элементов  -  с другого  конца  цепи:  только  из  ее  начала
(вершины);

Рис. 19

Схема взаимосвязи элементов иепи связанных структур

3) в списке элементы обычно упорядочены по определенному признаку, одному из элементов записи, из которых формируется список; включение и
исключение элементов производится в любом месте цепи, так как поиск
требуемого места в списке производится, как правило, по признаку, по которому список упорядочен.

По количеству указателей одного элемента и способам их соединения цепи связанных структур могут быть однонаправленные, двунаправленные и закольцованные. Двунаправленные и закольцованные цепи повышают их надежность. Рассмотрим связанные однонаправленные цепи, т. е. цепи, элементы которых содержат один указатель для их реализации, на примере стека, очереди и списка.

Стек

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

LIFO - Last in - First Out (последним вошел - первым вышел);

магазинная память (оружейный термин).

Пример организации данных в виде стека - это стопка тарелок: тарелка, уложенная на стопу последнею, извлекается из нее первою, т. е. тарелки укладываются в стопу снизу вверх, а извлекаются сверху вниз, начиная с верхней тарелки. Этот способ организации данных используется, например, при обработке последовательности активизированных подпрограмм и вложенных циклов. При этом подпрограмма, активизированная последнею, завершит свою работу первою. Цикл, начавший выполняться последним, завершится первым.

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

Базовые операции над стеком:

  1.  добавление в стек нового элемента;
  2.  чтение данных из вершины стека, т. е. помещенных в него последними;
  3.  удаление из стека данных, помещенных в него последними.

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

DOP - процедура дополнения стека новым элементом; UD - функция удаления элемента из вершины стека; СНТ - функция чтения данных из вершины стека.

Листинг 37. Тестирование стека.

TYPE PSTRC = ^STRC;

    STRC = RECORD

INF : INTEGER;   { - информация элемента стека  } PTR : PSTRC  { - указатель на предыдущий элемент} END;

VAR S1, S2 : PSTRC; I : INTEGER; ERR : BOOLEAN;

{         - Дополнение стека новым элементом   }

PROCEDURE DOP ( VAR S : PSTRC; DAT : INTEGER );

VAR NOV : PSTRC; { - указатель нового элемента стека }

BEGIN NEW ( NOV ); { - запрос ОП для нового элемента   }

NOV^.INF := DAT; NOV^. PTR := S; S :=NOV; END;

{   Удаление последнего элемента из стека -     }

FUNCTION UD (VAR S:PSTRC; VAR ERR : BOOLEAN } : INTEGER;
VAR OLD : PSTRC; { - указатель на удаляемый элемент }

BEGIN IF S <> NIL THEN BEGIN { - удаление успешно }

OLD := S; S := S^.PTR; UD := OLD^.INF; DISPOSE (OLD);

ERR := FALSE;

END

ELSE BEGIN UD := 0; ERR := TRUE;  END;
END; { -
удаление неуспешно }

{   Чтение последнего элемента из стека -        — }

FUNCTION СНТ ( S : PSTRC; VAR ERR : BOOLEAN ) : INTEGER; BEGIN

IF S <> NIL THEN BEGIN { Чтение успешно: }

WRITE ('INF= ',S^.INF:3); ERR := FALSE; CHT := S^.INF

END

ELSE BEGIN WRITELN('СТЕК ПУСТ'); ERR:=TRUE; CHT:=0;

END END;

/ ОСНОВНАЯ ПРОГРАММА - - }

BEGIN  ASSIGN (OUTPUT, 'STACK.RES'); REWRITE (OUTPUT);

S1 := NIL;    S2 := NIL;

WRITELN (' ПРОВЕРКА ПУСТОТЫ СТЕКОВ ' );

      CHT (S1, ERR);    CHT (S2, ERR);

WRITELN (' СТЕК SI: ДОПОЛНЕНИЕ И ЧТЕНИЕ ' );

FOR I := 12 TO 16 DO BEGIN

DOP (S1,I); WRITELN('I = ',1:3,'CHT =', CHT(S1,ERR):3);

END;

WRITELN('ЗАПОЛНЕНИЕ СТЕКА S2 ЭЛЕМЕНТАМИ, СЧИТАННЫМИ И УДАЛЕННЫМИ ИЗ S1');

FOR I := 1 ТО 5 DO BEGIN

DOP ( 32, CHT(SI, ERR));

IF NOT ERR THEN WRITELN ('UD = ', UD(S1,ERR):3) ;

END;

WRITELN ('ЧТЕНИЕ ИЗ СТЕКА 32 И УДАЛЕНИЕ ЕГО ЭЛЕМЕНТОВ'); FOR I:=1 ТО 5 DO WRITELN(CHT(S2,ERR):3,' ',UD(S2,ERR):3); WRITELN (' ПРОВЕРКА ПУСТОТЫ СТЕКОВ ');

CHT (SI, ERR);   CHT (S2, ERR); END.

В начале и в конце тестирования производится проверка пустоты стеков S1 и S2 с помощью функции СНТ - чтения.

Формальным параметром подпрограмм DOP и UD является параметр-переменная S - указатель на вершину стека. Определение формального параметра S в подпрограммах DOP и UD в виде параметра-переменной необходимо для того, чтобы возвратить новое значение указателя на вершину стека после выполнения соответствующих действий над стеком.

Процедура DOP предназначена для включения в стек нового элемента. Схематично это представлено на рис. 20.

Рис. 20

Схема включения в стек нового элемента

Формальными параметрами процедуры DOP являются: S - указатель на вершину стека, параметр-переменная; DAT - информация для нового элемента.

Локальной переменной процедуры DOP является NOV - указатель на новый элемент стека.

В программе листинга 37 используются 2 указателя на вершины двух стеков: S1 и S2. Указатели S1 и S2 всегда содержат адреса последних элементов, введенных в стек. Первоначальные значения S1 и S2 = NIL. Стек пуст. Дополнение стека новым элементом производится с помощью процедуры DOP. При вызове из программы процедуры DOP(S1,I); в процедуру передаются в качестве фактических параметров:

S1 - указатель на вершину первого стека;

I - информация для нового элемента (записи) стека.

В процедуре DOP с помощью процедуры NEW для нового элемента стека выделяется ОП, адрес начала которой запоминается в NOV - локальном указателе стека. В новый элемент стека заносится его информация: NOV^. INF : = DAT;. После этого новый элемент присоединяется к прежней вершине стека; для этого формируется значение его указателя на элемент прежней вершины стека в виде

NOV^.PTR   :=   S;

где     S - указатель на вершину стека (фактический параметр S1).

Новый элемент стал вершиной стека, что и фиксируется формированием нового значения указателя на вершину стека в виде S := NOV. Так как фактическим параметром был S1 - указатель на вершину стека, в качестве результата работы процедуры DOP возвращается его значение на новую вершину стека: S := NOV;.

Функция UD предназначена для удаления элемента из вершины стека. Формальные параметры функции UD:

S - указатель на вершину стека, параметр-переменная;

ERR - возвращаемое значение признака успешности удаления.

Для упрощения программы возвращаемое значение ERR не анализируется в вызывающей программе. Локальная переменная функции UD = OLD – это указатель на старую, удаляемую запись; начальное значение OLD  =   S - это указатель (адрес) вершины стека.

OLD^. INF - удаляемая (старая) информация; это значение возвращается в качестве результата с помощью оператора UD := OLD^.INF;. Функция UD возвращает в качестве результатов:

1) в случае успешного удаления - значения:

S - указатель на новую вершину стека через параметр;

OLD^ . INF - удаляемая информация - с помощью оператора

UD   :=  OLD.INF;;

ERR = FALSE - признак успешного удаления - через параметр;

2) в случае неуспешного удаления, если стек пуст и удаления элемента не
происходит:

S - прежний указатель на вершину стека;

- удаленную информацию: UD = 0;

ERR = TRUE - признак неуспешного удаления.

В случае успешного удаления элемента память удаленного элемента освобождается с помощью процедуры DISPOSE (OLD) ;.

В начале выполнения функции UD наличие в стеке элементов определяется с помощью анализа S - значения указателя на вершину стека:

  1.  если S   =  NIL, т. е. стек пуст, формируется значение признака неуспешности удаления ERR = TRUE и удаленное значение =  0;
  2.  если S <> NIL, т. е. стек не пуст:

а) формируются возвращаемые значения:

удаляемой информации: UD   := OLD^.INF;

указателя на предыдущий элемент стека: S   := S^.PTR;

признака успешности удаления: ERR = FALSE;

б) с помощью процедуры DISPOSE освобождается ОП удаленного элемента стека: DISPOSE   (OLD) ;.

Функция СНТ предназначена для считывания и возврата информации из элемента вершины стека, если стек не пуст, и значения 0, если стек пуст. Признак успешности чтения имеет те же значения, что и при выполнении функции UD. Формальный параметр S - параметр-значение - указатель на вершину стека, так как значение указателя не изменяется в функции СНТ. Возвращаемые значения:

  1.  если стек пуст, ERR = TRUE и значение информации, равное 0,
  2.  если стек не пуст, ERR   =   FALSE и значение информации из элемента
    вершины стека.

Очередь

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

FIFO - First In - First Out (первым вошел - первым вышел).

Очередь - это связанная структура данных, в которой добавлять элементы можно только в конец очереди, а удалять и читать данные можно только с начала очереди: доступен при этом только элемент, стоящий в очереди первым в начале очереди. Будем называть первым элементом очереди элемент, поступивший в нее первым, и последним элементом - элемент, поступивший в очередь последним. Базовые операции над очередью:

  1.  добавление нового элемента в конец очереди (процедура DOP - дополнения);
  2.  чтение из очереди данных, помещенных в нее первыми (функция СНТ -
    чтения);
  3.  удаление из очереди первого элемента, т. е. данных, размещенных в вершине цепи (функция UD - удаления ).

При работе с очередями можно использовать один указатель на начало очереди или 2 указателя: один на начало очереди, другой - на ее конец. Использование двух указателей упростит алгоритм подключения нового элемента.

В программе листинга 38 представлено формирование и тестирование очереди с использованием записей, аналогичных записи, приведенной в подразделе "Стек" (разд. 8).

Листинг 38. Тестирование очереди.

TYPE PSTRC = ^ STRC;         { - указатель на запись }

STRC = RECORD {  Запись в составе: }

INF : INTEGER;  {  - информация элемента очереди    }

PTR : PSTRC    {  - указатель на следующий, элемент }

END;

VAR Q1, Q2 : PSTRC; { - указатели на очереди }

I : INTEGER; ERR : BOOLEAN;

{   Дополнение очереди новым элементом   }

PROCEDURE DOP ( VAR Q : PSTRC; DAT : INTEGER );

VAR NOV, CUR, PR : PSTRC; BEGIN  CUR := Q; PR := NIL;

NEW ( NOV ); { - запрос ОП для нового элемента }

NOV^.INF := DAT; NOV^.PTR := NIL;

WHILE CUR <> NIL DO BEGIN

PR:=CUR; CUR := CUR^.PTR; { - движение вдоль очереди }

END;

{  Подключение нового элемента очереди: }

IF PR<>NIL THEN PR^.PTR:=NOV {- новый элемент - очередной} ELSE Q := NOV;        { - новый элемент - первый    } END;

{   Чтение первого элемента очереди   }

FUNCTION СНТ ( Q : PSTRC; VAR ERR : BOOLEAN ) : INTEGER; BEGIN

IF Q <> NIL THEN BEGIN { - чтение успешно }

ERR := FALSE;   CHT := Q^.INF

END

ELSE BEGIN { - чтение неуспешно }

WRITE ( ' ПУСТА ' ); ERR := TRUE; CHT := 0;

END END;

{   Удаление первого элемента из очереди-- - }

FUNCTION UD (VAR Q:PSTRC; VAR ERR:BOOLEAN ) : INTEGER;

VAR OLD : PSTRC;  VAL : INTEGER;

BEGIN  OLD := Q;

IF Q <> NIL THEN BEGIN { - очередь не пуста }

Q := Q^.PTR; UD:=OLD^.INF; DISPOSE(OLD); ERR := FALSE;

     END ELSE BEGIN UD:=0; ERR:=TRUE; {- очередь пуста }

END END;

{  ОСНОВНАЯ   ПРОГРАММА- -}

BEGIN  ASSIGN(OUTPUT, 'QUEUE.RES'); REWRITE(OUTPUT);

  Q1:=NIL; Q2:=NIL;

WRITELN('ОЧЕРЕДЬ Q1:ДОПОЛНЕНИЕ');

FOR I:=12 TO 16 DO BEGIN DOP(Q1,I); WRITELN('I =',I:3); END; WRITELN ('ЧТЕНИЕ 1-ГО ЭЛЕМЕНТА ОЧЕРЕДИ Q1', #10#13,

'Q1.INF = ', CHT(Q1, ERR) : 3);

WRITELN ('ЗАПОЛНЕНИЕ ОЧЕРЕДИ Q2 ЭЛЕМЕНТАМИ, СЧИТАННЫМИ',

' И УДАЛЕННЫМИ ИЗ Q1');

FOR I := 1 ТО 5 DO BEGIN  DOP ( Q2, CHT(Q1, ERR));

IF NOT ERR THEN WRITELN ('UD2 =', UD(Q1,ERR):3); END; WRITELN ('ЧТЕНИЕ 1-ГО ЭЛЕМЕНТА ОЧЕРЕДИ Q2', #10#13,

'Q2.INF = ', CHT(Q2, ERR));

WRITELN ('ЧТЕНИЕ ИЗ ОЧЕРЕДИ Q2 И УДАЛЕНИЕ ЕЕ ЭЛЕМЕНТОВ',

#10#13, 'СЧИТАНО  УДАЛЕНО');

FOR I := 1 ТО 5 DO WRITELN(CHT(Q2, ERR) : 4, '  ', UD(Q2,ERR) : 7); WRITELN ('ПРОВЕРКА ПУСТОТЫ ОЧЕРЕДЕЙ ' );

WRITELN ('ОЧЕРЕДЬ Q1:', CHT(Q1, ERR), 'ОЧЕРЕДЬ Q2:', CHT(Q2,ERR)); END.

В программе листинга 38 используются: DOP - процедура дополнения очереди новым элементом; UD - функция удаления элемента из начала очереди; СНТ - функция чтения элемента из начала очереди.

В процессе тестирования очереди программой листинга 38 производится:

заполнение очереди Q1 числами от 12 до 16 (с помощью DOP);

заполнение очереди Q2 значениями, удаленными из очереди Q1;

вывод значений, считанных из начала очередей Q1 и Q2;

вывод и удаление всех значений из очереди Q2.

В начале и в конце тестирования производится проверка пустоты очередей Q1 и Q2 с помощью функции СНТ - чтения.

В программе используется 2 указателя на начала двух очередей: Q1 и Q2. Первоначальные значения Q1 и Q2 = N11. Очередь пуста. Указатель на очередь всегда содержит адрес первого элемента очереди (вершины цепи). Все  элементы очереди связаны между собою с помощью указателей PTR (см. рис. 19). Значение указателя в последнем элементе очереди (поступившем в очередь последним) равно NIL (нулю).

Рассмотрим подпрограммы программы листинга 38.

Процедура DOP предназначена для дополнения очереди новым элементом, который подключается в конец очереди.

Формальные параметры подпрограмм DOP, UD и СНТ аналогичны параметрам таких же подпрограмм, используемым при тестировании стека. Формальные параметры процедуры DOP:

Q - указатель на очередь, параметр-переменная;

DAT - информация для нового элемента, параметр-значение.

Локальные переменные процедуры DOP: CUR - указатель текущего (очередного) элемента очереди; PR - указатель предыдущего (перед CUR) элемента очереди; NOV - указатель на новый элемент очереди.

Схема алгоритма процедуры DOP представлена на рис. 21.

Рис. 21

Схема алгоритма процедуры DOP - включения в очередь нового элемента

Начальные значения локальных переменных:

CUR   =   0 - указывает на начало (вершину) очереди; если очередь пуста,

значение CUR  =  Q  =  NIL;;

PR = NIL - не указывает ни на что.

В процедуре OOP с помощью процедуры NEW для нового элемента очереди выделяется ОП, адрес которой запоминается в NOV - локальном указателе очереди. Затем новый элемент очереди заполняется:

  1.  информацией: NOV^. INF   :=  DAT;;
  2.  указателем: NOV^.PTR   :=   NIL;  так как это элемент очереди, включенный в нее последним.

Новый элемент должен быть подключен в качестве следующего элемента после последнего элемента очереди, т. е. после элемента, указатель которого имеет нулевое значение. Для поиска этого элемента надо просмотреть все элементы от начала очереди до элемента, имеющего нулевой указатель PTR. Продвижение вдоль очереди от начала к ее концу осуществляется с помощью двух указателей: CUR и PR. Схематично продвижение указателей вдоль очереди представлено на рис. 22.

Рис. 22

Схема перемещения указателей вдоль очереди от начала к ее концу для включения нового элемента

При этом анализируется значение CUR:

1) если CUR <> NIL, т. е. очередь не пуста, то производится движение вдоль
очереди; для этого:

PR   := CUR; - указатель предыдущего элемента адресует текущий;

CUR := CUR^.PTR; - указатель текущего элемента переключается на элемент, следующий после него; после чего анализ значения CUR повторяется;

2) если CUR  =  NIL, движение вдоль очереди прекращается; это может быть
в случае, если:

а) достигнут конец очереди;

б) очередь пуста; продвижения вдоль очереди не было, т. е. остались первоначальные значения: CUR =  PR = NIL.

Распознавание этих ситуаций производится из анализа PR:

1) если PR   =   NIL,  т. е.  очередь пуста, движения вдоль очереди не было и PR = CUR  =NIL; при этом новый элемент становится ее первым и последним элементом: указатель ее начала (вершины) получает значение адреса нового элемента: Q   := NOV;

2) если PR  <>  NIL, т. е. было движение вдоль очереди, PR адресует последний элемент старой (недополненной) очереди и к этому элементу присоединяется новый последний элемент очереди: PR^.PTR  :=  NOV; -"Вы,  ' NOV' ,-за. мною!".

На этом выполнение процедуры DOP завершается.

Функция UD предназначена для удаления элемента из начала (вершины) очереди. Формальные параметры функции UD:

Q - указатель на очередь, параметр-переменная;

ERR  -  признак  успешности  удаления  элемента  из  очереди  -  параметр-переменная типа BOOLEAN.

Локальная переменная функции UD:

OLD - указатель на старый, удаляемый элемент.

Начальное значение локальной переменной: OLD = Q; - указатель на вершину очереди.

В функции UD анализируется значение Q:

1) если Q <> NIL, т. е. очередь не пуста, возвращаются: OLD^ .INF - удаляемая информация;

Q   :=   Q^.PTR; - указатель на новое начало очереди, т. е. на ее следующий элемент; ERR   := FALSE; - признак успешности удаления;

освобождается ОП удаляемого элемента: DISPOSE   (OLD);.

2) если Q = NIL, т. е. очередь пуста, возвращаются:

ERR   : = TRUE; - признак неуспешности удаления элемента; значение UD   :=   0;.

Таким образом, функция UD возвращает в качестве результатов:

1) в случае успешного удаления - значения:

Q - указателя на новую вершину очереди (через параметр);

ERR = FALSE - признак успешного удаления (через параметр);

UD   := OLD^.INF; - информацию удаленного элемента очереди;

2) в случае неуспешного удаления - если очередь пуста и удаления элемента
не происходит:

Q - неизмененное значение указателя;

0 - удаленная информация;

ERR = TRUE - признак неуспешного удаления.

Функция СНТ предназначена для считывания и возврата информации из элемента начала (вершины) очереди, если она не пуста, и возврата значения 0, если очередь пуста. Формальный параметр функции СНТ: Q - указатель на конец очереди. Признак успешности чтения имеет те же значения, что и при выполнении функции UD. Чтение элемента из начала (вершины) очереди аналогично чтению элемента из вершины стека.

Список

Список - это соединение элементов в порядке убывания или возрастания ключевого признака - одного из элементов записи, из которых состоит список. Каждый элемент списка может быть достаточно сложной структуры.

Базовые операции над списком:

  1.  добавление нового элемента в список;
  2.  удаление из списка элемента, заданного поисковым признаком;
  3.  поиск в списке и вывод заданного элемента;
  4.  чтение и вывод всех элементов списка;
  5.  уничтожение списка путем освобождения ОП, занимаемой его элементами.

Рассмотрим однонаправленный список с записями типа STUD, содержащими сведения о студентах. Элементы списка будут расположены в списке в порядке возрастания ключей - значений NZ - номеров зачеток, одного из элементов записи STUD.

Программа тестирования списка приведена в листинге 39.

Листинг 39. Тестирование списка.

TYPE  PSTUD =   ^STUD; {   -  указатель   на  запись }

STUD = RECORD {   Запись   в  составе: }

FIO   :   STRING[20]; {  -  фамилия  студента }

NZ      :   INTEGER;   {   -  номер  зачетки }

RS      :   REAL;  {   -  размер  стипендии }

 PTR : PSTUD {- указатель на следующий элемент списка}

END;

VAR  SPIS:PSTUD; I:INTEGER; ERR:BOOLEAN;

{ Инициализация типизированных констант-записей }

CONST ST1:STUD=(FIO:'ИВАНОВ И.И.';NZ : 12; RS:50; PTR: NIL);

ST2 : STUD = (FIO: 'ПЕТРОВ П.П.'; NZ: 13; RS: 40; PTR: NIL);

ST3 : STUD = (FIO: 'СИДОРОВ С.С.1; NZ: 14; RS: 30; PTR: NIL);

{      Вывод данных  одной  записи      }

PROCEDURE   P (ST:STUD);

BEGIN  WRITELN (ST.FIO:15, ST.NZ:4, ST.RS:7:2);      END;

{      Проверка  пустоты списка  -     }

FUNCTION  PP( S : PSTUD): BOOLEAN;

BEGIN

IF S=NIL THEN BEGIN WRITELN ('СПИСОК ПУСТ'); PP:=TRUE END

ELSE PP := FALSE

END;

{   Дополнение списка одной новой записью   }

PROCEDURE DOP ( VAR S : PSTUD; DAT :STUD );

VAR NOV, CUR, PR : PSTUD;  KEY : INTEGER;

BEGIN

CUR := S; PR:=NIL; KEY:=DAT.NZ; WRITELN('KEY =', KEY);

    NEW ( NOV );  NOV^ := DAT;

WHILE (CUR <> NIL) AND (CUR^.NZ < KEY) DO BEGIN

PR:=CUR; CUR:=CUR^.PTR;  { - движение вдоль списка }

END;

NOV^.PTR:=CUR;  {- подключение нового элемента справа} {   Подключение нового элемента слева:  }

IF PR = NIL THEN      S := NOY   { - в начало списка   } ELSE PR^. PTR := NOV      { - в середину списка }

END;

{   Вывод данных списка   }

PROCEDURE CHT ( S : PSTUD );

VAR CUR : PSTUD;

BEGIN  WRITELN ('- ЧТЕНИЕ СПИСКА - ');   CUR := S;

IF PP ( S ) THEN EXIT;  { - проверка пустоты списка } WHILE CUR <> NIL DO BEGIN

P(CUR^); CUR:=CUR^.PTR; {-вывод и движение вдоль списка }

END END;

{   Поиск в списке по заданному значению ключа   }

PROCEDURE POISK ( S : PSTUD; TNZ : INTEGER );

VAR CUR : PSTUD;

BEGIN   WRITELN ( 'ПОИСК TNZ = ', TNZ );

IF PP ( S ) THEN EXIT; { - проверка пустоты списка }

CUR := S; { Движение вдоль списка:  }

WHILE(CUR<>NIL) AND (CUR^.NZ<>TNZ) DO CUR := CUR^.PTR; IF CUR = NIL THEN WRITELN(' ПОИСК НЕУСПЕШЕН')

  ELSE P(CUR^);{ - вывод найденного элемента списка } END;

{ Удаление из списка записи с заданным значением ключа  }

PROCEDURE UD (VAR S:PSTUD; TNZ : INTEGER );

VAR CUR,PR:PSTUD; BEGIN  WRITELN('УДАЛЕНИЕ TNZ = ',TNZ);

IF PP ( S ) THEN EXIT; { - проверка пустоты списка }

CUR := S; PR := NIL;

WHILE (CUR<>NIL) AND (CUR^.NZ<>TNZ) DO BEGIN  {Движение} PR := CUR; CUR := CUR^.PTR;      END; { - вдоль списка } IF CUR = NIL THEN BEGIN WRITELN ( 'УДАЛЕНИЕ НЕУСПЕШНО'); EXIT END;

P (CUR^);   IF PR = NIL THEN BEGIN

WRITELN('УДАЛЯЕМ 1-Й ЭЛЕМЕНТ СПИСКА: '); S := CUR^.PTR;  END ELSE BEGIN

WRITELN('УДАЛЯЕМ НЕ 1-Й ЭЛЕМЕНТ СПИСКА:'); PR^.PTR := CUR^.PTR; END;

DISPOSE (CUR); { - освобождение ОП }

END;

{   Уничтожение списка и освобождение ОП   }

PROCEDURE OSV ( VAR S : PSTUD );

VAR CUR, PR : PSTUD;

BEGIN   WRITELN (' СПИСОК УНИЧТОЖАЕТСЯ !!');

IF PP ( S ) THEN EXIT; { - проверка пустоты списка }

CUR := S;  PR := NIL; WHILE CUR 0 NIL DO BEGIN

PR := CUR; CUR := CUR^.PTR; DISPOSE(PR);

END;

S:=NIL {- обнуление указателя на начало списка}
END;
{       ОСНОВНАЯ     ПРОГРАММА    }

BEGIN  ASSIGN(OUTPUT, 'SPISOK.RES') ; REWRITE(OUTPUT) ;

SPIS := NIL;

WRITELN (#10#13,

'ПРОВЕРКА ПУСТОТЫ СПИСКА ЧТЕНИЕМ, ПОИСКОМ И УДАЛЕНИЕМ'); СНТ (SPIS);   POISK(SPIS, 12);   UD ( SPIS, 12 );

WRITELN ( 'ЗАПОЛНЕНИЕ СПИСКА ');

DOP (SPIS, ST1); DOP (SPIS, ST3);

DOP (SPIS, ST2); CHT(SPIS);

WRITELN ('ПОИСК ЭЛЕМЕНТОВ СПИСКА ПО ЗАДАННОМУ ЗНАЧЕНИЮ КЛЮЧА ');

POISK(SPIS, 13); POISK(SPIS, 12); POISK(SPIS, 5); POISK(SPIS, 14);

WRITELN('УДАЛЕНИЕ ДАННЫХ ИЗ СПИСКА И ПРОВЕРКА ПОИСКОМ:'); UD(SPIS,13); POISK(SPIS,13); UD(SPIS,12); POISK(SPIS,12); WRITELN(' ДОПОЛНЕНИЕ СПИСКА ');

DOP(SPIS,ST3); DOP(SPIS,ST1); DOP(SPIS,ST2);DOP(SPIS,ST2);

CHT(SPIS);

WRITELN(' УНИЧТОЖЕНИЕ СПИСКА ');   OSV (SPIS);

WRITELN ('ПРОВЕРКА ПУСТОТЫ СПИСКА ЧТЕНИЕМ' ); СНТ (SPIS); END.

В программе листинга 39 указатель SPIS всегда содержит адрес первого элемента списка (его начала). Все элементы списка связаны между собой с помощью указателей PTR (см. рис. 19). Значение указателя в последнем элементе списка (содержащем максимальное значение NZ) равно NIL. Первоначальное значение указателя на вершину списка SPIS = NIL - список пуст.

Процедуры программы листинга 39:

DOP - дополнение списка новым элементом;

UD - удаление из списка требуемого элемента;

POISK - поиск и вывод данных требуемого элемента списка;

OSV - освобождение ОП списка, уничтожение списка;

СНТ - чтение и вывод всех данных списка;

Р - вывод данных одного элемента списка.

С помощью функции РР производится анализ пустоты списка. В процессе тестирования списка с помощью программы листинга 39 производится:

проверка пустоты списка с помощью процедур СНТ, POISK и UD;
-  заполнение списка
SPIS содержимым записей ST1, ST2 и ST3;

чтение заполненного списка с помощью процедуры СНТ;

поиск и вывод содержимого заданных элементов списка для успешного и
неуспешного поиска;

удаление заданного элемента списка (например, с TNZ   =   13) и после
дующий неуспешный поиск этого элемента;

дополнение списка с последующим успешным поиском;

уничтожение списка с последующим чтением пустого списка.

Процедура  DOP предназначена для дополнения списка новым  элементом, т. е. включения в список нового элемента без нарушения его упорядоченности. Формальные параметры процедуры DOP:

S - указатель на начало (вершину) списка, параметр-переменная;

DAT - запись типа STUD, содержащая информацию для нового элемента списка, параметр-значение.

Локальные переменные процедуры DOP:

CUR - указатель текущего (очередного) элемента списка;

PR - указатель предыдущего (перед CUR) элемента списка;

NOV - указатель на новый элемент списка;

KEY - значение ключа - номера зачетки нового элемента списка.

Схема алгоритма процедуры DOP представлена на рис. 23.

Рис. 23

Схема алгоритма процедуры DOP - включения в список нового элемента

Начальные значения локальных переменных:

CUR := S; - указывает на начало (вершину) списка; если список пуст, S = NIL;

PR   := NIL; - не указывает ни на что;

KEY   := DAT.NZ; - значение ключа нового элемента списка.

В процедуре DOP с помощью процедуры NEW (NOV); для нового элемента списка выделяется ОП, адрес начала которой запоминается в NOV -


 

А также другие работы, которые могут Вас заинтересовать

77173. PR И РЕКЛАМА В СРЕДСТВАХ МАССОВОЙ ИНФОРМАЦИИ КАК ЧАСТЬ СИСТЕМЫ БАНКОВСКОГО МАРКЕТИНГА 398.5 KB
  Актуальность выбранной темы определяется также тем, что усиливается необходимость анализа некоторых аспектов деятельности коммерческих банков, нацеленных на вхождение России в мировое хозяйство.
77176. Формирование кадровой политики в ООО «Идеальные окна» 343.35 KB
  Сущность и содержание кадровой политики Кадровая политика организации –генеральное направление кадровой работы совокупность принципов методов форм организационного механизма по выработке целей и задач направленных на...
77177. Проблемы и препятствия на пути воздействия на трудовую мотивацию персонала. Пути совершенствования мотивации труда 324.5 KB
  Государственное управление заключает в себе огромный материальный и человеческий риск. Это прежде всего высокие затраты, опасность ущемления общественного благосостояния, и, вызванная последним, низкая репутация чиновничества и государства в целом в глазах общественности.
77178. Рассмотрите причины конфликтных ситуаций, разработайте программу оптимизации социально-психологического климата в коллективе 316 KB
  Конфликты занимают особое место в жизни человека и общества. Управление ими в организации является одним из важнейших направлений в деятельности руководителя. Конфликт – явление, знакомое каждому человеку.
77179. Разработать систему материального стимулирования сотрудника для повышения эффективности работы предприятия 292.5 KB
  Истинные причины, побуждающие работника максимально прикладывать усилия в работе определить нелегко. Этими условиями являются его желание, возможности, квалификация и, конечно же, мотивация - то есть побуждение. Потребности – это внутренние побуждения к действию.
77180. Технологии проведения политических избирательных кампаний 274 KB
  Это позволяет говорить об избирательной кампании которую в наиболее общем виде можно определить как всю совокупность действий предпринимаемых партиями избирательными объединениями или кандидатами и их командами для достижения своих предвыборных целей.
77181. Product Placement: вчера, сегодня, завтра 263.5 KB
  Приведем пример одной из самых культовых фигур сегодняшнего общества - Санта Клауса. Его история веками передавалась из поколения в поколение в легендах и фольклоре. Но образ Санты, хотя и опирается на могучие традиции, очень многим обязан процессу коммерциализации, происходившему в обществе.