Формирование с помощью указателей однонаправленного списка по принципу стека, поиск элемента

Динамическая память позволяет реализовать широко используемую в некоторых программах организацию данных в виде списков (рис. 2).

Однонаправленный список

Каждое звено списка имеет информационное поле и указатель на следующее звено. В указатель последнего звена списка записывается Nil – это является концом списка.

Списки могут быть сформированы двумя способами:

- по принципу стека (звенья в списке будут следовать в порядке, обратном порядку их поступления);

- по принципу «очереди» (звенья в списке будут следовать в порядке их поступления).

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

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

Задача

Написать программу, включающую в себя подпрограммы формирования линейного списка по принципу стека, поиска в списке L звена с первым вхождением элемента Е, если такой есть, вывода списка на экран. Значения информационных полей и искомый элемент Е – значения типа Integer.Сформированный по принципу стека список

Program Primer1; Uses Crt; Type Spisok = ^ Zveno; Zveno = Record Elem : Integer; Next : Spisok; End; Var L : Spisok; E : Integer; Procedure Form(Var L1 : Spisok); Var Sym : Char; X : Spisok; Begin X:=Nil; Repeat New(L1); Writeln(‘Введите элемент звена’); Readln(L1^.Elem); L1^.Next:=X; X:=L1; Write(‘Будете вводить еще (Y/N)’); Readln(Sym); Until Upcase(Sym)=’N’; End; Procedure Search(L1: Spisok; E1: Integer); Var Flag : Boolean; Begin Flag:=False; While (L1 <> Nil) and (not Flag) Do If L1^.Elem = E Then Flag:=True; Else L1:=L1^.Next; If Flag Then Writeln(‘Е=’,E,’ найден’); Else Writeln(‘Е=’,E,’ не найден’); End; Procedure Wywod(L1 : Spisok); Var P : Spisok; Begin P:=L1; While P <> Nil Do Begin Write(P^.Elem,’ ‘); P:=P^.Next; End; Writeln; End; Begin Clrscr; Form(L); Writeln(‘Вывод исходного списка’); Wywod(L); Writeln(‘Е – искомый элемент’); Writeln(‘Введите Е>’); Readln(E); Search(L,E); Readkey; End.

{тип – указатель на тип-запись} {тип - запись} {информационное поле записи} {указатель на следующее звено списка} {указатель} {искомый элемент списка} {процедура формирования списка} {по принципу стека} {ответ о продолжении формирования списка} {рабочая переменная} {см. пояснения к программе ниже} {заем памяти из кучи} {конец процедуры Form} {процедура поиска элемента Е} {флаг того, что Е был найден} {элемент Е еще не найден} {пока не конец списка и не найден Е} {если текущий элемент равен Е} {то установка флага} {иначе переход к следующему элементу} {если Е был найден} {то вывод «Элемент Е найден»} {иначе вывод «Элемент Е не найден»} {конец процедуры Search} {процедура вывода списка на экран} {конец процедуры вывода списка} {начало основной программы} {очистка экрана} {формирование списка (стек)} {вывод исходного списка на экран} {ввод элемента Е для поиска} {поиск элемента Е } {ожидание нажатия любой клавиши} {конец программы}