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

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