Списки

1. Списки

Лекция 2

2. Определения

Список – структура данных, представляющая собой
конечную последовательность элементов.
Элемент списка:
Данные
Связь

3. Односвязные списки

Односвязный список – это список, у элементов которого
существует связь, указывающая на следующий элемент
списка ( односторонняя связь).
Голова
Хвост

4. Описание списка на Си

struct list {
int data;
//информационное поле, данные
struct list *next; // указатель на следующий элемент списка
};
/* Описание переменных: */
struct list *head=NULL; // - указатель на голову списка
struct list *p, *t;

5. Создание первого элемента списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 5;
p->next = NULL;
head = p;
head
p
5
NULL

6. Вставка нового элемента в начало списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 3;
p->next = head;
head = p;
head
p
5
3
NULL

7. Вставка нового элемента в конец списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 10;
p->next = NULL;
t = head;
while (t->next != NULL)
t = t->next;
t->next = p;
head
3
5
NULL
t
p
10
NULL

8. Вставка нового элемента в середину списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 4;
t = head;
while (t->next ->data != 5) //вставка перед элементом с заданным свойством
t = t->next;
p->next = t->next;
t->next = p;
head
3
5
t
p
4
10
NULL

9. Удаление элемента из списка

t = head;
while (t->next ->data != 5)
t = t->next;
p = t->next;
t->next = p->next;
free(p);
head
3
5
t
p
4
10
NULL

10. Лабораторная работа

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

11. Циклические списки

Циклический список – это список, в котором связь
последнего элемента указывает на первый или
один из других элементов этого списка.
head
Задача: Для заданного односвязного списка определить,
является ли он циклическим.
Преобразовывать список нельзя.

12. Двусвязные списки

Двусвязные списки – это списки, элементы которых
имеют по две связи, указывающие на предыдущий
и следующий элементы.
NULL
head
typedef struct list {
int data;
struct list *prev;
struct list *next;
} List;
NULL

13. Удаление элемента из двусвязного списка

List *del (List *p) { //возвращает указатель на следующий элемент списка
List *pp,*pn;
if (p == NULL) return NULL;
pp = p->prev;
pn = p->next;
if (pp) pp->next = pn;
if (pn) pn->prev = pp;
free(p);
return pn;
}
pp
p
pn

14. Иерархические списки

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