数据结构实验之快速排序

#include<iostream.h>

#include<string.h>

 

#define Maxsize 100//顺序表的最大长度

#define MAXNUM 100

 

int num=0;

 

typedef struct

{

       int   num;              //学号

       char       name[10];//     姓名

}Student;

 

Student student[Maxsize];

 

char re_choose[]={"\n选择非法，请输入正确的编号...\n"};

 

void Menu_name()

     //作者信息

{  

       cout<<"              **************************************************  "<<endl;

       cout<<"                                 快速排序                         "<<endl;

       cout<<"              **************************************************  "<<endl;

       cout<<endl;

}

 

                            //记录类型

typedef struct

{

    Student r[Maxsize+1];

    int Length;                    //顺序表长度

}SqList;                       //顺序表类型

 

SqList L;

 

void CreteSqList(SqList &L,int length)

{

       L.Length=length;

       int i;

            for( i = 0; i<L.Length;i++)

              {                  

                     L.r[i].num=student[i].num;//以学号为关键字;

                     //注意这里这样编写是为了不改变排序的函数

                     strcpy(L.r[i].name,student[i].name);                  

              }           

}

 

void print_Sqlist(SqList &L)

{

       cout<<"第"<<num<<"次排序"<<endl;

       for(int n =0;n<L.Length;n++)

       {

                     cout<<L.r[n].num<<"  ";

       }

       cout<<endl;

}

 

int Partition(Student r[],int low,int high)

{//对记录序列L.r[low..high]进行一次快速排序，并将本范围的元素按标准元素分为两部分，

//且标准元素在这两部分之间。

       int  StandardKey;

       Student Temp;

       Temp= r[low];                                          //将标准记录放入中间单元

 

 

 

       StandardKey=r[low].num;                          //本范围的标准元素

 

 

       while (low<=high)                             //从表的两端交替地向中间扫描

       {

              while(low<high && r[high].num>=StandardKey)

                     high--;

 

              r[low++]=r[high];                             //将小于标准元素的数据往前放

 

              while(low<=high && r[low].num<=StandardKey)

                     low++;

 

              r[high--]=r[low];                        //将大于标准元素的数据往后放

       }

 

       r[--low]=Temp;      //标准元素移到正确位置

 

       print_Sqlist(L);//打印序列排序结果

 

       return low;                                               //返回标准位置

}           

void Qsort(Student r[],int low,int high)

{//对记录序列r[low..high]进行快速排序

       int StandardLoc;

       if(low<=high-1)

       {

              num++;

              StandardLoc=Partition(r,low,high);

              //对r[low..high]进行一次划分，并返回标准位置

 

              Qsort(r,low,StandardLoc-1);

              Qsort(r,StandardLoc+1,high);

 

       }

}

 

void QuickSort(SqList &L)

{//对顺序表L进行快速排序

       Qsort(L.r,0,L.Length-1);                     //low和high用初值0,L.length-1调用

}

 

 

 

void Displayarray(Student a[])

{

       int i;

       for(i=1;i<Maxsize&&a[i-1].num!=0;i++)

       {

              cout<<"  序号:"<<i<<'\t'<<"  学号:"<<a[i-1].num<<'\t'<<"  姓名:"<<a[i-1].name<<'\t';

              cout<<endl;

       }

       cout<<endl;

}

 

void Displayarray1(SqList &L)

{

       int i;

       for(i=0;i<L.Length;i++)

       {

              cout<<"  序号:"<<i+1<<'\t'<<"  学号:"<<L.r[i].num<<'\t'<<"姓名:"<<L.r[i].name<<'\t';

              cout<<endl;

       }

       cout<<endl;

}

 

void Menu()    //菜单函数

{

       cout<<"\n\t\t"<<"请选择以下一个功能:"<<endl;

       cout<<"\n\t\t"<<"1.排序前学生成绩表."<<endl;

       cout<<"\t\t2.快速排序过程演示." << endl;

       cout<<"\t\t3.排序后学生成绩表." << endl;

       cout<<"\t\t0.退出.\n"<<endl;

}

 

 

 

 

int main()

{

       int i,a;

       Menu_name();

       char name[20][20]={"LEBRON","IVERSON","NUSH","DUNCAN","YAO","KOBY","PARK","ROY","ALLAN","PUAL"};

    int num[10]={23,3,13,21,11,24,17,7,20,34};

       for(i=0;i<10;i++)

       {

              student[i].num=num[i];

              strcpy(student[i].name,name[i]);  

       }

       cout<<"\t\t\t******学生学号的快速排序******\t\n";

       CreteSqList(L,10); 

       while(1)

       {

              Menu();  

              cout<<"\n\t请输入功能编号:";

              cin>>a;  

                     switch(a)

                     {

                    

                            case 1 ://排序前学生成绩表.

                                   cout<<"\n排序前学生成绩表:\n";

                                   Displayarray(student);                 

                                   break;

 

                            case 2 ://快速排序过程演示.

                                   cout<<"\n\n************堆排序算法演示*********\n";

                                   QuickSort(L);

                                   print_Sqlist(L);

                                   break;

 

                            case 3 ://排序后学生成绩表.

                                   cout<<"\n排序后学生成绩表:\n";

                                   Displayarray1(L);

                                   break;

                           

                            case 0:

                                   return 0;

                                   break;

                            default  :

                                   cout <<re_choose<<endl;

                                   break;

             

                     }//end switch

              }

       return 0;

}