Пояснения к программе
В разделе описания типов объявлен тип 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 – параметр–значение.
Формирование с помощью указателей однонаправленного списка по принципу «очереди», поиск элемента
Если список формируется по принципу «очереди», то звенья в списке следуют в порядке их поступления.
Задача. Написать программу, включающую в себя подпрограммы формирования линейного списка по принципу «очереди», поиска в списке 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} {процедура вывода списка на экран}
{конец процедуры вывода списка} {начало основной программы} {очистка экрана} {формирование списка (очередь)}
{вывод исходного списка на экран}
{ввод элемента Е для поиска} {поиск элемента Е, если он есть}
{конец программы} |