Списки Лекция 10

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

Односвязные (в том числе циклические ) Двусвязные (в том числе циклические ) Иерархические

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

Односвязный список struct Tlist { char word[256]; //область данных; можно: char* word; int count; struct Tlist *next; //ссылка на следующий узел }; struct Tlist * Head = NULL; //голова списка struct Tlist * new_el(char newWord[]) { struct Tlist * p=(struct Tlist*) malloc( sizeof(struct Tlist)); if(p){ strcpy(p->word, newWord); //записать слово p->count = 1; //счетчик слов == 1 p->next = NULL; //следующего узла нет } return p; //результат функции – адрес элемента }

Создание первого элемента списка p = (struct Tlist*) malloc(sizeof(struct Tlist)); p->data = 5; p->next = NULL; head = p; head p 5NULL struct Tlist *head=NULL; Struct Tlist *p;

Списки смежностей NULL

struct Ie _ list{ struct Ie _ list *next; struct Tlist *simpleList; }; struct Ie _ list *list; list=(struct Ie_list *) malloc(sizeof(struct Ie_list )); If (list) { list->next=NULL; list->simpleList = new_el(hello!); }

Вставка элемента в односвязный список после элемента с адресом prev void AddAfter (Node prev, char data[]) { Node cur = new_el(data); if (cur) { cur ->next = prev->next; prev->next = cur; } } typedef struct Tlist * Node; //указатель на элемент

Node AddFirst (Node Head, char data[]) { Node cur = new_el(data); if(cur) cur ->next = Head; return cur; } Вставка элемента в голову односвязного списка

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

Проход по списку Node p = Head; while (p) { // пока не дошли до конца (p!= NULL) p = p->next; // переходим к следующему } Поиск элемента в списке Node Find (Node Head, char s[]) { Node q = Head; // лишняя переменная, достаточно Head while (q && strcmp(q->word, s)) q = q->next; return q; }

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

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

Двусвязный список struct Tlist2 { char word[256]; //область данных struct Tlist2 *next; // ссылка на следующий узел struct Tlist2 *prev; // ссылка на предыдущий узел }; struct Tlist2 * Head = NULL; // голова списка struct Tlist2 * new _ el _ 2(char newWord[]) { struct Tlist2 * p=(struct Tlist2 *) malloc( sizeof(struct Tlist2)) ; if(p){ strcpy(p->word, newWord); //записать слово p->next = NULL; // следующего узла нет p->prev = NULL; // предыдущего узла нет } return p; // результат функции – адрес элемента }

Удаление элемента после элемента с адресом cur q = cur->next; cur->next = q -> next; cur->next->next->prev = cur; free(q);

Вставка элемента в двусвязный список после элемента с адресом pr cur = new_el_2(data); If cur) { cur ->next = pr->next; pr->next->prev = cur; pr->next = cur; cur->prev = pr; }

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

Линейный список - это множество, состоящее из n (n0) узлов (элементов) X[1], X[2], …, X[n], структурные свойства которого ограничены линейным (одномерным) относительным положением узлов (элементов), т.е. следующими условиями: если n > 0, то X[1] – первый узел; если 1 < k < n, то k-му узлу X[k] предшествует узел X[k-1], а за узлом X[k] следует узел X[k+1]; X[n] – последний узел.

Операции над линейными списками 1.Получить доступ к k-му элементу списка, проанализировать и/или изменить значения его полей. 2.Включить новый узел перед k- м. 3.Исключить k-й узел. 4.Объединить два или более линейных списков в один. 5.Разбить линейный список на два или более линейных списков. 6.Сделать копию линейного списка. 7.Определить количество узлов. 8.Выполнить сортировку в возрастающем порядке по некоторым значениям полей в узлах. 9.Найти в списке узел с заданным значением в некотором поле. 10. … и т.д.

Не все операции нужны одновременно! =>=> Будем различать типы линейных списков по набору главных операций, которые над ними выполняются.

Стек -это линейный список, в котором все включения и исключения (и всякий доступ) делаются на одном конце списка (вершина стека) Верх Третий сверху Второй сверху Четвертый сверху Низ Включить или исключить

Операции работы со стеками 1.makenull (S) – делает стек S пустым 2.create(S) – создает стек 3.top (S) – выдает значение верхнего элемента стека, не удаляя его 4.pop(S) – выдает значение верхнего элемента стека и удаляет его из стека 5.push(x, S) – помещает в стек S новый элемент со значением x 6.empty (S) - если стек пуст, то функция возвращает 1 (истина), иначе – 0 (ложь).

Стеки push-down список реверсивная память гнездовая память магазин LIFO (last-in-first-out) список йо-йо

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

Реализация стека strict Tlist { int data; struct Tlist * next; } typedef struct Tlist * Stack1; // в этом случае работа такая же, как // с односвязным списком typedef struct stack {struct Tlist * top; } Stack; void makenull (Stack *S){ struct Tlist *p; while (S->top) { p = S->top; S->top = p->next; free(p); } }

Stack * create () { Stack *S; S = (Stack *)malloc(sizeof(Stack)); S->top = NULL; return S; } int top (Stack *S) { if (S->top) return (S->top->data); else return 0; //здесь может быть реакция на //ошибку – обращение к пустому стеку }

i nt pop(Stack *S){ int a; struct Tlist *p; p = S->top; a = p->data; S-> top = p->next; free(p); return a; }

void push(int a, Stack *S){ // return NULL - ? struct Tlist *p; p =(struct Tlist *)malloc(sizeof(struct Tlist)); if(p) { p->data = a; p->next = S-> top; S->top = p ; } } int empty (Stack *S) { return (S->top == NULL); }

Очередь -это линейный список, в котором все включения производятся на одном конце списка, все исключения – на другом его конце НачалоВторойТретийЧетвертыйКонец Исключить Включить

Очереди FIFO (first-in-first-out) –первый вошел, первый вышел

Операции работы с очередями 1.makenull (Q) – делает очередь Q пустой 2.create(Q) – создает очередь 3.first (Q) – выдает значение первого элемента очереди, не удаляя его 4.get(Q)/outqueue(Q) – выдает значение первого элемента очереди и удаляет его из очереди 5.put(x, Q)/inqueue(x, Q) – помещает в конец очереди Q новый элемент со значением x 6.empty (Q) - если очередь пуста, то функция возвращает 1 (истина), иначе – 0 (ложь).

Реализация очереди struct Tlist { into data; struct Tlist * next; } typedef struct queue { struct Tlist *first; struct Tlist *end; } Queue;

Дек (double-ended queue) очередь с двумя концами - это линейный список, в котором все включения и исключения производятся на обоих концах списка Левый конец Второй слева Третий слева или справа Второй справа Правый конец Включить или исключить Включить или исключить