数据结构实验报告代码

代码太多懒得抄就贴上来

程序源代码

	// paixu.cpp : 定义控制台应用程序的入口点。
//

//#include <stdafx.h>
#include <iostream.h>
#include <math.h>
#include "stdlib.h"
//using namespace std; //Visual Studio格式
#define OK  1

#define NULL 0
#define MAXSIZE  10
#define RANDRANGE 100
typedef int Status;
typedef int KeyType;

	typedef struct{
	KeyType key;
	int     otherinfo;
}RedType;
typedef struct{
	RedType r[MAXSIZE+1];   //数组中下标为0的分量不用来存储排序序列
	int length;	
}SqList;
void OutPut(SqList L){//输出顺序表
	int i;
	for(i=1;i<=L.length ;i++)
		cout<<L.r[i].key<<"\t" ;		
	cout<<"\n";
}
Status inittable(SqList &L,int n){
	//初始化顺序表函数,n为表中数据元素的个数，产生[0，RANDRANGE]的随机数存入表中
    int i,j,flag;
	KeyType e;
	L.length =n;
	for(i=1;i<=n;i++){
		flag=0;
		e=rand()%RANDRANGE;
		e=e%10+8;/////////////////////////////////////可删掉该语句
		for(j=1;j<i;j++){
			if(L.r [j].key ==e)
				flag=1;
		}
		if(!flag)
			L.r [j].key=e;
		else i--;
	}
	return OK;
}
void InsertSort(SqList &L){//直接插入排序
	int i,j;
	for(i=2;i<=L.length;i++){
		if(L.r[i].key<L.r[i-1].key){
			L.r[0].key=L.r[i].key;   
			L.r[i].key=L.r[i-1].key; 
			for(j=i-2;L.r[0].key<L.r[j].key;j--)
				L.r[j+1]=L.r[j];
			L.r[j+1].key=L.r[0].key; 
		}
		cout<<"第"<<i-1<<"趟排序结果\n";//输出每趟直接插入排序的结果
		OutPut(L);
		
	}
}
void BInsertSort(SqList &L){//折半插入排序
	int low,high,m,i,j;
	for(i=2;i<L.length;i++){
		L.r[0].key=L.r[i].key; 
		low=1; high=i-1;
		while(low<=high){
			m=(low+high)/2;
			if(L.r[0].key<L.r[m].key) high=m-1;
			else low=m+1;
		}
		for(j=i-1;j>=high+1;j--) L.r[j+1].key=L.r[j].key;       
		L.r[high+1].key=L.r[0].key;
		cout<<"第"<<i-1<<"趟排序结果\n";
		OutPut(L);
	}
}
void InsertSort2(SqList L,RedType d[],int &first,int &final){//2_路插入排序
	int i,j,k;
	for(i=1;i<=L.length;i++)  d[i].key=0; //为了后面输出时结果明了整齐，先给d[]数组初始化为0，该for语句也可以删掉。
	first=1;  final=1;
	d[1].key =L.r[1].key;
	for(i=2;i<=L.length;i++){
		if(L.r[i].key >=d[1].key ){
			for(j=final;L.r[i].key <d[j].key ;j--)
				d[j+1].key =d[j].key ;			
			d[j+1].key =L.r[i].key ;			
			final++;
		}
		else{
			if(first==1){
				first=L.length ;
				d[first].key =L.r[i].key ;				
			}
			else{
				for(j=first;L.r[i].key>d[j].key && j<=L.length  ;j++)
					d[j-1].key =d[j].key ;				
				d[j-1].key =L.r[i].key ;			    
			    first--;
			}
		}
		//以下语句是输出每趟排序后d[]数组中的情况和first及final值
		cout<<"first="<<first<<"\tfinal="<<final<<"\n";
		for(k=1;k<=L.length;k++)
			cout<<d[k].key<<"\t";
			
		cout<<"\n";
	}
}
void OutPut2(RedType d[],int first,int final,int length){//输出2_路插入排序结果
	int i;
	cout<<"2-路插入排序的结果：\n";
	for(i=first;i<=length;i++)
		cout<<d[i].key <<"\t";
		
	if(final<length)
		for(i=1;i<=final;i++)
			cout<<d[i].key <<"\t";	
			
	cout<<"\n";
    cout<<"2-路插入排序后数据在d[]数组中的存储：\n";
	cout<<"first="<<first<<"\tfinal="<<final<<"\n";
	for(i=1;i<=length;i++)
		cout<<d[i].key<<"\t";
		
	cout<<"\n";
}
//希尔排序
void ShellInsert(SqList &L,int dk){
	int i,j;
	for(i=dk+1;i<=L.length ;i++)
		if(L.r[i].key <L.r[i-dk].key ){
			L.r[0].key =L.r[i].key ;
			for(j=i-dk;j>0 && L.r[0].key <L.r[j].key ;j-=dk)
				L.r[j+dk]=L.r[j];
			L.r[j+dk]=L.r[0];
		}
}
void ShellSort(SqList &L,int dlta[],int t){
	int k;
	for(k=0;k<t;++k){
		ShellInsert(L,dlta[k]);
		cout<<"步长为"<<dlta[k]<<"的排序结果\n";
		OutPut(L);
	}
}//希尔排序

void BubbleSort(SqList &L){//起泡排序
	int n,i,flag;
	KeyType e;
	for(n=1;n<L.length ;n++){
		flag=0;
		for(i=1;i<=L.length-n;i++)
			if(L.r[i].key >L.r[i+1].key ){
				e=L.r[i].key ;
				L.r[i].key =L.r[i+1].key ;
				L.r[i+1].key =e;
				flag=1;
			}
			if(flag==0) return;
	}	
}
//快速排序
int Partition(SqList &L,int low,int high){
	KeyType pkey;
	L.r[0].key =L.r[low].key ;
	pkey=L.r[low].key ;
	while(low<high){
		while(low<high && L.r[high].key >=pkey) --high;
		L.r[low].key =L.r[high].key ;
		while(low<high && L.r[low].key <=pkey) ++low;
		L.r[high].key =L.r[low].key ;
	}
	L.r[low]=L.r[0];
	return low;
}
void QSort(SqList &L,int low,int high){
	int ploc;
	if(low<high){
		ploc=Partition(L,low,high);
		QSort(L,low,ploc-1);
		QSort(L,ploc+1,high);
	}
}
void QuickSort(SqList &L){
	QSort(L,1,L.length );
} //快速排序
//简单选择排序
int SelectMinKey(SqList L,int i){
	int min,j;
	min=i;
	for(j=i+1;j<=L.length ;j++)
		if(L.r[j].key<L.r[min].key )
			min=j;
	return min;
}
void SelectSort(SqList &L){
	int i,j;
	KeyType e;
	for(i=1;i<L.length ;i++){
		j=SelectMinKey(L,i);
		if(i!=j) {
			e=L.r[i].key ;
			L.r[i].key =L.r[j].key ;
			L.r[j].key =e;
		}
	}
}//简单选择排序
//堆排序
void HeapAdjust(SqList &H,int s,int m){
	int j;
	RedType rc;
	rc.key=H.r[s].key ;
	for(j=2*s;j<=m;j*=2){
		if(j<m && H.r[j].key<H.r[j+1].key) ++j;
		if(rc.key>=H.r[j].key) break;
		H.r[s].key=H.r[j].key; s=j;
	}
	H.r[s].key=rc.key;
}
void HeapSort(SqList &H){
	int i;
	KeyType t;
	for(i=H.length/2;i>0;--i)
		HeapAdjust(H,i,H.length);
	cout<<"将初始序列建立初始堆:\n"; // 将由初始序列建立的初始堆输出
	OutPut(H);  //将由初始序列建立的初始堆输出，这两条语句可删掉，不输出
	for(i=H.length;i>1;--i){
		t=H.r[1].key;
		H.r[1].key=H.r[i].key;
		H.r[i].key=t;
		HeapAdjust(H,1,i-1);
		cout<<"输出堆顶后调整成堆:\n"; // 输出堆顶后调整的新堆输出，也可删掉这两条语句不输出
		OutPut(H);  //  输出堆顶后调整的新堆输出，也可删掉这两条语句不输出

	}
}//堆排序


/////////////////////////////////////////////////////
//基数排序
typedef struct Node{ //定义基数排序用到的链式队列结点类型
	int data;
	struct Node *next;
}RLQNode,*RLinkQueue;

void initQue(RLinkQueue front[],RLinkQueue end[]){//初始化带头节点的链式队列（空队列）
	int i;
	RLinkQueue p;
	for(i=0;i<10;i++){
		p=(RLinkQueue)malloc(sizeof(RLQNode));
		p->next =NULL;
		if(!p) exit(OVERFLOW);
		front[i]=p;
		end[i]=p;
	}
}
void Distribute(int S[],int n,RLinkQueue end[],int k){
	//一次分配算法，从个位开始分配,个位定义为第1次，十位定义为第2次，依次类推
	//S为待排序数组，n为数组S长度，front为队头指针数组，end为队尾指针数组，k为第几次分配
	int i,t1,t2,d;
	RLinkQueue p;
	t1=(int)pow(10,k);
	t2=(int)pow(10,k-1);
	for(i=0;i<n;i++){
		d=(S[i]%t1)/t2;
		p=(RLinkQueue)malloc(sizeof(RLQNode));
		if(!p) exit(OVERFLOW);
		p->data =S[i];
		p->next =NULL;
		end[d]->next =p;
		end[d]=p;
	}//for
}
void outDisQ(RLinkQueue front[],int k){//输出分配后各队列
	int i;
	RLinkQueue p;
	cout<<"第"<<k<<"次分配后队列：\n";
	for(i=0;i<10;i++){
		cout<<i<<"队列：";
		p=front[i]->next ;		
		while(p){
			cout<<p->data<<"\t";
			p=p->next ;
		}//while
		cout<<"\n";
	}//for
}
void outArr(int S[],int n){//输出基数排序数组
	int i;
	cout<<"收集数据：\n";
	for(i=0;i<n;i++)
		cout<<S[i]<<"\t";
	cout<<"\n";
}
void Collect(int S[],RLinkQueue front[],RLinkQueue end[]){//一次收集算法
	int i,j=0;
	RLinkQueue p;
	for(i=0;i<10;i++){
		while(front[i]->next){
			p=front[i]->next ;
			S[j]=p->data ;
			j++;
			front[i]->next =p->next ;
			free(p);
		}//while
		end[i]=front[i];
	}//for
}

void RadixSort(){
	int n,i,k,*arr;
	RLinkQueue front[10],end[10];
	cout<<"请输入待排序序列长度：";
	cin>>n;
	arr=(int*)malloc(n*sizeof(int));
	if(!arr) exit(OVERFLOW);
	initQue(front,end);
	cout<<"请输入"<<n<<"个待排序整型关键字，关键字位数最多5位\n";
	for(i=0;i<n;i++)
		cin>>arr[i];
	for(k=1;k<=5;k++){
		Distribute(arr,n,end,k);
		outDisQ(front,k);
		Collect(arr,front,end);
		outArr(arr,n);
	}//for
	outArr(arr,n);
}

//基数排序
/////////////////////////////////////////////////////


void  main()
{
	SqList L;
	int first,final;
	RedType d[MAXSIZE+1];
	//int dlta[]={17,13,7,5,3,1};	如果希尔排序序列长，则步长数组dlta可长一些
	int dlta[]={5,3,1};//希尔序列只有10个，步长5、3、1即可
	cout<<"\n----用直接插入排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);//输出顺序表
	InsertSort(L);//直接插入排序
	cout<<"直接插入排序的结果：\n";
    OutPut(L);

	cout<<"\n----用折半插入排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	BInsertSort(L);//折半插入排序
	cout<<"折半插入排序的结果：\n";
    OutPut(L);

	cout<<"\n----用2-路插入排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	InsertSort2(L,d,first,final);//2-路插入排序	
    OutPut2(d,first,final,L.length );//输出2路插入排序结果
	
	cout<<"\n----用冒泡排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	BubbleSort(L);//冒泡排序
	cout<<"冒泡排序的结果：\n";
    OutPut(L);

	cout<<"\n----用快速排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	QuickSort(L);//快速排序	
	cout<<"快速排序的结果：\n";
    OutPut(L);

	cout<<"\n----用希尔排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	ShellSort(L,dlta,3);//希尔排序
	cout<<"希尔排序的结果：\n";
    OutPut(L);
	
	cout<<"\n----用简单选择排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	SelectSort(L);//简单选择排序
	cout<<"简单选择排序的结果：\n";
    OutPut(L);

	cout<<"\n----用堆排序方法排序如下----\n\n";
	inittable(L,MAXSIZE);
	cout<<"随机生成的初始数据序列：\n";
	OutPut(L);
	HeapSort(L);//堆排序
	cout<<"堆排序的结果：\n";
    OutPut(L);

	cout<<"基数排序： \n";
	RadixSort();

}

结果如下图所示