课程设计--------数据结构课程设计报告学号：1016020203姓名：张灿指导教师：曹春萍专业：计算机完成日期：2012.06.25目录A篇：旅游信息管理系统一、题目要求1、题目内容----------------------------------1二、程序设计目标1、题目分析----------------------------------12、功能简介----------------------------------23、数据结构----------------------------------2三、概要简述1、功能结构图---------------------------------32、模块分析-----------------------------------3四、详细设计1、结构体定义----------------------------32、程序流程图---------------------------5五、源程序代码1、源程序c++实现代码-------------------------6六、调试分析及测试结果1、运行结果截------------------------------14七、附录1、补充说明--------------------------------19八、程序小结1、报告总结———————————————19B篇：B-树手工题一、题目要求1、题目内容-----------------------------------20二、运行过程1、从空树插入---------------------------------202、插入完成-----------------------------------253、依次删除要求点-----------------------------264、最终结果-----------------------------------28C篇：附加题一、题目1、题目内容—————————————————29二、程序设计目标1、功能简介—————————————————292、数据结构—————————————————29三、设计思路1、结构体定义————————————————292、功能结构图———————————————303、程序流程图———————————————30四、实现代码1、程序代码————————————————32五、程序调试以及运行结果1、调试结果及截图—————————————43六、报告总结1、报告总结————————————————44A篇：旅游信息管理系统一、题目要求1、题目内容旅游信息管理系统1）数据结构（1）、二叉排序树加单链表（2）、二叉排序树说明：1、用二叉排序树表示旅游地点，用单链表表示游客。

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

2）、功能（1）、旅游地点的插入（2）、游客报名（3）、当某地的旅游人数少于三个人时，取消次旅游地，建议游客该选其他旅游点（4）、当某旅游地旅游人数等于六个时，不允许在报名。

建议游客改选其它旅游地。

二、程序设计目标1、题目分析读题可知，需完成两方面的编程以对旅游系统进行操作。

一方面是旅游公司管理人员，主要是旅游景点的添加与删除，对旅游人员的录入与删除，对旅游人数的统计，把游客所需信息打印等等；第二方面是游客对于旅游地的选、改、删，以及个人信息的输入、确认等等。

2、功能简介由以上分析可得：本设计程序功能主要有：①、旅游公司管理人员对旅游人员和旅游地点的操作，用二叉排序树管理旅游地点。

主要有地点的变更，插入、删除、游客的信息存储及及时提醒等功能。

其中二叉树每一个结点包括旅游地点的区号（area_node）、名称（area）、该旅游地的游客人数（count）、以及一个指向游客信息结构的指针（list），还有二叉树结点的左孩子和右孩子指针（lchild，rchild）。

②、游客可以登陆旅游公司界面进行报名、选择旅游地点和输入个人信息。

游客结构采用单链表，其中包括单链表的初始化、插入、删除、计数功能。

其中每一个单链表结点包括游客的编号（id)、姓名（name)、性别（sex）、和链接链表的指针（next）。

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

三、概要简述1、功能结构图主 菜 单程序员 游客2、模块分析本程序包括三个模块：主程序模块、二叉排序树模块、单链表模块，工作区选择模块。

如图：二叉排序树模块 主程序模块 单链表模块四、详细设计 1、结构体定义工作去选择模块插入 删除 插入遍历遍历二叉树 单链表1）、链表结点结构体typedef struct tourist{string name;int id;string sex;struct tourist *next;}Trist,*linklist;左孩子区号地名游客数右孩子指向链表的指针2）、二叉排序树结点结构体typedef struct Tree_Place{int area_code; //旅游地区号string area; //旅游地名称int count; //记录该旅游地报名游客人数struct Tree_Place *lchild,*rchild;Trist *list; //指向游客所在单链表的指针}Place,*TPlace;左孩子区号地名游客数右孩子指向链表的指针2、程序流程图主 菜 单（1、程序员，2、游客）1输入密码 错误正确 （12345） 2程序管理员 游 客输入成功退/输 Y NN Y输入地点查询各地游客数输入旅游地区号 退出显示少于3人地修改旅游地点查询可报名地 显示所有旅游地重复 提醒 打印 退出删除提醒可报地 打印个人信息超额 输入信息 可报退出 报名成功退出删除五、源程序代码1、源程序c++实现代码#include<iostream>#include<stdlib.h>#include<string>#include<iomanip>using namespace std;#define MAX 50#define SIZE 12typedef struct tourist{char name[SIZE];int id;char sex[5];struct tourist *next;}Trist,*linklist;typedef struct Tree_Place{int code; //旅游地区号char area[SIZE]; //旅游地名称int count; //记录该旅游地报名游客人数struct Tree_Place *lchild,*rchild;Trist *list; //指向游客所在单链表的指针}Place,*TPlace;void Search_T(TPlace &tree,int co);void Mainlist(TPlace &tree);void Tour_1(TPlace &tree);void Tour_2(TPlace &tree);void Destory(TPlace &tree);void Init_L(linklist &head){head=NULL;}void Insert_L (TPlace &tree,TPlace &t,linklist &head){linklist tr;char c;int i=1,co,id;while(t->count<6&&i==1){cout<<"请输入你的身份证号："<<endl;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);}}else Tour_2(tree);}void Delet_L (linklist &head){linklist p,pro;pro=head;while(pro){p=pro ;pro=p->next ;free(p);}}void Insert_T(TPlace &tree,TPlace p){ //在二叉排序树中插入一个新结点if (tree==NULL) tree=p;else if(p->code<tree->code) Insert_T(tree->lchild,p);else if(p->code>tree->code) Insert_T(tree->rchild,p);}void Search_T(TPlace &tree,int co){char c;TPlace p;int code;p=tree;while(p&&p->code!=co ){if(p->code>co)p=p->lchild ;else p=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<<"请重新输入区号"<<endl;cin>>code;Search_T(tree,code);}else Tour_2(tree);}else {cout<<"可以报名"<<endl;Insert_L(tree,p, p->list);Tour_2(tree);} }}TPlace Delete_T(TPlace &t,int co){TPlace p,parent,s,q;//parent指向要删除的节点的双亲，p指向要删除的节点p=t;parent=NULL;while(p){if(p->code==co)break;parent=p;if(p->code>co)p=p->lchild;elsep=p->rchild;}if(p==NULL) //不存在该树节点return t;if(p->lchild==NULL) //无左子树，右子树可有可无if(parent==NULL)t=p->rchild;elseif(parent->lchild==p)parent->lchild=p->rchild;elseparent->rchild=p->rchild;Delet_L (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;elseq->rchild=s->lchild;p->code=s->code; Delet_L (s->list);free(s);}return t;}void Fun1(TPlace &tree){char c;int n;TPlace p;cout<<"请输入插入地点个数："<<endl;cin>>n;cout<<"依次输入各个旅游地点的区号和地名："<<endl;for(int i=0;i<n;i++){p=(TPlace)malloc(sizeof(Place));cout<<"请输入第"<<i+1<<"个地点："<<endl;cin>>p->code>>p->area ;p->lchild =p->rchild =NULL;p->list=NULL;p->count =0;Insert_T(tree,p);}cout<<"输入完成，输入y或者Y继续操作，其他键退出！";cin>>c;if(c=='y'||c=='Y') Fun1(tree);else {system("cls");Tour_1(tree);}}void Fun2(TPlace &tree,int x){int top=0;TPlace p,s[MAX];p=tree;while(p||top>0){while(p){s[top++]=p;p=p->lchild;}if(top>0){p=s[--top];cout<<setw(8)<<"区号:"<<p->code<<setw(10)<<"地名:"<<p->area<<setw(10)<<"人数:"<<p->count<<endl;p=p->rchild;}}if(tree==NULL)cout<<"还未录入旅游地！请稍后查询！"<<endl;cout<<"按任意键返回上一级菜单！"<<endl;system("pause");if(x==1)Tour_1(tree);if(x==2) Tour_2(tree);}void Fun3(TPlace &tree,int x){int n1=0,n2=0; char c;int top=0; int elem[MAX];TPlace p,s[MAX];p=tree;while(p||top>0){while(p){s[top++]=p;p=p->lchild;}if(top>0){p=s[--top];if(p->count<3&&x==1){cout<<setw(8)<<"区号:"<<p->code<<setw(10)<<"地名:"<<p->area<<setw(10)<<"人数:"<<p->count<<endl;elem[n1]=p->code ;n1++; } if(p->count<6&&x==2){cout<<setw(8)<<"区号:"<<p->code<<setw(10)<<"地名:"<<p->area<<setw(10)<<"人数:"<<p->count<<endl;;n2++; }p=p->rchild;}}if(x==1){cout<<"一共有"<<n1<<"各旅游景点人数少于三个"<<endl;cout<<"删除旅游地请输入D或者d，其他键返回菜单！"<<endl;cin>>c;if(c=='d'||c=='D') {for(int i=0;i<n1;i++) Delete_T(tree,elem[i]);cout<<"删除完成！"<<endl;} system("pause");Tour_1(tree);}if(x==2){cout<<"一共有"<<n2<<"个旅游景点仍可报名"<<endl;cout<<"按任意键返回上一级菜单！"<<endl;system("pause");Tour_2(tree);}}void Fun4(TPlace &tree){int co,id;TPlace p;linklist l,pre;p=tree;cout<<"输入要退出旅游地的区号和自己的身份证号："<<endl;cin>>co>>id;while(p&&p->code!=co ){if(p->code>co)p=p->lchild ;else p=p->rchild ;}if(!p){ cout<<"此旅游地点还未存在！"<<endl;system("pause");Tour_2(tree);}else{l=p->list;pre=l;while(l->id!=id){pre=l;l=l->next;}pre->next=l->next;free(l);p->count--;cout<<"输入要报名的地点区号："<<endl; cin>>co;Search_T(tree,co);}}void Mainlist(TPlace &tree){system("cls");cout<<"******************************************************"<<endl<<endl;cout<<" 欢迎登陆旅游购票系统"<<endl;cout<<" 请选择登录身份："<<endl;cout<<" 1、旅游公司管理人员"<<endl;cout<<" 2、游客"<<endl;cout<<" 3、退出程序"<<endl;cout<<"******************************************************"<<endl<<endl;int n,key,i=1;cin>>n;switch(n){case 3: Destory(tree);exit(0);case 1: do{cout<<"请输入登陆密码：";cin>>key;i++; }while(key!=12345&&i<=3); if(key==12345) Tour_1(tree);else Mainlist(tree);break;case 2: Tour_2(tree);break;default :cout<<"输入错误，请重新选择！"<<endl;system("pause"); Mainlist(tree);}}void Tour_1(TPlace &tree){system("cls");int n;cout<<"******************************************************"<<endl<<endl;cout<<" 1、输入旅游地点 "<<endl;cout<<" 2、查询各旅游地游客人数"<<endl;cout<<" 3、显示不足三人的旅游地"<<endl;cout<<" 4、退出"<<endl;cout<<"******************************************************"<<endl<<endl;cin>>n;switch(n){case 1: Fun1(tree);break;case 2: Fun2(tree,1);break;case 3: Fun3(tree,1);break;case 4: Mainlist(tree);break;default :cout<<"输入错误，请重新输入！"<<endl;system("pause");Tour_1(tree);; }}void Tour_2(TPlace &tree){int code;system("cls");int n;cout<<"******************************************************"<<endl<<endl;cout<<" 1、输入旅游地区号 "<<endl;cout<<" 2、显示所有旅游地"<<endl;cout<<" 3、查询可报名地"<<endl;cout<<" 4、修改旅游地点"<<endl;cout<<" 5、退出"<<endl;cout<<"******************************************************"<<endl<<endl;cin>>n;switch(n){case 1: cout<<"请输入区号："<<endl;cin>>code;Search_T(tree,code);break;case 2: Fun2(tree,2);break;case 3: Fun3(tree,2);break;case 4: Fun4(tree);break;case 5:Mainlist(tree);break;default :cout<<"输入错误，请重新输入！"<<endl;system("pause");Tour_2(tree);} }//销毁二叉树void Destory(TPlace &tree){if(!tree) {cout<<"此树已空！"<<endl;system("pause"); exit(0);} if(tree&&tree->lchild)Destory(tree->lchild);if(tree&&tree->rchild)Destory(tree->rchild);cout<<setw(5)<<tree->code<<setw(5)<<tree->area<<endl;Delet_L (tree->list);free(tree);}void main(){TPlace T=NULL;Mainlist(T);}六、调试分析及测试结果1、运行结果截图七、附录1、补充说明#include<stdlib.h> ：包含分配空间的头文件#include<string> ：包含对字符串进行操作的头文件#include<iomanip> ：包含控制输出格式的头文件Destory 函数为释放内存，删除所建树的所有节点。