Разработать проект для обработки дерева поиска - C (СИ)
Формулировка задачи:
Разработать проект для обработки дерева поиска, каждый элемент которого содержит целочисленный ключ и строку текста, содержащую, например, ФИО и номер паспорта (ввод исходной информации рекомендуется записать в файл). В программе должны быть реализованы следующие возможности:
-создание дерева
-добавление новой записи
-поиск информации по заданному ключу
-удаление информации с заданным ключом
-вывод информации
-удаление из левой ветви дерева узел с максимальным значением ключа и все связанные с ним узлы
Язык Си
Решение задачи: «Разработать проект для обработки дерева поиска»
textual
Листинг программы
#include <stdio.h> #include <malloc.h> #include <string.h> #define MAX_LEN 48 typedef struct _node { unsigned key; char inf[MAX_LEN]; struct _node* left; struct _node* right; } node; int tree_insert(node** root, unsigned key, const char* inf); void tree_remove(node** root, unsigned key); char* tree_search(node* root, unsigned key); void tree_print(FILE* _out, const node* root); void tree_clear(node* root); node* tree_open(const char* fn); int main(void){ node* tr = tree_open("file.txt"); if(tr != NULL){ tree_print(stdout, tr); tree_clear(tr); } getchar(); return 0; } //загрузка из файла ключ Ф.И.О node* tree_open(const char* fn){ char s[MAX_LEN], b[16]; unsigned k; node* tr = NULL; FILE* fp = fopen(fn, "rt"); if(fp == NULL) return NULL; sprintf(b, "%%u %%%d[^\n]", MAX_LEN - 1); while(fscanf(fp, b, &k, s) == 2) tree_insert(&tr, k, s); fclose(fp); return tr; } //вставка int tree_insert(node** root, unsigned key, const char* inf){ node* p = *root; while(p != NULL){ if(key < p->key){ root = &p->left; p = p->left; } else if(key > p->key){ root = &p->right; p = p->right; } else return 0; } p = (node*)malloc(sizeof(node)); if(p != NULL){ p->key = key; strcpy(p->inf, inf); p->left = p->right = NULL; *root = p; } return (p != NULL); } //удаление void tree_remove(node** root, unsigned key){ node* p1, *p2, *p = *root; while((p != NULL) && (p->key != key)){ if(key < p->key){ 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); } //поиск char* tree_search(node* root, unsigned key){ while((root != NULL) && (root->key != key)){ if(key < root->key) root = root->left; else root = root->right; } return (root != NULL) ? &root->inf[0] : NULL; } //печать void tree_print(FILE* _out, const node* root){ if(root != NULL){ if(root->left != NULL) tree_print(_out, root->left); fprintf(_out, "KEY: %u\tINFO: %s\n", root->key, root->inf); if(root->right != NULL) tree_print(_out, root->right); } } //удаление всех void tree_clear(node* root){ if(root != NULL){ if(root->left != NULL) tree_clear(root->left); if(root->right != NULL) tree_clear(root->right); free(root); } }
Объяснение кода листинга программы
- Загрузка дерева из файла.
- Вставка нового элемента в дерево.
- Удаление элемента из дерева.
- Поиск элемента в дереве.
- Печать содержимого дерева в файл.
- Очистка дерева и освобождение памяти.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д