Разработать проект для обработки дерева поиска - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Разработать проект для обработки дерева поиска, каждый элемент которого содержит целочисленный ключ и строку текста, содержащую, например, ФИО и номер паспорта (ввод исходной информации рекомендуется записать в файл). В программе должны быть реализованы следующие возможности: -создание дерева -добавление новой записи -поиск информации по заданному ключу -удаление информации с заданным ключом -вывод информации -удаление из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы Язык Си

Решение задачи: «Разработать проект для обработки дерева поиска»

textual
Листинг программы 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <string.h>
  4. #define MAX_LEN  48
  5.  
  6. typedef struct _node {
  7.     unsigned key;
  8.     char     inf[MAX_LEN];
  9.     struct _node* left;
  10.     struct _node* right;
  11. } node;
  12. int   tree_insert(node** root, unsigned key, const char* inf);
  13. void  tree_remove(node** root, unsigned key);
  14. char* tree_search(node* root, unsigned key);
  15. void  tree_print(FILE* _out, const node* root);
  16. void  tree_clear(node* root);
  17. node* tree_open(const char* fn); 
  18.  
  19.  
  20. int main(void){
  21.     node* tr = tree_open("file.txt");
  22.     if(tr != NULL){
  23.         tree_print(stdout, tr);
  24.         tree_clear(tr);
  25.     }
  26.     getchar();
  27.     return 0;
  28. }
  29.  
  30. //загрузка из файла ключ Ф.И.О
  31. node* tree_open(const char* fn){
  32.     char     s[MAX_LEN], b[16];
  33.     unsigned k;
  34.  
  35.     node* tr = NULL;
  36.     FILE* fp = fopen(fn, "rt");
  37.     if(fp == NULL)
  38.         return NULL;
  39.  
  40.     sprintf(b, "%%u %%%d[^\n]", MAX_LEN - 1);
  41.     while(fscanf(fp, b, &k, s) == 2)
  42.         tree_insert(&tr, k, s);
  43.     
  44.     fclose(fp);
  45.     return tr;
  46. }
  47.  
  48. //вставка
  49. int tree_insert(node** root, unsigned key, const char* inf){
  50.     node* p = *root;
  51.     while(p != NULL){
  52.         if(key < p->key){
  53.             root = &p->left;
  54.             p    = p->left;
  55.         } else if(key > p->key){
  56.             root = &p->right;
  57.             p    = p->right;
  58.         } else
  59.             return 0;
  60.     }
  61.  
  62.     p = (node*)malloc(sizeof(node));
  63.     if(p != NULL){
  64.         p->key  = key;
  65.         strcpy(p->inf, inf);
  66.         p->left = p->right = NULL;
  67.         *root   = p;
  68.     }
  69.     return (p != NULL);
  70. }
  71.  
  72. //удаление
  73. void tree_remove(node** root, unsigned key){
  74.     node* p1, *p2, *p = *root;
  75.     while((p != NULL) && (p->key != key)){
  76.         if(key < p->key){
  77.             root = &p->left;
  78.             p    = p->left;
  79.         } else {
  80.             root = &p->right;
  81.             p    = p->right;
  82.         }
  83.     }
  84.  
  85.     if(p == NULL)
  86.         return;
  87.     else if(p->right == NULL)
  88.         *root = p->left;
  89.     else {
  90.         p2 = p->right;
  91.         if(p2->left == NULL){
  92.             p2->left = p->left;
  93.             *root    = p2;
  94.         } else {
  95.             for(p1 = p2->left; p1->left != NULL; p1 = p2->left)
  96.                 p2 = p1;
  97.  
  98.             p2->left  = p1->right;
  99.             p1->left  = p->left;
  100.             p1->right = p->right;
  101.             *root     = p1;
  102.         }
  103.     }
  104.     free(p);
  105. }
  106.  
  107. //поиск
  108. char* tree_search(node* root, unsigned key){
  109.     while((root != NULL) && (root->key != key)){
  110.         if(key < root->key)
  111.             root = root->left;
  112.         else
  113.             root = root->right;
  114.     }
  115.     return (root != NULL) ? &root->inf[0] : NULL;
  116. }
  117.  
  118. //печать
  119. void tree_print(FILE* _out, const node* root){
  120.     if(root != NULL){
  121.         if(root->left != NULL)
  122.             tree_print(_out, root->left);
  123.  
  124.         fprintf(_out, "KEY: %u\tINFO: %s\n", root->key, root->inf);
  125.  
  126.         if(root->right != NULL)
  127.             tree_print(_out, root->right);
  128.     }
  129. }
  130.  
  131. //удаление всех
  132. void tree_clear(node* root){
  133.     if(root != NULL){
  134.         if(root->left != NULL)
  135.             tree_clear(root->left);
  136.         if(root->right != NULL)
  137.             tree_clear(root->right);
  138.         free(root);
  139.     }
  140. }

Объяснение кода листинга программы

  1. Загрузка дерева из файла.
  2. Вставка нового элемента в дерево.
  3. Удаление элемента из дерева.
  4. Поиск элемента в дереве.
  5. Печать содержимого дерева в файл.
  6. Очистка дерева и освобождение памяти.

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.714 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы