数据结构.docx
《数据结构.docx》由会员分享，可在线阅读，更多相关《数据结构.docx（32页珍藏版）》请在冰点文库上搜索。
数据结构
《数据结构》实验报告
班级：
学号：
姓名：
实验一链表
1．#include
usingnamespacestd;
structnode{
intdata;
node*next;
};
classlist{
public:
list（）;
voidcreate_R（）;
voidprint（）;
node*locate（constintx）const;
private:
intcount;
node*head;
};
list:
:
list（）{
head=newnode;
head->next=NULL;
count=0;
}
voidlist:
:
create_R（）{
intx;
cin>>x;
node*rear=head;
while（x!
=-1）
{
count++;
node*s=newnode;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
voidlist:
:
print（）{
node*p;
p=head->next;
while（p!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<}
node*list:
:
locate（constintx）const{
node*p;
inti=1;
p=head->next;
if（x>count）
returnNULL;
else
while（ii++;
p=p->next;}
returnp;
cout<data<}
intmain（）{
listA;
inti;
cout<<"请输入数据数据"<A.create_R（）;
A.print（）;
cout<<"请输入查询位置"<cin>>i;
cout<<"查询位置指针地址为"<return0;
}
2.#include
usingnamespacestd;
structnode{
intdata;
node*next;
};
classlist{
public:
list（）;
voidcreate_R（）;
voidprint（）;
voidinsert（constinti,constintx）;
private:
intcount;
node*head;
};
list:
:
list（）{
head=newnode;
head->next=NULL;
count=0;
}
voidlist:
:
create_R（）{
intx;
cin>>x;
node*rear=head;
while（x!
=-1）
{
count++;
node*s=newnode;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
voidlist:
:
insert（constinti,constintx）{
node*p=NULL;
p=head->next;
intj=1;
while（p!
=NULL&&j<（i-1））{
p=p->next;
j++;}
node*s=newnode;
s->data=x;
s->next=p->next;
p->next=s;
count++;
}
voidlist:
:
print（）{
node*p;
p=head->next;
while（p!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<}
intmain（）{
listA;
A.create_R（）;
A.print（）;
cout<A.insert（3,5）;
cout<A.print（）;
cout<return0;
}
3.#include
usingnamespacestd;
structnode{
intdata;
node*next;
};
classlist{
public:
list（）;
voidcreate_R（）;
voidprint（）;
voiddelete_element（constinti）;
private:
intcount;
node*head;
};
list:
:
list（）{
head=newnode;
head->next=NULL;
count=0;
}
voidlist:
:
create_R（）{
intx;
cin>>x;
node*rear=head;
while（x!
=-1）
{
count++;
node*s=newnode;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
voidlist:
:
delete_element（constinti）{
node*p=NULL,*u=NULL;
intj;
p=head;j=0;
while（j!
=（i-1）&&p!
=NULL）{
p=p->next;
j++;
}
if（i<1||i>count）
cout<<"删除位置错误"<u=p->next;
p->next=u->next;
deleteu;
count--;
}
voidlist:
:
print（）{
node*p;
p=head->next;
while（p!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<}
intmain（）{
listA;
A.create_R（）;
A.print（）;
cout<A.delete_element（3）;
cout<A.print（）;
cout<return0;
}
4.#include
usingnamespacestd;
structnode{
intdata;
node*next;
};
classlist{
public:
list（）;
voidcreate_R（）;
voidprint（）;
voidinsert（constintx）;
private:
intcount;
node*head;
};
list:
:
list（）{
head=newnode;
head->next=NULL;
count=0;
}
voidlist:
:
create_R（）{
intx;
cin>>x;
node*rear=head;
while（x!
=-1）
{
count++;
node*s=newnode;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
voidlist:
:
insert（constintx）{
node*p,*s;
p=head;
while（（p->next!
=NULL）&&p->next->datap=p->next;
//if（p->next==NULL||p->next->data>x）
s=newnode;
s->data=x;
s->next=p->next;
p->next=s;
count++;
}
voidlist:
:
print（）{
node*p;
p=head->next;
while（p!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<}
intmain（）{
listA;
A.create_R（）;
A.insert（55）;
cout<A.print（）;
cout<return0;
}
5.#include
usingnamespacestd;
structnode{
intdata;
node*next;
};
classlist{
public:
list（）;
voidcreate_R（）;
voidprint（）;
node*get_head（）{returnhead;};
voidcopy1（listA,listB）;
voidcopy2（listA,listC）;
private:
intcount;
node*head;
};
list:
:
list（）{
head=newnode;
head->next=NULL;
count=0;
}
voidlist:
:
create_R（）{
intx;
cin>>x;
node*rear=head;
while（x!
=-1）
{
count++;
node*s=newnode;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
voidlist:
:
copy1（listA,listB）{
node*s,*PA,*PB;
PA=A.get_head（）->next;
PB=B.get_head（）;
while（PA!
=NULL）{
s=newnode;
s->data=PA->data;
PB->next=s;
PB=s;
count++;
PB->next=NULL;
if（PA->next==NULL）break;
PA=PA->next->next;
}
}
voidlist:
:
copy2（listA,listC）{
node*s,*PA,*PC;
PA=A.get_head（）->next->next;
PC=C.get_head（）;
while（PA!
=NULL）{
s=newnode;
s->data=PA->data;
PC->next=s;
PC=s;
count++;
PC->next=NULL;
if（（PA->next）==NULL）break;
PA=PA->next->next;
}
}
voidlist:
:
print（）{
node*p;
p=head->next;
while（p!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<}
intmain（）{
listA;listB;listC;
A.create_R（）;
A.copy1（A,B）;
A.copy2（A,C）;
A.print（）;
cout<B.print（）;
cout<C.print（）;
cout<return0;
}
6.#include
usingnamespacestd;
structnode{
intdata;
node*next;
};
classlist{
public:
list（）;
voidcreate_R（）;
voidprint（）;
node*get_head（）{returnhead;};
voidmerge_list（listA,listB,listC）;
private:
intcount;
node*head;
};
list:
:
list（）{
head=newnode;
head->next=NULL;
count=0;
}
voidlist:
:
create_R（）{
intx;
cin>>x;
node*rear=head;
while（x!
=-1）
{
count++;
node*s=newnode;
s->data=x;
rear->next=s;
rear=s;
rear->next=NULL;
cin>>x;
}
}
voidlist:
:
merge_list（listA,listB,listC）
{
node*pa,*pb,*rc,*u;
rc=C.get_head（）;
pa=A.get_head（）->next;pb=B.get_head（）->next;
while（pa!
=NULL&&pb!
=NULL）
{
if（pa->datadata）
pa=pa->next;
elseif（pa->data>pb->data）
pb=pb->next;
else
{u=newnode;
u->data=pa->data;
rc->next=u;
rc=u;
rc->next=NULL;
C.count++;
pa=pa->next;pb=pb->next;
}
}
}
voidlist:
:
print（）{
node*p;
p=head->next;
while（p!
=NULL）{
cout<data<<"";
p=p->next;
}
cout<}
intmain（）{
listA;listB;listC;
cout<<"inputA:
"<A.create_R（）;
cout<<"inputB:
"<B.create_R（）;
C.merge_list（A,B,C）;
A.print（）;
cout<B.print（）;
cout<C.print（）;
cout<return0;
}
实验二二叉树
1.#include
usingnamespacestd;
typedefstructbnode
{chardata;
structbnode*lchild,*rchild;
};
typedefbnode*bitre;
voidcreate_pre_bitre_（bitre&T）{
charch;
cin>>ch;
if（ch=='.'）T=NULL;
else{
T=newbnode;
T->data=ch;
create_pre_bitre_（T->lchild）;
create_pre_bitre_（T->rchild）;
}
}
inthigh（bnode*T）{
if（T==NULL）return0;
else
return（（high（T->lchild）>high（T->rchild））?
high（T->lchild）:
high（T->rchild））+1;
}
intmain（）
{
bitret;
cout<<"输入该二叉树的先序序列"<create_pre_bitre_（t）;cout<cout<<"高度="<return0;
}
2.#include
#include
usingnamespacestd;
typedefstructbnode
{chardata;
structbnode*lchild,*rchild;
};
typedefbnode*bitre;
intn=0;
voidcreate_pre_bitre_（bitre&T）{
charch;
cin>>ch;
if（ch=='.'）T=NULL;
else{
T=newbnode;
T->data=ch;
create_pre_bitre_（T->lchild）;
create_pre_bitre_（T->rchild）;
}
}
voidinorder（bnode*T）
{
if（T!
=NULL）
{
n++;
inorder（T->lchild）;
cout<data<<"（"<inorder（T->rchild）;
n--;
}
}
intmain（）
{
bitret;
cout<<"输入该二叉树的先序序列"<create_pre_bitre_（t）;cout<cout<<"该二叉树的中序序列为";
inorder（t）;cout<return0;
}
3.#include
usingnamespacestd;
constintmax=5;
inti=1;charA[max];
typedefstructbnode
{chardata;
structbnode*lchild,*rchild;
};
typedefbnode*bitre;
voidcreate（bitre&T,inti）
{
if（i>max）T=NULL;
else{
if（A[i]=='.'）T=NULL;
else{
T=newbnode;
T->data=A[i];
create（T->lchild,2*i）;
create（T->rchild,2*i+1）;}
}
}
voidcreate_A（）
{
cout<<"请输入数组：
"<for（intn=1;n>A[n];}
}
voidpreorder（bnode*T）
{
if（T!
=NULL）
{cout<data<<"";
preorder（T->lchild）;
preorder（T->rchild）;
}
}
voidinorder（bnode*T）{
if（T!
=NULL）
{
inorder（T->lchild）;
cout<data<<"";
inorder（T->rchild）;
}
}
voidpostorder（bnode*T）
{
if（T!
=NULL）
{
postorder（T->lchild）;
postorder（T->rchild）;
cout<data<<"";
}
}
intmain（）
{
bitret;
create_A（）;
create（t,i）;
cout<<"该二叉树的先序序列为";
preorder（t）;
cout<cout<<"该二叉树的中序序列为";
inorder（t）;
cout<cout<<"该二叉树的后序序列为";
postorder（t）;
cout<cout<data;
return0;
}
4.#include
#include
usingnamespacestd;
typedefstructbnode
{chardata;
structbnode*lchild,*rchild;
};
typedefbnode*bitre;
voidcreate_pre_bitre_（bitre&T）
{
charch;
cin>>ch;
if（ch=='.'）T=NULL;
else{
T=newbnode;
T->data=ch;
create_pre_bitre_（T->lchild）;
create_pre_bitre_（T->rchild）;
}
}
voidcopy_T（bitre&T,bitre&T1）
{
if（T==NULL）T1=NULL;
else
{
T1=newbnode;
T1->data=T->data;
copy_T（T->lchild,T1->lchild）;
copy_T（T->rchild,T1->rchild）;
}
//cout<<"拷贝成功"<}
voidpreorder（bnode*T）
{
if（T!
=NULL）
{cout<data<<"";
preorder（T->lchild）;
preorder（T->rchild）;
}
}
voidinorder（bnode*T）
{
if（T!
=NULL）
{
inorder（T->lchild）;
cout<data<<"";
inorder（T->rchild）;
}
}
voidpostorder（bnode*T）
{
if（T!
=NULL）
{
postorder（T->lchild）;
postorder（T->rchild）;
cout<data<<"";
}
升级会员 