数据结构课程设计Word格式文档下载.docx
《数据结构课程设计Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计Word格式文档下载.docx（33页珍藏版）》请在冰点文库上搜索。
4、严禁抄袭，否则成绩作废。
5、设计达到一定工作量。
四、设计内容、步骤及要求
1、集合的并、交和差运算
【问题描述】
编制一个能演示执行集合的并、交和差运算的程序。
【基本要求】
（1）集合的元素限定为小写字母字符[‘a’..’z’]。
（2）演示程序以用户和计算机的对话方式执行。
【测试数据】
（1）Set1="
magazine"
，Set2="
paper"
，
Set1∪Set2="
aegimnprz"
，Setl∩Set2="
ae"
，Set1-Set2="
gimnz"
。
（2）Set1="
012oper4a6tion89"
errordata"
adeinoprt"
aeort"
inp"
【实现提示】
以有序链表表示集合。
【选作内容】
（1）集合的元素判定和子集判定运算。
（2）求集合的补集。
（3）集合的混合运算表达式求值。
（4）集合的元素类型推广到其他类型，甚至任意类型。
2、一元稀疏多项式计算器
设计一个一元稀疏多项式简单计算器。
一元稀疏多项式简单计算器的基本功能是：
（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：
n，cl，el，c2，e2，…，cn，en，其中n是多项式的项数，ci和ei，分别是第i项的系数和指数，序列按指数降序排列；
（3）多项式a和b相加，建立多项式a+b；
（4）多项式a和b相减，建立多项式a-b。
（1）（2x+5x8－3.1x11）+（7－5x8+11x9）=（－3.lx11+11x9+2x+7）
（2）（6x-3－x+4.4x2－1.2x9）－（-6x-3+5.4x2－x2+7.8x15）
=（-7.8x15-1.2x9+12x-3-x）
（3）（1+x+x2+x3+x4+x5）+（-x3－x4）=（1+x+x2+x5）
（4）（x+x3）+（-x－x3）=0
（5）（x+x100）+（x100+x200）=（x+2x100+x200）
（6）（x+x2+x3）+0=x+x2+x3
（7）互换上述测试数据中的前后两个多项式
用带表头结点的单链表存储多项式。
（1）计算多项式在x处的值。
（2）求多项式a的导函数
3、算术表达式计算
表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。
设计一个程序，演示用算符优先法对算术表达式求值的过程。
（难度系数：
0.7）
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。
利用运算符优先关系，实现对算术四则混合运算表达式的求值。
8；
1+2+3+4；
88-1*5；
1024/4*8；
1024/（4*8）；
（20+2）*（6/2）；
3-3-3；
8/（9-9）；
2*（6+2*（3+6*（6+6）））；
（（（6+6）*6+3）*2+6）*2；
设置运算符栈和运算数栈辅助分析算符优先关系；
在读入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算；
在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作等内容。
【选做内容】
（1）扩充运算符集，如增加乘方、单目减、赋值等运算。
（2）运算量可以是变量。
（3）运算量可以是实数类型。
4、哈夫曼编/译码器设计
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼的编/译码系统。
0.82）
一个完整的系统应该具有以下功能：
（1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中；
（2）E：
编码（Encoding）。
利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中；
（3）D：
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码。
结果存入文件TectFile中。
自行建立。
编码结果以文本方式存储在文件CodeFile中；
用户界面可以设计为“菜单”方式。
（1）上述文件CodeFile中的每个“0”或“1”实际上占用了一个字节的空间，只起到示意或模拟的作用。
为最大限度地利用码点存储能力，试改写程序，将编码结果以二进制形式存放在文件CodeFile中。
（2）实现各个转换操作的源/目文件，均由用户在选择此操作时指定。
5、校园导游系统模拟
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
0.87）
（1）设计学校的校园平面图，所含景点不少于6个。
以图中顶点表示校内各景点，存放景点名称、代号、间介等信息；
以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。
无
（1）提供途中任意景点问路查询，即求任意两个景点间的所有路径。
（2）提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。
6、哈希表设计
针对某个集体（比如你所在的班级）中的"
人名"
设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
假设人名为中国人姓名的汉语拼音形式。
待填入哈希表的人名共有30个，取平均查找长度的上限为2。
哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。
取读者周围较熟悉的30个人的姓名。
如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。
人名的长度均不超过19个字符（最长的人名如z庄双双（ZhangStmarlgShang〉。
字符的取码方法可直接利用C语言中的toascii函数，并可对过长的人名先作折叠处理。
（1）从教科书上介绍的几种晗希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率（可以用更大的名字集合作试验〉。
（2）研究这30个人名的特点，努力找一个晗希函数，使得对于不同的拼音名一定不发生地址冲突。
（3）在哈希函数确定的前提下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的晗希表中关键字的聚簇性。
7、图书管理
图书管理基本业务活动包括:
对一本书的采编入库、清除库存、借阅和归还等等。
试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。
（1）每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。
（2）作为演示系统，不必使用文件，全部数据可以都在内存存放。
但是由于上述四项基本业务活动都是通过书号（即关键字〉进行的，所以要用B树〈24树〉对书号建立索引，以获得高效率。
（3）系统应实现的操作及其功能定义如下:
1采编入库z新购入一种书，经分类和确定书号之后登记到图书账目中去。
如果这种书在账中已有，则只将总库存量增加。
②清除库存:
某种书已无保留价值，将它从图书账目中注销。
③借阅:
如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。
④归还z注销对借阅者的登记，改变该书的现存量。
⑤显示:
以凹入表的形式显示B树。
这个操作是为了调试和维护的目的而设置的。
入库书号:
35，16，18，70，5，50，22，60，13，17，12，45，25，毡，15，90，30，7然后清除:
45，90，50，22，42
其余数据自行设计。
由空树开始，每插入删除一个关键字后就显示B树的状态。
（1）24树的查找算法是基础，入库和清除操作都要调用。
难点在于删除关键字的算法，因而只要算法对2-3树适用就可以了，暂时不必追求高阶B树也适用的删除算法。
（2）每种书的记录可以用动（或静）态链式结构。
借阅登记信息可以链接在相应的那种书的记录之后。
（l）将一次会话过程（即程序一次运行）中的全部人机对话记入一个日志文件"
log"
中去。
（2）增加列出某著者全部著作名的操作。
思考如何提高这一操作的效率，参阅教科书12.6.2节。
（3〉增加列出某种书状态的操作。
状态信息除了包括这种书记录的全部信息外还包括最早到期（包括已逾期）的借阅者证号，日期可用整数实现，以求简化。
（4）增加预约借书功能。
五、时间安排
类型
序号
学时
实验名称
选题要求
设计型实验
1
6
设计一集合的并、交和差运算
选其一
2
设计二一元稀疏多项式计算器
3
设计三算术表达式计算
4
12
设计四哈夫曼编/译码器设计
5
设计五校园导游系统模拟
设计六哈希表设计
7
设计七图书管理
六、评分标准
数据结构课程设计一共3个设计内容，设计一、设计二和设计三选其一，30分，设计四和设计五选其一，40分，设计六和设计七选其一，30分，满分100分。
具体评分标准如下：
1、设计报告20%
1）关键代码分析：
10%
用算法思想或者伪代码来描述，需要计算时间复杂度。
2）主程序流程图：
5%
3）总结5%
2、源程序80%
1）程序运行流畅，没有明显的错误10%
2）代码规范，有注释，缩紧，换行等10%
3）关键算法使用的存储结构，执行过程，内存分配，算法思想和流程清楚30%
4）回答与程序相关的问题准确无误10%
5）程序功能有新意和创造性10%
6）其他10%
验收过程中，教师当场根据程序运行的过程进行提问，以此来判断该程序是否为独立完成。
七、参考资料
[1]严蔚敏，《数据结构C语言》，清华大学出版社；
[2]谭浩强，《c语言程序设计》，清华大学出版社；
[3]李春葆，《数据结构教材（第3版）》，清华大学出版社；
[4]李春保，《数据结构习题》，清华大学出版社；
[5]严蔚敏，《数据结构习题》，清华大学出版社；
[6]王立柱，《c语言与数据结构》，清华大学出版社；
[7]李春葆，《数据结构（C语言篇）习题与解析》，清华大学出版社；
八．设计范例
停车场管理系统
1．问题描述
设停车场是一个可停放n辆汽车的狭长通道，且只有一个门可供出入。
汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆汽车即可开入；
当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原顺序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
2．需求分析
（1）根据车辆到达停车场到车辆离开停车场时所停留的时间进行计时收费。
（2）当有车辆从停车场离开时，等待的车辆按顺序进入停车场停放。
实现停车场的调度功能。
（3）用顺序栈来表示停车场，链队表示停车场外的便道。
（4）显示停车场信息和便道信息。
（5）程序执行的命令为：
车辆进入停车场
车辆离开停车场
显示停车场的信息。
用户根据系统所规定并提示的要求输入有关内容，车场所能容纳的车辆数由收费人员来确定，车辆离开时，车主还可以得到收据，便于收费的管理使用；
并且系统程序所提供的一些信息可通过特殊硬件显示出来，供车主了解信息，准确有效的停车。
程序应该能够显示当前存车信息以及等待车的信息，便于管理人员对车辆进行管理，并且能够给等待的车提供一些信息，便于他们能够及时的停车。
程序执行的命令为：
输入进站信息->
输入出站信息->
打印收据
改程序系简单的用于运用栈与队列基本知识的工具，不能用于现实中，特别是栈“先进后出”的规则大大限定了该程序的推广，现实世界的车站管理系统比这个远远复杂的多。
3.概要设计
3.1.设定栈的抽象数据类型定义为：
ADTstack{
数据对象：
D={ai|ai∈charset,i=1,2,……,n,n>
=0}
数据关系：
R1={<
ai-1,ai>
|ai-1,ai∈D,i=2……,n}
基本操作：
InitStack（&
S）
操作结果：
构造一个空栈S。
Push（&
S,e）
初始条件：
栈S已经存在。
在栈S的栈顶插入新的栈顶元素e。
Pop（&
S,&
e）
删除S的栈顶元素，并以e返回其值。
StackTraverse（S,visit（））
从栈底到栈顶依次对S中的每一个元素调用函数visit（）.
}ADTstack
3.2.设定队列的抽象数据类型定义为:
D={ai|ai∈Elemset,i=1,2,……,n,n>
约定其中ai为队列头,an为队列尾.
基本操作:
InitQueue（&
Q）
操作结果:
构造一个空队列Q.
DestroyQueue（&
初始条件:
队列Q已存在.
队列Q被销毁,不再存在.
ClearQueue（&
将Q清为空队列.
QueueEmpty（Q）
若Q为空队列,则返回True,否则返回False.
QueueLength（Q）
队列Q已经存在.
返回Q的元素个数,即队列的长度.
GetHead（Q,&
Q为非空队列.
用e返回Q的对头元素.
EnQueue（&
Q,e）
插入元素e为Q新的队尾元素.
DeQueue（&
Q,&
删除Q的队头元素,并用e返回其值.
QueueTraverse（Q,visit（））
Q已存在且非空.
从队头到队尾,依次对Q的每一个数据元素调用函数visit（）.一旦visit（）失败,则操作失败.
}ADTQueue
3.3.本程序包括四个模块
1）主程序模块
Voidmain（）
{
声明定义
调用栈与队列的函数
主信息（输入初始操作信息）
}
2）栈模块---实现栈抽象数据类型
3）队列模块---实现队列抽象数据类型
4）结构体模块---用于对对象及变量的管理
各模块之间的调用关系如下：
主程序模块
↓
结构体模块
栈模块
队列模块
（4）设计停车管理程序的要求
按照从终端读入的输入数据进行模拟管理，每一组输入数据包括三个数据项：
汽车“进站”或“出站”信息、汽车牌照号码以及进站或出站的时刻，对每一组输入数据进行操作后的输出信息为：
若是车辆到达，则输出汽车在停车场内或便道上的停车位置；
若是车辆离去，则输出汽车在停车场内逗留的时间和应交纳的费用（在便道上停留不收费），按以顺序结构实现，队列以链表结构实现。
4．详细设计：
4.1.时间结点类型
typedefstructtime{
inthour;
intmin;
}Time;
/*时间结点*/
4.2.车辆进出站信息类型
typedefstructnode{
charnum[10];
Timereach;
Timeleave;
}CarNode;
/*车辆信息结点*/
4.3.停车场和便道信息类型
typedefstructNODE{
CarNode*stack[Max+1];
inttop;
}SeqStackCar;
/*模拟车站*/
typedefstructcar{
CarNode*data;
structcar*next;
}QueueNode;
typedefstructNode{
QueueNode*head;
QueueNode*rear;
}LinkQueueCar;
/*模拟通道*/
voidInitStack（SeqStackCar*,intn）;
/*声明栈*/
//初始化，创建两个新栈S,S1
intInitQueue（LinkQueueCar*）;
/*声明便道*/
//初始化，创建一个队列Q用于便道
intArrival（SeqStackCar*,LinkQueueCar*,intn）;
/*车辆进站*/
voidLeave（SeqStackCar*,SeqStackCar*,LinkQueueCar*,intn）;
/*车辆出站*/
voidList（SeqStackCar,LinkQueueCar）;
/*显示存车信息*/
voidInitStack（SeqStackCar*s,intn）/*初始化栈*/
4.4.主函数和其它函数的伪码算法
voidmain（）
{//主程序
initialization（）;
//初始化
while
（1）{
scanf（...................）;
//根据提示信息输入想要的操作
switch（k）{//根据输入的数调用不同的函数
case1:
case2:
....................
typedefstruct**{
//用于创建不同结构体类型的指针与变量
voidPRINT（CarNode*p）{
//调用输出函数
Leave（*p,n）...................
根据求解时间值来求得费用,并通过收据打印出来
5.主要函数思想
本程序是个简单的栈与队列的应用程序,其所用的函数也是栈与队列的基本函数,但在编写函数时应特别注意它的面向对象性与窗口化设计,切身为使用者着想.所以在运用一些函数时调用的基本语句有太多的重复,其目的在于实现它本来的基本目的.
6．调试分析：
本次课程设计是栈与队列的复习应用，调试比较顺利，只是在调用栈与队列的函数时遇到一些问题，比如想通过键盘输入来确定停车场的停车数，所以初始化时那些操作函数必须带有停车数这个参数。
在定义栈的元素最大空间时如果使用顺序栈必须先给它赋初值，但如果通过链表就可以实现动态分配内存，为栈动态开辟新空间。
在判断键盘输入是否符合要求时，如果不符合要求应循环赋值，直到符合要求为止，在此利用的do-while循环语句与外部while语句套用时应使用两次break语句，才能跳出循环，否则会造成死循环。
7．软件使用说明书
本次设计的程序，能实现车场存车及便道存车信息的输入，输出，查找等功能，并建立和更新的存车费用信息保存于文件输出或打印。
对于查找等功能能够按存车位置及车牌号分别进行。
每辆车的相关信息包括：
车牌号，进站时间，出站时间，存车位置，停车费用等。
下面介绍该程序的使用说明：
7.1.停车场.exe；
7.2.进入演示系统后首先是一个用户及管理员使用注意事项界面，进入后会出现菜单选项。
1.车辆进站2.车辆出站3.存车信息4.离开系统
请选择：
1|2|3|4.
这时可按照提示进行你想要的操作。
7.3.对于1－4的具体操作与内容请详见前面的调试分析，您便可以轻松操作了！
8.课程设计总结
栈和队列是常用的一种数据结构，在程序设计中经常用到。
本次实验利用栈和数组，完成了停车场的停车过程的模拟。
实现了车辆进站、车辆出站、存车信息等功能。
经过测试，程序能够正确执行各命令，准确无误，达到了课程设计的目标。
经过这次课程设计，通过对程序的编制，调试和运行，使我更好的掌握了栈和队列基本性质和有关它们之间关系使用问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。
这次数据结构的程序设计，对于我来说是一个挑战。
我对数据结构的学习在程序的设计中也有所体现。
课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。
参考文献
[1]黄同成，黄俊民，董建寅．数据结构[M]．北京：
中国电力出版社，2008
[2]董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：
[3]严蔚敏，吴伟民.数据结构（C语言版）[M].
升级会员 