60.txt

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

#include <math.h>
#define maxsize 1000
#define sortnum 6
typedef void(*func)(long c,long s);
static func sorts[sortnum]=
  {bubble ,insertsort,selectsort,quicksort,shellsort,heapsort};
static char *sortnames[sortnum]={"bubbl","insert","selec","quick","shell","heap"};
typdef int datatype[maxsize+2];
datatype data;
  
datatype data2;
int size;
long co;
long sh;

int a[maxsize],b[maxsize],c[maxsize];


for(i=0;i<maxsize;i++)
a[i]=i;

for(i=0;i<maxsize;i++)
b[i]=maxsize-i+1;


for(i=0;i<maxsize;i++)
c[i]=ran();





void beforesort(){
co=sh=0;
}




less(int i,int j){
co++;
return data[i]<data[j];
}



swap(int i,int j)
{data[i]<->data[j];
 sh=sh+3;
 }



shift(int i,int j)
{data[j]=data[i];
sh++;
}


  
copy(datatype data1,datatype & data2)
{for(i=1;i<size;i++)
  data2[i]i=data[i];
}







inverseorder()
{for(i=1;i<=size;i++)data[i]=data2[i]=size-i+1;
}






initlist()
{if(n<1)size=0;
 else{
     if(n>max)n=max;
     for(i=1;i<=n;i++)data2[i]=data[i]=i;
     size=n;}

copy(data,data2);

copy(data2,data);



bubblesort()
{
before();
 do{
     swapped=false;
     for(i=1;i<=size-1;i++)
     if(less(i+1,i)){swap(i+1,i);swapped=true;
}}while(swapped);
 c=co;s=sh;
}



insertsort()
 {before();
  for(i=2;i<=size;i++){
  shift(i,0);j=i-1;
  while(less(0,j)){shift(j,j+1);j--;}
 shift(0,j+1);
}
c=co;s=sh;
 }
  


selectsort()
{before();
 for(i=1;i<=size-1;i++){
min=i;
for(j=i+1;j<=size;j++)
  if(less(j,min))min=j;
 }
 c=co;s=sh;
}





qsort(lo,hi)
{if(lo<hi){
i=lo;j=hi;m=(lo+hi)/2;
 do{
   while(less(i,m))i++;
    while(less(m,j))j--;
   if(i<=j){
      if(m==i)m=j;
       else if(m==j)m=i;
      swap(i,j);i++;j--;
}
}while(i<=j);
  qsort(lo,j);qsort(i,hi);
}
}


quicksort(){
 before();
 qsort(l,size);
 c=co;s=sh;
}




shellsort()
{ before();
  i=4;h=l;
  while(i<=size){i=i*2;h=2*h+1;
}
while(h!=0){
 j=i-h;
  while(i<=size){
while(j>0&&less(j+h,j)){swap(j,j+h);j=j-h;
}
i++;}
h=(h-1)/2;}
 c=co;s=sh;
}


siftsort( left,right)
{i=left;j=2*i;shift(left,0);finished=false;
shift(left,max+1);
while(j<=right&&!finished){
if(j=right&&less(j+i,j))j=j+1;
if(!less(j,0))finish=true;
else(shift(j,i);i=j;j=2*i;)}
shift(max+1,i);
}





heapsort()
{before();
 for(left=size/2;left>=1;left--)siftsort(left,size);
for(right=size;right>=2;right--)
{swap(l,right);siftsort(1,right-1);}
c=co;s=sh;
}

void readcomand(char &cmd)
  {do{cmd=getchar();}while(cmd!='1'||cmd!='2'||cmd!='3'||cmd!='q'||cmd!='Q');}
void interpret(char cmd)
{switch(cmd){
  case '1':
  for(i=1;i<size;i++)
  data2[i]=data[i];

  for(j=0;j<sortnum;j++)

  { for(i=1;i<size;i++)
  data[i]=data2[i];
   (*sorts[j])(c,s);
    printf( "%6ld",c);
    printf( "%6ld",s);}
    break;
case'2':
        scanf("%d",n);
	if(n<100)n=100;
	if(n>1000)n=1000;
	initlist(n);
	break;
case'3':
	scanf("%d",groups);
	if(groups<mingroups)groups=mingroups;
	if(groups>maxgroups)groups=maxgroups;


void main()
{
do {
   readcommand(cmd);
   interpret(char cmd);}
  while(cmd!='q'&&cmd!='Q');
  }