yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Реализация списков с помощью указателей

Алгоритмы структуры данных

Реализация списков с помощью указателей

В этом разделе для реализации однонаправленных списков используются указатели, связывающие последовательные элементы списка. Эта реализация освобождает нас от использования непрерывной области памяти для хранения списка и, следовательно, от необходимости перемещения элементов списка при вставке или удалении элементов. Однако ценой за это удобство становится дополнительная память для хранения указателей.

В этой реализации список состоит из ячеек, каждая из которых содержит элемент списка и указатель на следующую ячейку списка. Если список состоит из элементов а1 , а2, ..., аn, то для і = 1, 2, ..., n-1 ячейка, содержащая элемент аi, имеет также указатель на ячейку, содержащую элемент ai+1. Ячейка, содержащая элемент аn, имеет указатель nil (нуль). Имеется также ячейка header (заголовок), которая указывает на ячейку, содержащую а1. Ячейка header не содержит элементов списка(oбъявление ячейки заголовка "полноценной" ячейкой (хотя и не содержащей элементов списка) упрощает реализацию операторов списка на языке Pascal. Можете использовать указатели на заголовки, если хотите каким-либо специальным способом реализовать операторы вставки и удаления в самом начале списка.). В случае пустого списка заголовок Имеет указатель nil, не указывающий ни на какую ячейку. На рис. 2.2 показан связанный список описанного вида.

 

 

 

 

 

Для однонаправленных списков удобно использовать определение позиций элементов, отличное от того определения позиций, которое применялось в реализации списков с помощью массивов. Здесь для і = 2, 3, ..., п позиция і определяется как указатель на ячейку, содержащую указатель на элемент ai. Позиция 1 — это указатель в ячейке заголовка, а позиция END(L) — указатель в последней ячейке списка L.

Бывает, что тип списка совпадает с типом позиций, т.е. является указателем на ячейку, реже на заголовок:  Формально определить структуру связанного списка  можно следующим образом:

 

type

celltype = record

element:   elementtype;

next:   ↑ celltype

end;

LIST  =  ↑ celltype;

position = ↑ celltype;

В листинге 2.3 показан код функции END(L). Результат функции получаем путем перемещения указателя q от начала списка к его концу, пока не будет достигнут конец списка, который определяется тем, что q становится указателем на ячейку с указателем nill. Отметим, что эта реализация функции END неэффективна, так как требует просмотра всего списка при каждом вычислении этой функции. Если необходимо частое использование данной функции, как в программе PURGE (листинг 2.1), то можно сделать на выбор следующее.

1.    Применить представление списков, которое не использует указатели на ячейки.

2.    Исключить использование функции END(L) там, где это возможно, заменив ее другими операторами. Например, условие р <> END(L) в строке (2) листинга 2.1 можно заменить условием p↑.next <> nill, но в этом случае программа становится зависимой от реализации списка.

 

Листинг 2.3.

function END  (  L:   LIST  ) :   position;

{ END возвращает указатель на последнюю ячейку списка L }

var

q:   position;

begin

(1)          q: =  L;    

(2)          while q↑.next <> nil do

(3)                     q:= q↑.next;

(4)          return (q)

end;   {  END  }

 

Листинг 2.4 содержит процедуры для операторов INSERT, DELETE, LOCATE и MAKENULL, которые используются в реализации списков с помощью указателей. Другие необходимые операторы можно реализовать как одношаговые процедуры, за исключением PREVIOUS, где требуется просмотр списка с начала. Мы оставляем написание этих процедур читателю в качестве упражнений. Отметим, что многие команды не требуют параметра L, списка, поэтому он опущен.

 

 

19