信管1171李威数据结构实验2
一、实验目的
1、 熟练理解树和二叉树的相关概念，掌握的存储结构和相关操作实现；
2、 掌握树的顺序结构的实现；
3、 学会运用树的知识解决实际问题
二、实验内容
自己确定一个二叉树（树结点类型、数目和结构自定）利用顺序结构方法存储。实
现树的构造，并完成：
1） 层序输出结点数据；
2） 以合理的格式，输出各个结点和双亲、孩子结点信息；
3） 输出所有的叶子结点信息；
4）分析你的算法对于给定的二叉树的存储效率。
三、实验步骤
1、依据实验内容，先确定具体的二叉树，并说明结点的数据据类型；
2、设计具体的算法；
3、写出完整程序；
4、总结、运行结果和分析算法效率。
5、总体收获和不足，疑问等。
确定的二叉树为：
Sequence stack
#include<iostream>
using namespace std;
const int MAX=10;
class Seqstack
{
private:
inttop;
intdata[MAX];
public:
Seqstack(){top=-1;}
~Seqstack(){}
voidpush(int x);
intpop();
intgettop(){if(top!=-1)return data[top];};
int empty();
};
void Seqstack::push(int x)
{
if(top==MAX-1)
throw"upfull";
top++;
data[top]=x;
}
int Seqstack::pop()
{
if(top==-1)
throw"downfull";
intx=data[top];
top--;
returnx;
}
int Seqstack::empty()
{
if(top==-1)
return1;
elsereturn 0;
}
int main()
{
Seqstackk;
if(k.empty())
cout<<"vacancy!"<<endl;
else
cout<<"notvacancy*.*"<<endl;
cout<<"put15 instack:"<<endl;
k.push(15);
cout<<"put43 instack:"<<endl;
k.push(43);
cout<<"gettop stack's element:"<<endl;
cout<<k.gettop()<<endl;
cout<<"pushall elements:"<<endl;
k.pop();
cout<<"gettop stack's element:"<<endl;
cout<<k.gettop()<<endl;
return0;
}
Chain stack
#include<iostream>
using namespace std;
struct Data
{
intdata;
structData *next;
}*s;
class Seqstack
{
private:
structData *top;
public:
Seqstack(){top=NULL;}
~Seqstack(){}
voidpush(int x);
intpop();
intgettop(){if(top!=NULL)return top->data;};
intempty();
};
void Seqstack::push(int x)
{
s=newstruct Data;
s->data=x;
s->next=top;
top=s;
}
int Seqstack::pop()
{
intx=top->data;
top=top->next;
returnx;
}
int Seqstack::empty()
{
if(top==NULL)
return1;
elsereturn 0;
}
int main()
{
Seqstackk;
if(k.empty())
cout<<"vacancy!"<<endl;
else
cout<<"notvacancy*.*"<<endl;
cout<<"put15 instack:"<<endl;
k.push(15);
cout<<"put43 instack:"<<endl;
k.push(43);
cout<<"gettop stack's element:"<<endl;
cout<<k.gettop()<<endl;
cout<<"pushall elements:"<<endl;
k.pop();
cout<<"gettop stack's element:"<<endl;
cout<<k.gettop()<<endl;
return0;
}
Sequence queue
#include<iostream>
using namespace std;
const int MAX=10;
class Queue
{
private:
intfront;
intrear;
intdata[MAX];
public:
Queue(){front=rear=MAX-1;}
~Queue(){}
intdeQueue();
voidenQueue(int x);
intgetQueue(){if(front!=rear)return data[(front+1)%MAX];};
intempty();
};
int Queue::deQueue()
{
if(front==rear)
throw"downfull";
intx=data[front];
front=(front+1)%MAX;
returnx;
}
void Queue::enQueue(int x)
{
if((rear-1)%MAX==front)
throw"upfull";
rear=(rear+1)%MAX;
data[rear]=x;
}
int Queue::empty()
{
if(front==rear)
return1;
elsereturn 0;
}
int main()
{
QueueS;
if(S.empty())
cout<<"Queueis empty"<<endl;
else
cout<<"Queueisn't empty"<<endl;
cout<<"10 in"<<endl;
S.enQueue(10);
cout<<"5 in"<<endl;
S.enQueue(5);
cout<<"gettop element"<<endl;
cout<<S.getQueue()<<endl;
cout<<"allout in a time"<<endl;
cout<<S.getQueue()<<endl;
S.deQueue();
cout<<"getfront element"<<endl;
cout<<S.getQueue()<<endl;
return0;
}
Chain queue
#include<iostream>
using namespace std;
const int MAX=10;
struct Data
{
intdata;
structData *next;
}*q;
class Queue
{
private:
Data*rear,*front;
public:
Queue(){rear=NULL;front=NULL;}
~Queue(){}
intdeQueue();
voidenQueue(int x);
intgetQueue();
intempty();
};
int Queue::deQueue()
{
if(empty())
throw"down full";
intx=front->data;
front=front->next;
deleteq;
returnx;
}
void Queue::enQueue(int x)
{
q=newData;
q->data=x;
q->next=NULL;
if(empty())
front=rear=q;
else
{
rear->next=q;
rear=q;
}
}
int Queue::getQueue()
{
if(!empty())
returnfront->data;
}
int Queue::empty()
{
if(front==NULL&&rear==NULL)
return1;
else
return0;
}
int main()
{
QueueS;
if(S.empty())
cout<<"Queueis empty"<<endl;
else
cout<<"Queueisn't empty"<<endl;
cout<<"10in"<<endl;
S.enQueue(10);
cout<<"5in"<<endl;
S.enQueue(5);
cout<<"gettop element"<<endl;
cout<<S.getQueue()<<endl;
cout<<"allout in a time"<<endl;
S.deQueue();
return0;
}
A program which transfor decimal numdersinto binary numbers
#include<iostream>
using namespace std;
const int MAX=10;
struct Data
{
intdata;
struct Data *next;
}*s;
class seqStack
{
private:
structData *top;
public:
seqStack(){top=NULL;}
~seqStack(){}
voidpush(int x);
intpop();
voidgetseqbinary();
intempty();
};
void seqStack::push(int x)
{
s=newstruct Data;
s->data=x;
s->next=top;
top=s;
}
int seqStack::pop()
{
intx=top->data;
top=top->next;
returnx;
}
int seqStack::empty()
{
if(top==NULL)
return1;
else
return0;
}
void seqStack::getseqbinary()
{
while(top!=NULL)
{
cout<<top->data;
top=top->next;
}
}
void change(int m)
{
seqStackS;
intk,r;
do
{
r=m%2;
S.push(r);
k=m/2;
m=k;
}
while(m!=0);
cout<<"transforinto binary number is:"<<endl;
S.getseqbinary();
cout<<endl;
}
int main()
{
intx;
cout<<"pleasetype in the decimal number you want to transfor into binarynumber"<<endl;
cin>>x;
change(x);
return0;
}
Canteen queue system
#include<iostream>
using namespace std;
struct Data
{
intdata;
structData *next;
}*q;
class Queue
{
private:
Data*rear,*front;
staticint num;
public:
Queue(){rear=NULL;front=NULL;}
~Queue(){}
intdeQueue();
voidenQueue();
voidgetQueue();
intempty();
intgetnum(){return num;};
};
int Queue::num=0;
int Queue::deQueue()
{
if(empty())
throw"down full";
q=front;
intx=front->data;
front=front->next;
deleteq;
returnx;
}
void Queue::enQueue()
{
num++;
q=newData;
q->data=num;
q->next=NULL;
if(empty())
front=rear=q;
else
{
rear->next=q;
rear=q;
}
}
void Queue::getQueue()
{
if(!empty())
q=front;
while(q!=NULL)
{
cout<<q->data<<"";
q=q->next;
}
}
int Queue::empty()
{
if(front==NULL||rear==NULL)
return1;
else
return0;
}
int main()
{
QueueS;
intx,flag=0;
cout<<"1.getnumber and queue"<<endl;
cout<<"2.finishand out of queue"<<endl;
cout<<"3.returnnumber"<<endl;
return0;
do
{
cin>>x;
switch(x)
{
case1:
S.enQueue();
cout<<"arrangenumber:"<<S.getnum()<<endl;
break;
case2:
try
{
cout<<S.deQueue()<<"numberfinish"<<endl;
}
catch(char*s)
{
cout<<s<<endl;
}
break;
case3:
cout<<"Queuenumber is:"<<endl;
S.getQueue();
break;
case4:
flag=1;
break;
}
}while(!flag);
return0;
}