Лекция 3

1. Лекция 3

Основы алгоритмизации и программирования
Часть 2
Лекция 3
Ассоциативные структуры
данных. Связные списки.

2. Напоминание: массивы и память

Сама память компьютера – это одномерный массив байт.
Массив – группа однотипных значений (элементов), расположенных в памяти
последовательно, друг за другом, объединённая общим именем.
Обычная память компьютера предполагает обращение к данным по номерам
элементов.
Для массива можно найти (и записать в другие переменные) номера
элементов с заданными свойствами, или упорядочить сам массив, тем самым
придав некоторым из номеров элементов дополнительный смысл кроме
обычного «здесь хранится элемент данных».
a
Расположение в памяти
a[-1]
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]

3. Напоминание: соглашение о нулевом указателе

Если указатель хранит нулевое значение, то есть указывает на начальный байт
памяти, считается, что ему не сопоставлены никакие данные.
Операция разыменования не допускается и приводит к специфической
ошибке.
Нулевой указатель можно обозначать как специальным словом NULL, так и
числом 0, или вовсе не обозначать, используя только логические операции.
Соглашение о нулевом указателе позволяет организовать другие способы
хранения/обработки большого количества данных, чем простые массивы.
На самом деле, рассмотренный двумерный динамический массив уже
демонстрирует одну из таких возможностей.
массив указателей A
A[0]
A[1]
A[2]
A[3]
A[3][0] A[3][1] A[3][2]
A[0][0] A[0][1] A[0][2]
A[1][0] A[1][1] A[1][2]
A[2][0] A[2][1] A[2][2]
массивы чисел A[0]..A[3] (не обязаны быть одинаковой длины и вообще существовать)

4. Постановка задачи

Общая задача:
Рассмотреть варианты организации хранения данных, при которых одни
данные, непосредственно доступные через переменные в некоторой точке
выполнения программы, позволяют получить быстрый доступ к другим
данным, которые понадобятся в дальнейшем.
В памяти компьютера, организованной как пронумерованная
последовательность байт, задача решается с помощью указателей, хранящих
адрес «следующих порций данных», или же 0, если «следующих данных» нет.
Задача о списках:
Рассмотреть хранение данных в виде цепочки элементов, каждый из которых
хранит местонахождение в памяти следующего элемента (или является
нулевым указателем).
a
a[-1] a[0]
Список L
Массив
a[1]
a[2]
a[3]
a[4]
a[5]
0

5. Элемент списка

Список L
0
Элемент списка – структура данных, которая хранит по меньшей мере один
адрес следующего элемента и некоторые полезные данные.
Пример на Си – список из точек
адрес
полезные
следующего
данные
typedef struct ListElt//"list element"
{
struct ListElt *next;//адрес следующего
int x, y;//полезные данные
}ListElt;
Запись вида struct ListElt *next; внутри самой структуры ListElt на первый
взгляд выглядит абсурдной – но это не попытка поместить структуру саму в
себя.
struct ListElt *next; - указатель, то есть всего лишь число.

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

Список L
0
Показанный на схеме список называется
односвязным, поскольку каждый элемент хранит только адрес следующего
элемента
и линейным, поскольку цепочка элементов завершается нулевым указателем.
0
«голова»
(первый
элемент)
списка
«хвост»
(все остальные элементы) списка

7. Разнообразие

Односвязный циклический
L
Двусвязный линейный
L
0
0
Двусвязный циклический
L
Каждый элемент
двусвязного списка
хранит два адреса –
следующего и
предыдущего элемента
typedef struct Dlist
{
struct Dlist *next,
*prev;
int data;
}Dlist;

8. Функции. Создание одного элемента

Элементы списков почти всегда создаются в динамической памяти
typedef struct ListElt
{
struct ListElt *next;
int data;
}ListElt;
ListElt* createList(int x)
{
ListElt* p=malloc(sizeof(ListElt));
p->next=0;
p->data=x;
return p;
}
0
x
Функция создания одного элемента некоторой структуры в
динамической памяти всегда выглядит примерно одинаково: создаём
указатель и выделяем память, заполняем данные, возвращаем указатель
на созданный элемент.

9. Добавление элемента в начало списка

Просто создадим новый элемент и скажем, что начало старой цепочки следует
за ним.
ListElt* addFirst(ListElt* h, int x)
{
ListElt* p=createList(x);
p->next=h;
return p;
}
//или так, с дублированием кода
ListElt* addFirst(ListElt* h, int x)
{
ListElt* p=malloc(sizeof(ListElt));
p->data=x;
p->next=h;
p
h h
return p;
}
x
…
…
0
…
…
Использование
L=addFirst(L, 42);//добавить в начало списка L элемент с
числом 42

10. Итерирование

(Обход-осмотр всех элементов «хранилища данных» для выполнения
некоторой операции с каждым из них)
Массив и печать массива
int A[10], i;//i-"бегущий номер"
...
for(i=0; i<10; ++i)
printf("%d ", A[i]);
Список и печать списка
ListElt *L, *cur; //cur-"бегущий указатель"
...
for(cur=L; cur; cur=cur->next)
printf("%d ", cur->data);
Указатель cur последовательно пробегает все элементы списка. Цепочка
элементов при этом не нарушается. cur
L
0
…
…
…
…

11. Добавление элемента в конец

Чтобы добавить или удалить элемент в позиции с заданным свойством, нужно
найти предшественника удаляемого или нового элемента.
ListElt* addLast(ListElt *h, int x)
{
ListElt *cur; //cur-"бегущий указатель"
if(!h)
return createList(x);//особый случай
for(cur=h; cur->next; cur=cur->next);//пустой цикл
cur->next=createList(x);
return h;
}
Если список не пуст, указатель cur последовательно пробегает все
элементы списка и останавливается на последнем элементе
cur
h
0
…
…
…
…

12. Удаление всего списка

Поскольку для каждого элемента команда выделения памяти была вызвана
отдельно, команду освобождения памяти тоже нужно вызвать для каждого
элемента.
void destroyList(ListElt *h)
{
ListElt *del; //del-"удаляемый элемент"
while(h)
{
del=h;
h=h->next;
free(del);
}
}
Перед тем, как стереть элемент, запоминаем следующий за ним, - иначе
будет утечка памяти.
del
h
0
…
…
…
…

13. Задачи

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

14. Комментарии

Структура «списка» определяется только наличием указателя на следующий
элемент. Хранимые данные могут быть любого типа.
Для списков (и других структур на основе указателей) характерны
дополнительные расходы памяти собственно на хранение указателей.
При перестроении списка нигде не происходит перезапись хранимых данных
из одного элемента в другой, меняются только указатели next.
Операции резервирования и очистки памяти – одни из самых медленных
«элементарных» операций по работе с памятью. Если предполагается
большое число добавлений и удалений элементов, часть неиспользуемых
элементов стоит не очищать с помощью free, а поместить в отдельный список
«пустых» элементов.

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

Структура «списка» определяется только наличием указателя на следующий
элемент. Хранимые данные могут быть любого типа.
Например, можно создать массив из списков, или список из массивов, или
«иерархический список», элементы которого будут хранить другие списки.
A[0]
A[1]
A[2]
A[3]
0
Массив списков
ListElt *A[4];
0
Иерархический список
ListOfListsElt *L;

16. Управляющие структуры

«Управляющая структура» или «оболочка» может хранить начало списка и
другую информацию о нём. При написании функций для таких структур это
избавляет от необходимости возвращать новое начало списка, позволяя
вернуть более полезный ответ, а в ряде случаев ускоряет работу.
Пример «Очередь»
typedef struct ListElt//элемент
{
struct ListElt *next;
int data;
}ListElt;
typedef struct Queue//оболочка
{
ListElt *first, *last;
}Queue;
Очевидно, что операция
добавления элемента в конец
будет выполняться быстрее.
оболочка Queue
0 элементы ListElt