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

数据结构课程设计指导书胡 振 华湖南城市学院数学与计算科学系2013.9一课程设计的目的软件设计能力培养对学生是很重要。通过数据结构的学习，使学生对软件编程能力有一定的提高。数据结构学习是锻炼学生在进一步掌握模块化、结构化程序设计的方法的同时，培养学生运用已学知识分析问题、解决问题及编写实用程序的能力，通过对线性化、层次化、网络化数据结构的了解进一步掌握自然数据的结构方式及组织方式，让学生深入体会存储在计算机中的数据及程序，如何运用数据实现编程。课程设计是数据结构课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。主要目的如下：1 通过不同类型的程序设计使学生学会分析数据如何组织，进一步掌握数据的几种不同的存储方式。2 为专业课的深入学习和毕业设计打基础。二课程设计的任务和要求本次设计是为加强学生的软件编程能力而进行的专门训练。选题考虑到学生在数据结构中学过的各种算法、数据组织方式进行选题，考虑数据结构算法所涉及的操作系统、网络、编译方法等中的实例，进行设计。下面是课程设计待选题目共44题。按学号相应选题，如：学号为01选择1题。分析题目，完成相应题目的程序设计。注：每班学生最多38人，后面的题目稍难，有能力的同学可选3844题。题目： 1. 键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。2.请设计一个有效的算法，可以进行两个n位大整数的乘法运算。3请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。4. 给定两个序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>，要求找出X和Y的一个最长公共子序列。5. 分子式是用来表达分子组成结构的表达式，一般表达形式为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。试编写程序求出给定的各个分子式所对应的分子量。6设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序.（不允许使用数组做辅助存储）7擦数游戏在黑板上从1开始写出一组连续的自然数，然后擦去其中的一个数k，其余的数的平均值为a/b(a,b为整数)。试编写程序求出被擦去的数k。8基数排序9连通无向图的非递归遍历。10求二叉树根结点到指定结点的路径。11判别给定的二叉树是否为二叉排序树。12已知二叉树的中序和先序序列，求后序序列。 13. 拓扑排序14对一个存储为邻接表的图，给出求其所有连通分量。15试修改起泡排序，以交替的正、反两个方向进行扫描。即第一趟把排序码最大的记录放到最末尾，第二趟把排序码最小的记录放到最头上。如此反复进行。16矩阵A中的元素若满足：Ai,j是第i行中值最小的元素，且又是第j列中值最大的元素，则称元素Ai,j为该矩阵的一个马鞍点。求出m×n矩阵的所有马鞍点。17最小生成树(普里母算法实现 28题用其他算法实现)18. 迷宫求解：在迷宫中求一条路径的算法，基本思想：若当前、位置可通过，则压入栈中，否则探索下一位置，若走不通，则回溯，迷宫大小：M*N。迷宫设置自定义。19设明文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) (当Ci<=7FH) Ci=Pi+Kj-80H (j=i mod (m+1) (当Ci>7FH)解密： Pi=Ci-Kj (j=i mod (m+1) (当Ci>=Kj) Pi=Ci-Kj+80H (j=i mod (m+1) (当Ci<Kj)20求二叉树中指定两个结点共同的祖先。21哈夫曼编码：根据字符使用权值不同，设计最优的二进制编码，初使条件：已知N个权值。实现顺序：先构造哈夫曼树，然后再求各叶结点的编码。22判别给定的二叉树是否是完全二叉树。23关键路径24处理器中有一就绪队列，若干个进程依到达的时刻依次进入就绪队列，每个进程有进程名和处理器处理此进程的所需空间，仿静态链表形式分配内存所需空间，编程序实现内存分配算法。25. 求一个表达式的逆波兰式26. 汉诺塔非递归算法27. 已知二叉树的中序和后序序列，求先序序列。28. 最小生成树29. 求树的宽度所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。30. 堆排序的实现：在顺序结构上完成,先建堆然后重建堆,最后实现全部排序31. 万年历：通过给定的年，求该年的日历，闰年算法：Y%4 &&!Y%100|Y%4000 32. 归并排序算法：用两路归并算法，实现N个无素的排序33. 求子串在主串中的位置并置换子串：给定主串和子串，显示出子串在主串中的第一个位置，基子串在主串中不存在，则返0；若非零则用给定的串替换子串。34. 内存分配算法：利用静态链表，模拟实现内存分配35. 最短路径 求图中任意两点间的最短路径 36. 约瑟夫环37. 学籍管理 对学生、课程、成绩分别建立三个数据文件（学生、课程、成绩属性自定）。查询某个学生的选课情况成绩不及格的学生情况对课程名按不及格学生人数进行排序建立模拟索引。38. 工资管理 自己建立数据文件（提示可建立：职工、工资级别、职工工资）完成：查询职工的平均工资查询某一级别人员的平均工资普调工资将职工姓名按工资额度进行排序39. 房产信息管理 按上述建立数据文件的方式对房产信息进行如下管理：查询修改排序40. 供货信息管理 按上述建立数据文件的方式对供货信息进行如下管理：查询修改排序41. 在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W1919表示一个棋盘，若Wij=0表示在位置(i,j)上没有子，Wij=1表示该位置上的是黑子，Wij=-1表示该位置上是白子。模拟实现五子棋 过程。42. 商店货架以栈的形式摆放商品，生产日期越近的越靠近栈底,出栈是从栈顶取货，一天营业结束，如果货架不满,则需上货，如果直接将商品摆放到货架上，则会使生产日期越近的越靠近栈顶.这就需要倒货架，仍使生产日期越近的越靠近栈底。写出货物进栈、出栈算法。43. 银行业务模拟问题描述： 客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。 44. 运动会分数统计程序的设计 运动会分数统计任务：参加运动会有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、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2. 要求：1) 对相应的题目进行算法设计2) 编写源代码3) 上机调试4) 显示调试结果5) 写出实验总结3课程设计说明书设计完成后，将自己选定的题目按上述要求完成课程设计说明书。课程设计说明书内容包含：题目、要求、初步设计（可以是流程图、功能模块图）、详细设计、程序代码、测试数据、运行结果、遇到的问题及总结几部分。三课程设计进度安排设计总学时为2周课程设计大体分五个阶段:1、选题与搜集资料:每人选择相应题目,进行课程设计课题的资料搜集.2、分析与概要设计:根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,并在此基础上进行实现程序功能的算法设计.3、程序设计:运用掌握C语言编写程序,实现所程序的各个模块功能.4、调试与测试:自行调试程序,成员交叉测试程序,并记录测试情况.5、实习报告:编写实习报告6、验收与评分:指导教师对每个小组的开发的系统,及每个成员开发的模块进行综合验收.结合设计报告,根据课程设计成绩的评定方法,评出成绩.四.课程设计考核标准考核时主要有如下几项参考：1 初步设计内容的考核：是否有查阅资料能力？是否有设计思想？2 程序编码能力调试能力的考核：程序是否清晰、易读？在技算计上是否可独立完成程序的调试，是否熟练？3 说明书质量的考核：设计结构是否合理？叙述是否正确？方案是否可行？4 答辩：设计结果的调试能力，对自己设计是否熟练？5 出勤率极平时表现的考核：出勤超过2次不到者成绩为不及格。五.课程设计报告的内容设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写,打印并装订,排版及图,表要清楚,工整.装订顺序如下:封面、任务书、目录、正文.正文包括以下7个内容:1.需求分析以无歧义的陈述说明程序设计的任务,强调的是程序要做什么 ，需要什么结果、所能达到的功能.2.概要设计说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.3.详细设计实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图、N S 图进行描述,画出函数和过程的调用关系图.4.调试分析内容包括:a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想;c.经验和体会等.5.测试结果列出你的测试结果,包括输入和输出.这里的测试数据应该完整和严格,最好多于需求分析中所列.6.参考文献列出参考的相关资料和书籍.六.主要参考书目1、姜学军等数据结构（C语言版）. 中国轻工出版社2、严慰敏. 数据结构（C语言版）. 清华大学出版社3、徐孝凯. 数据结构实用教程（C/C+描述）. 北京:清华大学出版社. 4、陈慧南. 数据结构（使用C+语言描述）. 南京:东南大学出版社.