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

1.

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

2.

Связный список
разновидность линейных структур данных,
представляющая собой последовательность элементов,
обычно отсортированную в соответствии с заданным
правилом. Последовательность может содержать любое
количество элементов, поскольку при создании списка
используется динамическое распределение памяти
Язык Си. Тема 11
2

3.

Создание структуры для
связного списка
typedef struct node {
int value;
struct node * pnext;
}Node;
Язык Си. Тема 11
3

4.

Добавление элемента в
список
void add2list(Node **pphead, int val)
{
Node **pp = pphead, *pnew;
while(*pp)
{
if(val < (*pp)->value)
break;
else
pp = &((*pp)->pnext);
}
pnew = (Node*)malloc(sizeof(Node));
pnew->value = val;
pnew->pnext = *pp;
*pp = pnew;
}
Язык Си. Тема 11
4

5.

Печать списка
void print(Node *phead)
{
Node* p = phead;
while(p)
{
printf(“%d ”, p->value);
p = p->pnext;
}
printf(“\n”);
}
Язык Си. Тема 11
5

6.

Удаление списка
void deleteList(Node *phead)
{
if(phead)
{
deleteList(phead->pnext);
if(phead)
free(phead);
}
}
Язык Си. Тема 11
6

7.

Работа со списком
int main()
{
Node *phead = 0;
srand(time(0));
for(int i = 0; i < 10; ++i)
add2list(&phead, rand() % 100);
printf("Elements of the list:\n");
print(phead);
deleteList(phead);
}
Язык Си. Тема 11
7

8.

Стек
список типа LIFO (last in first out – последним вошел –
первым вышел).
При работе со стеком предполагаются только две
операции:
занесение элемента в вершину стека
удаление элемента, находящегося в вершине стека
Язык Си. Тема 11
8

9.

Создание структуры для
стека
typedef struct node {
int value;
struct node* pnext;
}Node;
Язык Си. Тема 11
9

10.

Добавление элемента в стек
Node* push(Node* phead, int v)
{
Node *p = (Node*)malloc(sizeof(Node));
p->value=v;
p->pnext = phead;
return p;
}
Язык Си. Тема 11
10

11.

Удаление элемента из стека
Node* pop(Node* phead)
{
Node *p = phead->pnext;
free(phead);
return p;
}
Язык Си. Тема 11
11

12.

Проверка, не пустой ли стек
int IsEmpty(Node *phead)
{
if(phead)
return 0;
return 1;
}
Язык Си. Тема 11
12

13.

Работа со стеком
int main() {
srand(time(0));
Node *head=0;
for(int i=0; i<10; i++) {
head=push(head, rand()%100+1);
}
while(!IsEmpty(head)) {
head = pop(head);
}
return 0;
}
Язык Си. Тема 11
13

14.

Очередь
структура данных типа FIFO (first in first out – первым
вошел - первым вышел).
Узлы очереди удаляются только из головы очереди, а
помещаются в очередь только в ее хвосте
Язык Си. Тема 11
14

15.

Создание структуры для
очереди
typedef struct queue
{
char* str;
struct queue* next;
}Queue;
Язык Си. Тема 11
15

16.

Добавление элемента в
очередь
Queue* add2Queue(char* s, Queue* phead)
{
Queue* pnew= (Queue*)malloc(sizeof(Queue));
Queue *p = phead;
while(p && p->next)
{
p=p->next;
}
pnew->str = (char*)malloc(strlen(s)+1);
pnew->next = NULL;
strcpy(pnew->str, s);
if(p)
p->next = pnew;
if(phead)
return phead;
return pnew;
}
Язык Си. Тема 11
16

17.

Удаление элемента из
очереди
Queue* deleteFromQueue(Queue *phead)
{
Queue *p = NULL;
if(phead)
p=phead->next;
free(phead->str);
free(phead);
return p;
}
Язык Си. Тема 11
17

18.

Печать очереди
void printQueue(Queue* phead)
{
while(phead)
{
printf(“%s\n”,phead->str);
phead = phead->next;
}
}
Язык Си. Тема 11
18

19.

Работа с очередью
int main() {
Queue * head = NULL;
char stroka[255];
printf("Enter a string:\n");
gets(stroka);
while(strlen(stroka)) {
char raz[] = {' ', '\t', '\0'};
char *s=strtok(stroka, raz);
while(s) {
head = add2Queue(s, head);
s = strtok(NULL, raz);
}
printf("Enter a string:\n");
gets(stroka);
}
printQueue(head);
while(head)
head = deleteFromQueue(head);
return 0;
}
Язык Си. Тема 11
19

20.

Бинарное дерево поиска
Дерево является нелинейной двумерной структурой
данных с особыми свойствами.
Бинарные деревья содержат по два указателя. Или один
из них, или оба могут быть нулевыми. Корневой узел
является первым узлом дерева.
Бинарное дерево поиска строится таким образом, что
все элементы левого поддерева меньше корня, а все
элементы правого – больше.
Язык Си. Тема 11
20

21.

Структура для бинарного
дерева поиска
typedef struct node
{
int num;
struct node* left;
struct node* right;
}Node;
Язык Си. Тема 11
21

22.

Добавление элемента в
дерево
Node* add(Node* root, int a)
{
if(!root)
{
Node *pnew = (Node*) malloc(sizeof(Node));
pnew->num = a;
pnew->left = NULL;
pnew->right = NULL;
root = pnew;
}
else if(root->num < a)
root->right = add(root->right, a);
else
root->left = add(root->left, a);
return root;
}
Язык Си. Тема 11
22

23.

Симметричный обход
дерева
void in(Node *root)
{
if(root)
{
in(root->left);
printf(”%d “,root->num);
in(root->right);
}
}
Язык Си. Тема 11
23

24.

Функция печати дерева
«на боку»
void print(Node* root, int level)
{
if(root)
print(root->right, level+1);
for(int i=0; i<level; i++)
printf("
");
if(root)
printf(“%d
%d\n“ , root->num, level);
else
printf("#\n");
if(root)
print(root->left, level+1);
}
Язык Си. Тема 11
24

25.

Функция удаления элемента
Node* del(Node* root, int a) {
if(!root) {
printf("No such element!\n");
return NULL;
}
else if(root->num == a) {
root = delNode(root);
return root;
}
else if(root->num < a) {
root->right = del(root->right, a);
return root;
}
else {
root->left = del(root->left, a);
return root;
}
}
Язык Си. Тема 11
25

26.

Функция удаления
найденного элемента
Node* delNode(Node* elem){
if(!elem->left&&!elem->right) {
free(elem);
return NULL;
}
else if((elem->left&&!elem->right)||(!elem->left&&elem->right))
Node *p = elem;
if(elem->left) {
elem = elem->left;
p->left = NULL;
}
else {
elem = elem->right;
p->right = NULL;
}
free(p);
return elem;
}
else {
int a;
replace(&(elem->right), &a);
elem->num = a;
return elem;
}
}
Язык Си. Тема 11
{
26

27.

Функция замещения
удаленного элемента
void replace(Node** elem, int* a)
{
if((*elem)->left)
replace(&((*elem)->left), a);
else
{
*a = (*elem)->num;
Node *p = *elem;
*elem = (*elem)->right;
p->right = NULL;
free(p);
}
}
Язык Си. Тема 11
27

28.

Работа с бинарным деревом
поиска
int main() {
Node* root = NULL;
srand(time(0));
for(int i = 0; i<10; i++) {
int a = rand()%101-50;
root = add(root, a);
}
print(root,0);
int a;
scanf(“%d”, &a);
root = del(root, a);
printf(“\n\n”);
print(root,0);
printf("\npost\n");
post(root);
printf("\nin\n");
in(root);
printf("\npost\n");
pre(root);
printf("\n");
return 0;
}
Язык Си. Тема 11
28

29.

Обход дерева каталогов
Создание структуры
typedef struct node
{
char* data;
struct node* child;
struct node* brother;
}Node;
Язык Си. Тема 11
29

30.

Создание дерева
Node* Create(char * data)
{
Node* root = (Node*) malloc(sizeof(Node));
root->data = data;
root->brother = NULL;
root->child = NULL;
return root;
}
Язык Си. Тема 11
30

31.

Добавление «брата»
Node* AddBrother(Node* oldbrother, char* data)
{
Node* p = oldbrother;
while(p&& p->brother)
p = p->brother;
Node* temp;
temp = (Node*)malloc(sizeof(Node));
temp->data
= data;
temp->brother = NULL;
temp->child
= NULL;
if(p)
p->brother = temp;
else
p = temp;
return oldbrother;
}
Язык Си. Тема 11
31

32.

Добавление «ребенка»
Node* AddChild(Node * par, char* data)
{
if(par->child)
par->child = AddBrother(par->child, data);
else
{
par->child = (Node*) malloc(sizeof(Node));
par->child->data
= data;
par->child->child
= NULL;
par->child->brother = NULL;
}
return par;
}
Язык Си. Тема 11
32

33.

Функция печати
void Print(Node* root, int level, FILE *fout)
{
Node* p = root;
for(int i=0; i<level; i++)
fprintf(fout,"
");
fprintf(fout, "%s\n", p->data);
if(p->child)
Print(p->child, level+1, fout);
if(p->brother)
Print(p->brother, level, fout);
}
Язык Си. Тема 11
33

34.

Функция удаления дерева
Node* Delete(Node* root)
{
Node* p = root;
if(p->brother)
p->brother = Delete(p->brother);
if(p->child)
p->child
= Delete(p->child);
free(p);
return 0;
}
Язык Си. Тема 11
34

35.

Обход дерева каталогов
Node* Go(char* path, Node* root)
{
_finddata_t fc;
intptr_t hFile = _findfirst(path, &fc);
if(!hFile)
return root;
_findnext(hFile, &fc);
while(_findnext(hFile, &fc) == 0)
{
char* temp = MakeString(fc.name);
if( fc.attrib & _A_SUBDIR)
{
root = AddChild(root, temp);
char path1 [1000];
strcpy(path1, path);
strcpy(path1+strlen(path1)-1, fc.name);
strcat(path1, "\\*");
Node* p = root->child;
while(p->brother)
p = p->brother;
p = Go(path1, p);
}
else
root = AddChild(root, temp);
}
root;
Языкreturn
Си. Тема 11
}
35

36.

Создание копии переданной
строки
char* MakeString(char* str)
{
char * temp = (char*)malloc(strlen(str)+1);
strcpy(temp, str);
return temp;
}
Язык Си. Тема 11
36

37.

Начало обхода
Node* MakeTree(char* path, Node* root)
{
char* data = MakeString(path);
strcat(path, "\\*");
root = Create(path);
root = Go(path, root);
return root;
}
Язык Си. Тема 11
37

38.

Работа с деревом каталогов
int main()
{
FILE* fout;
fout= fopen("1.txt","w");
Node* root = NULL;
char path[1000] = "C:\\Distrib";
root = MakeTree(path, root);
Print(root, 0, fout);
fclose(fout);
return 0;
}
Язык Си. Тема 11
38

39.

Конец
Язык Си. Тема 11
39