旅游管理系统实践与B树算法应用

课程设计

-----数据构造课程设计汇报

学号：—

姓名：

指导教师

专业:计算机

完毕日期：

目录

A篇：旅游信息管理系统

一S题目规定

1、题目内容-----------------------------------1

二、程序设计目的

1、题目分析------------------------------------1

2、功能简介------------------------------------2

3、数据构造------------------------------------2

三、概要简述

1、功能构造图-----------------------------------3

2、模块分析-------------------------------------3

四、详细设计

1、构造体定义----------------------------------3

2、程序流程图---------------------------------5

五、源程序代码

1、源程序C-+实现代码--------------------------6

六、调试分析及测试成果

1、运行成果截-----------------------------------14

七、附录

1、补充阐明------------------------------------19

八、程序小结

1、汇报总结----------------------------------19

B篇:B-树手工题

一、题目规定

1、题目内容-----------------------------------20

二、运行过程

1、从空树插入---------------------------------20

2、插入完毕-----------------------------------25

3、依次删除规定点-----------------------------26

4、最终止果-----------------------------------28

篇：附加题

一、题目

1、题目内容----------------------------------29

二、程序设计目的

1、功能简介----------------------------------29

2、数据构造----------------------------------29

三、设计思绪

1、构造体定义----------------------------------29

2、功能构造图--------------------------------30

3、程序流程图--------------------------------30

四、实现代码

1、程序代码----------------------------------32

五、程序调试以及运行成果

1、调试成果及截图---------------------------43

六、汇报总结

1、汇报总结---------------------------------44

A篇：旅游信息管理系统

一\题目规定

1、题目内容

旅游信息管理系统

1)数据构造

(1)、二叉排序树加单链表

(2)、二叉排序树

阐明：1、用二叉排序树表达旅游地点，用单链表表达游客。

2、用二叉排序树表达旅游地点和游客。

2)、功能

(1)、旅游地点的插入

(2)、游客报名

(3)、当某地H勺旅游人数少于三个人时，取消次旅游地，提议

游客该选其他旅游点

(4)、当某旅游地旅游人数等于六个时，不容许在报名。提

议游客改选其他旅游地。

二、程序设计目的

1、题目分析

读题可知，需完毕两方面的编程以对旅游系统进行操作。首先

是旅游企业管理人员，重要是旅游景点的添加与删除，对旅游人员的

录入与删除，对旅游人数的记录，把游客所需信息打印等等；第二方

面是游客对于旅游地的选、改、删，以及个人信息的输入、确认等等。

2、功能简介

由以上分析可得：本设计程序功能重要有：

①、旅游企业管理人员对旅游人员和旅游地点的操作，用二

叉排序树管理旅游地点。重要有地点的变更，插入、删除、游客的信

息存储及及时提醒等功能。其中一叉树每一种结点包括旅游地点口勺区

号（area_node）＞名称（area）、该旅游地日勺游客人数（count）^以

及一种指向游客信息构造的指针（list）,尚有二叉树结点的左孩子

和右孩子指针（Ichild,rchild）o

②、游客可以登陆旅游企加界面进行报名、选择旅游地点和输

入个人信息。游客构造采用单链表，其中包括单链表的初始化、插入、

删除、计数功能。其中每一种单链表结点包括游客的编号（id）、姓

名（name）、性别（sex）、和链接链表日勺指针（next）。

3、数据构造

用到的数据构造有：单链表，排序二叉树，数组。

三、概要简述

1＞功能构造图

2、模块分析

本程序包括三个模块：主程序模块、二叉排序树模块、单链表

模块，工作区选择模块。如图：

工＜一»二叉排序树模块

主程序模块1一A作

去＜一＞|单链表模块一

四、详细设计

1、构造体定义

1)、链表结点构造体

typedcfstructtourist(

stringname;

intid;

stringsex;

structtourist*next;

}Trist,*linklist;

左孩子区号地名游客数右孩子指向链表的指针

2）、二叉排序树结点阂造体

typedefstructTreePlace{

intarea_code;〃旅游地区号

stringarea;〃旅游地名称

intcount;〃记录该旅游地报名游客人数

structTree_Place*lchild,*rchild;

Trist〃指向游客所在单链表的指针

}Place,*TPlace;

左孩子区号地名游客数右孩子指向链表的指针

2、程序流程图

主菜单(i-fiUsUi2、游客）

输入密码错误

对欧(12345)

III

五、源程序代码

1、源程序C++实现代码

#include<iostream>

#include<stdlib.h>

#include<string>

itincludo<iomanip>

usingnamespacestd;

^defineMAX50

#defineSIZE12

typedefstructtourist{

charname[SIZE];

intid;

charsex[5];

structtourist*next;

}Trist,*1inklist;

typedefstructTreePkice{

intcode;〃旅游地区号

chararea[SIZE];〃旅游地名称

intcount:〃记录该旅游地报名游客

人数

structTree_Place*lchild,*rchild;

Trist*list;〃指向游客所在单链表

的指针

}Place,*TPlace;

voidSearch_T(TPlace&tree,intco);

voidMainlist(TPlacefetree);

voidTour1(TPlace&tree):

voidTour_2(TPlace&tree);

voidDestory(TPlace&tree);

voidInit_L(linklist也head)

{

head二NULL;

}

voidlnsert_L(TPlace&tree,TPlace&t,linklist&head)

{

linklisttr;

charc;

inti=l,co,id;

while(t->count<6&&i==l)

{

cout<<”请输入你口勺身份证号：

cin»id;

tr=(linklist)malloc(sizeof(Trist));

tr->id=id;

cout«〃输入姓名,性别："<<endl;

cin>>tr->name»tr->sex;

tr->next=head;

head=tr;

t->count++;

cout<<〃继续报名请按1,按0退出！"<<endl;

cin>>i;

)

if(t->count>=6)

(

cout。〃此旅游地人数已满，按'y'选择其他旅游地,其他键退出！

，，<<endl;cin»c;

if(c='y'||c='Y'){cout«，/请重新输入区号

，，<<endl;cin»co;Search_T(tree,co);}

}

elseTour_2(tree);

}

voidDeletL(linklistShead)

{

linklistp,pro;

pro二head;

while(pro)

p=pro;pro=p->next;free(p);

)

)

voidlnsert_T(TPlace&tree,TPlacep){〃在二叉排序树中插入一种

新结点

if(tree二二NULL)tree二p;

elseif(p->code<tree->code)lnsert_T(tree->lchild,p);

elseif(p->code>tree->code)Insert,T(tree->rchild,p);

}

voidSearchT(TPlace&tree,intco)

{

charc;

TPlacep;

intcode;

p=tree;

while(p&&p->code!=co)

if(p->code>co)

p=p->lchild;

elsep=p->rchild;

)

if(!p){cout<<“此旅游地点尚未存在！"<<endl;system("pause");Tour_2(tree：;}

else(

if(p->count>=6)

{

cout*〃此旅游地人数已满，按'y'选择其他旅游地，其他键退出！

"<<endl;cin»c;

if(c='y'||c二二'Y'){cout<<〃请重新输入区号

，z<<endl;cin»code;SearchT(tree,code);}elseTour_2(tree);

)

else{cout<<“可以报名"<<endl;Insert_L(tree,p,p->list);Tour_2(tree):}

)

}

TPlaceDclcteT(TPlace&t,intco)

(

TPlacep,parent,s,q;〃parent指向要删除H勺节点的J双亲，p指向要删除的节点

P=t；

parcnt=NULL;

while(p)

if(p->code-co)

break;

parent=p;

if(p->code>co)

p=p->lchild;

else

p=p->rchild;

)

if(p二二NULL)〃不存在该树节点

returnt;

if(p-"child二二NULL)〃无左子树，右子树可有可无

(

if(parent二二NULL)

t=p->rchild;

else

if(parent->lchild~p)

parent->lchild=p->rchiId;

else

parent->rchild=p->rchild;

DeletL(p->list)：free(p);

else〃有左子树，右子树可有可无

q二p;

s=q->lchild;////

while(s->rchild)

{

q二s;

s=s->rchild;

)

if(q==p)〃其左孩子没有右子树

q->lchild=s->lchild;

else

q->rchi1d=s->IchiId;

p->code=s->code;Delet_L(s->list);

free(s);

)

returnt;

)

voidFunl(TPlace&tree)

charc;

intn;

TPlacep;

cout«"请输入插入地点个数："<<endl;

cin>>n;

cout<<〃依次输入各个旅游地点的|区号和地名：”《endl;

for(inti=O;i<n;i++)

{

p=(TPlace)malloc[sizeof(Place));

cout<〈"请输入第〈〃个地点：〃<<endl;

cin»p->code»p->area;

p->lchiId=p->rchiId=NULL;

p->list=NULL;

p->count=0;

Insert_T(tree,p);

)

cout<<〃输入完毕，输入y或者Y继续操作，其他键退出！〃；

cin>>c;

if(c==，y||c==，Y*)Funl(tree);

else{system(^cls^);Tour_l(tree);}

}

voidFun2(TPlace&.tree,intx)

(

inttop二U;

TPlacep,s[MAX];

p=tree;

whi1c(p||top>0)

(

while(p)

(

s[top++]=p;

p=p->lchild;

)

if(top>0)

{p=s[—top];cout«setw(8)«/z区号:，z«p->code<<setw(10)«*地

名:，，<<p->area<<setw(10)<<"人数："<<p->count«endl;

p=p->rchild;}

)

if(tree二二NULL)cout<<"尚未录入旅游地！请稍后查询！〃<<endl;

cout<<"按任意键返回上一级菜单！"<<endl;

system(''paused);if(x==l)Tour_l(tree);if(x-2)Tour_2(tree);

)

voidFun3(TPlace&tree,intx)

(

intnl=0,n2=0;charc;

inttop=0;intelem[MAX];

TPlacep,s[MAX];

p=trcc;

while(p||top>0)

(

while(p)

(

s[top++]=p;

p=p->lchiId;

)

if(top>0)

{p=s[—top];

if(p->count<3&&x==l){

cout<<setw(8)«z，区号："<<p->code<〈setw(10)<X"地

名：“«p->area〈〈setw(10)<<〃人数：〃<<p->count〈〈endl;elem[nl]=p->code;nl++:}

if(p->count<6&&x==2){

cout<<setw(8)«z，区号：“<<p->code<〈setw(10)«“地

名：“<9->2「62<〈56,(10)«"人数："<9->以)11。1；<<611(11；；。2++；}

p=p->rchild;}

}

if(x=l){cout«"一共有"<<nl<<"各旅游景点人数少于三个，z«endl;cout<<〃删除旅

游地请输入D或者d,其他键返回菜单！〃<<endl;cin>>c;

if(c==，d*I|c=，D*){for(inti=0:i<nl:i++)Delete_T(tree,elemfi]):cout«，，ffl

除完毕！“<<endl;}system("pause");Tour」(tree);}

[1>(乂=2)k。成。〃一共有〃<<。2<<〃个旅游景点仍可报名〃<。£1;。。a《"按任意键返

回上一级菜单！"<<endl;system("pause");Tour2(tree);}

)

voidFun4(TPlace&tree)

intco,id;

TPlacep;

linklist1,pre;

p二tree;

cout«〃输入要退出旅游地的区号和自己的身份证号：〃。endl;

cin>>co>>id;

while(p&&p->code!=co)

{

ii(p->code>co)

p=p->lchild;

elsep=p->rchild;

)

if(!p){cout<<“此旅游地点尚未存在!/z«endl:system(z，pause^):Tour_2(tree);}

else

{l=p->list;pre=l;

while(l->id!=id)

{

pre=l;

l=l->next;

}

pre->next=l->next;fre=(l);p->count-;cout<<“输入要报名H勺地点区号："<<endl;

cin>>co;

SearchT(tree,co);

}

)

voidMainlist(TPlace&trce)

(

system(，，cls，/);

cout<</，

******************************************************”<<cndI(〈end1;

cout«z，欢迎登陆旅游购票系统"<<ondl;

cout<<”请选择登录身份："<<endl;

cout<<"1、旅游企业管理人员“(<cndl;

cout<<〃2、游客〃<<endl;

cout<<^3、退出程序"<<endl;

cout<</，

******************************************************〃<<°nd1〈〈end1;

intn,key,i=l;

cin>>n;

switch(n)

case3:Destory(tree);exit(0);

case1:do{cout<〈”请输入登陆密码：“；cin〉》key;i++;}while(key!=12345&&i<=3);

if(key==12345)Tourl(tree);elseMainlist(tree);break;

case2:Tour2(tree);break;

default:cout<<"输入错误，请重新选择！"<<endl;system("pause");

Mainlist(tree);

)

)

voidTourl(TPlace&tree)

(

system("cls");

intn;

cout<<”

cout<</，1、输入旅游地点*«endl;

cout<<"2、查询各旅游地游客人数〃<<endl;

coul<<”3、显示局限性三人的旅游地"Oendl;

cout<<z，4、退出〃<<endl;

cout<<”

******************************************************”<<end1(〈end1;

cin>>n;

switch(n){

case1:Funl(tree);break;

case2:Fun2(tree,1);break;

case3:Fun3(tree,1);break;

case4:Mainlist(tree);break;

default:cout<<〃输入错误，请重新输入！“<<endl;system("pause〃);Tour_l(tree);;

)

}

voidTour_2(TPlace&tree)

{

intcode;

system("cis");

intn;

cout<<，/

******************************************************“<<0nd1<<endl;

cout<<"1、输入旅游地区号w«cndl;

COUt<</，2、显示所有旅游地〃<<endl;

COUt<<，/3、查询可报名地"〈<endl;

COUt<<，/4、修改旅游地点"〈<endl;

COUt<</，5、退出“<<endl;

COUt<<，/

******************************************************“«endl<Xendl;

cin>>n;

switch(n){

case1:cout<<〃请输入区号:，，<<endl;cin»code;SearchT(tree,code);break;

case2:Fun2(tree,2);break;

case3:Fun3(tree,2);break;

case4:Fund(tree);break;

caseb:Mainl1st(tree);break;

default:cout<<“输入错误,请重新输入入〈〈endl;system("pause");Tour_2(tree);)

)

〃销毁二义树

voidDestorv(TPlace&tree)

(

if(!tree){cout<<”此树已空！”《endl;system「pause");exit(0);)

if(tree&&tree->lchild)

Destory(tree->lchiId);

if(tree&&tree->rchiId)

Destory(tree->rchild);

cout«setw(5)<<tree->code«setw(5)<<tree->area«endl;

DeletL(tree->list);

free(tree);

}

voidmain()

{

TPlaceT二NULL;

Mainlist(T);

}

六、调试分析及测试成果

1、运行成果截图

“，欢迎登陆旅游购票系统

请选择登录身俭屋f

1、翻拾司管理人员

2、游客

1

请输入登陆密码：12345.

萼入

曹楣

1地占

游

2人数

显

询i

足

不

三

地

3游

退

4击

依次榆入各个旅游地点的区号和地名＜输入。。结束〉:

跖入完成，输入y或者Y继续操作，其他键退出！v.

篡曹需地占

游I人数

显不足

三游地

退

个数：

入地点

入插

3输

：

地名

号和

的区

地点

工网

△各

菽施

点：

个地

入孰

谙输

：

地点

勤2个

请,小

点：

个地

昨3

天逢

41

：

地点

第4个

请输入

家庄

12石

：

地点

谦个

狎鲁

!

退出

他键

作，其

续操

者噬

入y或

踱输

落入

蟹人普需地占

游S数

显询不足

三地

退击

区0寸地名北人赞

1

0

f

1地名庄

2

区0

石人及

=

2地名

1

区滨U

于地名上货

3

5

区人数0

地.鬟

f=

4

1

0

区j

&

?

T

1反回上单

费>衣建继练

^

•

.

输

入旅

地

1区O

2所

显

示9S

3

查

询

4点

需

5加

请输入区号：

翻糕的身份证号：

08111824

酚簪性别：

善续报名请按1,按。退出!

请输入你的身份证号：

10231505

械入姓名，性别：

五国平男

据续报名请按1,按。退出!

i青输入你的身份证号：

10091112

班人姓名，性别：

藜明男

继续报名请按工，按。退出!

请输入你的身份证号：

09087564

簿A姓名，性别：

李丽女__________________

黎明男

继续报名请按1,按。退出！

:青输入你的身份证号：

09087564

龄姓名，性别：

露矍鼠请按1,按腿出！

量输入你的身份证号：

斯01234密576，性别：

或理报名请按1,按。退出！

量输入你的身份证号：

07038901

卷△姓名，性别：

季靖女

继续报名请按工，按。退出！

3旅游地人数已满，按，短选择其他旅游地，其他键退出!

输入

地

区O

示

显9S

旅

查

可

危

点

I旅

输入要退出旅游地的区号和自己的身份证号:

2108111824

输入要报名的地点区号：

4盟1糕的身份证号：

0谶8111824性别：

里续报名请按［,按。退出！

输入

游地

1区O

2显S

示

旅

篇

查

3可

询

余

点

4旅

5备

一

地

告

北

人个

区号:

:1数

区

地

号

人:0

区10

地

号

SJi数

告

12石F:0

区

:数

地

人

号35

一

点:0

41僧

1聘

网

睛

答

-嬖

安

键

回tT.

口

键

”

继

意

R荏••.

萼

曹

落

1地占

游

数

2宛I

显

不

足

三

地

3人

4退

3

区号:岬、地名:，北京_人数

删醯辅1翻焉4粼着!返返回菜单!

七、附录

1、补充阐明

#include<stdlib.h>：包括分派空间的头文献

#include<string>：包括对字符串进行操作H勺头文献

#include<iomanip>：包括控制输出格式的头文献

Destcxry函数为释放内存，删除所建树的所有节点。

八、程序小结

1、试验总结

旅游信息管理系统B勺程序重要分为两大方面的构思，从两个方面

对程序进行操作，又通过某些关系使构造很好日勺结合在一起，完毕了

此操作系统日勺某些基本操作c例如有旅游景点日勺建立、删除、遍历和

游客信息日勺插入语更改等，分别对应二叉树日勺插入，删除和遍历，尚

有对链表日勺某些基本操作。

我认为操作系统得以实现日勺关键是在旅游景点的节点上创立了

指向游客链表日勺指针，两种构造便产生了一定联络。

通过这次数据构造课程设计，我对数据构造有了更深一步的理

解，对已学过日勺数据构造日勺掌握程度在应用中通过产生问题，处理问

题日勺过程得以很好的提高。

B篇：B-树手工题

一、题目规定

1、题目内容

从空的三阶B-树开始一次插入20、30、50、52、60、68、70、10、5、

80、90然后分别删除60、90、88、20画出上述操作日勺B-树各状态。

二、运行过程

1、从空树插入

1）、

2）、

（2030:

3）、

（2030501201C.50.；1

4）、

7）、

C_2()3C_50y

68

68

C_5__3C_2()3C_50_J>C；7()8()9(O

3、依次删除规定点

5）、

4、最终止果

C篇：附加题

一、题目

1、题目规定

编程实现B-树

注：其中包括对B-树的结点日勺插入、删除、遍历和清晰B-树。

二、程序设计额目的

1＞功能简介

1）、B-树的初

2）、B-树的建立（结点的插入）

3）、B-树的删除（结点日勺删除）

4）、B-树的遍历（前序、中序、层次）

5）、B-树日勺销毁

2、数据构造

1)、B-树

2）、数组

3）、队列

4）、栈（递归）

三、设计思想

1、构造体定义

1）、B-树节点

structMBNode{

intkeynum;〃关键字个数域

MBNode*pareni;〃指向父结点的指针域

KeyTypekey[m+1];〃保留n个关键字日勺域，下标位置未用

MBNode*ptr[m+1];〃保留n+1个指向子树的指针域

｝；

2）、队列口勺结点

typedefstruct{

MBNodeeleni[M];〃寄存树节点

intfront,rear;〃队头队尾

}SQ;

2、功能构造图

插

入

1）、查找并插入

2）、查找并删除

1）、

2）、

开始

从树根起杳找带删除关

键字K所在的结点

结束

四、实现代码

1)C++源程序实现代码

#include<iostream>

#include<stdlib.h>

#include<math.h>

usingnamespacestd;

typedefintKeyType;

#defineMAXKEY9999

#defineM20

constintm=3;

typcdcfstructNodc{

intkeynum;〃关键字个数域

structNode*parent;〃指向父结点的指针域

KeyTypekcy[m-t-I];〃保留n个关键字的域，下标。位置未用

structNode求ptr|m+l];//保留n+1个指向子树的J指针域

}MNode,*MBNode;

typedefstruct{

MBNodeelem[M];

intfront,rear;

1SQ;

voidInitQ(SQ&Q)〃初始化队

(

Q.front=Q.rear=0;

)

voidEnterQ(SQ&Q,MBNodee)〃