Шрифт:
Функция
create
просто создает список List
свободной памяти. Она напоминает комбинацию конструктора (функция init
выполняет инициализацию) и оператора new
(функция malloc
выделяет память).
struct List* create /* создает пустой список */
{
struct List* lst =
(struct List*)malloc(sizeof(struct List));
init(lst);
return lst;
}
Функция
clear
предполагает, что все узлы уже созданы и расположены в свободной памяти, и удаляет их оттуда с помощью функции free
.
void clear(struct List* lst) /* удаляет все элементы списка lst */
{
assert(lst);
{
struct Link* curr = lst–>first;
while(curr) {
struct Link* next = curr–>suc;
free(curr);
curr = next;
}
lst–>first = lst–>last = 0;
}
}
Обратите внимание на способ, с помощью которого мы обходим список, используя член
suc
класса Link
. Мы не можем получить безопасный доступ к члену объекта после его удаления с помощью функции free
, поэтому ввели переменную next
, с помощью которой храним информацию о своей позиции в контейнере List
, одновременно удаляя объекты класса Link
с помощью функции free
. Если не все объекты структуры
Link
находятся в свободной памяти, лучше не вызывать функцию clear
, иначе она вызовет разрушение памяти. Функция
destroy
, по существу, противоположна функции create
, т.е. она представляет собой сочетание деструктора и оператора delete
.
void destroy(struct List* lst) /* удаляет все элементы списка lst;
затем удаляет сам список lst */
{
assert(lst);
clear(lst);
free(lst);
}
Обратите внимание на то, что перед вызовом функции очистки памяти (деструктора) мы не делаем никаких предположений об элементах, представленных в виде узлов списка. Эта схема не является полноценной имитацией методов языка С++ — она для этого не предназначена.
Функция
push_back
— добавление узла Link
в конец списка — вполне очевидна.
void push_back(struct List* lst, struct Link* p) /* добавляет элемент p
в конец списка lst */
{
assert(lst);
{
struct Link* last = lst–>last;
if (last) {
last–>suc = p; /* добавляет узел p после узла last */
p–>pre = last;
}
else {
lst–>first = p; /* p — первый элемент */
p–>pre = 0;
}
lst–>last = p; /* p — новый последний элемент */
p–>suc = 0;
}
}
Весь этот код было бы трудно написать, не нарисовав схему, состоящую из нескольких прямоугольников и стрелок. Обратите внимание на то, что мы забыли рассмотреть вариант, в котором аргумент
p
равен нулю. Передайте нуль вместо указателя на узел, и ваша программа даст сбой. Этот код нельзя назвать совершенно неправильным, но он не соответствует промышленным стандартам. Его цель — проиллюстрировать общепринятые и полезные методы (а также обычные недостатки и ошибки). Функцию
erase
можно было бы написать следующим образом:
struct Link* erase(struct List* lst, struct Link* p)
/*
удаляет узел p из списка lst;
возвращает указатель на узел, расположенный после узла p
*/
{
assert(lst);
if (p==0) return 0; /* OK для вызова erase(0) */
if (p == lst–>first) {