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

typedef struct // 定义结构体

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

typedef HTNode HFMT[MAXLEN]; // 是向量类型的 （3）求哈夫曼树对应的哈夫曼编码。 3．设计要求

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

? 输入一批权值，建立哈夫曼树，并求相应的哈夫曼编码。 ? 撰写课程设计报告，报告格式按规范设置。

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

? 了解串的一般操作方法和存储结构。 ? 掌握数字字符串和其对应数值的转换技巧。 ? 分析大整数运算的特点。 2．主要内容

任意输出两个大整数（至少18位以上），求它们加、减、乘、除的结果。如 12345678901234567890+1234567890=12345678902469135780 12345678901234567890-1234567890=12345678900000000000

12345678901234567890*1234567890=15241578751714678875019052100 12345678901234567890/1234567890=10000000001 3．设计要求

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

? 输入两个大整数，通过菜单选择项分别求其加减乘除运算的结果。 ? 撰写课程设计报告，报告格式按规范设置。

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

16

课题B6：平衡二叉树的构造及输出 1．设计目的

? 复习二叉树的三叉链表存储结构和遍历方法。 ? 掌握二叉排序树的特点和生成方法。

? 掌握平衡二叉树四种不平衡形态的判定和旋转为平衡的方法。 2．主要内容 算法步骤：

（1）输入结点数据，构造二叉树的结点，按二叉排序树的规则插入该结点到三

叉链表中；

（2）从插入的新结点开始，依次寻找其双亲，并检查其双亲的平衡因子是否属

于[-1,1]区间，直到树根节点；如果始终未发现不平衡结点，则可以断定插入该结点后的平衡二叉树仍然保持平衡，跳转到步骤（1）继续插入下一个结点；

（3）在步骤（2）中一旦发现某双亲的平衡因子不属于[-1,1]区间，则可以断定

插入新结点后的二叉树已不再平衡，该双亲结点即为离插入点最近的不平衡结点；

（4）根据该不平衡结点左右孩子及插入新结点的值，即可判定出该二叉树的不

平衡形态（共有LL型、LR型、RR型、RL型四种），然后判定得到的不平衡形态调用不同的旋转函数即可将其重新调整为平衡二叉树；

（5）重复步骤（1）（2）（3）（4），直到所有结点都插入到该平衡二叉树中为止； （6）输出该二叉树的前序（或者后序）序列和中序序列，手工恢复出该二叉树，

检验其是否为平衡二叉树；并验证其中序序列的有序性。 3．设计要求

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

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

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

? 掌握稀疏矩阵的特点及其存储形式(每个非零元素用一个三元组结点形式存储，为零的元素隐含表示不用存储)。

17

? 掌握稀疏矩阵的顺序存储及链式存储方法。

? 掌握稀疏矩阵的简单运算（转置、加、减、乘、除/求逆）。 2．主要内容

（1）采用单链表形式存储稀疏矩阵中各个非零元素的值，其中单链表中的结点

数据类型定义如下： typedef struct _node { int row; //行号 int col; //列号

int weight; //矩阵中的非零元素值 struct _node *next; } Node;

（2）输入二维矩阵A、B、C，分别进行矩阵的加减乘除操作。

?01??10030??900?30???????A?C??00? A??02004? B??73001?

?00??00500??00000?????????31????0?2?C??00?

??0??1?01????100000???80060?????A?B??75005? A?B???7?1003?

?00500??00500?????B?1????????? ??建立的单链表存储结构如下图所示：

矩阵A转置后的单链表存储结构如下图所示：

矩阵A和B相加之和矩阵的单链表存储结构如下图所示：

18

矩阵A和B相减之差矩阵的单链表存储结构如下图所示：

矩阵A和C相乘之积矩阵的单链表存储结构如下图所示：

矩阵B求逆之后的单链表存储结构略。

（3）将矩阵的转置、加、减、乘、求逆分别用函数实现，在主函数中分别调用

以上函数进行验证。 3．设计要求

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

? 输入相应矩阵，通过菜单选项得到矩阵间的运算结果，比较程序运行结果和手工计算结果是否一致；如果两个矩阵不能进行某种运算，需给出相应提示。 ? 转置、加、减、乘等功能为必做，矩阵相除/求逆的功能为选做。 ? 撰写课程设计报告，报告格式按规范设置。

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

课题B8：中国象棋中马的遍历问题（栈的应用） 1．设计目的

? 练习栈在实际问题中的使用方法，掌握栈的本质。 ? 掌握求解问题时使用的回溯策略。

? 比较递归和迭代函数的时间和空间代价，以及它们的难易程度。 ? 总结适合用递归或迭代解决问题的特点。 2．主要内容

编写程序实现马对棋盘方格的遍历。一个棋盘有八行八列共64个方格，输入马的起始方格位置，从起始方格出发，一个马的移动必须跨越两行一列或是两列一行。设起始方格的次序为1，马跳过的下一个方格的次序是上一个方格的次序加1。马必须经过每个方格且仅经过一次，并且马的移动不能超越棋盘边界，

19

求出马经过这64个方格的次序。

例如，下图显示了坐标（5，3）位置上马的所有合法移动位置（即K0~K7）。

图 位置K上马的八个合法移动位置

简化问题表述则为：从坐标（row，column）出发，依次尝试：（row-2，column+1）、（row-1，column+2）、（row+1，column+2）、（row+2，column+1）、（row+2，col …… 此处隐藏：2069字，全部文档内容请下载后查看。喜欢就下载吧 ……