《数据结构课程设计》讲义

1、 数据结构课程设计讲义一、 表达式求值问题1.1 问题定义及设计要求表达式求值是程序设计语言编译中的一个最基本问题。人们在书写表达式时通常采用将运算符放在两个操作数中间的“中缀”表示形式，称为中缀表达式。但是这种表达式形式对计算机处理来说是不太适合的。在计算机领域，经常将算术表达式表示成“后缀”表示形式，称为后缀表达式。如: 中缀表达式3+2*(7-5)对应的后缀表达式为3275-*+。要求设计算法，实现（1）算数四则运算中缀表达式到后缀表达式的转换；（2）后缀表达式的求值；（3）中缀表达式的求值。要求配备菜单，至少含如下选项：-1. 中缀表达式到后缀表达式的转换2. 后缀表达式的计算3. 中

2、缀表达式的计算4. 退出-要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。要求演示在求值过程中运算符栈、操作数栈、输入字符和主要操作过程及运算结果。要求在算法用到栈和队列。要求设计的数据结构与算法使算法的时间复杂度与空间复杂度尽可能低。1.2 中缀表达式到后缀表达式的转换（1）问题分析 假设在算术表达式中只含四种基本运算符，操作数是10以内的整数。假设一个中缀表达式中没有括号（如4+2*3，它的后缀表达式为423*+）。在扫描到中缀表达式中的2后，能立即输出+，因为*具有较高优先级，必须先运算，因此需先保存+。也就是说，新扫描运算符优先级必须与前一个运算符的优先级做比较，如果新

3、的运算符优先级高，就要像前一个运算符那样保存它，直到扫描到第二个操作数，将它输出后才能将该运算符输出。因此，在转化中必须保存两个运算符，后保存的运算符先输出。用计算机来实现这个转化过程，就需要用到能后进先出的数据结构-栈。如果在中缀表达式中含小括号，那么由于括号隔离了优先级规则，它在整个表达式的内部产生了完全独立的子表达式。因此，前面的算法就需要有所改变。当扫描到一个左括号时，需要将其压入栈中，使其在栈中产生一个“伪栈底”。这样算法就可以像前面一样进行。但当扫描到一个右括号时，需要将栈中从栈顶到“伪栈底”之间的所有运算符弹出，然后再将这个“伪栈底”删除。（2） 数据结构与算法设计算法基本思想：

4、利用栈（运算符栈）将中缀表达式转换为后缀表达式。顺序扫描中缀表达式，当读到数字时，直接将其送至输出队列中；当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；当读入左括号时，将其入运算符栈；当读到右括号时，将栈中从栈顶到靠近栈顶的第一个左括号(“伪栈底”）之间的所有运算符全部依次弹出，送至输出队列中，再删除栈中的左括号。算法设计要求：将表达式中的操作数规定为1位数字字符。也可根据个人的能力对这部分功能进行扩充，使得操作数可以是多位数，甚至可以是小数或负数。运算符可只包含+、-、*、/ 四种基本运算。也可根据需要对算法的功能进行扩充，允许有其它运算

5、符。为了简化算法，可认为扫描到的任何运算符，其优先级都比栈顶的左括号优先级高。为了方便边界条件（栈空）判断，提高算法运行效率，在扫描中缀表达式之前，在空栈中预先压入一个#字符作为栈底元素，另外，在中缀表达式的最后增加一个#字符作为中缀表达式的结束标志，当扫描到结束符#时，将栈中从栈顶到#之间的所有运算符全部依次弹出，送至输出队列中，再删除栈中的#，并结束算法。算法应该能够过滤掉输入符号之间的空格。也可对本算法功能进行扩充，使其具有对对输入表达式进行语法检查的功能。要求输出中间结果及最终结果，最好能在算法运行过程中演示运算符栈和存放后缀表达式的队列的变化情况。如，若输入的中缀表达式字符串：1+2

6、*（3-1+2）-3#，就会得到后缀表达式：1231-2+*+3-，在算法运行过程中，运算符栈和存放后缀表达式的队列变化过程如表1-1所示。 表1-1 中缀表达式到后缀表达式的转换过程示例转换步骤中缀表达式的读入运算符栈后缀表达式初始 1+2*（3-1+2）-3# # 空1 +2*（3-1+2）-3# # 12 2*（3-1+2）-3# #+ 13 *（3-1+2）-3# #+ 124 （3-1+2）-3# #+* 125 3-1+2）-3# #+*（ 126 -1+2）-3# #+*（ 1237 1+2）-3# #+*（- 1238 +2）-3# #+*（- 12319 2）-3 # #+*

7、（+ 1231-10 ）-3 # #+*（+ 1231-211 -3 # #+* 1231-2+12 3 # #- 1231-2+*+13 # #- 1231-2+*+314 空 1231-2+*+3-1.3 后缀表达式的计算（1）问题分析 在后缀表达式中，不仅不需要括号，而且还完全免除了运算符优先规则。后缀表达式只需要从左到右顺序计算。后缀表达式中可能有多个运算符，如1231-2+*+3-，因此必须像输入字符一样保存中间结果。在计算后缀表达式时，最后保存的值最先取出参与运算，所以需要用栈来存储操作数及中间结果。因为在生成的后缀表达式队列中，存放的是字符序列，因此在算法中要有一个数字字符到数值

8、的转换。（2） 算法设计算法基本思想：利用栈（操作数和运算结果栈）计算后缀表达式。顺序扫描后缀表达式，当读到数字时，将其送至栈中；当读到运算符时，将栈顶字符弹出，将其转换成对应的数值并赋给变量y，再将次栈顶字符弹出，将其转换成对应的数值，并赋给变量x，之后计算xy，将运算结果转换成对应的数字字符送入栈中。注意，本算法主要涉及两种数据结构：队列和栈。算法设计要求：本算法可以对任意输入的后缀表达式进行计算，也可以以前一个中缀表达式到后缀表达式转换算法的输出为输入，计算该后缀表达式。要求显示算法的运行结果。最好能在算法运行过程中演示运算结果栈的变化情况。以输入的后缀表达式为1231-2+*+3-的情

9、况为例，在算法运行过程中，操作数及运算结果栈变化过程如表1-2所示。表1-2 后缀表达式计算过程示例计算步骤后缀表达式的读入运算符栈初始 1231-2+*+3- 空1 231-2+*+3- 12 31-2+*+3- 123 1-2+*+3- 1234 -2+*+3- 12315 2+*+3- 122 6 +*+3- 12227 *+3- 1248 +3- 189 3- 910 - 9311 空 61.4 中缀表达式的计算（1）问题分析要把一个表达式翻译成正确求值的机器指令序列，首先要能够正确解释表达式。要对算术表达式求值，首先要了解算术四则运算规则。即：先乘除，后加减；同级从左到右计算；先括号

10、内，后括号外。例如，1+2*（3-1+2）-3=1+2*（2+2）-3=1+2*4-3=1+8-3=9-3=6任何一个表达式都是由操作数、运算符、界限符组成的。操作数既可以是常数，也可以是说明为变量或常量的标示符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。 为了简化问题，运算符可只包含+、-、*、/ 四种基本运算，括号只有圆括号。可根据需要及个人能力对算法的功能进行扩充，允许有其它运算符。为了简化算法，可认为扫描到的任何运算符，其优先级都比栈顶的左括号优先级高。算符之间的优先关系如表1-3所示。表1-3 算符之间的优先关系表+-*/()#+&g

11、t;><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=x)>>>>x>>#<<<<<x=（2） 算法设计算法基本思想：建立并初始化操作数栈和算符栈，将表达式起始符#压入算符栈。依次读入表达式中的每个字符，当读入的字符ch是操作数，将其入操作数栈；当读入的字符ch是运算符，则根据运算符栈的栈顶元素和ch的优先权比较结果

12、，做不同的处理：若是小于，则ch压入运算符栈，读入下一个字符。若是大于，则弹出运算符栈顶的运算符，从操作数栈弹出两个数，进行相应运算，将结果压入操作数栈。若是等于，则运算符栈顶元素是（且ch是），这时弹出运算符栈顶的（，相当于去括号，然后读入下一个字符。当读入的字符ch是#，且运算符栈顶元素也是#时，算法结束。算法设计要求：将表达式中的操作数规定为1位数字字符。也可根据个人的能力对这部分功能进行扩充，使得操作数可以是多位数。算法应能对由键盘输入任意中缀表达式进行计算。算法应该能够过滤掉输入符号之间的空格。也可对本算法功能进行扩充，使其具有对对输入表达式进行语法检查的功能。 要求在算法运行过程中

13、演示运算符栈和操作数栈的变化情况，并显示最终运算结果。1.5 评价标准 若本实验项目占100分，则其中，（1） 基本功能占60分，具体分值分部如下：l 中缀表达式到后缀表达式的转换 （20分）l 后缀表达式的计算（20分）l 中缀表达式的计算(20分)（2） 附加功能占20分，具体分值分部如下：l 具有语法检查功能（含滤空格、除零异常处理、括号匹配否判断等功能）。（4分）l 除了用键盘输入数据外，还可以将前一个运算的结果（以指定特定文件形式）作为下一个运算的输入。（2分）l 能演示算法运行过程中运算符栈和操作数栈的变化情况。（3分）l 能处理多位数、负数及小数的运算。（3分）l 能实现除了基本

14、的加减乘除运算以外的其他运算，每增加一个运算加一分，直到加满4分为止。（4分）l 界面友好，使用方便，最好能有图形界面。（4分） （3）设计报告占20分。 二、 哈夫曼编码/译码问题2.1 问题定义及设计要求哈夫曼算法应用非常广泛，本节以哈夫曼编码为例说明哈夫曼算法的应用。在电报通信中，电文是以二进制的0、1序列传送的。发送方需将电文中的字符转换成二进制的0、1序列（编码）；接收方则需将收到的电文转化为对应的字符序列（译码）。最简单的编码方式是等长编码，假设电文中字符串仅有26个大写的英文字母组成，采用等长的二进制编码时，每个字符用5位二进制位串表示即可（25>26）。接收方只要按5位分

15、割进行译码就可得到对应的字符。一般来说字符集中的字符在电文中出现的频率是不均匀的，例如，英文中使用A和E较Z要频繁的多。因此，若让使用频率高的字符编码尽可能短，则可使传送的电文总长缩短。然而使用不等长编码可能使译码产生多义性的电文，例如，若用00表示A，01表示E，0001表示Z，则当接受方接收到串0001时，无法确定原文是AE还是W。产生该问题的原因是A的编码是Z的编码的前缀。因此，若对某个字符集进行不等长编码，则要求字符集中任何一个字符的编码都不是其它字符编码的前缀，这种编码叫前缀（编）码。假设组成电文的字符集为C=c1,c2, cn,每个字符ci在电文中出现的次数为ti，ci的编码长度为

16、li，则电文总长为。然而不可能每次传送一个电文时都统计该电文中每个字符的具体出现次数，但可以通过大量的电文进行统计分析，得出每个字符ci出现的概率f(ci)，则是平均编码长度。显然，平均编码长度越小，电文总长越短。因此，若想电文总长最短，可以这样构造最优前缀码：用每个待编码字符ci作为叶结点，用其概率f(ci)作其权值，利用哈夫曼算法构造一棵带权路径长度最小的哈夫曼树。然后将哈夫曼树中每个分支结点的左分支标上0，右分支标上1，将从根到叶子的路径上的标号连接起来，作为该叶结点对应字符的哈夫曼编码。显然，每个字符ci的编码长度是从根到叶子ci的路径长度li，因此，既是平均编码长度，又是二叉树的带权

17、路径长度。由于哈夫曼树是带全路径长度最小的二叉树，因此哈夫曼编码平均编码长度最小。此外，没有一个叶结点是另一个叶结点的祖先，因此，任何字符的编码都不可能是另一个字符编码的前缀。因此，哈夫曼编码是最优的二进制前缀码。要求设计与实现一个哈夫曼编码/译码系统，至少具有如下功能：-1. 建立哈夫曼树2. 哈夫曼编码（生成字符的哈夫曼编码，并产生发送方0、1序列电文） 3. 译码4. 退出-要求设计的数据结构与算法使算法的时间复杂度与空间复杂度尽可能低。2.2 哈夫曼树的建立（1）问题分析哈夫曼树是叶结点的带权路径长度总和最小的二叉树，也称为最优二叉树。因此，在构造哈夫曼树时，权越大的叶结点应该离根越近

18、，权越小的叶结点离根越远。（2) 算法设计算法基本思想：(1) 根据给定的n个权值w1,w2,wn构成一个有n棵二叉树的森林F，其中每棵二叉树都只有一个权值为wi的根结点，其左右子树为空。(2) 贪心地从森林F中选出根结点的权值最小的和第二小的二叉树，将两棵树合并成一棵新树，为了保证新树仍然是一棵二叉树，需增加一个新的根结点，并将所选的两棵树的根分别作为新树根结点的左右孩子，将左右孩子的权值之和作为新根的权值。(3) 在新产生的森林F中，重复（2），直到深林F中只剩一棵树为止。 算法设计要求：在建立哈夫曼树时，叶结点对应的字符及其权值可以用键盘输入。也可以将算法设计的更复杂一些，对指定的文件（

19、电文）， 统计每个字符在电文中出现的次数。假设在电文字符串中只包含大写英文字母，则可定义一个含26个元素的一维整型数组，用于存储每个字母出现的次数。 算法可使用扫描到的字母的ASCII码值减去64作为统计数组的下标计数，从而提高效率。另外，算法还要求出电文中出现了哪些字符（在电文中出现的字符其出现次数不为零），保存这些字符及其在电文中出现的次数，以供建立哈夫曼树及编码时使用。最好能画出算法所建立的哈夫曼树。 2.3 哈夫曼编码（1）问题分析要编码的字符都是哈夫曼树中的叶结点，在哈夫曼树的存储结构中，因为增加了结点与其双亲的链接，所以在进行哈夫曼编码时可以从哈夫曼树的叶结点出发向上回溯到根结点，

20、从而得到该字符的哈夫曼编码。（2) 算法设计算法基本思想： 从哈夫曼树的叶子treei出发，利用双亲指针parent找到treei的双亲treeparent，再利用treeparent的lchild和rchild指针域确定treei是treeparent的左孩子还是右孩子，若是左孩子，则生成代码0，否则生成代码1。然后以treeparent为出发点，重复上述过程，直到找到根结点为止。 因为这样生成的0、1代码序列与要求的编码次序相反，因此，可以将生成的代码从后往前依次存放在一个位串bits中。虽然各字符的编码长度不同，但不会超过要编码的字符个数n，所以bits的大小可为n，并且需要一个指sta

21、rt指示编码在位串bitsn中的起始位置。算法设计要求：要求生成哈夫曼编码对照表，并显示每个字符的哈夫曼编码。要求建立编码文件，对于要编码的字符串中的每个字符，查哈夫曼编码对照表，找到后，将该字符的编码写到代码文件（或在屏幕输出），直到所有字符处理完为止。查哈夫曼编码对照表若能用散列表，算法运行效率会比较高。2.4 译码（1）问题分析接收方可根据哈夫曼树译码，译码过程与编码过程相反。（2) 算法设计算法基本思想： 从哈夫曼树的根结点出发，逐个读入电文中的二进制码，若读入0，走向左孩子，否则走向右孩子，一旦到叶结点，便可译出相应字符。然后，重新从根结点出发继续译码，直到二进制电文结束。 2.5

22、算法实现实例（1）建立哈夫曼树哈夫曼编树存储结构描述如下：int m=2*n; type structchar ch; int weight; int lchild, rchild, parent;HTnode，*HuffmanTree; / HTnode是哈夫曼树结点类型哈夫曼算法如下：void CreatHuffmanTree(HufmanTree &HT, int n) /哈夫曼树算法，n是叶结点数int S1,S2; if (n<=1) return; m=2*n-1；/m是哈夫曼树结点总数 HT=new HTNodem+1; /0单元不用 for(i=1;i<=m

23、;i+) HTi.weight=HTi.lchild=HTi.rchild=HTi.parent=0； for(i=1;i<=n;i+) cin>>HTi.ch >> HTi.weight; for(i=n+1;i<=m;i+) Select( HT,i,S1,S2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTS1.weight+HTS2.weight; /哈夫曼树算法void Select(HufmanTree HT, int i, int &

24、;s1, int &s2) /在HT中选出权最小的和第二小的根结点，其下标分别记在s1和s2中 S1=0; S2=0; sm1= sm2=MAX; for(j=1;j<i;j+) if(HTj.parent=0) if(HTj.weight<sm1) sm2=sm1; sm1=HTj.weight; S2=S1; S1=j; else if(treej.weight<sm2) sm2=HTj.weight; s2=j; （2）哈夫曼编码数据结构与算法设计：因为这样生成的0、1代码序列与要求的编码次序相反，因此，可以将生成的代码从后往前依次存放在一个位串bits中。虽然

25、各字符的编码长度不同，但不会超过要编码的字符个数n，所以bits的大小可为n，并且需要一个指start指示编码在位串bitsn中的起始位置。哈夫曼编码对照表的存储结构如下： type struct char ch; char *first; HuffmanCode;HuffmanCode HCm+1; /Huffman编码对照表生成字符-哈夫曼编码对照表的算法如下：HUFFMANCODE(HufmanTree HT, HuffmanCode &HC, int m)/构造哈夫曼编码HC=new char *m+1; / m是要编码的字符数 cd=new charm; cdm-1=0; f

26、or(i=1;i<=m;i+) strat=m-1; c=i; f=HTi.parent; while(f!=0) start-; if(HTf.lchild=c) cdstart=0; else cdstart=1; c=f; f=HTf.parent; HCi.first= new charm-start; Strcopy(HCi.first, &cdstart); delete cd;建立电文的编码文件的算法如下：void coding(HuffmanCode HC,char *str) /对str所代表的字符串进行编码并写入磁盘文件int i, j; FILE *fp; fp=fopen(“codefild.txt”, “w”);while(*str) for(i=1;i<=m;i+) if (HTi.ch=*str) fputs(HCi.first,fp); break; str+; （3）译码DECODE(codetype code , hufmtree tree )endflag=-1; i=m-1; scanf(“%d”,&b); while(b!=endflag) if(b=0) i=treei.lchild-1; else i=treei.rchild-1; if(treei.lc