btree.c

该文件夹中包含了大部分经典的算法的源程序代码

/* file name: btree.c */
/* 利用B-TREE来处理数据--加载、储存、新增、删除、修改、查询、输出 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#define MAX 2    /* 每一节点内至多可放数据笔数 */
#define MIN 1    /* 每一节点内至少需放数据笔数 */
typedef struct student {    /* 数据结构 */
 int count;                /* 节点数据数 */
 int id[MAX+1];            /* ID号码--键值 */
 char name[MAX+1][11];     /* 姓名 */
 int score[MAX+1];         /* 分数 */
 struct student *link[MAX+1];    /* 子链接 */
} Node_type;
Node_type *root;
void init_f(FILE *);  /* 初始化函数 */
void insert_f(void);  /* 新增函数 */
Node_type *access(int, char *, int, Node_type *);  /* 将新增数据加入B-tree中 */
int topdown(int, char *, int, Node_type *, int *, char *, int *,
   Node_type **);  /* 从根节点往下逐一寻找插入点，将数据新增的函数 */
/* 将数据置于某特定节点中 */
void putdata(int, char *, int, Node_type *, Node_type *, int);
void broken(int, char *, int, Node_type *, Node_type *, int, int *, char *,
   int *, Node_type **);  /* 将一节点划分为二 */
void update_f(void);  /* 修改函数 */
void delete_f(void);  /* 删除函数 */
Node_type *removing(int, Node_type *);  /* 将数据从B-tree中删除 */
int deldata(int, Node_type *);  /* 删除数据函数 */
void move(Node_type *, int);  /* 将节点中的数据逐一往左移 */
void replace(Node_type *, int);  /* 寻找替代节点 */
void restore(Node_type *, int);  /* 数据删除后的调整工作 */
void getleft(Node_type *, int);  /* 向左兄弟节点借一笔数据 */
void getright(Node_type *, int);  /* 向右兄弟节点借一笔数据 */
void combine(Node_type *, int);  /* 节点合并 */
void list_f(void);  /* 输出函数 */
void show(Node_type *);  /* 以递归方式依序将数据输出 */
void query_f(void);  /* 查询函数 */
void save(Node_type *, FILE *);  /* 储存函数 */
void quit(void);  /* 结束函数 */
Node_type * search(int, Node_type *, int *);  /* 依键值查找某特定节点函数 */
int searchnode(int, Node_type *, int *);  /* 依键值查找节点中某特定数据函数 */


void main(void)
{
     int flag=0, times=1;  /* times是判断是否为第一次进入需要加载输入文件 */
    FILE *infile, *outfile;
    char choice, filename[11], ans;
    system("cls");
    while(1)
    {
        if(times == 1)
    	{
        	do
    		{
                    /* 要求输入加载文件名称 */
                printf("\n  Please enter input file name: ");
                scanf("%s", filename);
                if((infile = fopen(filename, "r")) == NULL)
        		{
                    puts("  File name not found!!");
                	flag = 0;
        		}
        		else
                	flag = 1;
            }  while(flag == 0);  /* flag为0时，表示输入错误，会要求重新输入 */
            times++;
    	}
        fseek(infile, 0, 0);
        init_f(infile);
     do
     {
            printf("\n");
            puts("  *********************");
            puts("        1.insert");
            puts("        2.update");
            puts("        3.delete");
            puts("        4.list");
            puts("        5.query");
            puts("        6.save");
            puts("        7.quit");
            puts("  *********************");
            printf("  Please enter your choice(1..7): ");
            choice = getche();
            printf("\n");
            switch(choice)
            {
                case '1':
     	           insert_f();
            		break;
                case '2':
                	update_f();
            		break;
                case '3':
                	delete_f();
            		break;
                case '4':
                	list_f();
            		break;
                case '5':
                	query_f();
            		break;
                case '6':
                	flag = 0;
        			do
        			{
                        puts("\n  ---- SAVE ----");
                        printf("  Please enter saving file name: ");
                        scanf("%s", filename);
                        if((outfile = fopen(filename, "w")) == NULL)
        				{
                            puts(" File name can not be used!!");
                			flag = 0;
        				}
            			else
                           flag=1;
                    }  while(flag == 0);
                    save(root, outfile);
                    printf("  Save OK!\n");
                    fclose(outfile);
            		break;
                case '7': printf("  Are you sure? (Y/N): ");
                    ans = getche();
                    ans = toupper(ans);
                    if(ans == 'Y')
        			{
                        fclose(infile);
                		quit();
        			}
            		break;
                default: puts("  Choice error!!");
    		}
        }  while(choice != '7');
    }
}


/* 读入输入文件数据至B-tree中，infile为输入文件名称 */
void init_f(FILE *infile)
{
    int init_id, init_score;
    char init_name[11];
    root = NULL;
    while(fscanf(infile, "%d %10s %d\n", &init_id, init_name, &init_score)
            		!= EOF)
    {
        root = access(init_id, init_name, init_score, root);
    }
}

/* 新增一笔数据，并调整为B-tree */
void insert_f(void)
{
     int position, insert_id, insert_score; /* position记录数据在节点中新增的位置 */
    Node_type *node;
    char ans, insert_name[11];
    puts("\n  ---- INSERT ----");
    puts("  Please enter detail data");
    printf("  ID number: ");
    scanf("%d", &insert_id);
     /* 找寻新增数据是否已存在，若存在，则显示错误 */
    node = search(insert_id, root, &position);
    if(node != NULL)
        puts(" ID number has existed!!");
    else
    {
        printf("  Name: ");  /* 要求输入其它详细数据 */
        scanf("%s'", insert_name);
        printf("  Score: ");
        scanf("%d", &insert_score);
        printf("  Are you sure? (Y/N): ");
        ans = getche();
        printf("\n");
        ans = toupper(ans);
        if(ans == 'Y')
            root = access(insert_id, insert_name, insert_score, root);
    }
}

/* 将新增数据加入B-TREE，node指加入节点，传回值为root所在 */
Node_type *access(int app_id, char *app_name, int app_score, Node_type *node)
{
    int x_id, x_score, pushup;   /* pushup判断节点是否需划分而往上新增一节点 */
    char x_name[11];
    Node_type *xr, *p;
    pushup = topdown(app_id, app_name, app_score, node, &x_id, x_name,
                        &x_score, &xr);
    if(pushup)   /* 若pushup为1，则配置一个新节点，将数据放入 */
    {
        p = (Node_type *) malloc(sizeof(Node_type));
        p->link[0] = NULL;
        p->link[1] = NULL;
        p->link[2] = NULL;
        p->count = 1;
        p->id[1] = x_id;
        strcpy(p->name[1], x_name);
        p->score[1] = x_score;
        p->link[0] = root;
        p->link[1] = xr;
        return p;
    }
    return node;
}


/* 从树根往下寻找数据加入节点，将数据新增于B-tree中，参数p为目前所在节点，
   xr记录数据所对应的子链接 */
int topdown(int new_id, char *new_name, int new_score, Node_type *p,
            int *x_id, char *x_name, int *x_score, Node_type **xr)
{
    int k;
     if(p == NULL)  /* p为NULL表示新增第一笔数据 */
    {
        *x_id = new_id;
        strcpy(x_name, new_name);
        *x_score = new_score;
        *xr = NULL;
        return 1;
    }
    else
    {
          if(searchnode(new_id, p, &k))  /* 找寻新增数据键值是否重复，若重复则显示错误 */
    	{
            puts("  Data error, ID number has existed!!");
            quit();
            return 0;
    	}
         /* 继续往下找寻新增节点 */
        if(topdown(new_id, new_name, new_score, p->link[k], x_id, x_name,
                    x_score, xr))
    	{
            if(p->count < MAX)  /* 若新增节点有足够的空间存放数据，则将数据直接加入该节点 */ 
    		{
            putdata(*x_id, x_name, *x_score, *xr, p, k);
            return 0;
    		}
        	else
    		{
                 /* 若无足够空间，则须划分节点 */
                broken(*x_id, x_name, *x_score, *xr, p, k, x_id, x_name, x_score, xr);
                return 1;
    		}
    	}
        else
            return 0;
    }
}

/* 将新增数据直接加入于节点中，xr为新增数据对应的子链接所在，p为数据加入的节点 */
void putdata(int x_id, char *x_name, int x_score, Node_type *xr,
                Node_type *p, int k)
{
    int i;
    /* 将节点中的数据逐一右移，以空出新增数据加入的位置 */
    for(i = p->count; i > k; i--)
    {
        p->id[i+1] = p->id[i];
        strcpy(p->name[i+1], p->name[i]);
        p->score[i+1] = p->score[i];
        p->link[i+1] = p->link[i];
    }
    p->id[k+1] = x_id;
    strcpy(p->name[k+1], x_name);
    p->score[k+1] = x_score;
    p->link[k+1] = xr;
    p->count++;
}

/* 将节点一分为二，yr为划分后新增加的节点 */
void broken(int x_id, char *x_name, int x_score, Node_type *xr, Node_type *p,
            int k, int *y_id, char *y_name, int *y_score, Node_type **yr)
{
    int i;
    int median;    /* median记录从何处划分节点 */
    if(k <= MIN)
        median = MIN;
    else
        median = MIN + 1;
    *yr = (Node_type *) malloc(sizeof(Node_type));
     /* 将数据从划分处开始搬移至新节点中 */
    for(i = median + 1; i <= MAX; i++)
    {
        (*yr)->id[i-median] = p->id[i];
        strcpy((*yr)->name[i-median], p->name[i]);
        (*yr)->score[i-median] = p->score[i];
        (*yr)->link[i-median] = p->link[i];
    }
    (*yr)->count = MAX - median;
    p->count = median;
    if(k <= MIN)
        putdata(x_id, x_name, x_score, xr, p, k);
    else
        putdata(x_id, x_name, x_score, xr, *yr, k - median);
    *y_id = p->id[p->count];
    strcpy(y_name, p->name[p->count]);
    *y_score = p->score[p->count];
    (*yr)->link[0] = p->link[p->count];
    p->count--;
}

/* 修改数据函数 */
void update_f(void)
{
    int update_id, update_score, position;
    char ans, update_name[11];
    Node_type *node;
    puts("\n  ---- UPDATE ----");
    printf("  Please enter ID number: ");
    scanf("%d", &update_id);
    node = search(update_id, root, &position);   /* 找寻欲修改数据所在节点位置 */
    if(node != NULL)
    {
        printf("  Original name: %s\n", node->name[position]);
        printf("  Please enter new name: ");
        scanf("%10s", update_name);
        printf("  Original score: %d\n", node->score[position]);
        printf("  Please enter new score: ");
        scanf("%d", &update_score);
        printf("  Are you sure? (Y/N): ");
        ans = getche();
        printf("\n");
        ans = toupper(ans);
        if(ans == 'Y')
    	{
            node->score[position] = update_score;
            strcpy(node->name[position], update_name);
    	}
    }
    else
        puts("  ID number not found!!");
}