#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<<"請輸入順序表中的數(shù)據(jù):(以0結(jié)束)"<<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<<"現(xiàn)在的數(shù)據(jù)表是:"<<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<<"請輸入你要插入的數(shù)據(jù):";
	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)
{//在順序表中順序查找關(guān)鍵字等于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<<"你要查找的元素在數(shù)據(jù)表中是第"<<i<<"個."<<endl;
	else cout<<"表中沒有此元素!"<<endl;
	return i;
}

//折半查找
int Search_Bin(SqList L)
{
	//在有序表L中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為
	//該元素在表中的位置，否則為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<<"你要查找的元素在數(shù)據(jù)表中是第"<<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<<"次希爾排序的結(jié)果是:"<<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<<"數(shù)據(jù)未排序!"<<endl;
			else
				Search_Bin_Result(L);
			break;
		case 5:
			if(flag==1)
				cout<<"數(shù)據(jù)已排序!"<<endl;
			else
			{
				ShellSort(L);
				flag=1;
			}
			break;
		case 6:
			if(flag==1)
				cout<<"數(shù)據(jù)已排序!"<<endl;
			else
			{
				cout<<"您選擇了快速排序."<<endl;
				QSort(L,1,L.length);
				flag=1;
			}
			break;
		case 7:
			if(flag==1)
				cout<<"數(shù)據(jù)已排序!"<<endl;
			else
			{
				HeapSort(L);
				flag=1;
			}
			break;
		case 8:
			if(flag==1)
				cout<<"數(shù)據(jù)已排序!"<<endl;
			else
			{
				InsertSort(L);
				flag=1;
			}
			break;
		default:
			cout<<"輸入錯誤!"<<endl;
			break;
		}
		cout<<"請輸入你要進行的操作代號,輸0退出."<<endl;
		cin>>a;
	}
}