seart_sort.cpp

这是一系列关于二叉树的创建,查找,霍夫曼等数据结构编程,

#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
typedef struct
{
	int key;
}TNode,*Table;

int pivotkey;
int pivotloc;
int Partition(Table Array,int low,int high)
{//交换表中[low,high]的记录,枢轴记录到位,并返回其所在位置,
//此时在他之前(后)的记录均不大(小)于他
	Array[0] = Array[low];//表中的第一个记录作枢轴记录
	pivotkey = Array[low].key;//枢轴记录关键字
	while(low < high)
	{//从表的两端交替地向中间扫描
		while(low < high && Array[high].key >= pivotkey) --high;
		Array[low] = Array[high];//将比枢轴记录小的记录移到低端
		while(low < high && Array[low].key <= pivotkey) ++low;
		Array[high] = Array[low];//将比枢轴记录大的记录移到高端
	}
	Array[low] = Array[0];//枢轴记录到位
	return low;//返回枢轴位置
}
void QuickSort(Table Array,int low,int high)
{//对表做快速排序
	if(low < high)
	{//长度大于1
		pivotloc = Partition(Array,low,high);//将low,high一分为二
		QuickSort(Array,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置
		QuickSort(Array,pivotloc+1,high);//对高子表递归排序
	}
}

int Search(Table Array,int Key,int low,int high,int Length)
{//在有序表中二分查找其关键字等于Key的数据元素.若找到,则函数值为
//该元素在表中的位置,否则为0
	int mid;
	low = 1;//置区间初值
	high = Length;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(Key == Array[mid].key) //找到待查元素
			return mid;
		else if(Key < Array[mid].key) high = mid - 1;//继续在前半区间进行查找
		else low = mid + 1;//继续在后半区间进行查找
	}
	return 0;//表中不存在待查元素
}
void main()
{
	Table Array;
	int yes;
	int Length,i,low,high,Key;
	printf("\n☆☆☆☆☆☆☆☆☆☆☆☆☆☆二分查找与快速排序实验☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n\n");
	printf("请输入表的长度：Length = ");
	scanf("%d",&Length);
	printf("\n");
	Array = (Table)malloc((Length + 1) * sizeof(TNode));
	printf("请输入关键字：\n");
	for(i = 1;i <= Length;i++)
	{
		scanf("%d",&Array[i].key);
	}
	QuickSort(Array,1,Length);//排序
	printf("快速排序的结果为:\n");
	for(i = 1;i <= Length;i++)
	{
		printf("%d  ",Array[i].key);
	}
	printf("\n                查找关键字请按------------------1\n");
	printf("\n                退出查找请按--------------------0\n\n");
	printf("要查找元素吗?(是按1)否(按0)\n");
	scanf("%d",&yes);
	while(yes == 1)
	{
		printf("请输入待查的关键字：");
		scanf("%d",&Key);
		i = Search(Array,Key,low,high,Length);//查找
		if(i)
			printf("\n待查元素的位置是：%d\n",i);
		else
			printf("\n该表中无次元素!!\n");
		printf("\n要继续查找吗?(是按1)否(按0)\n");
		scanf("%d",&yes);
	}
	printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
}