ln23.c

有关数据结构的一些例子。用C语言编写的。非常有价值的程序。对初学者有指导借鉴意义。

#define NULL 0
#define n 7
#include "stdio.h"
typedef int datatype;
typedef struct
{ int key;
  datatype other;
} rectype;
rectype T[n];
int S1=1,T1=n;

INSORT(R)             /*直接排序*/
rectype R[];
{ int i,j;
  for(i=2;i<n;i++)
   { R[0]=R[i];
     j=i-1;
     while(R[0].key<R[j].key)
       R[j+1]=R[j--];
       R[j+1]=R[0];
   }
}

BUBSORT(R)           /*起泡排序*/
rectype R[];
{ int i,j,noswap;
  rectype temp;
  for(i=1;i<n;i++)
   { noswap=1;
     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;
	   noswap=0;
	 }
     if(noswap)
       break;
   }
}

int PARTION(R,l,h)   /*快速排序*/
rectype R[];
int l,h;
{ int i,j;
  rectype temp;
  i=l;  j=h;  temp=R[i];
  do
   { while((R[j].key>=temp.key) && (i<j))
       j--;
       if(i<j)
	 R[i++]=R[j];
     while((R[i].key<=temp.key) && (i<j))
       i++;
       if(i<j)
	 R[j--]=R[i];
   } while(i!=j);
  R[i]=temp;
  return(i);
}

QUISORT(R,s1,t1)
rectype R[];
int s1,t1;
{ int i;
  if(s1<t1)
   { i=PARTION(R,s1,t1);
     QUISORT(R,s1,i-1);
     QUISORT(R,i+1,t1);
   }
}

main()
{ int i,x;
  printf("\n请输入待排序的元素:\n");
  for(i=1;i<n;i++)
   { scanf("%d",&x);
     T[i].key=x;
   }
  printf("排序前的元素顺序为:\n");
  for(i=1;i<n;i++)
    printf("%d\t",T[i].key);
  printf("\n直接排序后的元素顺序为:\n");
  INSORT(T);
  for(i=1;i<n;i++)
    printf("%d\t",T[i].key);
  printf("\n起泡排序后的元素顺序为:\n");
  BUBSORT(T);
  for(i=2;i<n+1;i++)
    printf("%d\t",T[i].key);
  printf("\n快速排序后的元素顺序为:\n");
  QUISORT(T,S1,T1);
  for(i=2;i<n+1;i++)
    printf("%d\t",T[i].key);
  printf("\n");
}