数据结构课程设计任务书(信管15

《数据结构课程设计任务书(信管15》由会员分享，可在线阅读，更多相关《数据结构课程设计任务书(信管15（25页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计任务书（信管 福建工程学院计算机与信息科学系数据结构课程设计任务书使用班级：信管1501、1502使用学期：2015-2016学年第二学期指导老师：滕秀花、菜沛伟时间：17周星期四至18周星期三地点：公教2015 年 6 日一、设计目的算法与数据结构是计算机专业的核心课程，是一门实践性很强的课程。为了学好这门课 程,必须在掌握理论知识的同时，加强上机实践。针对数据结构的课程设计不仅可以加深对课程 内容的理解，并且可以通过实践进一步掌握程序 设计的技能与方法，学会数据的组织方法和现实 世界问题在计算机内部的表示方法，并针对问题 的应用背景分析，选择最佳的数据结构和算法。同时通过课

2、程设计，要求学生在完成程序设计的 同时能够写出比较规范的设计报告，初步感受软 件开发过程的项目管理方法和规范，为进一步学 习打下基础。二、设计题目:见附录B三、设计要求1、每人至少选择一题完成，每生至少完成一题C 语言成绩2、独立思考，独立完成：课程设计中各任务的 设计和调试要求独立完成，遇到问题可以讨论 但不可以拷贝，不允许雷同。3、在处理每个题目时，要求从分析题目的需求 入手，按设计抽象数据类型、构思算法、通过类 的设计实现抽象数据类型、编制上机程序和上机 调试等若干步骤完成题目，最终写出完整的分析 报告。前期准备工作完备与否直接影响到后序上 机调试工作的效率。在程序设计阶段应尽量利用 已

3、有的标准函数，加大代码的重用率。4、设计出的系统要有一个易于使用人机界面5、源程序中应对重要程序写出注释语句四、应提交的作品1. 设计报告（电子稿），文档书写格式可参看 附录Ao2. 源程序。五、提交方式及要求每个人以自己的“学号姓名”形式建立文件 夹，每个人的文档及源程序存放在自己的文件夹 内。答辩时拷贝给指导教师检查、答辩； 答辩时 请先去除代码中的注释。每位同学必须通过答辩，未答辩及答辩未通 过均为不及格。答辩结束后拷给学习委员，学习委员将全班的设计报告和程序收集齐后交给指导教师。六、时间安排第19周的星期四至20周星期三上午，每天1-6 节。时间17 周四至 18 周二18周二、周三内

4、容17周四上午选定题目：明确题目要求、 确定数据结构、算法描述， 准备测试数据等 完成要求问题并测试、归档 演示回答教师提问文档及 程序的整理并提交作品 课程设计期间不迟到，不早退，有特殊情况 要事先请假，并经有关老师批准方能有效，无故 缺席者作旷课处理。进入机房，应遵守机房规定的各项制度。A组：1在顺序存储实现如下排序算法 实现直接插入、冒泡排序、简单选择的排序 算法。基本要求： 待排序表的表长为 20000；其中 的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据（包含正序、逆序、基本有序、 随机）比较；比较的指标为有关键字参加的比较 次数和关键字移动次数（关键字交换计为3次移

5、动）2在链表上实现排序实现直接插入、冒泡排序、简单选择的排序算法。基本要求：待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据比较，比较的指标为有关键字 参加的比较次数和关键字移动次数（关键字交换 计为3次移动） 3二叉排序树的创建输入任意的数列创建二叉排序树，并进行先序、 中序、后序和层次遍历（用顺序队列辅助遍历）。 基本要求：存储结构利用二叉链表4链表的基本操作利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成 函数的形式），并能在屏幕上输出操作前后的结果。5宿舍管

6、理查询软件任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：采用交互工 作方式；建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序（冒 泡、选择、插入排序等任选一种） 查询菜单:（用不同的查找方法实现）按姓名查询 按学号查询 按房号查询6. 商品货架管理商店货架以栈的方式摆放商品。商品货架可 以看成一个栈，栈顶商品的生产日期最早，栈底 商品的生产日期最近。生产日期越接近的越靠栈 底，出货时从栈顶取货。一天营业结束，如果货 架不满，则需上货。入货直接将商品摆放到货架 上，则会使生产日期越近的商品越靠近栈顶。这 样就需要倒货架，使生产日期越近的越靠近栈 底。请编写程序模拟商品

7、销售，上架倒货架等操 作。（设有5种商品，每种商品至少有商品名和 生产日期两个属性） 7稀疏矩阵的快速转置*利用三元组表存储稀疏矩阵，利用快速转置 算法进行转置，并输出转置之前和之后的三元组 表以及矩阵。8. 背包问题有n项可投资的项目，每个项目需要投入资金s, 可获利润为vi，现有可用资金总数为M,应选择哪些项目来投资，才能获得最大利润9. 看病排队候诊医院各科室的医生有限，因此病人到医院看病 时必须排队候诊，而病人病情有轻重之分不能简 单地根据先来先服务的原则进行诊断治疗，所以 护士根据病人的病情规定了不同的优先级别。医 生在诊断治疗时，总是选择优先级高的病人进行 诊治，如果遇到两个优先级

8、别相同的病人，贝燧 择最先来排队的病人进行诊治。10. 恢复二叉树IWJIJJJJ已知二叉树的先根遍历结果和中序编列结果, 恢复二叉树，并后根遍历该二叉树B组:i排序算法的实现实现直接插入、冒泡排序、简单选择、快速 排序、堆排序的排序算法。基本要求：待排序表的表长为20000；其中 的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据（包含正序、逆序、基本有序、 随机）比较；比较的指标为有关键字参加的比较 次数和关键字移动次数（关键字交换计为 3次移动） 2哈希表针对同班同学信息设计一个通讯录，学生信息 有姓名，学号，电话号码等。以学生姓名为关 键字设计哈希表,并完成相应的建表和查表程

9、 序。基本要求：姓名以汉语拼音形式，待填入哈 希表的人名约30个，自行设计哈希函数和冲突 处理方法；在查找的过程中给出比较的次数。完 成按姓名查询的操作。要求：实现信息的增、删、改。将初始班级 的通讯录信息存入文件，3 校园导游程序设计一个校园导游程序为来访的客人提供各 种信息查询服务。（校园平面是一个无向网）基本要求：（1）设计学校的旗山校区北区校园平面图， 所含场所不少于10个。以图中顶点表示校内各 场所，存放场所名称、代号、简介等信息；以边 表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意场所相关信息的查询。3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的

10、一条最短的简单 路径。要求：实现场所和路径的增加、删除。数据 的保存、调入。4航空客运订票系统通过此系统可以实现如下功能： 录入：可以录入航班情况（数据可以存储在一个 数据文件中，数据结构、具体数据自定）； 查询：可以査询某个航线的情况（如，输入航 班号，查询起降时间，起飞抵达城市，航 班票价，票价折扣，确定航班是否满仓）; 可以输入起飞抵达城市，查询飞机航班情 况； 订票：（订票情况可以存在一个数据文件中，结 构自己设定）可以订票，如果该航班已经无票, 可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客 户资料有姓名，证件号，订票数量及航班情况, 订单要有编号。修改航班信息：

11、当航班信息改变可以修改航班数据文件要求： 根据以上功能说明，设计航班信息， 订票信息的存储结构，数据的存盘和调入，设计 程序完成功能； 5哈夫曼编码和译码利用哈夫曼编码进行信息通信可以大大提 高信道利用率，缩短信息传输时间，降低传输成 本。但是，这要求在发送端通过一个编码系统对 待传数据预先编码，在接收端将传来的数据进行 译码（复原）。对于双工信道（即可以双向传输 信息的信道），每端都需要一个完整的编/译码系 统。试为这样的信息收发站写一个哈夫曼编/译 码系统。基本要求:一个完整的系统应具有以下功能：（1）初始化（Initialization）o从终端读入字 符集大小n，以及n个字符和n个权值

12、，建立哈 夫曼树，（选做：并将它存于文件hfmTree中）。 并显示出每个字符的编码。（2）编码（Encoding）。利用已建好的哈夫 曼树（选做：如不在内存，则从文件htmTree 中读入），对输入的字符串文本（选做：对文件ToBeTran中的正文）进行编码，（选做：然后将结果存入文件CodeFile中。并显示在屏幕上。(3) 译码(Decoding)o利用已建好的哈夫 曼树将输入的代码进行译码(选做：将文件 CodeFile中的代码进行译码，结果存入文件 TextFile中。)，并显示在屏幕上。(4) 打印哈夫曼树(Tree Printing)。将程序中的哈夫曼树以直观的方式显示在屏幕上。

13、6元稀疏多项式计算器基本功能定为(i)输入并建立多项式 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,Cn,en,其中n是多项式的 相数,Ci和Ei分别是第i项的系数和指数,序列按指数降序排列 两个多项式相加，建立并输出和多项式(4)两个多项式相减，建立并输出差多项式两个多项式相乘，建立乘积多项式计算多项式在x处的值7. 学生成绩管理系统现有学生成绩信息文件1 (1.txt)，内容如下学生成绩信息文件2(2.txt),内容如下:姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847 姓名学号语文数学英语陈果

14、31576882李华明32889068张明东33484256李明国34504587陈道亮35475877试编写一管理系统，要求如下：1、实现对两个文件数据进行合并，生成新文件 3.txt2、抽取出三科成绩中有补考的学生并保存在 一个新文件4.tx t3、对合并后的文件3.txt中的数据按总分降 序排序（至少采用两种排序方法实现：插入， 希尔，冒泡，快速，堆）4、输入一个学生姓名后，能查找到此学生的信 息并输出结果（至少采用两种査找方法实现： 顺序，折半，二叉排序，哈希表）5、要求使用结构体，链或数组等实现上述要 求.8. 教学计划安排检验程序（拓扑排序） 本次课程设计的任务是：针对学院的计算机

15、系本科课程，根据课程之间的依赖关系，制定课程安排计划， 并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两 间的先后关系，程序执行后会给出每学期应学的课程。(1) 输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于 20，学期数小于或是等 于 8，课程名的长度小于等于 10 个字符。 程序所能达到的功能：按照用户的输入，给出每学期应学的课程。测试数据：输入：学期数：5,课程数：12,课程间的先后关系数：16,课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,

16、v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11 v6输出：第1学期应学的课程：v1 v9第2学期应学的课程：v2 v4 v10 v11第3学期应学的课程：v3 v6 v12第4学期应学的课程：v5 v8第5学期应学的课程：v79停车场问题停车场是一条可以停放n辆车的狭窄通道， 且只有一个大门汽车停放安到达时间的先后依 次由北向南排列(大门在最南端，最先到达的第 一辆车停在最北端)若停车场已经停满n辆车， 后来的汽车在便道上等候，一旦有车开走，排在

17、 便道上的第一辆车可以开入；当停车场的某辆车 要离开时，停在他后面的车要先后退为他让路， 等它开岀后其他车在按照原次序开入车场，每两 停在车场的车要安时间长短缴费。要求：以栈 模拟停车场，以队列车场外的便道，按照从终端 输入的数据序列进行模拟管理。每一组数据包括 三个数据项：汽车“到达”或“离去”信息、汽 车牌照号码、以及到达或离去的时刻。对每一组 数据进行操作后的信息为：若是车辆到达，则输11出汽车在停车场的内或便道上的位置：若是车辆 离去则输出汽车在停车场内的停留时间和应缴 纳的费用（在便道上的停留时间不收费）。栈以 顺序结构实现，队列以链表结构实现。10括号匹配情况*假设在一个算术表达式

18、中，可以包含三种括号：圆括号（和），方括号丫和和花括 号和尸，并且这三种括号可以按任意的次序 嵌套使用。比如,（）。现在需要设计一个算法，用来检验在输入的算术 表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现 左括号，必有相应的右括号与之匹配，并且每对 括号之间可以嵌套，但不能出现交叉情况。我们 可以利用一个栈结构保存每个出现的左括号，当 遇到右括号时，从栈中弹出左括号，检验匹配情 况。在检验过程中，若遇到以下几种情况之一， 就可以得出括号不匹配的结论。（1）当遇到某一 个右括号时，栈已空，说明到目前为止，右括号 多于左括号；（2）从栈中弹出的左括号与当前检 验的右括号类型不

19、同，说明出现了括号交叉情 况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。要求用 栈完成。11、最小生成树给定一个地区的n个城市间的距离网，建立最小 生成树，并计算得到的最小生成树的代价。要求 如下： 城市间的距离网采用邻接矩阵表示，邻接矩阵 的存储结构定义采用教材给出定义，若两个城市 之间不存在道路，则将相应边的权值设为自己定 义的无穷大值。要求在屏幕上显示得到的最小生 成树中包括了哪些城市间的道路，并显示得到的 最小生成树的代价；11 表示城市间距离网的邻接矩阵（要求至少6个 城市，10条边） 最小生成树中包括的边及其权值，并显示得到 的最小生成树的代价。1

20、2. 空间最近点对在空中交通控制问题中，若将飞机作为空间中移 动的一个点来处理，则求出具有最大碰撞危险的 两架飞机。（提示：即空间中最接近的一对点，求平面即可）13. 假币检查1）在 n 枚外观相同的硬币中，有一枚是假币， 并且已知假币较轻。可以通过一架天平来任意比 较两组硬币，从而得硬币的重量是否相同，或者 哪一组更轻一些，假币问题要求设计一个算法来 检测出这枚假币。（2）在120枚外观相同的硬币中，有一枚是假 币，并且已知假币与真币的重量不同，但不知道 假币与真币相比较轻还是重。可以通过一架天平 来任意比较两组硬币，最坏情况下，能不能只比 较5次就检测出这枚假币。14拿子游戏 考虑下面这个

21、游戏：桌子上有一堆火柴，游戏开 始时共有n根火柴，两个玩家轮流拿走1根、2 根、3根或4根火柴，拿走最后火柴的玩家为获 胜方。请为先走的玩家设计一个制胜的策略（如 果该策略存在）。15猴子分桃 问题描述:动物园里的n只猴子编号为 1,2,3, ，n，依次排成一队等待饲养员按规则 分桃。动物园的分桃规则是每只猴子可分得个桃子，但必须排队领取。饲养员循环地每次取 出一个，2给，k个桃放入筐中，由排在队 首的猴子领取。取到筐中的桃子数为k后，又重 新从 1开始。当筐中桃子数加上队首猴子可取的 桃子数不超过m时，队首的猴子可以全部取得 饲养员手中桃子；取得桃子总数不足m个桃子， 继续到队尾排队等候。当

22、筐中桃子数加上队首猴 子可取的桃子数超过m时，队首的猴子只能取 满m个，然后离开队列，筐中剩余桃子由下一 直猴子取用。上述分桃过程一直进行到每只猴子 都分到m个桃子。实验任务：对于给定的n,k和m，模拟上述猴子分桃过程输入5,3,40输岀：1 3 5 2 416.KMP算法求一个字符串在另一个字符串中第一次出现的 位置。17模仿阵724161475236183T22-?2064打294121092251811魔方阵是一个古老的智力问题，它要求在一个m*m的矩阵中填入1m2的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相 等。要求：输入m,实现，输出18家族关系查询系统si建立家族

23、关系数据库，实现对家族成员关系的相 关查询要求：建立家族关系能存储到文件中；实现家族 成员的添加（双亲最多2个孩子）；可以查询家 族成员的双亲、祖先、兄弟、孩子和后代信息。 提示：树状结构可以用三叉链表。附录B:报告福建工程学院课程设计课程：题目专 业：班级：座 号：姓名：实验题目：求迷宫的最短路径一、要解决的问题 这是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的 大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍， 心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以 达到出口。我们要解决的是如何找到了一条迷宫的最短路径。二、算法基本思想描述

24、：要用到回溯的思想。从迷宫入口点出发，向四周搜索，记下所有一步能到 达的坐标点；然后依次从这些点出发，再记下所有一步能到达的坐标点，依此类推，直到到达迷宫的出口点为止，然后从迷宫出口点沿搜索路径回溯。 这样就找到了一条迷宫的最短路径，否则迷宫无路径。由于先到达的点先搜索, 故用先进先出的数据结构一队列来保存已到达的坐标点。三、设计1. 数据结构的设计（1）迷宫的表示设迷宫为m行n列，利用mazemn来表示迷宫，mazemn=O或1,其中0 表示通路，1表示不通。入口坐标（1，1），出口坐标（m,n）迷宫定义如下：#define m 6#define n 8int mazem+2n+2；（2）试

25、探方向的表示在迷宫中有8个方向可以试探，规定：从当前位置向前试探的方向为从正东 开始沿顺时针方向进行。为了简化问题，将这8个方向的坐标增量放在一个结 构数组move8中。在move数组中，每个元素有两个域组成，X：横坐标增量;Y：纵坐标增量。序 号XY0011112100,1, 1,1, 1,0,z(X-(XT(x-l/ (x,(X(X,(x+/ ”(x+1,(x+Move数组定义如下：typedef struetint x,y;item;item move8=1,-1,0,-1,-1,-1,-1,0,-1,1 ;3）队列的表示在找到出口点之后，需要沿搜索路径回溯，所以到达某点时，不仅要记下

26、该点的坐标，还要记下该点的前驱。用一个结构数组sqnum作为队列的存储 空间。Sq的每一个结构有三个域：x,y,pre，其中x, y分别为所到达的点的坐 标，pre为前驱点的坐标。还设队头front和队尾rear指针。#define num 50typedef struetin t x,y；int pre;SqType;SqType sqnum；int front, rear；2. 算法的设计（1）求最短路径的算法设计(2 , 2 )123456781、1110 X1112110丿f屯1030*1L11141110-115”011、060*111k00*1(4 ,4 )(4 , 5 )6 )

27、( 5 , 6 )(5 ,(2(1 )1 )(5 , 2 )5 ,3 )初始状态，队列中只有一个元素sq1,记录的是入口点的坐标（1, 1）,因 为该点是出发点，因此没有直接前驱点，pre域为-1,队头指针front的队尾指 针rear均指向它，此后搜索时都是以front所指点为搜索的出发点，即将该点 的坐标及front所指点的位置入队，这样不但记下了到达点的坐标，还记下了 它的前驱点。Front所指向点的8个方向搜索完毕后，则出队，继续对下一点搜 索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫的最短路径，算法 结束；或者当前队空，既没有搜索点了，表明没有路径，算法也结束。（2）防止重复

28、到达某点的考虑为避免发生死循环，当到达某点（i，j）后，使mazeij置-1,以便区 分未到达过的顶点。算法结束前可恢复原迷宫。（3）队列头、尾指针的指向队头指针指向搜索的出发点，当找到一个可到达点，就入队；当 8个方位 都搜索完毕，队头指针往后移一个（出队，但原位置值依然存在，方便最后回 溯）。（4）模块结构及功能：主程序d）e）f）g）h）a) void main()S始化V d _in it丄quint pat h(i nt,int)void pri nt_pat h(SqType,re*r) void invoid out_queue(SqType)int empty_queue(Sq

29、Type)初始化_ 主程序 求最初始化求初始化打印路径/求迷宫的最短路径/打印路径_queue（SqType ,（入队3卩。）| /入队队操作 判队空作判队空主要模块算法描述求迷宫最短路径的算法描述: pat h（int maze,i nt move） 队列头、尾指针初始化（=-1）; 将入口点的前驱设置为-1,入队； 将入口点设置为已走过； 将是否找到出口点信息found赋值为0 （未找到）； while （未找到&队列非空）队头指针后移指向当前搜索点，并将它赋值给x； for i=1 to 8搜索x点的8个方向 if （找到一个可走点）就将该点坐标及前驱值（fron t）入队; 将该点设置

30、为已走过；if （该点是出口点）found=1； if（找到）回溯打印最短路径；else打印“该迷宫没有路径”； 四、源程序清单：（略）五、测试数据及测试结果：例如：测试数据：mazem+2n+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,11,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1;测试结果：(6,8) (5,7) (4,6) (4,5) (3,4)(3,3) (2,2) (1,1) 六、课程设计总结及心得体会：可以包括：课程设计过程的收获、遇到问题、 遇到问题解决问题过程的思考、程序调试能力的 思考、对数据结