数据结构综合实验题目及要求.docx
《数据结构综合实验题目及要求.docx》由会员分享，可在线阅读，更多相关《数据结构综合实验题目及要求.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构综合实验题目及要求
数据结构综合实验设计题目及要求
一、要求
本次课程设计可以从以下的题目中任选其一，每个题目基本实现的要求是：
1、程序设计书（Word格式）。
包括程序设计目标、问题描述、需求分析、概要设计、详细设计、源程序清单（要求格式整齐400行以上，要有注释说明）、软件说明书（给出软件如何使用，使用时的注意事项）、测试报告（每个函数的功能测试，输入条件，输出结果）和总结。
2、可执行程序源代码。
二、设计题目
题目一仓库管理系统（线性表应用）
[问题描述]
建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物以及建立新的仓库存储系统。
[实现提示]
可以采用双向链表的存储结构，如可定义如下的存储结构：
typedefstructdnode/*定义双向链表结构体*/
{intnumber;/*货物编号*/
charname[max];/*货物名称*/
intcounter;/*货物数量*/
structdnode*prior,*next;/*定义两指针，分别指向其前驱和后继*/
}dlnode;
题目二单位员工通讯录管理系统（线性表应用）
[问题描述]
为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的办公室电话、手机号、及电子邮箱。
其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。
[实现提示]
可以采用单链表的存储结构，如可定义如下的存储结构：
typedefstruct{/*员工通讯信息的结构类型定义*/
charnum[5];/*员工编号*/
charname[10];/*员工姓名*/
charphone[15];/*办公室电话号码*/
charcall[15];/*手机号码*/
}DataType;
/*通讯录单链表的结点类型*/
typedefstructnode
{DataTypedata;/*结点的数据域*/
structnode*next;/*结点的指针域*/
}ListNode,*LinkList;
题目三哈夫曼编码/译码系统（树应用）
[问题描述]
利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。
现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。
[实现提示]
在本例中设置发送者和接受者两个功能，
发送者的功能包括：
①输入待传送的字符信息；
②统计字符信息中出现的字符种类数和各字符出现的次数（频率）；
②根据字符的种类数和各自出现的次数建立哈夫曼树；
③利用以上哈夫曼树求出各字符的哈夫曼编码；
④将字符信息转换成对应的编码信息进行传送。
接受者的功能包括：
①接收发送者传送来的编码信息；
②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。
从以上分析可发现，在本例中的主要算法有三个：
（1）哈夫曼树的建立；
（2）哈夫曼编码的生成；
（3）对编码信息的翻译。
题目四教学计划编制问题（图的应用）
[问题描述]
大学的每个专业都要制定教学计划。
假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。
每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。
每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。
每门课恰好占一个学期。
试在这样的前提下设计一个教学计划编制程序。
[实现提示]
1、输入参数应包括：
学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。
2、应允许用户指定下列两种编排策略之一：
一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
3、若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。
计划的表格格式可以自己设计。
4、可设学期总数不超过12，课程总数不超过100。
如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。
题目五图书管理系统（查找应用）
[问题描述]
图书管理基本业务活动包括：
对一本书的采编入库、清除库存、借阅和归还等等。
试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。
[实现提示]
1、每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。
2、由于图书管理的基本业务活动都是通过书号（即关键字）进行的，所以要用对书号索引，以获得高效率。
3、系统应实现的基本功能有：
●采编入库：
新购入一种书，经分类和确定书号之后登记到图书帐目中去。
如果这两种书在帐中已有，则只将总库存量增加。
●清除库存：
某种书已无保留价值，将它从图书帐目中注销。
●借阅：
如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。
●归还：
注销对借阅者的登记，改变该书的现存量。
●显示：
以凹入表的形式显示B树。
这个操作是为了调试和维护的目的而设置的。
题目六通信录查询系统（查找应用）
【问题描述】
设计散列表实现通讯录查找系统。
（1）设每个记录有下列数据项：
电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码为关键字建立散列表；
（3）采用二次探测再散列法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）通讯录信息文件保存；
（6）要求人机界面友好，使用图形化界面；
【实现提示】
主函数：
根据选单的选项调用各函数，并完成相应的功能。
Menu（）的功能：
显示英文提示选单。
Quit（）的功能：
退出选单。
Create（）的功能：
创建新的通讯录。
Append（）的功能：
在通讯录的末尾写入新的信息，并返回选单。
Find（）：
查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。
Alter（）的功能：
修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。
Delete（）的功能：
删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。
List（）的功能：
显示通讯录中的所有记录。
Save（）的功能：
保存通讯录中的所有记录到指定文件中。
Load（）的功能：
从指定文件中读取通讯录中的记录。
题目七药店的药品销售统计系统（排序应用）
【问题描述】
设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。
【实现提示】
在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。
各药品的信息包括：
药品编号、药名、药品单价、销出数量、销售额。
药品编号共4位，采用字母和数字混合编号，如：
A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。
对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。
在本设计中，对单价的排序采用冒泡排序法，对销售量的排序采用快速排序法，对销售额的排序采用堆排序法。
药品信息的元素类型定义：
typedefstructnode
{charnum[4];/*药品编号*/
charname[10];/*药品名称*/
floatprice;/*药品单价*/
intcount;/*销售数量*/
floatsale;/*本药品销售额*/
}DataType;
存储药品信息的顺序表的定义：
typedefstruct
{DataTyper[MaxSize];
intlength;
}SequenList;
题目八电视大赛观众投票及排名系统（排序应用）
【问题描述】
在很多的电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。
现在要求编写一程序模拟实现上述系统的功能。
【实现提示】
在本例中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。
将选手的编号和姓名依此存入顺序表单元中，观众通过按键进行投票，按’1’为1号选手投票，按’2’为2号选手投票，以此类推，以按’0’作为投票结束标志。
投票结束后进行排序，在此采用希尔排序，然后为每个选手计算名次，得票相同的名次也相同，
（1）存储类型的定义
参赛选手信息存储类型的定义：
typedefstructnode{
charname[8];/*选手姓名*/
intnum;/*选手编号*/
intscore;/*选手得分*/
inttax;/*选手名次*/
}Node;
题目九运动会分数统计（排序应用）
【问题描述】
参加运动会有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）.可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：
输入数据形式和范围：
20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）
输出形式：
有中文提示，各学校分数为整形
界面要求：
有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：
学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：
要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。
进行程序测试，以保证程序的稳定。
测试数据及测试结果请在上交的资料中写明；
题目十航班信息的查询与检索（排序应用）
【问题描述】
该设计要求对飞机航班信息进行排序和查找。
可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。
【实现提示】
对于本设计，可采用基数排序法对一组具有结构特点的飞机航班号进行排序，利用二分查找法对排好序的航班记录按航班号实现快速查找，按其他次关键字的查找可采用最简单的顺序查找方法进行，因此他们用得较少。
每个航班记录包括八项，分别是：
航班号、起点站、终点站、班期、起飞时间、到达时间、飞机型号以及票价等，假设航班信息表（8条记录）
航班号
起点站
终点站
班期
起飞时间
到达时间
机型
票价
CA1544
合肥
北京
1.2.4.5
1055
1240
733
960
MU5341
上海
广州
每日
1420
1615
M90
1280
CZ3869
重庆
深圳
2.4.6
0855
1035
733
1010
MU3682
桂林
南京
2.3.4.6.7
2050
2215
M90
1380
HU1836
上海
北京
每日
0940
1120
738
1250
CZ3528
成都
厦门
1.3.4.5.7
1510
1650
CRJ
1060
MU4594
昆明
西安
1.3.5.6
1015
1140
328
1160
SC7425
青岛
海口
1.3.6
1920
2120
DH4
1630
其中航班号一项的格式为：
K0K1K2K3K4K5
C
Z
3
8
6
9
其中K0和K1的输入值是航空公司的别称，用两个大写字母标示，后4位为航班号，这种航班号关键字可分成两段，即字母和数字。
其余七项输入内容因为不涉及本设计的核心，因此除了票价为数值型外，均定义为字符串即可。
题目十一迷宫与栈问题（线性表应用）
【问题描述】
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。
设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【实现提示】
1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i，j，d）的形式输出。
其中：
（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
如，对于下列数据的迷宫，输出一条通路为：
（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
2）编写递归形式的算法，求得迷宫中所有可能的通路。
3）以方阵形式输出迷宫及其通路。
【测试数据】
迷宫的测试数据如下：
左上角（0，1）为入口，右下角（8，9）为出口。
题目十二算术表达式与二叉树（树的应用）
【问题描述】
一个表达式和一棵二叉树之间，存在着自然的对应关系。
写一个程序，实现基于二叉树表示的算术表达式的操作。
【实现提示】
假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^（乘幂））。
实现以下操作：
1）ReadExpre（E）—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。
2）WriteExpre（E）—用带括弧的中缀表达式输出表达式E。
3）Assign（V,c）—实现对变量V的赋值（V=c），变量的初值为0。
4）Value（E）—对算术表达式E求值。
5）CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）
题目十三银行业务模拟与离散事件模拟（线性表应用）
【问题描述】
假设某银行有4个窗口对外接待客户，从早晨银行开门（开门9：
00am，关门5：
00pm）起不断有客户进入银行。
由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需要在每个窗口前顺次排队，对于刚进入银行的客户（建议：
客户进入时间使用随机函数产生），如果某个窗口的业务员正空闲，则可上前办理业务；反之，若4个窗口均有窗户所占，他便会排在人数最少的队伍后面。
【实现提示】
1）编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。
2）建议有如下设置：
a）客户到达时间随机产生，一天客户的人数设定为100人。
b）银行业务员处理时间随机产生，平均处理时间10分钟。
3）将一天的数据（包括业务员和客户）以文件方式输出。
题目十四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，输入每个人的密码，建立单循环链表。
输出形式：
建立一个输出函数，将正确的输出序列。
题目十五校园导游程序（图的应用）
【问题描述】
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。
要求能够回答有关景点介绍、游览路径等问题。
【实现提示】
（1）查询各景点的相关信息；
（2）查询图中任意两个景点间的最短路径。
（3）查询图中任意两个景点间的所有路径。
（4）增加、删除、更新有关景点和道路的信息。
题目十六所有顶点对最短路径问题（图的应用）
[问题描述]
医院选址：
4个村庄之间的交通图如图1所示，村庄之间的距离为图中各边上的权值。
现在要从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。
图1村庄交通图
[实现提示]
用有向加权图表示的交通图中，有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。
该问题实质上是求解任意两顶点间最短路径问题。
解决思想与方案：
（1）运用弗洛伊德算法求出有向图中各顶点对的最短距离。
（2）根据步骤
（1）结果，求出每个顶点到其他顶点的最短距离的最大值。
（3）最大值最小的顶点作为医院所在村庄。
结构定义：
typedefcharvextype;/*顶点数据类型*/
typedefintedgetype;/*边数据类型*/
typedefstruct
{
vextypevex[MANVEX];
edgetypearc[MANVEX][MANVEX];
intvexnum,arcnum;/*顶点数和边数*/
}Mgraph;/*图的邻接矩阵表示结构定义*/
三、上交作业及成绩评定
1、上交要求
1）以班级为单位上交课程综合实验报告电子版，以学号+姓名+题目名称作为文件名。
2）以个人为单位上交一份综合实验报告打印文稿，排版一定要规范，否则影响成绩。
2、评分标准
根据完成任务的情况、实验报告书的质量和实验完成过程中的工作态度等按照30%、50%、20%加权综合打分。
上机程序检查未通过者、无设计报告者以及严重抄袭他人设计者，成绩为不及格。
升级会员 