base.cpp

各种内部排序算法的实现和比较

#include "base.h"

//////////////////////////// SqList的基本操作 ////////////////////////////
int InitSqList(SqList &L)
{//初始化线形表L
	int i;

	L.r=(RedType *)malloc((MAXSIZE+1)*sizeof(RedType));
	for(i=1;i<MAXSIZE+1;i++)
		L.r[i].key=0;
	L.length=0;	//空表长度为0
	return 1;
}//InitSqList

int ClearSqList(SqList &L)
{//将存在的线形表L置空
	L.length=0;
	return 1;
}//ClearSqList

int DestroySqList(SqList &L)
{//销毁线形表L
	if(!L.r)
		return 0;
	free(L.r);
	L.length=0;
	return 1;
}//DestroySqList

void PrintSqList(SqList L)
{//输出线性表L元素
  int i;
  int j=0;
  for(i=1;i<=L.length;i++)
  {
	  if(j!=8)
	  {
		  cout<<setw(8)<<L.r[i].key;
		  j++;
	  }
	  else{
		  j=0;
		  cout<<endl;
	  }
  }
  cout<<endl;
}//PrintSqList
/*
void CreatSqList(SqList &L)//测试专用
{//建线性表L
	int	l,i;
	cout<<"表长:	";
	cin >>l;
	L.length=l;
	for(i=1;i<=l;i++)
	{
		cout<<"第"<<i<<"个:	";
		cin >>L.r[i].key;
	}
}
*/
/////////////////////////////////////////////////////////////////////////////
//////////////////////////// SLinkListType 的基本操作 ///////////////////////
int InitSLinkList(SLinkListType &SL)
{//初始化静态链表SL
	int i;
	SL.r=(SLNode *)malloc((SIZE+1)*sizeof(SLNode));
	for(i=1;i<SIZE+1;i++)
		SL.r[i].rc=0;
	SL.length=0;					//空表长度为0
	return 1;
}//InitSLinkList

int ClearSLinkList(SLinkListType &SL)
{//将存在的静态链表SL置空
	SL.length=0;
	return 1;
}//ClearSLinkList

int DestroySLinkList(SLinkListType &SL)
{//销毁静态链表SL
	if(!SL.r)
		return 0;
	free(SL.r);
	SL.length=0;
	return 1;
}//DestroySLinkList

void PrintSLinkList(SLinkListType SL)
{//输出静态链表SL元素
  int i;
  int j=0;
  for(i=1;i<=SL.length;i++)
  {
	  if(j!=8)
	  {
		  cout<<setw(8)<<SL.r[i].rc;
		  j++;
	  }
	  else{
		  j=0;
		  cout<<endl;
	  }
  }
  cout<<endl;
}//PrintSLinkList
/*
void CreatSLinkList(SLinkListType &SL)//测试专用
{//建线性表SL
	int	l,i;
	cout<<"表长:	";
	cin >>l;
	SL.length=l;
	for(i=1;i<=l;i++)
	{
		cout<<"第"<<i<<"个:	";
		cin >>SL.r[i].rc;
	}
}
*/
/////////////////////////////////////////////////////////////////////////////
///////////////////////// SLList 基本操作 ///////////////////////////////////
int Getkeynum(int m)
{//获取m的位数
	int num=1;
	if(m<10)
		return num;
	else
		do{
			m=m/10;
			num++;
		}while(m!=0);
	return num-1;
}

int InitSLList(SLList &SLL,RedType D[],int n)
{//初始化静态链表SLL(把数组D中的数据存于SLL中)
	char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
	int i,j,k;

	SLL.r=(SLCell*)malloc((MAX_SPACE+1)*sizeof(SLCell));
	int max=D[0].key;						//max为关键字的最大值
	for(i=1;i<n;i++)
	{
		if(max<D[i].key)
			max=D[i].key;
	}
	k=SLL.keynum=Getkeynum(max);
	SLL.recnum=n;
	for(i=1;i<=n;i++)
	{
		itoa(D[i-1].key,c,10);				//将10进制整型转化为字符型,存入c
		for(j=strlen(c);j<SLL.keynum;j++)	//若c的长度<max的位数,在c前补'0'
		{
			strcpy(c1,"0");
			strcat(c1,c);
			strcpy(c,c1);
		}
		for(j=0;j<k;j++)
		SLL.r[i].keys[j]=c[k-1-j];
	}
	SLL.keynum=k;
	SLL.recnum=n;
	return 1;
}

int ClearSLList(SLList &SLL)
{//清空静态链表SLL
	SLL.recnum=0;
	return 1;
}

int DestroySLList(SLList &SLL)
{//销毁静态链表SL
	if(!SLL.r)
		return 0;
	free(SLL.r);
	SLL.recnum=0;
	SLL.keynum=0;
	return 1;
}//DestroySLList

void PrintlSLList(SLList SLL)
 {//按链表输出静态链表SLL
	int i=SLL.r[0].next,j;
	int k=0;
	while(i)
	{
		if(k!=8)
		{
			for(j=SLL.keynum-1;j>=0;j--)
				cout<<SLL.r[i].keys[j];
			cout<<"	";
			i=SLL.r[i].next;
			k++;
		}
		else{
			cout<<endl;
			k=0;	
		}
	}
}

void PrintSLList(SLList SLL)
{//按数组序号输出静态链表SLL
	int i,j,k;
	for(i=1,k=0;i<=SLL.recnum;i++)
	{
		if(k!=8)
		{
			for(j=SLL.keynum-1;j>=0;j--)
				cout<<SLL.r[i].keys[j];
				cout<<"	";
				k++;
		}
		else{
			cout<<endl;
			i--;
			k=0;
		}
	}
}