数据完整程序（课程设计）.c

数据结构中各种排序算法

#include <stdio.h>
#include <time.h> /**  时间函数头文件 **/
#include <dos.h>  /****   延时函数头文件  **/

#define MAXTEM 10
typedef int KeyType;
typedef struct  {
  KeyType Key;
      /***** other information!   ******/
} RecType;

typedef RecType Sqlist[MAXTEM+1];
/** Sqlist[0]元素作为监视哨  **/

    /****             ****/
void CreateSqlist(Sqlist R)
{int i,j;
  for(i=1;i<MAXTEM+1;i++)
   {puts("Enter key:");
    scanf("%d",&j);
    R[i].Key=j;
   }
Print(R);
  return ;
 }

     /*****              Output function         *****/
Print(Sqlist  R)
{int i;
 for(i=1;i<=MAXTEM;i++)
printf(" %3d",R[i].Key);
printf("\n\n");
return 0;
}

/****               NO.1  Bullesort     function            ****/
void Bullesort(Sqlist R)         /*排序元素R[1]至R[MAXTEM]*/
{        int i,j,M;
	 for(i=1;i<=MAXTEM;i++)
          {  delay(10000);
             for(j=MAXTEM;j>=i+1;j--)
		   if(R[j].Key<R[j-1].Key)   /*比较*/
		     { M=R[j].Key;
			R[j]=R[j-1];    /*R[j]与R[j+1]交换*/
			  R[j-1].Key=M;
		     }
              }
  Print(R);
    return;
}

/*****               No.2 Insertsort function           ******/

void Insertsort(Sqlist R)/*直接出入排序*/
{ int i,j;
   for(i=2;i<=MAXTEM;i++)
    { delay(10000);
      R[0]=R[i];  /**R[0]为监视哨 **/
       j=i-1;
      while(R[0].Key<R[j].Key)
       { R[j+1]=R[j];  /**元素移动，以便腾出一个位置出入R[i]*/
	j--;
	}
       R[j+1]=R[0];  /**将监视哨中元素赋给第j+1个元素**/
    }
 Print(R);
return ;
}

 /****           NO.3  Quicksort function               ****/

void Quicksort(Sqlist R,int n,int m)
{  int i=n,j=m;
   if(n<m)
    {delay(5000);
    R[0]=R[n];
      do
     { delay(10000);
        while(j>i&&R[j].Key>=R[0].Key) j--;/*从右往左扫描*/
	if(i<j)
	 {  R[i]=R[j];/*替换*/
	    i++;
	  }
     while(i<j&&R[i].Key<=R[0].Key) i++;/*从左往右扫描*/
       if(i<j)
	{ R[j]=R[i];/*替换*/
	   j--;
	 }
    }while(i<j);
   R[i]=R[0];
    Quicksort(R,n,j-1);   /*对左区间递归排序 **/
    Quicksort(R,j+1,m);/*对右区间递归排序*/
   }
  return ;
}




/****             No.4 Heapsort   function    大根堆排序        ****/

void Heapify(Sqlist R,int low,int high)
{int large,temp=R[low].Key;/*筛选运算*/
  for(large=low*2;large<=high;large *=2)
  {delay(10000);
    if ((large <high) && (R[large].Key<R[large+1].Key))
       large++;
    if (temp>= R[large].Key)  break;
     R[low].Key = R[large].Key;
     low = large;
  }
  R[low].Key = temp;
}


void BuildHeap(Sqlist R)   /****  建堆   *****/
{ int i;
  for (i=MAXTEM/2;i>0;i--)
{ delay(10000);
    Heapify(R,i,MAXTEM);
}

}
void Heapsort(Sqlist R)  /*  对R[1..MAXTEM]进行堆排序,不妨用R[0]做暂存单元  */
{int i;
  BuildHeap(R);  /*  将R[1..MAXTEM]建成初始堆  */
  for (i=MAXTEM;i>1;i--)
  {  /* 对当前无序区R[1..i]进行堆排序,共做MAXTEM-1趟  */
    delay(5000);
    R[0] = R[1];  /* 将堆顶和堆中最后一个记录交换  */
    R[1] = R[i];
    R[i] = R[0];
    Heapify(R,1,i-1);  /* 将R[1..i-1]重新调整为堆,仅有R[[1]可能违反堆性质  */
  }
  return ;
}

/*****           NO.5  Selectsort function          ****/

void Selectsort(Sqlist R)/*直接选择排序*/
{  int i,j,k,temp;
    for(i=1;i<=MAXTEM;i++)
      {  delay(5000);
         k=i;
	 for(j=i+1;j<=MAXTEM;j++)
           if(R[j].Key<R[k].Key)
      k=j;  /*  k标记每趟选择排序过程中无序区段中的最小元素的位置*/
         temp=R[i].Key;
         R[i]=R[k];
	 R[k].Key=temp;  /*将R[k]与R[i]交换*/
      }
 Print(R);
       return;
}

/******    No.6 Mergesort function    ******/

void Merge(Sqlist R,int low,int m,int high)
{   /*将两个有序的子序列R[low..m)和R[m+1..high]归并成一个有序的子序列R[low..high] */
  int i=low,j=m+1,p=0;   /*置初始值*/
     RecType *R1;   /*R1是局部向量,若p定义为此类型指针速度更快*/
   R1=(RecType*)malloc((high-low+1)*sizeof(RecType));    /*动态申请R1*/
     if(! R1)
     printf("Insufficient memory available!");
     while(i<=m&&j<=high)   /*两子序列非空时，取其小者输出到R1[p]上*/
        R1[p++]=(R[i].Key<=R[j].Key)?R[i++]:R[j++];
     while(i<=m)     /*若第1个子序列非空,则复制剩余记录到R1中*/
       R1[p++]=R[i++];
     while(j<=high)    /*若第2个子序列非空,则复制剩余记录到R1中*/
       R1[p++]=R[j++];
     for(p=0,i=low;i<=high;p++,i++)
       R[i]=R1[p];    /*归并完成后将结果复制回R[low..high]*/

}


void MergePass(Sqlist R,int length)
{    int i;
     for(i=1;i+2*length-1<=MAXTEM;i=i+2*length)
      Merge(R,i,i+length-1,i+2*length-1);         /*归并长度为length的两个相邻子序列*/
    if(i+length-1<MAXTEM)   /*尚有两个子序列其中后一个长度小于length*/
	Merge(R,i,i+length-1,MAXTEM);   /*归并最后两个子序列*/
        /*注意若i≤n且i+length-1≥n时 则剩余一个子序列轮空，无须归并*/
}

void Mergesort(Sqlist R)   /*二路归并排序算法*/
{/*采用自底向上的方法，对R[1..MAXTEM]进行二路归并排序*/
 int i;
 for(i=1;i<MAXTEM;i*=2)   /*做趟归并*/
 {
  delay(5000);
  MergePass(R,i);  /*有序段长度≥n时终止*/
}
}

 /*****   No.7  RadixSort function   ****/

#define KeySize  4   /**  最长位数  **/
#define Queue_num 10  /**  队列的数目  ***/
typedef RecType DataType;

typedef struct queuenode {
  DataType data;
  struct queuenode *next;
} QueueNode;

typedef struct  {
  QueueNode *front;  /**  队头指针  **/
  QueueNode *rear;   /**  队尾指针  **/
}  LinkQueue;

void InitQueue(LinkQueue *Q)   /**  队列初始化 **/
{Q->front = Q->rear = NULL;
}

int QueueEmpty(LinkQueue *Q)  /** 队的判空  **/
{return (Q->front ? 0 : 1);
}

void EnQueue (LinkQueue *Q,DataType x)   /***   入队  ***/
{QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));
   p->data = x;  p->next = NULL;
   if (QueueEmpty(Q))
      Q->front = Q->rear = p;
   else  {
      Q->rear->next = p;
      Q->rear = p;
   }
}

DataType DeQueue(LinkQueue *Q)  /**  出队  */
{ DataType x;
  QueueNode *p;
  p = Q->front;
  x = p->data;
  Q->front = p->next;
  if (Q->rear == p)
     Q->rear = NULL;
  free(p);
  return x;
}

void Distribute(Sqlist R,LinkQueue B[],int j)
{  /***    对子表进行分配  **/
  int i,k,t;
  j = KeySize - j;
  for (i=1;i<=MAXTEM;i++)  {
    delay(5000);
    k = R[i].Key;
    for (t=1;t<j;t++)  k /= 10;
    k %= 10;
    EnQueue(&B[k],R[i]);
  }
}

void Collect(Sqlist R,LinkQueue B[])   /*  收集子表  */
{  int i=1,j;
  for (j=0;j<Queue_num;j++)
  {  delay(5000);
    while (!QueueEmpty(&B[j]))
      R[i++] = DeQueue(&B[j]);
  }
}

void RadixSort(Sqlist R)    /*  基数排序  */
{  LinkQueue B[Queue_num];
  int i;
  for (i=0;i<Queue_num;i++)
    InitQueue(&B[i]);
  for (i=KeySize-1;i>=0;i--)
   { delay(5000);
     Distribute(R,B,i);
     Collect(R,B);
   }
 Print(R);
}


Print_Time(clock_t start,clock_t end)
{  printf("\nThe time is :%f\n",(double)(end-start)/CLK_TCK);
}



void menu(Sqlist R)
{ int k,n=1,m=MAXTEM;
  clock_t start,end;
  char ch;
 printf("\n\t\t+----------------------------------------+");
 printf("\n\t\t|       1.  Bulle     sort               |");
 printf("\n\t\t|       2.  Insert    sort               |");
 printf("\n\t\t|       3.  Quick     sort               |");
 printf("\n\t\t|       4.  Select    sort               |");
 printf("\n\t\t|       5   Heap      sort               |");
 printf("\n\t\t|       6.  Merge     sort               |");
 printf("\n\t\t|       7.  Radix     sort               |");
 printf("\n\t\t|       0.  exit                         |");
 printf("\n\t\t+----------------------------------------+\n");
 printf("make your choice:");
 scanf("%d",&k);
 do
  {switch(k)
   { case 0:  exit(0);
     case 1: start=clock(); Bullesort(R);     end=clock();  Print_Time(start,end);            break;
     case 2: start=clock(); Insertsort(R);    end=clock();  Print_Time(start,end);            break;
     case 3: start=clock(); Quicksort(R,n,m); end=clock();  Print(R);  Print_Time(start,end); break;
     case 4: start=clock(); Selectsort(R);    end=clock();  Print_Time(start,end);  break;
     case 5: start=clock(); Heapsort(R);      end=clock();  Print(R); Print_Time(start,end);  break;
     case 6: start=clock(); Mergesort(R);     end=clock();  Print(R); Print_Time(start,end);  break;
     case 7: start=clock(); RadixSort(R);     end=clock();  Print_Time(start,end);            break;
     default:printf("ERROR!\n");
    }
	fflush(stdin);
	printf("return?(y/n)\n");
        ch=getchar();
	if(ch=='n'||ch=='N')
        {   printf("make your choice:");
            scanf("%d",&k);
        }
	else break;
    }while(9);
}

main()
{  Sqlist R;
   clrscr();
   CreateSqlist(R);
    menu(R);
}