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

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

Struct SList2

{

Int value;

struct SList2 *prev, *next;

};

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

Для сокращения имени типа в языке С можно использовать оператор typedef. Принцип работы данного оператора следующий. Если перед определением некоторой переменной с именем NAME написать оператор typedef, то NAME из имени переменной превратится в имя нового типа. Т.о. следующий оператор создает новый тип TList2, который можно использовать вместо типа struct SList2:

Typedef struct SList2 TList2;

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

TList2 *head=NULL, *current=NULL;

Признаком пустоты списка служит нулевое значение указателя head. Установка текущего элемента на начало списка сводится к присвоению

current=head;

Вставка элемента со значением value после текущего может быть произведена следующим образом:

TList2 *InsertData(int value, TList2 **head, TList2 **current)

{

TList2 *New=(TList2 *)malloc(sizeof(TList2));

New->value = value;

if(*head == NULL) //Случай пустого списка

{*current =*head = New; (*head)->next= (*head)->prev=NULL; return New;}

if(*current==NULL) //Случай вставки в начало списка

{

(*current)=New; (*current)->next=*head; (*current)->prev=NULL;

(*head)->prev=New;

(*head)=New;

Return New;

}

New->next = (*current)->next; New->prev=*current;

if((*current)->next!= NULL) (*current)->next->prev = New;

(*current) ->next = New;

Return New;

}

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

current = InsertData(value, &head, &current);

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

TList2 *InsertData(int value, TList2 *&head, TList2 *&current)

{

TList2 *New=(TList2 *)malloc(sizeof(TList2));

New->value = value;

if(head == NULL) //Случай пустого списка

{current =head = New; head->next= head->prev=NULL; return New;}

if(current==NULL) //Случай вставки в начало списка

{

current=New; current->next=head; current->prev=NULL;

head->prev=New;

head=New;

Return New;

}

New->next = current->next; New->prev=current;

if(current->next!= NULL) current->next->prev = New;

current ->next = New;

Return New;

}

Вызывать эту функцию надо следующим образом

Дата добавления: 2015-10-30