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

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

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

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

4、种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史、地志、族谱）之一，属珍贵的人文资料，对于历史学、民俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。本课程设计对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。设计要求：完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。课程设计题四：哈夫曼编/译码器 设计目的：1. 掌握建立

5、哈夫曼树和哈夫曼编码的方法。2. 掌握哈夫曼编码的实际应用方法。设计内容：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完成的编译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。设计要求：1. 初始化。根据上课时给出的英文字母的使用频度，建立哈夫曼树。2. 编码。利用已建好的哈夫曼树，对电报正文进行编码。3. 译码。对编码好的内容进行译码。4. 打印编码。5. 打印哈夫曼树。 课程设计题五：交通咨询系统设计 设计目的

6、： 1. 熟练掌握迪杰斯特拉算法和费洛伊德算法，能够利用它们解决最短路径问题。设计内容：设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径问题（可参考教材P187交通图实例建立无向图）。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。最短路径问题的提出随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。而网络分析中最基本和关键的问题是最短路径

7、问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间一般在1s-3s，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。最优路径问题不仅包括最短路径问题，还有可能涉及到最少时间问题、最少收费（存在收费公路）问题、或者是几个问题的综合，这时将必须考虑道路级别、道路流量、道路穿越代价（如红灯平均等待时间）等

8、诸多因素。但是必须指出的是，一般来说最优路径在距离上应该是最短的，但最短路径在行驶时间和能源消耗的意义上未必是最优的。其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。设计要求： 1. 建立交通网络网的存储结构。2. 总体设计要画流程图。3. 提供程序测试方案。4. 界面友好。课程设计题六：列车管理系统设计目的： 综合运用链表知识解决实际问题的能力。设计内容： 设计火车售票处的计算机系统可以为客户提供下列各项服务：1.查询列车信息：根据旅客提出的起始站和终点站名输出下列信息，列车车次、发车时刻、到达时刻、运行时间、硬座票价、硬卧票价（分为上中下铺三种情况）、软卧票价（

9、分上下两种情况），以及每个途经站点的站名、到达时间、发车时间、运行里程等信息；2.录入列车信息；3. 修改列车信息；4. 删除列车信息；5. 浏览所有列车信息；6. 其它必要功能。设计要求： 1. 要求采用链表方式存储所有列车车次基本信息（如车次名称等），对于其中的每个列车车次，也采用链表方式存储各个途经站点信息；2. 能够支持查询、修改、增加、删除等信息；3. 建议提供保存和打开功能，用户可以把所有信息保存到硬盘文件上，也可以从硬盘文件上读取信息；4. 界面要友好。课程设计题七：寻找关键路径设计目的： 1. 熟练掌握图的存储表示方法；2. 熟练掌握在AOE和AOV中进行拓扑排序以及寻找关键路

10、径的算法。设计内容：建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，再编写函数实现图的关键路径寻找方法。设计要求：1. 选择邻接矩阵作为有向图的存储结构模拟整个过程，并输出关键路径。2. 自行设计数据调试程序课程设计题八：教学计划编制问题设计内容：大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。设计要求：1. 输入

11、参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。2. 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。3. 若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。课程设计题九：电梯模拟系统（1）模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层、第一层、第二层、第三层和第四层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来该层候命。五个楼层从下到上的编号为

12、：0、1、2、3、4。除了地下层外，每一层都有一个要求向下的按钮除了第四层外，每一层都有一个要求向上的按钮。对应的变量为：CallUp0.3和CallDown1.4。电梯内的五个目标层按钮对应的变量为：CallCar0.4。（2）电梯一共有七个状态，即正在开门（Opening）、已开门（Opened）、正在关门（Closing）、已关门（Closed）、等待（Waiting）、移动（Moving）、减速（Decelerate）。（3）乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。对于在楼层内等待电梯的乘客，将插入在等候队列里，每一层有两个

13、等候队列，一队要求向上，一队要求向下，用链队列来实现。对于在电梯内的乘客，用五个乘客栈来实现，该乘客要去哪一层，就把他放在相应编号的栈中，对应变量为EleStack04。（4）模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要耗费一定的时间单位（简记为t）：有人进出时，电梯每隔40t测试一次，若无人进出，则关门关门和开门各需要20t每个人进出电梯均需要25t电梯加速需要15t上升时，每一层需要51t，减速需要14t下降时，每一层需要61t，减速需要23t如果电梯在某层静止时间超过300t，则驶回1层候命。（5）按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。课程设计题十：

14、公交线路管理设计目的本项目是对公交车线路信息的简单模拟，以完成建立公交路线信息、修改公交路线信息和删除公交路线信息等功能。设计思路本项目的实质是完成对公交线路信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。数据结构公交站点之间的关系可以是任意的，任意两个站点之间都可能相关。而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。所以可以用图形结构来表示n个公交站点之间以及站点之间可能设置的公交路线，其中网的顶点表示公交站点，边表示两个站点之间的路线，赋予边

15、的权值表示相应的距离。因为公交路线是有一定的连续关系的，如果想输出从某一个起始点开始到某一终点结束的公交路线，就需要找到从某一顶点开始的第一个邻接点和下一个邻接点。因为在邻接表中容易找到任一顶点的第一个邻接点和下一个邻接点，所以本项目使用了图的邻接表存储结构。邻接表是图的一种链式存储结构。在邻接表中，对图的每一个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。每个链

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