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

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

Графически связи в списках удобно изображать с помощью стрелок, как было показано в разделе описания указателей. Если элемент списка не связан с любым другим, то в поле указателя записывают значение, не указывающее ни на какой элемент (пустой указатель). Такая ссылка в Паскале обозначается nil, а на схеме обозначается перечеркнутым прямоугольником. Ниже приведена структура односвязного списка (рис.40), т.е. связь идет от одного элемента списка к другому в одном направлении. Здесь поле D – это информационное поле, в котором находятся данные (любой допустимый в языке Паскаль тип), поле N (NEXT) – указатель на следующий элемент списка.

Каждый список должен иметь следующие указатели: Head – голова списка, Cur – текущий элемент списка, иногда в односвязных списках также используется указатель Tail – хвост списка (в двухсвяхных списках он используется всегда). Поле указателя последнего элемента списка является пустым, в нем находится специальный признак nil, свидетельствующий о конце списка и обозначается перечеркнутым квадратом.

Двухсвязный линейный список отличается от односвязного наличием в каждом узле списка ещё одного указателя B (Back), ссылающегося на предыдущий элемент списка (рис.41).

Структура данных, соответствующая двухсвязному линейному списку описывается на языке Си следующим образом:

struct list

{

Int value; // значение элемента

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

struct list *back; // указатель на предыдующий элемент

}

При работе с линейными списками используются следующие основные операции:

• создание списка;

• добавление нового элемента в список: в голову списка, в хвост списка, после текущего элемента списка, перед текущим элементом списка;

• удаление элемента из списка;

• обход списка с целью его обработки;

• поиск узла в списке;

• переход на узел в списке по номеру от начала и другие операции.

Создание списка

При создании списка нужно выполнить следующие действия (рис. 42):

• выделить память;

• «обнулить» указатели на предыдущий и последующий элементы;

• определить указатели на голову, хвост и текущий элемент списка;

• внести в информационную часть списка данные.

Добавление нового узла в список

Для добавления нового узла в голову списка нужно выполнить последоватеьность действий, указанных в табл.15.

Таблица 15.

Добавление нового узла в голову списка

№	Действие	Иллюстрация
1.	Выделить память под новый узел списка: list* ptr = new list.	ptr
2.	Заполнить информационную часть узла и обнулить указатели в нем	данные ptr
3.	Если список пуст, то этот узел сделать головой списка: head = ptr.	данные head
4.	Если список не пуст, то
4.1.	Для нового узла следующий указатель установить на голову текущего списка: ptr -> next = head.	ptr head
4.2.	Для головы списка предыдущий указатель установить на новый узел: head -> back = ptr.	ptr head
4.3.	Установить на новый узел указатель на голову списка: head = ptr.	ptr head

int val;

list head;

list* ptr = new list;

ptr->value = val;

ptr->next = NULL;

ptr->back = NULL;

if (head == Nil) head = ptr //список пустой?

else

{

Ptr->next = head;

Head->back = ptr;

Head = ptr;

}

Добавление в хвост списка и после текущего узла списка (или перед текущим) делается аналогично:

int s

list tail;

list* ptr = new list;

ptr->value = val;

ptr->next = NULL;

ptr->back = NULL;

if (tail == NULL) tail = ptr //список пустой?

else

{

tail->next = ptr;

prt->back = tail;

tail = ptr;

}

Удаление узла из списка

При удалении узла из списка нужно рассмотреть следующие ситуации:

1. Удаляемый узел является головой списка.

2. Удаляемый узел является хвостом списка.

3. Удаляемый узел единственный в списке.

4. Удаляемый узел не является ни головой, ни хвостом, ни единственным в списке.

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

Таблица 16.

Удаление узла внутри списка

№	Действие	Иллюстрация
1.	На текущий узел указывает предыдущий узел. Этот указатель нужно «перекинуть» на следующий за текущим узел: cur->back->next =cur->next;	cur->back->next Cur->next Cur->back cur cur->next->back
2.	С cur->back->next ледующий узел за текущим после удаления текущего узла должен будет указывать на предыдущий от текущего узла. Заменяем этот указатель: cur->next->back = cur->back;	Cur->next Cur->back cur cur->next->back back
3.	З cur->back->next апомним указатель на текущий элемент во временном указателе tail: tail = cur;	Cur->next Cur->back cur cur->next->back tail
4.	Т cur->back->next екущим элементом списка будет теперь следующий за ним узел: cur = cur->next;	Cur->next Cur->back cur cur->next->back tail
5.	Освобождаем память, выделенную динамически для удаляемого узла списка: free(tail);	cur

//удаление узла в списке

list head,tail,cur, temp;

// проверяем является ли узел единственным в списке?

if ((cur->next == NULL) && (cur->back = NULL))

{

head = NULL;

tail = NULL; // делаем список пустым

free(cur);

cur = NULL; //освобождаем память

}

else

if (cur->next == NULL) // текущий узел является хвостом?

{

tail = tail->back; // Хвостом теперь станет предпоследний узел

tail->next = NULL;

free (cur);

cur = tail;

}

else

if (cur->back == NULL) // текущий узел является головой?

{

head = head->next; // головой становится второй узел списка

head->back = NULL;

free (cur);

cur = head;

}

else //узел ни голова, ни хвост, ни единственный в списке

{

cur->back->next = cur->next;

cur->next->back = cur->back;

temp = cur;

cur = cur->next;

free (temp);

};

}

Обход списка и переход к узлу по номеру от головы списка

Обход списка осуществляется с целью анализа, обработки и поиска данных находящихся в списке. Заметим, что переход к следующему узлу осуществляется присваиванием указателю C на текущий узел значения указателя на следующий узел cur->next. Но по определению списка, последний узел в списке содержит пустой указатель на следующий узел. А значит это и является признаком конца обхода списка. Таким образом, стандартный алгоритм обхода списка прост:

3. Выполнять в цикле:

4. Обработать текущий узел.

5. Перейти к следующему узлу.

6. До тех пор пока указатель на следующий узел станет пустым.

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