数据结构专业课程设计任务计划书

福建工程学院计算机和信息科学系《数据结构课程设计》任务书使用班级：信管1501、1502使用学期：-第二学期指导老师：滕秀花、菜沛伟时间：17周星期四至18周星期三地点：公教6日

一、设计目标《算法和数据结构》是计算机专业关键课程，是一门实践性很强课程。为了学好这门课程，必需在掌握理论知识同时，加强上机实践。针对数据结构课程设计不仅能够加深对课程内容了解，而且能够经过实践深入掌握程序设计技能和方法，学会数据组织方法和现实世界问题在计算机内部表示方法，并针对问题应用背景分析，选择最好数据结构和算法。同时经过课程设计，要求学生在完成程序设计同时能够写出比较规范设计汇报，初步感受软件开发过程项目管理方法和规范，为深入学习打下基础。二、设计题目:见附录B三、设计要求1、每人最少选择一题完成，每生最少完成一题。C语言成绩2、独立思索，独立完成：课程设计中各任务设计和调试要求独立完成，碰到问题能够讨论，但不能够拷贝，不许可雷同。3、在处理每个题目时，要求从分析题目标需求入手，按设计抽象数据类型、构思算法、经过类设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整分析汇报。前期准备工作完备是否直接影响到后序上机调试工作效率。在程序设计阶段应尽可能利用已经有标准函数，加大代码重用率。4、设计出系统要有一个易于使用人机界面。5、源程序中应对关键程序写出注释语句四、应提交作品设计汇报（电子稿），文档书写格式可参看附录A。源程序。五、提交方法及要求每个人以自己“学号姓名”形式建立文件夹，每个人文档及源程序存放在自己文件夹内。答辩时拷贝给指导老师检验、答辩；答辩时请先去除代码中注释。每位同学必需经过答辩，未答辩及答辩未经过均为不及格。答辩结束后拷给学习委员，学习委员将全班设计汇报和程序搜集齐后交给指导老师。六、时间安排第19周星期四至20周星期三早晨，天天1-6节。时间内容17周四早晨选定题目：明确题目要求、确定数据结构、算法描述，准备测试数据等17周四至18周二完成要求问题并测试、归档18周二、周三演示回复老师提问文档及程序整理并提交作品课程设计期间不迟到，不早退，有特殊情况要事先请假，并经相关老师同意方能有效，无故缺席者作旷课处理。进入机房，应遵守机房要求各项制度。A组：1.在次序存放实现以下排序算法实现直接插入、冒泡排序、简单选择排序算法。基础要求：待排序表表长为0；其中数据要用伪随机数产生程序产生；最少要用5组不一样输入数据(包含正序、逆序、基础有序、随机)比较；比较指标为相关键字参与比较次数和关键字移动次数（关键字交换计为3次移动）2.在链表上实现排序实现直接插入、冒泡排序、简单选择排序算法。基础要求：待排序表表长为0；其中数据要用伪随机数产生程序产生；最少要用5组不一样输入数据比较，比较指标为相关键字参与比较次数和关键字移动次数（关键字交换计为3次移动）3.二叉排序树创建输入任意数列创建二叉排序树，并进行先序、中序、后序和层次遍历（用次序队列辅助遍历）。基础要求：存放结构利用二叉链表4.链表基础操作利作链表插入运算建立线性链表，然后利用链表查找、删除、计数、输出等运算反复实现链表这些操作（插入、删除、查找、计数、输出单独写成函数形式），并能在屏幕上输出操作前后结果。5.宿舍管理查询软件任务：为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求：采取交互工作方法；建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一个)查询菜单:（用不一样查找方法实现）按姓名查询按学号查询按房号查询6.商品货架管理商店货架以栈方法摆放商品。商品货架能够看成一个栈，栈顶商品生产日期最早，栈底商品生产日期最近。生产日期越靠近越靠栈底，出货时从栈顶取货。一天营业结束，假如货架不满，则需上货。入货直接将商品摆放到货架上，则会使生产日期越近商品越靠近栈顶。这么就需要倒货架，使生产日期越近越靠近栈底。请编写程序模拟商品销售，上架倒货架等操作。（设有5种商品，每种商品最少有商品名和生产日期两个属性）7.稀疏矩阵快速转置**利用三元组表存放稀疏矩阵，利用快速转置算法进行转置，并输出转置之前和以后三元组表和矩阵。8．背包问题有n项可投资项目，每个项目需要投入资金s，可赢利润为vi，现有可用资金总数为M，应选择哪些项目来投资，才能取得最大利润。9.看病排队候诊医院各科室医生有限，所以病人到医院看病时必需排队候诊，而病人病情有轻重之分不能简单地依据先来先服务标准进行诊疗诊疗，所以护士依据病人病情要求了不一样优先等级。医生在诊疗诊疗时，总是选择优先级高病人进行诊治，假如碰到两个优先等级相同病人，则选择最先来排队病人进行诊治。10.恢复二叉树已知二叉树先根遍历结果和中序编列结果，恢复二叉树，并后根遍历该二叉树B组：1.排序算法实现实现直接插入、冒泡排序、简单选择、快速排序、堆排序排序算法。基础要求：待排序表表长为0；其中数据要用伪随机数产生程序产生；最少要用5组不一样输入数据(包含正序、逆序、基础有序、随机)比较；比较指标为相关键字参与比较次数和关键字移动次数（关键字交换计为3次移动）2．哈希表针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成对应建表和查表程序。基础要求：姓名以汉语拼音形式，待填入哈希表人名约30个，自行设计哈希函数和冲突处理方法；在查找过程中给出比较次数。完成按姓名查询操作。要求：实现信息增、删、改。将初始班级通讯录信息存入文件，3.校园导游程序设计一个校园导游程序为来访客人提供多种信息查询服务。（校园平面是一个无向网）基础要求：（1）)设计学校旗山校区北区校园平面图，所含场所不少于10个。以图中顶点表示校内各场所，存放场所名称、代号、介绍等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意场所相关信息查询。（3）为来访客人提供图中任意场所问路查询，即查询任意两个景点之间一条最短简单路径。要求：实现场所和路径增加、删除。数据保留、调入。4.航空客运订票系统经过此系统能够实现以下功效：录入：能够录入航班情况（数据能够存放在一个数据文件中，数据结构、具体数据自定）；查询：能够查询某个航线情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；能够输入起飞抵达城市，查询飞机航班情况；订票：（订票情况能够存在一个数据文件中，结构自己设定）能够订票，假如该航班已经无票，能够提供相关可选择航班；退票：可退票，退票后修改相关数据文件；用户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变能够修改航班数据文件要求：依据以上功效说明，设计航班信息，订票信息存放结构，数据存盘和调入，设计程序完成功效；5.哈夫曼编码和译码利用哈夫曼编码进行信息通信能够大大提升信道利用率，缩短信息传输时间，降低传输成本。不过，这要求在发送端经过一个编码系统对待传数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信道（即能够双向传输信息信道），每端全部需要一个完整编/译码系统。试为这么信息收发站写一个哈夫曼编/译码系统。基础要求:一个完整系统应含有以下功效：（1）初始化（Initialization）。从终端读入字符集大小n，和n个字符和n个权值，建立哈夫曼树，(选做：并将它存于文件hfmTree中）。并显示出每个字符编码。（2）编码（Encoding）。利用已建好哈夫曼树（选做：如不在内存，则从文件htmTree中读入），对输入字符串文本（选做：对文件ToBeTran中正文）进行编码，（选做：然后将结果存入文件CodeFile中。）并显示在屏幕上。（3）译码（Decoding）。利用已建好哈夫曼树将输入代码进行译码（选做：将文件CodeFile中代码进行译码，结果存入文件TextFile中。），并显示在屏幕上。（4）打印哈夫曼树（TreePrinting）。将程序中哈夫曼树以直观方法显示在屏幕上。6.一元稀疏多项式计算器基础功效定为

(1)输入并建立多项式

(2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,.....,Cn,en,其中n是多项式相数,Ci和Ei分别是第i项系数和指数,序列按指数降序排列

(3)两个多项式相加，建立并输出和多项式

(4)两个多项式相减，建立并输出差多项式

(5)两个多项式相乘,建立乘积多项式

(6)计算多项式在x处值7.学生成绩管理系统现有学生成绩信息文件1（1.txt），内容以下姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847….......…学生成绩信息文件2（2.txt）,内容以下:姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国34504587陈道亮35475877….......…试编写一管理系统,要求以下:实现对两个文件数据进行合并,生成新文件3.txt抽取出三科成绩中有补考学生并保留在一个新文件4.txt对合并后文件3.txt中数据按总分降序排序(最少采取两种排序方法实现：插入，希尔，冒泡，快速，堆)输入一个学生姓名后,能查找到此学生信息并输出结果(最少采取两种查找方法实现：次序，折半，二叉排序，哈希表)要求使用结构体,链或数组等实现上述要求.8.教学计划安排检验程序（拓扑排序）此次课程设计任务是：针对学院计算机系本科课程，依据课程之间依靠关系，制订课程安排计划，并满足各学期课程数大致相同。根据用户输入课程数，学期数，课程间前后关系数目和课程间两两间前后关系，程序实施后会给出每学期应学课程。

(1)输入形式和输入值范围：输入间用空格隔开。要求用户输入课程数小于20，学期数小于或是等于8，课程名长度小于等于10个字符。

(2)程序所能达成功效：根据用户输入，给出每学期应学课程。

(4)测试数据：输入：学期数：５，课程数：12，课程间前后关系数：16，课程代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间前后关系：v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6

输出：第1学期应学课程：v1v9

第2学期应学课程：v2v4v10v11

第3学期应学课程：v3v6v12

第4学期应学课程：v5v8

第5学期应学课程：v7

9.停车场问题停车场是一条能够停放n辆车狭窄通道，且只有一个大门汽车停放安抵达时间前后依次由北向南排列（大门在最南端，最先抵达第一辆车停在最北端）若停车场已经停满n辆车，以后汽车在便道上等候，一旦有车开走，排在便道上第一辆车能够开入；当停车场某辆车要离开时，停在她后面车要前后退为她让路，等它开出后其它车在根据原次序开入车场，每两停在车场车要安时间长短缴费。要求：以栈模拟停车场，以队列车场外便道，根据从终端输入数据序列进行模拟管理。每一组数据包含三个数据项：汽车“抵达”或“离去”信息、汽车牌照号码、和抵达或离去时刻。对每一组数据进行操作后信息为：若是车辆抵达，则输出汽车在停车场内或便道上位置：若是车辆离去则输出汽车在停车场内停留时间和应缴纳费用（在便道上停留时间不收费）。栈以次序结构实现，队列以链表结构实现。10.括号匹配情况***假设在一个算术表示式中，能够包含三种括号：圆括号"（"和"）"，方括号"["和"]"和花括号"{"和"}"，而且这三种括号能够按任意次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入算术表示式中所使用括号正当性。算术表示式中多种括号使用规则为：出现左括号，必有对应右括号和之匹配，而且每对括号之间能够嵌套，但不能出现交叉情况。我们能够利用一个栈结构保留每个出现左括号，当碰到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若碰到以下多个情况之一，就能够得出括号不匹配结论。（1）当碰到某一个右括号时，栈已空，说明到现在为止，右括号多于左括号；（2）从栈中弹出左括号和目前检验右括号类型不一样，说明出现了括号交叉情况；（3）算术表示式输入完成，但栈中还有没有匹配左括号，说明左括号多于右括号。要求用栈完成。11、最小生成树给定一个地域n个城市间距离网，建立最小生成树，并计算得到最小生成树代价。要求以下：①城市间距离网采取邻接矩阵表示，邻接矩阵存放结构定义采取教材给出定义，若两个城市之间不存在道路，则将对应边权值设为自己定义无穷大值。要求在屏幕上显示得到最小生成树中包含了哪些城市间道路，并显示得到最小生成树代价；②表示城市间距离网邻接矩阵（要求最少6个城市，10条边）③最小生成树中包含边及其权值，并显示得到最小生成树代价。12.空间最近点对在空中交通控制问题中，若将飞机作为空间中移动一个点来处理，则求出含有最大碰撞危险两架飞机。(提醒：即空间中最靠近一对点，求平面即可)13.假币检验（1）在n枚外观相同硬币中，有一枚是假币，而且已知假币较轻。能够经过一架天平来任意比较两组硬币，从而得硬币重量是否相同，或哪一组更轻部分，假币问题要求设计一个算法来检测出这枚假币。（2）在120枚外观相同硬币中，有一枚是假币，而且已知假币和真币重量不一样，但不知道假币和真币相比较轻还是重。能够经过一架天平来任意比较两组硬币，最坏情况下，能不能只比较5次就检测出这枚假币。14.拿子游戏考虑下面这个游戏：桌子上有一堆火柴，游戏开始时共有n根火柴，两个玩家轮番拿走1根、2根、3根或4根火柴，拿走最终火柴玩家为获胜方。请为先走玩家设计一个制胜策略（假如该策略存在）。15.猴子分桃.问题描述:动物园里n只猴子编号为1,2,3，….，n，依次排成一队等候喂养员按规则分桃。动物园分桃规则是每只猴子可分得m个桃子，但必需排队领取。喂养员循环地每次取出一个，2给，…，k个桃放入筐中，由排在队首猴子领取。取到筐中桃子数为k后，又重新从1开始。当筐中桃子数加上队首猴子可取桃子数不超出m时，队首猴子能够全部取得喂养员手中桃子；取得桃子总数不足m个桃子，继续到队尾排队等候。当筐中桃子数加上队首猴子可取桃子数超出m时，队首猴子只能取满m个，然后离开队列，筐中剩下桃子由下一直猴子取用。上述分桃过程一直进行到每只猴子全部分到m个桃子。试验任务：对于给定n,k和m，模拟上述猴子分桃过程输入5,3,40输出：1352416.KMP算法求一个字符串在另一个字符串中第一次出现位置。17.模拟阵15812417161475232220136432119121092251811618753294魔方阵是一个古老智力问题，它要求在一个m*m矩阵中填入1~m2数字（m为奇数），使得每一行、每一列、每条对角线累加和全部相等。要求：输入m，实现，输出18.家族关系查询系统建立家族关系数据库，实现对家族组员关系相关查询要求：建立家族关系能存放到文件中；实现家族组员添加（双亲最多2个孩子）；能够查询家族组员双亲、祖先、弟兄、孩子和后代信息。提醒：树状结构能够用三叉链表。

附录B:汇报福建工程学院课程设计课程：题目：专业：班级：座号：姓名：年月日

试验题目：求迷宫最短路径一、要处理问题这是试验心理学中一个经典问题，心理学家把一只老鼠从一个无顶盖大盒子入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻求通路以达成出口。我们要处理是怎样找到了一条迷宫最短路径。二、算法基础思想描述：要用到回溯思想。从迷宫入口点出发，向四面搜索，记下全部一步能抵达坐标点；然后依次从这些点出发，再记下全部一步能抵达坐标点，……..依这类推，直到抵达迷宫出口点为止，然后从迷宫出口点沿搜索路径回溯。这么就找到了一条迷宫最短路径，不然迷宫无路径。因为先抵达点先搜索，故用优异先出数据结构——队列来保留已抵达坐标点。三、设计1.数据结构设计（1）迷宫表示设迷宫为m行n列，利用maze[m][n]来表示迷宫，maze[m][n]=0或1，其中0表示通路，1表示不通。入口坐标（1，1），出口坐标（m,n）.迷宫定义以下：#definem6#definen8intmaze[m+2][n+2]；（2）试探方向表示在迷宫中有8个方向能够试探，要求：从目前位置向前试探方向为从正东开始沿顺时针方向进行。为了简化问题，将这8个方向坐标增量放在一个结构数组move[8]中。在move数组中，每个元素有两个域组成，X：横坐标增量；Y：纵坐标增量。序号序号XY00111121031-140-15-1-16-107-11(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)Move数组定义以下：typedefstruct{intx,y;}item;itemmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};（3）队列表示在找到出口点以后，需要沿搜索路径回溯，所以抵达某点时，不仅要记下该点坐标，还要记下该点前驱。用一个结构数组sq[num]作为队列存放空间。Sq每一个结构有三个域：x,y,pre,其中x，y分别为所抵达点坐标，pre为前驱点坐标。还设队头front和队尾rear指针。#definenum50typedefstruct{intx,y；intpre;}SqType;SqTypesq[num]；intfront，rear；2.算法设计（1）求最短路径算法设计初始状态，队列中只有一个元素sq[1],统计是入口点坐标（1，1），因为该点是出发点，所以没有直接前驱点，pre域为-1，队头指针front队尾指针rear均指向它，以后搜索时全部是以front所指点为搜索出发点，立即该点坐标及front所指点位置入队，这么不仅记下了抵达点坐标，还记下了它前驱点。Front所指向点8个方向搜索完成后，则出队，继续对下一点搜索。搜索过程中碰到出口点则成功，搜索结束，打印出迷宫最短路径，算法结束；或目前队空，既没有搜索点了，表明没有路径，算法也结束。（2）预防反复抵达某点考虑为避免发生死循环，当抵达某点（i，j）后，使maze[i][j]置-1，方便区分未抵达过顶点。算法结束前可恢复原迷宫。（3）队列头、尾指针指向队头指针指向搜索出发点，当找到一个可抵达点，就入队；当8个方位全部搜索完成，队头指针往后移一个（出队，但原位置值仍然存在，方便最终回溯）。（4）模块结构及功效：主程序主程序队列初始化打印路径入队迷宫初始化求最短路经出队判队空voidmain()//主程序viodinit_maze(int)//迷宫初始化voidinit_queue(SqType)//队列初始化intpath(int,int)//求迷宫最短路径voidprint_path(SqType,rear)//打印路径voidin_queue(SqType,datatype)//入队操作voidout