2022年数据结构课程设计任务书计算机级 .pdf

1 福建工程学院计算机与信息科学系数据结构课程设计任务书使用班级：计算机1105-1108 使用学期： 2011-2012 学年第二学期指导老师：滕秀花、聂作先、肖琳时间： 19 周星期四至 20 周星期三地点：公教1#-201 ，202 2012 年 6 月 20 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2 一、设计目的算法与数据结构是计算机专业的核心课程，是一门实践性很强的课程。为了学好这门课程， 必须在掌握理论知识的同时，加强上机实践。 针对数据结构的课程设计不仅可以加深对课程内容的理解，并且可以通过实践进一步掌握程序设计的技能与方法，学会数据的组织方法和现实世界问题在计算机内部的表示方法，并针对问题的应用背景分析，选择最佳的数据结构和算法。 同时通过课程设计，要求学生在完成程序设计的同时能够写出比较规范的设计报告，初步感受软件开发过程的项目管理方法和规范，为进一步学习打下基础。二、设计题目:见附录 B 三、设计要求1、每人 至少选择一题完成，每道题每个班选择人数不能超过2 人。2、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝，不允许雷同。3、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。 前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。4、设计出的系统要有一个易于使用人机界面。5、源程序中应对重要程序写出注释语句四、应提交的作品1.设计报告（电子稿） ，文档书写格式可参看附录A。2.源程序。五、提交方式及要求每个人以自己的“学号姓名”形式建立文件夹，每个人的文档及源程序存放在自己的文件夹内。答辩时拷贝给指导教师检查、答辩；答辩时请先去除代码中的注释。每位同学必须通过答辩，未答辩及答辩未通过均为不及格。答辩结束后拷给学习委员，学习委员将全班的设计报告和程序收集齐后交给指导教师。六、时间安排第 19 周的星期四至20 周星期三上午，每天1-6 节。时间内容19 周四上午选定题目： 明确题目要求、 确定数据结构、 算法描述，准备测试数据等19 周四至 20 周二完成要求问题并测试、归档20 周二、周三演示回答教师提问文档及程序的整理并提交作品课程设计期间不迟到，不早退，有特殊情况要事先请假，并经有关老师批准方能有效，无故缺席者作旷课处理。进入机房，应遵守机房规定的各项制度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 3 附录 A：题目1. 基本线性表的就地逆置* 在基本线性表原有空间的基础上，将线性表中的数据元素逆置，使新的顺序序列与原来的顺序序列刚好相反。如原来顺序序列“abcdef” ，逆置之后的新顺序序列为” fedcba” 。基本要求：利用顺序结构和链式结构分别实现；操作过程必须在线性表的原有空间，不能借助临时变量所申请的临时空间，也不能借助其他形式的临时空间。2.简单排序算法的实现* 实现直接插入、冒泡排序、简单选择的排序算法。基本要求：待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用 5 组不同的输入数据(包含正序、逆序、基本有序、随机)比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3 次移动）3.排序算法的实现 * 实现直接插入、冒泡排序、简单选择、快速排序、堆排序的排序算法。基本要求：待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用 5 组不同的输入数据(包含正序、逆序、基本有序、随机)比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3 次移动）4.在链表上实现排序 * 实现直接插入、冒泡排序、简单选择的排序算法。基本要求：待排序表的表长为20000；其中的数据要用伪随机数产生程序产生；至少要用 5 组不同的输入数据比较，比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3 次移动）5.二叉排序树的创建* 输入任意的数列创建二叉排序树，并进行先序、中序、后序和层次遍历。基本要求：存储结构利用二叉链表6.哈希表 * 针对同班同学信息设计一个通讯录，学生信息有姓名，学号， 电话号码等。 以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30 个， 自行设计哈希函数和冲突处理方法 ；在查找的过程中给出比较的次数。完成按姓名查询的操作。要求：实现信息的增、删、改。将初始班级的通讯录信息存入文件，7 .校园导游程序* 设计一个校园导游程序为来访的客人提供各种信息查询服务。基本要求：（1）)设计学校的旗山校区北区校园平面图，所含场所不少于10 个。以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意场所相关信息的查询。（3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 4 要求：实现场所和路径的增加、删除。数据的保存、调入。8.航空客运订票系统* 通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）；查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况；订票： （订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，数据的存盘和调入，设计程序完成功能；9.哈夫曼编码和译码* 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是， 这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码 （复原）。对于双工信道 （即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求 :一个完整的系统应具有以下功能：（1）初始化（ Initialization ） 。从终端读入字符集大小n，以及n 个字符和n 个权值，建立哈夫曼树， (选做：并将它存于文件hfmTree 中） 。并显示出每个字符的编码。（2）编码（ Encoding） 。利用已建好的哈夫曼树（选做：如不在内存，则从文件htmTree中读入），对输入的字符串文本（选做：对文件ToBeTran 中的正文）进行编码， （选做：然后将结果存入文件CodeFile 中。 ）并显示在屏幕上。（3）译码（ Decoding） 。利用已建好的哈夫曼树将输入的代码进行译码（选做：将文件CodeFile 中的代码进行译码，结果存入文件TextFile 中。 ） ，并显示在屏幕上。（4）打印哈夫曼树（Tree Printing） 。将已在内存中的哈夫曼树以直观的方式显示在屏幕上。10.约瑟夫环问题* 要求： 输入数据：输入m的初值， n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列。任务：编号是 1，2，,n 的 n 个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自 1 开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的 m 值，从他在顺时针方向的下一个人开始重新从1 报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m 的初值为 20，n=7 ,7 个人的密码依次为3，1，7，2，4，7，4，则正确的输出是什么？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 5 11.链表的基本操作* 1 掌握线性链表的建立。2掌握线性链表的基本操作。二、设计内容和要求利作链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。12.一元稀疏多项式计算器* 基本功能定为(1) 输入并建立多项式(2) 输出多项式 ,输出形式为整数序列 :n,c1,e1,c2,e2,.,Cn,en, 其中 n是多项式的相数,Ci和 Ei 分别是第 i 项的系数和指数 ,序列按指数降序排列(3) 两个多项式相加，建立并输出和多项式(4) 两个多项式相减，建立并输出差多项式(5) 两个多项式相乘 , 建立乘积多项式(6) 计算多项式在x 处的值13.宿舍管理查询软件* 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：采用交互工作方式；建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种) 查询菜单 :（用不同的查找方法实现）按姓名查询按学号查询按房号查询14.设计一个计算机管理系统完成图书管理基本业务* 基本要求：每种书的登记内容包括书号、书名、著作者、现存量和库存量；对书号建立索引表（线性表）以提高查找效率；a) 系统主要功能如下：采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；b) 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；c) 归还：注销对借阅者的登记，改变该书的现存量。15.猴子吃桃子问题* 有一群猴子摘了一堆桃子， 他们每天都吃当前桃子的一半且再多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 6 1、采用数组数据结构实现上述求解2、采用链数据结构实现上述求解3、采用递归实现上述求解16.数制转换问题* 任意给定一个 M进制的数 x ，请实现如下要求1)求出此数 x 的 10 进制值2)实现对 x 向任意的一个非 M进制的数的转换。至少用两种或两种以上的方法实现上述要求（用栈解决， 用数组解决， 其它方法解决） 。17.学生成绩管理系统* 现有学生成绩信息文件1（1.txt） ，内容如下姓名学号语文数学英语张明明 01 67 78 82 李成友 02 78 91 88 张辉灿 03 68 82 56 王露 04 56 45 77 陈东明 05 67 38 47 , . . . . ,学生成绩信息文件2（ 2.txt） , 内容如下 : 姓名学号语文数学英语陈果 31 57 68 82 李华明 32 88 90 68 张明东 33 48 42 56 李明国 34 50 45 87 陈道亮 35 47 58 77 , . . . . ,试编写一管理系统, 要求如下 : 1、 实现对两个文件数据进行合并, 生成新文件3.txt 2、 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt 3、 对合并后的文件3.txt中的数据按总分降序排序( 至少采用两种排序方法实现) 4、 输入一个学生姓名后, 能查找到此学生的信息并输出结果( 至少采用两种查找方法实现) 5、 要求使用结构体, 链或数组等实现上述要求. 18.教学计划安排检验程序（拓扑排序）* 本次课程设计的任务是：针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。(1) 输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于 8，课程名的长度小于等于10 个字符。(2) 程序所能达到的功能：按照用户的输入，给出每学期应学的课程。(4) 测试数据：输入：学期数：，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 7 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 学期应学的课程：v7 19.停车场问题 * 停车场是一条可以停放n 辆车的狭窄通道， 且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端）若停车场已经停满n辆车， 后来的汽车在便道上等候，一旦有车开走， 排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要安时间长短缴费。要求：以栈模拟停车场，以队列车场外的便道， 按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为： 若是车辆到达， 则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现。20. 括号匹配情况* 假设在一个算术表达式中，可以包含三种括号：圆括号（和），方括号 和 和花括 号 和 ， 并 且 这 三 种 括 号 可 以 按 任 意 的 次 序 嵌 套 使 用 。 比如， .(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。（1）当遇到某一个右括号时，栈已空，说明到目前为止， 右括号多于左括号； （2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。要求用栈完成。21. 商品货架管理* 商店货架以栈的方式摆放商品。商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。生产日期越接近的越靠栈底，出货时从栈顶取货。一天营业结束，如果货架不满， 则需上货。 入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。 这样就需要倒货架，使生产日期越近的越靠近栈底。请编写程序模拟商品销售，上架倒货架等操作。 （设有 5 种商品，每种商品至少有商品名和生产日期两个属性）22.稀疏矩阵的快速转置* 利用三元组表存储稀疏矩阵，利用快速转置算法进行转置，并输出转置之前和之后的三元组表以及矩阵。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 8 附录 B:报告福建工程学院课程设计课程：题目：专业：班级：座号：姓名：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 9 实验题目：求迷宫的最短路径一、要解决的问题这是实验心理学中的一个经典问题， 心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。 迷宫中设置很多隔壁， 对前进方向形成了多处障碍， 心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。我们要解决的是如何找到了一条迷宫的最短路径。二、算法基本思想描述：要用到回溯的思想。 从迷宫入口点出发， 向四周搜索， 记下所有一步能到达的坐标点；然后依次从这些点出发，再记下所有一步能到达的坐标点，. .依此类推，直到到达迷宫的出口点为止，然后从迷宫出口点沿搜索路径回溯。这样就找到了一条迷宫的最短路径，否则迷宫无路径。 由于先到达的点先搜索， 故用先进先出的数据结构 队列来保存已到达的坐标点。三、设计1. 数据结构的设计（1）迷宫的表示设迷宫为 m行 n 列，利用 mazemn 来表示迷宫， mazemn=0 或 1，其中 0表示通路， 1 表示不通。入口坐标（ 1，1） ，出口坐标（ m,n）. 迷宫定义如下： #define m 6 #define n 8 int mazem+2n+2；（2）试探方向的表示在迷宫中有 8 个方向可以试探， 规定：从当前位置向前试探的方向为从正东开始沿顺时针方向进行。 为了简化问题， 将这 8 个方向的坐标增量放在一个结构数组 move8 中。在 move数组中，每个元素有两个域组成，X：横坐标增量；Y：纵坐标增量。Move数组定义如下：typedef struct int x,y;item; item move8= 0,1, 1,1, 1,0, 1,-1,0,-1, -1,-1,-1,0,-1,1 ; （3）队列的表示在找到出口点之后，需要沿搜索路径回溯，所以到达某点时，不仅要记下该点的坐标，还要记下该点的前驱。用一个结构数组sqnum 作为队列的存储序号X Y 0 0 1 1 1 1 2 1 0 3 1 -1 4 0 -1 5 -1 -1 6 -1 0 7 -1 1 (x,y) (x-1,y) (x+1,y) (x-1,y+1) (x,y+1) (x+1,y+1) (x-1,y-1) (x,y-1) (x+1,y-1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 10 空间。Sq的每一个结构有三个域： x,y,pre,其中 x，y 分别为所到达的点的坐标，pre 为前驱点的坐标。还设队头front和队尾 rear 指针。 #define num 50 typedef struct int x,y； int pre; SqType; SqType sqnum ；int front，rear ；2. 算法的设计（1）求最短路径的算法设计01110111101010100100111101110011100110000110011012345678123456（1 ， 1 ）（2 ， 2 ）（3 ， 3 ）（ 3 ，1 ）（ 3 ， 4 ）（ 2 ，4 ）（4 ，5 ）（ 1 ，5 ）（ 4 ，1 ）（ 5 ，2 ）（4 ， 6 ）（5 ，6 ）（ 2 ，6 ）（ 5 ，3 ）（5 ， 7 ）（6 ，5 ）（ 6 ，4 ）（ 5 ，8 ）（ 6 ，8 ）初始状态，队列中只有一个元素sq1, 记录的是入口点的坐标（ 1，1） ，因为该点是出发点，因此没有直接前驱点，pre 域为-1，队头指针 front的队尾指针 rear 均指向它，此后搜索时都是以front所指点为搜索的出发点，即将该点的坐标及 front所指点的位置入队， 这样不但记下了到达点的坐标，还记下了它的前驱点。Front 所指向点的 8 个方向搜索完毕后， 则出队，继续对下一点搜索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫的最短路径，算法结束；或者当前队空，既没有搜索点了，表明没有路径，算法也结束。（2）防止重复到达某点的考虑为避免发生死循环，当到达某点（i ，j ）后，使mazeij置-1，以便区分未到达过的顶点。算法结束前可恢复原迷宫。（3）队列头、尾指针的指向队头指针指向搜索的出发点，当找到一个可到达点， 就入队；当 8 个方位都搜索完毕， 队头指针往后移一个 （出队，但原位置值依然存在， 方便最后回溯）。（4）模块结构及功能：主程序队列初始化打印路径迷宫初始化求最短路经名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 11 a)void main() /主程序b)viod init_maze(int) /迷宫的初始化c)void init_queue(SqType) /队列的初始化d)int path(int,int) /求迷宫的最短路径e)void print_path(SqType,rear) /打印路径f)void in_queue(SqType ,datatype) /入队操作g)void out_queue(SqType) /出队操作h)int empty_queue(SqType) /判队空（5）主要模块算法描述求迷宫最短路径的算法描述：path(int maze,int move) 队列头、尾指针初始化（=-1） ；将入口点的前驱设置为 -1，入队；将入口点设置为已走过；将是否找到出口点信息found 赋值为 0（未找到）； while （未找到 & 队列非空） 队头指针后移指向当前搜索点，并将它赋值给x； for i=1 to 8 搜索 x 点的 8个方向 if（找到一个可走点） 就将该点坐标及前驱值（ front ）入队；将该点设置为已走过； 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,1, 1,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) 六、课程设计总结及心得体会：可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -