Динамическая память позволяет реализовать широко используемую в некоторых программах организацию данных в виде списков (рис. 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} {процедура вывода списка на экран} {конец процедуры вывода списка} {начало основной программы} {очистка экрана} {формирование списка (стек)} {вывод исходного списка на экран} {ввод элемента Е для поиска} {поиск элемента Е } {ожидание нажатия любой клавиши} {конец программы} |
Пояснения к программе
В разделе описания типов объявлен тип Zveno, содержащий следующие поля: Elem – элемент звена (информационное поле), Next – указатель на следующее звено.
Формирование списка из двух звеньев по принципу стека (процедура Form):
а) X:=Nil; в) New(L1);
New(L1); Readln(L1^.Elem);
Readln(L1^.Elem);
б) L1^.Next:=X; г) L1^.Elem:=X;
X:=L1; X:=L1;
В процедуре Form вначале рабочая переменная Х полагается равной Nil. С помощью процедуры New выделяется динамическая память под первое звено (переменная L1 – указатель на 1-ое звено) и в поле Elem этого звена с клавиатуры вводится 1-й элемент. В поле Next 1-ого звена копируется значение переменной Х, т.е. в поле Next 1-ого звена заносится указатель Nil. После этого в переменной Х запоминается указатель на 1-е звено. Далее формируется второе звено (переменная L1 – указатель на 2-ое звено). В поле Next 2-ого звена копируется значение переменной Х, т. е. в это поле заносится указатель на 1-ое звено. После этого в переменной Х запоминается указатель на 2-ое звено.
Этот процесс повторяется до тех пор, пока все звенья не будут сформированы. Таким образом, список будет содержать звенья, связанные между собой, причем последнее звено будет стоять в начале списка, а первое – в конце. В переменной L1 будет находиться указатель на начало списка.
В процедуре Search осуществляется последовательный перебор элементов списка, пока не будет найден искомый элемент или не достигнут конец списка. В конце процедуры на экран выводится соответствующее сообщение.
Процедура Wywod выводит элементы всех звеньев списка до и после удаления. Для вывода списка используется переменная L1, при этом адрес начала не изменяется, т. к. L1 – параметр–значение.