Связные списки
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Связные списки
Лекция 5
Связные списки (Linked lists)
▪ Связный список (linked list) – динамическая структура данных для хранения
информации, в которой каждый элемент хранит указатели на один или несколько
других элементов
Операция
Описание
Вычислительная
сложность
Сложность
по памяти
AddFront(L,x)
Добавляет элемент 𝑥
в начало списка 𝐿
𝑂(1)
𝑂(1)
AddEnd(L,x)
Добавляет элемент 𝑥
в конец списка 𝐿
𝑂(𝑛)
𝑂(1)
Lookup(L,x)
Отыскивает элемент 𝑥
в списке 𝐿
𝑂(𝑛)
𝑂(1)
Size(L)
Возвращает количество
элементов в списке 𝐿
𝑂(1) или 𝑂(𝑛)
𝑂(1)
2
Односвязный список (Singly linked list)
▪ Размер списка заранее не известен – элементы добавляются во время
работы программы (динамически)
▪ Память под элементы выделяется динамически (функции: malloc, calloc, free)
Head
Данные Next
Данные Next
Данные Next
NULL
3
Односвязный список (Singly linked list)
#include
#include
struct listnode {
char *data;
int value;
struct listnode *next;
};
/* Data */
/* Data */
/* Next node */
4
Односвязный список (Singly linked list)
struct listnode *list_createnode(char *data,
int value)
{
struct listnode *p;
}
p = malloc(sizeof(*p));
// Выделяем память
if (p != NULL) {
p->data = strdup(data);
p->value = value;
p->next = NULL;
}
Сложность создания элемента
return p;
TCreateNode = O(1)
5
Создание элемента (выделение памяти)
int main()
{
struct listnode *node;
/* Список из одного элемента */
node = list_createnode(“Ivanov Ivan”, 178);
return 0;
}
0x22340AFF
node =
0x22340AFF
data: “Ivanov Ivan”
value: 178
next: NULL
6
Добавление элемента в начало списка
head = 0xAF22
0xAF22
Data
Value
Data
Next
Value
Next
NULL
1. Создаем новый узел newnode в памяти
newnode = 0x12A2
0x12A2
Data
Value
head = 0xAF22
0xAF22
Next
NULL
Data
Value
Next
Data
Value
Next
NULL
7
Добавление элемента в начало списка
newnode = 0x12A2
0x12A2
head = 0xAF22
0xAF22
Data
Next
Value
Data
Value
Next
Data
Value
Next
NULL
NULL
2. Устанавливаем указатель next узла newnode на head
newnode = 0x12A2
0x12A2
Data
Value
head = 0xAF22
0xAF22
Next
0xAF22
Data
Value
Next
Data
Value
Next
NULL
8
Добавление элемента в начало списка
newnode = 0x12A2
0x12A2
Data
Value
head = 0xAF22
0xAF22
Next
0xAF22
Data
Value
Next
Data
Value
Next
NULL
Next
NULL
3. Делаем головой списка узел newnode
newnode = 0x12A2
head = 0x12A2
0x12A2
0xAF22
Data
Value
Next
0xAF22
Data
Value
Next
Data
Value
9
Добавление элемента в начало списка
struct listnode *list_addfront(struct listnode *list,
char *data, int value)
{
struct listnode *newnode;
newnode = list_createnode(data, value);
if (newnode != NULL) {
newnode->next = list;
return newnode;
}
return list;
}
TAddFront = O(1)
10
Добавление элемента в начало списка
int main()
{
struct listnode *head;
head = list_addfront(NULL, "Ivanov Ivan", 178);
head = list_addfront(head, "Petrov Petr", 182);
return 0;
}
0x6600AA
head =
0x6600AA
0x2233FF
data: “Petrov Petr”
value: 182
data: “Ivanov Ivan”
value: 178
next: 0x2233FF
next: NULL
11
Поиск элемента в списке (Lookup)
▪ Начиная с головы списка, просматриваем все узлы и сравниваем ключи
▪ В худшем случае требуется просмотреть все узлы, это требует 𝑂(𝑛) операций
head
data: “Mars”
value: 182
data: “Pluton”
value: 178
data: “Saturn”
value: 169
next: 0xdeadbeaf
next: 0x3434ff99
next: NULL
12
Поиск элемента в списке (Lookup)
struct listnode *list_lookup(struct listnode *list,
char *data, int value)
{
for ( ; list != NULL; list = list->next) {
if (strcmp(list->data, data) == 0 &&
list->value == value)
{
return list;
}
}
return NULL; // Не нашли
TLookup = O(n)
}
13
Поиск элемента в списке (Lookup)
int main()
{
struct listnode *node, *p;
node = list_addfront(NULL, “Mars", 178);
node = list_addfront(node, “Pluton", 182);
node = list_addfront(node, “Saturn", 169);
p = list_lookup(node, “Pluton", 182);
if (p != NULL) {
printf("Data: %s\n", p->data);
}
return 0;
}
14
Удаление элемента (Delete)
1. Находим элемент в списке (за время 𝑂(𝑛))
2. Корректируем указатели (за 𝑂(1))
3. Удаляем элемент из памяти (за 𝑂(1))
Удаляемый элемент
data: “Mars”
value: 182
data: “Pluton”
value: 178
data: “Saturn”
value: 169
next: 0xdeadbeaf
next: 0x3434ff99
next: NULL
Три возможных ситуации:
удаляемый узел – в начале списка
удаляемый узел – внутренний узел (есть элементы слава и справа)
удаляемый узел – в конце списка
15
Удаление элемента (Delete)
struct listnode *list_delete(struct listnode *list,
char *data, int value)
{
struct listnode *p, *prev = NULL;
}
for (p = list; p != NULL; p = p->next) {
if (strcmp(p->data, data) == 0 && p->value == value) {
if (prev == NULL)
list = p->next;
// Удаляем голову
else
prev->next = p->next; // Есть элемент слева
free(p);
// Освобождаем память
return list;
// Указатель на новую голову
}
prev = p; // Запоминаем предыдущий элемент (левый)
}
return NULL;
// Не нашли
TDelete = O(n)
16
Удаление элемента (Delete)
int main()
{
struct listnode *node, *p;
node = list_addfront(NULL, “Mars", 178);
node = list_addfront(node, “Pluton", 182);
node = list_addfront(node, “Saturn", 169);
p = list_delete(node, “Pluton", 182);
if (p != NULL) {
node = p; // Указатель на новую голову
printf(“Item deleted\n");
}
return 0;
}
17
Двусвязные списки (Doubly linked lists)
▪ Каждый узел двусвязного списка имеет три поля: value, next и prev
▪ Поле value – это некоторые данные, ассоциированные с узлом
▪ В поле next хранится адрес узла, следующего за текущим, а в поле prev – адрес
предшествующего узла
18
Создание нового узла
struct listnode *list_createnode(char *data,
int value)
{
struct listnode *p;
}
p = malloc(sizeof(*p));
// Выделяем память
if (p != NULL) {
p->data = strdup(data);
p->value = value;
p->next = NULL;
p->prev = NULL;
}
return p;
T = O(1)
19
Добавление узла в начало списка
▪ Функция создает в памяти новый узел с заданным значением поля value
▪ В поле next нового узла заносится адрес головы списка
▪ Если список не пуст, то необходим записать в указатель prev первого узла адрес нового элемент
struct listnode *list_addfront(struct listnode *list, char *data, int value)
{
struct listnode *newnode;
T = O(1)
newnode = list_createnode(data, value);
if (newnode != NULL) {
newnode->next = list;
if (list != NULL)
list.prev = newnode;
return newnode;
}
return list;
}
20
Добавление узла в конец списка
struct listnode *list_addend(struct listnode *list, char *data, int value)
{
struct listnode *newnode, node;
T = O(n)
newnode = list_createnode(data, value);
if (newnode != NULL) {
if (list = NULL)
return newnode;
node = list;
while (node.next != NULL)
node = node.next;
node.next = newnode;
newnode.prev = node;
}
return list;
}
21
Удаление узла
22
Удаление узла
struct listnode *list_delete(struct listnode *list,
char *data, int value)
{
struct listnode *p;
}
for (p = list; p != NULL; p = p->next) {
if (strcmp(p->data, data) == 0 && p->value == value) {
if (p->prev == NULL)
list = p->next;
// Удаляем голову
else
p->prev->next = p->next; // Есть элемент слева
if (p->next != NULL)
p->next->prev = p->prev;
free(p);
// Освобождаем память
return list;
// Указатель на новую голову
}
}
T = O(n)
return NULL;
// Не нашли
23
Литература
▪ Керниган Б.У., Пайк Р. Практика программирования. – М.: Вильямс, 2004.
[Kernighan, С. 61-66]
▪ [DSABook, Глава 6]
24
Стеки и очереди
Лекция 6
Стек (Stack)
▪ Стек (Stack) – структура данных для хранения элементов
▪ Дисциплина доступа к элементам:
“последним пришел – первым вышел” (Last In – First Out, LIFO)
▪ Элементы помещаются и извлекаются с вершины стека (top)
D
Pop
Push
Top
D
D
C
B
A
26
Подходы к реализации стека
1. На основе связных списков (linked lists)
Длина стека ограничена объемом доступной памяти
2. На основе статических массивов
Длина стека фиксирована (задана его максимальная длина –
количество элементов в массиве)
27
Реализация стека на основе связных списков
▪ Элементы стека хранятся в односвязном списке (singly linked list)
▪ Добавление элемент и удаление выполняется за время 𝑂(1)
Stack:
Size
Top
Данные
Next
Данные
Next
Данные
Next
NULL
28
Реализация стека на основе связных списков
#include
#include
#include "llist.h"
struct stack {
struct listnode *top;
int size;
};
/* Вершина стека */
29
Реализация стека на основе связных списков
/*
* Фрагмент файла llist.h
*/
struct listnode {
int value;
/* Данные стека */
struct listnode *next;
};
30
Реализация стека на основе связных списков
/* stack_create: Creates an empty stack */
struct stack *stack_create()
{
struct stack *s = malloc(sizeof(*s));
if (s != NULL) {
s->size = 0;
s->top = NULL;
}
return s;
TCreate = O(1)
}
31
Реализация стека на основе связных списков
/* stack_free: Removes stack */
void stack_free(struct stack *s)
{
while (s->size > 0)
stack_pop(s);
/* Delete All items */
free(s);
TFree = O(n)
}
Stack:
Size
Top
Данные Next
Данные Next
Данные Next
NULL
32
Реализация стека на основе связных списков
/* stack_size: Returns size of a stack */
int stack_size(struct stack *s)
{
return s->size;
TSize = O(1)
}
33
Реализация стека на основе связных списков
int main()
{
struct stack *s;
s = stack_create();
printf("Stack size: %d\n", stack_size(s));
stack_free(s);
return 0;
}
34
Реализация стека на основе связных списков
/* stack_push: Pushes item to the stack */
int stack_push(struct stack *s, int value)
{
s->top = list_addfront(s->top, value);
if (s->top == NULL) {
fprintf(stderr,
"stack: Stack overflow\n");
return -1;
}
s->size++;
return 0;
TPush = O(1)
}
35
Реализация стека на основе связных списков
int main()
{
struct stack *s;
int i, val;
s = stack_create();
for (i = 1; i <= 10; i++) {
stack_push(s, i);
}
for (i = 1; i <= 11; i++) {
val = stack_pop(s);
printf("pop: %d\n", val);
}
stack_free(s);
}
pop:
pop:
pop:
pop:
pop:
pop:
pop:
pop:
pop:
pop:
pop:
10
9
8
7
6
5
4
3
2
1
-1
return 0;
36
Реализация стека на основе массива
▪ Элементы стека хранятся в массиве фиксированной длины 𝐿
▪ Добавление элемента и его удаление выполняются за время 𝑂(1)
L–1
…
Top
2
C
1
B
A
37
Реализация стека на основе массива
#include
#include
struct stack {
int *v;
int top;
int size;
int maxsize;
};
38
Реализация стека на основе массива
/* stack_create: Creates an empty stack */
struct stack *stack_create(int maxsize)
{
struct stack *s = malloc(sizeof(*s));
if (s != NULL) {
s->v = malloc(sizeof(int) * maxsize);
if (s->v == NULL) {
free(s);
return NULL;
}
s->size = 0;
s->top = 0;
s->maxsize = maxsize;
}
return s;
TCreate = O(1)
}
39
Реализация стека на основе массива
/* stack_free: Removes stack */
void stack_free(struct stack *s)
{
free(s->v);
free(s);
}
TFree = O(1)
/* stack_size: Returns size of a stack */
int stack_size(struct stack *s)
TSize = O(1)
{
return s->size;
}
40
Реализация стека на основе массива
/* stack_push: Pushes item to the stack */
int stack_push(struct stack *s, int value)
{
if (s->top < s->maxsize) {
s->v[s->top++] = value;
s->size++;
} else {
fprintf(stderr,"stack: Stack overflow\n");
return -1;
}
return 0;
TPush = O(1)
}
41
Реализация стека на основе массива
/* stack_pop: Pops item from the stack */
int stack_pop(struct stack *s)
{
if (s->top == 0) {
fprintf(stderr,
"stack: Stack underflow\n");
return -1;
}
s->size--;
return s->v[--s->top];
TPop = O(1)
}
42
Очередь (Queue)
▪ Очередь (Queue) – структура данных для хранения элементов
(контейнер)
▪ Дисциплина доступа к элементам:
“первым пришел – первым вышел” (First In – First Out, FIFO)
▪ Элементы добавляются в хвост (tail), извлекаются с головы (head)
Кит
Enqueue
Front
(head)
Back
(tail, rear)
Слон
Жираф
Волк
Заяц
Dequeue
Рысь
43
Очередь (Queue)
▪ Очереди широко используется в алгоритмах обработки данных:
очереди печати
буфер ввода с клавиатуры
алгоритмы работы с графами
44
Очередь (Queue)
Операция
Описание
Enqueue(q,x)
Добавляет элемент 𝑥 в очередь 𝑞
Dequeue(q)
Извлекает элемент из очереди 𝑞
Size(q)
Clear(q)
Возвращает количество элементов в очереди 𝑞
Очищает очередь 𝑞
45
Подходы к реализации очереди
1. На основе связных списков
Длина очереди ограничена лишь объемом доступной памяти
2. На основе статических массивов
Длина очереди фиксирована (задана максимальная длина)
46
Реализация очереди на основе связных списков
▪ Элементы очереди хранятся в односвязном списке (singly linked list)
▪ Для быстрого (за время 𝑂(1)) добавления и извлечения элементов из
списка поддерживается указатель на последний элемент (tail)
▪ Новые элементы добавляются в конец списка
Queue:
Size
Head
Tail
Данные Next
Данные Next
Данные Next
NULL
47
Реализация очереди на основе связных списков
▪ Преимущества: длина очереди ограничена лишь объемом доступной памяти
▪ Недостатки (по сравнению с реализацией на основе массивов): работа с
очередью немного медленнее, требуется больше памяти для хранения одного
элемента
Queue:
Size
Head
Tail
Данные Next
Данные Next
Данные Next
NULL
48
Реализация очереди на основе связных списков
#include
#include
#include "llist.h"
struct queue {
struct listnode *head;
struct listnode *tail;
int size;
};
49
Реализация очереди на основе связных списков
/* queue_create: Creates an empty queue */
struct queue *queue_create()
{
struct queue *q = malloc(sizeof(*q));
if (q != NULL) {
q->size = 0;
q->head = NULL;
q->tail = NULL;
}
return q;
TCreate = O(1)
}
50
Реализация очереди на основе связных списков
/* queue_free: Removes queue */
void queue_free(struct queue *q)
{
while (q->size > 0)
queue_dequeue(q);
free(q);
TFree = O(n)
}
51
Реализация очереди на основе связных списков
/* queue_size: Returns size of a queue */
int queue_size(struct queue *q)
{
return q->size;
}
int main()
{
struct queue *q;
q = queue_create();
}
queue_free(q);
return 0;
TSize = O(1)
52
Реализация очереди на основе связных списков
/* queue_enqueue: Add item to the queue */
void queue_enqueue(struct queue *q, int value)
{
struct listnode *oldtail = q->tail;
/* Create new node */
q->tail = list_createnode(value);
}
if (q->head == NULL) {
/* List is empty */
q->head = q->tail;
} else {
/* Add new node to the end of list */
oldtail->next = q->tail;
}
TEnqueue = O(1)
q->size++;
53
Реализация очереди на основе связных списков
int main()
{
struct queue *q;
int i;
q = queue_create();
for (i = 1; i <= 10; i++) {
queue_enqueue(q, i);
}
printf("Queue size: %d\n", queue_size(q));
}
queue_free(q);
return 0;
54
Реализация очереди на основе связных списков
/* queue_dequeue: Gets item from the queue */
int queue_dequeue(struct queue *q)
{
int value;
struct listnode *p;
if (q->size == 0)
return -1;
}
/* Delete first node */
value = q->head->value;
p = q->head->next;
free(q->head);
q->head = p;
q->size--;
return value;
TDequeue = O(1)
55
Реализация очереди на основе связных списков
int main()
{
struct queue *q;
int i, j;
q = queue_create();
/* ... */
for (i = 1; i <= 11; i++) {
j = queue_dequeue(q);
printf("%d: next element: %d\n", i, j);
}
}
queue_free(q);
return 0;
56
Реализация очереди на основе циклических
массивов
▪ Элементы очереди хранятся в массиве фиксированной длины [0. . 𝐿 – 1]
▪ Массив логически представляется в виде кольца (circular buffer)
▪ В пустой очереди 𝑇𝑎𝑖𝑙 = 0, 𝐻𝑒𝑎𝑑 = 𝐿
1
2
𝐿– 1
𝐿
X
Tail
Head
57
Реализация очереди на основе циклических
массивов
▪ При добавлении элемента в очередь значение 𝑇𝑎𝑖𝑙 циклически
увеличивается на 1 (сдвигается на следующую свободную позицию)
▪ Если 𝐻𝑒𝑎𝑑 = 𝑇𝑎𝑖𝑙 + 1, то очередь переполнена!
Enqueue(1):
1
1
2
𝐿– 1
𝐿
X
Tail
Head
58
Реализация очереди на основе циклических
массивов
▪ При удалении возвращается элемент с номером 𝐻𝑒𝑎𝑑 % 𝐿
▪ Значение 𝐻𝑒𝑎𝑑 циклически увеличивается на 1 (указывает на
следующий элемент очереди)
1
2
L–1
1
L
X
Head
Tail
Dequeue():
1
2
L–1
L
X
Head Tail
59
Реализация очереди на основе циклических
массивов
#include
#include
struct queue {
int *v;
int head;
int tail;
int size;
int maxsize;
};
60
Реализация очереди на основе циклических
массивов
/* queue_create: Creates an empty queue */
struct queue *queue_create(int maxsize)
{
struct queue *q = malloc(sizeof(*q));
if (q != NULL) {
q->v = malloc(sizeof(int) * (maxsize + 1));
if (q->v == NULL) {
free(q);
return NULL;
}
q->maxsize = maxsize;
q->size = 0;
q->head = maxsize + 1;
q->tail = 0;
}
TCreate = O(1)
return q;
}
61
Реализация очереди на основе циклических
массивов
/* queue_free: Removes queue */
void queue_free(struct queue *q)
{
free(q->v);
free(q);
}
/* queue_size: Returns size of a queue */
int queue_size(struct queue *q)
{
return q->size;
}
62
Реализация очереди на основе циклических
массивов
/* queue_enqueue: Add item to the queue */
int queue_enqueue(struct queue *q, int value)
{
if (q->head == q->tail + 1) {
fprintf(stderr,
"queue: Queue overflow\n");
return -1;
}
}
q->v[q->tail++] = value;
q->tail = q->tail % (q->maxsize + 1);
q->size++;
TEnqueue = O(1)
return 0;
63
Реализация очереди на основе циклических
массивов
/* queue_dequeue: Gets item from the queue */
int queue_dequeue(struct queue *q)
{
if (q->head % (q->maxsize + 1) == q->tail)
{
/* Queue is empty */
fprintf(stderr,
"queue: Queue is empty\n");
return -1;
}
}
q->head = q->head % (q->maxsize + 1);
q->size--;
return q->v[q->head++];
TDequeue = O(1)
64
Реализация очереди на основе циклических
массивов
int main()
{
struct queue *q;
int i, val;
q = queue_create(10);
val = queue_dequeue(q);
for (i = 1; i <= 11; i++) {
queue_enqueue(q, i);
}
for (i = 1; i <= 5; i++) {
val = queue_dequeue(q);
}
}
queue_free(q);
return 0;
65
Литература
▪ Найти и прочитать о двухсторонней очереди
(дек, deque – double ended queue)
▪ [DSABook, Глава 7, Глава 8]
66
