数据结构小实验.docx

数据结构小实验.docx

《数据结构小实验.docx》由会员分享，可在线阅读，更多相关《数据结构小实验.docx（53页珍藏版）》请在冰点文库上搜索。

数据结构小实验

第二章

第一题

//设线性表存储在数组A[1..arrsize]的前elenum个分量中，且递增有序。

//试编写一个算法：

将x插入到线性表的适当位置上以保持线性表的有序性，并且分析算法的时间复杂度。

#include

#defineLEN100

usingnamespacestd;

classSqList

{

int*elem;

intsize;

public:

SqList（）;

intInsert（intx）;

voidShow（）;

};

SqList:

:

SqList（）

{

size=0;

elem=newint[LEN];

}

intSqList:

:

Insert（intx）

{

inti;

if（size>=LEN）return0;

for（i=size-1;i>=0&&elem[i]>=x;i--）elem[i+1]=elem[i];

elem[i+1]=x;

size++;

return1;

}

voidSqList:

:

Show（）

{

for（inti=0;i

cout<

cout<

}

intmain（）

{

SqLista;

intsize,data,val;

cout<<"Pleaseinputthesize:

";

cin>>size;

cout<<"Pleaseinputthenumber:

";

for（inti=0;i

{

cin>>data;

if（!

a.Insert（data））cout<<"InsertFail,itisfull!

"<

}

cout<<"PleaseinputthenumberyouwanttoInsert:

";

cin>>val;

if（!

a.Insert（val））cout<<"InsertFail,itisfull!

"<

cout<<"Nowthenumberisasfollow:

";

a.Show（）;

return0;

}

第2题

//已知单链表L中的结点是按值非递减有序排列的，试编写一算法将值为X的结点插入到表L中，使得L仍然有序。

#include

usingnamespacestd;

typedefintT;

structLNode

{

Tdata;

LNode*next;

LNode（constT&d=0,LNode*n=NULL）:

data（d）,next（n）{};

};

classLinkList

{

LNode*head;

public:

LinkList（）;

~LinkList（）;

voidShow（）;

voidInsert（Tx）;

};

LinkList:

:

LinkList（）

{

LNode*q;

Tx;

head=NULL;

cout<<"Pleaseinputthedatafromhightolow（exitin0）:

"<

while（cin>>x&&x!

=0）

{

q=newLNode（x）;

q->next=head;

head=q;

}

}

LinkList:

:

~LinkList（）

{

LNode*p;

while（head!

=NULL）

{

p=head;

head=head->next;

deletep;

}

}

voidLinkList:

:

Show（）

{

LNode*p=head;

while（p!

=NULL）

{

cout<data<<"";

p=p->next;

}

cout<

}

voidLinkList:

:

Insert（Tx）

{

LNode*p=head,*q;

if（p!

=NULL&&p->data>x）

{

q=newLNode（x）;

q->next=head;

head=q;

return;

}

while（p->next&&p->next->data

p=p->next;

q=newLNode（x）;

q->next=p->next;

p->next=q;

}

intmain（）

{

Ta;

charflag='y';

LinkListA;

cout<<"Thelinlistisasfollows:

";

A.Show（）;

while（flag=='y'||flag=='Y'）

{

cout<<"PleaseinputthedatayouwanttoInsert:

";

cin>>a;

A.Insert（a）;

cout<<"Thelinlistisasfollows:

";

A.Show（）;

cout<<"Continue\?

（yorn）";

cin>>flag;

}

return0;

}

第3题

//用单链表作存储结构，编写一个实现线性表中元素逆置的算法。

#include

usingnamespacestd;

typedefintT;

structLNode

{

Tdata;

LNode*next;

LNode（constT&d=0,LNode*n=NULL）:

data（d）,next（n）{};

};

LNode*Create（）

{

intx;

LNode*head,*tail,*p;

head=tail=NULL;

cout<<"Pleaseinputthedata（exitin0）:

";

while（cin>>x&&x!

=0）

{

p=newLNode（x,NULL）;

if（head==NULL）head=tail=p;

else

{

tail->next=p;

tail=tail->next;

}

}

returnhead;

}

LNode*Reverse（LNode*head）

{

LNode*p,*q;

p=head;

head=NULL;

while（p!

=NULL）

{

q=p;

p=p->next;

q->next=head;

head=q;

}

returnhead;

}

voidShow（LNode*head）

{

LNode*p=head;

while（p!

=NULL）

{

cout<data<<"";

p=p->next;

}

cout<

}

intmain（）

{

LNode*h;

charflag;

flag='y';

while（flag=='y'||flag=='Y'）

{

h=Create（）;

h=Reverse（h）;

cout<<"Reverseasfollow:

";

Show（h）;

cout<<"Continue（yorn）:

";

cin>>flag;

}

return0;

}

第4题

//已知一个单链表中的数据元素含有三类字符（即字母字符，数字字符和其它字符）

//试编写算法，构造三个循环链表，使每个循环链表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间。

#include

usingnamespacestd;

typedefcharT;

structLNode

{

Tdata;

LNode*next;

LNode（constT&d='',LNode*n=NULL）:

data（d）,next（n）{};

};

classLinkList

{

LNode*head;

public:

LinkList（）;

voidShow（LNode*）;

voidClassify（LNode*&,LNode*&,LNode*&）;

voidDest（LNode*）;

};

LinkList:

:

LinkList（）

{

cout<<"Pleaseinputthedata（exitin'0'）:

";

Tx;

head=newLNode（）;

LNode*p=head,*q;

while（cin>>x&&x!

='0'）

{

q=newLNode（x）;

p->next=q;

p=p->next;

}

}

voidLinkList:

:

Dest（LNode*H）

{

LNode*p=H;

while（p->next!

=H）

{

LNode*q=p;

p=p->next;

deleteq;

}

}

voidLinkList:

:

Show（LNode*H）

{

LNode*p=H->next;

while（p!

=H）

{

cout<data<<"";

p=p->next;

}

cout<

}

voidLinkList:

:

Classify（LNode*&A,LNode*&B,LNode*&C）

{

LNode*s,*p,*q,*r;

s=head->next;

A=newLNode（）;p=A;

B=newLNode（）;q=B;

C=newLNode（）;r=C;

while（s!

=NULL）

{

if（s->data>='0'&&s->data<='9'）

{

p->next=s;p=p->next;

}

else

if（s->data>='a'&&s->data<='z'||s->data>='A'&&s->data<='Z'）

{

q->next=s;q=q->next;

}

else

{

r->next=s;r=r->next;

}

s=s->next;

}

p->next=A;q->next=B;r->next=C;

}

intmain（）

{

charflag;

flag='y';

while（flag=='y'||flag=='Y'）

{

LinkLista;

LNode*aa=NULL,*bb=NULL,*cc=NULL;

a.Classify（aa,bb,cc）;

cout<<"Thenumberis:

";

a.Show（aa）;

cout<<"Thecharis:

";

a.Show（bb）;

cout<<"Theothersis:

";

a.Show（cc）;

a.Dest（aa）;a.Dest（bb）;a.Dest（cc）;

cout<

cout<<"Continue\?

（yorn）:

";

cin>>flag;

}

return0;

}

第5题

//试编写一个算法，找出一个循环链表中的最小值。

#include

usingnamespacestd;

typedefintT;

structLNode

{

Tdata;

LNode*next;

LNode（constT&d=0,LNode*n=NULL）:

data（d）,next（n）{};

};

classDlList

{

LNode*head;

public:

DlList（）;

~DlList（）;

voidShow（）;

TMin（）;

};

DlList:

:

DlList（）

{

Tx;

head=newLNode（）;

LNode*p=head,*q;

cout<<"Pleaseinputthedata（exitin0）:

";

while（cin>>x&&x!

=0）

{

q=newLNode（）;

q->data=x;

p->next=q;

p=q;

}

p->next=head;

}

DlList:

:

~DlList（）

{

LNode*p=head;

while（p->next!

=head）

{

LNode*q=p;

p=p->next;

deleteq;

}

}

voidDlList:

:

Show（）

{

LNode*p=head->next;

while（p!

=head）

{

cout<data<<"";

p=p->next;

}

cout<

}

TDlList:

:

Min（）

{

TMin,temp;

LNode*p=head->next;

if（p!

=NULL）

{

Min=p->data;

p=p->next;

}

while（p!

=head）

{

if（p->data

{

temp=Min;

Min=p->data;

p->data=temp;

}

p=p->next;

}

returnMin;

}

intmain（）

{

charflag;

flag='y';

while（flag=='y'||flag=='Y'）

{

DlListA;

cout<<"TheDlListisasfollows:

";

A.Show（）;

cout<<"TheMindatais:

"<

cout<<"Continue\?

（yorn）:

";

cin>>flag;

}

return0;

}

第三章

/*将一个十进制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*/

#include

#include

usingnamespacestd;

voidtrans（intN,intd）

{

stackS;

intnum=N;

while（N）

{

chartemp=N%d;

num=（temp<10）?

（temp+'0'）:

（temp+'A'-10）;

S.push（num）;

N/=d;

}

while（!

S.empty（））

{

cout<

S.pop（）;

}

cout<

}

intmain（）

{

intnumber,d;

cout<<"PleaseinputN=";

while（cin>>number）

{

cout<<"Pleaseinputd=";

cin>>d;

cout<<"AftertransformN=";

if（number<0）

{

cout<<"-";

trans（-number,d）;

}

elsetrans（number,d）;

cout<<"PleaseinputN=";

}

return0;

}

第六章

第1题/*以二叉链表作存储结构，编写一个算法将二叉树左、右子树进行交换的算法。

*/

#include

usingnamespacestd;

classBNode

{

friendclassBTree;

intdata;

BNode*lchild,*rchild;

public:

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;

public:

BTree（）{root=Create（）;};

voidExchange（）;

voidShow（）;

};

BNode*BTree:

:

Create（）

{

BNode*p;

intch;

cin>>ch;

if（ch==-1）returnNULL;

else

{

p=newBNode（ch）;

p->lchild=Create（）;

p->rchild=Create（）;

returnp;

}

}

voidBTree:

:

Exchange（）

{

Exchange（root）;

}

voidBTree:

:

Exchange（BNode*&p）

{

BNode*q;

if（p!

=NULL）

{

q=p->lchild;p->lchild=p->rchild;p->rchild=q;

Exchange（p->lchild）;

Exchange（p->rchild）;

}

}

voidBTree:

:

Show（）

{

Show（root,1）;

}

voidBTree:

:

Show（BNode*p,intl）

{

if（p!

=NULL）

{

Show（p->rchild,l+1）;

for（inti=0;i<6*（l-1）;i++）cout<<"";

cout<<"..."<data<

Show（p->lchild,l+1）;

}

}

intmain（）

{

cout<<"PleaseinputthedatasofBTreeinpreorder（'-1'representNULL）:

"<

BTreeb1;

cout<<"BeforeExchange:

"<

b1.Show（）;

cout<

cout<<"AfterExchange:

"<

b1.Exchange（）;

b1.Show（）;

return0;

}

第2题

/*一棵具有n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行前序遍历。

*/

#include

#include

usingnamespacestd;

voidPreorder（inta[],intn）

{

stacks;

inti=1;

s.push（a[i-1]）;

while（!

s.empty（））

{

i=s.top（）;

cout<

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};

cout<<"Layerorder:

"<

for（intj=0;j<7;j++）

cout<

cout<

cout<<"Preorder:

"<

Preorder（a,7）;

cout<

return0;

}

第3题

/*试编写算法判别两棵二叉树是否等价。

如果T1和T2都是空二叉树，

或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的；T1的右子树与T2的右子树是等价的。

*/

#include

usingnamespacestd;

classBNode

{

friendclassBTree;

intdata;

BNode*lchild,*rchild;

public:

BNode（constint&d=0,BNode*l=NULL,BNode*r=NULL）:

data（d）,lchild（l）,rchild（r）{};

};

classBTree

{

private:

BNode*Create（）;

boolEqual（BNode*p,BNode*q）;

protected:

BNode*root;

public:

BTree（）{root=Create（）;};

boolEqual（BTree&p）;

};

BNode*BTree:

:

Create（）

{

BNode*p;

intch;

cin>>ch;

if（ch==-1）returnNULL;

else

{

p=newBNode（ch）;

p->lchild=Create（）;

p->rchild=Create（）;

returnp;

}

}

boolBTree:

:

Equal（BTree&p）

{

return（Equal（root,p.root））;

}

boolBTree:

:

Equal（BNode*p,BNode*q）