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

Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Алго-

20

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

PersonList[1].Index    := 190000; PersonList[1].Name     := ^,Иванов';

PersonList[1].Adress := ^лСанкт-Петербург, ул. Б.Морская, д.67';

В памяти ЭВМ ячейки таблицы обычно располагаются построчно, непрерывно, в соседних ячейках. Размер памяти, занимаемой таблицей, есть суммарный размер ячеек.

1.2.6. Линейные списки

Список - это структура данных, представляющая собой логически связанную последовательность элементов списка.

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

Динамическая структура данных - это структура данных, определяющие характеристики которой могут изменяться на протяжении ее существования.

Обеспечиваемая такими структурами способность к адаптации часто достигается меньшей эффективностью доступа к их элементам.

Динамические структуры данных отличаются от статических двумя основными свойствами:

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

Для обращения к динамическим данным применяют указатели, рассмотренные выше.

Созданием динамических данных должна заниматься сама программа во время своего исполнения. В языке программирования Паскаль для этого существует специальная процедура:

New(Current);

После выполнения данной процедуры в оперативной памяти ЭВМ создается динамическая переменная, тип которой определяется типом указателя Current.

После использования динамического данного и при отсутствии необходимости его дальнейшего использования необходимо освободить оперативную память ЭВМ от этого данного с помощью соответствующей процедуры:

Dispose(Current);

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

1.2.6.1. Линейный однонаправленный список

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

Основные операции, осуществляемые с линейным однонаправленным списком:

• вставка элемента;
• просмотр;
• поиск;
• удаление элемента.

Следует обратить особое внимание на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.

Для описания алгоритмов этих основных операций используем следующие объявления: type

PElement = ATypeElement;  {указатель на тип элемента} 
TypeElement = record        {тип элемента списка} 
Data: TypeData; {поле данных элемента}

Next: PElement; {поле указателя на следующий элемент}

end; var

ptrHead: PElement; {указатель на первый элемент списка}

ptrCurrent: PElement; {указатель на текущий элемент}

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

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

procedure Ins LineSingleList(DataElem:  TypeData;

var ptrHead, ptrCurrent: PElement); {Вставка непервого элемента в линейный однонаправленный список} {справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement;      {вспомогательный указатель} begin

New(ptrAddition);

ptrAdditionA.Data := DataElem;

if ptrHead = nil then begin     {список пуст}

{создаем первый элемент списка}

ptrAdditionA.Next := nil;

ptrHead := ptrAddition; end else begin     {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

ptrAdditionA.Next := ptrCurrentA.Next;

ptrCurrentA.Next := ptrAddition; end;

ptrCurrent := ptrAddition; end;

procedure InsFirst LineSingleList(DataElem: TypeData;

var ptrHead: PElement); {Вставка первого элемента в линейный однонаправленный список} var

ptrAddition: PElement;      {вспомогательный указатель} begin

New(ptrAddition);

ptrAdditionA.Data := DataElem;

if ptrHead = nil then begin     {список пуст}

{создаем первый элемент списка}

ptrAdditionA.Next := nil; end else begin     {список не пуст}

{вставляем новый элемент слева (перед) первым элементом}

ptrAdditionA.Next := ptrHead; end;

ptrHead := ptrAddition; end;

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

Операция просмотра списка заключается в последовательном просмотре всех элементов списка:

procedure Scan LineSingleList(ptrHead:  PElement);

{Просмотр линейного однонаправленного списка} var

ptrAddition: PElement;      {вспомогательный указатель} begin

ptrAddition := ptrHead;

while ptrAddition <> nil do begin {пока не конец списка} 
writeln(ptrAdditionA.Data); {Вывод значения элемента}

ptrAddition := ptrAdditionA.Next; end; end;

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

function Find LineSingleList(DataElem:  TypeData;

var ptrHead, ptrCurrent: PElement): boolean; {Поиск элемента в линейном однонаправленном списке} var

ptrAddition:PElement;    {Дополнительный указатель} begin

if (ptrHead <> nil)

then begin    {Если существует список} ptrAddition := ptrHead; while (ptrAddition <> nil) and

(ptrAddition^A.Data <> DataElem) do {пока не конец списка и не найден элемент} ptrAddition := ptrAdditionA.Next; {Если элемент найден,

то результатом работы функции является - true} if ptrAddition <> nil then begin Find LineSingleList := true; ptrCurrent := ptrAddition; end else begin

Find LineSingleList := false; end; end else begin

Find LineSingleList:= false; end; end;

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

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

Алгоритмы удаления первого и непервого элементов списка отличаются друг от друга. Поэтому в процедуре, реализующую данную операцию, осуществляется проверка, какой элемент удаляется, и далее реализуется соответствующий алгоритм удаления:

procedure Del LineSingleList(var ptrHead,

ptrCurrent: PElement); {Удаление элемента из линейного однонаправленного списка} var

ptrAddition: PElement;      {вспомогательный указатель} begin

if ptrCurrent <> nil then begin     {вх.параметр корректен} 
if ptrCurrent = ptrHead then begin      {удаляем первый} 
ptrHead := ptrHeadA.Next; 
dispose(ptrCurrent); 
ptrCurrent := ptrHead; 
end else begin {удаляем непервый}

{устанавливаем вспомогательный указатель на элемент, предшествующий удаляемому} ptrAddition := ptrHead;

while ptrAdditionA.Next <> ptrCurrent do

ptrAddition := ptrAdditionA.Next; {непосредственное удаление элемента} ptrAdditionA.Next := ptrCurrentA.Next; dispose(ptrCurrent); ptrCurrent := ptrAddition;

end; end; end;

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

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

1.2.6.2. Линейный двунаправленный список

В этом линейном списке любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке или является пустым указателем у последнего элемента, а второй - на предыдущий элемент в списке или является пустым указателем у первого элемента (рис. 3).

Основные операции, осуществляемые с линейным двунаправленным списком те же, что и с однонаправленным линейным списком:

• вставка элемента;
• просмотр;
• поиск;
• удаление элемента.

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

Для описания алгоритмов этих основных операций используем следующие объявления:

type

PElement = ATypeElement;{указатель на тип элемента}

TypeElement = record       {тип элемента списка} 
Data: TypeData; {поле данных элемента}

Next, {поле указателя на следующий элемент}

Last: PElement; {поле указателя на предьщующий элемент}

end;

var

ptrHead: PElement; {указатель на первый элемент списка}

ptrCurrent: PElement;      {указатель на текущий элемент}

Операция вставки реализовывается с помощью двух процедур, аналогичных процедурам вставки для линейного однонаправленного списка: InsFirst LineDubleList и Ins LineDubleList. Однако при вставке последующего элемента придется учитывать особенности добавления элемента в конец списка:

procedure Ins LineDubleList(DataElem:  TypeData;

var ptrHead, ptrCurrent: PElement); {Вставка непервого элемента в линейный двунаправленный список} {справа от элемента, на который указывает ptrCurrent}

var

ptrAddition: PElement;      {вспомогательный указатель} begin

New(ptrAddition);

ptrAdditionA.Data := DataElem;

if ptrHead = nil then begin     {список пуст}

{создаем первый элемент списка}

ptrAdditionA.Next := nil;

ptrAdditionA.Last := nil;

ptrHead := ptrAddition; 
end else begin {список не пуст}

{вставляем элемент списка справа от элемента,}

{на который указывает ptrCurrent}

if ptrCurrentA.Next <> nil then {вставляем не последний}

ptrCurrentA.NextA.Last := ptrAddition; ptrAdditionA.Next := ptrCurrentA.Next; ptrCurrentA.Next := ptrAddition; ptrAdditionA.Last := ptrCurrent; end;

ptrCurrent := ptrAddition; end;

procedure InsFirst LineDubleList(DataElem: TypeData;

var ptrHead: PElement); {Вставка первого элемента в линейный двунаправленный список} var

ptrAddition: PElement;      {вспомогательный указатель} begin

New(ptrAddition); ptrAdditionA.Data := DataElem; ptrAdditionA.Last := nil;

if ptrHead = nil then begin     {список пуст}

{создаем первый элемент списка}

ptrAdditionA.Next := nil; end else begin     {список не пуст}

{вставляем новый элемент слева (перед) первым элементом}

ptrAdditionA.Next := ptrHead;

ptrHeadA.Last := ptrAddition; end;

ptrHead := ptrAddition; end;

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

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

Операция удаления элемента также осуществляется во многом аналогично удалению из линейного однонаправленного списка:

procedure Del LineDubleList(var ptrHead,

ptrCurrent: PElement); {Удаление элемента из линейного двунаправленного списка} var

ptrAddition: PElement;      {вспомогательный указатель} begin

if ptrCurrent <> nil then begin     {входной параметр корректен} if ptrCurrent = ptrHead then begin      {удаляем первый} ptrHead := ptrHeadA.Next; dispose(ptrCurrent); ptrHeadA.Last := nil; ptrCurrent := ptrHead; end else begin      {удаляем непервый}

if ptrCurrentA.Next = nil then begin     {удаляем последний} ptrCurrentA.LastA.Next := nil;

dispose(ptrCurrent); ptrCurrent := ptrHead; end else begin      {удаляем непоследний и непервый} ptrAddition := ptrCurrentA.Next; ptrCurrentA.LastA.Next := ptrCurrentA.Next; ptrCurrentA.NextA.Last := ptrCurrentA.Last; dispose(ptrCurrent); ptrCurrent := ptrAddition; end; end; end; end;

Использование двух указателей в линейном двунаправленном списке позволяет ускорить операции, связанные с передвижением по списку за счет двунаправленности этого движения. Однако элементы списка за счет дополнительного поля занимают больший объем памяти. Кроме того, усложнились операции вставки и удаления элементов за счет необходимости манипулирования большим числом указателей.