Списковые структуры. Функции динамического выделения памяти. Рекурсивные структуры. Разновидности списков: стек, очередь, кольцевой список

1.1.4. Списковые структуры. Функции динамического выделения памяти.

Рекурсивные структуры. Разновидности списков: стек, очередь, кольцевой список. Основные операции со списками

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

Списки данных могут храниться и в массивах, но связные списки предоставляют некоторые преимущества:

1)  применение списков является уместным в том случае, когда число элементов заранее неизвестно;

2)  они могут сортироваться просто путём вставки нового элемента в соответствующую позицию. При этом существующие элементы не надо перемещать.

Однако у них есть и недостатки:

1)  для доступа к узлу списка нужно последовательно пройти все предыдущие узлы. Адрес же элемента массива может быть вычислен непосредственно на основе адреса первого элемента;

2)  указатели занимают некоторое место в памяти. Пример списковой структуры: struct a {

int x; //Поле данных char y[10]; //Поле данных

struct a *next; //Указатель на следующий узел

};

Классификация списков по видам связей:

•  однонаправленный – с указателем только на следующий элемент:

head – указатель на первый элемент last – указатель на последний элемент next – указатель на следующий элемент

•  двунаправленный – с указателями на предыдущий и следующий элементы:

prev – указатель на предыдущий элемент

•  кольцевой – за последним элементом идёт первый. Может быть одно- или двунаправленным. Двунаправленный кольцевой список:

Классификация списков по порядку добавления и удаления элементов:

•  стек (LIFO – last in, first out) – добавление и удаление элементов происходит только в начале списка;

•  очередь (FIFO – first in, first out) – элементы добавляются только в конце списка, а удаляются только в начале;  дек – элементы можно добавлять и удалять как в начале, так и в конце.

Функции динамического выделения памяти: void *malloc(size_t size)

Выделяет непрерывную область памяти размером size байт (параметр size имеет тип size_t, как и результат операции sizeof). Возвращает указатель без типа на начало выделенной области. Для использования этого указателя его необходимо преобразовать к нужному типу. Если выделить память не удалось, возвращает NULL. void *calloc(size_t n, size_t size)

Предназначена для выделения памяти под заданное (n) количество объектов, каждый из которых имеет размер size. Выделяет непрерывную область размером n×size байт. void *realloc(void *ptr, size_t size)

Предназначена для изменения размера динамически выделенной области, адресуемой указателем ptr. Размер области может как увеличиваться, так и уменьшаться. Функция возвращает адрес новой области памяти, при этом старая освобождается. Данные из освобождаемой области копируются в новую, но не более size байт. void free(void *ptr)

Предназначена для освобождения памяти, выделенной функциями malloc, calloc и realloc. ptr – указатель на такую область памяти. Использование других указателей в функции free делает её поведение неопределённым и может привести к потере управления памятью.

Основные операции с однонаправленными списками:  вставка элемента после того, на который указывает ref:

n = (a *)malloc(sizeof(a)); //Адрес выделенной памяти сохраняется в n

                            //a – тип структуры

n->next = ref->next; //Указатель на следующий за вставляемым элемент ref->next = n; //Указатель на новый элемент if(ref==last) last=n; //Установка конца списка

 удаление элемента, следующего за ref:

if((n = ref->next) == NULL) printf("Нет следующего\n"); else

{ref->next = n->next; //Указатель на следующий за удаляемым элемент free(n); //Освобождение памяти if(n==last) last=ref;} //Установка конца списка

Основные операции с двунаправленными списками:  вставка элемента после того, на который указывает ref:

n = (a *)malloc(sizeof(a)); //Адрес выделенной памяти сохраняется в n n->prev = ref; //Указатель на предшествующий вставляемому элемент n->next = ref->next; //Указатель на следующий за вставляемым элемент

if(ref==last) last=n; //Установка конца списка else (ref->next)->prev = n; //Указатель prev на новый элемент ref->next = n; //Указатель next на новый элемент

 удаление элемента, следующего за ref:

if((n = ref->next) == NULL) printf("Нет следующего\n"); else

{ref->next = n->next; //Указатель на следующий за удаляемым элемент

if(n==last) last=ref; //Установка конца списка

else (ref->next)->prev=ref; //Указатель на предшествующий удаляемому элемент free(n);} //Освобождение памяти