Если список формируется по принципу «очереди», то звенья в списке следуют в порядке их поступления.
Задача. Написать программу, включающую в себя подпрограммы формирования линейного списка по принципу «очереди», поиска в списке L звена с первым вхождением элемента Е, если такой есть, вывода списка на экран. Значения информационных полей и искомый элемент Е – значения типа Integer.Сформированный по принципу «очереди» список
| Program Primer2; 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; Pr, X: Spisok; Begin L1:= Nil; Repeat New(X); If L1 = Nil Then L1:=X Else Pr^.Next:=X; Writeln(‘Введите элемент звена’); Readln(X^.Elem); Pr:=X; Write(‘Продолжить (Y/N)’); Readln(Sym); Until (Sym=’N’) or (Sym=’n’); X^.Next:=Nil; End; Procedure Search(Var L1: Spisok; E1: Integer); Var Flag: Boolean; Begin Flag:=False; While (L1 <> Nil) and (not Flag) Do If L2^.Elem = E Then Flag:=True Else L1:=L1^.Next; If Flag Then Writeln(‘Е=’,E,’ найден’); Else Writeln(‘Е=’,E,’ не найден’); End; Procedure Wywod(L1: Spisok); Begin While L1 <> Nil Do Begin Write(L^.Elem,‘ ’); L1:=L1^.Next; End; Writeln; End; Begin Clrscr; Form(L); Writeln(‘Вывод исходного списка’); Wywod(L); Writeln(‘Введите элемент Е для поиска’); Readln(E); Search(L,E); Readkey; End. | {тип –указатель на тип-запись} {тип - запись} {информационное поле записи} {указатель на следующее звено списка} {указатель} {удаляемый элемент списка} {процедура формирования списка} {по принципу «очереди»} {ответ о продолжении формирования списка} {рабочие переменные} {см. пояснения к программе ниже} {заем памяти из кучи} {конец процедуры Form} {процедура поиска элемента Е} {флаг того, что Е был найден и удален} {элемент Е еще не найден} {пока не конец очереди и не найден элемент Е} {если текущий элемент равен Е} {то установка флага} {иначе переход к следующему элементу} {если Е был найден} {то вывод «Элемент Е найден»} {иначе вывод «Элемент Е не найден»} {конец процедуры Search} {процедура вывода списка на экран} {конец процедуры вывода списка} {начало основной программы} {очистка экрана} {формирование списка (очередь)} {вывод исходного списка на экран} {ввод элемента Е для поиска} {поиск элемента Е, если он есть} {конец программы} |
Пояснения к программе
В разделе описания типов объявлен тип Zveno, содержащий следующие поля: Elem – элемент звена (информационное поле), Next – указатель на следующее звено.
Формирование списка из трёх звеньев по принципу «очереди»:
а) L1:=Nil; в) New(X);
New(X); Pr^.Next:=X;
Readln(X^.Elem);
Pr:=X;
б) L1:=X; г) New(X);
Readln(X^.Elem); Pr^.Next:=X;
Pr:=X; Readln(X^.Elem);
Pr:=X;
X^.Next:=Nil;
В процедуре Form вначале переменная L1 полагается равной Nil, и выделяется динамическая память под 1-ое звено (переменная Х – указатель на 1-ое звено). Далее, если L1 равно Nil, в L1 заносится указатель на первое звено, т. е. в L1 будет находиться указатель на начало списка. В поле Elem этого звена с клавиатуры вводится 1-й элемент. В переменной Pr запоминается указатель на 1-ое звено.
После этого выделяется память под 2-ое звено (переменная Х – указатель на 2-ое звено). В поле Next 1-ого звена копируется значение переменной Х, т. е. в это поле заносится указатель на 2-ое звено. Затем заполняется поле Elem 2-ого звена. После этого в переменной Pr запоминается указатель на 2-ое звено.
Аналогично формируется 3-е звено. В поле Next последнего звена заносится Nil. Таким образом, список будет содержать звенья, связанные между собой, причем, 1-ое звено будет стоять в начале списка, а последнее – в конце. В переменной L1 будет находиться указатель на начало списка.
В процедуре Search осуществляется последовательный перебор элементов списка, пока не будет найден искомый элемент или не достигнут конец списка. В конце процедуры на экран выводится соответствующее сообщение.
Процедура Wywod выводит элементы всех звеньев списка до и после удаления. Для вывода списка используется переменная L1, при этом адрес начала не изменяется, т. к. L1 – параметр–значение.