heap.c

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

/* file name: heap.c */
/* 利用堆树(HEAP TREE)处理会员进出数据--加载、储存、插入、删除、输出 */
#include <stdio.h>
#include <conio.h>
#define MAX 100  /* 设定上限 */
void load_f(void);    /* 加载函数 */
void save_f(void);    /* 储存函数 */
void insert_f(void);  /* 插入函数 */
void delete_f(void);  /* 删除函数 */
void display_f(void); /* 输出函数 */
void create(int);     /* 建立数据于堆树 */
void removes(int);    /* 从堆树中删除数据 */
void show(char);      /* 印出数据于屏幕 */
void adjust_u(int [], int);      /* 从下而上调整数据 */
void adjust_d(int [], int, int); /* 从上而下调整数据 */
void exchange(int *, int *);     /* 交换数据 */
int search(int);                 /* 查找数据 */
int heap_tree[MAX];   /* 堆树数组 */
int last_index = 0;   /* 最后一笔数据的INDEX */

void main(void)
{
	char option;
	load_f();
	do
	{
		printf("\n ***************************\n");
		printf("         <1> login\n");
		printf("         <2> logout\n");
		printf("         <3> show\n");
		printf("         <4> quit\n");
		printf(" ***************************\n");
		printf(" Please enter your choice: ");
		option = getche();
		printf("\n");
		switch(option)
		{
			case '1':
				insert_f();
				break;
			case '2':
				delete_f();
				break;
			case '3':
				display_f();
				break;
			case '4':
				save_f();
				break;
			default :
				printf("\n Option error!!\n");
		}
	} while(option != '4');
}

void load_f(void)
{
	FILE *fptr;
	int id_temp;
	if((fptr = fopen("dfile.dat", "r")) == NULL) /* 开文件失败显示错误讯息 */
	{
		printf(" File dfile.dat not found!!\n");
		printf(" Loading failure!!\n");
	}
	else
	{
		printf(" Loading...");
		while(fscanf(fptr, "%d", &id_temp) != EOF)
			create(id_temp);  /* 建立堆 */
		printf("OK\n");
		fclose(fptr);
	}
}

void save_f(void)
{
	FILE *fptr;
	int c_index;
	fptr = fopen("dfile.dat", "w");
	printf("\n Data save...");
	for(c_index = 1; c_index <= last_index; c_index++)
		fprintf(fptr, "%d\n", heap_tree[c_index]);
	printf("OK");
	fclose(fptr);
}

void insert_f(void)
{
	int id_temp;
	if(last_index >= MAX) /* 资料数超过上限，显示错误讯息 */
	{
		printf("\n Login members are more than %d!!\n", MAX);
		printf(" Please wait for a minute!!\n");
	}
	else
	{
		printf("\n Please enter login ID number: ");
		scanf("%d", &id_temp);
		create(id_temp);  /* 建立堆 */
		printf(" Login successfully!!\n");
	}
}

void delete_f(void)
{
	int id_temp, del_index;
	if(last_index < 1)   /* 无数据存在，显示错误讯息 */
	{
		printf("\n No member to logout!!\n");
		printf(" Please check again!!\n");
	}
	else
	{
		printf("\n Please enter logout ID number: ");
		scanf("%d", &id_temp);
		del_index = search(id_temp);  /* 寻找欲删除数据 */
		if(del_index == 0)   /* 没找到数据，显示错误讯息 */
			printf(" ID number not found!!\n");
		else
		{
			removes(del_index);   /* 删除数据，并调整堆树 */
			printf(" ID number %d logout!!\n", id_temp);
		}
	}
}

void display_f(void)
{
	char option;
	if(last_index < 1)   /* 无数据存在，显示错误讯息 */
		printf("\n No member to show!!\n");
	else
	{
		printf("\n ***************************\n");
		printf("        <1> increase\n");  /* 选择第一项为由小到大排列 */
		printf("        <2> decrease\n");   /* 选择第二项为由大到小排列 */
		printf(" ***************************\n");
		do
		{
			printf(" Please enter your option: ");
			option = getche();
			printf("\n");
		} while(option != '1' && option != '2');
		show(option);
	}
}

void create(int id_temp)   /* ID_TEMP为新增资料 */
{
	heap_tree[++last_index] = id_temp;  /* 将数据新增于最后 */
	adjust_u(heap_tree, last_index);     /* 调整新增数据 */
}

void removes(int index_temp)  /* INDEX_TEMP为欲删除数据之INDEX */
{	/* 以最后一笔数据代替删除数据 */
	heap_tree[index_temp] = heap_tree[last_index];
	heap_tree[last_index--] = 0;
	if(last_index > 1)   /* 当数据笔数大于1笔，则做调整 */
	{	/* 当替代数据大于其PARENT NODE，则往上调整 */
		if(heap_tree[index_temp] > heap_tree[index_temp / 2] && index_temp > 1)
			adjust_u(heap_tree, index_temp);
		else /* 替代数据小于其CHILDEN NODE，则往下调整 */
			adjust_d(heap_tree, index_temp, last_index-1);
	}
}

void show(char op)
{
	int heap_temp[MAX+1];
	int c_index;
	/* 将堆树数据复制到另一个数组作排序工作 */
	for(c_index = 1; c_index <= last_index; c_index++)
		heap_temp[c_index] = heap_tree[c_index];
	/* 将数组调整为由小到大排列 */
	for(c_index = last_index-1; c_index > 0; c_index--)
	{
		exchange(&heap_temp[1], &heap_temp[c_index+1]);
		adjust_d(heap_temp, 1, c_index);
	}
	printf("\n       ID number\n");
	printf(" =====================\n");
	/* 选择第一种方式输出，以递增方式输出--使用堆栈
    选择第二种方式输出，以递减方式输出--使用队列 */
	{
		case '1':
			for(c_index = 1; c_index <= last_index; c_index++)
				printf("%14d\n", heap_temp[c_index]);
			break;
		case '2':
			for(c_index = last_index; c_index > 0; c_index--)
				printf("%14d\n", heap_temp[c_index]);
			break;
	}
	printf(" =====================\n");
	printf(" Total member: %d\n", last_index);
}

void adjust_u(int temp[], int index)  /* INDEX为目前数据在数组之INDEX */
{
	while(index > 1)  /* 将资料往上调整至根为止 */
	{
		if(temp[index] <= temp[index/2])  /* 数据调整完毕就跳出，否则交换数据 */
			break;
		else
			exchange(&temp[index], &temp[index/2]);
		index /= 2;
	}
}

/* INDEX1为目前数据在数组之INDEX，INDEX2为最后一笔数据在数组之INDEX */
void adjust_d(int temp[], int index1, int index2)
{/* ID_TEMP记录目前数据，INDEX_TEMP则是目前资料之CHILDEN NODE的INDEX */
	int id_temp, index_temp;
	id_temp = temp[index1];
	index_temp = index1 * 2;
/* 当比较数据之INDEX不大于最后一笔数据之INDEX，则继续比较 */
	while(index_temp <= index2)
	{
		if((index_temp < index2) && (temp[index_temp] < temp[index_temp+1]))
			index_temp++;   /* INDEX_TEMP记录目前数据之CHILDEN NODE中较大者 */
		if(id_temp >= temp[index_temp])   /* 比较完毕则跳出，否则交换数据 */
			break;
		else
		{
			temp[index_temp/2] = temp[index_temp];
			index_temp *= 2;
		}
	}
	temp[index_temp/2] = id_temp;
}

void exchange(int *id1, int *id2) /* 交换传来之ID1及ID2储存之数据 */
{
	int id_temp;
	id_temp = *id1;
	*id1 = *id2;
	*id2 = id_temp;
}

int search(int id_temp)  /* 寻找数组中ID_TEMP所在 */
{
	int c_index;
	for(c_index = 1; c_index <= MAX; c_index++)
		if(id_temp == heap_tree[c_index])
			return c_index;  /* 找到则回传数据在数组中之INDEX */
	return 0;   /* 没找到则回传0 */
}