1.2 Абстрактный тип данных «список»
В математике список представляет собой последовательность элементов определенного типа: а1,а2, …..аn, гдеn≥0 и всеаiимеют один тип. Количество,n– длина списка, еслиn ≥ 1, тоа1– первый элемент, ааn– последний, в случаеn= 0 имеем пустой список.
Списки являются чрезвычайно гибкой структурой: их легко сделать большими или меньшими; их элементы доступны для вставки или удаления в любой позиции списка. Списки можно объединять или разбивать на меньшие списки.
При реализации списков с помощью массивов их элементы располагаются в смежных ячейках массива. Это представление позволяет легко просматривать содержимое списка и вставлять новые элементы в его конец. Однако вставка нового элемента в середину списка требует перемещения всех последующих элементов на одну позицию к концу массива. Операция удаления также требует перемещения элементов списка с целью освобождения ячейки.
Рассмотрим реализацию однонаправленного связанного списка с использованием указателей, связывающих последовательные элементы списка. Однонаправленный связанный список представляет собой динамическую структуру данных, число элементов которой может изменяться по мере того, как данные помещаются в список или удаляются из него. Эта реализация освобождает от непрерывной области памяти для хранения списка и, следовательно, от необходимости перемещения элементов списка при вставке или удалении элементов. Однако ценой за это удобство становится использование дополнительной памяти для хранения указателей.
В этой реализации список состоит из
ячеек, каждая из которых содержит элемент
списка и указатель на следующую ячейку
списка. Если список состоит из элементов
то дляi=1, 2,…, n-1ячейка, содержащая
элемент
,
имеет также указатель на ячейку,
содержащую элемент
.
Ячейка, содержащая элемент
,
имеет указатель nil(нуль). Имеется
также ячейкаheader(заголовок), которая
указывает на ячейку, содержащую
.
Ячейкаheaderне содержит элементов
списка. В случае пустого списка заголовок
имеет указательnil, не указывающий
ни на какую ячейку. Список, не содержащий
элементов, называется пустым или нулевым.
На рис. 1.1 показан однонаправленный
связанный список.
Рис. 1.1 Связанный список
Для однонаправленных списков удобно
использовать следующее определение
позиций элементов. Здесь для i=2, 3, … ,
nпозицияi определяется как
указатель на ячейку, содержащую указатель
на элемент
.
Позиция 1 – это указатель в ячейке
заголовка, а позицияend(L) –
указатель в последней ячейке спискаL.
Формально структуру связанного списка
можно определить следующим образом:
Основные операции, выполняемые с элементами списка: просмотр, вставка, удаление.
Ниже приведен код процедуры создания списка. Здесь строится список целых чисел, и признаком завершения построения является введенное нулевое значение в поле данных.
Procedure make(x : pt);
Var y:pt;
Begin
New(x);
Readln (x^.data);
While( x^.data <> 0) do
Begin
y:=x;
New(x);
y^.next:=x;
Readln(x^.data);
End;
y^.next:=nil;
End;
Процедура просмотра элементов списка
Процедура вставки элемента в заданную позицию списка.
Procedure Insert ( x : integer; p:pt);
Var
temp: pt;
Begin
(1) temp:= p^.next;
(2) New(p^.next);
(3) p^.next^.data:= x;
(4) p^.next^.next:=temp;
End;
Механизм управления указателями в процедуре Insert приведен на рис. 1.2. На рис. 1.2 а) показана ситуация перед выполнением процедуры вставки. Необходимо вставить новый элементxперед элементомb, поэтому в строке (1) задаетсяtempкак указатель на ячейку, содержащую элементb. В строке (2) листинга создается новая ячейка, и в полеnext ячейки, содержащей элемента, ставится указатель на новую ячейку. В строке (3) полеdata вновь созданной ячейки принимает значениех, а в строке (4) полеnextэтой ячейки принимает значение переменнойtemp, которая хранит указатель на ячейку, содержащую элементb. На рис. 1.2 б) представлен результат выполнения процедурыInsert, где пунктирными линиями показаны новые указатели и номерами, совпадающими с номерами строк в листинге, помечены этапы их создания.
Рис. 1.2 Реализация вставки элемента в список
На рис. 1.3 показана схема манипулирования указателями в процедуре удаления элемента из списка. Старые указатели показаны сплошными линиями, а новые – пунктирной. Ниже приведен код процедуры удаления элемента.
Procedure Delete ( b : integer; p:pt);
Begin
If p^.next^.data=b then
p^.next:= p^.next^.next;
End;
Рис. 1.3 Реализация удаления элемента из списка