数据结构课程设计指导题目.docx
《数据结构课程设计指导题目.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计指导题目.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构课程设计指导题目
1、需求分析
1．程序的功能；
2．输入输出的要求；
3．测试数据。
2、概要设计
包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。
3、详细设计
包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）。
源程序要按照写程序的规则来编写。
要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
4、调试分析
测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？
问题如何解决？
），算法的改进设想。
5、核心源程序清单和执行结果
源程序要按照写程序的规则来编写。
要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
1、一元多项式乘法
1）问题描述
已知A（x）=a0+a1x+a2x2+……+anxn和B（x）=b0+b1x+b2x2+……+bmxm，并且在A（x）和B（x）中指数相差很多，求A（x）=A（x）*B（x）。
2）基本要求
（1）设计存储结构表示一元多项式；
（2）设计算法实现一元多项式乘法；
（3）分析算法的时间复杂度和空间复杂度。
2、迷宫问题
1）问题描述
迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。
例如，图2所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。
0
1
2
3
4
5
6
7
8
9
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
2
1
1
0
1
0
1
1
1
1
1
3
1
0
1
0
0
0
0
0
1
1
4
1
0
1
1
1
0
1
1
1
1
5
1
1
0
0
1
1
0
0
0
1
6
1
0
1
1
0
0
1
1
0
1
7
1
1
1
1
1
1
1
1
1
1
2）基本要求
（1）设计数据结构存储迷宫；
（2）设计存储结构保存从入口到出口的通路；
（3）设计算法完成迷宫问题的求解；
（4）分析算法的时间复杂度。
3）设计思想
可以采用回溯法实现该问题的求解。
回溯法是一种不断试探及时纠正错误的搜索方法。
从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。
可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是（x,y），与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素由两个域组成：
x表示横坐标增量，y表示纵坐标增量。
这样会很方便地求出从某点（x，y）按某一方向v（0≤v≤7）到达新点（i，j）的坐标：
i=x+move[v].x；j=y+move[v].y。
算法用伪代码描述如下：
1.栈初始化；
2.将入口点坐标（x,y）及该点的方向d（设为-1）入栈；
3.当栈不空时循环执行下述操作：
3.1（x,y,d）<==栈顶元素出栈；
3.2求出下一个要试探的方向d++;
3.3沿顺时针试探每一个方向，执行下述操作：
3.3.1如果方向d可走，则
3.3.1.1将（x,y,d）入栈；
3.3.1.2求新点坐标（i,j）；
3.3.1.3将新点（i,j）切换为当前点（x,y）；
3.3.1.4若（x,y）是终点，则算法结束；
否则，重置d=0；
3.3.2否则，试探下一个方向d++；
3、抽签游戏
1）问题描述
抽签是我们日常生活中经常遇到的一件事，并且其形式有很多种。
这里介绍一种抽签游戏，如图3所示，最上面一排是游戏的参加者——称为抽签者，最下面一排是签号（奖品、公差等）。
每个人依次顺着竖线往下走，当碰到横线时，即转横向前进，碰到竖线再往下，以此类推，则游戏结束后，抽签者会一一对应到最下面一排的签号。
2.基本要求
（1）设计存储结构存储抽签者、签号、游戏用横线、竖线等；
（2）设计算法实现抽签；
（3）存储游戏的最终结果。
3.设计思想
分析上面的抽签游戏的示例，遇到一条横线，代表这两个竖线的数据就要交换顺序，例如，原来的顺序为{A0,A1,A2,A3,A4}，经过第0层横线后，顺序为{A1,A0,A3,A2,A4}，再经过第1层横线后，顺序为{A1,A3,A0,A2,A4}，以此类推，最后顺序为{A4,A1,A0,A2,A3}，对应到{p0,p1,p2,p3,p4}。
在该游戏中，需解决以下问题：
（1）抽签游戏可以多人参与，只要加上竖线和横线即可。
那么，如何表示这些参与者呢？
解决：
假设有n个人参加，可以用一个一维数组A[n]来记录n个抽签者。
（2）签号如何存储？
解决：
签号的存储也可设计成一个一维数组p[n]来记录n个签号。
（3）如何存储游戏的最终结果？
解决：
设计一维数组B[n]存储最终的对应结果，同时在执行过程中记载中间结果。
（4）当碰到某一横线跨在第i条和第i+1条竖线上时，如何交换数据？
解决：
用一维数组B[n]来存放游戏过程中的中间结果和最终结果，通过交换B[i]和B[i+1]的值解决交换数据问题。
（5）如何表示抽签游戏的竖线和横线布局？
解决：
设计一个二维数组M[m][n]，M[i][j]表示第i层上第j条和第j+1条竖线之间是否有横线，其值为0或1，1代表有横线，0代表没有横线。
图3所述示例对应的数组M如图4所示。
算法设计要点如下：
（1）按从上到下、由左到右的方式遍历数组M，若某元素值为1，则进行数据交换。
（2）在数据交换的过程中，用一维数组B来存放游戏过程中的顺序和最终的顺序，即：
如果M[i][j]=1，则B[j]←→B[j+1]；
（3）最后B[n]即为所求；
4、信号放大器
1）问题描述
天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。
为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。
设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
2）基本要求
（1）建立模型，设计数据结构；
（2）设计算法完成放大器的放置；
（3）分析算法的时间复杂度。
3）设计思想
为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。
图5是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。
对于网络中任一结点i，设d（i）表示结点i与其父结点间的衰减量，D（i）为从结点i到结点i的子树中任一叶子结点的衰减量的最大值，并有如下递推公式：
在此公式中，要计算某结点的D值，必须先计算其孩子结点的D值，因而必须后序遍历二叉树，当访问一个结点时，计算其D值。
例如，D（B）=max{D（D）+d（D），D（E）}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。
若在结点D处放置一个放大器，则D（B）=2。
根据上述分析，设计如下存储结构：
structelement
{
intD;//该结点的衰减量
intd;//父结点的衰减量
boolboost;//当且仅当本处设置放大器，则boost为true
};
structBiNode
{
elementdata;
BiNode*lchild,*rchild;
};
计算并放置放大器的伪代码为：
1.D（i）=0;
2.for（i的每个孩子j）
2.1如果D（j）+d（j）>容忍值，则在j处放置放大器;
2.2否则D（i）=max{D（i），D（j）+d（j）};
【思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？
5、哈夫曼编码
1）问题描述
设某编码系统共有n个字符，使用频率分别为{w1,w2,…,wn}，设计一个不等长的编码方案，使得该编码系统的空间效率最好。
2）基本要求
（1）设计数据结构；
（2）设计编码算法；
（3）分析时间复杂度和空间复杂度。
3）设计思想
利用Huffman编码树求得最佳的编码方案。
根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：
权值、左孩子、右孩子、双亲，如图6所示。
由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。
构造哈夫曼树的伪代码如下：
1.数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；
2.数组huffTree的前n个元素的权值置给定权值w[n]；
3.进行n-1次合并
3.1在二叉树集合中选取两个权值最小的根结点，其下标分别为i1,i2；
3.2将二叉树i1、i2合并为一棵新的二叉树k；
在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。
【思考题】对于采用哈夫曼编码树进行的编码，如何设计解码算法？
6、TSP问题
1）问题描述
所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。
该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。
2）基本要求
（1）上网查找TSP问题的应用实例；
（2）分析求TSP问题的全局最优解的时间复杂度；
（3）设计一个求近似解的算法；
（4）分析算法的时间复杂度。
3）设计思想
对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。
但是用穷举法求解TSP问题的时间复杂度为Ο（n!
），当n大到一定程度后是不可解的。
本实验只要求近似解，可以采用贪心法求解：
任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。
为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。
算法用伪代码描述如下：
1.任意选择某个顶点v作为出发点；
2.执行下述过程，直到所有顶点都被访问：
2.1v=最后一个被访问的顶点；
2.2在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j；
2.2访问顶点j；
3.从最后一个访问的顶点直接回到出发点v；
【思考题】上网查找TSP问题的应用实例，写一篇综述报告。
7、医院选址问题
1）问题描述
n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。
现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？
2）基本要求
（1）建立模型，设计存储结构；
（2）设计算法完成问题求解；
（3）分析算法的时间复杂度。
3）设计思想
医院选址问题实际是求有向图中心点的问题。
首先定义顶点的偏心度。
设图G=（V，E），对任一顶点k，称E（k）=max{d（i,k）}（i∈V）为顶点k的偏心度。
显然，偏心度最小的顶点即为图G的中心点。
如图7（a）所示是一个带权有向图，其各顶点的偏心度如图（b）所示。
医院选址问题的算法用伪代码描述如下：
1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；
2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；
3．具有最小偏心度的顶点即为所求。
【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。
从医院选址问题的求解过程，你有什么感想？
8、排序二叉树的遍历（用递归或非递归的方法都可以）
1）问题描述
输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。
2）基本要求
（1）用菜单实现
（2）能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。
9、集合运算
1）问题描述
使用链表来表示集合，完成集合的合并，求交集等操作。
2）基本要求
（1）用链表表示两个集合
（2）对两个集合分别从小到大排序
（3）两个集合合并成另一个新集合，如数值相同，合并为一个数据项
（4）求出两个集合的交集建立一个新的集合。
附录2：
课程设计说明书规范
一、课程设计说明书规范
课程设计说明书是课程设计主要成果之一，对于设计类，应包括图纸、程序、实物成果等。
1、说明书基本格式
说明书可以手写或打印，书写要用黑或蓝黑墨水，书写工整；打印时正文采用5号宋体，A4纸，页边距均为20mm，行间距采用18磅。
文中标题采用宋体加粗。
2、说明书结构及要求
（1）封面（见附录3）
包括：
题目、系别、班级、完成日期、成绩及指导教师（签字）、学生姓名等项。
（2）课程设计任务书（格式见附录4）
（3）目录
要求层次清晰，给出标题及页次。
最后一项为"参考资料"。
打印时各章题序及标题用小4号黑体,其余用小4号宋体。
（4）正文
正文应按照目录所确定的顺序依次撰写，要求计算准确，论述清楚、简练、通顺，插图清晰整洁。
文中图、标及公式应规范地绘制和书写。
（5）参考资料
参考资料按下述顺序和格式书写：
[1]毛昶熙，周名德等．闸坝工程水力学与设计管理.北京：
水利电力出版社，1995：
8—9
如参考网上资料，请写明网址。
注：
正文内容可参考以下内容：
正文
a）总体设计（程序设计组成框图、流程图）
b）详细设计（模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等）
c）调试与测试：
调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施
d）关键源程序清单和执行结果：
清单中应有足够的注释问题描述和功能设计
（附录3：
封面要求：
）
学号
天津城市建设学院
数据结构课程设计
设计说明书
题目
起止日期：
2009年10月20日至2009年12月14日
学生姓名
班级
成绩
指导教师（签字）
电子与信息工程系
年月日
附表4
天津城市建设学院
课程设计任务书
2009—2010学年第1学期
电子与信息工程系专业班级
课程设计名称：
数据结构课程设计
设计题目：
完成期限：
自2009年10月20日至2009年12月14日共周
设计依据、要求及主要内容（可另加附页）：
一、设计目的
熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。
二、设计要求
在本课程设计过程中要求学生：
（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；
（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。
凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。
（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表。
（4）认真编写课程设计报告。
三、设计内容
（自填，只填自己的设计内容）
四、参考文献
1、王红梅，数据结构，清华大学出版社
2、王红梅，数据结构学习辅导与实验指导，清华大学出版社
3、严蔚敏、吴伟民，《数据结构C语言版》，清华大学出版社（配题集）
升级会员 