Тема 9. Динамические структуры данных
Статические и динамические структуры данных
Динамические структуры данных
Линейные списки
Пример обхода списка
Включение в список
Пример включения в список
Исключение из списка
Пример исключения из списка
Очередь, стек
Пример реализации очереди
Пример реализации стека
Деревья
Алгоритм обхода дерева. Структура данных
Алгоритм обхода дерева. Данные
Алгоритм обхода дерева. Пример реализации
Алгоритм обхода дерева. Результат
Графы
Алгоритм обхода графа. Разметка
Алгоритм обхода графа. Расчет
Алгоритм обхода графа. Результат
Соответствие между операторами и структурами данных
414.00K
Category: programmingprogramming

Динамические структуры данных. Тема 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
English     Русский Rules