Huffman Encoding final
user_8306938
csharp
a year ago
3.8 kB
6
Indexable
//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 }
Editor is loading...
Leave a Comment