数据结构课程设计题目.docx
《数据结构课程设计题目.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计题目.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构课程设计题目
1.通讯录的制作
【问题描述】
设计一个通讯录管理程序。
【基本要求】
1）每条信息至包含：
姓名（NAME）、性别（GENDER）、电话（TEL）、城市（CITY）邮编（EIP）几项。
2）作为一个完整的系统，应具有友好的界面和较强的容错能力
要求：
显示提示选单。
根据选单的选项调用各函数，并完成相应的功能。
能对通讯录的末尾，写入新的信息，并返回选单。
能查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。
（能按姓名、电话、城市3种方式查询）
能修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。
（按姓名、电话）
能删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。
（按姓名、电话）
能显示通讯录中的所有记录。
通讯录信息以文件形式存盘。
2.图书管理系统
【问题描述】
设计一个计算机管理系统完成图书管理基本业务。
【基本要求】
1）每种书的登记内容包括书号、书名、著作者、现存量和库存量；
2）对书号建立索引表（线性表）以提高查找效率；
3）系统主要功能如下：
采编入库：
新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
借阅：
如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
归还：
注销对借阅者的登记，改变该书的现存量。
【进一步完成内容】（选做）
1）系统功能的进一步完善；
2）索引表采用树表。
3.简单的职工管理系统
【问题描述】
设计简单的职工信息管理程序。
对单位的职工进行管理，包括插入、删除、查找、排序等功能。
职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。
【基本要求】
（1）新增一名职工：
将新增职工对象按姓名以字典方式职工管理文件中。
（2）删除一名职工：
从职工管理文件中删除一名职工对象。
（3）查询：
从职工管理文件中查询符合某些条件的职工。
（4）修改：
检索某个职工对象，对其某些属性进行修改。
（5）排序：
按某种需要对职工对象文件进行排序。
【实现提示】
职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。
（1）由键盘输入职工对象，以文件方式保存。
程序执行时先将文件读入内存。
（2）对职工对象中的"姓名"按字典顺序进行排序。
（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。
【选做内容】
将职工对象按散列法存储，并设计解决冲突的方法。
在此基础上实现增、删、查询、修改、排序等操作。
4.仓库管理系统（线性表应用）
【问题描述】
建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物信息、实现货物的入库出库，要求能用文件保存仓库货品信息。
【实现提示】可以采用双向链表的存储结构，如可定义如下的存储结构：
typedefstructdnode/*定义双向链表结构体*/
{intnumber;/*货物编号*/
charname[max];/*货物名称*/
intcounter;/*货物数量*/
structdnode*prior,*next;/*定义两指针，分别指向其前驱和后继*/
}dlnode;
5.运动会分数统计
【问题描述】参加运动会有n个学校，学校编号为1……n。
比赛分成m个男子项目，和w个女子项目。
项目编号为男子1……m，女子m+1……m+w。
不同的项目取前五名或前三名积分；取前五名的积分分别为：
7、5、3、2、1，前三名的积分分别为：
5、3、2；哪些取前五名或前三名由学生自己设定。
（m<=20,n<=20）
【基本要求】
1）可以输入各个项目的前三名或前五名的成绩；
2）能统计各学校总分，
3）可以按学校编号或名称、学校总分、男女团体总分排序输出；
4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
5）数据存入文件并能随时查询
6）规定：
输入数据形式和范围：
可以输入学校的名称，运动项目的名称
输出形式：
有中文提示，各学校分数为整形
界面要求：
有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：
学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：
要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。
进行程序测试，以保证程序的稳定。
测试数据及测试结果请在上交的资料中写明；
6.飞机订票系统
【问题描述】
设计一个飞机订票系统。
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
设计航班信息，订票信息的存储结构，设计程序完成功能。
【基本要求】
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；
订票：
可以订票，如果该航班已经无票，可以提供相关可选择航班；（订票情况可以存在一个数据文件中，结构自己设定）
退票：
可退票，退票后修改相关数据文件；
修改航班信息：
当航班信息改变可以修改航班数据文件
7.校园导游问题
【问题描述】设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
【基本要求】
1）设计校园平面图，在校园景点选10个左右景点。
以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
2）为来访客人提供图中任意景点相关信息的查询。
3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
4）增加、删除、更新有关景点和道路的信息
【实现提示】一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。
顶点和边均含有相关信息。
8.敢死队问题
【问题描述】
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。
如果前一个战士没完成任务，则要再派一个战士上去。
现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。
如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。
以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
【基本要求】至少采用两种不同的数据结构的方法实现。
9.学生搭配问题
【问题描述】
一班有m个女生,有n个男生（m不等于n）,现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴.
【基本要求】
请设计一系统模拟动态地显示出上述过程,要求如下:
1）输出每曲配对情况
2）计算出任何一个男生（编号为X）和任意女生（编号为Y）,在第K曲配对跳舞的情况.至少求出K的两个值.
3）尽量设计出多种算法及程序,可视情况适当加分
提示:
用队列来解决比较方便.
10.教学计划编制问题
【问题描述】
大学的每个专业都要制定教学计划。
假设任何专业都有固定的学习年限，每学年含两学
期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在
开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的，可以有任意多门，
也可以没有。
每门课恰好占一个学期。
试在这样的前提下设计一个教学计划编制程序。
【基本要求】
（1）输入参数包括：
学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：
一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。
计划的表格格式自行设计。
【测试数据】
学期总数：
6；学分上限：
10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。
先修关系如下：
课程编号
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1，C2
C4
汇编语言
C1
C5
语言的设计和分析
C3，C4
C6
计算机原理
C11
C7
编译原理
C5，C3
C8
操作系统
C3，C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C9，C10，C1
【实现提示】
可设学期总数不超过12，课程总数不超过100。
如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。
应建立内部课程序号与课程号之间的对应关系。
11双层停车场管理
【问题描述】
有一个两层的停车场，每层有6个车位，当第一层车停满后才允许使用第二层。
（停车场可用一个二维数组实现，每个数组元素存放一个车牌号）每辆车的信息包括车牌号，层号，车位号，停车时间共4项。
其中停车时间按分钟计算。
【基本要求】
（1）假设停车场初始状态为第一层已经停有4辆车，其车位号依次为1—4，停车时间依次为20，15，10，5。
即先将这四辆车的信息存入文件“car.dat”中（数组的对应元素也要进行赋值）
（2）停车操作：
当一辆车进入停车场时，先输入其车牌号，再为它分配一个层号和一个车位号（分配前先查询车位的使用情况，如果第一层有空则必须停在第一层），停车时间设为5，最后将新停入的汽车的信息添加文件“car.dat”中，并将在此之前的所有车的停车时间加5。
（2）收费管理（取车）：
当有车离开时，输入其车牌号，先按其停车时间计算费用，每5分钟0.2元。
（停车费用可设置一个变量进行保存），同时从文件“car.dat”中删除该车的信息，并将该车对应的车位设置为可使用状态（即二维数组对应元素清零）。
按用户的选择来判断是否要输出停车收费的总计。
（4）输出停车场中全部车辆的信息。
（5）退出系统。
12.迷宫问题
【问题描述】
迷宫实验是取自心理学的一个古典实验。
在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。
盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。
对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。
老鼠经多次实验终于得到它学习走迷宫的路线。
设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【实现提示】
可以利用一个二维数组maze[i][j]表示迷宫，其中1<=i<=m,1<=j<=n,m和n分别代表迷宫的行数和列数。
数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。
假定从maze[1][1]出发，出口位于maze[m][n]，移动方向可以是8个方向（东、东南、南、西南、西、西北、北和东北）。
计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。
为了保证在任何位置上都能沿原路退回，需要用一个后进先出的栈结构来保存从入口到当前位置的路径。
13.哈夫曼编码/译码器
【问题描述】
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼编/译码系统。
【基本要求】
一个完整的系统应具有以下功能：
（1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：
编码（Encoding）。
利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：
印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码写入文件CodePrint中。
（5）T：
印哈夫曼树（TreePrinting）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
【测试数据】
（1）数据一：
已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。
利用此数据对程序进行调试。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：
“THIS PROGRAM IS MY FAVORITE”。
字符
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
57
63
15
1
48
51
80
23
8
18
1
16
1
【实现提示】
（1）文件CodeFile的基类型可以设为子界型bit=0..1。
（2）用户界面可以设计为“菜单”方式：
显示上述功能符号，再加上“Q”，表示运行Quit。
请用户键入一个先功能符，把些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。
（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。
每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
14.模拟旅馆管理系统的一个功能——床位的分配与回收
【问题描述】
某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位（1≤i≤n）。
试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。
【基本要求】
（1）输入数据
分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。
回收时，输入房间等级、房间号和床位号。
（2）输出数据
分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码和床位号码。
分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？
”的询问信息。
若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。
15.家谱管理系统
【问题描述】实现具有下列功能的家谱管理系统
1）.输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：
姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。
2）.实现数据的存盘和读盘。
3）.显示家谱。
4）.显示第n代所有人的信息。
5）.按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。
6）.按照出生日期查询成员名单。
7）.输入两人姓名，确定其关系。
8）.某成员添加孩子。
9）.删除某成员（若其还有后代，则一并删除）。
10）.修改某成员信息。
11）.按出生日期对家谱中所有人排序。
12）.打开一家谱时，提示当天生日的健在成员。
【基本要求】
建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。
界面要求：
有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：
学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。
测试数据：
要求使用1、全部合法数据；2、局部非法数据。
进行程序测试，以保证程序的稳定。
测试数据及测试结果请在上交的资料中写明；
16.活期储蓄帐目管理
【问题描述】 活期储蓄处理中，储户开户、销户、存入、支出活动频繁。
设计一个活期储蓄账目管理系统。
【基本要求】
1）能比较迅速地找到储户的帐户，以实现存款、取款记账；
2）能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。
17.栈的应用:
表达式求值
【问题描述】设计一个表达式求值的程序。
该程序必须可以接受包含（，），+，-，*，/，%，和^（求幂运算符）的中缀表达式，并求出结果。
如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。
【输入要求】
程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。
【输出要求】
对于每一个表达式，将其结果放在“output.txt”文件的每一行中，这些结果可能是值（精确到小数点后两位），也可能是错误信息“ERRORININFIXNOTATION”。
【输入例子】
4.99+5.99+6.99*1.06
（3*5*（4+8）%2）
2^2^3
1+2（
2/0
（2-4）^3.1
2.5%2
2%2.5
【输出例子】
18.39
0.00
256.00
Errorininfixnotation.
Errorininfixnotation.
Errorininfixnotation.
Errorininfixnotation.
Errorininfixnotation.\
18.图结构:
拯救007
【问题描述】看过007系列电影的人们一定很熟悉JamesBond这个世界上最著名的特工了。
在电影“LiveandLetDie”中JamesBond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。
这时JamesBond做出了最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反应过来的时候，他又跳到了另一只鳄鱼的头上„„最后他终于安全地跳到了湖岸上。
假设湖是100×100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。
湖中心的圆形小岛的圆心在（0，0），直径是15。
一些凶猛的鳄鱼分布在湖中不同的位置。
现已知湖中鳄鱼的位置（坐标）和JamesBond可以跳的最大距离，请你告诉JamesBond一条最短的到达湖边的路径。
他逃出去的路径的长度等于他跳的次数。
【输入要求】
程序从“input.txt”文件中读取输入信息，这个文件包含了多组输入数据。
每组输入数据的起始行中包含两个整数n和d，n是鳄鱼的数量而且n≤100，d是007可以跳的最大距离而且d>0。
起始行下面的每一行是鳄鱼的坐标（x，y），其中x,y都是整数，而且没有任何两只鳄鱼出现在同一个位置。
input.txt文件以一个负数结尾。
【输出要求】
程序输出结果输出到output.txt文件中。
对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：
第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标（x，y），每行一个坐标。
如果007不可能跳出去，则将-1写入文件。
如果这里有很多个最短的路径，只需输出其中的任意一种
【输入例子】
410
170
270
370
450
110
2030
-1
【输出例子】
5
170
270
370
450
-1
提示：
将每个鳄鱼看作图中的一个顶点。
如果007可以从A点跳到B点，则A和B之间就有一条边。
19.最小生成树:
室内布线
【问题描述】装修新房子是一项颇为复杂的工程，现在需要写个程序帮助房主设计室内电线的布局。
首先，墙壁上插座的位置是固定的。
插座间需要有电线相连，而且要布置的整齐美观，即要求每条线都与至少一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。
房主要求知道，要将所有插座连通，自己需要买的电线的最短长度。
另外，别忘了每个房间都有门，电线不可以穿门而过。
上图给出了一个有4插座的房间的电线布局。
【输入要求】
输入由若干组测试数据组成。
每组数据的第1行包含房间的长、宽、高和插座的个数N（N为一个不超过20的正整数）。
接下去的N行中，第i行给出第i个插座的位置坐标（xi,yi,zi）；最后一行包含4个3元组（x1,y1,z1）…（x4，y4，z4），分别是长方形门框的4个角三维坐标。
4个数字全部为0表示全部测试结束，不要对该数据任何处理。
注意：
这里假设长方体形状的房间完全位于三维直角坐标系的第一象限内，并且有一个角落在原点上。
地板位于x-y平面。
题目数据保证，每个插座仅属于四面墙中的一面，门上没有插座。
要求每段电线的两端必须仅与插座连接，电线之间不能互相交叉焊接。
【输出要求】
对每一组测试，在一行里输出要将所有插座连通需要买的电线的最短整数长度。
【输入例子】
1010104
013.3
2.502
500.8
5101
0000031.5001.503
0000
【输出例子】
21
20.神秘国度的爱情故事
【问题描述】某个太空神秘国度中有很多美丽的小村，从太空中可以望见，小村间有路相连，更精确点说，任意两村之间有且仅有一条路径。
小村A中有位年轻人爱上了自己村里美丽姑娘。
每天早晨，姑娘都要去小村B里的面包房工作，傍晚6点回家。
年轻人终于决定要向姑娘表白，他打算在小村C等着姑娘路过的时候把爱慕说出来。
问题是，他不能确定小村C是否在小村B到小村A之间的路径上。
你可帮助他解决这个问题吗？
【输入要求】
输入由若干组测试数据组成。
每组数据的第1行包含一正整数N（1≤N≤50000），代表神秘国度中小村的个数，每个小村即从0到N-1编号。
接下来有N-1行输入，每行熬好一条双向道路的两个端点小村的编号，中间用空格分开。
之后一行包含一正整数M（1≤M≤500000），代表着该组测试问题的个数。
接下来M行，每行给出A、B、C三个小村的编号，中间用空格分开。
当N为0时，表示全部测试结束，不要对该数据做任何处理。
【输出要求】
对每一组测试给定的A、B、C，在一行里输出答案，即：
如果C在A和B之间的路径上，输出Yes，否则输出No。
【输入例子】
3
11
22
3
021
120
121
0
升级会员 