算法与数据结构课程设计题目及任务书

1、课程设计题目课程设计题一 ：学生成绩管理系统设计目的：1. 掌握线性链表的建立。2. 掌握线性链表的基本操作。3. 掌握查找的基本算法。设计内容：利用线性链表实现学生成绩管理系统， 具体功能： 输入、输出、插入、删除、 查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出，并能在 屏幕上输出操作前后的结果。设计要求 ：1. 写出系统需求分析，并建模。2. 输出操作前后的结果。课程设计题二：停车场管理系统设计目的：1. 掌握栈和队列的建立。2. 掌握栈和队列的基本操作。3. 深入了解栈和队列的特性 ,以便在解决实际问题中灵活运用它们。4. 加深对栈和队列的理解和认识。设计内容 ：设有一

2、个可以停放 n 辆汽车的狭长停车场 , 它只有一个大门可以供车辆进 出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（ 最先到达的第一辆车放在停车场的最里面 ） 。如果停车场已放满 n 辆车, 则后来的车辆只 能在停车场大门外的便道上等待 ,一旦停车场内有车开走 , 则排在便道上的第一 辆车就进入停车场。停车场内如有某辆车要开走 , 在他之后进入停车场的车都必 须先退出停车场为它让路 ,待其开出停车场后 , 这些车辆在依原来的次序进场。 每 辆车在离开停车场时 , 都应依据它在停车场内停留的时间长短交费。如果停留在 便道上的车未进停车场就要离去 ,允许其离去 ,不收停车费,并且仍

3、然保持在便道 上等待的车辆的次序。编制一程序模拟该停车场的管理。设计要求 ：1. 以栈模拟停车场 ,以队列模拟车场外的便道 ,按照从终端读入的输入数据序列 进行模拟管理。2. 每一组输入数据包括三个数据项：汽车 “到达 ”或“离去”信息、汽车牌照号码 以及到达或离去的时刻。3. 对每一组输入数据进行操作后的输出信息为： 若是车辆到达 ,则输出汽车在停 车场或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时 间和应交纳的费用 （在便道上停留的时间不收费，功能可自己添加 ）。课程设计题三：家谱管理系统设计目的：1. 掌握树的逻辑结构、存储结构及其特点。2. 掌握树的基本操作，并在在解决

4、实际问题中灵活运用它们。3. 加深对栈和队列的理解和认识。设计内容：家谱（或称族谱） 是一种以表谱形式， 记载一个以血缘关系为主体的家族世 系繁衍和重要人物事迹的特殊图书体裁。 家谱是中国特有的文化遗产， 是中华民 族的三大文献（国史、地志、族谱）之一，属珍贵的人文资料，对于历史学、民 俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。本课 程设计对家谱管理进行简单的模拟， 以实现查看祖先和子孙个人信息、 插入家族 成员、删除家族成员等功能。设计要求 ：完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定 义家族成员的数据结构， 然后将每个功能写成一个函数来完成对

5、数据的操作， 最 后完成主函数以验证各个函数功能并得出运行结果。课程设计题四：哈夫曼编 /译码器设计目的 ：1. 掌握建立哈夫曼树和哈夫曼编码的方法。2. 掌握哈夫曼编码的实际应用方法。设计内容：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间 , 降 低传输成本。但是, 这要求在发送端通过一个编码系统对待传数据预先编码 , 在接 收端将传来的数据进行译码。对于双工信道 （ 即可以双向传输信息的信道 ）, 每端 都需要一个完成的编 译码系统。试为这样的信息收发站写一个哈夫曼的编 译码 系统。设计要求 ：1. 初始化。根据上课时给出的英文字母的使用频度，建立哈夫曼树。2. 编码。利

6、用已建好的哈夫曼树，对电报正文进行编码。3. 译码。对编码好的内容进行译码。4. 打印编码。5. 打印哈夫曼树。课程设计题五 ：交通咨询系统设计设计目的：1. 熟练掌握迪杰斯特拉算法和费洛伊德算法， 能够利用它们解决最短路径问题。设计内容：设计一个交通咨询系统， 能让旅客咨询从任一个城市顶点到另一个城市顶点 之间的最短路径问题（可参考教材 P187 交通图实例建立无向图）。设计分三个 部分，一是建立交通网络图的存储结构； 二是解决单源最短路径问题； 最后再实 现两个城市顶点之间的最短路径问题。最短路径问题的提出随着计算机的普及以及地理信息科学的发展， GIS 因其 强大的功能得到日益广泛和深入

7、的应用。网络分析作为 GIS 最主要的功能之一， 在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计 中发挥了重要的作用。而网络分析中最基本和关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量， 如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低 费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统 等（ 110报警、 119火警以及医疗救护系统），这些系统一般要求计算出到出事 地点的最佳路线的时间一般在 1s-3s ，在行车过程中还需要实时计算出车辆前方 的行驶路线， 这就决定了最短路径问题的实

8、现应该是高效率的。 最优路径问题不 仅包括最短路径问题， 还有可能涉及到最少时间问题、 最少收费（存在收费公路） 问题、或者是几个问题的综合，这时将必须考虑道路级别、道路流量、道路穿越 代价（如红灯平均等待时间）等诸多因素。但是必须指出的是，一般来说最优路 径在距离上应该是最短的， 但最短路径在行驶时间和能源消耗的意义上未必是最 优的。其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最 短路径算法。设计要求：1. 建立交通网络网的存储结构2. 总体设计要画流程图3. 提供程序测试方案。4. 界面友好。课程设计题六：列车管理系统设计目的：综合运用链表知识解决实际问题的能力。设计内容

9、：设计火车售票处的计算机系统可以为客户提供下列各项服务： 1. 查询列车信 息：根据旅客提出的起始站和终点站名输出下列信息，列车车次、发车时刻、到 达时刻、运行时间、硬座票价、硬卧票价（分为上中下铺三种情况） 、软卧票价 （分上下两种情况），以及每个途经站点的站名、到达时间、发车时间、运行里 程等信息； 2.录入列车信息； 3. 修改列车信息； 4. 删除列车信息； 5. 浏览所有 列车信息； 6. 其它必要功能。设计要求：1. 要求采用链表方式存储所有列车车次基本信息 （如车次名称等），对于其中的 每个列车车次，也采用链表方式存储各个途经站点信息；2. 能够支持查询、修改、增加、删除等信息；

10、3. 建议提供保存和打开功能，用户可以把所有信息保存到硬盘文件上，也可以 从硬盘文件上读取信息；4. 界面要友好课程设计题七：寻找关键路径设计目的：1. 熟练掌握图的存储表示方法；2. 熟练掌握在 AOE 和 AOV 中进行拓扑排序以及寻找关键路径的算法。设计内容：建立图的存储结构， 能够输入图的顶点和边的信息， 并存储到相应存储结构 中，再编写函数实现图的关键路径寻找方法。设计要求 ：1. 选择邻接矩阵作为有向图的存储结构模拟整个过程，并输出关键路径。2. 自行设计数据调试程序课程设计题八：教学计划编制问题设计内容：大学的每个专业都要制订教学计划。 假设任何专业都有固定的学习年限， 每 学年

11、含两学期， 每学期的时间长度和学分上限均相等。 每个专业开设的课程都是 确定的，而且课程在开设时间的安排必须满足先修关系。 每门课程有哪些先修课 程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样 的前提下设计一个教学计划编制程序。设计要求 ：1. 输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占 3 位的字母数字串）、学分和直接先修课的课程号。2. 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中3. 若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到 用户指定的文件中。计划的表

12、格格式自行设计。课程设计题九：电梯模拟系统（1）模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停 留。五个楼层由下至上依次称为地下层、第一层、第二层、第三层和第四层，其 中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来该层 候命。五个楼层从下到上的编号为： 0、1、2、3、4。除了地下层外，每一层都 有一个要求向下的按钮除了第四层外， 每一层都有一个要求向上的按钮。 对应的 变量为： CallUp0.3 和 CallDown1.4 。电梯内的五个目标层按钮对应的变 量为： CallCar0.4 。（2）电梯一共有七个状态，即正在开门（ Opening）、已开门（

13、Opened）、 正在关门（ Closing ）、已关门（ Closed ）、等待（ Waiting ）、移动（Moving）、 减速（ Decelerate ）。（3）乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长 等待时间，一旦等候电梯时间过长，他将放弃。对于在楼层内等待电梯的乘客， 将插入在等候队列里，每一层有两个等候队列，一队要求向上，一队要求向下， 用链队列来实现。 对于在电梯内的乘客， 用五个乘客栈来实现， 该乘客要去哪一 层，就把他放在相应编号的栈中，对应变量为 EleStack0 4 。（4）模拟时钟从 0 开始，时间单位为 0.1 秒。人和电梯的各种动作均要耗

14、费一定的时间单位（简记为 t ）：有人进出时，电梯每隔 40t 测试一次，若无人进出，则关门 关门和开门各需要 20t每个人进出电梯均需要 25t电梯加速需要 15t上升时，每一层需要 51t ，减速需要 14t下降时，每一层需要 61t ，减速需要 23t 如果电梯在某层静止时间超过 300t ，则驶回 1层候命。5)按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列课程设计题十：公交线路管理设计目的本项目是对公交车线路信息的简单模拟， 以完成建立公交路线信息、 修改公交路线信息 和删除公交路线信息等功能。设计思路本项目的实质是完成对公交线路信息的建立、查找、插入、修改、删除等功能，

15、可以首 先定义项目的数据结构， 然后将每个功能写成一个函数来完成对数据的操作， 最后完成主函 数以验证各个函数功能并得出运行结果。数据结构公交站点之间的关系可以是任意的，任意两个站点之间都可能相关。而在图形结构中， 结点之间的关系可以是任意的， 图中任意两个数据元素之间都可能相关。 所以可以用图形结 构来表示 n 个公交站点之间以及站点之间可能设置的公交路线，其中网的顶点表示公交站 点，边表示两个站点之间的路线，赋予边的权值表示相应的距离。因为公交路线是有一定的连续关系的， 如果想输出从某一个起始点开始到某一终点结束 的公交路线， 就需要找到从某一顶点开始的第一个邻接点和下一个邻接点。 因为在

16、邻接表中 容易找到任一顶点的第一个邻接点和下一个邻接点，所以本项目使用了图的邻接表存储结 构。邻接表是图的一种链式存储结构。在邻接表中，对图的每一个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点vi 的边(对有向图是以顶点 vi 为尾的弧)。每个结点由三个域组成，其中邻接点域 (adjvex) 指示与顶点 vi 邻接的点在图中的位置，链域 (nextarc) 指 示下一条边或弧的结点；数据域 (info) 存储和边或弧相关的信息，如权值等。每个链表上附 设一个表头结点，在表头结点中，除了设有链域 (firstarc) 指向链表中第一个结点之外，还设 有存储顶点 vi的名或其它有关信

17、息的数据域 (data) 。这些表头结点通常以顺序结构的形式存 储，以便随机访问任意顶点的链表。图的邻接表存储表示结构可形式的说明如下：#define MAX_VERTEX_NUM 20typedef struct ArcNode/弧的结构int adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; / 指向下一条弧的指针InfoType *info; /该弧相关信息的指针/顶点结构ArcNode;typedef struct VNodeVertexType data; /顶点信息ArcNode *firstarc; / 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef struct / 图的结构AdjList vertices;intvexnum, arcnum; /图的当前顶点数和弧数intkind; /图的种类标志ALGraph;课程设计题十一：智能计算器具体要求是以字符序列的形式从终端输入语法正确的、 不含变量的表达式， 并利用给定 的优先关系实现对算术四则混合表达式的求值，并演示在求值过程