++

数据结构课程设计：冒泡排序算法的具体实现

#define MAXSIZE 1000   //可排序表的最大长度
#define SORTNUM 2      //测试两种排序方法
typedef void (*Func)(long c,longs);   //2种排序方法的函数类型Func
static Func Sorts[SORTNUM]={BubbleSort,QuickSort};   //便于依次测试2种排序算法
static char *SortNames[SORTNUM]={"Bubbl","Quick"};   //用于显示测试结果比较表
static int Mix[]={0,1,4,16,64,128,256,512,4096};     //构造各级乱序表时随机交换元素个数
typedef int DataType[MAXSIZE+2];      //data[-1]和data[MAXSIZE+1]为辅助单元
DataType data;     //可排序表的顺序存储空间
DataType data2;    //辅助空间,保留最新打乱的数据
int      size;     //表的当前长度
long  compCount;   //关键字比较技数
long  shiftCount;  //关键字移动技数
//------------内部操作-------------
void BeforeSort()     //每个排序算法在入口处调用
{
 compCount=shiftCount=0;
} //BeforeSort                                                                                                                                                                                                                                         

status Less (int i,int j)    //若表中第i个元素小于第j个元素,则返回True,否则False
{
 compCount++;                //关键字比较次数加1
 return data[i]<data[j];
}  //Less

void Swap (int i,int j)      //交换表中第i个和第j个数据元素
{
 data[i]<-->data[j];
   shiftCount=shiftCount+3;  //关键字移动次数加3
}  //Swap

void Shift (int i,int j)     //将表中第i个元素的值赋给第j个元素
{
 data[j]=data[i];
   shiftCount++;             //关键字移动次数加1    
}   //Shift

void  CopyData (DataType list1,DataType &list2)      //复制数据
{
 for (i=1;i<=size;i++)   list2[[i]=list1[i];
}  //CopyData

void InverseOrder()          //将可排序表置为逆序
{
 for (i=1;i<=size;i++) data[i]=data2[i]=size-i+1;
}  //InverseOrder

//------部分操作的伪码算法-------- 
void InitList(int n)
{
 if (n<1) size=0; 
 else{
   if (n>MAXSIZE) n=MAXSIZE;
   for (i=1;i<=n;i++) data[i]=data2[i]=i;
   size=n;
  }
  compCount=shiftCount=0;
}  //InitList

void RandomizeList(int d,int isInverse)   //对可排序表进行d次随机打乱.d>=0&&d<=8,d为0时表不变
{
 if(isInverse)InverseOrder();            //逆序
 else InitList(size);                    //正序
 for(i=1;i<=Mix[d];i++)                  //d级打乱,随机交换若干元素
   data[Random(size)+1]<-->data[Random(size)+1];
 CopyData(data,data2);                   //保留,以便对各种排序算法测试相同数据
}  //RandomizeList

void RecallList()             //恢复最后一次用RandomizeList随机打乱后的可排序表
{
 CopyData(data2,data);
}  //RecallList

void BubbleSort (listtype r,long &c,long&s)   //进行冒泡排序,返回关键字比较次数c和移动次数s
 Sorted=FALSE;Pass=0;
 while (!Sorted)
 {Pass++;Sorted=TRUE;
  for(i=1;i<=n-Pass;i++)
    if(r[i].key>r[i+1].key)
    {r[i]<-->r[i+1];
     Sorted=FALSE;
    }
  }
  c=compCount;s=shiftCount;
}

void QuickSort(listtype r,int c,s)
{
 if(c<s)
 {QuickSort(r,c,s,&k);
  QuickSort(r,c,k-1);
  QuickSort(r,k+1,s);
 }
}
void QuickSort(listtype r,int c,s,*i)
{
 c=compCount;s=shiftCount;
 *i=c;j=s;rp=r[c];x=r[c].key;
 while(i<j)
 {while((*i<j)&&(r[j].key>=x))
   j--;
   r[*i]=r[j];
   while((*i<j)&&(r[i].key<=x))
   (*i)++;
   r[j]=r[*i];
  }
  r[i]=rp;
}



#define minGroup 8
#define maxGroup 18
void Initialization(){//系统初始化
  randomize();
  clscr();//清屏

在屏幕上方显示操作命令清单和缺省值：
    SortTest-1  Size(100-1000)--2 Groups(8-18)--3 Quit--q
      size=400  groups=18
 }//Initialization

void ReadCommand(char &cmd){//读入操作命令符
显示键入操作命令符的提示信息；
do{cmd=getche();} while(cmd不属于['1','2','3','q','Q']);
}
void Interpret(char cmd){//解释执行操作命令cmd
  switch(cmd){
case'1':显示测试结果比较表的表头；//以下略去表格符号显示
        for(i=0;i<=groups-1;i++){//逐组测试
          if(i<groups/2)
             RandomizeList(i,FALSE);//对正序表作第i级打乱
          else 
             RandomizeList(groups-i-1,TRUE);//对逆序表作第i级打乱
          for(j=0;j<SORTNUM;j++){//对每种排序方法测试
            RecallList();//还原数据
            (*Sorts[j])(c,s);//测试第j种排序算法
//显示关键字比较次数c和移动次数s：
   GotoXY(6+(j-1)*6,i+7);printf("%6ld",c);
   GotoXY(44+(j-1)*6,i+7);printf("%6ld",s);
  }//forj
}//fori
显示测试结果比较表的相应部分表格符；
break;
case'2':显示键入可排序的长度的提示信息；
       scanf("%d",n);//读入表的长度到整数变量n
       if(n<100) n=100;
       if(n>1000)n=1000;
       InitList(n);//构造元素依次为1，2，3......n的有序表
       break;
case'3':显示键入测试的组数的提示信息；
       scanf("%d",groups);
       if(groups<minGroup) groups=minGroup;  
       if(groups>maxGroup) groups=maxGroup; 
      }
}//Interpret


void main(){//主函数
Initialization();   //初始化
 do{
    ReadCommand(cmd);   // 读入一个操作命令符

    Interpret(cmd);    //解释执行命令符
  }while (cmd!='q'&&cmd!='Q');
}//main