《数据结构》课程设计指导书(4)

（1）定义一个运算符栈，输入一个中缀表达式（运算对象为整数，含有+、-、*、

/、%及括号等运算符）。

（2）如果读入的是运算对象，则直接输出到后缀表达式。

（3）如果读入的是运算符，则比较该运算符和栈顶元素的优先级；若该运算符

优先级高于栈顶元素的优先级，则直接进栈；若该运算符优先级低于或等于栈顶元素的优先级，则将栈中高于或等于该运算符优先级的元素先出栈并输出到后缀表达式，然后再将该运算符进栈。

（4）如果读入的是开括号“（”则直接进栈；如果读入的是闭括号“）”则一直

出栈并输出到后缀表达式，直到遇到一个开括号“（”为止，开括号“（”和闭括号“）”均不输入到后缀表达式。

（5）重复（2）（3）（4）步，直到读入中缀表达式结束符，然后将栈中剩余的所

有运算符依次出栈并输出到后缀表达式。 后缀表达式求值的步骤：

（1）定义一个double型的运算对象栈，将中缀表达式转换得到的后缀表达式从

左向右依次读入。

（2）如果读入的是运算对象，直接进入运算对象栈。

（3）如果读入的是运算符，立即从运算对象栈中弹出两个运算对象，计算两个

运算对象运算后的值（先弹出的放后面，后弹出的放前面），并将计算结果存回运算对象栈。

（4）重复（2）（3）步，直到后缀表达式结束，最后栈中保存的那个数即为该后

缀表达式的计算结果

（5）检验程序运行结果的正确性。

假设输入中缀表达式为：(123?32)/5*2?15*18/(2?4)/15?7

32，?，5，/，2，*，15，18，*，2，4，?，/，15，/，?，7，? 转换成的后缀表达式为：123，后缀表达式求得的值为：52 3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。 ? 所有运算对象为多位整数。 ? 能够识别除数为零的错误。

? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。

11

课题A8：哈夫曼编码器 1．设计目的

? 复习二叉树的存储结构和遍历方法。

? 掌握哈夫曼树的构造过程和哈夫曼编码的求解方法。 ? 掌握文件的基本读写方法。 2．主要内容

（1）从权值文件weight.txt中读取权值数据，生成一棵哈夫曼树。 （2）存储哈夫曼树采用静态链表或二叉链表。

若采用静态链表，其数据类型为：

typedef struct // 定义结构体

{ int weight; // 定义一个整型权值变量 int lchild,rchild,parent; // 定义左、右孩子及双亲指针 } HTNode;

typedef HTNode HFMT [MAXLEN]; // 是向量类型的

（3）根据哈夫曼树的求其对应的哈夫曼编码，并将编码写入结果文件code.txt。

图A8-1 给定的权值文件

图A8-2 生成的哈夫曼编码文件

提示：最终生成的哈夫曼编码文件code.txt可能与图A8-2不一样（因为生成的哈夫曼树形态并不是唯一的），但是所有哈夫曼树的WPL（带权路径长度）肯定是一样的。 3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。

12

? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 从文件读入一批权值，建立一棵哈夫曼树，求其对应的哈夫曼编码，并将编码写入编码文件。

? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。 B类题目[共9题]

课题B1：文件记录读取并排序 1．设计目的

? 掌握常用排序算法的过程及特点。 ? 掌握文件读写的基本方法。 2．主要内容

编写程序，将Info.txt文件中的数据记录读出，并按学分排序后写入Result.txt文件。

Info.txt文件中的内容如下图所示。

图B1-1 待排序的原始记录文件

3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 排序方法要求采用快速排序、堆排序、希尔排序、归并排序中的一种，如果

13

采用希尔排序，则每趟的增量值依次为（5，3，1）。

? 如果有多个同学同时完成该课题，要求每个同学均采用不同的排序方法。 ? 给出具体的算法分析，包括排序算法的稳定性、各种不同排序算法的适用条件及性能分析、时间复杂度和空间复杂度等。 ? 撰写课程设计报告，报告格式按规范设置。 课题B2：有向无环图的判定及拓扑排序 1．设计目的

? 掌握图的存储结构和图的两种遍历方法。 ? 掌握有向无环图的判定方法以及拓扑排序算法。 2．主要内容

（1）输入给定有向图的顶点总数和所有顶点标志（每个顶点均用一个大写英文

字母作为标志）；

（2）输入图中弧的总数，并利用循环依次输入各条弧，建立该有向图的邻接表

存储结构；

（3）从图中选取一个入度为零的顶点（如果存在多个顶点入度为零，则任选其

中之一即可），标记该顶点并删除以该顶点为弧尾的所有弧，删除每条弧的同时更新相应弧头的入度值；

（4）不断重复步骤（3），直到找不到入度为零的顶点或者已经删除所有弧为止； （5）如果还有顶点尚未标记（尚未标记顶点的入度肯定均不为零），或者还有弧

结点未被删除，则可判定该图中存在环；如果可以将图中所有顶点全部标记，则标记顶点的顺序即为该有向无环图的拓扑序列；

（6）给出该图有无环的判定结果。若为有向无环图，则给出其拓扑序列；若图

中存在环，则列出环中的所有顶点； 3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 测试时分别输入存在环和不存在环的两个图，输出是否存在环的判定结果，并给出相应的拓扑序列或者列出环中的所有顶点。 ? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。

课题B3：浮点数的IEEE754标准格式转换及输出 1．设计目的

14

? 掌握float型浮点数的存储结构和特点。 ? 掌握C系列语言中的位运算和串操作方法。 ? 了解IEEE754标准。 2．主要内容

（1）输入一个十进制形式浮点数，将其IEEE754结构的存储形式以十六进制形

式输出。

（2）以8位十六进制数形式给定一个IEEE754结构的浮点数，将其代表的十进

制数输出。

（3）验证例子 …… 此处隐藏：1756字，全部文档内容请下载后查看。喜欢就下载吧 ……