实践教学

实验一 停车场管理系统

（一）实验内容

以栈模拟车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现。

（二）实验过程

编程实现实验内容。

（三）实验教学基本要求

通过实例，使学生掌握栈和队列两种特殊的线性结构，掌握栈和队列的特点。 实验后学生提交实验报告。

（四）实验设备和材料

学效机房或实验室的计算机。

实验二 教学计划编制问题

（一）实验内容

假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。编制一个教学计划程序。

（二）实验过程

编程实现实验内容。

（三）实验教学基本要求

通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。 实验后学生提交实验报告。

（四）实验设备和材料

学效机房或实验室的计算机。

实验三 最小生成树问题

（一）实验内容

利用克鲁斯卡尔算法求最小生成树。以文本形式输出树中各条边以及他们的权值。

（二）实验过程

编程实现实验内容

（三）实验教学基本要求

通过实例，使学生熟悉图的各种存储结构的特性，掌握如何应用图结构解决具体问题。 实验后学生提交实验报告。

（四）实验设备和材料

学效机房或实验室的计算机。

实验四 哈希表设计

（一）实验内容

假设人名为中国人的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。

（二）实验过程

编程实现实验内容

（三）实验教学基本要求

掌握索引技术的使用。

（四）实验设备和材料

学效机房或实验室的计算机。

实验一 停车场管理系统

数据结构设计：

1．为了便于区分每辆汽车并了解每辆车当前所处的位置，需要记录汽车的牌照号码和汽车的当前状态，所以为汽车定义一个新的类型CAR；

2．由于停车位只能停放有限的几辆车，而且为了便于停车场的管理，要为每个车位分配一个固定的编号，不妨设为1、2、3、4和5（可利用数组的下标），分别表示停车位的1车位、2车位、3车位、4车位和5车位，针对这种情况使用一个顺序栈比较方便；

3．当停车场的停车位上都已经停满了汽车，又有新的汽车到来时要把它调度到便道上，便道上的车辆要按照进入便道的先后顺序顺次存放在便道上，为便道上的每个位置也分配一个固定的编号，当有车从停车位上离开后，便道上的第一辆汽车就立即进入停车位上的某个车位，由于问题描述中限制了便道上的汽车不能从便道上开走，即便道上的汽车只有在停车位上停放过之后才能离开停车场，这样越早进入便道的汽车就越早进入停车位，而且每次进入停车位的汽车都是处于便道“最前面”的汽车，显然这里使用一个顺序队来描述便道，可以利用数组的下标表示便道的位置；

4．当某辆车要离开停车场的时候，比它后进停车位的车要为它让路，而且当它开走之后让路的车还要按照原来的停放次序再次进入停车位的某个车位上，为了完成这项功能，再定义一个辅助栈，停车位中让路的车依次“压入”辅助栈，待提出开走请求的车开走后再从辅助栈的栈顶依次“弹出”到停车位中。对辅助栈也采用顺序栈。

功能（函数）设计：

1．本程序从总体上分为4个大的功能模块，分别为程序功能介绍和操作提示模块、汽车进入停车位的管理模块、汽车离开停车位的管理模块和查看停车场停车状态的查询模块。

2．以上4个总体功能模块要用到的栈和队列的基本操作所对应的主要函数如下：

3．由于程序应该能够随时处理用户所提出的各种操作请求，所以在主函数中用一个do…while循环结构随时监控键盘的按键操作，遇到相应的按键就转到对应函数继续运行，运行完该函数继续监控键盘按键，如此往复，直到接到“退出”指令程序才能结束。

实验二 教学计划编制问题

数据结构设计：

1．struct Course //课程的相关信息

2．图的存储定义：

#define MAX_VERTEX_NUM 50 //最大课程数

struct ArcNode

struct VNode

struct ALGraph_1

功能（函数）设计：

实验三和实验四的答案将于近日公布

敬请期待(>▽