ch6(6)

1.验证性实验（满分80）

二叉树链式存储结构

 二叉链表的C语言描述

 基本运算的算法——建立二叉链表、先序遍历二叉树、中序遍历二叉树、

后序遍历二叉树、后序遍历求二叉树深度

2.设计性实验（满分90）

（1）合式公式及类型的判断 ①合式公式的定义

 单个命题常项、命题变项p、q、r、0、1、T、F等是合式公式。  若A、B均是合式公式，则：

 A是合式公式。

 A∧B、A∨B、AB、AB均为合式公式。

 有限次运用上述两个规则得到的字符串是合式公式。 ②基本要求

 为了方便输入合式公式，可用以下字符代替联接词：

！： &&：∧ ||：∨ ->： <>：

 根据合式公式的定义判断输入的字符串是否为合式公式。

 若输入的字符串是合式公式，则生成该公式的真值表，并判断公式的类

型（重言式、矛盾式、可满足式）。 ③实现提示

 首先弄清联接词的优先级别：、∧、∨、、。

 建立该字符串对应的命题合式公式的二叉树表示形式，算法思想类似于

表达式的二叉树表示，对于单目运算符，约定其对应的二叉树的左子树为空。若算法结束时存放运算符的栈T非空，或存放二叉树结点的栈S中不止一个元素，则该字符串并非合法的合式公式，否则是合法的合式公式。

 统计该命题合式公式中变元的个数，对各变元赋值，求其命题公式的真

值表，并输出。

 若该命题公式的真值表中全0则为矛盾式，全1则为重言式，有0有1

则为可满足式。 ④思考

 如何输出该合式公式的主析取范式和主合取范式？ （2）等价关系与集合的划分 ①基本要求

对于任何一个集合及其上的一个等价关系R，给出该集合的一个划分。  按以下格式输入集合中的元素，及该集合上的关系的序偶对。

1,2,3,4,5,6,7,8,9

<2,2><1,1><3,4><4,8><3,8>  验证关系R的等价性。

 输出与该等价关系对应的集合的划分。 ②实现提示

 集合中的元素采用顺序表s存储，关系R的表示采用关系矩阵MR=(mij)，

若∈R，则mij=1，否则mij=0。

 关系的等价性验证需验证关系是否具有自反性、对称性、传递性。关系

R是自反的充要条件是关系矩阵MR的对角线全1；关系R是对称的充要条件是mij = mji；关系R是传递的充要条件是对任意的i、j、k，若mij =1，mjk=1，则必有mik =1。

 等价关系诱导的集合的划分实质上是等价关系的等价类的集合，因此只

需求出该等价关系的等价类即可。

3.综合性实验（满分100）

文件压缩 ①基本要求

哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，

并将该哈夫曼树保存到文件HufTree.dat中。

 根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并

将字符编码保存到HufCode.txt文件中。

 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。  解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。 ②选做要求

 实现Burrows-Wheeler压缩算法。

 比较Burrows-Wheeler压缩算法与单纯的哈夫曼编码压缩算法的压缩效

率。

 针对不同长度的文件，统计Burrows-Wheeler压缩算法的执行时间。 ③实现提示

 利用哈夫曼编码压缩文件

 统计词频并建立哈夫曼树：读入文本文件，用一个长度为256的数

组（以字符的ASCII码作为下标）统计各个字符出现的频率，以词频为权值建立哈夫曼树。

 编码：根据哈夫曼树对每个字符进行哈夫曼编码，编码的基本方法

是：结点的左分支编码为“0”，结点的右分支编码为“1”，则从叶子到根结点的路径上经过的0、1序列的逆序，即为该叶子结点字符对应的哈夫曼编码，每个字符的编码用数组存放，一个数组元素存放一位编码0/1，并将编码写入文件HufCode.txt。

 压缩：读入待压缩文件，将每个字符的哈夫曼编码（每个字符的编

码是不等长的0/1序列）的每一位作为一个二进制位，并将多个字符的编码拼接成一个字节，按字节存储。整个文件的字符均编码压缩得到压缩文件CodeFile.dat。

 解压：读入压缩文件CodeFile.dat的二进制序列，从哈夫曼树的根

结点出发，若是0，则沿哈夫曼树的左子树深入，若是1，则沿哈夫曼树当前结点的右子树深入，到达叶子结点时该结点对应的字符即为当前读入的0/1序列的解码，将之写入解压文件，再一次读入其后的二进制序列并译码解压。

 Burrows-Wheeler压缩算法

Burrows-Wheeler Transform(BWT)变换、MTF算法与哈夫曼三者结合的BWT算法是UNIX下的压缩工具bzip2的压缩算法，具有很高的压缩率。该算法的执行步骤如下：

压缩过程：源文件BWT变换MTF算法解压过程：压缩文件Huffuman译码MTF逆变换BWT逆变换源文件Huffuman编码压缩文件

 Burrows-Wheeler Transform变换：是将待压缩文件逐个循环移位后

再全文排序，是的具有相同后缀的字符排在一起。以待变换的字符串S=“abraca”为例，首先将具有n个字符的串S依次循环左移1位，得到n个字符串序列；然后将上述n个字符串序列按ASCII码排序，取排序后的n个字符串的最后一列字符作为输出字符串T=“caraab”，同时构造数组next[]。数组next[]是静态链表，将排序后的字符串按排序前的顺序连成单循环链表，其中，x为该静态链表的头指针，故从头指针x出发，沿着next[x]可依次找到排序前的各个字符串。

总之，Burrows-Wheeler变换的输入是待变换的文本字符串S，经过变换之后输出字符串T、数组next[]（静态链表）及静态链表的头指针x。

循环移位后得到的字符串序列 0 a b r a c a 1 b r a c a a 2 r a c a a b 3 a c a a b r 4 c a a b r a 5 a a b r a c

0 1 2 3 4 5

排序后的字符串序列 a a b r a a b r a c a c a a b b r a c a c a a b r r a c a a

c a r a a b

T next[] c 1 a 3 r 4 x=1 a 5 a 0 b 2

Burrows-Wheeler逆变换，即从已知的文本字符数组T、静态链表next[]及其头指针x恢复到变换前的文本S。由于T是排序后的字符串的最后一列字符，且这些字符串是依次向左循环移位一位得到的，而next[]数组则刚好将排序前的文本串连成了单链表，这意味着，若x下标指向的是排序前的第i个字符串，而第i+1个字符串为第i个字符串循环左移一位得到，因此，第i+1个字符串的最后一个字符即为第i个字符串的第一个字符，故T[next[x]]即为原串S中的第i个字符，即

for (int i=0;iS[i++]=T.GetChar(x);}

在算法的具体实现过程中，有以下两点需要注意：

 对BWT变换中的输入文本进行循环移位得到n个字符串并排

序，并非要等将n个字符串全部移位求出后再排序，如此做法对大文件的变换无论在时间上还是在空间上都不太可行，因此请读者考虑在无需将输入文本逐个循环左移并排序时，如何得到输出字符串T[]及x。

 对next[]，无需在BWT变换中求得，因为只有在BWT逆变换

中才有用，而且可直接根据字符串T[]求得next[]，进而恢复源字符串。如T[]=“caraab”，它是由源串经循环移位并排序后得到的尾字符组成，因此与T对应的首字符应为对T排序的有序串“aaabcr”，可根据首字符组成的串“aaabcr”及T[]得到数组得next[]。

0 1 2 3 4 5

a a a b c r

BWT变换 - - - - - - - - - - - - - - - - - -

-

- - - - -

c a r a a b

T next[] c 1 a 3 r 4 x=1 a 5 a 0 b 2

因字符“c”只出现一次，则对应的next[4]=0，“b”也出现一次，所

以next[3]=5，而“a”字符出现了3次，若第i行、第j行的字符均为“a”，

且i＜j，则next[i]＜next[j]。  MTF（Move To Front）算法：MTF算法的目的是通过自适应的方式，

将出现频率不同的字符重新排列，是高频出现的字符尽量排在低频出现的字符前面，并对输入文本中的字符在给定的有序字符集中的位序及相对位置编码，而不是对输入文本中的字符进行编码。 首先建立输入字符集的有序序列，针对输入文本中的每个字符，查找其在有序字符集中的位置，并输出，同时将有序字符序列中的该字符移动到首部。若MTF算法输入的文本字符串为“caaabcccr”，则输入文本字符集的有序序列为{a、b、c、r}，则字符串“caaabcccr”经MTF变换的过程为

a c a a a b c c c r

有序字符集： Move To Front 输入 输出 b c r c 2 a b r a 1 c b r a 0 c b r a 0 c b r b 2 a c r c 2 b a r c 0 b a r c 0 b a r r 3 c b a 因此，MTF的输入为字符串“caaabcccr”，输出为“210022003”。 在算法实现时，首先建立256个ASCII码字符的有序序列，且每个字符的位序即为该字符的ASCII码；再逐个读入经BWT变换之后得到数组T[]中的字符，依次查找T[]中每个字符在有序字符序列中的位序，并输出，同时将有序字符序列中的该字符移动到首部。由于经过BWT算法之后，相同后缀的字符均排列在一起，使得该字符在有序字符序列中连续出现，因此这些字符在有序字符序列中的位序多位0、1、2、3等较小的数，即在MTF算法输出的0～255的整数中，0、1、2、3等较小的数出现的概率将大大增加，使得这些数字的哈夫曼编码长度很短，甚至达到了高压缩率的目次，如：

MTF输入： a b b b a a b b b b a c c a b b a a a b c MTF输出： 97 98 0 0 1 0 1 0 0 0 1 99 0 1 2 0 1 0 0 1 2

MTF的逆变换：建立256个字符的有序集，将MTF输出的数字序列逐个读入（该序列中的数字表示MTF的输入字符在有序集中的位置），因此根据数字输出有序集中相应位置的字符，并在有序集中将该字符移到集合首部，即可恢复MTF变换前输入的文本。  MTF算法的输出作为哈夫曼编码的输入，进行编码。 上述3中算法均是可逆变换，故可解码，压缩、解压缩也就不成问题了。有关Burrows-Wheeler压缩算法的算法思想和步骤见“Burrows M, Wheeler D J. A block-sorting lossless data compression algorithm [R]. Digital System Research Center Research Report 124, 1994”