数据结构课程设计Word格式文档下载.docx
《数据结构课程设计Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计Word格式文档下载.docx（23页珍藏版）》请在冰点文库上搜索。
（4）1,0001,0001；
-1,0001,0001；
（5）1,0001,0001；
-1,0001,0000；
应输出“1”。
（6）-9999,9999,9999；
-9999,9999,9999；
应输出“1,9999,9999,9998”。
（7）1,0000,9999,9999；
1；
应输出“1,0001,0000,0000”。
*实现提示：
（1）每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。
（2）可以利用头结点数据域的符号代表长整数的符号。
用其绝对值表示元素结点数目。
相加过程中不要破坏两个操作数链表。
不能给长整数位数规定上限。
选做内容
实现长整数的四则运算。
2、栈和队列部分
【马踏棋盘】
将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。
要求每个方格上只进入一次，走遍棋盘上全部64个方格。
编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。
由读者指定,可自行指定一个马的初始位置。
每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”（悔棋）使用。
并探讨每次选择位置的“最佳策略”，以减少回溯的次数。
【魔王语言解释】
[问题描述]
有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
（1）α－>
β1β2…βm
（2）（θδ1δ2…δn）－>
θδnθδn－1…θδ1θ
在这两种形式中，从左到右均表示解释。
试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。
[基本要求]
用下述两条具体规则和上述规则形式
（2）实现。
设大写字母表示魔王语言的词汇；
小写字母表示人的语言词汇；
希腊字母表示可以用大写字母或小写字母代换的变量。
魔王语言可含人的词汇。
（1）B－>
tAdA
（2）A－>
sae
[测试数据]
B（ehnxgz）B解释成tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：
“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
[小写字母与汉字对应关系]
tdsaezgxnh
天地上一只鹅追赶下蛋恨
3、树和图部分
【重言式判别】
[问题描述]
一个逻辑表达式如果对于其变元的任一种取值均为真，则成为重言式；
反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式。
试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。
，
[基本要求]
（1）逻辑表达式从终端输入，长度不超过一行。
逻辑运算符包括“｜”、“＆”和“～”，分别表示或、与和非，运算优先程度递增，但可有括号改变，即括号内的运算优先。
逻辑变元为大写字母。
表达式中任何地方都可以含有多个空格符。
（2）若是重言式或矛盾式，可以只显示“TrueForever”或“FalseForever”，否则显示“Satisfactible”以及变量名序列，与用户交互。
若用户对表达式变元取定一组值，程序就求出并显示逻辑表达式的值。
[测试数据]
（1）（A｜～A）＆（B|~B）
（2）（A&
～A）＆C
（3）A|B|C|D|E｜～A
[实现提示]
（1）识别逻辑表达式的符号形式并建立二叉树可以有两种策略：
自底向上的算符优先法和自顶向下分割，先序遍历建立二叉树的方法。
（2）可设表达式中逻辑变量数不超过20。
真值的产生可以通过在一维数组上维护一个“软计数器”实现，用递归算法实现更简单。
【图的邻接矩阵存储结构建立】
建立图的邻接矩阵存储结构（图的类型可以是有向图或有向网、无向图或无向网，学生可以任选一种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的dfs及bfs次序。
【校园导游咨询】
[问题描述]
（1）设计你的学校的校园平面图，所含景点不少于10个。
以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；
以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
（3）为来访客人提供图中任意景点相关信息的查询。
由读者根据实际情况指定。
【kruskal算法实现最小生成树问题】
五、实验报告模板
《数据结构》
课程设计报告
课程名称：
《数据结构》课程设计
课程设计题目：
飞机订票系统
姓名：
院系：
计算机学院
专业：
年级：
学号：
指导教师：
2011年9月22日
1课程设计的目的………………………………………………………………x
2需求分析………………………………………………………………………x
3课程设计报告内容……………………………………………………………x
1、概要设计……………………………………………………………………x
2、详细设计……………………………………………………………………x
3、调试分析……………………………………………………………………x
4、用户手册……………………………………………………………………x
5、测试结果……………………………………………………………………x
6、程序清单……………………………………………………………………x
4小结…………………………………………………………………………x
5参考文献………………………………………………………………x
1、课程设计的目的
（1）熟练使用C语言编写程序，解决实际问题；
（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2、需求分析
1、任务：
通过此系统可以实现如下功能：
（1）输入航班信息：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）
（2）输出航班信息：
输出航班号、起始站、终点站、订票时间、机票数。
（3）查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
（4）订票：
（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；
（5）退票：
可退票，退票后修改相关数据文件；
（6）修改航班信息：
当航班信息改变可以修改航班数据文件
2、测试数据
输入航班信息：
航班号起始站终点站时间机票数
分别实现航班信息的修改、查询、输出等功能。
3、课程设计报告内容
概要设计
（1）在分析题目要求的基础上，我首先设计了一个结构体，定义如下
structair{
intnum;
charstart[20];
charover[20];
intcount;
}s[N];
存储订票系统的信息。
（2）基本操作：
voidinput（）;
//输入航班信息
voidprint（）;
//输出航班信息
voidsave（）;
//保存航班信息
voidread（）;
//读取航班信息
voidsearch（）;
//查找航班信息
voidshanchu（）;
//删除航班信息
voiddingpiao（）;
//订票信息
voidtuipiao（）;
//退票信息
voidxiugai（）;
//修改信息
2、本程序分为9个模块
Voidmain｛
初始化；
voidsave（）;
voidsearch（）;
voiddingpiao（）;
｝
函数调用关系基本结构图如下所示：
3、调试分析
（略）
4、用户手册
5、测试结果
4、小结
一、这次课程设计的心得体会通过实践我的收获如下：
1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。
3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。
4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。
二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业实验课，多在实践中锻炼自己。
2、写程序的过程中要考虑周到，严密。
3、在做设计的时候要有信心，有耐心，切勿浮躁。
4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
5、程序清单：
（见附录）
6、参考文献
[1]严蔚敏，吴伟民编著.数据结构（C语言版）——北京：
清华大学出版社，2007.
[2]严蔚敏，吴伟民米宁编著.数据结构题集（C语言版）——北京：
[3]网上搜索相关程序作为参考
7、程序运行结果：
附件：
#include<
stdio.h>
//标准输入、输出头文件
string.h>
//包含字符串函数处理头文件
stdlib.h>
//包含动态存储与释放函数头文件
#defineN10000
structair//定义结构体数组
{
inti;
intm=0;
//修改信息
voidmain（）
intj;
printf（"
欢迎进入飞机票管理系统！
\n"
）;
do
{
1.输入航班信息\n\n"
"
2.浏览航班信息\n\n"
3.修改航班信息\n\n"
4.查找航班信息\n\n"
5.删除航班信息\n\n"
6.订票信息\n\n"
7.退票信息\n\n"
0.退出\n\n"
请在0-7中选择以回车键结束：
\n\n"
scanf（"
%d"
&
j）;
switch（j）
case1:
input（）;
//调用输入函数
break;
case2:
print（）;
//调用打印函数
case3:
xiugai（）;
//调用修改函数
case4:
search（）;
//调用查找函数
case5:
shanchu（）;
//调用删除函数
case6:
dingpiao（）;
//调用订票函数
case7:
tuipiao（）;
//调用退票函数
case0:
;
}
}while（j!
=0）;
//判断结束
谢谢使用，再见！
\n"
}//主函数结束
voidinput（）//打印模块程序
{
inty;
intj=0;
请依次输入航班信息:
//打印提示信息
for（i=0;
i<
N;
i++）
请输入航班号:
s[i].num）;
//读取航班号
请输入起始站:
%s"
s[i].start）;
//读取起始站
请输入终点站:
s[i].over）;
//读取终点站
请输入时间:
请输入机票数:
m）;
s[i].count）;
//读取机票数
j++;
第%d个信息已经输完是否继续?
按1继续，按0结束"
j）;
y）;
if（y==0）
save（）;
//将结构体信息存盘
voidsave（）//保存模块程序
FILE*fp,*fp1;
//定义文件指针
if（（fp=fopen（"
chen.dat"
"
wb"
））==NULL）//打开文件并判断是否出错
创建文件失败!
//打印出错提示
getchar（）;
return;
if（（fp1=fopen（"
hao.dat"
m;
if（fwrite（&
s[i],sizeof（structair）,1,fp）==0）//向文件写入数据，并判断是否出错
向文件输入数据失败!
fprintf（fp1,"
fclose（fp）;
//关闭文件
fclose（fp1）;
}
voidread（）//从文件读取信息模块
rb"
））==NULL）//打开文件，并判断是否出错
出错，请检查文件是否存在，按任意键返回住菜单"
fscanf（fp1,"
m）;
i++）
fread（&
s[i],sizeof（air）,1,fp）;
//从文件中读取信息
voidprint（）//打印模块
charw[10];
read（）;
//调用读取文件函数
航班号起始站终点站时间机票数\n"
printf（PRINT）;
//打印信息
请按1结束返回上层菜单以:
w）;
voidsearch（）//查询模块
charname1[20];
charname2[20];
charii[10];
intn,no;
do
请选择查找方式：
//打印查询方式菜单
1.按航班号查找\n\n"
2.按终点站查找\n\n"
3.按航线查找\n\n"
0.返回\n\n"
请在0-3中选择：
按其他键以回车键结束返回主菜单:
n）;
//读取查找方式
if（n==0）
switch（n）
请输入航班号：
no）;
//航班号
请输入终点站名称：
name2）;
请输入起始站名称：
name1）;
//终点站
//调用读取函数
{
if（strcmp（s[i].over,name1）==0||strcmp（s[i].over,name2）==0）//按终点站起始站判断输出条件
\n查找航班信息成功!
if（s[i].num==no）//按航班号判断输出条件
}
no=0;
//将航班号赋值为0
没有您需要的信息或查找完毕：
是否继续查找?
请键入yes或no以回车键结束\n"
ii）;
}while（strcmp（ii,"
yes"
）==0）;
//判断结束
voidshanchu（）//删除模块
intno,n;
do
请选择删除以方式回车键结束：
//打印删除方式菜单
*1.按航班号删除\n\n"
*2.按航线删除\n\n"
*0.返回\n\n"
请在0-2中选择以回车键结束：
//读取删除方式
//跳出循环
//读取航班号
//跳出循环
请输入起始站名称：
if（s[i].num==no||strcmp（s[i].start,name1）==0&
&
strcmp（s[i].over,name2）==0）//判断输入信息是否存在
s[i]=s[m-1];
m--;
查找完毕或没有这个信息\n\n"
是否继续删除\n"
//读取是否继续信息
//调用读取函数
if（!
strcmp（ii,"
））//判断是否继续删除
请按任意键以回车键结束返回上层菜单:
}while（n!
=1&
n!
=2&
=3&
=4&
voiddingpiao（）//订票模块
intn;
chara[10];
search（）;
//调用查询模块
请输入您要订的机票数以回车键结束：
//读取所订机票数
if（n<
0）
请输入有效的机票数！
//判断机票数是否出错
if（s[i].
升级会员 