搜索
数据结构A课程设计指导书计算机与信息工程学院一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求在本课程设计过程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。（3）认真编写课程设计报告。课程设计报告的书写格式及要求见附录2。三、设计步骤1、问题分析和任务定义；2、数据类型和系统设计；3、编码实现和静态检查；4、上机调试；5、总结和整理课程设计说明书。四、考核方式和成绩评定考核分为两个部分：程序运行情况：按规定时间到机房运行程序，由教师检查运行情况。针对自己的程序，学生能熟练清楚地回答教师的问题。课程设计说明书：是否按规定书写课程设计说明书的各项内容。课程设计成绩采用五级分制。100%=程序运行情况（60%）+课程设计说明书（40%）五、上交相关内容要求上交时间：最后一次课，验收程序时。纸质版：课程设计说明书，内容与电子版完全一致，具体要求见电子版说明。电子版：压缩包上传到ftp，命名“学号姓名”，必须由以下部分组成，缺一不可：1．源程序：学生按照课程设计的具体要求所开发的所有源程序（放到一个文件夹中）；2．说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3．课程设计说明书：（保存在word文档中，文件名要求按照学号-姓名-课程设计说明书命名，如文件名为101-张三-课程设计说明书.doc）根据《附录1：数据结构课程设计的具体内容》的题目要求，完成课程设计说明书，内容按照如下几个方面展开，格式见《附录2：课程设计说明书规范》；1、需求分析1．程序的功能；2．输入输出的要求；3．测试数据。2、概要设计包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。3、详细设计包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）。4、调试分析测试数据，测试输出的结果。分析时间复杂度，思考每个模块在设计和调试时存在的问题及解决方案（问题是哪些？问题如何解决？），算法的改进设想。5、核心源程序清单和执行结果源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序清单中应有足够的注释描述问题和功能设计。通过一系列的程序执行结果截图，展示程序的所有功能。附录1数据结构课程设计的具体内容本次课程设计完成如下模块（共15个模块，见题目分配表，确定自己题目）1、信号放大器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)+d(E)}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。若在结点D处放置一个放大器，则D(B)=2。根据上述分析，设计如下存储结构：ABCDEFGHIJK1312222122图5网络分布示意图D(i)=0若i为叶子结点D(i)=max{D(j)+d(j)}若i不是叶子结点且j是i的孩子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)};【思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？2、迷宫问题迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。2)基本要求(1)设计数据结构存储迷宫；01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111入口(1,1)出口(6,8)图2迷宫示意图，其中1代表有障碍，0代表无障碍前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下(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、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；4、医院选址问题1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边vi,vj上的权值表示从村庄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．具有最小偏心度的顶点即为所求。【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？5、机器调度问题1)问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：(1)一台机器在同一时间内只能处理一个作业；(2)一个作业不能同时在两台机器上处理；(3)作业i一旦运行，则需要ti个连续时间单位。设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。2)基本要求(1)建立问题模型，设计数据结构；(2)设计调度算法，为每个作业分配一台可用机器；(3)给出分配方案。3)设计思想假设有七个作业，所需时间分别为{2,14,4,16,6,5,3}，有三台机器，编号分别为m1、m2和m3。这七个作业在三台机器上进行调度的情形如图9所示，阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行，在这16个时间单位中，机器1完成了对作业4的处理；作业2在0到14时间被调度到机器2上处理，之后机器2在14到17时间处理作业7；在机器3上，作业5在0～6时间完成，作业6在6～11时间完成，作业3在11～15时间完成，作业1在15～17时间完成。注意到作业i只能在一台机器上从si时刻到si+ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。abcde1253214顶点偏心度ab6c8d5e7(a)(b)图7带权有向图及各顶点的偏心度m1m2m3时间作业5作业6作业3作业1作业2作业7作业4654在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。下面设计完成LPT算法的存储结构。·为每个机器设计数据类型：structMachineNode{intID;//机器号intavail;//机器可用时刻};·为每个作业设计数据类型：structJobNode{intID;//作业号inttime;//处理时间};LPT算法用伪代码描述如下：1.如果作业数n≤机器