数据结构课程设计指导手册

数据结构课程设计指导手册课程设计是课程学习后的一个综合性实践教学环节，是对课程理论和课程实验的综合和补充。它主要培养学生综合运用已学过的理论和方法去分析和解决实际问题的能力，对加深课程理论的理解和应用、切实加强学生的实践动手能力和创新能力具有重要意义。课程设计是大学生必不可少的一个综合性理论实践环节。一、课程设计目的与要求课程设计是使学生融会贯通本课程所学专业理论知识，完成一个较完整的程序设计和程序调试过程，以加深学生对所学理论的理解与应用，进一步认识和熟悉数据结构中各种算法的实现与具体应用，了解解决实际问题的一般过程，培养学生综合运用基础理论知识和专业知识去解决实际问题的能力。通过综合性课程设计训练，使学生达到以下的目的和要求：1、结合该课程中所学的各种数据结构及其操作，设计一个综合的程序解决具体的问题，将所学知识应用到具体实际中去；2、学会查阅相关手册和资料，通过查阅手册和资料，进一步熟悉常用方法的用途和技巧，并掌握这些方法的具体含义和如何使用这些方法解决实际问题；3、掌握综合性程序设计的基本过程以及具体问题中数据结构的选择与应用；4、掌握综合性程序设计的调试技术，熟悉常用调试方法的使用；5、认真撰写总结报告，培养严谨的作风和科学的态度。二、时间安排根据专业计划和该课程教学大纲的要求，课程设计安排在学期末，总学时1周。三、指导教师由担任本课程的教师或其他老师担任指导教师，指导教师具体负责课程设计的任务布置、实践指导和成绩评定。指导教师在公布课程设计课题时应包括以下内容：课题名称；问题描述；主要任务；主要参考文献等内容。指导教师在学生停课期间应及时了解学生的实践进度和出勤情况，为学生解决疑难问题和课程设计过程中所遇到的困难。四、选题内容和要求选题分指导教师选题和学生自己选题两种，学生选题应通过指导教师批准后方可进行。1、选题内容选题要符合该课程的教学要求，各课程设计的内容及要求详见附录1。2、选题要求⑴注意选题内容的先进性、综合性、实践性，应适合实践教学和启发创新，选题内容不应太简单，难度要适中；⑵结合各种数据结构在实际问题中的具体应用进行选题；⑶选题应能完整的实现一个具体问题。五、实施步骤1、选题指导教师在课程结束之前根据该课程设计的要求向系部上报课程设计的课题名称、进度和要求，系部批准后进行实施。学生根据自己的兴趣爱好按指导教师公布的课题进行选题、着手准备资料的查阅。学生也可以自己选题，但课题应经过指导教师的批准后方可进行。2、问题分析和任务定义在进行设计之前，首先应该充分的分析和理解问题，明确问题要求做什么？限制条件是什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务做出明确的回答。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。3、数据类型和系统设计在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义，各个主模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明做出的进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。4、编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60个字符。每个函数体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应该分割为较小的函数。不管你是否写出编码的程序，在上机之前，认真地静态检查是必不可少的。静态检查主要有两种方法，一是用一组测试数据手工执行程序；二是通过阅读或给别人讲解自己的程序而深入全面的理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。5、上机准备和上机调试上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试底层函数。必要时可以令写一个调用驱动程序。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“冥思苦想”，而应该动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。6、撰写课程设计总结报告课程设计总结报告是课程设计工作的整理和总结，主要包括课程设计的目的、问题描述、需求分析、概要设计、详细设计、调试分析、使用说明和总结。六、上交材料学生应按规范(见附录2)撰写课程设计总结报告。课程设计实践教学环节结束后，教师应将总结报告按要求装订后送交系存档。七、课程设计报告的撰写规范课程设计的总结报告是在完成设计、编码、调试后，学生对归纳技术文档、撰写科学技术总结报告能力的训练，培养学生严谨的作风和科学的态度。通过撰写课程设计总结报告，不仅可以把设计、编码、调试及技术参考等内容进行全面总结，而且还可以把实践内容提升到理论高度。总结报告按如下内容顺序用A4纸进行打印（撰写）并装订成册：1、统一的封面（含课程设计课题名称、专业、班级、姓名、学号、指导教师等，详见附录1）；2、问题描述和任务要求（由指导教师在选题时提供给学生）；3、内容摘要；4、目录；5、课程设计总结报告正文，正文可按章节来撰写，应包含以下内容：⑴实习目的⑵需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：输入的形式和输入值得范围；输出的形式；程序所能达到的功能；测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。⑶概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。⑷详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其它模块也都要写出伪码算法；画出函数的调用关系图。⑸调试与测试结果分析调试分析包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；算法的时间复杂度和空间复杂度分析和改进思想；经验和体会等。测试结果分析：列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。⑹使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。⑺总结5、按统一格式列出主要参考文献6、附录（带注释源程序）。8、指导教师成绩评定表。八、成绩评定学生按要求上交课程设计总结报告。指导教师根据学生在课程设计中的表现、学生上交的课程设计总结报告内容进行综合评定，成绩不合格者重修。其中课程设计实际完成情况占50%，课程设计总结报告占50%，指导教师按要求在成绩评定表上打分。课程设计最终成绩分为“优秀”、“良好”、“中等”、“及格”、“不及格”五级。“优秀”为100分到90分，“良好”为89分到80分，“中等”为79分到70分，“及格”为69分到60分，“不及格”为60分以下。九、课程设计学生守则及管理规定1、学生在课程设计期间应遵守学校作息制度；请假需经指导教师同意，并按学校规定办理请假手续，否则以旷课论处，每天以6课时计算。2、学生必须随时接受指导教师的检查，指导及安排的工作。3、课程设计所使用的机器，须经指导教师同意后，方可使用。课程设计结束后，制作成果必须交学院资料室。4、学生使用的计算机、电子仪器或其它设备，若因责任事故造成丢失或损坏，应酌情赔偿。若设备发生故障，应及时报告，学生不得擅自修理。5、严格禁止学生在计算机房或实验室玩游戏，每发现一次，则课程设计成绩降低5分。学生未经指导教师同意将私人盘片、器材带入计算机房或实验室，将予以没收。学生也不得将计算机房和实验室中的任何设备、器材和工具带回宿舍使用，否则视为盗窃。6、学生在实验室内必须严肃认真，不得大声喧哗，严禁吃任何食物，严禁吸烟，每日负责卫生打扫，并在离开时切断电源，关好水龙头，关紧门窗。7、学生借阅院资料室参考书籍和资料时，必须由指导老师带领，并由指导老师签名借阅。8、课程设计学生在停课期间必须每天到所在的实验室签到。附录1课程设计的题目及要求：（一）航空订票系统1.问题描述：设计一个航空订票系统，通过此系统可以实现如下功能：（1）可以录入航班信息（数据可以存储在一个数据文件中，数据结构、具体数据自定）；（2）可以查询任意航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；（3）可以输入起飞抵达城市，查询飞机航班情况；（4）可以订票，如果该航班已经无票，可以提供相关可选择航班；（5）可退票，退票后修改相关数据文件；（6）客户资料有姓名，证件号，订票数量及航班情况，订单要有编号；（7）当航班信息改变可以修改航班数据文件。2.基本要求：（1）任意性：用户可任意设计航班信息及订票信息的存储结构。（2）友好性：界面要友好，输入有提示，尽量展示人性化。（3）可读性：源程序代码清晰、有层次，必要时给出注释。（4）健壮性：用户输入非法数据时，系统要及时给出警告信息。（5）测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。（二）景区旅游信息管理系统1.问题描述：设计一个景区旅游信息管理系统，实现以下功能：（1）景区旅游信息管理系统中，首先通过遍历景点，给出一个入口景点；（2）设计景区的旅游景点，确定入口和出口景点；（3）根据导游策略建立导游线路图并遍历景点；（4）提供两个任意景点之间的最短路径及最短距离；（5）通过求最小生成树对景区进行建设和规划。2.基本要求（1）任意性：用户可任意设计景区旅游景点、图的存储结构及导游策略。（2）友好性：界面要友好，输入有提示，尽量展示人性化。（3）可读性：源程序代码清晰、有层次，必要时给出注释。（4）健壮性：用户输入非法数据时，系统要及时给出警告信息。（5）测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。（三）停车场问题1.问题描述：停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端）若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要安时间长短缴费。2.基本要求：（1）以栈模拟停车场，以队列车场外的便道，按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现。（2）友好性：界面要友好，输入有提示，尽量展示人性化。（3）可读性：源程序代码清晰、有层次，必要时给出注释。（4）健壮性：用户输入非法数据时，系统要及时给出警告信息。（5）测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。（四）一元多项式的应用1.问题描述：设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+AmxmBn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x