Ссылочная реализация в динамической памяти на основе указателей

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

struct item // структура одного элемента

{ type_of_data data; // тип был определен с помощью typedef

item *next; // указатель на следующий элемент списка

};

Далее требуется определить, какие дополнительные указатели необходимы для эффективной реализации операций над списками (вспомним, что при реализации стека использовался один, а при реализации очереди — два дополнительных указателя). Рассмотрим операции вставки и удаления элементов в произвольной позиции.

На рис.2.10. схематически показан процесс вставки нового элемента между первым и вторым элементами списка.

Рис.2.10. Вставка нового элемента в произвольную позицию списка.

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

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

 

Рис. 2.11. Удаление элементов однонаправленного списка

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

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

Отсюда вывод: для того, чтобы реализовать АТД «Однонаправленный список с выделенным текущим элементом», необходимо, кроме самого списка, иметь три дополнительных указателя:

· на начало списка списка — назовем этот указатель head;

· на текущий элемент — cur;

· на элемент, предшествующий текущему — predcur.

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

Таким образом, можно определить однонаправленный список в виде, например, представленной ниже структуры list_l1:

struct list_l1 //структура списка

{ item *head, *cur, *predcur; //формуляр списка

// базовые функции

list_l1() {head=cur=predcur=NULL;}//конструктор

bool eolist() {return cur==NULL;}//проверка на конец списка

bool isnull() { return head==NULL; } // проверка на пустоту

type_of_data getdata(); //получить текущий элемент

void first(); //встать в начало

void next(); //перейти к следующему элементу

void ins(type_of_data x);//вставка перед текущим элементом

void del(); // удаление текущего, текущим станет предыдущий

void makenull(); // очистка списка

};

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

· head=predcur=cur=NULL — список пуст, в этом состоянии нельзя удалять элементы, первый добавленный элемент будет одновременно и началом, и концом списка;

· head ≠ NULL; cur=head; predcur=NULL — «начало списка»; в этом состоянии новый элемент вставляется перед первым;

· head ≠ NULL; predcur ≠ NULL; cur=NULL; — «конец списка», в этом состоянии новый элемент вставляется после последнего, а удалить текущий элемент нельзя.

Два последних состояния определены для непустого списка

 (head ≠ NULL).

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

void list_l1::next()

{ if (isnull()) {cerr << "Список пустой"; exit(1);}

if (eolist()) {cerr << "Достигнут конец списка"; exit(2);}

predcur=cur; cur=cur->next;

}

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

void list_l1::ins(type_of_data x)

{ item *temp=new item;

temp->data=x; temp->next=cur;

if (predcur) //вставка не в начало списка

predcur->next=temp;  

else head=temp; //вставка в начало

cur=temp;

}

Удаление требует несколько большего количества проверок, поскольку необходимо обработать аварийные ситуации.

void list_l1::del()

{ if (isnull()) {cerr << "Список пустой"; exit(1); }

if (eolist()) {cerr << "Достигнут конец списка"; exit(2);}

if (predcur) //удаляется не первый элемент списка

{ predcur->next=cur->next; delete cur; cur=predcur->next;

}

else // удаляется первый элемент

{ head=head->next; delete cur; cur=head;

}

}