heapsort.cpp

这个是编译原理课程的词法分析器

#include <stdio.h>
#include <conio.h>
#define N 6
int k,j;

/* 
 * 建堆函数 
 */
void buildHeap(int *a,int i,int n){
	int tmp;
	k=i;
	j=2*k+1;
	while(j<=n){
		if(j<n && a[j]<a[j+1])
			j++;
		if(a[k]>=a[j])
			break;
		tmp=a[k];
		a[k]=a[j];
		a[j]=tmp;        
		k=j;
		j=2*j+1;
	}
}

/* 
 * 打印数组函数 
 */
void output(int *a,int n){
	int i;
	printf("\n");
	for(i=0;i<n;i++){
		printf("%3d",a[i]);
	}
	printf("\n");
}

/* 
 * 打印堆函数 
 */
void outputHeap(int *a,int b1,int b2){
	int size;
	int h=0,sum=0,item=1;
	int i,j,cnt,start,tmp;
	size=b2-b1+1;
	while(sum<=size){
		sum+=item;
		h++;
		item*=2;
	}
	item=1;
	cnt=0;
	start=b1;
	tmp=1;
	printf("\n----------------------------------\n");    
	printf("堆： ");
	while(1){
		for(i=0;i<h;i++){
			for(j=0;j<h-i;j++)
				printf("   ");
			for(j=0;j<i+1;j++)
				printf(" "); 
			for(j=0;j<tmp;j++){
				if(cnt>size-1)
					goto end;
				printf("%4d",a[cnt++]);
			}
			printf("\n");
			tmp*=2;
		}       
	}
	end:
	printf("\n");         
	return;                  
}

/* 
 * 打印已排序数组函数 
 */
void printArray(int *a,int b2,int len){
	int i; 
	printf("  已排序：\n");
  for(i=0;i<b2;i++){
		printf("   ");
  }          
  for(i=b2;i<=len;i++){
    printf("%3d",a[i]);
  }          
  printf("\n");
} 

/* 
 * 主函数 
 */
void main(){
	/* int a[]={-1,2,5,1,0,-3,-2,8,6}; */
	int a[50];
	int i;
	int tmp;
	int sum;    
	int len;
	printf("            堆排序\n");
	printf("\n==================================\n");    
	printf("\n输入待排序数组个数：\n");
	scanf("%3d",&len);    
	printf("\n输入待排序数组：\n");
	for(i=0;i<len;i++)
		scanf("%3d",&a[i]);        
	tmp=1;sum=0;
	while(sum+tmp<=len){
		sum+=tmp;    
		tmp*=2;
	}
	printf("\n==================================\n");    
	printf("\n  初始数组：            \n");    
	output(a,len);    
	/* 建初始堆 */
	for(i=sum-1;i>=0;i--)
		buildHeap(a,i,len-1);       
	outputHeap(a,0,len-1);      
	/* 改建堆 */
	for(i=0;i<len-1;i++){
		tmp=a[0];
		a[0]=a[len-1-i];
		a[len-1-i]=tmp;
		buildHeap(a,0,len-2-i);
		outputHeap(a,0,len-2-i);
		printArray(a,len-1-i,len-1);        
	}
	printf("\n----------------------------------\n");
	printf("\n  排序结果：\n");        
	output(a,len);
	printf("\n==================================\n\n");  
	getch();
}