课程设计指导书新.doc

大连海洋大学理学院课程设计指导书课程设计名称： 数据结构课程设计 指 导 教 师： 董云影 专 业、班级：信息与计算科学10-1.2 时 间： 13-14学年第2学期第15周 一、课程设计的目的：该课程设计是在学生学习了数据结构理论课的基础之上，使用C语言作为实现工具，使学生对数据结构的基本理论从编程到实现有一个全面的体验，能初步掌握用不同的数据结构设计解决问题的算法的方法与技巧。通过本课程设计使学生能具有一定的自学能力和独立分析问题、解决问题的能力。通过严格的C语言编程实践，使学生逐步树立严肃认真、一丝不苟、实事求是的科学作风，并能独立编写并实现出解决实际问题的算法程序。该课程设计是学生面向程序设计的一个重要的实践教学部分。二、课程设计的要求：教师向学生布置需要解决的问题，规定设计技术指标和其他要求。并给予学生设计中需要的参考资料。教师讲授必要的C语言编程基础知识和数据结构预备知识，以及程序设计方法，着重帮助学生明确任务，掌握程序设计的基本方法。其余时间，主要是学生自学并独立完成程序设计和调试。学生对设计的全过程提交实验报告，实验报告要求如下。三、课程设计应用软件： Turbo C 或 VC+四、课程设计的具体内容：每位同学必须在以下8个题目中任选一个题目，提交实验报告，如有雷同或不按要求书写实验报告者一律以0分记！1. 设计一个一元多项式简单的计算器基本功能：1） 输入并建立多项式2） 输出多项式3) 两个多项式相加减.相乘，建立并设计一个一元多项式实现提示：可选择带头结点的单循环链表或单链表存储多项式，头结点可存储单链表的参数，如项数等。2. 停车场模拟管理系统问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。实验要求（程序完成的功能）：要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。实现提示：汽车的模拟输入信息格式可以是：（到达/离去，汽车牌号，到达/离去的时刻）。例如：（A，1，5）表示1号牌照车在5这个时刻到达，而（D，5，20）表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为（E，0，0）时结束。本题可以用栈和队列来实现。3.迷宫问题问题描述：本实验是迷宫问题，取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个 出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走该迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求：（1）一条通路的二元组（i，j）数据序列，（i，j）表示通路上某一点的坐标。（2）用标志（如数字8）在二维数组中标出该条通路，并在屏幕上输出二维数组。实现提示：（1） 以二维数组mazeij表示迷宫，其中0,0，数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。限定迷宫的大小m=n=9。假定从mg00出发，出口位于mgmn,移动方向为顺时针的8个方向(东，东南，南，西南，西，西北，北，东北)。（2） 以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n，从第2行至第m+1行为迷宫值；（3） 若设定的迷宫存在通路，则以方阵形式及其通路路径输出，若设定的迷宫不存在通路，则输出“没有可走路径”（4） 用一种标志（本题设为8）在二维数组中显示该条通路，并在屏幕上输出二维数组，本程序最终要求求出一条成功的通路4树的问题问题描述：编写在一个以二叉链表作为存储结构的二叉树中交换所有结点的左、右子树的算法。基本思想：设二叉树的根指针为t且以二叉链表表示，可利用一个类型为seqstack的指针栈来实现，且设栈单元包含两个域，一个域为data,一个域为top,整个栈的容量为maxsize，当树非空时，将当前栈顶元素出栈当做根结点，然后依据当前根结点是否有孩子结点来判断是否将其左右指针进行交换；再将交换后的左指针或右指针入栈，这样反复进行，直到栈空为止。5.图的问题1问题描述：如果以无向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通信网络的总造价最低。实现提示：这是一个求连通的带权无向图（即网络）的最小代价生成树的问题。建立图的邻接矩阵，然后用prim算法来求最小生成树。6.图的问题2问题描述：假设以一个带权有向图表示某一区域的公交线路图，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需要的时间）。试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。实现提示：该问题可归结为一个带权有向图中顶点间最短路径问题，分别建立以票价为权或以搭乘时间为权的图的邻接矩阵，以Floyd算法来求最短路径及其路径长度。7.查找的问题问题描述：设计一个读入一串整数构成一棵二叉排序树的算法。实现提示：二叉排序树的构成，可以从空的二叉树开始，每输入一个结点数据，就建立一个新的结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。8.排序的问题（统计成绩）问题描述：给出n个学生的考试成绩表，每条信息由姓名与分数组成，试设计一个算法：（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分 数相同的为同一名次；（2） 按名次列出每个学生的姓名与分数。基本要求：学生考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。五、课程设计报告书写流程1弄清课程设计要求在该部分中根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求做什么？以及限制条件是什么？ 问题描述： (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能；2概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1) 数据结构 (2) 程序模块 (3) 各模块之间的调用关系以及算法设计 3详细设计 实现概要设计中定义的所有数据类型，对每个操作写出伪码算法，对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；写出主函数和过程的调用关系。4测试与分析 测试数据，输出测试的结果，这里的测试数据应该完整和严格。并对结果进行分析。 5总结 总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容。 6、附录：源程序清单六、成绩评定1考核方式包括基本知识的掌握程度，程序设计方法是否合理；设计代码是否正确，程序是否简化高效，设计是否具有创新精神；以及出席情况和学习态度等环节。成绩按优、良、中、及格、不及格五级分制评定。2考核成绩评定标准优：实验报告完全按照规定书写，编程及设计方法正确，代码正确，结果正确，设计具有创新精神，学习态度认真，无缺席。良：实验报告基本按照规定书写，编程及设计方法正确，代码正确，结果正确，学习态度认真，无缺席。中：实验报告基本按照规定书