课程设计指导书新.doc

大连海洋大学理学院

课程设计指导书

课程设计名称：数据结构课程设计
指导教师：董云影
专业、班级：信息与计算科学10-1.2
时间：13-14学年第2学期第15周

一、课程设计的目的：
该课程设计是在学生学习了数据结构理论课的基础之上，使用C语言作为实现工具，使学生对数据结构的基本理论从编程到实现有一个全面的体验，能初步掌握用不同的数据结构设计解决问题的算法的方法与技巧。通过本课程设计使学生能具有一定的自学能力和独立分析问题、解决问题的能力。通过严格的C语言编程实践，使学生逐步树立严肃认真、一丝不苟、实事求是的科学作风，并能独立编写并实现出解决实际问题的算法程序。该课程设计是学生面向程序设计的一个重要的实践教学部分。
二、课程设计的要求：
教师向学生布置需要解决的问题，规定设计技术指标和其他要求。并给予学生设计中需要的参考资料。
教师讲授必要的C语言编程基础知识和数据结构预备知识，以及程序设计方法，着重帮助学生明确任务，掌握程序设计的基本方法。其余时间，主要是学生自学并独立完成程序设计和调试。
学生对设计的全过程提交实验报告，实验报告要求如下。
三、课程设计应用软件：
TurboC或VC++
四、课程设计的具体内容：
每位同学必须在以下8个题目中任选一个题目，提交实验报告，如有雷同或不按要求书写实验报告者一律以0分记！
1.设计一个一元多项式简单的计算器
基本功能：
输入并建立多项式
输出多项式
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）在二维数组中标出该条通路，并在屏幕上输出二维数组。
实现提示：
以二维数组maze[i][j]表示迷宫，其中0,0，数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。限定迷宫的大小m=n=9。假定从mg[0][0]出发，出口位于mg[m][n],移动方向为顺时针的8个方向(东，东南，南，西南，西，西北，北，东北)。
以文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n，从第2行至第m+1行为迷宫值；
若设定的迷宫存在通路，则以方阵形式及其通路路径输出，若设定的迷宫不存在通路，则输出“没有可走路径”
用一种标志（本题设为8）在二维数组中显示该条通路，并在屏幕上输出二维数组，本程序最终要求求出一条成功的通路

4．树的问题
问题描述：编写在一个以二叉链表作为存储结构的二叉树中交换所有结点的左、右子树的算法。
基本思想：设二叉树的根指针为t且以二叉链表表示，可利用一个类型为seqstack的指针栈来实现，且设栈单元包含两个域，一个域为data,一个域为top,整个栈的容量为maxsize，当树非空时，将当前栈顶元素出栈当做根结点，然后依据当前根结点