}
}
{ flag = 1; break; } } } if (flag == 1) { for (int y = a[z]; y < N; y++) file1 << c[y] <<' '; file1 <<\不是唯一可译码。\\n\; } else{ for (int y = a[z]; y < N; y++) file1 << c[y] <<' '; file1 <<\是唯一可译码。\\n\; } }
file1 <<\尾随后缀集合为：\; for (i = 0; i < sum; i++) file1 << f[i] <<' '; file1 <<\; z++; sum = 0;
4. 运行结果
输入文件：in1.txt
说明：输入文件中第一个数字表示码的组数，第二个数字表示一组码码字的个数，一组码结束以“$”符号结尾；“$”符号后的数字表示下一组码的码字个数。此例以两组码输入为例，多组码判断同上。
输出文件：out1.txt
结果分析：程序首先读取第一组码，进行是否唯一可译码的判断，在输出文件第一行输出判断结果，在第二行输出该码字产生的尾随后缀集合（若只是输出是否唯一可译码的判断结果，不能完全说明程序的正确性，可能存在偶然性；若是输出的尾随后缀集合是正确的，则能说明程序的正确性，由于选取的两组数据来自课本，可以准确的知道尾随后缀集合是否正确，则可验证此程序的正确性，即可用于判断码是否为唯一可译码）。
5. 设计体会
通过此实验的设计，进一步加深了我对唯一可译码判别方法的理解。此实验在设计完成的过程中出现两大难点，第一点就是，作为此程序的核心，两个码字生成尾随后缀的函数编写，选取两个字符数组保存码字和后缀，通过码字长度和单个字符比较来生成尾随后缀；第二个难点是码字的文件读取，起初考虑的是整个码字一起读取，发现实现过程较为复杂，经过修改，改为单个字符读取能简化程序的设计。其他部分按照唯一可译码的判断方法进行设计，关键部分调用尾随后缀生成函数即可，再将判断结果输出到输出文件。此实验总体而言较为简单，实现时注意细节、没有逻辑误区即可。
二、游程编码+Huffman码
1. 任务说明
要求：一无记忆二元信源，0符号的出现概率为1/4, 1符号的出现概率为3/4。现要求 对该信源连续出现的n个符号序列，先进行游程编码，再对结果进行Huffman 编码。然后，再进行Huffman译码和游程译码。假定，连续出现的0或1序列 的长度不超过16，n不小于256。 输入：长为n的0/1串
输出：1. 游程编码结果，2. Huffman编码结果，3. Huffman译码结果 4. 游程译码结果 输入文件:in2.txt，含至少两组输入
输出文件:out2.txt，对每组输入的处理结果
2. 实现原理
游程编码：信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串， 这种字符串的长度称为游程。游程编码（RLC）就是将信源输出的这种字符 序列映射成由串的字符，串的长度和串的位置三个标志组成的标志序列。知 道了串的字符、串的长度和串的位置的标志序列，就可以完全恢复出原来的 字符序列。
在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连 “0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分 别称为游程长度L(0)和L(l)。“0”游程和“l”游程总是交替出现的。如果规 定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游 程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随 机变量，其取值可为1，2，3，?，直到无限。
Huffman码：（1）将q个信源符号按概率分布P（si）的大小，以递减次序排列起来， 设p1>=p2>=p3>=...>=pq
（2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个
概率最小的信源符号合并成一个信服好，并用这两个最小概率之和 作为新符号的概率，从而得到只包含q-1个服啊后的新信源，称为 S信源的缩减信源S1。
（3）把缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两 个概率最小的符号合并成一个新符号，并分别用0和1码符号表示， 这样又形成了q-2个符号的缩减信源S2。
（4）依次继续下去，直至缩减信源最后只剩两个符号为止。将这最后两 个符号分别用0和1码符号表示。最后这两个符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得 出各信源符号所对应的码符号序列，即得对应的码字。
Huffman码参考算法伪代码： if q=2 then Return Else
s0?0,s1?1
降序排序
{pi}
缩减信源：创建一个符号s'以取代递归调用Huffman算法以得到布为
sq?1,sq?2，其概率的编码
p'?pq?2?pq?1
（相应的概率分
s0,s1,...,sq?3,s'w0,w1,...,wq?3,w'p0,p1,...,pq?3,p'）
Return End if
s0?w0,s1?w1,...,sq?3?wq?3,sq?2?w'0,sq?1?w'13. 实现源码
#include
#pragmawarning(disable:4996) #define N 100 #define M 2*N-1
typedefchar * HuffmanCode[2 * M];//haffman编码 usingnamespace std; char x[100]; char y[100];
fstream in(\); fstream out(\);
void youchengbianma(char a[100]) { char yc[100]; int i = 0, j = 0, jishu = 1; yc[0] = a[0]; for (i = 0; a[i] != '\\0'; i++) { if (a[i] == a[i + 1]) jishu++; else { yc[j + 1] = jishu + 48; j = j + 2; yc[j] = a[i + 1]; jishu = 1; }
} yc[j] = '\\0'; cout <<\游程编码后：\<< yc << endl; strcpy_s(x, yc); }
void youchengyima(char a[100]) { char bz = 0, jieya[100], j, jishu; for (int i = 0; a[i] != '\\0'; i = i + 2) { jieya[bz] = a[i]; for (j = bz, jishu = 1; jishu <= a[i + 1] - 48; jishu++, j++) jieya[j] = a[i]; bz = j; } jieya[j] = '\\0'; cout <<\游程译码后：\<< jieya << endl; out <<\游程译码后：\<< jieya << endl; }
typedefstruct { int weight;//权值 int parent;//父节节点 int LChild;//左子节点 int RChild;//右子节点
}HTNode, Huffman[M + 1];//huffman树 typedefstruct Node { int weight; //叶子结点的权值 char c; //叶子结点 int num; //叶子结点的二进制码的长度 }WNode, WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[], int *s, WeightNode CW, int *p) { int i, j, k; int tag; *p = 0;//叶子节点个数 //统计字符出现个数,放入CW for (i = 0; ch[i] != '\\0'; i++) { tag = 1; for (j = 0; j 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库信息论课程设计报告(2)在线全文阅读。
相关推荐：