12级数据结构与算法课程设计指导书.pdf

长沙学院

课程设计指导书

系（部）计算机科学技术

专业软件工程(服务外包)

2013年12月1日

课程名称：数据结构与算法课程设计

课程编号：JX

主笔人：刘钢钦

主审人：潘怡

一、课程设计的目的

1巩固与加深对课程内容的理解。通过应用程序的设计过程，使学生加深对课程内容的理解，巩固

所学的专业基础知识。

2熟悉开发工具的使用。通过编制与上机调试程序，使学生逐步积累编制与调试程序的经验，促进

实践能力提高。

3培养与增强学生的综合运用能力。通过有一定实用价值的应用程序的开发，激发学生的学习兴趣，

促进学生综合运用能力的提高。

4培养与增强学生的自学能力和利用文献的能力。

二、课程设计的题目

为了充分调动学生的学习积极性与主动性，适应不同兴趣、不同程度的学生对课程设计的要求，本

课程设计提供四个任选题。每个学生可以根据本人的兴趣及能力选择教师指定的选题，也可以自定其他

的选题。

1、一元多项式计算问题

2、迷宫问题

3、利用二叉排序树对顺序表进行排序

4、交通咨询系统

5、内部排序算法的比较

三、设计内容

1、一元多项式计算问题

问题描述：

设计一个稀疏多项式简单计算器

基本要求：

(1)输入并分别建立多项式A和B

(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和

ei是第i项的系数和指数，序列按指数降序排列

2

(3)完成两个多项式的相加、相减，并将结果输出；

测试数据：

14821082

(1)A+BA=3x-8x+6x+2B=2x+4x+-6x

1410861486

(2)A-BA=11x+3x+2x+10x+5B=2x+3x+5x+7

3131

(3)A+BA=x+xB=-x-x

7531

(4)A+BA=0B=x+x+x+x

(5)A-BA=100x100+50x50+20x20+xB=10x100+10x50+10x20+x

选作内容：

（1）.多项式在x=1时的运算结果

（2）求多项式A和B的乘积

2、迷宫问题

问题描述：

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口

（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。

基本要求：

首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路以

三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

测试数据：

左上角（1，1）为入口，右下角（m,n）为出口。

选作内容：

（1）编写递归形式的算法，求得迷宫中的所有可能的通路

（2）以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路

3、利用二叉排序树对顺序表进行排序

问题描述：

利用二叉排序树对顺序表进行排序。

基本要求：

（1）生成一个顺序表L;

（2）对所生成的顺序表L构造二叉排序树;

（3）利用栈结构实现中序遍历二叉排序树;

（4）中序遍历所构造的二叉排序树将记录由小到大输出。

测试数据：

用伪随机数产生程序产生，表长不小于