Презентация на тему Динамические типы данных. Списки

множество (набор) элементов (узлов), которые состоят из данных и полей связи между

Списки – наиболее широко применяемая в программировании динамическая структура данных:
- при решении прикладных задач программирования:
при организации списков объектов (пользователей, задач, документов, рассылки, и т.п.);
- в системном императивном программировании:
при реализации ядра ОС;
при реализации СУБД;
при реализации пользовательского интерфейса;
при работе с файлами;
при построении других динамических структур данных: стеки, очереди, деревья, сети и графы, хеш-таблицы;
при построении трансляторов;
в функциональном программировании:
язык ЛИСП и его диалекты

на одном уровне (в линию).
Мультисписки – узлы могут быть

Вложенные

размещение в динамической памяти.
Используются указатели для реализации полей связи.
Достоинства:
лёгкость

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

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

Сравнение массивов и списков

список;
удаление элемента из списка;
поиск элемента в списке
удаление списка.

*next; // указатель на след.узел
};
typedef Node *PNode; //

Создание списка

PNode createNode (int num)
{
PNode PNew = new Node; // указатель на новый узел
PNew->data = num; // поле данных – номер узла
PNew->next = NULL; // следующего узла нет
return PNew; // результат функции – адрес узла
}

Создание узла

PNew;
в пустой список:
void addFirst (PNode &PHead, PNode PNew)
{
// установить

в начало списка:

адрес головы списка передается по ссылке

1

2

p, PNode PNew)
{
//установить next нового узла на узел, следующий

Последовательность операций менять нельзя, т.к. будет потерян адрес узла, следующего за заданным.

1

p

(Head == NULL) { // если список пуст,
AddFirst(Head, NewNode);

Добавление узла в конец списка

= PHead;
if (Head == p) {
AddFirst(Head, NewNode); // вставка

Добавление узла перед заданным

printf("[ "); while(p != NULL) { printf("%d ", p->data); p = p->next; } printf("]\n"); }
PNode

Поиск элемента в списке

q = PHead;
if (Head == DNode)
Head = DNode->next; //

q

DNode

delete_List(PHead->next);
delete PHead;
}
}
Удаление списка
Задание:
Удалить все элементы.
Найти