归并算法.txt

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

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

#define LQ(a,b)  ((a)<=(b))
typedef char type;//归并算法


void merge(type sr[],type tr[],int i,int m,int n){
    
    int j,k,h;


	for(j=m+1,k=i;i<=m&&j<=n;++k){
	  if(LQ(sr[i],sr[j]))tr[k]=sr[i++];
	  else tr[k]=sr[j++];
	}
    if(i<=m){
	      for(h=i;h<=m;h++)
			  tr[k++]=sr[h];	
	}
	else 
    	   for(h=j;h<=n;h++)
		      tr[k++]=sr[h];
}


void msort(type sr[],type tr1[],int s,int t){
  char tr2[127];
  int m;
  if(s==t)tr1[s]=sr[s];
  else{
       m=(s+t)/2;
       msort(sr,tr2,s,m);
	   msort(sr,tr2,m+1,t);
	   merge(tr2,tr1,s,m,t); //将tr2[s...m]和tr2[m+1,t]归并到tr1[s...t]
  }
}


main(){
  
 int n;
 FILE *fp,*fpp;
 type str[127];

 if((fp=fopen("g:\\yt\\input01.txt","r"))==NULL){
	 printf("file open error!\n");
     exit(1);
 }
 if((fpp=fopen("g:\\yt\\output01.txt","w"))==NULL){
	 printf("file open error!\n");
     exit(2);
 }
 while(!feof(fp)){
	 fscanf(fp,"%s",str);
	 n=strlen(str);
	 msort(str,str,0,n-1);
	 fprintf(fpp,"%s\n",str);
	 printf("%s\n",str);
 }
}