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

数据结构课程设计指导书孙鸿飞东北电力大学经济管理学院数据结构课程设计指导书一、课程设计的目的数据结构课程是信息管理与信息系统专业的核心课程，是一门以实践为主的课程。计算机学科各领域及应用都用到各种数据结构，特别是随着计算机应用领域的扩大和非数值计算的增加，数据大量增加，它们之间的结构关系也日益复杂，无论是操作系统、数据库系统、电子商务系统、编译系统及信息系统等的设计和实现，还是其它各种应用软件都涉及不同的数据结构。学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。本课程设计是在学生理解了数据结构内在的逻辑关系的基础上，深入讨论它们在计算机中的存储表示，结合上机进行算法及存储表示的实现。这样，进一步提高学生软件设计和编程水平。课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。经过查找参考资料、技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。课程设计所安排的题目，在难度和深度方面都大于课内的上机训练。二、课程设计要求学生必须仔细阅读数据结构课程设计指导，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要三周时间完成，三周中每天（按每周5天）至少要上3-4小时的机来调试C语言/C+语言设计的程序，总共至少要上机调试程序50小时。7月9日9点提交课程设计所需全部资料，7月10日、11日进行最终答辩和程序测试，地点：经济管理学院D304。课程设计不安排补考，不合格者将随下届同学重新进行课程设计。注意：在课程设计时，任选下列一题完成。要求每个同学独立完成。三、课程设计的具体内容1 试设计一个航空客运定票系统。基本要求如下：每条航线所涉及的信息有：终点站名、航班号、飞行日期（星期几飞行）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。系统能实现的操作和功能如下：查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少于订票额，则需重新询问客户要求。若需要，可登记排队候补；承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。实现提示：两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。由于预约人数无法预计，队列也应以链表作为存储结构。2 校园导游咨询（为来访的客人提供各种信息服务）问题描述：设计你的学校的校园平面图，所含景点10个左右。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。3 停车场管理问题问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。实现要求：要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。实现提示：汽车的模拟输入信息格式可以是：(到达离去，汽车牌照号码，到达离去的时刻)。例如，(A，1，5)表示1号牌照车在5这个时刻到达，而(D，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(E，0，0)时结束。本题可用栈和队列来实现。4 迷宫问题问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。实现要求：要求程序输出：(1)一条通路的二元组(i，j)数据序列，(i，j)表示通路上某一点的坐标。(2)用一种标志(如数字8)在二维数组中标出该条通路，并在屏幕上输出二维数组。实现提示：可以利用一个二维数组mazeij表示迷宫，其中1=i=m，1=j=n。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从mazel1出发，出口位于mazemn，移动方向可以是8个方向(东，东南，南，西南，西，西北，北和东北)。5 n阶魔阵问题问题描述：给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，n2组成。魔阵的每一行元素之和，每列元素之和以及主、副对角线元素之和均相等。即对于给定的奇数n以及i=1,2,3,n，魔阵a满足条件：实现要求：要求输出结果的格式要具有n阶方阵的形式。实现提示：依次将自然数填入方阵中，共填n轮，每轮填n次。第一轮的第一次，将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是aij:每轮中第2至第n次将数填入ai+1,j+1，若遇到下列两种情况之一，则填写位置按以下规则调整。aij是最后一列（即j=n）位置，则将下一个数填入ai+1,1；aij是最后一行（即i=n）位置，则将下一个数填入a1,j+1新一轮的第一次填入a1,j-1。6 公交线路问题问题描述：假设以一个带权有向图表示某一个区域的公交线路；图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间）。试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。实现提示：该问题可归结为一个求带权有向图中顶点间最短路径的问题。分别建立以票价为权或以搭乘时间为权的图的邻接矩阵，以Floyd算法来求最短路径及其路径长度。7 编写一个五子棋的游戏程序。问题描述：实现两人对下功能。8纸牌游戏问题描述：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？9文章编辑问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”（3）输出删除某一字符串后的文章。10运动会分数统计问题描述：参加运动会有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/c+语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。四、上交相关内容要求上交的成果的内容必须由以下四个部分组成，缺一不可。1上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；2上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；3课程设计报告：（保存在word文档中，文件名要求按照姓名-学号-课程设计报告起名，如文件名为张三-001-课程设计报告.doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；（至少10页以上）其中包括：a）需求分析：在该部分中叙述，每个模块的功能要求。b）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。c）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。d）调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 4. 课设总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容。五、设计和调试过程的规范化要求1、对每个题目要有需求分析在需求分析中，将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。对有些题目提出算法改进方案，比较不同算法的优缺点。如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法；2、对每个题目要有相应的源程序（可以是一组源程序，即详细设计部分）：源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；3、最后提供的主程序可以象一个应用系统一样有主窗口，通过主菜单和分级菜单调用课程设计中要求完成的各个功能模块，调用后可以返回到主菜单，继续选择其他功能进行其他功能的选择。六、成绩评定方法数据结构课程设计的最后成绩由以下几个方面组成：程序运行情况（20分），程序的结构合理与否（10分），算法说明的清晰程度（10分），上交磁盘中程序存放的规范程度（10分），课程设计报告完成情况（20分），独立完成情况（学生间不相互雷同）（20分），以及加分因素（10分）（包括：总结的深刻程度、算法的创新性等）；共100分。根据以上评定方法，成绩分为：优秀、良好、中等、不及格四个级别。（上空小宋4号字5行）本科课程设计论文（宋小2居中）（空小宋4号字1行）课程设计论文题目（不超过25个汉字，黑体2号字）（题目与姓名之