sort.cpp

这是数据结构课程的试验

#include <iostream.h>
#include <stdlib.h>

//待查对象存储为结构体数组，先对其关键字进行快速排序，然后折半查找

struct SS {
	int key;	//关键字
	char message;	//信息
};

//划分区间，比较大小后移动位置
int Partition (SS *p, int low, int high ) {
	SS *pl,*ph;
	pl = p + low;
	ph = p + high;
    *p = *pl;//子表的第一个记录作基准对象
    int pivotkey = pl->key; //基准对象关键字
	while(low<high){
		while(low<high && ph->key >= pivotkey) {--high;break;}
		pl = p +low;
		ph = p +high;
		*pl = *ph; //小于基准对象的移到区间的左侧
		while(low<high&& pl->key <= pivotkey) {++low;break;}
		pl = p +low;
		ph = p +high;
		*ph = *pl ; //大于基准对象的移到区间的右侧
	}    
	*pl = *p;
	return low;
}

//快速排序
void QuickSort (SS *sp,int low, int high){
//在序列low-high 中递归地进行快速排序
	if ( low < high) {					
		int pivotloc = Partition (sp, low, high);   //划分
		QuickSort ( sp, low, pivotloc-1); //对左序列同样处理	    
		QuickSort ( sp, pivotloc+1, high); //对右序列同样处理
	}
}

//折半查找
char Search_Bin (SS *sp, int kval,int low,int high) {
	SS *sp1;
	while (low <= high) {
		int mid = (low + high) / 2;
		sp1 = sp + mid;
		if (kval == sp1->key)
			return  sp1->message;        // 找到待查元素
		else
			if (kval < sp1->key)
				high = mid - 1;       // 继续在前半区间进行查找
			else  low = mid + 1; // 继续在后半区间进行查找
	}
	cout<<"没有你要查找的关键字！"<<endl;
	exit(1);
} 



void main(){
	cout<<"请输入序列的个数："<<endl;
	int N;
	cin>>N;
	SS *sep,*sep1;
	sep = new SS[N + 1];
	cout<<"请输入信息和关键字："<<endl;
	for (int i = 1 ; i < N + 1; i++) {
		sep1 = sep + i;
		cin>>
			sep1->message>>
			sep1->key;
	}
	QuickSort (sep,1, N);
	int v;
	cout<<"请输入你要查找信息的关键字："<<endl;
	cin>>v;
	cout<<"你要查找的信息为: "<<endl;
	cout<<Search_Bin(sep,v,1,N)<<endl;
}