Загвоздка с деревом, динамические структуры данных - 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 из дерева.
- Печать дерева на экран.
- Удаление всех элементов из дерева.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д