------ 赫夫曼樹和赫夫曼編碼的存儲表示------ [cpp] typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char ** HuffmanCode; void HuffmanCoding(HuffmanTree& HT,HuffmanCode & HC,int *w,int n) { if (n < 1) return;\ int m = 2* n + 1; HT = (HuffmanTree) malloc (m+1)* sizeof(HTNode); //0 號單元未用 for ( HuffmanTree p = HT; i=1; i<=n; ++i; ++p; ++w) *p = {*w,0,0,0,0}; for(; i<=m; ++i; ++p) *p = {0,0,0,0}; for(i = n+1; i<=m; i++) { //建立HuffmanTree Select(HT,i-1,s1,s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } HC = (HuffmanCode)malloc((n+1)* sizeof(char*)); cd = (char*) malloc(n* sizeof(char)); cd [n-1] = "\0"; for ( i=1; i<=n; i++) { int start = n-1; for ( c=i, f = HT[i].parent; f!=0; c=f; f = HT[f].parent ) if( HT[f].lchild == c ) cd [--start] = "0"; else cd [--start] = "1"; HC[i] = (char*) malloc ( (n-start)* sizeof(char)); strcyp(HC[i],&cd[start]); } free(cd); } ------ 無棧非遞歸遍歷赫夫曼樹，求赫夫曼編碼------ [cpp] HC = (HuffmanCode) malloc ( (n+1) * sizeof(char*)); int p = m, cdlen = 0; for ( int i=1; i<=m; ++i) HT[i].weight = 0; while(p) { if ( HT[p].weight == 0 ) { HT[p].weight = 1; if ( HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] = "0"; }else if ( HT[p].lchild == 0) { HC[p] = (char*) malloc ((cdlen+1) * sizeof(char)); cd[cdlen] = "\0"; www.2cto.com strcpy(HC[p],cd); } }else if ( HP[p].weight == 1) { HT[p].weight = 2; if ( HT[p].rchild != 0) { p = HT[p].rchild; cd [cdlen++] = "1"; }else { HT[p].weight = 0; p = HT[p].parent; --cdlen; } } }
