数据结构——顺序查找、二分查找，冒泡排序，堆排序

#include 
#include  
#include 
#include  
#include 
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status; 
typedef int KeyType;	//关键字类型为int 
typedef  struct{
	KeyType key;		//关键字
	//其他域按需定义	
}ElemType;				//元素（记录）类型 

typedef struct{
    ElemType *r;		//存储空间基地址 
    int length;			//表的长度（元素个数） 
}SqList;


Status InitList(SqList  &L){//键盘输入数据表 
  	int n,i;
	cout<<"n数据个数:";
    cin>>n; 
    L.r=new ElemType[n+1]; 
    if (!L.r) return OVERFLOW;
	cout<<"n输入数据:";
    for (i=1;i<=n;i++){
	 	cin>>L.r[i].key;//输入n个元素的关键字，其他项略 
	}     
    L.length=n;
 	return OK;
}

Status InitList_random(SqList  &L)//生成随机数表 
{
	int i,n;
	cout<<"n数据个数:";
	cin>>n;
	L.r=new ElemType[n+1];
	if(!L.r)
	return OVERFLOW;
	srand(time(NULL));
	for(i=1;i<=n;i++)
	{
		L.r[i].key= rand()%1000;
	}
	L.length=n;
	return OK; 
}

Status DestroyList(SqList &L){
	delete []L.r;
	L.r=NULL;
	L.length=0;
	return OK;
}
void OutputList(SqList L){//输出数据表 
    cout<<"n数据表：";
	for (int i=1;i<=L.length;i++){
    	cout<=1&&L.r[i].key!=key;i--);//从后往前查找 
	if(i>=1)    //查找成功，返回位置，否则返回0 
	return i;
	else
	return 0;
}

int Search_Bin(SqList L,KeyType key) {//折半查找 
//在有序表中查找关键字为key的记录，查找成功，返回位置，否则返回0 	
	int low=1,high=L.length,mid;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key==L.r[mid].key)
		{
			return mid;
		}
		
		else if(key0)&&(flag==1))
	{  
		flag=0;   //先置为0 
		for(int i=1;i<=m;i++)
		{
			if(L.r[i].key>L.r[i+1].key)
			{
				flag=1;     //一旦发生交换就置为1 
				t=L.r[i];
				L.r[i]=L.r[i+1];
				L.r[i+1]=t;
			}
		}
	}
} 

void HeapAdjust(SqList &L,int s,int m)//调整堆 
{
	ElemType rc;
	rc=L.r[s];
	for(int j=2*s;j<=m;j*=2) 
	{
		if(j=L.r[j].key) break;
		L.r[s]=L.r[j];
		s=j;
	}
	L.r[s]=rc;
 } 
 
void HeapSort(SqList &L)
{
	int i,j;
	ElemType t;
	for(i=L.length/2;i>0;--i)//将无序序列建成大根堆 
	{
		HeapAdjust(L,i,L.length);
	}
	//cout<1;--j)
	{
		//将堆顶与最后一个交换 
		t=L.r[1];
		L.r[1]=L.r[j];
		L.r[j]=t;
		HeapAdjust(L,1,j-1);//将L.r[1,j-1]重新调整为大根堆 
	}
}

//#include "comdef.h"
//#include "sqlistdef.h"
//#include "sqlistapp.h"
int main(){
	SqList L;
	int choice;
	KeyType key;
	InitList(L);
	do{
		cout<<"nn  	 数据查找与排序		";
    	cout<<"n==========================";
		cout<<"n  	 1:输出数据表";
		cout<<"n  	 2:顺序查找法";
    	cout<<"n  	 3:折半查找法";
    	cout<<"n  	 4:插入排序法";	
		cout<<"n  	 5:冒泡排序法";
		cout<<"n  	 6:堆排序法";
		cout<<"n  	 0:退出";
		cout<<"n==========================";
		cout<<"n输入选择：";
		cin>>choice;
		switch (choice){
			
			case 1:	OutputList(L);									
					break; 
					
			case 2: int a;
			        cout<<"利用顺序查找法查找数据值key=";
					cin>>key;
					a=Search_Seq(L,key);
					if(a!=0)
					cout<<"元素"<key;
					b=Search_Bin(L,key);
					if(b!=0)
					cout<<"元素"< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5691026.html