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

структуры данных
Шевченко А. В.

и динамические структуры данных
Структуры данных
Статические
Динамические
Структуры
Объединения
Массивы
Списки
Графы
Деревья

структуры данных
"Я женился на вдове, у которой была взрослая дочь.

Мой отец, часто навещавший нас, влюбился в мою падчерицу и женился на ней. Следовательно, мой отец стал моим зятем, а моя падчерица - моей мачехой. Спустя несколько месяцев моя жена родила сына, который стал шурином моего отца и одновременно моим дядей. У жены моего отца, то есть моей падчерицы, тоже родился сын. Таким образом, у меня появился брат и одновременно внук. Моя жена является моей бабушкой, так как она мать моей мачехи. Следовательно, я муж моей жены и одновременно ее внук, другими словами - я собственный дедушка."

Из одной цюрихской газеты, июль 1922 года.

списки
18
44
44
55
55
Заголовок
first: 18
18
44
44
55
55
Заголовок
first: 18
last: 55
18
44
Петров
Сидоров

обхода списка
typedef struct {short code; char name[24]; short next;} PERS;

PERS

pers[] = {{ 1, "Александров", 0}, ...
{18, "Иванов", 44}, ...
{44, "Петров", 55}, ...
{55, "Сидоров", 0}, ... };

int first = 18;

while(first)
{
int i = first-1;
printf(pers[i].name);
first = pers[i].next;
}

в список
18
44
44
03
55
Заголовок
first: 18
last: 55
18
03
03
55
44
18
44
44
55
55
Заголовок
first: 18
last: 55
18
44

включения в список
typedef struct {short code; char name[24]; short next;

short prev;} PERS;

PERS pers[] = {{ 1, "Александров", 0, 0}, ...
{03, "Антонов", 0, 0}, ...
{18, "Иванов", 44, 0}, ...
{44, "Петров", 55, 18}, ...
{55, "Сидоров", 0, 44}, ... };

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;

А. В.
Исключение из списка
18
03
55
Заголовок
first: 18
last: 55
03
03
55
18

исключения из списка
typedef struct {short code; char name[24]; short next;

short prev;} PERS;

PERS pers[] = {{ 1, "Александров", 0, 0}, ...
{03, "Антонов", 55, 44}, ...
{18, "Иванов", 44, 0}, ...
{44, "Петров", 3, 18}, ...
{55, "Сидоров", 0, 3}, ... };

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;

стек
Очередь (FIFO)



Стек (LIFO)



Дисциплина очереди

- первым вошел - первым вышел

Дисциплина стека - последним вошел - первым вышел

реализации очереди
int queue[100];
int n = 0;

void QueueIn(int Value)
{
queue[n++]

= Value;
}

int QueueOut()
{
int value = queue[0];
n--;

for(int i = 0; i < n; i++)
queue[i] = queue[i+1];

return(value);
}

void main()
{
QueueIn(18);
QueueIn(44);
QueueIn(3);
QueueIn(55);

while(n)
{
int next = QueueOut();
...
}
}

реализации стека
int stack[100];
int n = 0;

void StackIn(int Value)
{
stack[n++]

= Value;
}

int StackOut()
{
return(stack[--n]);
}

void main()
{
StackIn(18);
StackIn(44);
StackIn(3);
StackIn(55);

while(n)
{
int next = StackOut();
...
}
}

М8
Болт М8х40
1
1
1
2
1
1
2
1
36
1
1
Гайка М8
Задача расчета потребности в ресурсах для партии в

100 шт.
Вариант 1: дерево

обхода дерева. Структура данных
typedef struct
{
short code;

float quant;
} CHILD;

typedef struct
{
short code;
char name[32];
CHILD childs[8];
int nchild;
} PROD;

ИЗДЕЛИЕ

имеет

1

Код

Наименование

Число комплектующих

КОМПЛЕКТУЮЩЕЕ

Количество

М

является

1

М

обхода дерева. Данные
PROD prod[] =
{
{ 1, "Велосипед",

{{2, 1}, {3, 2}, {4, 1}, {5, 1}}, 4},
{ 2, "Рама", {}, 0},
{ 3, "Колесо", {{6, 36}, {7, 1}, {8, 1}, {9, 1}}, 4},
{ 4, "Руль", {}, 0},
{ 5, "Седло", {{10, 1}, {11, 1}}, 2},
{ 6, "Спица", {}, 0},
{ 7, "Обод", {}, 0},
{ 8, "Шина", {}, 0},
{ 9, "Втулка", {{10, 2}}, 1},
{10, "Гайка М8", {}, 0},
{11, "Болт М8х40", {}, 0}
};

обхода дерева. Пример реализации
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);
}

обхода дерева. Результат
Велосипед : 100
Рама :

100
Колесо : 200
Спица : 7200
Обод : 200
Шина : 200
Втулка : 200
Гайка М8 : 400
Руль : 100
Седло : 100
Гайка М8 : 100
Болт М8х40 : 100

М8
Болт М8х40
1
1
1
2
1
1
2
1
36
1
1
Задача расчета потребности в ресурсах для партии в 100

шт.
Вариант 2: ациклический граф

name[32];
CHILD childs[8];
int nchild;
int

count;
int quant;
} PROD;

Программирование и основы алгоритмизации

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

19

Шевченко А. В.

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

void graphmark(short code)
{
PROD* p = &prod[code-1];

if(++p->count > 1) return;

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);
...
}

1

1

1

1

1

1

1

1

1

2

name[32];
CHILD childs[8];
int nchild;
int

count;
int quant;
} PROD;

Программирование и основы алгоритмизации

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

20

Шевченко А. В.

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

void graphcalc(short code, int Quant)
{
PROD* p = &prod[code-1];
p->quant += Quant;

if(--p->count > 0) return;

printf("%s %d\n", p->name, 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);
}

1

1

1

1

1

1

1

1

1

2

обхода графа. Результат
Велосипед : 100
Рама :

100
Колесо : 200
Спица : 7200
Обод : 200
Шина : 200
Втулка : 200
Руль : 100
Седло : 100
Гайка М8 : 500
Болт М8х40 : 100

между операторами и структурами данных
"Образ"
Операторы
Атомарный объект
Присваивание
Перечисление
Составной оператор
C++
=
{ ; ; }
Данные
Простой

тип

Запись

C++

char, short

struct

Выбор

Условный оператор

if

Объединение

union

Предопределенное
повторение

Цикл с параметром

for

Массив

[]

Повторение

Цикл с условием

while

Список

*p

Рекурсия

Процедура

f()

Дерево

*p

Граф

Оператор перехода

goto

Сеть

*p