13-14-1 数据结构课程设计题目

《数据结构》课程设计题目课程设计题一：学生成绩管理系统

设计目的：掌握线性链表的建立。掌握线性链表的基本操作。掌握查找的基本算法。设计内容：

利用线性链表实现学生成绩管理系统，具体功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出，并能在屏幕上输出操作前后的结果。

设计要求：写出系统需求分析，并建模。编程实现，界面友好。输出操作前后的结果。课程设计题二：停车场管理系统

设计目的：掌握栈和队列的建立。掌握栈和队列的基本操作。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们。加深对栈和队列的理解和认识。设计内容：

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

设计要求：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费，功能自己添加)。课程设计题三：约瑟夫(Joseph)环

设计目的：掌握单向循环链表的建立。掌握单向循环链表的操作。设计内容：

编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。请设计一个程序求出出列顺序。

设计要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7，7个人的密码依次为3，1，7，2，4，7，4，首先m=6，则正确的输出是什么？输入数据：建立输入函数处理输入的数据，输入m的初值n，输入每个人的密码，建立单向循环链表。输出形式：建立一个输出函数，将正确的出列顺序输出。课程设计题四：文学研究助手的实现

设计目的：熟悉串类型的实现方法和文本匹配方法。熟悉一般文字处理软件的设计方法。设计内容：

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

设计要求：英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。设计题五：稀疏矩阵的运算

设计目的：掌握稀疏矩阵的压缩存储方法。掌握稀疏矩阵的基本操作。设计内容：

设计一个稀疏矩阵的运算器。

设计要求：动态创建稀疏矩阵。实现稀疏矩阵的输出显示。实现稀疏矩阵的加法。实现稀疏矩阵的减法。实现稀疏矩阵的转置。

课程设计题六：哈夫曼树及其应用

设计目的：熟悉树的各种存储结构及其特点。掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。设计内容：

欲发一封内容为AABBCAB……(共长100字符，其中:A、B、C、D、E、F分别有7、9、12、22、23、27个)的电报报文，实现哈夫曼编码。

设计要求：分析系统需求。建立哈夫曼树。进行哈夫曼编码，并求出平均编码长度。编程实现2、3步骤。课程设计题七：哈夫曼编/译码器

设计目的：掌握建立哈夫曼树和哈夫曼编码的方法。掌握哈夫曼编码的实际应用方法。设计内容：

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完成的编\译码系统。试为这样的信息收发站写一个哈夫曼的编\译码系统。

设计要求：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。编码。利用已建好的哈夫曼树，对正文进行编码。译码。对编码好的内容进行译码。打印编码。打印哈夫曼树。课程设计题八：图的遍历演示

设计目的：理解图的基本概念。熟悉图的各种存储结构及其构造算法。掌握图的遍历方法。设计内容：

实现图的深度优先、广度优先遍历算法，并输出原图结构及遍历结果。

设计要求：两种遍历方法必须都要实现。界面友好，函数功能要划分合理。程序要加必要的注释。提供程序测试方案。课程设计题九：交通咨询系统设计

设计目的：熟练掌握迪杰斯特拉算法熟练费洛伊德求最短路径算法。能够解决工程项目实施过程中的关键路径问题。设计内容：

设计一个交通咨询系统，能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。

设计要求：建立交通网络网的存储结构。总体设计要画流程图。提供程序测试方案。界面友好。课程设计题十：航班信息的查询与检索

设计目的：深刻理解排序的定义和各种排序方法的特点，并能灵活的应用；掌握描述查找过程的判定树的构造方法。设计内容：

设计民航售票处的计算机系统可以为客户提供下列各项服务：查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行、最近一天航班的日期和余票额；

承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况。

设计要求：对飞机航班信息进行排序和查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。采用基数排序法对一组具有结构特点的飞机航班号进行排序。利用二分查找法对排好序的航班记录按航班号实现快速排序。每个航班记录包括八项，分别为：航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等。课程设计题十一、算术表达式求值设计目的：掌握栈的建立。掌握栈的基本操作。深入了解栈的特性，以便在解决实际问题中灵活运用它们。加深对栈的理解和认识。设计内容：对带括号的任意算术表达式求值。设计要求：利用栈判断表达式的正确性，括号是否匹配。利用栈进行任意带括号的算术表达式的四则混合运算。数据类型为浮点型。课程设计题十二：一元多项式相加设计目的：掌握线性链表的建立。掌握线性链表的基本操作。掌握线性链表合并的算法。设计内容：

利用链表实现一元多项式相加。设计要求：一元多项式需要动态建立。回显一元多项式的具体表达式。一元多项式的项数不能是固定值，由键盘任意输入。程序应能进行循环运算，不需运算时，选择相应退出功能。课程设计题十三：二叉树基本操作设计目的：掌握二叉树的二叉链表存储方式。掌握二叉树的建立。掌握二叉树的遍历方法：先序、中序、后序遍历。掌握二叉树的基本性质。设计内容：

利用二叉链表建立二叉树并实现其基本操作。设计要求：按先序次序输入二叉树中节点的值，动态建立二叉树。输出二叉树的先序、中序、后序遍历序列。输出二叉树中结点个数。输出二叉树的深度。课程设计题十四：拓扑排序的应用设计目的：掌握有向图邻接表存储结构掌握AOV网深刻理解拓扑排序设计内容：以本专业课程系统为例，以本专业课程系统为例，根据课程之间的依赖关系制定课程安排计划，并满足各学期课程数目大致相同。设计要求：输入本专业在大学期间的所有课程，并显示课程之间的关系。按8学期计算，使课程尽可能安排在前几个学期，课程数不少于16门。给出教学计划，即每学期应该如何安排课程，才能满足课程间的依赖关系。课程设计题十五：图书管理系统

设计目的：掌握顺序表的堆分配存储方式。掌握顺序表的基本操作。正确应用查找算法。正确应用排序算法。设计内容：

利用顺序表实现图书管理系统。

设计要求：实现图书信息的基本操作输入、输出、插入、删除、追加、显示、保存、实现查找功能（按不同关键字查找）。实现排序功能（按不同关键字排序）。具有分类统计功能。课程设计题十六：宿舍管理查询系统设计目的：掌握顺序表的存储方式。掌握基本的排序算法。掌握二分查找等查找算法。设计内容：为学生宿舍管理人员编写一个能进行宿舍管理、查询软件。设计要求：建立关于宿舍及学生的数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)查询菜单：用二分查找实现按姓名查询、按学号查询、按房号查询。课程设计题十七：构造可以使n个城市连接的最小生成树（限1人完成）设计目的：掌握图的邻接矩阵的存储方式掌握Prim或Kruskal最小生成树的算法设计内容：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。设计要求：城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。课程设计题十八：文本文件单词的检索与计数设计目的：熟悉串类型的实现方法和文本匹配方法。熟悉一般文字处理软件的