数据结构课程设计指导书.docx
《数据结构课程设计指导书.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计指导书.docx（35页珍藏版）》请在冰点文库上搜索。
数据结构课程设计指导书
《数据结构》课程设计指导书
一、课程设计目的
《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。
课程设计是加强学生实践能力的一个强有力手段。
本课程设计的目的就是要达到理论与实际应用相结合，使学生深化理解书本知识，获取上机实践经验，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养软件工作者所需的动手能力、独立解决问题的能力。
该课程设计侧重软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，以至一整套软件工作规范的训练和科学作风的培养。
通过该课程设计的操作与实践，使学生真正掌握数据结构相关算法的实现及应用方法，在一定程度上提高使用数据结构相关算法的综合设计能力，具体掌握的基本能力如下：
1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
二、课程设计要求
学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课程设计的要求。
通过设计一个完整的程序，使学生掌握数据结构的应用，算法的编写。
要求如下：
1.做好上机准备：
要充分认识课程设计对自己的重要性，认真做好设计前的各项准备工作。
每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。
2.既要虚心接受老师的指导，又要充分发挥主观能动性。
结合课题，独立思考，努力钻研，勤于实践，勇于创新。
充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。
3.独立思考，独立完成：
课程设计中各项任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。
在设计过程中，要严格要求自己，树立严肃，严密，严谨的科学态度，必须按时，按质，按量完成课程设计。
不得弄虚作假，不准抄袭他人内容。
4.设计的题目要求达到一定工作量（1000行以上代码），并具有一定的深度和难度。
编写出课程设计说明书，说明书不少于2000字（代码不算）。
5.课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。
课程设计期间，无故缺席按旷课处理。
6.按照任意性（用户任意给定输入，系统能够完成正确的计算），友好性（界面要友好，输入有提示，尽量展示人性化），可读性（源程序代码清晰、有层次），健壮性（用户输入非法数据时，系统要及时给出警告信息），结构性（应用程序具有良好的程序结构）要求分析设计实现。
7.整个系统只能有一个执行程序，各项内容分别以不同文件存放，功能尽量模块化。
三、考核方式与成绩评定
1.由指导教师根据学生完成任务的情况、课程设计报告的质量和课程设计过程中的工作态度等综合打分。
成绩评定实行优秀、良好、中等、及格和不及格五个等级。
2.设计程序的检查由教师当面在计算机上检查测试，并同时对程序中的问题至少提出三个问题，学生当面回答，作为最终成绩评定的一部分；
3.独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。
发现课程设计基本雷同，一律不及格；缺席时间达四分之一以上者，其成绩按不及格处理；上机时间内做与课设无关的事情，达五次以上者，其成绩按不及格处理。
4.完成2项以下者，最好成绩为及格；完成2项至3项者，最好成绩为中；完成4项至6项者，最好成绩为良；完成7项以上，成绩为优秀。
5.成绩评定标准：
平时表现：
50%，上机演示：
30%，设计报告：
20%。
四、课程设计最终需提交的内容：
1.学生应提交的资料包括：
⏹纸质的课程设计报告1份；
⏹程序及代码（电子文档）。
该部分包括源代码和可执行文件两个部分。
以电子方式提交的文件全部存在一个目录中，并对其进行压缩（用Winrar或Winzip均可），压缩后的文件按规定格式进行命名，命名格式为：
班级+序号+姓名。
rar（如地信051_12_张文。
rar）。
⏹将源程序、课程设计报告的电子文档按规定的文件名称和格式放在所建的文件夹（各班序号）下，并拷贝到指导教师指定的文件夹中。
2.课程设计报告应包括封面、目录、正文和参考文献等部分，一律用A4纸张打印，正文用5号宋体（报告封面、内容及要求都在服务器的数据结构目录下）。
3.报告提交时间：
第21周星期三下午4点之前由学习委员收集上交，迟交无成绩。
五、注意事项
1.迟到3次或缺席一次，成绩下降一个档次，迟到6次或缺席2次，成绩再下降一个档次，依次类推。
2.上机时发现玩游戏及聊天2次，成绩下降一个档次，玩游戏4次，成绩再下降一个档次，依次类推。
3.源程序和课程设计报告，缺一不可。
4.平时上机带齐《C++语言程序设计》、《数据结构》、笔、纸。
六、参考实例（任选）
1.内部排序算法的性能分析
[问题描述]设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。
[基本要求]
1）.对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；
2）.待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：
关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；数据类型可变。
3）.输出比较结果。
[实现提示]采用模版及顺序存储结构
2.线性链表基本操作的实现
[问题描述]线性链表的插入、删除、遍历等操作的实现。
[基本要求]要求生成线性表时，可以键盘上读取元素
3.表达式求解问题
[问题描述]设计一个程序，求解算术表达式。
[基本要求]以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。
4.二叉排序树的操作（创建，插入，查询，删除）
5.二叉树的遍历、线索及应用（用递归或非递归的方法都可以）
[问题描述]建立二叉树，并输出二叉树的先序，中序和后序遍历序列，以及二叉树的叶子数。
[基本要求]要求根据读取的元素建立二叉树，能输出各种遍历。
[实现提示]可通过输入带空格的前序序列建立二叉链表。
6.哈夫曼编码/译码器
[问题描述]设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将一个压缩文件译码还原为一个文本文件。
[基本要求]输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；
1）.将文本文件利用哈夫曼树进行编码，生成压缩文件；
2）.输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码；
3）.显示指定的压缩文件和文本文件；
[实现提示]采用顺序存储结构建立赫夫曼树，编码采用从叶子结点到根结点的求取方法。
7.图的建立及输出
任务：
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
要求：
给出图的深度优先和广度优先遍历算法，并给出遍历过程的动态演示效果
8.最小生成树问题。
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
9.拓扑排序
[问题描述]建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，再编写函数实现图的拓扑排序。
[基本要求]选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。
10.校园导游咨询系统
[问题描述]设计一个校园导游程序，为来访的客人提供信息查询服务。
[基本要求]
1）.设计学校的校园平面图，所含景点不少于10个，以图中顶点表示校内各景点，存放景点名称、代号、简介等信息，以边表示路径，存放路径长度等相关信息。
2）.为来访客人提供图中任意景点相关信息的查询；
3）.为来访客人提供从校门口到图中任意景点的问路查询；
4）.提供求任意两个景点之间的所有路径的功能；
5）.提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳（短）路径。
11.订票系统
任务：
通过此系统可以实现如下功能：
录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；
订票：
可以订票（订票情况可以存在一个数据文件中，结构自己设定），如果该航班已经无票，可以提供相关可选择航班；
退票：
可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：
当航班信息改变可以修改航班数据文件
要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
12.运动会分数统计
任务：
参加运动会有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.选择数据结构
不同的存储结构对算法的时间、空间、性能方面可能有不同的影响，选择数据结构时，除了要能将所需的数据元素极其关系存储起来外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。
4.编程
将问题的描述算法和数据结构，用计算机语言来表示并将其转换为完整的上机程序。
5.总结
对设计进行总结和讨论，包括本设计的优、缺点，时、空间性能，与其他可能存在的求解方法之间的比较等。
八、内容与时间安排
17周
星期一
星期二
星期三
星期四
星期五
星期六
星期日
上午
内部排序
表达式
二叉树
下午
单链表
查找
晚上
答疑
18周
星期一
星期二
星期三
星期四
星期五
星期六
星期日
上午
最小生成树
校园导航、考核
下午
哈夫曼
最小生成树
校园导航、考核
晚上
答疑
九、常用软件工程设计步骤
1.需求分析：
根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么（而不是怎么做）限制条件是什么。
2.逻辑设计：
对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。
逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；
3.详细设计：
定义相应的存储结构并写出各函数的伪码算法。
在这个过程中，要综合考虑系统功能，使得系统结构清晰，合理，简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。
详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；
4.程序编码：
把详细设计的结果进一步求精为程序设计语言程序。
同时加入一些注解和断言，使程序中逻辑概念清楚；
5.程序调试与测试：
采用自底向上，分模块进行，即先调试低层函数。
能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。
调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；
6.结果分析：
程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。
算法的时间，空间复杂性分析。
日志
ch1su
加博友 关注她
最新日志
∙资深HR多年识人经验——人可
∙朋友；当你失去目标的时候请
∙一个大学男生写的 写的真好
∙异步FIFO为什么要使用格雷码
∙Voice Activity Detection a
∙Stop Wasting Time Online
该作者的其他文章
博主推荐
相关日志
随机阅读
首页推荐
∙七岁儿童射杀雄鹿
∙打了6925个孔的女子竟然出嫁了
∙柔身美女怎样钻进玻璃小盒
∙实拍黄小琥歌友会现场（图）
∙中国古典文学的四个李宇春
∙与鱼儿海里自由翱游
更多>>
对“推广广告”提建议
数据结构——表达式求解
喜欢的句子
数据结构课程设计——算术表达式求解
数据结构2009-06-1516:
56:
35阅读986评论2 字号：
大中小 订阅
题目：
算术表达式求值演示
一、 需求分析
1、 为了实现算符优先算法使用两个工作栈，一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。
2、 在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。
3、 开始将‘#’入操作符栈，通过一个函数来判别算术运算符的优先级。
且规定‘#’的优先级最低。
在输入表达式的最后输入‘#’，代表表达式输入结束。
在表达式输入过程中，遇操作数则直接入栈。
遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高（前面的运算还不应执行）则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符（注意当前运算符未变）与新栈顶运算符。
如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。
4、 最初实现的加、减、乘、除及带小括号的基本运算，但考虑到实用性，后来的设计中有加上了乘方运算。
在乘方运算中借用了C库中自带的乘方函数pow。
二、 概要设计
1、 设定栈的抽象数据类型定义：
ADTStack{
数据对象：
D＝{ai|ai∈ElemSet,i=1,2,...,n, n≥0}
数据关系：
R1＝{|ai-1,ai∈D,i=2,...,n}
约定an端为栈顶，a1端为栈底。
基本操作：
InitStack（&S）
操作结果：
构造一个空栈S。
DestroyStack（&S）
初始条件：
栈S已存在。
操作结果：
栈S被销毁。
StackEmpty（S）
初始条件：
栈S已存在。
操作结果：
若栈S为空栈，则返回TRUE，否则FALE。
StackLength（S）
初始条件：
栈S已存在。
操作结果：
返回S的元素个数，即栈的长度。
GetTop（S,&e）
初始条件：
栈S已存在且非空。
操作结果：
用e返回S的栈顶元素。
ClearStack（&S）
初始条件：
栈S已存在。
操作结果：
将S清为空栈。
Push（&S,e）
初始条件：
栈S已存在。
操作结果：
插入元素e为新的栈顶元素。
Pop（&S）
初始条件：
栈S已存在且非空。
操作结果：
删除S的栈顶元素，并用e返回其值。
}ADTStack
2、表达式的抽象数据类型
ADTarithmetic
{
数据对象：
D1={‘+’、‘-’、‘*’、‘/’、‘#’,‘^’}
D2={a1 a2 a3 a4……}
基本操作：
intIn（intc）
//判断输入字符c是否为运算符,返回1，则c为操作符，返回0则c不是操作符
charprecede（inttop,charc）
//判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回‘>’，前一个运算符小于当前运算符的优先级则返‘<’，当前一个运算符为‘（’当前运算符为‘）’时返回‘=’，用于去除表达式的括号。
elemtypeoperate（elemtypea,chartheta,elemtypeb）
//计算运算过程中的两个数的值，a，b为两个操作数，theta为操作符，成功，返回两个数的运算结果
elemtypeevaluate（structSqstackopnd,structSqstackoptr）
//求表达式的值的整个操作过程，通过调用相应的函数实现遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高（前面的运算还不应执行）则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符（注意当前运算符未变）与新栈顶运算符。
如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。
}
3、本程序包含的模块：
（1）、主程序模块
voidmain（）
{
structSqstackopnd;//操作数栈
structSqstackoptr;//操作符栈
elemtyperesult;
result=evaluate（opnd,optr）;
printf（"theresultis%d\n",result）;
}
（2）运算模块——实现数据表达式的运算
（3）栈模块——实现栈抽象数据类型
模块调用关系：
5、 计算表达式的伪码
初始化操作符栈
将‘#’入操作符栈
初始化操作数栈
输入字符c
while（c!
='#'||gettop（optr）!
='#'）
{
如果c是操作数
{
如果flag=1；
将操作数栈的栈顶元素出栈，和c共同转化为相应的int类型的数后入操作数栈
若flag=0
则将c-48入操作数栈
flag=1；
输入c
}
否则{
将c和操作符栈的栈顶元素比较
若c的优先级高于栈顶元素
C入操作符栈
输入下一个字符c
若为c与栈顶元素是一对括号，
则将栈顶元素出栈
输入下一字符c
若c的优先级低于栈顶元素
则计算操作数栈的栈顶的两个元素的运算，后将运算结果入栈
}
}//while
三、详细设计
1、输入字符为char类型
栈结构
structSqstack
{
elemtype*top;//栈顶指针
elemtype*base;//栈底指针
intstacksize; //栈的大小
};
2、栈的基本操作
（1）初始化栈
statusinitstack（structSqstack&s）
{
s.base=（elemtype*）malloc（stack_size*sizeof（elemtype））;
if（!
s.base）
returnOVERFLOW;
s.top=s.base;
s.stacksize=stack_size;
returnOK;
}
（2）入栈
statuspush（structSqstack&s,elemtypee）
{
if（s.top-s.base>=s.stacksize）
{
s.base=（elemtype*）realloc（s.base,（s.stacksize+stack_increasement）*
sizeof（elemtype））;
if（!
（s.base））
returnOVERFLOW;
s.top=s.base+s.stacksize;
s.stacksize+=stack_increasement;
}
*s.top++=e;
returnOK;
}
（3）出栈
elemtypepop（structSqstack&s）
{
elemtypee;
if（s.top==s.base）
returnERROR;
e=*--s.top;
returne;
}
（4）取栈顶元素
elemtypegettop（structSqstack&s）
{
elemtypee;
if（s.top==s.base）
returnERROR;
e=*（s.top-1）;
returne;
}
3、判断c是否是操作数
代码具体设计：
intIn（intc）
//
升级会员 