《数据结构课程设计》实验指导书
1.1 实验报告撰写的基本要求
1.1.1 问题描述
这一部分需要简单介绍题目内容，即该实验到底要做什么。
1.1.2 算法说明
这一部分需要详细描述解决问题需要用到算法和重要的数据结构，即该实验到底应该怎么做。
基本要求：处理问题中所用到的关键算法都要描述清楚，而不是仅描述主函数。
算法和数据结构可用伪码和图示描述，不要只写源代码和注释。
1.1.3 测试结果
这一部分内容需要紧扣实习的题目类型和要求，涉及提供相应的测试方法和结果。
对于需要利用某算法解决某问题的题目，应设计并填写一张测试用例表。
每个测试用例一般包括下列内容：
（1）测试输入：设计一组输入数据；
（2）测试目的：设计该输入的目的在于测试程序在哪方面可能存在漏洞；
（3）正确输出：对应该输入，若程序正确，应该输出的内容；
（4）实际输出：该数据输入后，实际测试得到的输出内容；
（5）错误原因：如果实际输出与正确输出不符，需分析产生错误的可能原因；
（6）当前状态：分为“通过”（实际输出与正确相符）、“已改正”（实际输出与正确输出不符，但现在已修改正确）、“待修改”（实际输出与正确输出不符，且尚未改正）三种状态；
（7）测试结果分析：需要详细解释测试策略，对得到的数据进行分析，总结出算法的时空复杂度，得出自己对算法性能等方面分析的结论。
附录：源代码
源代码列在附录中，要求程序风格清晰易理解，有充分的注释，有意义的注释行少于代码的30%将不能得分。
1.2 实习作业的提交要求
每个实习项目结束后，学生按照实验报告格式和内容要求提交实验报告（打印稿）1份，与此同时提交压缩后的电子资料1份，电子资料要求按照如下方式打包：
文档夹：包括电子版的实验报告
学号姓名.rar 源代码文件
代码夹：源代码文件对应的可执行文件
readme.txt文件，告知如何编译源代码，生
成可执行文件
2.1 实验项目
2.1.1 通讯录管理
问题描述：设计一个计算机程序，实现通讯录管理。
设计要求：
1．设计一个含有6个菜单项的主控菜单，这6个菜单项的内容和输入提示如下：
1 通讯录链表的建立
2 通讯者结点的插入
3 通讯者结点的查询
4 通讯者结点的删除
5 通讯录链表的输出
0 退出管理系统
请选择0~5：
2．使用数字0~5来选择菜单项，其它输入则不起作用。
2.1.2 停车场管理
问题描述：设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。
在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。
若停车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。
当停车场内某辆车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该辆车开出大门后，其他车辆再按原次序返回车场。
每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。
设计要求：
1．模拟上述管理过程。
要求以顺序栈模拟停车场，以链队列模拟便道。
2．从终端读入汽车到达或离去的数据，每组数据包括三项：
（1）是“到达”还是“离去”；
（2）汽车牌照号码；
（3）“到达”或“离去”的时刻。
3．与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停
车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。
提示：需要另设一个栈，临时停放为让路而从停车场退出的车。
2.1.3 学生成绩名次表
问题描述：建设一个年级（M个班）的学生参加某门课程的考试，每个班最多有N个学生，请输出各班的成绩名次表（M个）、以班级为单位的成绩名次表（1个）、以及以年级为单位的成绩名次表（1个）。
设计要求：
1．功能：每个班级的学生记录按学号顺序排列，每个学生记录至少包含排列名次、学号、成绩3个字段。
2．输入：随机产生M*N个成绩。
3．输出：
（1）输出每个班级的成绩名次表，具有相同成绩的名次相同；
（2）输出以班级为单位的成绩名次表。
（3）输出以年级为单位的成绩名次表，具有相同成绩的名次相同。
2.1.4 校园导游程序
问题描述：用无向图表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等。
设计要求：
1．查询各景点的相关信息；
2．查询图中任意两个景点间的最短路径；
3．查询图中任意两个景点间的所有路径
2.2 实验项目说明
1．每个实验项目完成的时间为8~10学时，由实验指导教师根据实际情况确定实验时间，每个项目实验结束后均需要按照要求提交相关实验资料。
2．所有学生提交的实验资料不能雷同，雷同率超过30%，此次实验成绩为0分。
附录：实验报告格式
实验X XXXXXXXX
班级：__________ 学号：__________ 姓名：__________
指导教师签名：__________ 成绩：__________
一、问题描述
XXXXXXXXXXXXXXXX……
二、算法说明
1．数据结构说明
XXXXXXXXXXXXXXXX……
2．算法说明
XXXXXXXXXXXXXXXX……
三、测试结果
1．测试输入：XXXXXXXXXXXX
2．测试目的：XXXXXXXXXXXX
3．正确输出：XXXXXXXXXXXX
4．实际输出：XXXXXXXXXXXX
5．错误原因：XXXXXXXXXXXX
6．当前状态：XXXXXXXXXXXX
7．测试结果分析：XXXXXXXXXXXX
附录：源代码。