《2016年数据结构》教案 第五章 树、图及其应用.docVIP

ch5 树、图及其应用 1. 重言式判别 【问题描述】 一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。 【基本要求】 (1) 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 |， 和 ~，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元 为大写字母。表达式中任何地方都可以含有多个空格符。 (2) 若是重言式或矛盾式，可以只显示True forever，或False forever，否则显示 Satisfactible 以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。 【测试数据】 (1) (A|~A)(B|~B) (2) (A~A)C (3) A|B|C|D|E|~A (4) ABC~B (5) (A|B)(A|~B) (6) A~B|~AB;O ,0;0,1;1,0;1,1 。 2. 哈夫曼编/译码器 【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成 本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编 /译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 【基本要求】 一个完整的系统应具有以下功能： (1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 (2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。 (4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。 (5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 【测试数据】 (1)利用教科书例 6-2 中的数据调试程序。 (2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现以下报文的编码和译码：THIS PROGRAM IS MY FAVORITE。 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【选作内容】 (1)上述文件CodeFile中的每个0或1实际上占用了一个字节的空间，只起到示意或模拟的作用。为最大限度地利用编码存储能力，试改写你的系统，将编码结果以二进制形式存放在文件CodeFile中。 (2)修改你的系统，实现对你的系统的原程序的编码和译码(主要是将行尾符编/译码问题)。 (3)实现各个转换操作的源/目文件，均由用户在选择此操作时指定。 3. 图遍历的演示 【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 【基本要求】 以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 【测试数据】 教科书图7.33。暂时忽略里程，起点为北京。 【实现提示】 设图的结点不超过30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，…，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 【选作内容】 (1)借助于栈类型(自己定义和实现)，用非递归算法实现深度优先遍历。 (2)以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 4. 教学计划编制问题 【问题描述】 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是