bst.c

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

/* file name: bin_search_tree.c */
/* 利用二叉查找树处理数据－加载、储存、新增、删除、修改、输出 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

/* 定义student结构 */
struct student {
	char name[20];  /* 学生姓名 */
	int score;  /* 学生成绩 */
	struct student *llink;  /* 左子链接 */
	struct student *rlink;   /* 右子链接 */
};

void load_f(void);      /* 加载函数 */
void save_f(void);      /* 储存函数 */
void insert_f(void);    /* 新增函数 */
void delete_f(void);    /* 删除函数 */
void modify_f(void);    /* 修改函数 */
void show_f(void);      /* 输出函数 */
void access(char [], int);  /* 将数据插入二叉查找树 */
void removing(char []);  /* 将数据从二叉查找树中移除 */
struct student *replace(struct student *);  /* 寻找替代节点 */

void connect(struct student *, char);  /* 调整链接 */
void inorder(struct student *);  /* 数据以中序法输出 */
void preorder(struct student *, FILE *);  /* 数据以前序法写入表 */
struct student *search(char []);  /* 查找节点 */
struct student *search_re_r(struct student *);  /* 查找右子树替代节点 */
struct student *search_re_l(struct student *);  /* 查找左子树替代节点 */
struct student *search_p(struct student *);  /* 查找父节点 */

struct student *root, *ptr;

void main(void)
{
	char option;
	load_f();  /* 载入文件 */
	while(1)
	{
		puts("");
		puts("********************");
		puts("     <1> insert");
		puts("     <2> delete");
		puts("     <3> modify");
		puts("     <4> show");
		puts("     <5> quit");
		puts("********************");
		printf("Enter your choice: ");
		option = getche();
		printf("\n\n");
		switch(option)
		{
			case '1':
				insert_f();
				break;
			case '2':
				delete_f();
				break;
			case '3':
				modify_f();
				break;
			case '4':
				show_f();
				break;
			case '5':
				save_f();  /* 储存文件 */
				exit(0);
			default :
				puts("Wrong option!");
		}
	}
}

/* 加载函数，将数据文件dfile.dat加载到程序中 */
void load_f(void)
{
	FILE *fptr;
	char name[20];
	int score;
	printf("File loading...");
	if((fptr = fopen("bst.dat", "r")) == NULL)   /* 打开文件 */
	{
		puts("failed!");
		puts("Dfile.dat not found!");
		return;
	}
	while(fscanf(fptr, "%s %d", name, &score) != EOF)   /* 读取文件数据 */
		if(strcmp(name, "") != 0)
			access(name, score);
	puts("OK!");
	fclose(fptr);   /* 关闭文件 */
}

/* 储存文件，将二叉查找树中的数据储存至数据文件dfile.dat中 */
void save_f(void)
{
	FILE *fptr;
	printf("File saving...");
	if((fptr = fopen("bst.dat", "w")) == NULL)  /* 开启文件 */
	{
		puts("failed!");
		return;
	}
	preorder(root, fptr);   /* 以前序法写入 */
	puts("OK!");
	fclose(fptr);  /* 关闭文件 */
}

/* 新增函数，新增一笔新的数据 */
void insert_f(void)
{
	char name[20], temp[4];
	int score;
	puts("=====INSERT DATA=====");
	printf("Enter student name: ");
	gets(name);
	printf("Enter student score: ");
	gets(temp);
	score = atoi(temp);
	access(name, score);
}

/* 删除函数，将数据从二叉查找树中删除 */
void delete_f(void)
{
	char name[20];
	if(root == NULL)
	{
		puts("No student record!");
		return;
	}
	puts("=====DELETE DATA=====");
	printf("Enter student name: ");
	gets(name);
	removing(name);
}

/* 修改数据，修改学生成绩 */
void modify_f(void)
{
	struct student *node;
	char name[20], temp[4];
	if(root == NULL)   /* 判断根节点是否为NULL */
	{
		puts("No student record!");
		return;
	}
	puts("=====MODIFY DATA===== ");
	printf("Enter student name: ");
	gets(name);
	if((node = search(name)) == NULL)
		printf("Student %s not found!\n", name);
	else
	{
		/* 列出原数据状况 */
		printf("Original student name: %s\n", node->name);
		printf("Original student score: %d\n", node->score);
		printf("Enter new score: ");
		gets(temp);
		node->score = atoi(temp);
		printf("Data of student %s modified\n", name);
	}
}

/* 输出函数，将数据输出至屏幕 */
void show_f(void)
{
	if(root == NULL)  /* 判断根节点是否为NULL */
	{
		puts("No student record!");
		return;
	}
	puts("=====SHOW DATA=====");
	inorder(root);  /* 以中序法输出数据 */
}
/* 处理二叉查找树，将新增数据插入至二叉查找树中 */
void access(char name[], int score)
{
	struct student *node, *prev;
	if(search(name) != NULL)  /* 数据已存在则显示错误 */
	{
		printf("Student %s has existed!\n", name);
		return;
	}
	ptr = (struct student *) malloc(sizeof(struct student));
	strcpy(ptr->name, name);
	ptr->score = score;
	ptr->llink = ptr->rlink = NULL;
	if(root == NULL)  /* 当根节点为NULL的状况 */
		root = ptr;
	else   /* 当根节点不为NULL的状况 */
	{
		node = root;
		while(node != NULL)  /* 查找数据插入点 */
		{
			prev = node;
			if(strcmp(ptr->name, node->name) < 0)
				node = node->llink;
			else
				node = node->rlink;
		}
		if(strcmp(ptr->name, prev->name) < 0)
			prev->llink = ptr;
		else
			prev->rlink = ptr;
	}
}

/* 将数据从二叉查找树中移除 */
void removing(char name[])
{
	struct student *del_node;
	if((del_node = search(name)) == NULL)  /* 找不到数据则显示错误 */
	{
		printf("Student %s not found!\n", name);
		return;
	}
	/* 节点不为树叶节点的状况 */
	if(del_node->llink != NULL || del_node->rlink != NULL)
		del_node = replace(del_node);
	else  /* 节点为树叶节点的状况 */
		if(del_node == root)
			root = NULL;
		else
			connect(del_node, 'n');
	free(del_node);  /* 释放内存 */
	printf("Data of student %s deleted!\n", name);
}

/* 寻找删除非树叶节点的替代节点 */
struct student *replace(struct student *node)
{
	struct student *re_node;
	/* 当右子树找不到替代节点，会查找左子树是否存在替代节点 */
	if((re_node = search_re_r(node->rlink)) == NULL)
		re_node = search_re_l(node->llink);
	if(re_node->rlink != NULL)  /* 当替代节点有右子树存在的状况 */
		connect(re_node, 'r');
	else
		if(re_node->llink != NULL)  /* 当替代节点有左子树存在的状况 */
			connect(re_node, 'l');
		else  /* 当替代节点为树叶节点的状况 */
			connect(re_node, 'n');
	strcpy(node->name, re_node->name);
	node->score = re_node->score;
	return re_node;
}

/* 调整二叉查找树的链接，link为r表示处理右链接，为l表处理左链接，
   为m则将链接指向NULL */
void connect(struct student *node, char link)
{
	struct student *parent;
	parent = search_p(node);   /* 查找父节点 */
	/* 节点为父节点左子树的状况 */
	if(strcmp(node->name, parent->name) < 0)
		if(link == 'r')   /* link为r */
			parent->llink = node->rlink;
		else  /* link