习题7-排序综合练习.c

数据结构各章实验源代码； 数据结构实验源代码

#include  <stdio.h>
#include  "datastru.h"

int createList(RECNODE  *r)
{ int j, k;

 printf("\n\n输入待排序数据(整数，以空格隔开，0 结束) : "); k = 0; scanf("%d",&j);
 while(j != 0) { k++; r[k].key = j; scanf("%d",&j); }
 return k;
}

frontdisplayList(RECNODE *r, int n)
{int i;

 printf("\n排序前 : ");
 for (i = 0; i < n; i++)   printf("  %d",r[i+1].key);
 printf("\n\n");
}

reardisplayList(RECNODE *r, int n)
{int i;

 printf("\n\n排序后 : ");
 for (i = 0; i < n; i++)   printf("  %d",r[i+1].key);
 printf("\n\n");
}

void insertsort(RECNODE *r, int n)
{/*直接插入排序*/
	int i,j;

	for(i = 2; i <= n; i++)
	  { r[0] = r[i];   j = i - 1;     /*r[0]是监视哨，j表示当前已排好序列的长度*/
	    while(r[0].key < r[j].key)    /*确定插入位置*/
	       {r[j + 1] = r[j];   j--;}
	    r[j + 1] = r[0];              /*元素插入*/
	  }
}

void bublesort(RECNODE *r, int n)
{/*简单交换排序:冒泡排序*/
	int i, j;
	RECNODE temp;
	for(i = 1; i < n; i++)
	  for(j = n - 1; j >= i; j--)
		if(r[j + 1].key < r[j].key)
		  {temp = r[j + 1];  r[j + 1] = r[j];  r[j] = temp;}
}

int partition(RECNODE *r, int *low, int *high)
{/*一趟快速排序,返回i,产生了两个独立的待排子序列*/
	int i, j;
	RECNODE	 temp;

	i = *low;  j = *high;
	temp = r[i];                                         /*枢轴记录保存在temp变量中*/
	do{ while((r[j].key >= temp.key) && (i < j))  j--;   /*j指针记录和枢轴记录比较*/
	    if(i < j)    { r[i] = r[j];   i++;}
	   while((r[i].key <= temp.key) && (i < j))   i++;   /*i指针记录和枢轴记录比较*/
	   if(i < j)     { r[j] = r[i];   j--;}
          }while(i != j);
	r[i] = temp;                                         /*枢轴记录的排序位置确定在i*/
	return i;
}

void quicksort(RECNODE *r, int start, int end)
{/*快速排序*/
	int i;
	if(start < end)
	   { i = partition(r, &start, &end);  /*一趟快速排序,返回i,产生了两个独立的待排子序列*/
	     quicksort(r, start, i - 1);      /*对两个独立的待排子序列分别递归调用快速排序算法*/
	     quicksort(r, i + 1,end);}
}

void selesort(RECNODE *r, int n)
{/*简单选择排序*/
	int i,j,k;
	RECNODE temp;

	for(i = 1; i < n; i++)
	  { k = i;                       /*k:最小关键字的初始位置*/
	    for(j = i + 1; j <= n; j++)
	      if(r[j].key < r[k].key)
		 k = j;                  /*k:跟踪记录当前最小关键字的位置*/
	    if(k != i)                   /*最小关键字元素和待排序列的第一个元素交换*/
	      {temp = r[i];   r[i] = r[k];   r[k] = temp;}
	  }
}

void sift(RECNODE *r, int i, int m)
{/*i是根结点编号,m是以i结点为根的子树中最后一个结点的编号*/
	int j;
	RECNODE temp;

	temp = r[i];
	j = 2 * i;       /*j为i根结点的左孩子*/
	while(j <= m)
	  {if(j < m && (r[j].key < r[j + 1].key))
	    j++;                                  /*当i结点有左右孩子时,j取关键字大的孩子结点编号*/
	   if(temp.key < r[j].key)
	     { r[i] = r[j];   i = j;   j = 2 * i;}/*按堆定义调整,并向下一层筛选调整 */
	   else   break;                          /*筛选调整完成,跳出循环 */
	  }
	r[i] = temp;
}

void heapsort(RECNODE *r, int n)
{/*堆排序: n为r表中记录数,从r[1]开始放起*/
	int i;
	RECNODE temp;

	for(i = n/2; i >= 1; i--)
	  sift(r, i, n);             /*将无序序列建成大堆*/
	for(i = n; i >= 2; i--)
	  {temp = r[1];              /*堆顶及堆尾元素交换*/
	   r[1] = r[i];
	   r[i] = temp;
	   sift(r,1,i - 1);          /*交换后,从第一个元素开始调整为大堆,每次记录个数少一个*/
	  }         
}

void merge(RECNODE *r, int low, int m, int high)
{/*两相邻的有序表(一个从low到m;另一个从m+1到high)合并为一个有序表(从low到high)*/
 	RECNODE  r1[MAXSIZE];             /*合并时用的缓冲向量*/
	int i, j, k;

	i = low;
	j = m + 1;
	k = 0;
	while(i <= m && j <= high)              /*两相邻的有序表合并*/
	  if(r[i].key <= r[j].key)
	    {r1[k] = r[i];  i++;  k++;}
	  else
	    {r1[k] = r[j];  j++;  k++;}
	while(i <= m)                           /*有序表剩余部分处理*/
	   {r1[k] = r[i];  i++;  k++;}
	while(j <= high)                        //有序表剩余部分处理
	   {r1[k] = r[j];  j++;  k++;}
	for(i = low, k = 0; i <= high; i++, k++)/*缓冲向量r1复制到原来的r中*/
	   r[i] = r1[k];

}

void merge_one(RECNODE *r, int lenth, int n)
{/*二路归并中的"一趟归并"算法*/
	int i = 0;

	while(i + 2 * lenth - 1 < n)
	  {merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*两子序列长度相等的*/
	   i = i + 2 * lenth;}                           /*情况下调用merge*/
	if(i + lenth - 1 < n - 1)
	   merge(r, i, i + lenth - 1, n - 1);            /*序列中的余留部分处理*/
}

void mergesort(RECNODE *r, int n)
{/*二路归并排序算法*/
	int lenth = 1;                 /*有序子序列长度初始值 = 1*/

	while(lenth < n)
	  {merge_one(r, lenth, n);     /*调用"一趟归并"的算法*/
	   lenth = 2 * lenth;}         /*有序子序列长度加倍*/
}

void main() {
	RECNODE  a[MAXSIZE];
	int len, b, j, k;
	int loop = 1;
	
	while (loop) {
	printf("\n\n排序综合练习\n\n");
	printf("  0 -- 退出\n");
	printf("  1 -- 直接插入排序\n");
	printf("  2 -- 简单交换(冒泡)排序\n");
	printf("  3 -- 快速排序\n");
	printf("  4 -- 简单选择排序\n");
	printf("  5 -- 堆排序\n");
	printf("  6 -- 二路归并排序\n");
	printf("\n\n  请选择项号 ： ");
	scanf("%d",&b);
	printf("\n\n");
	if(b >= 0 && b <= 6) 
		switch(b) {
			case 0: loop = 0;
			        break;
			case 1: len = createList(a);
				frontdisplayList(a,len);
				insertsort(a,len);
				reardisplayList(a,len);
				break;
			case 2: len = createList(a);
				frontdisplayList(a,len);
				bublesort(a, len);
				reardisplayList(a,len);
				break;
			case 3: len = createList(a);
				frontdisplayList(a,len);
				quicksort(a, 1, len);
				reardisplayList(a,len);
				break;
			case 4: len = createList(a);
				frontdisplayList(a,len);
				selesort(a, len);
				reardisplayList(a,len);
				break;
			case 5: len = createList(a);
				frontdisplayList(a,len);
				heapsort(a, len);
				reardisplayList(a,len);
				break;
			case 6:  printf("\n\n输入待排序数据(整数，以空格隔开，0 结束) : "); k = 0; scanf("%d",&j);
                while(j != 0) { k++; a[k-1].key = j; scanf("%d",&j); }
			    len = k;
                printf("\n排序前 : ");
                for (j = 0; j < len; j++)   printf("  %d",a[j].key);
                printf("\n\n");
                mergesort(a, len);
                printf("\n\n排序后 : ");
                for (j = 0; j < len; j++)   printf("  %d",a[j].key);
                printf("\n\n");
				break;
		}
	printf("\n\n结束此练习吗? (0 -- 结束 1 -- 继续) : ");
	scanf("%d",&loop);
	printf("\n\n");
	}
}