关于数据结构的课程设计

#include "stdio.h"

#define MAX 30000

/* 函数声明区 */

int SequenceSearch(int e[], int len, int key);

int BinarySearch(int e[], int len, int key);

void StraightInsertSort(int e[], int len);

void QuickSort(int e[], int first, int end);

void MergeSort(int e[],int a[],int first,int end);

void HeapSort(int e[],int len);

void Print(int e[], int len, int cols);

/* 全局变量区 */

long compare; /* 比较次数 */

long move; /* 移动次数 */

void main()

{

    int i;

    int n;

    int table[MAX], table1[MAX];

    int key;

    int pos;

    int choice;

    int cols = 10;

    system("cls");

    printf("***********************************************************\n");

    printf("INITIALIZE TABLE\n");

    printf("n = ");

    scanf("%d", &n);

    srand(time(NULL));

    for(i=0; i

    {

     table[i] = rand();

     table1[i] = table[i];

    }

    while(1)

    {

     system("cls");

     printf("***********************************************************\n");

     printf("ORIGIN TABLE (%d) : \n", n);

     Print(table, n, cols);

     printf("***********************************************************\n");

     printf("ORDER TABLE (%d)  : \n", n);

     StraightInsertSort(table1, n);

     Print(table1, n, cols);

    printf("***********************************************************\n");

    printf("                 ALGORITH ANALYSIS SYSTEM                  \n\n");

    printf("                  1.  SEQUENCE SEARCHING                   \n");

    printf("                  2.  BINARY SEARCHING                     \n");

    printf("                  3.  STRAIGHT INSERT SORTING              \n");

    printf("                  4.  MERGE SORTING                        \n");

    printf("                  5.  HEAP SORTING                         \n");

    printf("                  6.  QUICK SORTING                        \n");

    printf("                  0.  EXIT SYSTEM                          \n\n");

    printf("***********************************************************\n\n");

    printf("     YOUR CHOICE : ");

    scanf("%d", &choice);

    switch(choice)

    {

     case 0:

     return;

     case 1:

     {     

     /***********************************************************************/

    /* 执行顺序查找 */

    printf("\t\tkey = ");

     scanf("%d", &key);

    compare = 0;

    pos = SequenceSearch(table, n, key);

    printf("\t\tSequence Searching \n");

    printf("----------------------------------------\n");

    printf("Analysis details : \n");

    if(pos == -1)

    {    

     printf("\tsearch %d fail.\n", key);

     printf("\tcompare : %ld times.", compare);

    }

    else

    {

     printf("\tsearch %d success.\n", key);

     printf("\tcompare : %ld times.", compare);

    }

    printf("\n\n");

    /***********************************************************************/     

     break;

     }

     case 2:

     {

     /***********************************************************************/

    /* 执行二分查找 */

    printf("\t\tkey = ");

     scanf("%d", &key);

    compare = 0;

    pos = BinarySearch(table1, n, key);

    printf("\t\tBinary Searching \n");

    printf("----------------------------------------\n");

    printf("Analysis details : \n");

    if(pos == -1)

    {    

     printf("\tsearch %d fail.\n", key);

     printf("\tcompare : %ld times.", compare);

    }

    else

    {

     printf("\tsearch %d success.\n", key);

     printf("\tcompare : %ld times.", compare);

    }

    printf("\n\n");

    /***********************************************************************/

     break;

     }

     case 3:

     {

     /***********************************************************************/

    /* 执行直接插入排序 */

    for(i=0; i

     table1[i] = table[i];

    compare = move = 0;

    StraightInsertSort(table1, n);

    printf("\t\tStraight Insert Sorting \n");

    printf("----------------------------------------\n");

    printf("Analysis details : \n");

    printf("\tcompare : %ld times.\n", compare);

    printf("\tmove    : %ld times.\n\n", move);

    /***********************************************************************/

     break;

     }

     case 4:

     {

     /***********************************************************************/

    /* 执行归并排序 */

    for(i=0; i

     table1[i] = table[i];

    compare = move = 0;

    MergeSort(table1, table, 0, n-1);

    printf("\t\tMerge Sorting \n");

    printf("----------------------------------------\n");

    printf("Analysis details : \n");

    printf("\tcompare : %ld times.\n", compare);

    printf("\tmove    : %ld times.\n\n", move);

    /***********************************************************************/

     break;

     }

     case 5:

     {

     /***********************************************************************/

    /* 执行堆排序 */

    for(i=0; i

     table1[i] = table[i];

    compare = move = 0;

    HeapSort(table1, n);

    printf("\t\tHeap Sorting \n");

    printf("----------------------------------------\n");

    printf("Analysis details : \n");

    printf("\tcompare : %ld times.\n", compare);

    printf("\tmove    : %ld times.\n\n", move);

    /***********************************************************************/

     break;

     }

     case 6:

     {

     /***********************************************************************/

    /* 执行快速排序 */

    for(i=0; i

     table1[i] = table[i];

    compare = move = 0;

    QuickSort(table1, 0, n-1);

    printf("\t\tQuick Sorting \n");

    printf("----------------------------------------\n");

    printf("Analysis details : \n");

    printf("\tcompare : %ld times.\n", compare);

    printf("\tmove    : %ld times.\n\n", move);

    /***********************************************************************/

     break;

     }

     default:

     break;

    }/* end of switch*/

    system("pause");

    getch();

   }

}

/*  顺 序 查 找  */

int SequenceSearch(int e[], int len, int key)

{

int i;

for(i=0; i

if(++compare && e[i]==key)

return i;

++compare;

return -1;

}

/*  二 分 查 找  */

int BinarySearch(int e[], int len, int key)

{

int high,low,mid;

high=len-1;

low=0;

while(low<=high)

  {

mid=(low+high)/2;

++compare;

if(key==e[mid])

return mid;

else if(key>e[mid])

low=mid+1;

else

high=mid-1;

}

++compare;

return  -1;

}

/*    直 接 插 入 排 序    */

void StraightInsertSort(int e[], int len)

{

int i,j,temp;

for(i=1; i

{

temp=e[i];

++move;

for(j=i-1; j>=0; j--)

{

if(++compare && e[j] > temp)

{

e[j+1]=e[j];

++move;

}

else

break;

}

e[j+1]=temp;

++move;

}

}

/*    快  速  排  序    */

void QuickSort(int e[], int first, int end)

{

int i=first,j=end,temp=e[first];

while(i

  {

while(++compare && i=temp)

j--;

e[i]=e[j];

++move;

while(++compare && i

i++;

e[j]=e[i];

++move;

  }

e[i]=temp;

  if(first

   QuickSort(e,first,i-1);

if(end>i+1)

QuickSort(e,i+1,end);

}

/*    归  并  排  序    */

void MergeSort(int e[],int a[],int first,int end)

{

void Merge(int e[],int a[],int first,int m,int end);

int m;

int bak[MAX];

if(first==end)

a[first]=e[first];

else

{

m=(first+end)/2;

MergeSort(e,bak,first,m);

MergeSort(e,bak,m+1,end);

Merge(bak,a,first,m,end);

}

for(m=0;m<=end;m++)

e[m]=a[m];

}

void Merge(int e[],int a[],int first,int m,int end)

{

int i=first,j=m+1,k=first;

while(i<=m && j<=end)

{

++compare;

++move;

if(e[i]<=e[j])

a[k++]=e[i++];

else

a[k++]=e[j++];

}

while(i<=m && ++move)

a[k++]=e[i++];

while(j<=end && ++move)

a[k++]=e[j++];

}

/*    堆   排   序     */

void HeapSort(int e[],int len)

{

void sift(int e[],int l,int m);

int i,temp;

for(i=len/2-1;i>=0;i--)

sift(e,i,len);

for(i=len-1;i>=1;i--)

{

move += 2;

temp=e[i];

e[i]=e[0];

e[0]=temp;

sift(e,0,i-1);

}

}

void sift(int e[],int l,int m)

{

int i,j,x;

i=l;

j=2*i+1;

x=e[i];

while(j<=m)

{

if(j

j++;

if(++compare && x

{

++move;

e[i]=e[j];

i=j;

j=2*i+1;

}

else j=m+1;

}

e[i]=x;

++move;

}

void Print(int e[], int len, int cols)

{

int i;

for(i=1; i<=len; i++)

{

printf("%6d", e[i-1]);

if(i%cols == 0)

printf("\n");

}

printf("\n");

} 

运行测试：