142 Односвязный линейный список. Добавление, удаление элементов. Вывод на экран.

Понятие "списки" включает в себя самые разные структуры данных. Это могут быть и массивы, в том числе массивы записей, и специальные динамические структуры данных, и даже деревья. Общим для них является то, что они содержат набор записей одного вида, ограниченный по размеру или неограниченный, упорядоченный или неупорядоченный. Данные, хранящиеся в этих записях, обычно логически связаны между собой. В тексте программы такая связь может выражаться в том, что все такие элементы хранятся в одном и том же массиве как непрерывном блоке памяти. Но кроме общего имени массива (и адреса его начала) между этими элементами никакой другой физической связи нет, и на физическом уровне подобные списки могут быть названы "несвязными" (или, что (почти) то же самое, "несвязанными"). Т.е. внутри них нет связей (их элементы не связаны друг с другом физически). Типичным примером незвязного (физически) списка является массив.

Связные списки

Вспомним общие черты очередей и стеков:

• Строгие правила доступа к данным;

• Операции извлечения (считывания) данных являются разрушающими.

Связные списки свободны от этих ограничений. Они допускают гибкие методы доступа; извлечение (чтение) элемента из списка не приводит к удалению его из списка и потере данных. Для фактического удаления элемента из связного списка требуется специальная процедура.

Связные спискипредставляют собой динамические структуры данных (динамические цепочки звеньев), в которых однотипные элементы (звенья) каким-либо образом связаны между собой, обычно на физическом уровне. Связь между элементами можно осуществить за счёт хранения в одном элементе адреса другого такого же элемента. Т.е. каждый информационный элемент содержит внутри себя указатель на собственный тип. Учитывая, что кроме этого указателя должны присутствовать полезные данные, тип информационного элемента оказывается записью.

Классификация связных списков. Почислу связей(и одновременно,направлению) списки бываютодносвязными(однонаправленными),двусвязными(двунаправленными) имногосвязными.

По способу организации связей(или поархитектуре) списки могут бытьлинейнымиикольцевыми(циклическими). Если список не является ни линейным, ни кольцевым, то остаётся единственный вариант - ветвящийся список, фактически являющийся одной издревовидныхструктур данных.

По степени упорядоченности хранимых данных списки могут быть упорядоченнымиинеупорядоченными. Такое разделение иногда бывает удобно на практике, но для поддержания упорядоченности списков приходится прибегать к специальным мерам.

Для списков, по сравнению с очередями и стеками, имеется значительно больше операций, которые включают в себя:

• добавление нового звена списка (вставка звена);

• удаление звена;

• просмотр (или прохождение) списка;

• поиск данных в списке;

• создание ведущего (заглавного) звена (при необходимости);

• сортировка списка;

• обращение (реверсирование) списка, т.е. перестановка всех его звеньев в обратном порядке.

Линейный односвязный списокявляется самым простым видом связных списков. Такой список можно определить с помощью описаний типов.

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

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

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

В обоих случаях к звеньям в "оторвавшейся" части списка больше нет доступа, и хранящиеся в них данные можно считать потерянными.

Для предовращения возникновения таких ошибок следует соблюдать правильный порядок проведения связей (т.е. присваивания указателей) при вставке нового звена и удалении существующего.

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

Ведущее(или заглавное) звено. Создаваться это звено может либо отдельной процедурой, либо набором операторов (эти же операторы и будут находиться в процедуре).

Возможна работа со связным списком и без выделенного ведущего звена, т.е. первое звено является обычным, в нём содержатся полезные данные. Именно такой вид списка использовался для организации стека. Ещё один пример использования подобных списков -очередь.

В остальных случаях (т.е. для обычных списков) использование ведущего звена является предпочтительным, т.к. позволяет избежать проверок при добавлении и удалении звеньев.

Недостаткиодносвязного списка заключаются в следующем:

1. По такому списку можно перемещаться только от начального звена к конечному. Начинать можно с любого звена в списке, но если вдруг возникнет необходимость обратиться к предшествующим элементам, придется начинать с начального звена, что неудобно, нерационально и усложняет алгоритмы обработки данных.

2. Наличие только одной связи снижает надёжность хранения данных в 1-связном списке.

3. Следствием первого недостатка является усложнение взаимодействия операций поиска и удаления.

Достоинствамиэтого списка являются меньший расход памяти по сравнению с другими связными динамическими структурами данных (всего 1 указатель) и простота операций.