Разработать проект для обработки дерева поиска - 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);
    }
}

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

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

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

7   голосов , оценка 3.714 из 5
Похожие ответы