《数据结构课程设计》指导书.doc

课程设计指导一、数据结构课程设计要求学生必须仔细阅读数据结构课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要2周时间完成。二、数据结构课程设计的具体内容 所选题目第一题：学号%11+1（或自由组合不超过3人）所选题目第二题：学号%39+13 例如：某班学号为10的同学应选择的题目为11题、23题三、上交相关内容要求上交的成果的内容必须由以下三个部分组成，缺一不可1上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2课程设计报告：（保存在word 文档中，文件名要求 按照姓名-学号-课程设计报告起名，如文件名为张三-001-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括:a)需求分析：在该部分中叙述，每个模块的功能要求b)概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。c）详细设计：各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析：测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 e）课设总结：总结可以包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容。四、 课程设计考核标准1 初步设计内容的考核：是否有查阅资料能力？是否有设计思想？2 程序编码能力调试能力的考核：程序是否清晰、易读？在技算计上是否可独立完成程序的调试，是否熟练？3 课程设计报告质量的考核：设计结构是否合理？叙述是否正确？方案是否可行？4 答辩：设计结果的调试能力，对自己设计是否熟练？5. 出勤率极平时表现的考核：无故缺勤者成绩为不及格。五、进度安排1、确定算法，进行初步设计（总体设计）2、详细设计、模块编码3、编码调试、测试（给出测试数据）4、验收、答辩 六、课程设计窗口参考1. 主窗口2. 分层菜单 3、4、参考题目：1、*学籍管理 对学生、课程、成绩分别建立三个数据文件（学生、课程、成绩属性自定）。查询某个学生的选课情况成绩不及格的学生情况对课程名按不及格学生人数进行排序建立模拟索引。问题描述：设计一个学生成绩管理程序，实现对学生成绩的输入、输出、查询、修改等功能。具体如下：（1） 输入学生各项信息、输入成绩信息；（2） 按学号查询成绩信息；（3） 按学号修改学生成绩信息；（4） 统计并打印信息；2、 *人事管理 自己建立数据文件（提示可建立：职工、部门、职工职称）完成：查询职工的平均年龄查询某一职称人员的平均年龄统计个职称人员数量统计2种数据。测试数据及测试结果请在上交的资料中写明;3、 *供货信息管理 按上述建立数据文件的方式对供货信息进行如下管理：查询货物信息修改信息对供货情况排序4、 *订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 5、*工资管理 自己建立数据文件（提示可建立：职工、工资级别、职工工资）完成：查询职工的平均工资查询某一级别人员的平均工资普调工资将职工姓名按工资额度进行排序6、 *银行业务模拟问题描述： 客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。 7、 *学生证管理程序题目描述：请设计一个学生证的管理程序。该程序应该具有下列功能：(1) 录入学生的学生证基本信息。(2) 按给定学号、班号等项，查询、插入、修改、删除信息；(3) 按学号、班号输出学生信息；(4) 统计信息。【提示】设计一个结构类型和一维数组类型，用来保存学生信息。8、 *图书登记管理程序题目描述：请设计一个图书登记管理程序。该程序应该具有下列功能：(1) 录入某本图书的信息； (2) 按给定书号、作者等项，查询、插入、修改、删除信息；(3) 显示该出版社的所有图书信息；(4) 统计各类信息的功能。【提示】设计一个结构类型和一维数组类型，用来保存图书信息。程序代码参见第1题。9、 * 学分管理程序题目描述：请设计一个学生的学分管理程序。假设每位学生必须完成基础课50学分、专业课50学分、选修课24学分、人文类课程8学分、实验性课程20学分才能够毕业。因此在管理学分时，要考虑每个学分所属于的课程类别。该程序应该具有下列功能：(1) 输入某学生的学分；(2) 给定学号、班号等条件，显示、修改、删除相应的信息；(3) 按照某条件进行排序；(4) 提供一些统计各类信息的功能。【提示】设计一个结构类型和一维数组类型，用来保存学分信息。10、 * 学生作业完成情况管理程序题目描述：请设计一个学生作业完成情况管理程序。假设某门课程一学期要留10次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分100）。该程序应该具有下列功能：(1) 输入信息；(2) 输出信息；(3) 给定条件，修改、删除相应信息； (4) 按条件统计。【提示】设计一个结构类型和一维数组类型，用来保存作业信息。11、 *存储管理中分区分配算法的模拟。问题描述 当作业运行时，由操作系统将内存空间分配给作业。分区管理是内存管理的一种方式，模拟分区分配算法采用最佳适应、最先适应等方式分配内存。选择不同的算法，对作业分配所需要的空间。当空间回收时，将空闲空间与被回收空间相连的部分连接成一块较大的空间。12、 *运动会分数统计程序的设计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1). 可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4). 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；13、 *CPU调度问题问题描述：在进程调度时，CPU选择进程处理的方式有几种，时间片轮转法、优先级调度法等。模拟操作系统实现调度CPU的调度过程。14、 请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。15、 给定两个序列X=和Y=，要求找出X和Y的一个最长公共子序列。16、 分子式是用来表达分子组成结构的表达式，一般表达形式为A1c1A2c2A3c3. 其中Ai(i=1,2,.)表示原子或原子团，ci(i=1,2,.)表示原子或原子团Ai重复的次数。当ci=1时，ci必须省略不写，且原子团的括号也不要。例如N的原子量为14，H的原子量为1，C的原子量为12，O的原子量为16，因此(NH4）2CO3的分子量为（14+1*4）*2+12+16*3=96。试编写程序求出给定的各个分子式所对应的分子量。17、 设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序.（不允许使用数组做辅助存储）18、 擦数游戏在黑板上从1开始写出一组连续的自然数，然后擦去其中的一个数k，其余的数的平均值为a/b(a,b为整数)。试编写程序求出被擦去的数k。19、 基数排序20、 连通无向图的非递归遍历。21、 求二叉树根结点到指定结点的路径。22、 判别给定的二叉树是否为二叉排序树。23、 已知二叉树的中序和先序序列，求后序序列。 24、 拓扑排序25、 对一个存储为邻接表的图，给出求其所有连通分量。26、 试修改起泡排序，以交替的正、反两个方向进行扫描。即第一趟把排序码最大的记录放到最末尾，第二趟把排序码最小的记录放到最头上。如此反复进行。27、 矩阵A中的元素若满足：Ai,j是第i行中值最小的元素，且又是第j列中值最大的元素，则称元素Ai,j为该矩阵的一个马鞍点。求出mn矩阵的所有马鞍点。28、 最小生成树(普里母算法实现 28题用其他算法实现)29、 迷宫求解：在迷宫中求一条路径的算法，基本思想：若当前、位置可通过，则压入栈中，否则探索下一位置，若走不通，则回溯，迷宫大小：M*N。迷宫设置自定义。30、 设明文P=P0P1P2Pn和密钥K=K0K1K2Km(n=m)中的字符Pi(1=i=n)或Kj(1=j=m)的ASCII为007FH，用密钥K对明文P进行加密得到密文C=C0C1C2Cn, 用密钥K对密文C解密得到明文P。加密： Ci=Pi+Kj (j=i mod (m+1) (当Ci7FH)解密： Pi=Ci-Kj (j=i mod (m+1) (当Ci=Kj)Pi=Ci-Kj+80H (j=i mod (m+1) (当CiKj)31、 求二叉树中指定两个结点共同的祖先。32、 判别给定的二叉树是否是完全二叉树。33、 关键路径34、 求一个表达式的逆波兰式35、 汉诺塔算法36、 已知二叉树的中序和后序序列，求先序序列。37、 最小生成树38、 求树的宽度所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。39、 堆排序的实现：在顺序结构上完成,先建堆然后重建堆,最后实现全部排序40、 万年历：通过给定的年，求该年的日历，闰年算法：Y%4 &!Y%100|Y%4000 41、 归并排序算法：用两路归并算法，实现N个无素的排序42、 求子串在主串中的位置并置换子串：给定主串和子串，显示出子串在主串中的第一个位置，基子串在主串中不存在，则返0；若非零则用给定的串替换子串。43、 最短路径 求图中任意两点间的最短路径 44、 在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W1919表示一个棋盘，若Wij=0表示在位置(i,j)上没有子，Wij=1表示该位置上的是黑子，Wij=-1表示该位置上是白子。模拟实现五子棋 过程。45、 商店货架以栈的形式摆放商品，生产日期越近的越靠近栈底,出栈是从栈顶取货，一天营业结束，如果货架不满,则需上货，如果直接将商品摆放到货架上，则会使生产日期越近的越靠近栈顶.这就需要倒货架，仍使生产日期越近