数据结构
实验报告
实验题目： 二叉排序树
班 级： 计算机141（专升本）
姓 名： 黄跃翔
学 号： 14501111
完成日期： 2015年6月12日
一、需求分析（说明实验任务，包括输入、输出、功能、测试数据等）
1.问题描述（Problem Description）：
输入一个整数关键字序列L，生成一棵用链式存储结构存储的二叉排序树，对该二叉排序树能进行查找和插入结点的操作，并对该二叉排序树中结点的关键字按递增和递减顺序输出。
具体要求：
输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，要求依次完成以下工作：
(1) 以这n个整数生成(建立)一棵用链式存储结构存储的二叉排序树；
(2) 按递增顺序输出该二叉排序树中的整数(关键字)；
(3) 输入一个整数key，对该二叉排序树进行查找，若在该二叉排序树中存在这个整数key，则输出find，否则输出not find。
(4) 输入一个整数key，若该二叉排序树中不存在这个整数key，则将key插入到该二叉排序树中，使插入后仍为原性质的二叉排序树；否则不必插入；
(5) 在(4)的基础上，按递减顺序输出该二叉排序树中的整数(关键字)。
2.对于输入输出的要求：
Input（输入）
输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行输入正整数n(5≤n≤20)，第二行输入n个整数，第三和第四行均输入整数key。
Output（输出）
每组输出的第一行为按递增顺序输出该二叉排序树中的整数(关键字)，每两个整数之间一个空格；第二行为find或not find；第三行为按递减顺序输出该二叉排序树中的整数(关键字)。
4.测试数据总共有两组：
第一组
8
10 79 6 81 43 75 26 69
43
69
第二组
10
94 22 25 24 20 42 39 71 53 57
88
1
5.测试数据结果输出：
第一组：
6 10 26 43 69 75 79 81
find
81 79 75 69 43 26 10 6
第二组：
20 22 24 25 39 42 53 57 71 94
not find
94 71 57 53 42 39 25 24 22 20 1
二、概要设计(数据类型的定义、算法思想、主程序和子程序(或功能)模块的说明及各程序模块之间的层次(调用)关系)
1.数据结构
typedef struct node // 二叉排序树中的结点结构
{
int data; // 整数(关键字)数据域
struct node *lchild,*rchild; // 指向左右孩子的指针
}nodeb,*bitree;
2.算法思想
第一部分：
建立二叉排序树。其关键字要求是各不相同的，则对于输入的关键字序列中的每一个整数，要在正在建立的二叉排序树中去查找是否已经存在该整数，不存在时，由查找模块返回要插入的结点位置的双亲结点，根据要建立的二叉排序树的性质，当要增加的整数比双亲结点的整数小的话就插到其左孩子的位置，否则插到其右孩子的位置。这样重复，直到输入结束(输入的整数为-1)为止。
第二部分：
查找算法是从二叉排序树的根结点开始，根据要查找的整数，若比其当前二叉排序树结点中的整数小就进入其左孩子所在的左子树中继续搜索，否则进入其右左孩子所在的右子树中继续搜索，这过程中，每进入子树前，保存当前结点，以便带回要插入结点的双亲结点。搜索直至找到要查找的整数，用一指针带回；或搜索直至叶子结点的下方，找不到要查找的整数而使空指针带回，以便判断要查找的整数是否找到。
第三部分：
按递增顺序输出该二叉排序树中的整数(关键字)，可直接用某种二叉树的遍历算法实现；按递减顺序输出该二叉排序树中的整数(关键字)，只要对某种二叉树的遍历算法稍作修改即可。同时插入算法思路和建立二叉排序树时增加一个整数的思路是一样的。
3.主程序
int main()
{
重复m组：
调用createbintree()算法建立二叉排序树t；
调用某种二叉树遍历算法按递增顺序输出该二叉排序树中的整数(关键字)；
输入要查找的整数，调用searchbst()算法查找要查找的整数；
根据查找的结果输出相应的信息；
输入要插入的整数，调用insertbst()算法将整数插入到二叉排序树中；
根据插入的结果输出相应的信息；
调用稍作修改的某种二叉树遍历算法按递减顺序输出该二叉排序树中的整数(关键字)；
}
4.子程序(或功能)模块
①建立二叉排序树算法
bitree createbintree(int n)
建立有n个整数的二叉排序树，其二叉排序树t，用函数值返回树
{
定义几个树；
定义2个int变量；
置t为空树；
for(n次)
{
置上面某一数为空树
输入整数；
查找该整数；
if(该整数在当前的二叉排序树中不存在)
{ 申请结点；
对该结点赋以该整数；
该结点的左右指针赋空值；
根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置
// 注意当二叉排序树还是空树时情况的处理
}
}
返回建好的二叉排序树t；
}
②查找算法
void searchbst(bitree t,bitree *f,bitree *p,int key)
//在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。f 为指向双亲结点的
{
while(t不空且t中的整数不是要找的整数key)
{ 用f记录当前结点；
if(要找的整数key小于t中的整数)
t进入其左孩子所在的左子树；
else t进入其右孩子所在的右子树；
}
}
③插入(增加)整数算法
int insertbst(bitree *t,int key)
//在二叉排序树t中插入整数key的结点，是否插入成功用函数值返回
{ 在二叉排序树t中查找整数key；
if(整数key在二叉排序树t中不存在)
{ 申请结点；
对该结点赋以该整数；
该结点的左右指针赋空值；
根据查找的结果，把该结点挂到某结点的左孩子或右孩子位置
// 注意当二叉排序树还是空树时情况的处理
}
else 插入不成功；
}
三、详细设计(实现概要设计中定义的数据类型，对主程序和其他模块写出算法，说明子模块的调用关系)
首先是对这次实现的二叉树建立，代码如下：
typedef struct node // 二叉排序树中的结点结构
{
int data; // 整数(关键字)数据域
struct node *lchild, *rchild; // 指向左右孩子的指针
}nodeb, *bitree;
然后是查询KEY的树节点操作代码：
void searchbst(bitree t, bitree *f, bitree *p, int key)
{
*p = t; *f = NULL;
// 在二叉排序树t中查找整数为key的结点，若找到，则p指向该结点，否则p为空。f 为
//指向双亲结点的
while (*p != NULL && ((*p)->data != key))
{
*f = *p;
if (key<(*p)->data) *p = (*p)->lchild;
else (*p) = (*p)->rchild;
}
}
接着是建立二叉树算法：
bitree createbintree(int n)//建立二叉树算法
{
bitree p, q, f, t;
int i, d;
t = NULL;
for (i = 0; i<n; i++)
{
p = NULL;
cin >> d;
searchbst(t, &f, &p, d);
if (!p)
{
q = new nodeb;
q->data = d;
q->lchild = q->rchild = NULL;
if (f == NULL) t = q;
else if (d<f->data) f->lchild = q;
else f->rchild = q;
}
}
return t;
}
最后一个子模块插入整数算法：
int insertbst(bitree *t, int key)
/* 在二叉排序树t中插入整数key的结点，是否插入成功用函数值返回 */
{
bitree p, f, s;
searchbst(*t, &f, &p, key);
if (!p)
{
s = new nodeb;
s->data = key;
s->lchild = s->rchild = NULL;
if (!f) *t = s;
else if (key<f->data) f->lchild = s;
else f->rchild = s;
return 1;
}
else return 0;
}
void inordertraverse(bitree t, int *i)
{
if (t)
{
inordertraverse(t->lchild, i);
(*i)++;
if (*i == 1) printf("%d", t->data);
else printf(" %d", t->data);
inordertraverse(t->rchild, i);
}
}
void postordertraverse(bitree t, int *i)
{
if (t)
{
postordertraverse(t->rchild, i);
(*i)++;
if (*i == 1) printf("%d", t->data);
else printf(" %d", t->data);
postordertraverse(t->lchild, i);
}
}
主函数中的模块的调用如下代码：
int main()
{
bitree t, p, f;
int d, j, n, key, i;
cin >> d;
for (j = 0; j<d; j++)
{
cin >> n;
t = createbintree(n);
i = 0; inordertraverse(t, &i); printf("\n");
cin >> key;
searchbst(t, &f, &p, key);
if (p) printf("find\n");
else printf("not find\n");
cin >> key;
insertbst(&t, key);
i = 0; postordertraverse(t, &i); printf("\n");
}
return 1;
}
四、调试分析(调试过程中遇到的问题是如何解决的、对设计与实现简要回顾或分析、经验和体会、经验和不足等，至少写三条)
1. 二叉排序树的结点的构造，有数据域和只想左右孩子的指针。
2. 对已经构造好的二叉排序树进行遍历，由二叉排序树的性质可知，要升序遍历可采用中序遍历二叉树的方法，而要降序遍历时，则需要采用递归先遍历右子树，再根结点，最后遍历左子树。
3. 二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题
回顾整个实验过程，大整数的加法可以通过用不同的储存结构对其进行存储再运算得到（可以推广到其他问题）。
而本次实验我试验了2种存储结构，即链式存储方式和顺序存储方式，对于用链表作为存储结构，感觉到这种方式可以适应不定长度的大数的好处。
唯一遗憾的就是没有进一步去研究其他的运算方式，如“减乘除”，或者更繁杂的开根号，N次方等。以后有空余时间一定要去好好了解一下。
通过本次课程设计，我对大整数的理解和认识又有了进一步的提高，对之前学过的链表和顺序表的知识进行了一次复习巩固，更难得的是对这些理论知识进行了一次映像深刻的应用实践，通过同学间的交流，个人去图书馆或是网上的资料的查阅完成了本次数据结构的第一次的实验。只要有信心，不断努力就能够解决遇到的问题。
五、测试结果(列出测试数据和结果，说明是否通过测试)
这是第一组数据的测试结果：
这是第二组数据的测试结果：
可见测试结果与实验要求结果符合！
六、实验成绩(教师填写)
教师签名：
第二篇：数据结构实验报告(实验三 停车场管理)
韶 关 学 院
学 生 实 验 报 告 册
实验课程名称：数据结构与算法
实验项目名称：实验三 栈和队列及其应用
停车场管理
实验类型（打√）：（基础 、综合 、设计√ ）
院 系：信息工程学院计算机系 专 业：*****
姓 名：*** 学 号：*****
指导老师：陈正铭
韶关学院教务处编制
一、实验预习报告内容
预习日期：20##年 4 月 16 日
二、实验原始（数据）记录
实验时间： 20## 年 4 月 18 日（星期三 第 7，8 节）
实验同组人：
三、实验报告内容
20##年 4 月 20 日
注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。
2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。
【源程序】
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
typedef int Status; //元素类型
int flag=0;
typedef struct{
int carnumber; //车号
int time; //汽车“到”或“离”的时刻
}SElemType;
//以下是对栈数据类型的定义
#define STACK_INIT_SIZE 2
#define STACKINCREMENT 1
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &s){
//构造一个空栈S
s.base=(SElemType * )malloc
(STACK_INIT_SIZE * sizeof(SElemType));
if(!s.base) exit(0);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return 1;
}
Status Push(SqStack &s,SElemType e){
//插入元素e为新的栈顶元素
if(s.top-s.base>=s.stacksize){//栈满
s.base=(SElemType * ) realloc
(s.base,(s.stacksize+STACKINCREMENT) * sizeof(SElemType));
if(!s.base) exit(0); //存储分配失败
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return 1;
}
Status Pop(SqStack &s,SElemType &e){
//若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}
//以下是对队列数据类型的定义
typedef struct QNode{
SElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q){
//构造一个空队列Q
Q.front=Q.rear
=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(0);
Q.front->next=NULL;
return 1;
}
Status EnQueue(LinkQueue &Q,SElemType e){ //插入元素e为新的队尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(0);
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}
Status DeQueue(LinkQueue &Q,SElemType &e){//若队列不空，则删除Q的对头元素，用e返回其值，并返回OK，否则返回ERROR
QueuePtr p;
if(Q.front==Q.rear) return 0;
p=Q.front->next;
e=p->data;
p->next=NULL;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return 1;
}
//对汽车到达时的处理
void CarArrival(SqStack &s,LinkQueue &Q){
SElemType e;
cout<<"请输入车号:";
cin>>e.carnumber;
cout<<"请输入到达时刻:";
cin>>e.time;
if(s.top-s.base>s.stacksize){
EnQueue(Q,e);
cout<<"--------------------------------\n";
cout<<"|车号| 停车位置 | 到达时刻 |\n";
cout<<"--------------------------------\n";
cout<<"|"<<e.carnumber<<"| 停在便道上等待|"<<e.time<<" |"<<"\n";
cout<<"--------------------------------\n";
}
else{
Push(s,e);
*s.top++=e;
cout<<"-------------------------------\n";
cout<<"|车号| 停车位置 | 到达时刻 |\n";
cout<<"-------------------------------\n";
cout<<"|"<<e.carnumber<<"| 停在停场内"<<++flag<<"号位|"<<e.time<<" |"<<"\n";
cout<<"-------------------------------\n";
}
}
void CarDeparture(SqStack &s,LinkQueue &Q){
SqStack T; //临时倒车处
int money;//停留时刻
SElemType a,e;
int carnumber,time;;
InitStack(T);//构造临时倒车处
cout<<"请输入车号:"<<endl;
cin>>carnumber;
cout<<"请输入离去时刻:"<<endl;
cin>>time;
a=*(s.top-1);
do{
Pop(s,e);Push(T,e);
*s.top--=e;
a=*(s.top-1);
}while(e.carnumber!=carnumber);
Pop(s,e);
money=time-e.time;
cout<<"韶关学院停车场收费单 \n";
cout<<"--------------------------------\n";
cout<<"|车号 |到达时刻 |离去时刻 |停留时刻 |费用(元) |\n";
cout<<"--------------------------------\n";
cout<<"|"<<carnumber<<"|"<<e.time<<" |"<<time<<"|"<<money<<" |"<<money*2<<" |"<<"\n";
cout<<"--------------------------------\n";
flag--;
while(T.base!=T.top){
Pop(T,e);
*s.top++=e;
}
while(Q.front!=Q.rear){
if(s.top-s.base<s.stacksize){
DeQueue(Q,e);
Push(s,e);
*s.top++=e;
}
}
if(s.top-s.base> STACK_INIT_SIZE){
cout<<"\n便道上有车进入停车场!"<<"\n此车停在"<<++flag<<"车位"<<endl;
}
}
void shurujiesu(){
cout<<"\n\n输入结束（END)!\n\n";
}
void main()
{ char choice;
SqStack s;//s为停车场
LinkQueue Q;//Q为便道
InitStack(s);InitQueue(Q);
cout<<"----------------------------\n";
cout<<|*********欢迎使用广东省韶关学院停车场管理系统**********| \n";
cout<<"|==========================|\n";
cout<<"\n|A、汽车到达 | \n";
cout<<"\n|D、汽车离开 | \n";
cout<<"\n|E、输入结束 | \n";
cout<<"\n|Q、退出本系统 | \n";
cout<<"\n|------------------| \n";
cout<<" 请选择所需要的操作功能(A,D,E,Q):";
do{
cin>>choice;
switch(choice){
case'A':
CarArrival(s,Q);break;
case'D':
CarDeparture(s,Q);break;
case'E':
shurujiesu();break;
case'Q':
exit(0);
}
cout<<"请选择所需要的操作功能(A,D,E,Q):";
}while(1);
}