121.c

数据结构168个实验程序,很全面

#define MAXSIZE 30
#define OVERFLOW -1
#include "stdio.h"
#include "stdlib.h"
 typedef struct {
                     int low;
                     int high;
                   } boundary; //子序列的上下界类型
 typedef struct
 {
	 int r[MAXSIZE+1];
	 int length;
 }SQList;
 int InitStack(boundary * s)
{ 
	 s=(boundary *)malloc(100*sizeof(boundary));
	 if (!s) exit(OVERFLOW);
}
 int StackEmpty(boundary * S)
 {
	if (S->high-S->low==0) return(1);
	else return(0);
 }

 int Partition(SQList L,int low,int high)//一趟划分的算法,与书上相同
{
	 int pivotkey;
	 L.r[0]=L.r[low];
	 pivotkey=L.r[low];
  while(low<high)
  {
    while(low<high&&L.r[high]>=pivotkey)
      high--;
    L.r[low]=L.r[high];
    while(low<high&&L.r[low]<=pivotkey)
      low++;
    L.r[high]=L.r[low];
  }//while
  L.r[low]=L.r[0];
  return low;
}//Partition 
 void Easy_Sort(SQList L,int low,int high)//对长度小于3的子序列进行比较排序
{
	int temp;
	if(high-low==1) //子序列只含两个元素
    if(L.r[low]>L.r[high]) 
	{
		temp=L.r[low];
		L.r[low]=L.r[high];
		L.r[high]=temp;
	}
  else //子序列含有三个元素
  {
    if(L.r[low]>L.r[low+1]) 
	{
		temp=L.r[low];
		L.r[low]=L.r[low+1];
		L.r[low+1]=temp;
	}
    if(L.r[low+1]>L.r[high]) 
	{
		temp=L.r[low+1];
		L.r[low+1]=L.r[high];
		L.r[high]=temp;
	}
    if(L.r[low]>L.r[low+1])
	{
		temp=L.r[low];
		L.r[low]=L.r[low+1];
		L.r[low+1]=temp;
	}
  }
}//Easy_Sort 
 void QSort_NotRecurve(SQList L)//快速排序的非递归算法
 {
	int low,high,pivot;
	boundary * S,a;
	low=1;high=L.length;
	InitStack(S); //S的元素为boundary类型
	while(low<high&&!StackEmpty(S)) //注意排序结束的条件
	{
    if(high-low>2) //如果当前子序列长度大于3且尚未排好序
    {
      pivot=Partition(L,low,high); //进行一趟划分
      if(high-pivot>pivot-low)
      {
        Push(S,{pivot+1,high}); //把长的子序列边界入栈
        high=pivot-1; //短的子序列留待下次排序
      }
      else
      {
        Push(S,{low,pivot-1});
        low=pivot+1;
      }
    }//if
    else if(low<high&&high-low<3)//如果当前子序列长度小于3且尚未排好序
    {
      Easy_Sort(L,low,high); //直接进行比较排序
      low=high; //当前子序列标志为已排好序
    }
    else //如果当前子序列已排好序但栈中还有未排序的子序列
    {
      Pop(S,a); //从栈中取出一个子序列
      low=a.low;
      high=a.high;
    }
  }//while
}//QSort_NotRecurve 

 void main()
 {
	 SQList L;
	 int i;
	 printf("输入多少数据:");
	 scanf("%d",&L.length);
	 printf("输入数据:\n");
	 for(i=1;i<=L.length;i++)
		scanf("%d",&L.r[i]);
	 QSort_NotRecurve(L);
	 printf("%d",L.length);
 
 }