Тема Связанные списки Лекция 08.11.11г. 1

элементы которой расположены в линейном порядке. Однако, в отличие от

массива, в котором этот порядок определяется индексами, порядок в связанном списке поддерживается с помощью указателей. Связанные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции, рассмотренные ранее для массивов.
Списки могут быть разных видов. Простейшим из списков является однократно связанный (однонаправленный - singly linked) список. Будем обозначать вид таких списков L1.

typedef struct Node1 {
double elem; struct Node1 *next; } Node1;
typedef struct List1 { Node1* head; } List1;

и текст функции init_L1 , инициализирующей такой список.
void init_L1(List1 *l)

{
l->head = NULL;
}

В дальнейшем полезной будет функция печати элементов списка Print_L1.

void Print_L1(List1 *l) {
Node1 *p = l->head;
if (p == NULL) printf("List is empty");
while (p) { // цикл обхода узлов от головы к хвосту
printf("%5.1f ", p->elem);
p = p->next;
}
printf("\n----------------\n");
}

задачи включения нового элемента в однонаправленный список:
включение в голове списка

(перед первым элементом),
включение в хвосте списка (после последнего элемента),
включение после заданного узла.

elem

next

elem

next

elem

NULL

head

голова

хвост

elem

next

elem

NULL

новый

новый

На следующем слайде представлены тексты функций, реализующих включение нового элемента в голове списка Insert_head_L1 , в хвосте списка Insert_back_L1 и после заданного элемента Insert_L1 .

elem

next

новый

q – заданный узел

{
Node1* p = (Node1*)calloc(1, sizeof(Node1));
p->elem = z; p->next

= l->head;
l->head = p;
}
void Insert_back_L1(List1 *l, double z) {
Node1* p = (Node1*)calloc(1, sizeof(Node1));
p->elem = z; p->next = NULL;
if (l->head == NULL) {l->head = p; return;}
Node1* q = l->head;
while (q->next) q = q->next;
q->next = p;
}
void Insert_L1(List1 *l, Node1 *q, double z) {
Node1* p = (Node1*)calloc(1, sizeof(Node1));
p->elem = z; p->next = q->next; q->next = p;
}

На данном слайде представлены тексты функций, реализующих включение нового элемента в голове списка Insert_head_L1 , в хвосте списка Insert_back_L1 и после заданного элемента Insert_L1 .

однонаправленного списка имеет также несколько разновидностей:
извлечение первого элемента,
извлечение последнего

элемента,
извлечение элемента, следующего за заданным.

elem

next

elem

NULL

elem

NULL

head

голова

хвост

освобождение памяти

хвост

elem

next

elem

next

elem

NULL

head

голова

хвост

освобождение памяти

elem

next

q – заданный узел

функций, реализующих извлечение элемента в голове списка Extract_head_L1, в хвосте

списка Extract_back_L1 и после заданного элемента Extract_L1.

int Extract_head_L1(List1 *l, double *z) {
Node1 *p = l->head;
if (p == NULL) return 0;
*z = p->elem; l->head = p->next; free(p);
}
int Extract_back_L1(List1 *l, double *z) {
Node1 *p = l->head, *p1;
if (p == NULL) return 0;
if (p->next == NULL) {
*z = p->elem; l->head = NULL;
free(p); return 1; }
for (p1 = p->next; p1->next; p = p1, p1 = p->next);
*z = p1->elem; p->next = NULL; free(p1); return 1;
}
int Extract_L1(List1 *l, Node1 *q, double *z) {
Node1 *p = q->next;
if (p == NULL) return 0;
*z = p->elem; q->next = p->next; free(p); return 1;
}

структур данных, сформируем файл интерфейса List1.h и файл реализации List1.c

для списков вида L1 (тексты не приводятся), а также проведём тестирование:

#include
#include "List1.h"
int main() {
List1 l; init_L1(&l); Print_L1(&l);
Insert_head_L1(&l, 14.0);
Insert_back_L1(&l, 10.0);
Insert_head_L1(&l, 16.0); Print_L1(&l);
Insert_L1(&l, l.head->next, 20.0); Print_L1(&l);
Insert_L1(&l, l.head->next->next, 50.0);
Print_L1(&l);
double x;
Extract_L1(&l, l.head->next, &x); Print_L1(&l);
Extract_back_L1(&l, &x); Print_L1(&l);
Extract_head_L1(&l, &x); Print_L1(&l);
Extract_back_L1(&l, &x); Print_L1(&l);
system("PAUSE");
return 0;
}

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

задачи для однонаправленного списка: перестроить список так , чтобы хвост

стал головой и наоборот – голова стала хвостом (т.е. выполнить реверсирование списка). На рисунке показан один цикл обращения. Слева от пунктира – перестроенный список, справа – исходный.

void reverse_L1(List1 *l) {
Node1 *r = l->head, *y, *t;
if (r == NULL) return; // список пуст
y = r->next; // начальная установка
r->next = NULL; // голова стала хвостом
while (y) {
t = y->next; y->next = r; r = y; y = t;
}
l->head = r;
}

l;
init_L1(&l);
Print_L1(&l);
Insert_head_L1(&l, 14.0);
Insert_back_L1(&l, 10.0);
Insert_head_L1(&l, 16.0);

Print_L1(&l);
Insert_L1(&l, l.head->next, 20.0);
Print_L1(&l);
Insert_L1(&l, l.head->next->next, 50.0);
Print_L1(&l);
reverse_L1(&l); Print_L1(&l);
system("PAUSE");
return 0;
}

сортировка списка вставками.
10
head
t
50
20
14
16
N
20
14
16
N
50
a
b
10
N
исходный список
неотсортированный список
отсортированный список
фиктивные узлы
x
do { // цикл

по неотсортированному списку
a->next = t->next;
for (x = b; ;x = x->next) // цикл по отсортированному списку
if ((x->next == NULL) || (x->next->elem > t->elem)) {
t->next = x->next; x->next = t; break; }
} while (t = a->next);

t

20

14

16

N

50

N

a

b

10

неотсортированный список

отсортированный список

x

((l->head == NULL) || (l->head->next == NULL)) return;
Node1* a

= (Node1*)calloc(1, sizeof(Node1));
a->next = l->head->next->next;
Node1* t = l->head->next;
Node1* b = (Node1*)calloc(1, sizeof(Node1));
b->next = l->head; l->head->next = NULL;
Node1* x;
do {
a->next = t->next;
for (x = b; ;x = x->next)
if ((x->next == NULL) || (x->next->elem > t->elem)) {
t->next = x->next; x->next = t;
break;
}
} while (t = a->next);
l->head = b->next;
}

l;
init_L1(&l);
Print_L1(&l);
Insert_head_L1(&l, 14.0);
Insert_back_L1(&l, 10.0);
Insert_head_L1(&l, 16.0);

Print_L1(&l);
Insert_L1(&l, l.head->next, 20.0);
Print_L1(&l);
Insert_L1(&l, l.head->next->next, 50.0);
Print_L1(&l);
reverse_L1(&l); Print_L1(&l);
sort_L1(&l); Print_L1(&l);
reverse_L1(&l); Print_L1(&l);
system("PAUSE");
return 0;
}

List1 l;
init_L1(&l);
Print_L1(&l);
int i;
for(i = 0;

i<100; i++)
Insert_head_L1(&l, (double)(rand() % 1000));
Print_L1(&l);
sort_L1(&l); Print_L1(&l);
system("PAUSE");
return 0;
}