《数据结构—用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)-