1、软件工程数据结构课程设计指导数据结构课程设计任务书一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求在本课程设计过程中要求学生：（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。（3）认真编写课程设计报告。三、设计步骤1、 问题分析和任务定义；2、 数据类型和系统设计；3、 编码实现和静态检查；4、 上机调试；5、总结和整理课程设计报告。四、考
2、核方式和成绩评定考核分为两个部分： 程序运行情况：老师检查运行情况。 实验报告：是否按规定书写实验报告的各项内容。五、上交相关内容要求上交的成果的内容必须由以下两个部分组成，缺一不可1光盘，光盘中应有如下内容。 源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）； 程序的说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；2 课程设计报告：按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；1、需求分析1 程序的功能；2 输入输出的要求；3 测试数据。2、概要设计F
3、or personal use only in study and research; not for commercial use包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。3、详细设计包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）。For personal use only in study and research; not for commercial use源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。4、调试
4、分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。For personal use only in study and research; not for commercial use5、核心源程序清单和执行结果源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。附录1 数据结构课程设计的具体内容For personal use only in study and research; not for commercial use本次课程设计完成如下模块之一（一组一题）。
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所示为一个迷宫示意图，其中双
6、边矩形表示迷宫，1代表有障碍，0代表无障碍。012345678901111111111110111011112110101111131010000011410111011115110011000161011001101711111111112) 基本要求(1) 设计数据结构存储迷宫；(2) 设计存储结构保存从入口到出口的通路；(3) 设计算法完成迷宫问题的求解；(4) 分析算法的时间复杂度。3) 设计思想可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没
7、有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move8中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向 v (0v7) 到达新点（i，j）的坐标
8、：i=x+movev.x ； j=y+movev.y。算法用伪代码描述如下：1. 栈初始化；2. 将入口点坐标(x , y)及该点的方向d（设为-1）入栈；3. 当栈不空时循环执行下述操作：3.1 (x , y , d)容忍值，则在j处放置放大器; 2.2 否则D(i) = maxD(i)，D(j) +d(j) ;【思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？5、哈夫曼编码1) 问题描述设某编码系统共有n个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2) 基本要求(1) 设计数据结构；(2) 设计编码算法；(3
9、) 分析时间复杂度和空间复杂度。3) 设计思想 利用Huffman编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图6所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。构造哈夫曼树的伪代码如下：1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1； 2. 数组huffTree的前n个元素的权值置给定权值wn； 3. 进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为
10、i1, i2； 3.2 将二叉树i1、i2合并为一棵新的二叉树k； 在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。【思考题】对于采用哈夫曼编码树进行的编码，如何设计解码算法？6、TSP问题1) 问题描述所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。2) 基本要求(1) 上网查找TSP问题的应用实例；(2) 分析求TSP问题的全局最优解的时间复杂度；(3) 设计一个求近似解的算法；(4) 分析算法的时间复杂度。
11、3) 设计思想对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为(n!)，当n大到一定程度后是不可解的。本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：1. 任意选择某个顶点v作为出发点；2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2 在顶点v的邻接点中查找距离顶点v最近
12、的未被访问的邻接点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
13、d(i, k)（iV）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。医院选址问题的算法用伪代码描述如下：1对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3具有最小偏心度的顶点即为所求。【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？8、简单个人电话号码查询系统1) 问题描述人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入的信息（例
14、如姓名等）进行快速查询。2) 基本要求(1) 在外存上，用文件保存电话号码信息；(2) 在内存中，设计数据结构存储电话号码信息；(3) 提供查询功能：根据姓名实现快速查询；(4) 提供其他维护功能：例如插入、删除、修改等；(5) 按电话号码进行排序。3) 设计思想 由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据： const int max=10; struct TeleNu
15、mber string name; /姓名 string phoneNumber; /固定电话号码 string mobileNumber; /移动电话号码 string email; /电子邮箱 Telemax;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉排序树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉排序树是否平衡，如何使之达到平衡。9、各种排序算法时间性能的比较1) 问题描述 对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排
16、序、直接选择排序、堆排序和归并排序）的时间性能进行比较。2) 基本要求(1) 设计并实现上述各种排序算法；(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性能。3) 设计思想上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序算法中的适当位置插入计数器统计元素的比较次数和移动次数。【思考题】如果测算每
17、种排序算法所用实际的时间，应如何修改排序算法？10、机器调度问题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，有三台
18、机器，编号分别为m1、m2和m3。这七个作业在三台机器上进行调度的情形如图9所示，阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行，在这16个时间单位中，机器1完成了对作业4的处理；作业2在0到14时间被调度到机器2上处理，之后机器2在14到17时间处理作业7；在机器3上，作业5在06时间完成，作业6在611时间完成，作业3在1115时间完成，作业1在1517时间完成。注意到作业i只能在一台机器上从si时刻到si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。 在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需
19、时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。 下面设计完成LPT算法的存储结构。 为每个机器设计数据类型： struct MachineNode int ID; /机器号int avail; /机器可用时刻 ; 为每个作业设计数据类型： struct JobNode int ID; /作业号int time; /处理时间 ;LPT算法用伪代码描述如下：1. 如果作业数n机器数m，则 1.1 将作业i分配到机器i上； 1.2 最短调度长度等于n个作业中处理时间最大值；2. 否则，重复执行以下操作，直到n个作业都被分配： 2.1 将n个作业按处理时间建成一个大根堆H1； 2
20、.2 将m个机器按可用时刻建立一个小根堆H2； 2.3 将堆H1的堆顶作业分配给堆H2的堆顶机器； 2.4 将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入h2中； 2.5 将堆H1的堆顶元素删除；3. 堆H2的堆顶元素就是最短调度时间；11、 运动会分数统计1)问题描述参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）2) 基本要求(1)可以输入各个项目的前三名或
21、前五名的成绩；(2)能统计各学校总分，(3)可以按学校编号、学校总分、男女团体总分排序输出；(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整型界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要
22、求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；12、 订票系统1)问题描述通过此系统可以实现如下功能：(1)录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）(2)查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；(3)订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；(4)退票： 可退票，退票后修改相关数据文件；客户
23、资料有姓名，证件号，订票数量及航班情况，订单要有编号。(5)修改航班信息：当航班信息改变可以修改航班数据文件2) 基本要求根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。 13、 文章编辑1)问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。2) 基本要求静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；14、停车场管理1)问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若
