数数据结构实验指导书(学生正式2010秋)

1、数据结构课程实验指导书目 录实习步骤2实习报告规范4实习报告样例1最大公因数5实习报告样例2 进制转换11dev c+ 调试方法简介18visual c+6.0调试方法简介24实验用书推荐28预备实验1 字符串处理30预备实验2 文件读取31预备实验3 随机数生成32预备实验4 递归函数33预备实验5 字符串数组的查找34实验1约瑟夫环问题35实验2 一元多项式的运算36实验3 逆波兰表达式求值37实验4 杨辉三角显示39实验5四则运算表达式求值40实验6 bst41实验7 优先队列与堆42实验8 哈夫曼编/译码器44实验9 图的遍历问题45实验10 教学计划编制问题47实验11 最短路径问题

2、48实验12 最小生成树问题50实验13 快速排序51实验14 基数排序53实验15 散列表54实验16 自组织线性表56实习步骤（一）问题分析和任务定义在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么？限制条件是什么。注意：本步骤强调的是做什么？而不是怎么做。主要完成三个方面的工作：（1） 分析并确定问题要处理的对象（数据）是什么。例如：输入数据的类型、值的范围以及输入的形式。（2） 分析并确定要实现的功能是什么。也就是说要对输入的数据进行什么样的处理。注意：对问题中描述的需要实现的功能，应避开算法（具体的实现方法）和所涉及的数据类型，仅需对所需完成的任务做出明确的定义。（3

3、） 分析并确定处理后的结果如何显示。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据；以及相应的输出结果。（二）数据类型和系统设计当需求分析结束，明确问题要求后，开始为编写程序设计合适的数据结构和算法。本步骤分概要设计和详细设计两步实现。概要设计指的是，对问题描述中涉及的操作对象定义相应的抽象数据类型，并设计合适的算法；以及定义程序各个功能模块和模块之间的关系。在这个过程中，要根据问题的功能需求综合考虑，设计时空复杂度最优的抽象数据结构和算法（注意：实现提示和给出的部分代码中以及给出了建议）。抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体，算

4、法思想和过程明确有效，程序结构清晰、合理、简单和易于调试。作为概要设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），主要模块的算法思想，并画出模块之间的调用关系图。详细设计则定义相应的物理存储结构（抽象数据类型的物理实现）并写出各基本操作的伪码算法，以及主要模块算法的具体步骤。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，算法书写规范（采用文字性的步骤描述或者算法流程图的形式都行）。在求精的过程中，应尽量避免陷入语言细节，不必过早描述辅助数据结构和局部变量。（三）编码实现和静态检查在实验过程中，题目中会给出程序

5、的部分源代码，根据实习第二步的设计结果以及源代码的提示，编码实现程序的其余部分。编码是把详细设计的结果进一步求精为程序设计语言程序。对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。写出编码的程序后，在上机（编译和调试）之前，认真的静态检查是必不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为纠查错误是编译器的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除

6、语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。（四）上机准备和上机调试上机准备包括一下几个方面：（1） 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。（2） 上机调试程序时要带一本高级语言教材或手册。（3） 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴工”。计算机各专业的学生应

7、该能够熟练运用高级语言的程序调试器debug调试程序。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试底层函数。必要时可以另写一个调用驱动程序。这种表面上的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。在调试过程中可以不断借助debug的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想”，而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。（五）总结和整理实习报告按照实习报告的格式完成整个实习报告。同时总结和思考，回味设计的过程，体会

8、调试的过程，总结编程中的收获，记录实习过程的体会，交流程序设计各个步骤的心得。“学而不思则罔，思而不学则殆。”在程序设计中，只有做到勤思考、善总结，才能不断进步。实习报告规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下七个内容：1 需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：（1） 输入的形式和输入值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2 概要设计说明本程序中用到的所有抽象数据类型的定义、算法的基本思想、主程序的流程以及各程序模块之间的层次（调用）关系

9、。3 详细设计（1） 实现概要设计中定义的所有数据类型（物理数据结构），对每个操作只需要写出伪码算法；（2） 算法的具体步骤；（3） 算法的时空分析和改进设想；（4） 画出函数的调用关系图。（5） 输入和输出的格式。4 调试分析调试过程中遇到的问题，以及如何解决的；5 测试结果根据实验提供的测试数据，列出你所编写的程序的测试结果。6 用户使用说明（可选）说明如何使用编写的程序，详细列出每一步的操作步骤。7 实验心得（可选）对实验设计与实现过程的回顾和分析，以及经验和体会。8 附录（可选）带注释的源程序。如果是提交源程序电子版，只需列出程序文件名的清单。实习报告样例1最大公因数题目部分背景因数分

10、解，求最大公因数和公倍数等问题都是数学中古老而又重要德问题，这些问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。问题描述两个整数的最大公因数是同时整除二者的最大整数。试设计一个计算两个整数的最大公因数的程序。基本要求（1） 用户输入两个正整数，其取值范围为（0， 216），（2） 要求采用欧几里德算法，计算最大公因数。测试数据输入7591035输出69实现提示（1） 注意题目给出的正整数的取值范围，定义变量时，选择合适的数据类型。（2） 欧几里德算法计算最大公因数，编写成一个独立的函数，并注意该算法对两个数据的大小关系有要求，在设计函数的输入参数以及函数处理代码时要注意处理

11、。选作内容（1） 设计一个求取n个正整数的最大公因数的函数。（2） 如果用户输入的正整数的取值范围为（0, 232）、（0, 264），请设计求取两个大的正整数的最大公因数的函数。源程序及填空部分#include “stdio.h”typedef long elemtype; /欧几里德算法计算最大公因数函数elemtype gcd (elemtype m, elemtype n)/填空main ()elemtype a, b, g;/输入printf(“n本程序可以求取两个正整数的最大公因数n”);printf(“n请输入第一个正整数（注意输入的数要小于2100000000）：”);scan

12、f(“%ld”, &a);printf(“n请输入第二个正整数（注意输入的数要小于2100000000）：”);scanf(“%ld”, &b);g=gcd(a, b);/输出printf(“n两者的最大公因数是：%ld”, g);实验报告部分hunan university课程实习报告题 目： 最大公因数 学生姓名 学生学号 专业班级 指导老师 完 成 日 期 57 一、需求分析1 本程序要求采用欧几里德算法，计算并输出用户输入的两个正整数的最大公因数。2 两个正整数由用户通过键盘输入，其取值范围为（0， 216）。不对非法输入做处理，即假设输入都是合法的。3 在dos界面输出最大公因数。4

13、 测试数据输入7591035输出69二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。算法的基本思想根据题目要求，采用欧几里德算法计算两个正整数的最大公因数。该算法的基本思想是辗转相除法。设两数为a、b（ba），求它们最大公约数(a、b)的步骤如下：1. a b，令r为所得余数（0rb）若 r = 0，算法结束；b 即为答案。2. 互换：置 ab，br，并返回第一步。程序的流程程序由三个模块组成：（1） 输入模块：完成两个正整数的输入，存入变量a和b中。（2） 计算模块：设计一个最大公因数函数，elemtype gcd (elemtype m, elemt

14、ype n)，两个整数作为函数参数，计算结果通过函数名返回。（3） 输出模块：屏幕上显示计算的最大公因数。三、详细设计物理数据类型题目要求输入的正整数的取值范围在（0， 216）之间，为了能够存储，采用c语言中的长整型定义变量。typedef long elemtype算法的具体步骤欧几里德算法计算两个正整数的最大公因数的算法流程图如下算法的时空分析算法的运行时间依赖与确定余数序列有多长。可以证明，在两次迭代后，余数最多是原始值的一半。则迭代次数是2log no(log n)。输入和输出的格式输入本程序可以求取两个正整数的最大公因数/提示请输入第一个正整数（注意输入的数要小于210000000

15、0）：/提示等待输入请输入第二个正整数（注意输入的数要小于2100000000）：/提示等待输入输出/提示两者的最大公因数是：/输出结果的位置四、调试分析略。五、测试结果输入50 15输出5输入1989 1590 输出3六、用户使用说明（可选）1、本程序的运行环境为dos操作系统，执行文件为gcd.exe2、运行程序时提示输入两个整数本程序可以求取两个正整数的最大公因数请输入第一个正整数（注意输入的数要小于2100000000）：请输入第二个正整数（注意输入的数要小于2100000000）：输出两者的最大公因数是：七、实验心得（可选）略。七、附录（可选）gcd.c 主程序实习报告样例2 进制转

16、换题目部分背景机制转换是计算机实现计算的基本问题。问题描述十进制数n和其他d进制数的转换是计算机实现计算的基本问题。请编制一个满足下列要求的进制转换程序。基本要求（1） 用户输入一个非负的十进制整数，其取值范围为（0， 216），（2） 打印输出与其等值的八进制数。测试数据输入1000输出1750实现提示（1） 利用求模取余法，n（n div d） d n mod d公式实现。（2） 由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出正好相反，利用堆栈的后进先出的特性正好实现。选作内容（1） 设计一个能处理小数的进制转换程序。（2） 设计一个能处理负数的进制转换程序。源程序及

17、填空部分#include #include /*包含动态内存分配函数的头文件*/typedef int elemtype;typedef struct nodetype elemtypedata;struct nodetype*next;node;typedef struct node * top;int len;linkstack;void initstack(linkstack *s)/构造一个空栈s。s-top=null;s-len=0;int stackempty(linkstack *s)/若栈s为空栈，则返回true，否则返回falseif (s-len = 0)return 1;

18、elsereturn 0;/返回1 表示true，否则返回0表示falseint push(linkstack *s, elemtype e) /新元素e入栈/填空int pop(linkstack *s, elemtype *e) /栈顶元素出栈，并以e返回其值/填空void conversion(linkstack *s, int n) /进制转换，保存（入栈）在s中/填空void display(linkstack *s) /输出，把s中元素出栈，并显示/填空main()struct linkstack * ls;int n;int d;ls=(linkstack *)malloc(si

19、zeof(linkstack); /关键的初始化scanf(%d, &n);initstack(ls);conversion(ls, n);display(ls);实验报告部分hunan university课程实习报告题 目： 进制转换 学生姓名 学生学号 专业班级 指导老师 完 成 日 期 一、需求分析1 本程序要求对用户输入一个非负的十进制整数，打印输出与其等值的八进制数。2 十进制整数由用户通过键盘输入，其取值范围为（0， 28）。不对非法输入做处理，即假设输入都是合法的。3 在dos界面输出其等值的八进制数。4 测试数据输入1348输出2504二、概要设计抽象数据类型为实现上述程序的

20、功能，应以整数存储用户的输入。为了实现求模取余法，利用堆栈保存计算的结果。堆栈定义如下：adt stack数据对象：整数基本操作：initstack（&s）/构造一个空栈s。 stackempty（s）/若栈s为空栈，则返回true，否则返回falsepush（s，&e）/新元素e入栈 pop（&s，&e）/栈顶元素出栈，并以e返回其值算法的基本思想根据题目要求，用求模取余法，n（n div d） d n mod d公式实现。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出正好相反，利用堆栈的后进先出的特性正好实现。程序的流程程序由三个模块组成：（1） 输入模块：完成正整数

21、的输入，存入变量n中。（2） 转换模块：实现求模取余法，余数依次入堆栈中。（3） 输出模块：从堆栈中取数，并显示在屏幕上。三、详细设计物理数据类型题目要求输入的正整数的取值范围在（0， 28）之间，为了能够存储，变量n采用c语言中的int定义变量。因为堆栈需存储的元素个数和十进制数n的大小直接相关，其长度变化很大，所以堆栈采用单链表来实现其物理数据结构。堆栈的每个元素只需存储08的字符，所以栈中元素类型定义为字符型。typedef int elemtypetypedef struct nodetype elemtypedata;struct nodetype*next;node;typedef

22、 struct node * top;int len;linkstack;void initstack（linkstack *s）/构造一个空栈s。s-top = null;s-len=0;int stackempty（linkstack *s）/若栈s为空栈，则返回true，否则返回false若s-len= = 0 /返回1 表示true，否则返回0表示falseint push（linkstack *s，elemtype e）/新元素e入栈/分配新空间，建立一个新结点l (node *) malloc (sizeof(node);若l null 返回0表示false；入栈失败l-data

23、= e; l-next = s-top; /插入s-top = l; s-len+; 返回1 表示true，入栈成功int pop（linkstack &s，elemtype *e）/栈顶元素出栈，并以e返回其值若栈空，返回0表示false；出栈失败*e = s-top-data; l = s-top;s-top = s-top-next；free（l）；s-len-;返回1 表示true，出栈成功算法的具体步骤求模取余法流程图如下：函数名conversion(*s, n)输出的算法（函数display (*s)）：栈顶元素出栈，转换为字符的ascii码，然后用字符格式输出。算法的时空分析算法

24、的执行，主要是每次n除8，以及入栈，出栈显示，由于采用链表实现，入栈和出栈的时间复杂度都是o(1)，那么进制转换的时间复杂度，主要由n的大小决定，具体来说是要除8几次，即8 k = n。由此可知上述设计的时间复杂度是o(log8n)。函数的调用关系图initstack /堆栈初始化输入十进制数nconversion () /进制转换push /入堆栈主程序stackempty / 判定栈空display () /显示结果pop /出堆栈输入和输出的格式输入本程序可以把输入的十进制数转换为八进制的数/提示请输入十进制的正整数（注意输入的数要小于2100000000）：/提示等待输入输出/提示八进

25、制数数是：/输出结果的位置四、调试分析略。五、测试结果略。六、用户使用说明（可选）1、本程序的运行环境为dos操作系统，执行文件为conversion.exe2、运行程序时提示输入本程序可以把输入的十进制数转换为八进制的数请输入十进制的正整数（注意输入的数要小于2100000000）：输出八进制数数是：七、实验心得（可选）略。七、附录（可选）conversion.c 主程序stack.h 堆栈实现（数据结构）dev c+ 调试方法简介一、dev c+下的调试的几个基本步骤。1. 把“生成调试信息”设置为 yes。方法如下：tools（工具） - compiler options（编译器选项）

26、- settings（设置）2. 编译程序。程序“编译”编译后会出来这个对话框。点击“关闭”，关闭该按钮。3. 设置断点（break point）把光标移动到您想暂停执行的那一行，按 ctrl + f5，或者直接用鼠标点击下图红线标明的区域。（如下图）4. 开始调试（debug）按 f8 开始调试，或者点击“调试”选项（ debug ）后就弹出下拉菜单（如下图）。如果您没有把“生成调试信息”设置为 yes，dev-c+ 会提示说您的工程中没有调试信息。点击 yes，dev-c+ 会自动把“生成调试信息”设置为 yes，并且重新编译您的工程。程序运行到断点处会暂停；按 f7 执行当前行，并跳到下

27、一行；ctrl + f7 跳到下一断点，shift + f4 跳到光标所在行，并在该行设置断点。注意一点。比如。设置的“断点”是printf语句处。那执行只执行到scanf语句后就不会显示答案了。如下图。大家看到那蓝条，这是做什么的呢，这是因为设置的“断点”是printf语句后，但又显示不出答案。如果想得到答案。可以按左下角的。“下一步”如下图。5. 查看变量的值开始调试后，在图示区域按右键（如果您使用的是左手习惯，则是左键），选择“添加监测（add watch）”；或者直接按 f4。在弹出窗口中输入您想查看的变量名，然后按确定（ok），就可以看到该变量的值：用鼠标选择源文件中的变量名，然后按

28、 f4 也可以查看变量的值，该变量会出现在左边的监测列表中：如果在环境选项（environment options）中选择了“通过鼠标监测变量（watch variable under mouse）”，用鼠标指向您想要查看的变量一段时间，该变量也会被添加到监测列表中。重要提示：1) 当您想查看指针指向的变量的值的时候，按 f4，然后输入星号及指针的名字（如 *pointer）。 如果没加 *，看到的将会是一个地址，也就是指针的值。2) 有时，调试器（debugger）可能不知道某个指针的类型，从而不能显示该指针指向的变量的值。此时，我们需要手动输入该指针的类型。按 f4 后，以 *(type

29、*)pointer 形式输入。例如，*(int *)pointer。6. 最后点击“停止执行”就退出调试了。如下图。二、调式例子下面这个程序，编译能正常通过，但是运行时计算结果无法显示，通过调式可以找出存在死循环。#include #include int main(int argc, char *argv) int i=1, sum=0; while(i0)个人按顺时针方向围成一圈首先第1个人从1开始顺时针报数报m的人(m 为正整数)令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。基本要求需要基于线性表的基本操作

30、来实现约瑟夫问题需要利用数组来实现线性表输入输出格式输入格式：n，m输出格式1：在字符界面上输出这n个数的输出序列输出格式2：将这n个数的输出序列写入到文件中选做内容（1） 使用单链表来实现之（2） 使用循环链表来实现之测试用例输入：10，3输出：3 6 9 2 7 1 8 5 10 4课后习题请以o（n）的时间复杂度来实现约瑟夫问题。实验2 一元多项式的运算背景在数学上，一个一元n次多项式pn(x)可按降序写成：它是由n1个系数唯一确定。因此，在计算机里它可以用一个线性表p来表示：p=（pn, pn-1, , p1, po）一元多项式的运算包括加法、减法和乘法，而多项式的减法和乘法都可以用加

31、法来实现。问题描述设pn(x)和qm(x)分别两个一元多项式。试编写程序实现一元多项式的加法运算。基本要求需要基于线性表的基本操作来实现一元多项式的加法运算需要利用有序链表来实现线性表。输入输出举例/第一个多项式为9x15+7x8+5x3+3x输入4 /表示第一个多项式的项数9， 15（回车） /表示9x157， 8 （回车）5， 3 （回车）3， 1 （回车）输出9x15+ 7x8+5x3+3x1/第二个多项式为-7x8+6x3+2输入3 /表示第二个多项式的项数6， 3（回车） /表示9x15-7， 8（回车）2， 0 （回车）输出-7x8+ 6x3+2x0求和结果 9x15+11x3+3

32、x1+ 2x0实验3 逆波兰表达式求值背景表达式求值是程序设计语言编译中的一个最基本的问题因为任何程序设计语言都必须具有表达式求值的功能，同时表达式的计算应用也相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。通常，我们所说的表达式是由运算符、操作数、界限符所组成。而算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。1、中缀表达式将运算符放在两操作数的中间。在运算中存在运算符的优先权与结合性的问题。例如运算：a*b+(c-d/e)*f 时，编译器即自左向右逐一检查，当检查到第一个运算符“

33、*”时还无法知道是否执行；待检查到第二个运算符“ + ”时，因为知道“*”的优先级别高于“ + ”时，才知道执行“a*b”；当继续检查到“ ( ”时，可知道先执行括号以内部分等。2、前缀表达式将运算符放在两操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家jan lukasiewicz，这种表示法也称波兰表示法。3、后缀表达式将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。前缀和后缀表示法有三项公共特征：（1） 操作数的顺序与等价的中缀表达式中操作数的顺序一致（2） 不需要括号（3） 操作符的优先级不相关问题描述读

34、入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。基本要求（1）从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。（2）用堆栈来实现输入输出格式输入：在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。以“#”表示结束。输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字，如果不正确，请在字符界面上输出表达式错误提示。选作内容（1） 在输入和输出方式上发生改变：输入：将后缀表达式存于文本文件中，其中后缀表达式中两相邻操作数之间利用空格隔开，程序从该文本文件中读出表达式。输出：如果该后缀表

35、达式正确，则计算结果，计算结果保留小数点后面两位有效数字，同时将结果输出到该文件中原表达式的后面，结果与表达式之间用“=”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“-”相连。（2） 表达式中操作数为一实数，该实数精确到小数点后面两位有效数字。测试用例输入：2 3 * 1 #输出：5课后习题 n个元素1,2,n有n!个不同的排列。将这n！个排列按字典序列排列，并编号为0，1,n!-1.每个排列的编号为其字典序值。例如，当n=3时，6个不同排列的字典序值如下：字典序值012345排列123132213231312321请编程实现之。实验4 杨辉三角显示背景中国古

36、代数学史曾经有代写论文自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。杨辉三角是中国古代数学家贾宪在公元11世纪发现，并被南宋数学家杨辉在他的书中所引述，才使我们今天得以了解贾宪在数学上的重大贡献。杨辉三角是一个由数字排列成的三角形数表.一般形式如下: 问题描述编写程序，根据输入的行数，屏幕显示杨辉三角。基本要求(1) 行数不大于20行。(2) 基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现）(3) 基于数组实现队列的物理数据结构。输入输出输入 n 6输出1 n=01 1 n=11 2 1 n=21 3 3 1 n=31 4 6 4 1

37、n=41 5 10 10 5 1 n=51 6 15 20 15 6 1 n=6实验5四则运算表达式求值背景在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。问题描述四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。基本要求(1) 使用二叉树来实现。实现提示利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。输出：如果该中缀表达式

38、正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。选作内容（1）在输入输出方式上要求使用：输入：将中缀表达式存于文本文件中，程序从该文本文件中读出表达式。输出：如果该中缀表达式正确，则将后缀表达式输出到该文件中原表达式的后面，它们之间用“-”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“-”相连。(2) 利用堆栈来实现中缀表达式转换为后缀表达式。测试用例输入：21+23*（12-6）输出：21 23 12 6 -*+课后习题采用非递归的编程方法分别统计二叉树的节点个数度为1和叶子节点

39、的个数以及数据值的最大值和最小值。实验6 bst问题描述利用二叉查找树（bst）实现一个动态查找表。基本要求(1) 使用二叉树（bst）来实现。(2) 二叉树使用链式结构（二叉链表）实现。(3) 实现bst的构建，查找两个功能。实现提示输入：8/bst的节点个数34, 76, 45, 18, 26, 54, 92, 65 /8个数据45/查找 45输出：查找成功 3 /返回成功和查找时比较的次数 34/查找 34输出：查找成功 1 /返回成功和查找时比较的次数100/查找 100输出：查找不成功 3 /返回成功和查找时比较的次数选作内容(1) 实现二叉树（bst）的插入和删除功能。(2) 查找不成功时，被查找的数据插入到bst中。课后习题随机产生n个数据，构建bst。然后随机产生m个数据（可能由相等的数据），对每一个数据在bst中进行查找，统计比较的次数，求取查找的平均值。若查找不成功时，被查找的数据插入到bst中，统计比较的次数，求取查找的平均值。实验7 优先队列与堆背景优先级队列（priority queue）就是遵循两个排序规则的集合。首先，具有高优先级的项目在先。第二，具有相同优先级的项目使用先进先出方法来确定其排序。用到优先队列的地方：凡是需要取出集合中最值元素的地方。l 构建霍夫曼编码构建霍夫曼编码需要找到结点集合中频率最小的两个结点。然后合并结点插入到集