信息论课程设计报告(3)

{ tag = 0; break; } if (tag) { CW[++*p].c = ch[i]; CW[*p].weight = 1; for (k = i + 1; ch[k] != '\\0'; k++) if (ch[i] == ch[k]) CW[*p].weight++;//权值累加 } } *s = i;//字符串长度 }

/********创建HuffmanTree********/

void CreateHuffmanTree(Huffman ht, WeightNode w, int n) { int i, j; int s1, s2; //初始化哈夫曼树 for (i = 1; i <= n; i++) { ht[i].weight = w[i].weight; ht[i].parent = 0; ht[i].LChild = 0; ht[i].RChild = 0; } for (i = n + 1; i <= 2 * n - 1; i++) { ht[i].weight = 0; ht[i].parent = 0; ht[i].LChild = 0; ht[i].RChild = 0; } for (i = n + 1; i <= 2 * n - 1; i++) { for (j = 1; j <= i - 1; j++) if (!ht[j].parent) break; s1 = j; //找到第一个双亲为零的结点 for (; j <= i - 1; j++) if (!ht[j].parent) s1 = ht[s1].weight>ht[j].weight ? j : s1;

ht[s1].parent = i; ht[i].LChild = s1; for (j = 1; j <= i - 1; j++) if (!ht[j].parent) break; s2 = j; //找到第二个双亲为零的结点 for (; j <= i - 1; j++) if (!ht[j].parent) s2 = ht[s2].weight>ht[j].weight ? j : s2; ht[s2].parent = i; ht[i].RChild = s2; ht[i].weight = ht[s1].weight + ht[s2].weight;//权值累加 } }

/***********叶子结点的编码***********/

void CrtHuffmanNodeCode(Huffman ht, char ch[], HuffmanCode h, WeightNode weight, int m, int n) { int i, c, p, start; char *cd; cd = (char *)malloc(n*sizeof(char)); cd[n - 1] = '\\0';//末尾置0 for (i = 1; i <= n; i++) { start = n - 1; //cd串每次从末尾开始 c = i; p = ht[i].parent;//p在n+1至2n-1 while (p) //沿父亲方向遍历,直到为0 { start--;//依次向前置值 if (ht[p].LChild == c)//与左子相同,置0 cd[start] = '0'; else//否则置1 cd[start] = '1'; c = p; p = ht[p].parent; } weight[i].num = n - start; //二进制码的长度(包含末尾0) h[i] = (char *)malloc((n - start)*sizeof(char)); strcpy(h[i], &cd[start]);//将二进制字符串拷贝到指针数组h中 } free(cd);//释放cd内存 system(\); }

/*********所有字符的编码*********/

void CrtHuffmanCode(char ch[], HuffmanCode h, HuffmanCode hc, WeightNode weight, int n, int m) { int i, k; for (i = 0; i

/*****解码*****/

void TrsHuffmanTree(Huffman ht, WeightNode w, HuffmanCode hc, int n, int m) { int i = 0, j, p; while (i

/*****释放huffman编码内存*****/

void FreeHuffmanCode(HuffmanCode h, HuffmanCode hc, int n, int m) { int i; for (i = 1; i <= n; i++)//释放叶子结点的编码 free(h[i]); for (i = 0; i

int n; /*n为叶子结点的个数*/

*/

int m; /*m为字符串ch[]的长度*/ Huffman ht; /*Huffman二叉数*/

HuffmanCode h, hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/ WeightNode weight; /*存放叶子结点的信息*/ void huffmanbm(char *ch) { n = 0; int i; m = 0; printf(\); CreateWeight(ch, &m, weight, &n); /*产生叶子结点信息，m为字符串ch[]的长度 printf(\); for (i = 1; i <= n; i++) //输出叶子结点的字符与权值 printf(\, weight[i].c); printf(\); for (i = 1; i <= n; i++) printf(\, weight[i].weight); CreateHuffmanTree(ht, weight, n); /*产生Huffman树*/ printf(\); printf(\); for (i = 1; i <= 2 * n - 1; i++) //打印Huffman树的信息 printf(\, i, ht[i].weight, ht[i].parent, ht[i].LChild, ht[i].RChild); CrtHuffmanNodeCode(ht, ch, h, weight, m, n); /*叶子结点的编码*/ printf(\); /*打印叶子结点的编码*/ for (i = 1; i <= n; i++) { printf(\, weight[i].c); printf(\, h[i]); } CrtHuffmanCode(ch, h, hc, weight, n, m); /*所有字符的编码*/ printf(\编码后\); /*打印字符串的编码*/ for (i = 0; i < m; i++) { printf(\, hc[i]); strcpy(&y[i], hc[i]); } system(\); }

void huffmanyima() { printf(\译码后：\); TrsHuffmanTree(ht, weight, hc, n, m); /*解码*/

FreeHuffmanCode(h, hc, n, m); system(\); }

int main() { char s[100]; if (!in.is_open()) { cout <<\; exit(1); } while (!in.eof()) { in.getline(s, 100); cout << s << endl; youchengbianma(s); out <<\游程编码后：\<< x << endl; huffmanbm(x); out <<\编码后：\<< y << endl; out <<\译码后：\; huffmanyima(); youchengyima(x); } in.close(); out.close(); return 0;

}

4. 运行结果

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库信息论课程设计报告(3)在线全文阅读。