Динамические структуры данных. Тема 9

1. Тема 9. Динамические структуры данных

Программирование и основы алгоритмизации
Тема 9. Динамические структуры
данных
Шевченко А. В.
Тема 09. Динамические структуры данных
1

2. Статические и динамические структуры данных

Программирование и основы алгоритмизации
Статические и динамические структуры данных
Структуры
данных
Статические
Структуры
Массивы
Динамические
Списки
Объединения
Шевченко А. В.
Тема 09. Динамические структуры данных
Деревья
Графы
2

3. Динамические структуры данных

Программирование и основы алгоритмизации
Динамические структуры данных
"Я женился на вдове, у которой была
взрослая дочь. Мой отец, часто навещавший нас,
влюбился в мою падчерицу и женился на ней.
Следовательно, мой отец стал моим зятем, а моя
падчерица - моей мачехой. Спустя несколько месяцев
моя жена родила сына, который стал шурином
моего отца и одновременно моим дядей. У жены
моего отца, то есть моей падчерицы, тоже родился
сын. Таким образом, у меня появился брат и
одновременно внук. Моя жена является моей
бабушкой, так как она мать моей мачехи.
Следовательно, я муж моей жены и одновременно ее
внук, другими словами - я собственный дедушка."
Из одной цюрихской газеты, июль 1922 года.
Шевченко А. В.
Тема 09. Динамические структуры данных
3

4. Линейные списки

Программирование и основы алгоритмизации
Линейные списки
Код
Фамилия
Заголовок
01
Александров
first: 18
02
Алексеев
03
Антонов
...
...
18
Иванов
19
Михайлов
Заголовок
...
...
first: 18
44
Петров
last:
...
...
55
Сидоров
56
Тимофеев
55
18
44
44
55
18
44
44
55
18
55
55
44
Иванов
Петров
Сидоров
Шевченко А. В.
Тема 09. Динамические структуры данных
4

5. Пример обхода списка

Программирование и основы алгоритмизации
Пример обхода списка
typedef struct {short code; char name[24]; short next;} PERS;
PERS pers[] = {{ 1,
{18,
{44,
{55,
"Александров", 0}, ...
"Иванов",
44}, ...
"Петров",
55}, ...
"Сидоров",
0}, ... };
int first = 18;
while(first)
{
int i = first-1;
printf(pers[i].name);
first = pers[i].next;
}
Шевченко А. В.
Тема 09. Динамические структуры данных
5

6. Включение в список

Программирование и основы алгоритмизации
Включение в список
Заголовок
first: 18
18
44
last:
44
55
55
55
18
44
Заголовок
first: 18
18
44
last:
44
03
55
55
18
03
03
55
44
Шевченко А. В.
Тема 09. Динамические структуры данных
6

7. Пример включения в список

Программирование и основы алгоритмизации
Пример включения в список
typedef struct {short code; char name[24]; short next;
short prev;} PERS;
PERS pers[] = {{ 1,
{03,
{18,
{44,
{55,
"Александров", 0, 0}, ...
"Антонов",
0, 0}, ...
"Иванов",
44, 0}, ...
"Петров",
55, 18}, ...
"Сидоров",
0, 44}, ... };
55 44
3
3
int сurrent = 44;
int insert = 3;
int i = current-1;
int j = insert-1;
pers[pers[i].next-1].prev = insert;
pers[j].next = pers[i].next;
pers[i].next = insert;
pers[j].prev = current;
Шевченко А. В.
Тема 09. Динамические структуры данных
7

8. Исключение из списка

Программирование и основы алгоритмизации
Исключение из списка
Заголовок
first: 18
18
44
03
last:
44
03
55
18
44
03
55
55
55
Заголовок
first: 18
18
03
last:
03
55
55
18
Шевченко А. В.
Тема 09. Динамические структуры данных
03
8

9. Пример исключения из списка

Программирование и основы алгоритмизации
Пример исключения из списка
typedef struct {short code; char name[24]; short next;
short prev;} PERS;
PERS pers[] = {{ 1,
{03,
{18,
{44,
{55,
"Александров", 0, 0}, ...
"Антонов",
55, 44}, ...
"Иванов",
44, 0}, ...
"Петров",
3, 18}, ...
"Сидоров",
0, 3}, ... };
18
3
0
0
int current = 44;
int i = current-1;
pers[pers[i].next-1].prev = pers[i].prev;
pers[pers[i].prev-1].next = pers[i].next;
pers[i].next = 0;
pers[i].prev = 0;
Шевченко А. В.
Тема 09. Динамические структуры данных
9

10. Очередь, стек

Программирование и основы алгоритмизации
Очередь, стек
Очередь (FIFO)
Стек (LIFO)
Дисциплина очереди - первым
вошел - первым вышел
Дисциплина стека - последним
вошел - первым вышел
Шевченко А. В.
Тема 09. Динамические структуры данных
10

11. Пример реализации очереди

Программирование и основы алгоритмизации
Пример реализации очереди
int queue[100];
int n = 0;
void QueueIn(int Value)
{
queue[n++] = Value;
}
int QueueOut()
{
int value = queue[0];
n--;
void main()
{
QueueIn(18);
QueueIn(44);
QueueIn(3);
QueueIn(55);
while(n)
{
int next = QueueOut();
...
}
for(int i = 0; i < n; i++)
queue[i] = queue[i+1];
return(value);
}
}
Шевченко А. В.
Тема 09. Динамические структуры данных
11

12. Пример реализации стека

Программирование и основы алгоритмизации
Пример реализации стека
int stack[100];
int n = 0;
void StackIn(int Value)
{
stack[n++] = Value;
}
void main()
{
StackIn(18);
StackIn(44);
StackIn(3);
StackIn(55);
while(n)
{
int next = StackOut();
...
}
int StackOut()
{
return(stack[--n]);
}
}
Шевченко А. В.
Тема 09. Динамические структуры данных
12

13. Деревья

Программирование и основы алгоритмизации
Деревья
Велосипед
1
1
2
Рама
1
Колесо
Седло
Руль
1
36
Спица
1
1
1
Обод
Втулка
1
Болт М8х40
Шина
2
Гайка М8
Гайка М8
Задача расчета потребности в ресурсах для партии в 100 шт.
Вариант 1: дерево
Шевченко А. В.
Тема 09. Динамические структуры данных
13

14. Алгоритм обхода дерева. Структура данных

Программирование и основы алгоритмизации
Алгоритм обхода дерева. Структура данных
typedef struct
{
short code;
float quant;
} CHILD;
typedef struct
Код
ИЗДЕЛИЕ
1
является
М
1
Наименование
short code;
Число комплектующих
char
name[32];
CHILD childs[8];
имеет
int
М
КОМПЛЕКТУЮЩЕЕ
Шевченко А. В.
{
Количество
Тема 09. Динамические структуры данных
nchild;
} PROD;
14

15. Алгоритм обхода дерева. Данные

Программирование и основы алгоритмизации
Алгоритм обхода дерева. Данные
PROD prod[] =
{
{ 1, "Велосипед",
{ 2, "Рама",
{ 3, "Колесо",
{ 4, "Руль",
{ 5, "Седло",
{ 6, "Спица",
{ 7, "Обод",
{ 8, "Шина",
{ 9, "Втулка",
{10, "Гайка М8",
{11, "Болт М8х40",
};
Шевченко А. В.
{{2, 1}, {3, 2}, {4, 1}, {5, 1}}, 4},
{}, 0},
{{6, 36}, {7, 1}, {8, 1}, {9, 1}}, 4},
{}, 0},
{{10, 1}, {11, 1}}, 2},
{}, 0},
{}, 0},
{}, 0},
{{10, 2}}, 1},
{}, 0},
{}, 0}
Тема 09. Динамические структуры данных
15

16. Алгоритм обхода дерева. Пример реализации

Программирование и основы алгоритмизации
Алгоритм обхода дерева. Пример реализации
void treenode(short code, int Quant)
{
PROD* p = &prod[code-1];
printf("%s : %d\n", p->name, Quant);
for(int i = 0; i < p->nchild; i++)
treenode(p->childs[i].code,
p->childs[i].quant*Quant);
}
void main()
{
treenode(1, 100);
}
Шевченко А. В.
Тема 09. Динамические структуры данных
16

17. Алгоритм обхода дерева. Результат

Программирование и основы алгоритмизации
Алгоритм обхода дерева. Результат
Велосипед
1
1
2
Рама
1
Колесо
Седло
Руль
1
36
Спица
1
1
1
Обод
Втулка
1
Болт М8х40
Шина
2
Гайка М8
Велосипед
Рама
Колесо
Спица
Обод
Шина
Втулка
Гайка М8
Руль
Седло
Гайка М8
Болт М8х40
: 100
: 100
: 200
: 7200
: 200
: 200
: 200
: 400
: 100
: 100
: 100
: 100
Гайка М8
Шевченко А. В.
Тема 09. Динамические структуры данных
17

18. Графы

Программирование и основы алгоритмизации
Графы
Велосипед
1
1
2
Рама
1
Колесо
Седло
Руль
1
36
Спица
1
1
1
Обод
Втулка
Шина
Болт М8х40
1
2
Гайка М8
Задача расчета потребности в ресурсах для партии в 100 шт.
Вариант 2: ациклический граф
Шевченко А. В.
Тема 09. Динамические структуры данных
18

19. Алгоритм обхода графа. Разметка

Программирование и основы алгоритмизации
Алгоритм обхода графа. Разметка
1
void graphmark(short code)
{
PROD* p = &prod[code-1];
1
1
if(++p->count > 1) return;
1
1
2
1
1
1
1
typedef struct {
short code;
char name[32];
CHILD childs[8];
int
nchild;
int
count;
int
quant;
} PROD;
Шевченко А. В.
}
for(int i = 0; i < p->nchild; i++)
graphmark(p->childs[i].code);
void main()
{
for(int i = 0; i < NPROD; i++)
{
prod[i].count = 0;
prod[i].quant = 0;
}
}
graphmark(1);
...
Тема 09. Динамические структуры данных
19

20. Алгоритм обхода графа. Расчет

Программирование и основы алгоритмизации
Алгоритм обхода графа. Расчет
1
1
1
1
1
if(--p->count > 0) return;
2
1
printf("%s %d\n", p->name, Quant);
1
1
1
typedef struct {
short code;
char name[32];
CHILD childs[8];
int
nchild;
int
count;
int
quant;
} PROD;
Шевченко А. В.
void graphcalc(short code, int Quant)
{
PROD* p = &prod[code-1];
p->quant += Quant;
for(int i = 0; i < p->nchild; i++)
graphcalc(p->childs[i].code,
p->childs[i].quant*p->quant);
}
void main()
{
...
graphcalc(1, 100);
}
Тема 09. Динамические структуры данных
20

21. Алгоритм обхода графа. Результат

Программирование и основы алгоритмизации
Алгоритм обхода графа. Результат
Велосипед
1
1
2
Рама
Колесо
1
Седло
Руль
1
36
Спица
1
Обод
1
1
Втулка
Шина
2
1
Болт М8х40
Велосипед
Рама
Колесо
Спица
Обод
Шина
Втулка
Руль
Седло
Гайка М8
Болт М8х40
: 100
: 100
: 200
: 7200
: 200
: 200
: 200
: 100
: 100
: 500
: 100
Гайка М8
Шевченко А. В.
Тема 09. Динамические структуры данных
21

22. Соответствие между операторами и структурами данных

Программирование и основы алгоритмизации
Соответствие между операторами и структурами данных
"Образ"
Операторы
C++
Данные
C++
Атомарный объект
Присваивание
=
Простой тип
char, short
Перечисление
Составной оператор
{ ; ; }
Запись
struct
Выбор
Условный оператор
if
Объединение
union
Предопределенное
повторение
Цикл с параметром
for
Массив
[]
Повторение
Цикл с условием
while
Список
*p
Рекурсия
Процедура
f()
Дерево
*p
Граф
Оператор перехода
goto
Сеть
*p
Шевченко А. В.
Тема 09. Динамические структуры данных
22