堆排序.txt

中过科学技术大学历年复试机试题

#include<stdio.h>
#include<stdlib.h>
#include<string>

#define LT(a,b) ((a)<(b))//堆排序


void heapadjust(char str[],int s,int m){
  char rc;
  int j;
  rc=str[s];
  for(j=2*s;j<=m;j*=2){
     if(j<m&&LT(str[j],str[j+1]))++j;
	 if(!LT(rc,str[j]))break;
	 str[s]=str[j];
	 s=j;
  }
  str[s]=rc;
}

void heapsort(char str[]){
  int i,n;
  char ch;
  
  n=strlen(str);
  i=(n-1)/2;
  for(;i>=0;i--)
    heapadjust(str,i,n-1);
  
  for(i=n-1;i>0;--i){
    ch=str[i];
	str[i]=str[0];
	str[0]=ch;
	heapadjust(str,0,i-1);
  }
}

main(){
  FILE *fp,*fpp;
  if((fp=fopen("g:\\yt\\input01.txt","r"))==NULL){
      printf("input file open error!\n");
      exit(0);
  }
  if((fpp=fopen("g:\\yt\\output01.txt","w"))==NULL){
      printf("output file open error!\n");
      exit(1);
  }
  char str[127];
  while(!feof(fp)){
      fscanf(fp,"%s",str);
	  printf("%s\n",str);
	  
	  heapsort(str);
	  
	  fprintf(fpp,"%s\n",str);
	  printf("%s\n",str);
  }
}