数据结构小实验Word文件下载.docx
《数据结构小实验Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构小实验Word文件下载.docx（53页珍藏版）》请在冰点文库上搜索。
size;
i++）
cout<
<
elem[i]<
"
"
;
cout<
endl;
intmain（）
SqLista;
intsize,data,val;
Pleaseinputthesize:
cin>
>
Pleaseinputthenumber:
i++）
{
cin>
data;
if（!
a.Insert（data））cout<
InsertFail,itisfull!
<
endl;
}
PleaseinputthenumberyouwanttoInsert:
val;
if（!
a.Insert（val））cout<
Nowthenumberisasfollow:
a.Show（）;
return0;
第2题
//已知单链表L中的结点是按值非递减有序排列的，试编写一算法将值为X的结点插入到表L中，使得L仍然有序。
typedefintT;
structLNode
Tdata;
LNode*next;
LNode（constT&
d=0,LNode*n=NULL）:
data（d）,next（n）{};
classLinkList
LNode*head;
LinkList（）;
~LinkList（）;
voidInsert（Tx）;
LinkList:
LinkList（）
LNode*q;
Tx;
head=NULL;
Pleaseinputthedatafromhightolow（exitin0）:
while（cin>
x&
x!
=0）
q=newLNode（x）;
q->
next=head;
head=q;
~LinkList（）
LNode*p;
while（head!
=NULL）
p=head;
head=head->
next;
deletep;
voidLinkList:
Show（）
LNode*p=head;
while（p!
cout<
p->
data<
p=p->
Insert（Tx）
LNode*p=head,*q;
if（p!
=NULL&
data>
x）
next=head;
return;
while（p->
next&
next->
data<
next;
q=newLNode（x）;
q->
next=p->
p->
next=q;
Ta;
charflag='
y'
LinkListA;
Thelinlistisasfollows:
A.Show（）;
while（flag=='
||flag=='
Y'
）
PleaseinputthedatayouwanttoInsert:
cin>
a;
A.Insert（a）;
A.Show（）;
Continue\?
（yorn）"
flag;
第3题
//用单链表作存储结构，编写一个实现线性表中元素逆置的算法。
structLNode
LNode*next;
LNode*Create（）
intx;
LNode*head,*tail,*p;
head=tail=NULL;
Pleaseinputthedata（exitin0）:
p=newLNode（x,NULL）;
if（head==NULL）head=tail=p;
else
{
tail->
next=p;
tail=tail->
}
returnhead;
LNode*Reverse（LNode*head）
LNode*p,*q;
p=head;
q=p;
voidShow（LNode*head）
LNode*p=head;
while（p!
;
LNode*h;
charflag;
flag='
h=Create（）;
h=Reverse（h）;
Reverseasfollow:
Show（h）;
Continue（yorn）:
第4题
//已知一个单链表中的数据元素含有三类字符（即字母字符，数字字符和其它字符）
//试编写算法，构造三个循环链表，使每个循环链表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间。
typedefcharT;
d='
'
LNode*n=NULL）:
voidShow（LNode*）;
voidClassify（LNode*&
LNode*&
）;
voidDest（LNode*）;
Pleaseinputthedata（exitin'
0'
）:
head=newLNode（）;
='
p->
Dest（LNode*H）
LNode*p=H;
next!
=H）
LNode*q=p;
deleteq;
Show（LNode*H）
LNode*p=H->
=H）
Classify（LNode*&
A,LNode*&
B,LNode*&
C）
LNode*s,*p,*q,*r;
s=head->
A=newLNode（）;
p=A;
B=newLNode（）;
q=B;
C=newLNode（）;
r=C;
while（s!
if（s->
data>
s->
9'
）
p->
next=s;
p=p->
else
if（s->
a'
z'
||s->
A'
Z'
{
q->
q=q->
}
else
r->
r=r->
s=s->
next=A;
q->
next=B;
r->
next=C;
||flag=='
LinkLista;
LNode*aa=NULL,*bb=NULL,*cc=NULL;
a.Classify（aa,bb,cc）;
Thenumberis:
a.Show（aa）;
Thecharis:
a.Show（bb）;
Theothersis:
a.Show（cc）;
a.Dest（aa）;
a.Dest（bb）;
a.Dest（cc）;
（yorn）:
第5题
//试编写一个算法，找出一个循环链表中的最小值。
classDlList
LNode*head;
DlList（）;
~DlList（）;
TMin（）;
DlList:
DlList（）
Pleaseinputthedata（exitin0）:
q=newLNode（）;
data=x;
p=q;
~DlList（）
=head）
LNode*q=p;
voidDlList:
LNode*p=head->
TDlList:
Min（）
TMin,temp;
=NULL）
Min=p->
data;
if（p->
Min）
temp=Min;
Min=p->
data=temp;
returnMin;
DlListA;
TheDlListisasfollows:
TheMindatais:
A.Min（）<
第三章
/*将一个十进制N转换为一个d（二~九）进制的数，其解决方法很多,其中一个简单算法基于下列原理:
N=（n/d）*d+n%d
例如d=8时，（1348）10=（2504）8，其运算过程如下：
nn/8n%8
13481684
168210
2125
202
要求：
输入一个十进制数N和对应的转换进制d，在屏幕上输出转换结果。
如，输入N=1348d=8则结果为2504*/
stack>
voidtrans（intN,intd）
stack<
char>
S;
intnum=N;
while（N）
chartemp=N%d;
num=（temp<
10）?
（temp+'
-10）;
S.push（num）;
N/=d;
while（!
S.empty（））
S.top（）;
S.pop（）;
intnumber,d;
PleaseinputN="
number）
Pleaseinputd="
d;
AftertransformN="
if（number<
0）
cout<
-"
trans（-number,d）;
elsetrans（number,d）;
第六章
第1题/*以二叉链表作存储结构，编写一个算法将二叉树左、右子树进行交换的算法。
*/
classBNode
friendclassBTree;
intdata;
BNode*lchild,*rchild;
BNode（constint&
d=0,BNode*l=NULL,BNode*r=NULL）:
data（d）,lchild（l）,rchild（r）{};
classBTree
private:
BNode*Create（）;
voidExchange（BNode*&
p）;
voidShow（BNode*p,intl）;
protected:
BNode*root;
BTree（）{root=Create（）;
};
voidExchange（）;
BNode*BTree:
Create（）
BNode*p;
intch;
ch;
if（ch==-1）returnNULL;
else
p=newBNode（ch）;
lchild=Create（）;
rchild=Create（）;
returnp;
voidBTree:
Exchange（）
Exchange（root）;
Exchange（BNode*&
p）
BNode*q;
q=p->
lchild;
lchild=p->
rchild;
rchild=q;
Exchange（p->
lchild）;
rchild）;
Show（root,1）;
Show（BNode*p,intl）
Show（p->
rchild,l+1）;
for（inti=0;
6*（l-1）;
i++）cout<
..."
lchild,l+1）;
PleaseinputthedatasofBTreeinpreorder（'
-1'
representNULL）:
BTreeb1;
BeforeExchange:
b1.Show（）;
endl<
AfterExchange:
b1.Exchange（）;
/*一棵具有n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行前序遍历。
voidPreorder（inta[],intn）
int>
s;
inti=1;
s.push（a[i-1]）;
s.empty（））
i=s.top（）;
a[i-1]<
s.pop（）;
if（2*i+1<
=n）s.push（a[2*i]）;
if（2*i<
=n）s.push（a[2*i-1]）;
}
intmain（）
inta[7]={1,2,3,4,5,6,7};
Layerorder:
for（intj=0;
j<
7;
j++）
a[j]<
Preorder:
Preorder（a,7）;
/*试编写算法判别两棵二叉树是否等价。
如果T1和T2都是空二叉树，
或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的；
T1的右子树与T2的右子树是等价的。
classBNode
classBTree
BNode*Create（）;
boolEqual（BNode*p,BNode*q）;
boolEqual（BTree&
boolBTree:
Equal（BTree&
p）
return（Equal（root,p.root））;
Equal（BNode*p,BNode*q）
升级会员 