数据结构课程设计任务书(14级).docx

《数据结构课程设计任务书(14级).docx》由会员分享，可在线阅读，更多相关《数据结构课程设计任务书(14级).docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计任务书(14级) 数据结构课程设计任务书 题目一：计算AOE网的关键路径 AOE网即边表示活动的网络。通常，可用AOE网来估算工程计划的完成时间。如下所示的AOE网包括11项活动，9个事件，每个事件都有所需的完成时间。我们现在要解决的是：（1）完成整项工程至少需要多少时间（最短时间）；（2）哪些活动是影响工程进度的关键（关键活动）。 用e(i)表示活动最早开始时间，l(i)表示活动的最迟开始时间，则l(i)-e(i)为完成该活动的时间余量。对于本例列表如下： 下图就是上述AOE网的关键路径： 请编程完成下列工作： 1、输入： （1）顶点的信息和入度； （2）AOE网的边（始点、

2、终点和权值）。 2、输出： （1） AOE网的邻接表（按“顶点入度：顶点权值”的格式输出）如 a 0：-4 5-3 4-2 6 （2）输出关键活动 每行所显示的分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量： 当l(i)-e(i)=0时，在该行注明为关键活动。如： a b 0 0 0 关键活动 题目二：大赛投票系统 在电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。要求编写一程序模拟实现上述系统的功能。 首先输入参赛选手的人数（范围为2-9个），然后根据人数通

3、过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依次存入顺序表单元中，观众通过按键进行投票，按1对1号选手投票，按2对2号选手投票，以此类推，以按0作为投票结束标志。投票结束后采用希尔排序对选手进行排序，然后为每个选手计算名次，得票相同的名次也相同。 题目三停车场管理 问题描述：设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大门口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入

4、停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。 算法描述 提示：可以将停车场定义成一个顺序栈s1，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，故还必须有一个临时的顺序栈s2，存放让道的车辆。 当有车辆进停车场时，直接进入s1栈，若s1栈满，则进入便道（链队列q）。若有s1中车辆x离开时

5、，先让在x后面进栈的车从s1退栈并进栈到s2中，让x离开并收取停车费，然后，再把s2中的所有车辆退栈并重新进入s1栈，最后，将链队列q的队头车辆进栈到s1中并删除队头车辆。若有链队列q（便道）中的车辆y离开时，从链队列中删除该车辆即可，不收停车费。 车辆的数据可以表示为（车辆编号，到达/离开时间）。 题目四医务室模拟 问题描述：假设只有一名医生，在一段时间内随机地来几名病人，假设病人到达的时间间隔为014之间的某个随机值，每个病人所需处理时间为19分钟的某个随机值。试用队列结构进行模拟。 实现要求：要求输出医生的总等待时间和病人的平均等待时间。 设计思路提示：计算机模拟事件处理时，程序按模拟环

6、境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达的病人看 病。当一个病人就诊完毕而下一位还没到达时，时间立即推进为下一位病人，中间时间为医生空闲时间。当一位病人就诊还没结束，另有一些病人到达，则这些病人应依次排队，等候就诊。 题目五哈夫曼树的建立及应用 1、给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。 2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。 三、算法描述 将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。 建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组

7、，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。 要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。 设计报告要求 一、封面如下： 数据结构课程设计报告 专业 班级 姓名 学号 指导老师 评分 完成时间 二、正文内容如下： 1、设计题目 2、设计要求 3、设计思路 4、心得体会（必须有运行结果截图）。 5、源程序清单 三、用16开纸打印