本科生《算法与据结构》实验报告3.doc

《算法与数据结构》实验报告 学院 专业 姓名 学号 头结点的单链表存储两个集合中的元素和最终的结果出现重复链表学院 专业 姓名 学号 #include iostream.h const int StackSize=50; class Stack{ char *StackList; int top; public: Stack(){ StackList=new char[StackSize]; top=-1; } bool IsEmpty(); bool IsFull(); void Push(char x); char Pop(); char GetTop(); void postexpression(); }; // Stack [测试数据] 6＋3*(9-7)-8/2 转换后的后缀表达式为： 计算结果为： (8-2)/(3-1)*(9-6) 转换后的后缀表达式为： 计算结果为： [思考] 把中缀表达式转化为后缀表达式的好处？ 考虑当表达式中数据的位数超过一位时，如何修改你的程序？困难在哪？ 《算法与数据结构》实验报告 学院 专业 姓名 学号 学院 专业 姓名 学号 [问题描述]…………… [测试数据] 自定n值。 [思考] （1）杨辉三角形中系数之间的关系是什么？ （2）栈和队列各应用于什么范围？ 《算法与数据结构》实验报告 学院 专业 姓名 学号 [问题描述]…) 所谓创建二叉树是指按照某一种或某两种遍历序列建立起来的二叉树的存储结构。 （2）求叶结点的数目：getLeavesNum() （3）画二叉树：drawBTree() （4）输出二叉树的中序遍历序列。 [测试数据] 中序遍历序列结果为： （2）自己设定几组序列来验证程序的正确性。 [思考]学院 专业 姓名 学号 哈夫曼树利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）对于可以双向传输的信道，每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。 哈夫曼树哈夫曼树哈夫曼树哈夫曼树哈夫曼树 (1) 从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，将它存于文件 hfmtree 中。建好的哈夫曼进行编码并且输出。 利用已建好的哈夫曼编码文件 hfmtree ，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。 [测试数据] 用下表给出的字符集和频度的实际统计数据建立哈夫曼树： 字符 A B C D E F G H I J K L M N 频度 64 13 22 32 103 21 15 47 57 1 5 32 20 57 字符 O P Q R S T U V W X Y Z 空格 频度 63 15 1 48 51 80 23 8 18 1 16 1 168 并实现以下报文的译码和输出：THIS PROGRAM IS MY FAVORITE哈夫曼编码哈夫曼学院 专业 姓名 学号 深度优先遍历和广度优先遍历目的 熟悉图的两种常用的存储结构两种遍历方法，即深度优先遍历和广度优先遍历。进一步掌握递归设计方法。深度优先遍历和广度优先遍历 输出结果： [思考] 在你所设计的算法中，使用了什么数据结构？ 考虑如何把书上给出的递归实现的深度优先遍历学院 专业 姓名 学号 输出结果： [思考] 如何判断输入的无向网存在最小生成树? 若不