数据结构 课程设计报告
设计题目: 航空客运订票系统
院 系 年 级 学 生 学 号
指导教师
2015年11月26日
目 录
一、 课程设计目的 3
二、 需求分析 3
三、 概要设计
1.设计步骤 4 2.系统整体结构图 5 3.功能模块及调用关系说明 5
四、 详细设计和源代码
1. 实现概要设计中定义数据的存储结构 6 2. 查询航线信息功能的算法设计 7 3. 订票功能的算法设计 9 4. 退票功能的算法设计 12 5. 录入功能的算法设计6. 总航线预览功能的程序源代码 15
五、调试分析
1. 各功能的具体实例分析 16 2. 实验过程中出现的问题及解决方法 20
六、课程设计总结20
七、参考资料21
一、 课程设计目的
(1) 熟练使用 C 语言编写程序,解决实际问题;
(2) 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 航空订票系统:
(1)熟练掌握链表存储结构及其建立过程和常用操作; (2)熟练掌握队列的建立过程和常用操作;
(3) 学会自己调试程序的方法并掌握一定的技巧。
二、 需求分析
问题描述:航空客运订票的业务活动包括:查询航线、客票预订和办理退票等。试设计一个航空客运订票系统,以使上述业务可以借助计算机来完成。 设计任务:通过此系统可以实现如下功能:
录入:可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自
定)
查询:可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,
航班票价,票价折扣,确定航班是否满仓);可以输入起飞抵达城市,查询飞机航班情况;根据旅客提出的终点站名输出下列信息:航班号、飞机号、星期几飞行,最近一天航班的日期和余票额;
订票:(订票情况可以存在一个数据文件中,结构自己设定)根据客户提出的要求
(日期、航班号、订票数额)查询该航班票额情况,若尚有余额,则为客户办理订票手续,输出座位号;若已满员或余票额少于订票额,则需要重新询问客户要求。若需要,可预约登记排队等候。如果该航班已经无票,可以提供相关可选择航班;
退票:根据客户提供的情况(日期、航班、退票数额),为客户办理退票手续,然后
查询该航班是否有人预约登记,首先询问排在第一的客户,若所退票额能满足他的要求,则为他办理订票手续,否则依次询问其他排队预约的客户……退票成功后修改相关数据文件。
客户资料有姓名,证件号,订票数量及航班情况,订单要有编号。
修改航班信息:当航班信息改变可以修改航班数据文件
要求:根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功
能。
测试数据:由学生任意指定,但报告上要求写出多批数据测试结果。
实现提示:每条航线应包含的信息有:终点站名、航班号、飞机号、飞行日期(星期
几)、乘员定额、余票额、已订票的客户名单(包括姓名、订票额、座位号)和预约登记的客户名单(包括日期、姓名、所需票额)。这最后两项显然是一个线性表和一个队列。为查找方便、已订票客户的线性表应按客户姓名有序,并且,为插入和删除方便,应以链表作存储结构。由于预约人数无法预料,队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上,由于航线基本不变,可采用顺序存储结构,并按航班有序或按终点站名有序。每条航线是这张表上的一个记录,包含上述八个域,其中乘员名单域为指向乘员名单链表的头指针,预约登记客户名单域为分别指向队头和队尾的指针。
选做内容:当客户订票要求不能满足时,系统可向客户提供到达同一目的地的其它航线情况。
三、概要设计
1.设计步骤
1)分析问题,给出数学模型,设计相应的数据结构。 提示:
(1)己订票的客户名单可以用线性表来实现。为查找方便,线性表应按照客户姓名有序, 并且为了插入和删除的方便,应以链表作为存储结构。
(2)等候替补的客户名单可以用队列来实现。由于预约人数无法预计,所以队列也应以链表作为存储结构。
(3)需将输入的航班情况登录到一张线性表上(用顺序存储结构或链表存储结构) 。为了查询的方便,可以将航班情况按照航班有序或按照终点站名有序建立线性表。每条航线是这张线性表的一个记录,包含上述8个域,其中已订票的客户名单域是指向己订票的客户名单链表的头指针,等候替补的客户名单域是指向队头和队尾的指针。
2)算法设计
在已经选择好数据结构的前提下,为解决问题设计算法。 (1)确定所需模块
对于稍复杂的程序设计,要充分利用模块化程序设计方法,自顶向下,逐步细化,在整体思路确定的情况下,考虑所需模块数,各模块完成功能以及模块之间的数据联系和调用关系。
(2)各子模块功能描述
给出主要模块的算法描述,用流程图或伪代码表示。 (3)模块之间的调用关系 3)源程序清单
为了提高工作效率,充分利用上机调试程序的时间,要求学生在上机之前给出源程序清单。 4)用测试数据去验证算法及程序的正确性 5)算法分析
经过上机调试,源程序运行正确,并且实现算法要求的功能,解决课程设计题目中给出的问题后,分析算法的时间复杂度和空间复杂度。
2.系统整体结构图(功能模块图)
图 1. 系统整体结构图
3.功能模块及调用关系说明
(1)总航线信息预览:通过调用display()预览已经建立的全部航线的相关信息(航班号、飞机号 、终点站 、飞行日期 、 定额 、余票数 、排队等候人数),预览完返回主菜单。
(2)查询单条航线信息:根据乘客提出的终点站名或航班号调用Search()函数来查询并输出此条航线的相关信息(航班号、飞机号 、终点站 、飞行日期 、 定额 、余票数 、已订票乘客名单、排队等候乘客名单)。 并且查询完后询问乘客是否订票,是就调用订票Book()函数来为乘客进行订票,否就返回主菜单。
(3)办理订票业务:客户先输入的终点站名、订票数、姓名信息再来调用订票Book()函数,Book()函数根据客户提供的终点站名查询到该航线信息,若客户订票额末超过余票量,订票成功并登记信息,在订票乘员名单链表中添加乘客的信息; 如果暂时余票数不足是,询问客户是否要排队等侯,如果是,则在排队等候的队列中增加该乘客的订票信息。
(4)办理退票业务:调用tuipiao()查询函数,根据客户提供的航线进行搜索根据客户提供的姓名到订票客户名单域进行查询。退票成功后,重新将航线名单域指向订票单链表的头指针。根据队列中从出的客户信息判断是否满足要求,如果满足,则将该客户的信息插入到乘客信息链表中。
(5)录入航班信息:调用CreatPlane ()函数,根据输入的航班的相关的信息(航班号、飞机号 、终点站 、飞行日期 、 定额 、余票数),将此航班加入到原来的航班组中。
(6)退出系统
四、详细设计和源代码
1. 实现概要设计中定义数据的存储结构
(1)已订票乘客信息(单链表) typedef struct Cust {
char Name[15];
//乘客姓名
//乘客所乘飞机航班号 //乘客终点站 //已订票乘客信息
char number[10]; char end[15];
(2)排队等候的乘客信息
typedef struct waitNode //排队等候客户信息 {
char name[15];
int ticket;
//乘客姓名
//乘客的订票数
struct waitNode *next;
}waitNode,*waitlink; typedef struct {
waitlink front; waitlink rear;
}waitQueue; (3)航班信息 typedef struct Plane {
char number[10]; int planenum; char end[15]; char date[10]; int dinge;
//航班号 //飞机号 //终点站 //飞行日期 //成员定额 //剩余票数 //排队等候的人数 //链接已订票客户 //链接候补客户
//航班信息
int tick; int k;
Customer *first; waitQueue Q;
}PlaneLink;
2. 查询单条航线信息功能的算法设计(Search( )函数功能实现的源代码)
int Search(PlaneLink *p,int N) {
int i=0,Q;
cout
cout
cout
cout>>>>>\n";
cout>Q; if(Q==1) {
char end[10];
cout
cin>>end;
while(i
{
if(strcmp(p[i].end,end)==0) //先查看是否存在到该站点的航班
{
cout
cout
"
cout
break;
}
i++; }
else if(Q==2) {
char num[10];
cout
cin>>num;
while(i
{
if(strcmp(p[i].number,num)==0) //查看是否存在该航班号的航班
{
cout
cout
"
cout
if(i
int j; }
display_s(p, i, N); //调用display_s()函数输出该航班的已订票乘客和排队等候乘客的名单信
break; } i++; }
cout>j; if(j==1) {
char name[10]; int ticket;
cout
Book(p,p[i].end,ticket, name, N);
} }
else { cout
return 0; }
3. 订票功能的算法设计(Book( )函数功能实现源代码)
int Book(PlaneLink *p,char end[],int ticket,char name[],int N) {
int i; for(i=0;i
if(strcmp(p[i].end,end)==0) //先找出是否存在要订票的航班 {
if(p[i].tick>=ticket) //查看 余票数是否 >= 订票客户 订票数
{
p[i].tick-=ticket;
Customer *t=(Customer *)malloc(sizeof(Customer)); t->ticket=ticket; strcpy(t->Name,name);
strcpy(t->number,p[i].number); strcpy(t->end,p[i].end);
t->next=p[i].first; p[i].first=t; // 此使用的是头插法将订票乘客的信息放入
到 链表中 /
cout
cout
"
cout
}
else if(p[i].dinge
break;
队等候了
{ cout
char z;
cout
cout>z;
if(z=='Y'||z=='y') {
Queue(p,end,ticket , name, N,i); } //调用入队列函
数,将乘客信息插入排队等候的人后面
}
int display_s(PlaneLink *p,int i,int N) //输出已定票及排队乘客的名单信息 {
if(p[i].first!=NULL) //p[i].first!=NULL说明已订票链表不为空, 输出 已订票乘客 }
if(i>=N) {cout
}
}
break;
的名单信息
{
cout
息
}
{
coutNameticket
t=t->next; }
if(i
{
cout
cout
while(S!=NULL)
{
coutnameticketnext;
}
cout
}
附:入队函数Queue( )的源代码
int Queue(PlaneLink *p,char end[],int ticket,char name[],int N ,int i) //入队函数,将等候排队的乘客放入原来的队列中
{ 的信息
strcpy(q->name,name); q->ticket=ticket;
} return 0;
system("cls"); system("color 2e");
waitlink q=(waitlink)malloc(sizeof(waitNode)); //将要的入队的结点,存储将要入队乘客
}
if(p[i].Q.front==NULL) { } else { }
cout
p[i].Q.rear->next=q; p[i].Q.rear=q; p[i].k++; p[i].Q.front=p[i].Q.rear=q;
p[i].k++; //p[i].k用来记录排队人数
4. 退票功能的算法设计(tuipiao( )函数实现的源代码)
int tuipiao(PlaneLink *p,int N) { int i;
Customer *R,*S;
char number[10],Name[15]; cout>>>>>\n";
cout>number>>Name; for(i=0;i
if(strcmp(p[i].number,number)==0&&p[i].first!=NULL)
{
if(strcmp(p[i].first->Name,Name)==0) { }
p[i].tick=p[i].tick+p[i].first->ticket; p[i].first=p[i].first->next; cout
{
R=p[i].first; S=p[i].first->next;
息!\n\n";
while(S!=NULL) { if(strcmp(S->Name,Name)==0) { p[i].tick=p[i].tick+S->ticket; R->next=S->next;
cout
}
R=R->next; S=S->next;
}
if(S==NULL) cout
}
if(p[i].Q.front!=NULL) { waitlink Q=p[i].Q.front , q; while(Q!=NULL) { if(p[i].tick>=Q->ticket) { if(Q==p[i].Q.front) { coutnameticket,Q->name,N); if(p[i].Q.front==p[i].Q.rear) { p[i].Q.front=p[i].Q.rear=NULL; Q=Q->next;
}
}
}
}
}
}
{ p[i].Q.front=p[i].Q.front->next; Q=Q->next; }
else { }
coutnameticket,Q->name,N); q->next=Q->next; Q=Q->next;
else { q=Q; Q=Q->next; }
break;
if(strcmp(p[i].number,number)==0&&p[i].first==NULL)
{
cout
break; }
}
if(i>=N) cout
}
5. 录入功能的算法设计(CreatPlane( )函数的源代码)
void CreatPlane(PlaneLink *p,int n,int N) {
int i,j;
for(i=N;i
p[i].Q.front=p[i].Q.rear=NULL; //队列为空时的条件 cout>>>>>\n";
cout>p[i].number; }
cout>p[i].end; for( j=0;j
cout
if(strcmp(p[i].number,p[j].number)==0) //查看该航班号是否已经存在 { }
if(strcmp(p[i].end,p[j].end)==0) // 查看是否存在到改站点的航班 { }
cout
cin>>p[i].planenum>>p[i].date>>p[i].dinge;
p[i].tick=p[i].dinge; p[i].k=0; }
}
cout
6. 总航线预览功能的算法设计(display( )函数的源代码)
int display(PlaneLink *p,int N) //N为当前的航班数 {
cout
=============\n";
cout
候人数\n";
cout
_____\n";
for(int i=0;i
cout
te
}
cout
=============\n"; }
return 0;
五、调试分析
1)各功能的具体实例分析
为了调试分析方便,在程序中已经初始放入了三个航班信息,如下:
1. 系统主菜单界面
2. 总航线预览功能界面
3. 查询单条航线功能
图1. 按终点站名查询
图2. 按航班号查询
图3. 错误查询输出结果
4. 订票功能
1. 当订票的航班存在且航班的余票数≥乘客订票数时
②当订票的航班存在但余票数≤订票数≤航班的定额时
③当航班存在但订票数大于航班定额时乘客将无法排队等候了
4. 当预定的航班不存在时
5. 退票功能
①. 当退票后余票数能够满足排队乘客的需要时
②. 当航班号或姓名输入错误时,系统会输出显示以下的三种界面
图2
图3
图1
6. 录入功能
2)实验过程中出现的问题及解决方法:
1、 一开始错误很多,包括大量的语法错误和逻辑错误。通过反复的编译、调试、学习
和修改,更正了程序中的语法,使程序可以正常编译,运行。
2、 程序健壮性方面屡屡遇到问题,在程序的测试过程中逐步发现并改进,如主菜单选
择如果输入字符型数据就会引起程序的混乱出现自动跳出;解决方法,引入新的部分从键盘获取字符型数据,通过字符型常量与数据间的关系,将字符数据转化成整形数据。
3、 程序优化,程序虽然可以运行使用,但是有很多不合理处, 例如程序的运行过程对
于正确的输入情况考虑的还比较完全,但对于有误信息的输入情况考虑的不是很好,经常输入有误或是不符合的信息时,会出现死循环或者其他一些异常。对于种情况,我都是通过F10调试,在调试过程输入刚出错我输入的信息,然后逐句或是逐过程的进行调试,最终都能找到问题的具体所在处,然后通过分析为什么这处会出现异常,从这不断的调试及分析的过程中得出了这些错误的修改方法。从而不断的完善了整个系统程序。
4、 功能添加上,我是在实现基础功能的基础上再添加一些其他的比较复杂难处理的功
能,但在添加另外的功能时,常常会出现这些功能之间逻辑联系不好的问题。这些主要就是通过调试看 这些函数的连接处的代码的调试情况,比如一些for 循环、while 循环或是if 语句等的限制条件上把握的不好,经常会出现在我的逻辑理论上应该执行的语句没执行,而不该执行的却执行了的情况。在调试的时候我会首先看看这些连接处的中间变量的值的变化境况,通过这找出了比较这些语句的正确的限制的条件。
六、课程设计总结
1、 在一周的时间里,不断地对程序及各模块进行修改、编译、调试、运行,其间遇到很
多问题,但通过自己的努力及询问同学的帮助都一一解决了。
2、 因本人能力有限,在编写的时候只使用了相对较为简单的基础语言 ,代替了相对较
为复杂的语言,降低了运行效率。
3、 程序是写出来的,不是想出来的。开始阶总是在想,总感觉很困难做不了,但是真正
投入其中之后才发觉其实只要用心,只要有克服一切的勇气和信心就可以把程序做好,错误总是越改越少的。
4、 要用愉悦的心情去做,从编程的过程中体会乐趣,兴趣是最好的老师就是这么回事
5、 学会利用辅助程序去发现问题
6、 通过课程设计,自己通过系统分析、系统设计、编程调试,写实验报告等环节,进一
步掌握应用系统设计的方法和步骤,灵活运用并深刻理解典型数据结构在软件开发中的应用 。
7、 数据结构课程设计是检验我们这个学期学习成果的重要手段,通过这学期的学习,我
认为学好数据结构这门课程,不仅要认真阅读课本知识,更重要的是要通过上机实践才能增强和巩固我的知识。经过这一阶段的上机实践学习,使我对数据结构有了更进一步的认识和了解,要想学好它要重在实践,要通过不断的上机操作才能更好地学习它。通过实践,我也发现我的很多不足之处,首先是自己平时上机练习太少,知识的积压给编程带来了一定的麻烦。另外我对数据结构的一些标准库函数还不太了解,如开始进入系统后发现操作的界面很乱,如果能够及时的清屏那样就会变的很明了。查阅了相关的资料和问同学后我知道只要在程序中调用库函数system("cls")就可以了,知道了这个函数的基本用法;还有对数据结构中经常出现的错误也不了解,通过实践,使我独自处理错误的能力也有了很大的提高。
七、参考资料
1. 《数据结构(C 语言版)》 严蔚敏 吴伟民 编著,清华大学出版社
2. 《数据结构(C 语言版)》相配套的课本源代码
3. 《C++程序设计》谭浩强 编著 清华大学出版社
21 / 22
22 / 22