数据结构实验报告书Word格式.docx
《数据结构实验报告书Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告书Word格式.docx（29页珍藏版）》请在冰点文库上搜索。
if（other->
data<
=p->
data）
if（p==*head）
next=p;
else
last->
next=other;
p->
}
voidcreate（structAB**p,structAB*hb）
（*p）=（structAB*）malloc（sizeof（structAB））;
（*p）->
data=hb->
data;
intmain（）
intn;
structAB*ha,*hb,*p,*p0;
structAB*heada,*headb;
structAB*pre_a;
cout<
<
"
A（x）:
（endof0）"
endl;
ha=NULL;
while（scanf（"
%d"
&
n）&
n）
p=（structAB*）malloc（sizeof（structAB））;
data=n;
sort_insert（&
ha,p）;
heada=ha;
B（x）:
hb=NULL;
hb,p）;
headb=hb;
endl<
show!
p=heada;
while（p）
"
;
p=headb;
//"
work!
pre_a=ha;
while（ha&
hb）
if（ha->
hb->
pre_a==ha）
create（&
p0,hb）;
p0="
p0->
p0->
next=ha;
pre_a=p0;
heada=p0;
hb=hb->
elseif（ha->
pre_a!
=ha）
pre_a->
next=p0;
pre_a=ha;
ha=ha->
data==hb->
if（hb!
ha=pre_a;
ha->
next=hb;
worked!
return0;
三、实验结果截图
实验二
结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。
stdio.h>
stdlib.h>
structADT
inta,n;
structADT*next;
structADT*heada,*headb,*headc;
voidsort_insert（structADT**head,structADT*other）
structADT*last,*p;
n>
n&
last=p;
p=p->
n<
=p->
if（p==*head）
{
other->
next=*head;
*head=other;
}
else
last->
other->
p->
intx,y;
structADT*p;
structADT*pa,*pb,*pc;
printf（"
\n"
）;
heada=NULL;
%d%d"
x,&
y）&
x||y）
pa=（structADT*）malloc（sizeof（structADT））;
pa->
a=x;
n=y;
heada,pa）;
pa=heada;
headb=NULL;
pb=（structADT*）malloc（sizeof（structADT））;
pb->
headb,pb）;
pb=headb;
while（p!
if（p==heada）
A（x）=%d（%d）"
p->
a,p->
n）;
+%d（%d）"
if（p==headb）
B（x）=%d（%d）"
p=（structADT*）malloc（sizeof（structADT））;
a=0;
n=0;
pc=p;
headc=pc;
while（pa!
=NULL&
pb!
if（pa->
pc->
next=pa;
pc=pa;
pa=pa->
elseif（pa->
next=pb;
pc=pb;
pb=pb->
intaa=pa->
a+pb->
a;
if（aa==0）{pa=pa->
pb=pb->
a=aa;
n=pa->
n;
pa=pa->
next=pa?
pa:
pb;
Andyouwillget:
p=headc->
if（p==headc->
next）
C（x）=%d（%d）"
实验三
二叉树的动态二叉链表结构中的每个结点有三个字段：
data，lchild，rchild。
其中指针lchild
下标
data
lchild
rchild
1
A
2
6
B
3
4
C
0
D
5
E
F
7
G
和rchild的类型为bitre。
静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：
所不同的是，lchild和rdhild为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。
例如，二叉树的静态二叉链表如上图所示。
编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形式和有关的类型描述。
其中n为一个确定的整数。
structnode
structnode*l,*r;
}*tree;
structstatics
intlchild;
intrchild;
}sta[8];
intk=0;
inta[20]={1,2,3,0,0,4,5,0,0,0,6,0,7,0,0};
voidcreatpreorder（structnode*（&
T））
intnum=a[k++];
if（num==0）T=NULL;
T=（structnode*）malloc（sizeof（structnode））;
if（T==NULL）
exit（-1）;
T->
n=num;
creatpreorder（T->
l）;
creatpreorder（T->
r）;
intv=1;
voidpreorder（structnode*T）
if（T==NULL）return;
if（v==1）
printf（"
%c"
'
A'
-1+T->
printf（"
%c"
//动静转换
sta[T->
n].n=T->
if（T->
l==NULL）
sta[T->
n].lchild=0;
sta[T->
n].lchild=T->
l->
r==NULL）
n].rchild=0;
n].rchild=T->
r->
v++;
preorder（T->
preorder（T->
return;
inti;
creatpreorder（tree）;
先序遍历二叉树:
preorder（tree）;
\n\n"
静态二叉树:
下标\tdata\tlchild\trchild\n"
for（i=1;
i<
8;
i++）
%d\t%c\t%d\t%d\n"
sta[i].n,'
-1+sta[i].n,
sta[i].lchild,sta[i].rchild）;
实验四
设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O
（1）辅助空间。
string>
queue>
intn,m;
//点,边个数
constintN=100;
structEdge
intv;
structEdge*next;
}*Edge[N],*head[N];
boolvisit[N];
voidinit（）
for（i=0;
=n;
head[i]=NULL;
visit[i]=false;
voidlink（inta,intb）
structEdge*p;
p=（structEdge*）malloc（sizeof（structEdge））;
v=b;
next=head[a];
head[a]=p;
ints;
queue<
int>
Q;
voidBFS（structEdge*h）
intx;
while（!
Q.empty（））Q.pop（）;
Q.push（h->
v）;
visit[h->
v]=true;
Q.empty（））
x=Q.front（）;
Q.pop（）;
if（s==0）
x;
s++;
for（p=head[x]->
p!
=NULL;
p=p->
if（!
visit[p->
v]）
Q.push（p->
visit[p->
intss;
voidDFS（structEdge*h）
if（h==NULL）return;
for（p=h;
if（p==h&
!
visit[h->
if（ss==0）
h->
v;
ss++;
DFS（head[p->
v]）;
DFS（p）;
inti,a,b;
n,&
m）!
=EOF&
init（）;
for（i=0;
m;
scanf（"
a,&
b）;
link（a,b）;
v=i;
next=head[i];
head[i]=p;
p=head[i];
cout<
:
while（p!
{
if（p==head[i]）
cout<
else
->
p=p->
}
cout<
BFS:
s=0;
if（!
visit[i]）BFS（head[i]）;
memset（visit,false,sizeof（visit））;
DFS:
ss=0;
visit[i]）DFS（head[i]）;
实验五
5、二叉排序树采用二叉链表存储。
写一个算法，删除结点值是X的结点。
要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：
可不考虑被删除的结点是根的情况）。
#include<
iomanip>
cmath>
typedefstructtreenode
{
structtreenode*left;
structtreenode*right;
}BiTreenode,*BiTreep;
intSearchBST（BiTreep&
rt,intkey,BiTreepfather,BiTreep&
p）
{
p=father;
rt）
{
p=father;
returnfalse;
}
elseif（key==rt->
data）
p=rt;
returntrue;
elseif（key<
rt->
returnSearchBST（rt->
left,key,rt,p）;
returnSearchBST（rt->
right,key,rt,p）;
intInsertBST（BiTreep&
rt,intkey）
BiTreepp;
BiTreeps;
SearchBST（rt,key,NULL,p））
s=（BiTreep）malloc（sizeof（BiTreenode））;
s->
data=key;
left=s->
right=NULL;
if（!
p）
rt=s;
elseif（key<
p->
left=s;
else
right=s;
else
intDelte（BiTreep&
right）
BiTreepq=p;
left;
free（q）;
elseif（!
left）
right;
BiTreepfather=p;
BiTreeps=p->
while（s->
{
father=s;
s=s->
}
data=s->
if（p==father）
left=s->
returntrue;
}
intDeletBST（BiTreep&
bst,intitem）
if（bst==NULL）
return0;
if（item<
bst->
returnDeletBST（bst->
left,item）;
if（item>
right,item）;
if（bst->
left==NULL）
p=bst;
bst=bst->
free（p）;
return1;
elseif（bst->
right==NULL）
if（bst->
left->
bst->
data=bst->
ret
升级会员 