信息论课程设计报告Word格式.docx

1、这样，首先获得的是由最短码字能引起的所有尾随后缀。 接着，按照上述步骤将次短的码字、.所有码字可能产生的尾随后缀前部 列出。由此得到由码C的所有可能的尾随后缀组成的集合F。 参考算法伪代码：For all do if 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中End ifEnd forLoopFor all doElse if 是的前缀 thenEnd for If thenReturn falseElse if F 中未出现新的元素 thenReturn true/能走到这里，说明F中有新的元素出现，需继续 End loop3. 实现源码 #includefstreamstdi

2、o.hstring.h using namespace std; #pragma warning（disable:4996） char c10050; /保存码字 char f30050; /保存尾随后缀 int N, sum = 0; /N为码字的个数，sum为尾随后缀个数 int flag; /判断是否唯一可译标志位 /检测尾随后缀 void patterson（char c, char d） int i, j, k; for （i = 0; i+） If （ci = 0&di = ）/两字符串一样长，跳出 break; if （ci = ） /d比c长，将d的尾随后缀放入f中 for （

3、j = i; dj != j+） fsumj - i = dj; fsumj - i = for （k = 0; ksum; k+） if （strcmp（fsum, fk） = 0） /*查看当前生成的尾随后缀在f集合中 是否存在*/ sum-; break; sum+; if （di = ） /c比d长，将c的尾随后缀放入f中 cj ! fsumj - i = cj; if （strcmp（fsum, fk） = 0） /*查看当前生成的尾随后缀在f集合中 sum-; if （ci != di）/字符不一样了也退出（前缀不同） void main（） int k = 0, N = 0, m

4、 = 0, a50, z = 0; am = N; m+; fstream file1; file1.open（out1.txt）; /码字读取 FILE *file; file = fopen（in1.txt, r+ int num = fgetc（file） - 48; for （int n = 0; n num; n+） int i = 0, j; if （fgetc（file） = ） N += （fgetc（file） - 48）; else N += （fgetc（file） - 48）; am = N; fgetc（file）; for （k; k N; k+） for （int

5、 q = 0; q+） char temp = fgetc（file）; ckq = temp; if （temp = | temp = $） ckq = break; /生成尾随后缀 flag = 0; for （i = az; iN - 1; i+）/判断码本身是否重复 for （j = i + 1; jN; if （strcmp（ci, cj） = 0） flag = 1; if （flag = 1）/如果码本身有重复，就可以断定它不是唯一可译码 for （int y = az; y y+） file1 cy file1 不是唯一可译码。n else for （i = az; i+） /

6、*将原始码字生成的尾随后缀集合s1放入f 中*/ for （j = i + 1; patterson（ci, cj）; for （i = 0; i+） /根据原始码与si生成si+1也放入fi int s = 0; for （j = az; j+） /*判断si+1中的字符串是否与si中一 样 ，重复的则不再添加*/ if （i = sum） s = 1; else patterson（fi, cj）; if （s = 1）break; i+） /*判断尾随后缀与原始码字是否相同， 相同则不是唯一可译码*/ if （strcmp（fi, cj） = 0） flag = 1; break; if

7、 （flag = 1） for （int y = az; file1 else是唯一可译码。 file1 尾随后缀集合为： for （i = 0; i sum; fi =p2=p3=.=pq （2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个 概率最小的信源符号合并成一个信服好，并用这两个最小概率之和 作为新符号的概率，从而得到只包含q-1个服啊后的新信源，称为 S信源的缩减信源S1。 （3）把缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两 个概率最小的符号合并成一个新符号，并分别用0和1码符号表示， 这样又形成了q-2个符号的缩减信源S2。 （4）依次继续下去，直至

8、缩减信源最后只剩两个符号为止。将这最后两 个符号分别用0和1码符号表示。最后这两个符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得 出各信源符号所对应的码符号序列，即得对应的码字。Huffman码参考算法伪代码：if q=2 then Return Else降序排序缩减信源：创建一个符号以取代，其概率递归调用Huffman算法以得到的编码（相应的概率分布为）Return 3. 实现源码#include stdlib.h#pragma warning（disable:#define N 100#define M 2*N-1typedef char * Huffma

9、nCode2 * M;/haffman编码using namespace std;char x100;char y100;fstream in（in2.txtfstream out（out2.txtvoid youchengbianma（char a100）char yc100;int i = 0, j = 0, jishu = 1;yc0 = a0;for （i = 0; ai !if （ai = ai + 1）jishu+;elseycj + 1 = jishu + 48;j = j + 2;ycj = ai + 1;jishu = 1;ycj = cout 游程编码后： yc endl;

10、strcpy_s（x, yc）;void youchengyima（char a100）char bz = 0, jieya100, j, jishu;for （int i = 0; i = i + 2）jieyabz = ai;for （j = bz, jishu = 1; jishu = ai + 1 - 48; jishu+, j+）jieyaj = ai;bz = j;jieyaj = cout 游程译码后： jieya out typedef structint weight;/权值int parent;/父节节点int LChild;/左子节点int RChild;/右子节点HTN

11、ode, HuffmanM + 1;/huffman树typedef struct Node /叶子结点的权值char c; /叶子结点int num; /叶子结点的二进制码的长度WNode, WeightNodeN;/*产生叶子结点的字符和权值*/void CreateWeight（char ch, int *s, WeightNode CW, int *p）int i, j, k;int tag;*p = 0;/叶子节点个数/统计字符出现个数,放入CW chi !tag = 1;for （j = 0;i;if （chj = chi）tag = 0;break;if （tag）CW+*p.c

12、 = chi;CW*p.weight = 1;for （k = i + 1; chk !if （chi = chk）CW*p.weight+;/权值累加*s = i;/字符串长度/*创建HuffmanTree*/void CreateHuffmanTree（Huffman ht, WeightNode w, int n）int i, j;int s1, s2;/初始化哈夫曼树for （i = 1;= n;hti.weight = wi.weight;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;for （i = n + 1;= 2 * n - 1;hti.weight = 0;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;for （j = 1; j htj.weight ? j : s1;hts1.parent = i;hti.LChild = s1;s2 = j; /找到第二个双亲为零的结点s2 = hts2.weight s2;hts2.parent = i;hti.RChild = s2;hti.weight = hts1.weight + hts2.weight;/*叶子结点的编码*/void CrtHuffm