《数据结构》课程大作业题目列表

《数据结构》课程大作业题目列表

《数据结构》课程大作业要求：

每3~4名同学一组，每组任选作业题目中的一题，组内同学一起进行分析，每个人负责题目中的一个模块进行设计和实现。最后一次上机时，在上机实验室现场，每组分别演示自己的程序，每个同学讲解自己设计的部分，由老师打分。该分数与平时作业和平时上机一起计算进总成绩中。

1. 航空客运订票系统 ................................................................................................................... 2 2. 全国交通咨询模拟 ................................................................................................................... 4 3. 五子棋的设计与实现 ............................................................................................................... 6 4. 学生成绩管理系统 ................................................................................................................... 7 5. 城市导游咨询 ........................................................................................................................... 9 6. 图书管理系统 ......................................................................................................................... 11 7. 简单文本编辑器 ..................................................................................................................... 14 8. 排课软件 ................................................................................................................................. 15

1. 航空客运订票系统

1.1. 问题描述

航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。

每条航线所涉及的信息有：起点站名、终点站名、航班号、起降时间、飞机号、飞行周日（星期几）、票价、票价折扣、乘员定额、余票量、已订票的客户名单（包括姓名、证件类型、证件号码、订票数量、航班情况、舱位等级1，2或3，订单要有编号）以及等候替补的客户名单（包括姓名、所需票量）。

1.2. 功能描述

1. 录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具

体数据自定）

2. 对飞机航班信息进行排序和查询：可按航班的航班号、起点站、到达站、起

飞时间以及到达时间等信息查询某个航线的情况。（可以输入一个或多个信息进行查询。设计中，要求采用基数排序方法对一组具有结构特征的飞机航班号进行排序，利用二分查找的方法对排好序的航班记录按照航班号实现快速查找，而其他次关键字的查找则采用最简单的顺序查找方法进行。当然也可以使用其它的排序方法）

假设每个航班记录包括8项，分别是：航班号，起点站，到达战，班期，起飞时间，到达时间，飞机型号以及票价等，假设的航班信息表（8条记录）入下表所示：

航班信息表 航班号 CA1544 MU5341 CZ3869 MU3682 HU1836 CZ3528 MU4594 K0 C 起点站 合肥 上海 重庆 桂林 上海 成都 昆明 K1 Z 终点站 北京 广州 深圳 南京 北京 厦门 西安 K2 3 班期 1.2.4.5 每日 2.4.6 2.3.4.6.7 每日 1.3.4.5.7 1.3.5.6 起飞时间 到达时间 机型 1055 1420 0855 2050 0940 1510 1015 K3 8 1240 1615 1035 2215 1120 1650 1140 K4 6 733 M90 733 M90 738 CRJ 328 K5 9 票价 960 1280 1010 1380 1250 1060 1160 其中航班号的格式为： 其中k0和k1的输入值是航空公司的名称，用2个大写字母表示，后4位为航班编号，这种航班号关键字可未成2段，即字母和数字。其余7项输入内容因不涉及本设计的核心，因此除了票价为数值型外，均定义为字符型即可。

3. 订票：可以订票，如果该航班已经无票，可以提供相关可选择航班（订票情

况可以存在一个数据文件中，结构自己设定。相关可选择航班可包括进行中转的航班，比如输入西安－杭州，相关可选择航班包括西安－重庆－杭州） 4. 退票：可退票，退票后修改相关数据文件；（若有等候替补的客户名单，则

要及时通知这些客户并修改已订票客户名单）

5. 修改航班信息：当航班信息改变可以修改航班数据文件

6. 当客户不清楚航班的信息情况时，能通过输入起点站和终点站，输出费用最

小的航线。『若无直达航线，可输出中转航线。若有直达航线，但费用并不是最小，则同时输出费用最小的直达航线（在直达航线中费用最小的航线）和费用最小的中转航线（在所有的航线中费用最小的航线）』

1.3. 设计要求

1. 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；

2. 对以上每一个功能，都要输出一个例子进行相关的说明； 3. 上述功能的完成涉及到线性表、队列，查找和图 4. 上述系统的设计不可过于小，适中即可。

5. 可以为程序增加简单的界面，但是不要过多注重界面，而忽略程序功能的实

现。

1.4. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。

2. 全国交通咨询模拟

2.1. 问题描述

出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能的少，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供最优决策的交通咨询。

2.2. 功能描述

（1）提供对城市信息进行编辑（如：添加功删除）的功能

（2）城市之间有目前种交通工具：火车和飞机。提供对列车时间表和飞机航班进行编辑（增设或删除）的功能。

（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。

（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时坐哪一趟列车哪一次班机到何地。

2.3. 设计要求

提供对全国城市交通图和列车时刻表及飞机航班表的编辑（键盘输入）。 学生可以上网查找相关的算法，但是严禁不加思考和修改，直接拷贝使用，最后的文档中必须包含对本程序使用的核心数据结构的评价（优缺点等），若有，应包含改进的地方。

2.4. 实现提示

（1）飞机航班表的信息包括：起始站台票出发时间、终点站的到达时间和票价；列车时刻表则根据交通图给出各个路段的详细信息。

（2）以邻接表作交通图的存储结构，表示边的结点内除了含有邻接点的信息外，还应包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。

2.5. 选作要求

对全国城市交通图和列车时刻表及飞机航班表的编辑，使用文件形式输入； 可以为旅客提供两种以上的最优决策选择；

可以为程序增加简单的界面，但是不要因为界面，而延误了程序基本的功能实现。

（参考数据结构题集（C语言版）P 153）

2.6. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。

3. 五子棋的设计与实现

3.1. 问题描述

五子棋是起源于中国古代的传统黑白棋种之一，五子棋专用棋盘为十五路（15*15），盘面上横竖各15条、平行线、纵横、线路为黑色，构成225个交叉点。国际规则为：

（1）：对局人数： 2人。一人持黑子，一人持白子。 （2）：对局方式： 2人轮流一子一子的将棋子置於棋盘的点上。先着者持黑，后着者持白。 （3）：胜利条件：先下出连五者则为胜利。 试用相应的数据结构描述，并编程实现。

3.2. 功能描述

程序运行时，可以选择电脑和人对弈或者人人对弈，并设定先下着，通过一些简单的输入进行对弈；

该程序的基本要求为上面所述，如有其他问题，自行规定，将其设计到程序中，并在报告中声明；

鼓励学生上网查找相关的算法，但是严禁不加思考和修改，直接拷贝使用，最后的文档中必须包含对本程序使用的核心数据结构的评价（优缺点等），若有，应包含改进的地方。

3.3. 选作要求

? 为程序提供悔棋等功能；

? 如果条件允许，可以为程序增加简单的界面，但是不要因为界面，而延

误了程序基本的功能实现。

3.4. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。

4. 学生成绩管理系统

4.1. 问题描述

在年级成绩管理系统中，希望处理各班信息及各班每个学生的学习情况信息，其中班级信息包括班号和名称，学生学习情况信息包括学号，姓名，班号等，及已学课程的课程号及成绩，并能使管理人员通过界面完成对班级、学生信息的录入及对数据的查找和浏览。

4.2. 功能描述

? ? ? ? ? ? ? ?

登记各班的学生基本情况（学号，姓名，性别，年龄，电话等信息） 插入某班某个学生的基本情况 修改各班学生基本情况

删除某班某个学生或某班所有学生基本情况 登记各班所有学生各门课的成绩 修改某个学生某门功课的成绩 浏览各班信息

查找，浏览每个学生的基本信息 ? 查找，浏览每个学生的全部成绩信息

4.3. 设计要求

1. ? ? ? ?

分4个功能模块实现

班级管理模块：主要实现的功能为添加，删除某个班级

学生管理模块：实现的功能为登记，修改，删除某班某个学生的基本情况 成绩管理模块：实现的功能为登记，修改某个学生某门课的成绩

查选浏览模块：实现的功能为浏览各个班级信息，查找，浏览每个学生的基本信息，和全部成绩信息 2. 为用户操作提供人机界面。

4.4. 实现提示

本系统可以看作是一个树结构的应用问题，可考虑采用树的左孩子右兄弟存储结构：

Head

学生1 学生2 班级1 班级2

班级n 学生n ???? ????

成绩1 成绩2 成绩n 4.5. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。

5. 城市导游咨询

5.1. 问题描述

设计一个城市导游程序，为来旅游的游客提供景点和道路信息查询服务。

5.2. 功能描述

? ? ? ? ? ?

设计一个你所在城市的旅游景点和道路平面图，所含景点不少于10个。 可以添加、修改和删除景点以及景点的信息。

可以添加和删除连接景点的道路及道路长度信息。 景点信息包括景点的介绍、位置、道路等信息。 为游客提供图中任意景点相关信息查询。

为游客提供图中任意景点问路查询，即查询任意两个景点之间的一条最短的简单路径。

? 提供图中任意景点问路查询，即求任意两个景点之间的所有路径。

? 提供图中多个景点的最佳访问路线查选，即求途经这个景点的最佳（短）路

径。

5.3. 实现提示

? 以图中顶点表示校内各景点，存放景点名称，代号，简介等信息，以边表示

道路，存放道路长度等相关信息。

? 一般情况下，校园的道路是双向通行，可设校园平面图是一个无向网。顶点

和边均含有相关信息。

5.4. 选作要求

? 求城市景点图的关节点。

? 扩充道路信息，如道路类别（车道，人行道等），沿途景色等级，以至可按

游客所需分别查询人行路径或车行路径或观景路径。

? 考虑增加公交车查询，可添加公交车的名称、站名和途经的道路、票价等信

息，方便游客查询景点的公交车路线。

5.5. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。 （参考数据结构题集（C语言版）P 151）

6. 图书管理系统

6.1. 问题描述

图书信息表所表示的是一个数据库文件。图书管理一般包括：图书采编、图书编目、图书查询与图书流通（借、还书）等。要求设计一个图书管理信息系统，用计算机实现上述系统功能。图书管理系统的基本业务活动包括：对一本书的采编入库，清除库存，借阅和归还等等。试设计一个图书管理系统，将上诉业务活动借助于计算机系统完成。

6.2. 功能描述

? 每种书的登记内容至少包括书号，书名，著者，现存量和总库存量等五项 ? 基本业务活动通过书号（即关键字）进行，所以可考虑用B树（2－3）对书号建

立索引，以获得高效率。

? 建立一个图书信息数据文件来存储图书信息，并以书号、书名、作者及出版社为

关键字为图书文件建立若干索引文件。 ? 系统应实现的操作及其功能定义如下：

1． 采编入库：新购入一种书，经分类和确定书号之后登记到图书帐目中去，如果这种书再帐目中有，则只将总库存量增加；

2． 清除库存：某种书已无保留价值，将从图书帐目中注销； 3． 查询：提供关于书号、书名、作者及出版社的图书查询；

4． 借阅：如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限；

5． 归还：注销对借阅者的登记，改变该书的现存根据实际情况而定。

6.3. 设计要求

1. 建立一个图书信息数据库文件来存储图书信息。用户可输入若干种书的记

录，系统建立一个以书号为关键字的索引文件；在主数据库文件中建立以书名、作者以及出版社作为关键字的索引以及对应的索引链头文件，如下图所示： 记录书号 号 1 1021 书名 数据指针1 0 作者 指针2 李小0 出版社 人民指针3 0 分藏书类 量 021 8 借出数 0 2 3 4 5 6 7 8 1041 1106 1108 1203 2105 1012 0109 库 数据结构 操作系统 数据结构 程序设计 数据库 数据结构 程序设计 0 0 2 0 1 4 5 云 刘晓阳 许海平 孙华英 李小云 孙海平 李小云 刘晓阳 0 0 0 1 3 5 2 邮电 中国科学 人民邮电 清华大学 中国科学 清华大学 人民邮电 清华大学 0 1 0 2 4 3 6 013 024 013 035 021 013 035 6 7 5 6 6 5 7 0 0 0 0 0 0 0 书名 数据库 数据结构 操作系统 程序设计 作者 李小云 刘晓阳 许海平 孙华英 出版社 人民邮电 中国科学 清华大学 a) 图书主索引文件 链头地址 6 7 3 8 b)书名索引链头文件 链头地址 7 8 6 4 c)作者索引链头文件 链头指针 7 5 8 d)出版社索引链头文件 长度 2 3 1 2 长度 3 2 2 1 长度 3 2 3 2. 建立关于书号、书名、作者及出版社的图书查询；

3. 实现图书的借还子系统，包括建立读者文件、借还文件、读者管理及图书借

还等相关的处理。

4. 实现提示

? 2－3树的查找算法是基础，入库和清除操作都要调要。难点在于删除关键字的

算法，因而只要算法对2－3树适用就可以了。

? 每种书的记录可以用动（或静）态链式结构，借阅登记信息可以链接在相应的那

种书的记录之后

5. 选作内容

? 将一次会话过程（即程序一次运行）中的全部人机对话记入一个日志文件“log”

中去。

? 增加列出某著者全部著作名的操作。思考如何提高这一操作的效率。

? 增加列出某种书状态的操作。状态信息除了包括这种书记录的全部信息外还包括

最早到期（包括预期）的借阅者证号，日期可用整数实现，以求简化。 ? 增加预约借书功能。

6. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。 （参考数据结构题集（C语言版）P 167）

7. 简单文本编辑器

7.1. 问题描述

参照Turbo C编辑器或Windows的记事本等文本编辑器，使用串的技术设计一个功能简单的文本编辑器，要求具备字符录入、删除、光标移动、查找等基本功能。

7.2. 功能描述

从文件系统中打开文本文件（文件名为edit.txt，位于当前执行程序的目录下），可以进行简单的编辑操作，要求：

（1） 每行最多不超过80个字符，共N行（N>=1）; （2） 可以进行文字的添加、删除； （3） 可以通过光标定位到指定位置；

（4） 查找字串并定位光标（快捷键：CTRL+F或CTRL+S）； （5） 退出（快捷键：ESC）。

存储结构使用链表和串，分别用几个子函数实现相应的功能。

输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。

7.3. 设计要求

实现对串的基本操作（插入、删除、查找）函数，并在此基础上，建立以串为结点单元的单链表，屏幕的每行对应单链表的每个串结点，通过光标的上、下、左、右、翻页移动，进行链表的结点的定位，实现一个简单文本编辑器的基本功能。

7.4. 设计报告格式及主要内容

(1)需求分析说明文档

(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）

(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。

(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。

8. 排课软件

8.1. 问题描述

大学的每个专业都要进行排课。假设任何专业都有固定的学习年限，每学年含两学期，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的。每门课程恰好占一个学期，假定每天上午与下午各有5节课。试在这样的前提下设计一个教学计划编制程序。

8.2. 功能要求

1、 输入数据包括：各学期所开的课程数（必须使每学期所开的课程数之和与课程总数相

等），课程编号，课程名称，周学时数，指定开课学期，先决条件。如指定开课学期为0，表示由电脑自行制定开课学期。

2、 如输入数据不合理，比如每学期所开的课程数之和与课程总数不相等，应显示适当的提

示信息。

3、 试用文本文件存储输入数据。

4、 试用文本文件存储产生的各学期的课表。

8.3. 设计要求

可参考如下的课程结构定义： //课程结构 struct CourseType

{ char courseNo[5]; //课程编号 char courseName[100]; //课程名 int period; //学时数 int term; //开设学期 } 在课程表类Schedule中，包括输入与输出流文件，有向图，顶点入度，每学期应开设的课程数等数据成员，还包括读数据、写排课结果，利用拓扑排序的方法等。

课程信息由文件course_inf.txt表示，为了提高可读性，以//开始的行为注释行。 course_inf.txt如下： //课程编号 课程名称 学时数 指定开课学期 先修课程 C01 程序设计基础 5 0 C02 离散数学 6 0 C01 C03 数据结构 4 0 C01,C02 C04 汇编语言 5 0 C01 C05 算法设计与分析 4 0 C03,C04

C06 计算机体系结构 6 0 C11 C07 编译原理 5 0 C03 C08 操作系统原理 4 0 C05,C06 C09 高等数学 6 0 C10 线性代数 6 0 C09 C11 普通物理 4 0 C09 C12 数值分析 6 0 C09,C10,C11 C30 英语 5 1 C31 英语 5 2 C32 英语 5 3 C33 英语 5 4 C34 英语 5 5 C35 英语 5 6 C36 英语 5 7 C37 英语 5 8 C38 大学语文 3 1

//下面为各学期所开的课程数，必须使每学期所开的课程数之和与课程总数相等 6 7 3 6 5 5 5 1

C06 计算机体系结构 6 0 C11 C07 编译原理 5 0 C03 C08 操作系统原理 4 0 C05,C06 C09 高等数学 6 0 C10 线性代数 6 0 C09 C11 普通物理 4 0 C09 C12 数值分析 6 0 C09,C10,C11 C30 英语 5 1 C31 英语 5 2 C32 英语 5 3 C33 英语 5 4 C34 英语 5 5 C35 英语 5 6 C36 英语 5 7 C37 英语 5 8 C38 大学语文 3 1

//下面为各学期所开的课程数，必须使每学期所开的课程数之和与课程总数相等 6 7 3 6 5 5 5 1

本文来源：https://www.bwwdw.com/article/v0mw.html