avltree.c

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

/* file name: avltree.c */
/* 利用AVL-TREE 处理学生数据--取文件、存盘、插入、删除、修改、输出 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
void load_f(void);    /* 取文件函数 */
void save_f(void);    /* 存盘函数 */
void insert_f(void);  /* 插入函数 */
void delete_f(void);  /* 删除函数 */
void modify_f(void);  /* 修改函数 */
void list_f(void);    /* 输出函数 */
void sort_f(char[], char[]);      /* 插入文件后排序 */
void inorder(struct student *);   /* 输出使用中序追踪 */
void preorder(FILE *, struct student *);  /* 存盘使用前序追踪 */
void bf_count(struct student *);  /* 计算节点BF值 */
int height_count(struct student *);   /* 计算节点高度 */
void pivot_find(void);   /* 找出pivot所在节点 */
int type_find(void);     /* 找出改善方法 */
void type_ll(void);      /* 使用LL型态 */
void type_rr(void);      /* 使用RR型态 */
void type_lr(void);      /* 使用LR型态 */
void type_rl(void);      /* 使用RL型态 */
void anykey_f(void);
struct student {
char name[20];  /* 姓名 */
int score;  /* 分数 */
int bf;  /* 节点BF值 */
struct student *llink, *rlink;  /* 节点子链接 */
};
struct student *ptr, *root, *this_n, *prev, *pivot, *pivot_prev;
int nodecount = 0; /* 用来计算node个数 */


void main()
{
	char option;
	load_f();
	while(1)
	{
		system("cls");
		printf(" *****************************\n");
		printf("         <1> insert\n");
		printf("         <2> delete\n");
		printf("         <3> modify\n");
		printf("         <4> list\n");
		printf("         <5> exit\n");
		printf(" *****************************\n");
		printf("  Please input your choice: ");
		option = getche();
		switch(option)
		{
			case '1':
				insert_f();
				break;
			case '2':
				delete_f();
				break;
			case '3':
				modify_f();
				break;
			case '4':
				list_f();
				break;
			case '5':
				save_f();
				exit(0);
		}
	}
}

void load_f()
{
	FILE *fptro;
	char name_t[20], score_t[4];
	/* 打开文件时，若找不到文件，则要求输入第一笔数据 */
	if((fptro = fopen("avltree.dat","r")) == NULL)
	{
		printf(" File student.dat not found\n");
		printf(" The data can not be loaded\n");
		printf(" Press any key to insert the first data...");
		getch();
		insert_f();
	}
	else
	{
		while(fscanf(fptro, "%s %s", name_t, score_t) != EOF){
			sort_f(name_t, score_t);
			nodecount++;
		}
		fclose(fptro);
	}
}

void save_f()
{
	FILE *fptri;
	fptri = fopen("avltree.dat","w");
	preorder(fptri, root);   /* 数据写入文件是使用前序法写入 */
	fclose(fptri);
}

void insert_f(void)
{
	char name_t[20], score_t[4];
	system("cls");
	printf(" Please enter student name: ");
	gets(name_t);
	printf(" Please enter student score: ");
	gets(score_t);
	nodecount++;/* 盢node