11. Связные списки
struct
node
{
int
val;
node
*next;
};
Списки
- упорядоченное
множество, состоящее из переменного
числа элементов, к которым применимы
операции включения, исключения.
Длина списка
равна числу элементов, содержащихся в
списке. Список нулевой длины
называется пустым
списком.
Список,
отражающий отношения соседства между
элементами, называется линейным.
Добавление
элемента
в
начало:
void
addElementR(struct node ** head, int newData)
{
struct
node * newNode;
newNode
= (struct node *) malloc(sizeof(struct node));
newNode->data
= newData;
newNode->next
= NULL;
if
(*head == NULL) {
(*head)
= newNode;
return;
}
newNode->next
= (*head);
(*head)
= newNode;
}
Исключение
элемента:
int
delElementR(struct node** delnode)
{
struct
node* tmp;
if
(delnode != NULL) {
tmp
= *delnode;
*delnode
= (*delnode)->next;
free(tmp);
return
1;
}
return
0;
}
Фиктивная
голова это голова, указатель на которую
имеет значение NULL
Кольцевой
список, это список в котором последний
элемент имеет указатель на первый
элемент списка.
Двусторонняя
очередь
Дек
(двусвязная очередь)
- особый вид очереди. Последовательный
список, в котором как включение, так и
исключение элементов может осуществляться
с любого из двух концов списка.
