1611678431-0e68e83522cb9d960ac896aa5d90854d (826635), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

Связь междуэлементами можно осуществить за счёт хранения в одном элементе адреса другого такого жеэлемента (того же типа). Т.е. каждый информационный элемент содержит внутри себя указатель насобственный тип. Учитывая, что кроме этого указателя должны присутствовать полезные данные, типинформационного элемента оказывается записью. Например, для простейшего вида списка этот типможет быть следующим (на языках Си/Си++):struct Link1{int data;Link1* next;};пример 1Классификация связных списков. По числу связей (и одновременно, направлению) спискибывают односвязными (однонаправленными), двусвязными (двунаправленными) и многосвязными.По способу организации связей (или по архитектуре) списки могут быть линейными икольцевыми (циклическими). (Если список не является ни линейным, ни кольцевым, то остаётсяединственный вариант – ветвящийся список, фактически являющийся одной из древовидных структурданных.)По степени упорядоченности хранимых данных списки могут быть упорядоченными инеупорядоченными.

Такое разделение иногда бывает удобно на практике, но для поддержанияупорядоченности списков приходится прибегать к специальным мерам.Для списков, по сравнению с очередями и стеками, имеется значительно больше операций,которые включают в себя: добавление нового звена списка (вставка звена); удаление звена; просмотр (или прохождение) списка; поиск данных в списке; создание ведущего (заглавного) звена (при необходимости); сортировка списка; обращение (реверсирование) списка, т.е. перестановка всех его звеньев в обратномпорядке.Линейный односвязный списокЛинейный односвязный список является самым простым видом связных списков. Такойсписок можно определить с помощью описаний типов (см.

пример 1).Процедуры работы с линейным односвязным списком на языке Паскаль:Typerel1 = ^elem; (* Указатель на запись *)elem = recordnext: rel1;data: <Тип хранимых данных> (* Любой допустимый тип данных *)end;varL1: rel1;Для того, чтобы такие операции, как добавление или удаление звена, выполнялисьодинаково, независимо от места их выполнения в списке, удобно использовать ведущее илизаглавное звено - самое первое звено списка, в котором не обязаны храниться полезные данные. Егосоздание для односвязного списка можно осуществить следующим образом:var a, L1: list1;begin...new(L1);L1^.next := nil;a := L1;...Указатель на начало списка L1, значением которого является адрес ведущего звена,представляет список как единый программный объект.Указатель на следующий элемент в последнем звене списка имеет значение nil (NULL илипросто 0 в Си/Си++), что является признаком линейного списка.procedure insert1(link: rel1; info: <Тип>);var q: rel1;beginnew(q);q^.data := info;q^.next := link^.next;link^.next := qend;procedure delete1(link:rel1);var q: rel1;beginif link^.next <> nil thenbeginq := link^.next;link^.next := link^.next^.next;dispose(q);endend;function search1(l: rel1; info: <Тип>; var r: rel1):boolean;var q: rel1;beginsearch1 := false;r := nil;q := l^.next;while (q <> nil) and (r <> nil) dobeginif q^.data = info thenbeginsearch := true;r := qend;q := q^.nextendend;Процедуры добавления и удаления звеньев являются критическими с точки зрениясохранения целостности списка.

При неправильном выполнении этих процедур (т.е. при неправильнойочерёдности выполнения операций присваивания) возможны 2 ошибочные ситуации:1. Список "рвётся" по месту вставки или удаления звена, и звено, оказавшее последним,замыкается либо само на себя (чаще всего) (т.е. указатель next или аналогичный ему в этом звенеполучает значение адреса этого же звена), либо на одно из предшествующих звеньев (в зависимостиот неправильной реализации операций вставки или удаления звена). При попытке просмотра спискапроцедура просмотра зацикливается и бесконечно выводит содержимое одного и того же звена (илинескольких звеньев).2. Список так же "рвётся" по месту вставки или удаления звена, но указатель в звене, ставшемпоследним, получает какое-то произвольное значение, которое трактуется как адрес следующегозвена (реально не существующего), у которого также есть указатель next, содержащий какой-то адрес,и так далее, до тех пор, пока случайно не попадётся блок данных, для которого указатель next небудер равен нулю.

При попытке просмотра списка на дисплей сначала выводятся правильные данные,а затем случайный набор символов.В обоих случаях к звеньям в "оторвавшейся" части ("хвосте") списка больше нет доступа, ихранящиеся в них данные можно считать потерянными.Для предовращения возникновения таких ошибок следует соблюдать правильный порядокпроведения связей (т.е. присваивания указателей) при вставке нового звена и удалениисуществующего (очерёдность операций указана):Добавление звена в произвольную позицию за ведущим звеном:struct Link1{int data;Link1* next;};void Insert1(Link1* link, int data) // link - звено, за которым вставляется новое{Link1* q = new Link1; // 1 Выделение памяти под новое звеноq->data = data;// 2 Ввод данныхq->next = link->next; // 3 Проведение связи от нового звена к следующемуlink->next = q;// 4 Проведение связи от "старого" звена у новому}Возможность перемещаться по 1-связному списку только в одном направлении приводит ктому, что при удалении звена приходится задавать не реально удаляемое звено, а предшествующееему.

Это делается для того, чтобы можно было скорректировать связь для предшествующего звена,добраться до которого от удаляемого иначе невозможно.Удаление звена из любого места списка за ведущим звеном:void Delete1(Link1* link) // link - звено, предшествующее удаляемому{Link1* q;if (link->next)// Проверка на наличие звена, следующего за link{q = link->next // 1 Запоминание удаляемого звена для операции deletelink->next = q->next; // 2 Проведение новой связи в обход удаляемого звенаdelete q;// 3 Очистка памяти}}Одной из наиболее простых операций со всеми типами списков является их прохождение, т.е.поочерёдное получение доступа ко всем элементам.

Приведём процедуру, реализующую этуоперацию для просмотра списка (другие варианты использования прохождения – поиск данных исохранение списка в файл). В случае перемещения по 2-связному списку в "прямом" направлении этапроцедура является одинаковой для 1- и 2-связного линейных списков.Просмотр 1-связного линейного спискаvoid Show(Link1* link){Link1 *q = link->next; // Учитывается наличие "пустого" ведущего звенаwhile (q)// или while(q!=NULL){cout<<q->data<<' '; // или другая операцияq = q->next;// Переход по списку}cout<<endl;}Поиск в списке является вариантом операции просмотра и отличается тем, что:1.

вместо операции вывода на экран (cout<<q->data) используется операция сравненияискомых данных с хранящимися в звеньях списка;2. если искомые данные найдены, нет необходимости перемещаться по списку дальше.Поиск в односвязных списках имеет следующую особенность. Если он выполняется всочетании с удалением, то результатом поиска может (или должно) быть не то звено, в которомсодержатся искомые данные, а предшествующее ему. В итоге для поиска в списке могутпотребоваться либо две различные процедуры – "обычная" и находящая предыдущее звено, либоодна универсальная, позволяющая найти оба звена – с искомыми данными и предшествующее ему.Рассмотрим в качестве примера именно этот вариантУниверсальная процедура поиска (находит звено с ключом поиска и предшествующее ему)int Search(Link1* Start, // Точка начала поискаLink1*& Find,// Указатель для звена с искомыми даннымиLink1*& Pred,// Указатель для предыдущего звенаint Key)// Ключ поиска{Link1* Cur = Start->next; // Текущее звеноPred = Start; // Предыдущее звено ("отстаёт" на 1 шаг от текущего)int Success = 0; // Признак успеха поиска (установлен в 0)while (Cur && !Success) // Операция логическое "И"{if (Cur->data == Key) // нашли{Find = Cur; // Запоминание найденного звенаSuccess = 1; // Установка в 1 признака успехаbreak; // Выход из цикла при удачном поиске}Pred = Cur; // Перемещение предыдущего звенаCur = Cur->next; // Переход по списку вперёд}return Success;}Следует отметить, что возможны разные (в том числе более короткие) варианты реализациитакого алгоритма, например, без переменной Success (вместо неё используется указатель Find,который до начала поиска должен получить значение NULL и сохранить его при неудачном поиске).Процедура, которая находит только искомое звено, является более простой, – в ней не нуженуказатель Pred и все операторы, в которых он используется.Похожая процедура применяется для 1-связного кольцевого списка.

Отличие её отрассмотренного примера заключается в условии продолжения цикла в операторе while:while(Cur != Start && !Success) // Для кольцевого спискаВедущее (или заглавное) звено. Все приведённые выше примеры на языке Си++подразумевают наличие в списке ведущего звена. Создаваться это звено может либо отдельнойпроцедурой, либо следующим набором операторов (эти же операторы и будут находиться впроцедуре):Link1 *L1 = new Link1; // Выделение памяти под звеноL1->next = NULL; // Ведущее звено одновременно является последнимВозможна работа со связным списком и без выделенного ведущего звена, т.е. первое звеноявляется обычным, в нём содержатся полезные данные.

Характеристики

Список файлов ответов (шпаргалок)