Загвоздка с деревом, динамические структуры данных - C (СИ)
Формулировка задачи:
Всем доброго времени суток.
Столкнулся с такой проблемой. В языке С новичок и нужно написать программу с динамическими структурами данных.
Программу, реализующую структуру данных и методы работы с ней, а также дополнительный метод обработки (1)
Элементом структуры должно быть целое число.
(1) Двоичное дерево, минимальное значение, пример результата = 57, для следующих элементов 10, 5, 6, 23, 11, 2.
Также нужно вставить обязательно в программу следующие блоки кода.
1) Вставка элемента
void tree_insert( node* root, int x );
void tree_print( node* root );
void tree_remove( node* root, int x );
void tree_erase ( node* root );
#include <stdio.h> #include <stdlib.h> struct node { int data; struct node * next; }; void CreateList(node * list) { list->next=NULL; }; void list_insert(node *list, int x) { node *uzel; if (list->next == NULL) { list->next = (node *) malloc(sizeof(uzel)); list->next->data = x; list->next->next = NULL; return; }; if (list->next->data >= x) { uzel = (node *) malloc(sizeof(uzel)); uzel->data = x; uzel->next = list->next; list->next = uzel; } else { list_insert(list->next, x); } }; void list_remove(node *list, int x) { node * tmp; if(list->next->data == x) { tmp = list->next->next; free(list->next); list->next = tmp; } else { list_remove(list->next, x); } }; void list_erase(node *list){ node * tmp; tmp = list->next; int ms[100]={0}; int ix=0; while(tmp !=NULL) { node* next=tmp->next; free(tmp); tmp=next; } list->next=NULL; } void list_print(node *list) { node * tmp; if(list->next == NULL) { printf("List is empty"); return; } tmp = list->next; while(tmp !=NULL) { printf("%d ",tmp->data); tmp=tmp->next; }; }; int difference(node *list) { int i = 0 ; node * tmp = list; int max=tmp->next->data; int min=tmp->next->data; while(tmp->next != NULL) { if(tmp->next->data >max){ max=tmp->next->data; } if(tmp->data <min){ min=tmp->data; } i++; tmp=tmp->next; }; return max-min; }; int main () { node list; CreateList(&list); int i=0; while(i<15){ list_insert(&list, rand() % 111); i++; } printf("\nPrinting all of the elements....\n"); list_print(&list); list_remove(&list, 7); list_remove(&list, 41); list_remove(&list, 44); list_remove(&list, 54); list_remove(&list, 62); printf("\n\nPrinting all of the elements after removing 5 of them....\n"); list_print(&list); printf("\n\nThe difference between maximum and minimum : %d\n", difference(&list)); return 0; };
Решение задачи: «Загвоздка с деревом, динамические структуры данных»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef struct _node { int x; struct _node* left; struct _node* right; } node; node* tree_insert(node** root, int x); void tree_remove(node** root, int x); void tree_print(FILE* _out, const node* root); void tree_erase(node* root); int main(void){ int i; node* tr = NULL; for(i = 0; i < 30; ++i) tree_insert(&tr, rand() % 10); tree_print(stdout, tr); putchar('\n'); tree_remove(&tr, 5); tree_remove(&tr, 6); tree_remove(&tr, 7); tree_print(stdout, tr); tree_erase(tr); return 0; } //вставка node* tree_insert(node** root, int x){ node* p = *root; while(p != NULL){ if(x == p->x) return p; else if(x < p->x){ root = &p->left; p = p->left; } else { root = &p->right; p = p->right; } } p = (node*)malloc(sizeof(node)); if(p != NULL){ p->x = x; p->left = p->right = NULL; *root = p; } return p; } //удаление void tree_remove(node** root, int x){ node* p1, *p2, *p = *root; while(p != NULL){ if(x == p->x) break; else if(x < p->x){ root = &p->left; p = p->left; } else { root = &p->right; p = p->right; } } if(p == NULL) return; else if(p->right == NULL) *root = p->left; else { p2 = p->right; if(p2->left == NULL){ p2->left = p->left; *root = p2; } else { for(p1 = p2->left; p1->left != NULL; p1 = p2->left) p2 = p1; p2->left = p1->right; p1->left = p->left; p1->right = p->right; *root = p1; } } free(p); } //печать void tree_print(FILE* _out, const node* root){ if(root != NULL){ if(root->left != NULL) tree_print(_out, root->left); fprintf(_out, "%d ", root->x); if(root->right != NULL) tree_print(_out, root->right); } } //удаление всех void tree_erase(node* root){ if(root != NULL){ if(root->left != NULL) tree_erase(root->left); if(root->right != NULL) tree_erase(root->right); free(root); } }
Объяснение кода листинга программы
- Создание дерева из 30 элементов со случайными значениями от 0 до 9.
- Вставка элемента 5 в дерево.
- Вставка элемента 6 в дерево.
- Вставка элемента 7 в дерево.
- Печать дерева на экран.
- Удаление элементов 5, 6, 7 из дерева.
- Печать дерева на экран.
- Удаление всех элементов из дерева.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д