数据结构课程设计论文.docx
《数据结构课程设计论文.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计论文.docx（31页珍藏版）》请在冰点文库上搜索。
数据结构课程设计论文
以振兴民族软件产业为己任，
作真实、正值、优秀的科技人员！
——林锐语
数据结构课程设计论文
--微机024班欧阳锦林、王峰、段静缘
一、设计课题：
我们设计的程序有三个，分别是：
航空订票系统、24点游戏、旅游交通查询系统，为了用户的方便和更能体现C语言的模块化理念，我们把三个程序放到一个系统中去实现了。
二、设计内容
1、需求分析：
在完成课程设计的过程中，我们组合作为主，欧阳锦林主要负责程序设计与调试，王峰和段静缘主要负责资料收集与文档输入。
设计完成后交流了各人收获与体会。
（1）、航空订票系统：
通过此系统可以实现如下功能：
1）录入航线信息
每条航线信息包括航班号、飞机号、目的地、订票数、余票数共5项。
假设现在有3条航线,目的地分别是北京,上海,广州,飞机上可乘坐100人（即初始订票数为0,余票数为100）,将这3条航线信息存入文件“airline.dat”中。
2）订票业务
客户信息包括姓名,航班号,座位号（初始为0）,假设已有3个客户信息存入文件“customer.dat”中。
有新客户订票时,先输入客户的姓名和他提出的航班号,查询该航线的订票情况,若有余票,则为客户办理订票手续,分配给客户一个座位号,然后将新客户的信息添加到文件“customer.dat”中,并修改文件“airline.dat”中该航线的订票数和余票数。
若无余票,则输出客满信息。
进一步可实现如果该航班已经无票，可以提供相关可选择航班信息。
3）退票业务
根据客户提出的航班号,办理退票,从文件“customer.dat”中删除该客户的信息,并修改文件“airline.dat”中相应航线的订票数和余票数。
4）修改航班信息：
当航班信息改变可以修改航班数据文件。
5）输出全部航线信息和全部客户信息。
6）退出系统。
（2）、24点游戏：
基本要求及步骤：
1）随机产生四个1-13的数，分别代表13张牌。
2）提示玩家输入算式。
3）判断玩家输入的表达式是否合法，其中算式中的四个数字只能是程序所给的四个数字，非法则回到1）。
4）如果玩家认为这四张牌算不出24点（如：
1，1，1，1），可只输入？
，程序将判断这四张牌是否能得出24点，如果能，则程序将给出算式，如果不能，说明不能，并回到1）。
5）当用户正确输入算式后，用“堆栈来求表达式的值”的原理求出结果并判断是否为24，得出用户是输是赢的结果。
6）询问用户是否继续，是则回到1），否则结束程序。
（3）、旅游交通查询系统：
实现功能：
火车信息查询、最短路径查询、火车信息编辑、读入修改信息、查看火车信息、查看城市信息。
每个功能中又有一些小功能，如火车信息查询中有：
按车次查询、按出发地与目的地查询（其中又有最快、最省钱、全部选择）中转站查询、查看火车信息，火车信息编辑又包括：
添加火车信息、删除火车信息、查看火车信息、保存火车信息功能。
2、概要设计：
（1）、航空订票系统：
1）、抽象数据类型定义如下（C语言下的）：
typedefstructairline{
charline_num[8];//航班号
charplane_num[8];//飞机号
charend_place[20];//目的的
inttotal;//座位总数
intleft;//剩余座位
structairline*next;//下一个结点
}airline;
typedefstructcustomer{
charname[9];//顾客名
charline_num[8];//航班号
intseat_num;//座位号
structcustomer*next;//下一个结点
}customer;
/******************链表操作模块***********/
airline*init_airline（）;
//初始化链表
customer*init_customer（）;
//初始化链表
statusinsert_airline（airline**p,char*line_num,char*plane_num,char*end_place,inttotal,intleft）;
//airline链表插入操作
//插入航班
statusinsert_customer（customer**p,char*name,char*line_num,intseat）;
//customer链表插入操作
statuscreat_airline（airline**l）;
//创建airline单链表
statuscreat_customer（customer**l）;
//创建customer单链表
/******************链表操作模块********************/
2）、其它模块的实现函数声明如下：
//**********************信息修改****************/
airline*modefy_airline（airline*l,char*line_num）;
//修改airline链表中的数据
statusdelete_airline（airline*h,char*line_num）;
//删除航班
statusdelete_customer（customer*h,char*line_num）;
//删除顾客
statusdelete_cus（customer*h,airline*l,char*name）;
//顾客退票
statusincrease_air（airline*l,char*line_num,char*plane_num,char*end_place,inttotal）;
//增加航线
//**********************信息修改*************/
//*********************文件操作模块**************/
statussave_airline（airlineconst*l）;
//保存airline.dat
statussave_customer（customerconst*l）;
//保存顾客信息customer.dat
//*********************文件操作模块**************/
intchangStrInt（char*ch）;
//把字符串转化为整型
statusbook（airlineconst*l,char*line_num,customer*c,char*name）;
//订票
statusprint_airline（airlineconst*l）;
//打印航线信息
statusprint_customer（customerconst*l）;
//打印顾客信息
statusair_main（）;
//执行函数
（2）、24点游戏：
1）抽象数据类型定义如下（C语言下的）：
intnumber[2][4];
enum
{
eNumber=0,//操作数
eOperator=1//算子
};
typedefstructsqlist{
intbol;//bolis0whennum_chisanumber;bolis1whenthenum_chisaoprater
intnum_ch;
structsqlist*next;
}sqlist;
typedefstructsqstack{
int*base;
int*top;
intstacksize;
}sqstack;
/***************链表操作模块****************/
statusinit_sq（sqlist*l）;//初始化链表
statusinsert_sq（sqlist**p,inte,intbl）;
//链表插入操作
//由于这里要求修改外部指针,因此要用指向指针的指针
//将插入到链表的末尾
/***************链表操作模块**************/
2）、其它模块的实现函数声明如下：
/*******用栈进行表达式计算模块***********/
intcheck（sqlistl）;
//保证输入的数字是给出的四个数字
intchang（char*s,sqlist*l）;
//将用户的输入转化为单链表
intOperate（inta,inttheta,intb）;
//计算athetab
intReturnOpOrd（charop,char*TestOp）;
//被charprecede（charAop,charBop）所调用来求优先级
charprecede（charAop,charBop）;
//返回优先级
statusinitstack（sqstack*s）;
//栈初始化
intgettop（sqstack*s）;
//取栈顶元素
statuspush（sqstack*s,inte）;
//把e压栈
statuspop（sqstack*s,int*e）;
//出栈,用e保存
intEvaluateExpression（char*MyExpression）;
/***************链表操作模块******************/
intrandomm（）;//产生四个随机数
/****************计算机计算模块****************/
intCalcOneExpress（intexpression[][2]）;
intEqual24（intn）;
intCalcArray1（intiNumInput[2][4]）;
//a*b*c*d//7number
intCalcArray2（intiNumInput[2][4]）;
//（a*b）*c*d//9number
intCalcArray3（intiNumInput[2][4]）;
//（a*b*c）*d//9number
intCalcArray4（intiNumInput[2][4]）;
//（a*b*c）*d//9number
intCalcArray5（intiNumInput[2][4]）;
//（a*b）*（c*d）//11number
intCalcArray6（intiNumInput[2][4]）;
//（（a*b）*c）*d//11number
intCalcArray7（intiNumInput[2][4]）;
//（a*b*c）*d//9number
intCalc24（intnumber[2][4]）;
//括号的几种情况
//1无括号
//2（ab）cd同ab（cd）,下省略
//3（abc）d
//4a（bc）d
//5（ab）（cd）
//6（（ab）c）d
//7（a（bc））d
/****************计算机计算模块*****************/
voidgame_24_main（）;
//24点游戏执行函数
（3）、旅游交通查询系统：
1）所需抽象数据类型定义如下（C语言下的）：
typedefstruct{
intday;//天数
inthour;//小时数
intminute;//分钟数
}time_train;
typedefstructtown{
charname[9];//城镇名称
time_trainarrive;//火车到达时间
time_trainleave;//火车离站时间
structtown*next_town;//下一个城镇
}town;
typedefstructtrain{
chartrain_num[8];//火车序列号
charstart_place[9];//始发地
charend_place[9];//终点站
intfare;//费用
inthour;//时间（用小时计算）
structtrain*next_train;//指向下一辆列车
structtown*next_town;//指向下一个城镇
}train;
typedefstruct{
intlength;//长度
//inthour;//时间
//intfare;//费用
intivex,jvex;//边的两端顶点号
}path,*path_p;//路径类型
typedefstructpath_node{//边结点
pathpa;//路径类型
structpath_node*i_link,*j_link;
//i_link,j_link分别指向边结点的两顶点的地址
}path_node,*path_node_p;
typedefstruct{
charcity_name[9];//城市名
path_node_pfirsh_path;//指向第一条依附该顶点的边
}city_node,*city_p;//图结点
typedefstruct{
city_nodeadj_list[MAXSIZE];//邻接多重
intcity_num,path_num;//图的顶点数和边数
}graph_country;//图储存结构
//邻接多重表储存图
//路径类型
typedefstruct{//
intvx,vy;
}Edge;
typedefstruct{
Edgepath[100];//路径中边的序列
intlen;//路径中边的数目
}path_city;
typedefstruct{
charcitys[MAXSIZE][9];//路径中城市的序列
intnum;//城市数目
}p_city;//
/**************火车的链表操作模块**************/
train*init_train（）;
//初始化链表
town*init_town（）;
//初始化链表
statusinsert_train（train*l,char*train_num,char*start_place,char*end_place,intfare,inthour）;
//火车链表的插入操作
statusinsert_town（train*l,char*name,time_trainarrive,time_trainleave）;
//城市的插入操作
statusfind_town（train*l,char*town）;
////查找中转站
statusfind_train_num（train*l,char*train_num）;
//用火车序列号来查询
statusfind_place（train*l,char*start_place,char*end_place,charchoice）;
//用始发始发站和终点站来查询
//statuscreat_train（train*l）;
//内置数据来创建火车链表
statuscreat_train_f（train*l）;
//用文件来创建火车链表
statuscreat_train_save（train*l）;
//用修改后的储存文件train_save.dat来创建火车链表
statusprint_train（trainconst*l）;
//打印火车信息,包括中转站
statussave_train（trainl）;
//储存修改后的到train_save.dat文件中
statusdelete_train（train*l,char*train_num）;
//删除列车
/******************火车的链表存储操作模块*******/
/*******火车的图（多重邻接表）操作模块***********/
statusinsert_path（graph_country*l,pathpa）;
//在图l中插入边pa
statusinsert_city（graph_country*l,char*city_name,inti）;
//在图l的i位置插入一城市city_name
statusinit_graph（graph_country*l）;
//初始化图l
statuscreat_graph（graph_country*l）;
//创建图l,从文件中读取信息
voidget_city（graph_countryl,inti,char*city_name）;
//以city_name返回邻接多重表中序号为i顶点的城市名
path_node*first_path（graph_countryl,intvi）;
//返回图中依附于顶点的第一条这的指针:
l.adj_list[vi].firsh_path
path_node*next_path（graph_countryg,intvi,path_nodep,int*vj,path_node*q）;
//以vj返回图g中依附于顶点vi的一条边（由指针p所指）的另一端点;
//以q返回图中依附于顶点vi且相对于指针p所指边的下一条边
statusprint_graph（graph_countryg）;
//打印城市图的信息
/********火车的图（多重邻接表）操作模块*********/
2）、其它模块的实现函数声明如下：
/**********迪杰斯特拉算法实现模块**********/
voidinit_p（path_city*pa）;
//初始化为一条空路径
voidinit_set（p_city*p）;
//初始化生成最短路径结点的集合
voidcopy_path（path_city*pa1,path_city*pa2）;
//复制路径
voidinsert_p（path_city*pa,intv,intw）;
//在pa中插入一条边（v,w）
intpath_length（path_city*pa）;
//返回路径长度
voidout_path（graph_countryl,path_citypa,p_city*citys,intnd）;
//将路径转换为城市名称的序列
voidputin_set（char*city_name,p_city*p,intst）;
//把city_name（序号为st的结点）放入
voidshortest_path（graph_countryg,intst,intnd,int*pathlength,p_city*path_info）;
//利用迪杰斯特拉算法的基本思想求图g中从顶点st到顶点nd的一条最短路径
//最短路径path_info及其路径长度path_lenth
intminnal（int*dist,p_cityss）;
//求dist[]中的最小边
/********迪杰斯特拉算法实现模块************/
voidtrain_main（）;
//全国旅游交通查询的执行函数
intcity_name_int（graph_countryl,char*name）;
//在城市与计算机储存序号之间建立一一映射
3、详细设计：
所需抽象数据类型定义和一些函数的声明见设计概要。
这里只解释一下执行函数和一些比较复杂一点的算法。
（1）、航空订票系统：
1）、执行函数：
见voidair_main（）;
2）、定票函数：
statusbook（airlineconst*l,char*line_num,customer*c,char*name）//订票
{
//订票
airline*p=l;
customer*q=c->next;
p=l->next;
for（;q->next!
=NULL;q=q->next）{}
//PR（"%s\n",q->name）;
for（;p!
=NULL;p=p->next）
{
if（strcmp（line_num,p->line_num）==0）
{
if（p->left>0）
{
PR（"恭喜您!
订票成功!
\n"）;
PR（"你的座位号是:
%d\n",（p->total-p->left+1））;
insert_customer（&q,name,line_num,p->total-p->left+1）;
p->left--;
returnOK;
}
elsePR（"对不起,座位已满!
\n"）;
return0;
}
}
PR（"对不起,没有这个航班号!
\n"）;
returnERROR;
}
定票的同时也同时了修改航线信息，并在修改后把修改后的信息储存到文件中去。
3）、退票函数：
statusdelete_cus（customer*h,airline*l,char*name）
{
//顾客退票
customer*p,*pr;
charline_num[8];
//qr=h;
pr=h;
p=pr->next;
//PR（"开始删除\n"）;
while（p!
=NULL）
{
if（strcmp（name,p->name）==0）
{
strcpy（line_num,p->line_num）;
l=modefy_airline（l,line_num）;
pr->next=p->next;
free（p）;
PR（"顾客%s退票成功!
\n",p->name）;
returnOK;
}
pr=pr->next;
p=pr->next;
}
PR（"无此顾客，无法退票！
\n"）;
returnERROR;
}
在此函数执行后执行顾客信息修改和航线信息修改。
从而实现了退票功能。
（2）、24点游戏：
这个系统中主要有两个功能：
人算24点和计算机算24点，前者是在单链表和用栈来表达式求值的模块中实现的，后者是在机算模块（也有用栈求值）中实现
升级会员 