數(shù)據(jù)結構課程設計--哈夫曼編碼問題的設計和實現(xiàn)-資料下載頁
2025-06-06 01:27本頁面
【正文】 建立葉結點個數(shù)為 n，權值數(shù)組為 weight 的哈夫曼樹 haffTree*/ { int i,j,m1,m2,x1,x2。 for(i=0。i2*n1。i++) { if(in) haffTree[i].weight=weight[i]。 else haffTree[i].weight=0。 haffTree[i].parent=0。 haffTree[i].flag=0。 haffTree[i].leftChild=1。 haffTree[i].rightChild=1。 } /*構造哈夫曼樹 haffTree 的 n1 個非葉結點 */ for(i=0。in1。i++) { m1=m2=MaxValue。 x1=x2=0。 for(j=0。jn+i。j++) { if(haffTree[j].weightm1amp。amp。haffTree[j].flag==0) { m2=m1。 x2=x1。 m1=haffTree[j].weight。 x1=j。 } else 15 if(haffTree[j].weightm2amp。amp。haffTree[j].flag==0) { m2=haffTree[j].weight。 x2=j。 } } /*將找出的兩顆權值最小的子樹合并為一棵子樹 */ haffTree[x1].parent=n+i。 haffTree[x2].parent=n+i。 haffTree[x1].flag=1。 haffTree[x2].flag=1。 haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight。 haffTree[n+i].leftChild=x1。 haffTree[n+i].rightChild=x2。 } } void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*由 n個結點的哈夫曼樹 haffTree 構造哈夫曼編碼 haffCode*/ { Code *cd=(Code *)malloc(sizeof(Code))。 int i,j,child,parent。 /*求 n個結點的哈夫曼編碼 */ for(i=0。in。i++) { cdstart=n1。 cdweight=haffTree[i].weight。 child=i。 parent=haffTree[child].parent。 /*由葉結點向上直到根結點 */ while(parent!=0) { if(haffTree[parent].leftChild==child) cdbit[cdstart]=0。 /*左孩子分支編碼 0*/ else cdbit[cdstart]=1。 /*左孩子分支編碼 1*/ cdstart。 child=parent。 parent=haffTree[child].parent。 } for(j=cdstart+1。jn。j++) haffCode[i].bit[j]=cdbit[j]。 /*保存每個葉結點的編碼 */ haffCode[i].start=cdstart。 /*保存不等長編碼的起始位置 */ haffCode[i].weight=cdweight。 /*保存相應字符的權值 */ } 16 } int count(char * s,int * weight,int n) { int i,j,temp,k=0,p。 for(i=0。inamp。amp。s[i]!=39。\039。i++) { temp=1。 for(j=0。jn。j++) { if(s[j]==s[i]amp。amp。i!=j) { temp++。 for(p=j。pn。p++) s[p]=s[p+1]。 n。 j。 } } weight[k++]=temp。 } return i。 } void main() { int i,j,n。 int weight[16]。 char s[30]。 HaffNode *myHaffTree。 Code *myHaffCode。 printf( ************輸入字符串 ************\n)。 gets(s)。 n=count(s,weight,30)。 17 myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*n+1))。 myHaffCode=(Code*)malloc(sizeof(Code)*n)。 if(nMaxN) { printf(給出的 n越界，修改 MaxN!\n)。 exit(1)。 } Haffman(weight,n,myHaffTree)。 HaffmanCode(myHaffTree,n,myHaffCode)。 /*輸出每個葉結點的哈夫曼編碼 */ for(i=0。in。i++) { printf( W=%d C= ,myHaffCode[i].weight)。 for(j=myHaffCode[i].start+1。jn。j++) printf(%d,myHaffCode[i].bit[j])。 printf(\n)。 } }
畢業(yè)設計相關推薦
鄂ICP備17016276號-1