Основы программирования (947332), страница 39
Текст из файла (страница 39)
7.9, г);• П'Связные списки - каждый элемент включает несколько адресных полей, в которых записаны адреса других элементов или nil (рис. 7.9, д).Для описания элементов списка используют записи, например, элементодносвязного списка с двумя информационными и одним адресным полямиможет быть описан следующим образом:Туре ре = ^element;{тип указателя}element = recordname: string[16]; {информационное поле 1}telefon:string[7]; {информационное поле 2}р: ре;{адресное поле}end;Элемент двусвязного списка описывается с двумя адресными полями,например:Туре ре = ^element;{тип указателя}element = recordname: stringfldj; {информационное поле 1}telefon:string[7]; {информационное поле 2}prev: ре;{адресное поле «предыдущий»}next: ре;{адресное поле «следующий»}end;Соответственно элемент п-связного списка содержит заданное количество адресных полей.У любого списка имеется хотя бы один указатель, размещенный в статической памяти, который содержит адрес первого элемента списка или констант)^ nil, если список пуст.
Достаточно часто используют дополнительныеуказатели, в которых хранят адреса других элементов, например, адрес текущего элемента, адрес последнего элемента и т.п. Эти указатели также описываются как «указатели на элемент», например:Varfirst, last, q: ре;...В процессе выполнения программы динамические структуры создаются, обрабатываются и уничтожаются.225Часть 1. Основы алгоритмизации и процедурное программированиеРассмотрим некоторые приемы работы со списками на примере линейных односвязных списков и бинарных деревьев.7.4.
Линейные односвязные спискиЛинейные односвязные списки используют чаще других списковыхструктур, так как они сравнительно просты, но одновременно в отличие отодномерных массивов позволяют:• работать с произвольным количеством элементов, добавляя и удаляяих по мере необходимости;• осуществлять вставку и удаление записей, не перемещая остальныхэлементов последовательности.Недостатком этой структуры является то, что при поиске элемента пономеру приходится просматривать все ранее расположенные элементы, в товремя как в одномерном массиве возможен прямой доступ к элементу по индексу. К тому же реализация линейного односвязногр списка требует дополнительной памяти для хранения адресной части элементов.Рассмотрим более подробно, как выполняются основные операции с линейными односвязными списками.Исходные установки.
В начале программы необходимо описать элемент и его тип:Туре tpel=^element; {тип «указатель на элемент»}element^recordnum:mteger; {число}p:tpel;{указатель на следующий элемент}end;В статической памяти описываем переменную-указатель списка и несколько переменных-указателей, используемых при выполнении операций сосписком:Varfirst,{указатель списка - адрес первого элемента списка}n,f,q:tpel; {вспомогательные указатели}Исходное состояние «список пуст»:first :^ml;Добавление нового элемента к списку. Добавление элемента к спискувключает запрос памяти для размещения элемента и заполнение его информационной части. Построенный таким образом элемент добавляется к ужесуществующей части списка.В общем случае при добавлении элемента к списку возможны следующие варианты:2267.
Программирование с использованием динамической памяти• список пуст, добавляемый элемент станет единственным элементомсписка;• элемент необходимо вставить перед первым элементом списка;• элемент необходимо вставить перед заданным (не первым) элементомсписка;• элемент необходимо дописать в конец списка.Добавление элемента к пустому списку состоит из записи адреса элемента в указатель списка, причем в поле «адрес следующего» добавляемогоэлемента необходимо поместить nil:new(first);first ^.пит:=5;first \р:^пИ;{запрашиваем память под элемент}{заносим число в информационное поле}{записываем nil в поле «адрес следующего»}На рис.
7.10 показана последовательность операций при добавленииэлемента к пустому списку.Добавление элемента перед первым элементом списка. При выполненииэтой операции необходимо в поле «адрес следующего» переписать адреспервого элемента списка, а в указатель списка занести адрес добавляемогоэлемента (рис.
7.11):new(q);{запрашиваем память под элемент}q^.num:=4; {заносим число в информационное поле}q\p:=first; {в поле «адрес следующего» переписываем адреспервого элемента}first: =q; ... {в указатель списка заносим адрес нового элемента}Добавление элемента перед заданным (не первым). Для выполненияоперации необходимо знать адреса элементов, между которыми вставляетсяэлемент, так как адресные части этих элементов при выполнении операцииfirstfirstfirst:-nil:afirstII I\ new(first):= ^бfirst\ S \ I%^ =5;first Л пит:вI 5 101"%first Лр; =«//;гРис. 7.10.
Последовательность операций при добавленииэлемента к пустому списку:а - исходное состояние; б - запрос памяти под элемент;е - заполнение элемента; г - занесение nil в поле адреса следующего элемента227Часть I. Основы алгоритмизации и процедурное программированиеfirst1=^™firsttoЬи]new(q);q\ пит: =4;бfirstвfirstq\p:=^first;Рис. 7.11.
Последовательность операций при добавленииэлемента перед первым:а - исходное состояние; б - запрос памяти под элемент; в - заполнение элемента;г, д- шаги включения элемента в списокбудут корректироваться (рис. 7.12). Пусть f- адрес предыдущего элемента, ап - адрес следующего элемента, тогда:new(q):{запрашиваем память под элемент}q\num:=3; {заносим число в информационное поле}q\p:='n;{в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}f".p:^q;...
{в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}Минимально для вставки элемента в линейный односвязныи список необходимо знать только адрес предьщущего элемента, так как тогда адрес следующего элемента известен -поf^.p:new(q);q\num:=3;q\p:=f\p;f^.p:=q;228{запрашиваем память под элемент}{заносим число в информационное поле}{в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}...
{в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}7. Программирование с использованием динамической памятиfirstfirstfJL8~rg1qDn34ZI34 8T0Ifirst1XEEW3IEHX1S)q^.num:=3;I 3 IIfТхПЕНЗтЗЧоЛр.=л;^T Ofirstf^-p-q:Рис. 7.12. Добавление элемента перед заданным (не первым):а - исходное состояние; б - запрос памяти под элемент;в - заполнение элемента; г, д- шаги включения элемента в списокДобавление элемента в конец списка. В этом случае должен быть известен адрес элемента, после которого добавляется новый элемент (рис.
7.13):new(q):q\num:=7;q\p:=nil;f^.p:=q;...{запрашиваем память под элемент}{заносим число в информационное поле}{в поле «адрес следующего» элемента записываем nil}{в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}229Часть 1. Основы алгоритмизации и процедурное программированиеfirstfirstI'8Т01new(q);first\I IIq Л mwi: = 7;L~i-J—I/Л/?; =^;firstixr34zi3bzz^Л;?; ==«//;Рис.
7.13. Добавление элемента в конец списка:а - исходное состояние; б ~ запрос памяти под элемент;в - заполнение элемента; г.д- включение элемента в списокАнализ показывает, что этот случай можно свести к предьщущему, таккак адресная часть последнего элемента содержит nil:new(q);{запрашиваем память под элемент}q^Mum:=7; {заносим число в информационное поле}q^.p:=f^.p; {в поле «адрес следующего» нового элемента записываем nil}f^.p:=q; ...
{в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}2307. Программирование с использованием динамической памятиКомбинируя эти фрагменты, можно организовать построение списка слюбой дисциплиной добавления элементов.Пример 7.2, Разработать программу, которая строит список по типу стека из целых чисел, вводимых с клавиатуры. Количество чисел не известно,но отлично от нуля. Конец ввода - по комбинации клавиш CTRL-Z (конецфайла на устройстве ввода).Обычно построение списка по типу стека выполняется в два этапа: всписок заносится первый элемент, а затем организуется цикл добавленияэлементов перед первым:ReadLn(a);new(first);{запрашиваем память под элемент}first \пит:=а;{заносим число в информационное поле}first \р:=пИ;{записываем nil в поле, «адрес следующего»}while not EOF dobeginReadLn(a);new(q);{запрашиваем память под элемент}q\num:-a;{заносим число в информационное поле}q^.p:-first; {в поле «адрес следующего» переписываем адреспервого элемента}first:=q; {в указатель списка заносим адрес нового элемента}end; ...Пример 7.3.
Разработать программу, которая строит список по типу очереди из целых чисел, вводимых с клавиатуры. Количество чисел не известно, но отлично от нуля. Конец ввода - по комбинации CTRL-Z (конец файлана устройстве ввода).При построении списка по типу очереди сначала мы заносим в стек первый элемент, а затем организуем цикл добавления элементов после последнего, приняв во внимание, что nil необходимо разместить в адресном полетолько последнего элемента:ReadLn(a);new(first);first \пит:=а;f:=first;{запрашиваем память под элемент}{заносим число в информационное поле}{f - текущий элемент, после которого добавляетсяследующий}while not EOF dobeginReadLn(a);new(0;{запрашиваем память под элемент}q\num:-a;{заносим число в информационное поле}231Часть 1. Основы алгоритмизации и процедурное программированиеf\p:=q;f:-f\p;end;q\p:=nil;{в поле «адрес следующего» предыдущего элементазаносим адрес нового элемента}{теперь новый элемент стал последним}(в поле «адрес следующего» последнего элемента записываем nil}Этот фрагмент можно упростить, если заметить, что новый элемент ксписку можно добавлять сразу при запросе памяти:ReadLn(a);new(first);first ^.пит:=а;f:-first;{запрашиваем память под элемент}{заносим число в информационное поле}{f- текущий элемент, после которого добавляетсяследующий}while not EOF dobeginReadLn(a);new(f\p);{запрашиваем память под элемент}f:-f^'P;{теперь новый элемент стал последним}f\num:=a;{заносим число в информационное поле}end;f\p:=nil; ..• {в поле «адрес следующего» последнего элемента записываем nil}Пример 7.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
