Вопрос 6) Линейные списки.
Списки
Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера.
Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько будет произведено измерений.
Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти.
Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая.
А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое "связанный список"?
Связанный список
Каждый элемент списка состоит из двух частей: информационной части (.X1, X2 и т.д.) и указателя на следующий элемент списка (р2, р3 и т.д.).
Каждую такую пару называют звеном списка.
Последний элемент имеет пустой указатель Nil.
Добавление элемента в список:
Добавление происходит путем присоединения нового элемента к концу списка. При этом значение Nil в последнем элементе заменяется ссылкой на новый элемент цепочки.
Связанный список не занимает лишней памяти. Память расходуется в том объеме, который требуется для поступившей информации.
Описание списка
Туре Тип = ...; {Тип элемента информационного поля}
Связь = ^Звено;
Звено = Record
Элемент: Тип;
След : Связь
End;
Например:
Туре Link = ^Zveno;
Zveno = record
inf : Real;
sled : Link;
End;
Var Beg, Elem:Link;
X:real;
Формирование первого элемента списка:
New(Elem); {выделено в динамической памяти место для размещения вновь формируемого звена}
Elem^.inf:=x; {Сформировано значение поля inf}
Elem^.sled:=nil; {Cформировано значение поля sled}
Чтобы не потерять начало списка заводят вспомогательную переменную Beg, которая всегда указывает на начало списка (дескриптор списка).
Beg:=Elem; {Первый элемент списка}
Формирование следующего элемента списка.
Переменная Elem ссылается на последнее звено списка.
New(elem^.sled);
Elem:=elem^.sled;
Elem^.inf:=x;
Elem^.sled:=nil;
Переменная Elem снова ссылается на последнее звено списка.
Перебор элементов списка
Чтобы последовательно перебрать все звенья цепочки, необходимо понять способ перехода от одного звена к следующему по порядку звену:
Elem := Elem^.sled;
(Аналог i:=i+1; при работе с массивом)
Основные операции при работе со списками:
1. выделение (извлечение) первого элемента (его называют "головой" последовательности, он является результатом операции);
2. выделение "хвоста" последовательности, т.е. того, что остается, если удалить первый элемент;
3. операции, аналогичные (1) и (2), но для последнего элемента вместо первого;
4. выделение i-го элемента или элемента с данным значением компоненты;
5. выделение отрезка последовательности от i-го до j-го элемента;
Основные операции при работе со списками:
6. удаление элементов, выделенных операцией (1-5);
7. замена части последовательности, выделенной операцией (1-5), данным элементом или последовательностью;
8. включение заданного элемента или последовательности перед или после элемента, выделенного операцией (4);
9. сцепление (конкатенация,соединение) двух списков;
10. нахождение длинны списка a.
Двунаправленный список
