Huffman Encoding final

//by 吳聲寬 4112064029 電機一

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

void bubble(int*c,int);           //bubble sort int array c
void doHuffman(int*,int,int,int); //Huffman encoding function

char input[100]={0};             
int trueCounter[30]={0};         
int counter[30]={0};             
int compareCounter[30]={30};     
int trueBubbleCounter[30]={30};  
char huff[30][30]={(0,0)};       

int main(){
	int n,alpha=0,endNum;
	scanf("%d",&n);                       //n is how many char in the upcoming input string
	getchar();
	for(int i=0;i<n;i++){
		scanf("%c",&input[i]);            //save the original input string (never change)
		trueCounter[(int)input[i]-'A']++; //save the int form of input (A=0,B=1,...) (never change)
	}
	
	for(int i=0;i<30;i++){
		if(trueCounter[i]!=0){
			counter[alpha]=trueCounter[i];
			alpha++; //alpha = how many value in counter
			/*
				copy trueCounter to counter
				let counter be a changeable trueCounter
			*/
		}
	}
	
	bubble(counter,alpha); //bubblesort counter
	for(int i=0;i<30;i++){
		trueBubbleCounter[i]=counter[i];
		/*
			copy counter to trueBubbleCounter
			never change trueBubbleCounter
		*/
	}
	
	if(alpha==2||alpha==1){
		endNum=1; //endNum = the biggest bit value required for a char using Huffman code
	} else{
		endNum=alpha-1;
	}
	/*
		if there only have 2 kind of char, then max require is 1
		if there is more than 2 kind of char, then max require is [(kind of chars) - 1]
	*/
	
	//array "huff" save all the letters Huffman code idividually
	huff[alpha][endNum-1]='1'; 
	huff[alpha-1][endNum-1]='0';
	//set the last two char's (lowest frquency) last huffman code as 0 and 1
	
	doHuffman(counter,0,alpha,endNum); //Huffman encoding function
	
	for(int i=0;i<alpha;i++){
		for(int j=29;j>=0;j--){
			if(trueCounter[j]==trueBubbleCounter[i]){
				compareCounter[j]=alpha-i;
				trueCounter[j]=0;
				break;
			}
		}
		/*
			setting up compareCounter
			it is an array of pointers to know what letter correspond to what huffman code
			the array address is what letter it is (A=[0],B=[1],...)
			and the stored values is the pointer to huff array
		*/
	}
	
	for(int i=0;i<n;i++){
		printf("%s",huff[compareCounter[(int)input[i]-'A']]);
		/*
			print out the stored huffman code of each value
			for all letters in orignial input
		*/
	}
	
	return 0;
}

void bubble(int *c,int n){   //bubble sort function (explaination in the other final project)
	if(n==1) return;
	int count=0;
	for(int i=0;i<n-1;i++){
		if(c[i]>c[i+1]){
			int tmp=c[i];
			c[i]=c[i+1];
			c[i+1]=tmp;
			count++;
		}
	}
	if(count==0) return;
	bubble(counter,n-1);
}

void doHuffman(int *c,int start,int alpha,int endNum){
	endNum--;                                //the pointer for what bit to fill for huff array
	if(endNum==0) return;
	int sum=c[start]+c[start+1];             //sum = last two char value add together
	if(sum>c[start+2]){
		c[start+1]=c[start+2];
		c[start+2]=sum;
		huff[alpha-start-2][endNum-1]='1';
		for(int i=0;i<start+2;i++){
			huff[alpha-i][endNum-1]='0';
		}
		/*
			if the sum is larger than the next char value, rearrange the values
			then we know the new char will need to add '1' in huffman code
			and the other old chars will need to add '0' in huffman code
		*/
	} else{
		c[start+1]=sum;
		huff[alpha-start-2][endNum-1]='0';
		for(int i=0;i<start+2;i++){
			huff[alpha-i][endNum-1]='1';
		}
		/*
			if the sum is smaller or equal, no movement
			then we know the new char will need to add '0' in huffman code
			and the other old chars will need to add '1' in huffman code
		*/
	}
	start++;   //pointer for moving in huff array
	doHuffman(c,start,alpha,endNum); //recursion
}