px.h

数据结构基础代码

const error=0;
const ok=1;
const ERROR =-1; 
const OVERFLOW =-2; 
const LIST_INIT_SIZE=100; 
const maxsize=200;
const LISTINCREMENT=10;  

//定义线形表的结构
typedef struct {     
        int  *elem;     
        int length;     
        int listsize; 
		int incrementsize;
}sqlist; 
 
//给线形表的元素分配空间
void InitList_Sq(sqlist &l)
{
	l.elem=new int[maxsize];
	l.length=0;
	l.listsize=maxsize;
}
 
//初始化线形表
void create_sq(sqlist &l)
{
	int x;	
	cout<<"请输入线形表的元素:(输入0表示结束!)"<<endl;
	for(int i=1;i<=maxsize;i++)
	{ 
		cin>>x;
		if(x==0)
			break;
		l.elem[i]=x;
		l.length++;
	}
}

//直接插入排序
void insertsort(sqlist &l)
{
	int i,j;
	for(i=2;i<=l.length;++i)
	{
		if(l.elem[i]<l.elem[i-1])
		{
			l.elem[0]=l.elem[i];
			for(j=i-1;l.elem[0]<l.elem[j];--j)
				l.elem[j+1]=l.elem[j];
			l.elem[j+1]=l.elem[0];
		}
	}

}

//折半插入排序
void middlesort(sqlist &l)
{
	int low,high,m;
	for(int i=2;i<=l.length;++i)
	{
		l.elem[0]=l.elem[i];
		low=1;
		high=i-1;
		while(low<=high)
		{
			m=(low+high)/2;
			if(l.elem[0]<l.elem[m])
				high=m-1;
			else low=m+1;
		}
		for(int j=i-1;j>=high+1;--j)
			l.elem[j+1]=l.elem[j];
			l.elem[high+1]=l.elem[0];
	}
	for(i=1;i<=l.length;++i)
	{
		cout<<l.elem[i]<<'\t';
	}
}

//希尔排序
void shellinsert(sqlist &l, int dk) //对顺序表L作一趟希尔排序
{
	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[j]>=l.elem[0];j-=dk)
				l.elem[j+dk]=l.elem[j]; 
			l.elem[j+dk]=l.elem[0];
		}
}

//快速排序
int partition(sqlist l,int low,int high)
{
	int pivotkey;
	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]=pivotkey;
	return low;
}
void quicksort(sqlist l,int low,int high)
{
	int pivotloc;
	if(low<high)
	{
	pivotloc=partition(l,low,high);
	quicksort(l,1,pivotloc-1);
	quicksort(l,pivotloc+1,high);
	}
}
//简单选择排序
void selectsort(sqlist &l)
{
	int i,temp;
	for(i=1;i<l.length;i++)
	{
		int k=i;
		for(int j=i+1;j<=l.length;j++)
			if(l.elem[j]<l.elem[k]) k=j;
			if(k!=i)
			{
				temp=l.elem[k];
				l.elem[k]=l.elem[i];
				l.elem[i]=temp;
			}
	}
}