顺序表.cpp

属于利用C++开发的数据结构代码

#include"iostream.h"
#include"stdlib.h"
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 10
typedef struct{
	int *elem;
	int length;
	int listsize;
}SqList;

//顺序表的初始化
int InitList_Sq(SqList &L)
{
	int a;
	L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
	if(!L.elem) exit(0);
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	cout<<"请输入顺序表中的数据:(以0结束)"<<endl;
	cin>>a;
	for(int i=1;a!=0;i++)
	{
		L.elem[i]=a;
		L.length=i;
		cin>>a;
	}
	return 1;
}

//输出顺序表
void Print(SqList L)
{
	cout<<"现在的数据表是:"<<endl;
	for(int i=1;i<=L.length;i++)
		cout<<L.elem[i]<<' ';
	cout<<endl;
}

//在第i个位置之前插入元素
int ListInsert_Sq(SqList &L)
{
	int i,e;
	int *newbase,*p,*q;
	cout<<"请输入你要插入的数据:";
	cin>>e;
	cout<<"请输入你要插入的位置:";
	cin>>i;
	if(i<1||i>L.length) 
	{
		cout<<"插入位置不合法!"<<endl;
		return 0;
	}
	if(L.length>=L.listsize)
	{
		newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
		if(!newbase) exit(0);
		L.elem=newbase;
		L.listsize+=LISTINCREMENT;
	}
	q=&(L.elem[i]);
	for(p=&(L.elem[L.length]);p>=q;--p) 
		*(p+1)=*p;
	*q=e;
	++L.length;
	Print(L);
	return 1;
}

//顺序表的删除,删除第i个元素
int ListDelete_Sq(SqList &L)
{
	int *p,*q,i,e;
	cout<<"请输入你要删除的元素的位置:";
	cin>>i;
	if(i<1||i>L.length) 
	{
		cout<<"删除位置不合法!"<<endl;
		return 0;
	}
	p=&(L.elem[i]);
	e=*p;
	q=L.elem+L.length;
	for(++p;p<=q;++p)
		*(p-1)=*p;
	--L.length;
	Print(L);
	return 1;
}

//顺序查找
int Search_Seq(SqList L)
{//在顺序表中顺序查找关键字等于key的元素.若找到,返回该元素在表中的位置,否则为0.
	int key;
	cout<<"您选择了顺序查找."<<endl;
	cout<<"请输入你要查找的元素:";
	cin>>key;
	L.elem[0]=key;
	for(int i=L.length;L.elem[i]!=key;--i);
	if(i!=0)
		cout<<"你要查找的元素在数据表中是第"<<i<<"个."<<endl;
	else cout<<"表中没有此元素!"<<endl;
	return i;
}

//折半查找
int Search_Bin(SqList L)
{
	//在有序表L中折半查找其关键字等于key的数据元素。若找到，则函数值为
	//该元素在表中的位置，否则为0。
	int low,high,mid,key;
	cout<<"您选择了折半查找."<<endl;
	cout<<"请输入你要查找的元素:";
	cin>>key;
	low=1;
	high=L.length;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key==L.elem[mid]) return mid;
		else if(key<L.elem[mid]) high=mid-1;
		else low=mid+1;
	}
	return 0;
}

void Search_Bin_Result(SqList L)
{
	int i=Search_Bin(L);
	if(i!=0)
		cout<<"你要查找的元素在数据表中是第"<<i<<"个."<<endl;
	else cout<<"表中没有此元素!"<<endl;
}

//直接插入排序
void InsertSort(SqList &L)
{
	cout<<"您选择了直接插入排序."<<endl;
	for(int i=2;i<=L.length;++i)
		if(L.elem[i]<L.elem[i-1])
		{
			L.elem[0]=L.elem[i];
			L.elem[i]=L.elem[i-1];
			for(int j=i-2;L.elem[0]<L.elem[j];--j)
				L.elem[j+1]=L.elem[j];
			L.elem[j+1]=L.elem[0];
		}
	Print(L);
}

//希尔排序
void ShellInsert(SqList &L,int dk)
{
	for(int i=dk+1;i<=L.length;++i)
		if(L.elem[i]<L.elem[i-dk])
		{
			L.elem[0]=L.elem[i];
			for(int j=i-dk;j>0&&L.elem[0]<L.elem[j];j-=dk)
				L.elem[j+dk]=L.elem[j];
			L.elem[j+dk]=L.elem[0];
		}
}

void ShellSort(SqList &L)
{
	int k,dk;
	cout<<"您选择了希尔排序."<<endl;
	dk=L.length/2;
	for(k=0;dk!=0;k++)
	{
		ShellInsert(L,dk);
		dk=dk/2;
		cout<<"第"<<k+1<<"次希尔排序的结果是:"<<endl;
		for(int i=1;i<=L.length;i++)
			cout<<L.elem[i]<<' ';
		cout<<endl;
	}
}

//快速排序
int Partition(SqList &L,int low,int high)
{
	int pivotkey;
	L.elem[0]=L.elem[low];
	pivotkey=L.elem[low];
	while(low<high)
	{
		while(low<high&&L.elem[high]>=pivotkey) --high;
		L.elem[low]=L.elem[high];
		while(low<high&&L.elem[low]<=pivotkey) ++low;
		L.elem[high]=L.elem[low];
	}
	L.elem[low]=L.elem[0];
	Print(L);
	return low;
}

void QSort(SqList &L,int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1);
		QSort(L,pivotloc+1,high);
	}
}

//堆排序
typedef SqList HeapType;
void HeapAdjust(HeapType &H,int s,int m)
{
	//使H成为一个大顶堆
	int j,rc;
	rc=H.elem[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&H.elem[j]<H.elem[j+1]) ++j;
		if(rc>=H.elem[j]) break;
		H.elem[s]=H.elem[j];
		s=j;
	}
	H.elem[s]=rc;
}

void HeapSort(HeapType &H)
{
	int i,t;
	cout<<"您选择了堆排序."<<endl;
	for(i=H.length/2;i>0;--i)
		HeapAdjust(H,i,H.length);
	for(i=H.length;i>1;--i)
	{
		t=H.elem[1];	H.elem[1]=H.elem[i];	H.elem[i]=t;
		HeapAdjust(H,1,i-1);
	}
	Print(H);
}
		

void main()
{
	SqList L;
	int a,flag=0;     //flag=0时,顺序标未排序;flag=1时,顺序标已排序.
	if(InitList_Sq(L))
		Print(L);
	cout<<"你可以进行如下操作:"<<endl;
	cout<<"1.插入		2.删除		  3.顺序查找		4.折半查找"<<endl;
	cout<<"5.希尔排序	6.快速排序	  7.堆排序		8.直接插入排序"<<endl;
	cout<<"请输入你要进行的操作代号,输0退出."<<endl;
	cin>>a;
	while(a!=0)
	{
		switch(a)
		{
		case 1:
			ListInsert_Sq(L);
			break;
		case 2:
			ListDelete_Sq(L);
			break;
		case 3:
			Search_Seq(L);
			break;
		case 4:
			if(flag==0)
				cout<<"数据未排序!"<<endl;
			else
				Search_Bin_Result(L);
			break;
		case 5:
			if(flag==1)
				cout<<"数据已排序!"<<endl;
			else
			{
				ShellSort(L);
				flag=1;
			}
			break;
		case 6:
			if(flag==1)
				cout<<"数据已排序!"<<endl;
			else
			{
				cout<<"您选择了快速排序."<<endl;
				QSort(L,1,L.length);
				flag=1;
			}
			break;
		case 7:
			if(flag==1)
				cout<<"数据已排序!"<<endl;
			else
			{
				HeapSort(L);
				flag=1;
			}
			break;
		case 8:
			if(flag==1)
				cout<<"数据已排序!"<<endl;
			else
			{
				InsertSort(L);
				flag=1;
			}
			break;
		default:
			cout<<"输入错误!"<<endl;
			break;
		}
		cout<<"请输入你要进行的操作代号,输0退出."<<endl;
		cin>>a;
	}
}