Сложные структуры данных Связные списки. Структуры, ссылающиеся на себя struct node { int x; struct node *next; };

Презентация:



Advertisements
Похожие презентации
Лекция 14 Динамические данные. Виды памяти Существует три вида памяти: статическая, стековая и динамическая. Статическая память выделяется еще до начала.
Advertisements

Списки Лекция 10. Списки Список – структура данных, представляющая собой конечную последовательность элементов. Элемент списка: Данные Связь.
Распределение памяти. Динамическое выделение памяти.
Абстрактный тип данных список. Операции над абстрактным списком Создать пустой список Уничтожить список Определить, пуст ли список Определить количество.
ПРОГРАММИРОВАНИЕ/ ЯЗЫКИ ПРОГРАММИРОВАНИЯ Лекция 5 Структуры данных (весенний семестр 2012 г.) Доцент Кафедры вычислительных систем, к.т.н. Поляков Артем.
Лекция 14 Динамические данные. Виды памяти Существует три вида памяти: статическая, стековая и динамическая. Статическая память выделяется еще до начала.
Информационные технологии Классы памяти auto static extern register Автоматические переменные создаются при входе в функцию и уничтожаются при.
Структуры и алгоритмы обработки данных Лекция. Структуры. Связные списки. Заикин Олег Сергеевич zaikin.all24.org.
ООП Классы Данные отдельно, методы отдельно struct Node { Node* next; void* data; }; struct List { Node* first; int size; }; void* allocate() { … } void.
Двумерные динамические массивы. Двумерный массив - это одномерный массив, элементами которого являются одномерные массивы. Другими словами, это набор.
Под объявлением одномерного динамического массива понимают объявление указателя на переменную заданного типа для того, чтобы данную переменную можно.
УКАЗАТЕЛИ. Переменная - это именованная область памяти с заданным типом. [=значение]; int a; //Переменная типа integer с именем a int b=2;// Переменная.
Лабораторная работа 4. Подпрограммы. Задание на лабораторную работу Написать программу, реализующую хранение информации, указанной в вариантах индивидуальных.
Элементы ЯПВУ. УКАЗАТЕЛИ. C / С++ Pascal Вся динамическая память в Pascal это сплошной массив байтов (куча). Адрес начала кучи храниться в переменной HeapOrg,
В языках высокого уровня обращение к ячейкам памяти происходит не через числовые адреса, а посредством описательных имен. Такие имена называются переменными.
Основы информатики Лекция. Массивы. Указатели. Заикин Олег Сергеевич
Лабораторная работа 7. Работа с динамической памятью, строками и файлами.
Физические модели баз данных Файловые структуры, используемые для хранения информации в базах данных.
САОД кафедра ОСУ 1 Основные абстрактные типы данных Схема процесса создания программ для решения прикладных задач ВУ.
Списки Динамические структуры данных. 2 Строение: набор узлов, объединенных с помощью ссылок. Как устроен узел: данные ссылки на другие узлы Типы структур:
Транксрипт:

Сложные структуры данных Связные списки

Структуры, ссылающиеся на себя struct node { int x; struct node *next; };

Связный список Структура данных, представляющая собой конечное множество упорядоченных элементов (узлов), связанных друг с другом посредством указателей, называется связным списком. Каждый элемент связного списка содержит поле с данными, а также указатель (ссылку) на следующий и/или предыдущий элемент. Эта структура позволяет эффективно выполнять операции добавления и удаления элементов для любой позиции в последовательности.

Недостатки связного списка Недостатком связного списка, как и других структур типа «список», в сравнении его с массивом, является отсутствие возможности работать с данными в режиме произвольного доступа, т. е. список – структура последовательно доступа, в то время как массив – произвольного.

Односвязный список Каждый узел односвязного (однонаправленного связного) списка содержит указатель на следующий узел. Из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Так получается своеобразный поток, текущий в одном направлении.

Односвязный список Каждый из блоков представляет элемент (узел) списка. Здесь и далее Head list – заголовочный элемент списка (для него предполагается поле next). Он не содержит данные, а только ссылку на следующий элемент. На наличие данных указывает поле info, а ссылки – поле next. Признаком отсутствия указателя является поле nil.

Односвязные и двусвязные списки Односвязный список не самый удобный тип связного списка, т. к. из одной точки можно попасть лишь в следующую точку, двигаясь тем самым в конец. Когда кроме указателя на следующий элемент есть указатель на предыдущий, то такой список называется двусвязным.

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

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

Кольцевой список Еще один вид связного списка – кольцевой список. В кольцевом односвязном списке последний элемент ссылается на первый. В случае двусвязного кольцевого списка – плюс к этому первый ссылается на последний. Таким образом, получается зацикленная структура.

Управление памятью Для создания и использования динамических структур требуется динамическое распределение памяти возможность получения памяти для хранения новых узлов и освобождать память для удаления узлов.

Управление памятью Функции для управления динамической памятью объявлены в stdlib.h функция для выделения памяти: void* malloc (size_t size); Функция для освобождения ранее выделенной памяти: void free (void* ptr);

malloc void* malloc (size_t size); Резервирует блоки памяти размером size байт памяти и возвращает указатель на начало зарезервированного участка памяти. Например: newPtr = malloc (sizeof( struct node )); sizeof( struct node ) определяет размер в байтах структуры типа struct node, а malloc выделяет новый блок памяти размером в sizeof( struct node ) и возвращает указатель на выделенную память в newPtr. Если памяти для выделения не достаточно, то malloc возвращает указатель на NULL

free void free (void* ptr); Освобождает память, т.е. память возвращается системе, и в дальнейшем её можно будет выделить снова. Например: free (newPtr); После того как выделенная память больше не нужна необходимо её освободить при помощи free. Так же это не обходимо делать перед завершением программы, если память ещё не была освобождена.

#include struct node { int x; struct node *next; }; int main() { /* Обычная структура */ struct node *root; /* Теперь root указывает на структуру node */ root = (struct node *) malloc( sizeof(struct node) ); /* Узел root указывает на следующий элемент, которого пока нет */ root->next = NULL; /* Использование оператора -> позволяет изменять узел структуры, на которую он указывает */ root->x = 5; free ( root ); return 0; }

int main() { /* Это менять нельзя, т.к. тогда мы потеряем список в памяти */ struct node *root; /* Это указывает на каждый элемент списка, пока мы пробегаем по нему */ struct node *conductor; root = malloc( sizeof(struct node) ); root->next = 0; root->x = 12; conductor = root; if ( conductor != 0 ) { while ( conductor->next != 0) { conductor = conductor->next; }

/* Создаёт новый узел в конце */ conductor->next = malloc( sizeof(struct node) ); conductor = conductor->next; if ( conductor == 0 ) { printf("Не хватает памяти!\n"); return 0; } /* инициализируем память */ conductor->next = 0; conductor->x = 42; return 0; }

conductor = root; if ( conductor != 0 ) { /* убедимся, что существует место старта*/ while ( conductor->next != 0 ) { printf( "%d\n", conductor->x); conductor = conductor->next; } printf( "%d\n", conductor->x ); }

conductor = root; while ( conductor != NULL ) { printf( "%d\n", conductor->x ); conductor = conductor->next; }