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

假设马的起始位置为（6,8）时，则马遍历整个棋盘方格的次序如下图所示。

3．设计要求

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

? 输入马的初始坐标位置，输出马对整个棋盘的遍历顺序。 ? 撰写课程设计报告，报告格式按规范设置。

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

? 掌握十字链表结构顶点数组的构造方法。 ? 掌握十字链表结构中弧结点的插入和删除方法。 ? 掌握基于十字链表存储结构有向图的两种遍历方法。 2．主要内容

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

字母作为标志）；

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

表存储结构；

（3）输入一条弧的信息，构造弧结点，并将该弧结点插入到十字链表结构中； （4）输入一条已存在的弧，将其从图的十字链表结构中找到并删除； （5）输出图。

（6）实现BFS或DFS算法输出基于十字链表存储结构有向图的遍历序列。

21

以上（3）（4）（5）（6）项功能以菜单形式列出。

图B9-1 有向图

图B9-2 十字链表

3．设计要求

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

? 输入数据，并验证操作后的输出结果。 ? 撰写课程设计报告，报告格式按规范设置。

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

? （1）掌握线性表的顺序存储结构和链式存储结构。 ? （2）掌握线性表插入、删除等基本运算。

? （3）掌握线性表的典型应用——多项式运算（加、减、乘、除[选做]）。 2．主要内容

22

实现顺序结构或链式结构的多项式加减乘除运算。如果多项式采用顺序结构，则多项式运算的最高次应能达到x99。

例如，已知：f(x)?8x6?4x5?2x4?123x3?x?10

g(x)?2x3?5x2?x

（1）相加结果：f(x)?g(x)?8x6?4x5?2x4?121x3?5x2?10 （2）相减结果：f(x)?g(x)?8x6?4x5?2x4?125x3?5x2?2x?10 （3）相乘结果：

f(x)*g(x)?16x9?32x8?16x7?232x6?613x5?125x4?25x3?51x2?10x （4）相除结果：

商?4x3?12x2?27x；余数??32x2?x?10

如果采用顺序存储结构，则顺序表结点的数据类型定义如下： typedef struct _node { float coe; //系数 int index; //指数 } Node;

函数f(x)的顺序存储结构如下图所示。

图 多项式的顺序表存储结构

如果采用链式存储结构，则链表结点的数据类型定义如下：

23

typedef struct _node { float coe; //系数 int index; //指数 struct _node *next; } Node;

函数f(x)的链式存储结构如下图所示。

图 多项式的单链表存储结构