举例Word下载.docx
《举例Word下载.docx》由会员分享，可在线阅读，更多相关《举例Word下载.docx（39页珍藏版）》请在冰点文库上搜索。
三十三、在二叉树的二叉链表中增设一个指向父母结点的指针和一个标志位（初值为0），其取值范围为0、1、2，不使用堆栈也不用递归，后序遍历该二叉树，试给出算法：
22
三十四、在二叉树的二叉链表中增设一个标志位（初值为0），其取值范围为0、1、2，不使用堆栈也不用递归，后序遍历该二叉树，试给出算法：
三十五、试给出算法判断一棵树是否为二叉排序树：
23
三十六、试给出算法判断一棵树是否为平衡二叉树：
24
三十七、已知待排序列用单链表表示，试给出直接插入排序算法：
三十八、已知待排序列用单链表表示，试给出快速排序算法：
25
三十九、n=7,e=1026
四十、编程实现将以孩子-兄弟链表示的树用广义表的形式输出：
27
四十一、求集合的幂集28
四十二、在二叉链表中增加一个子孙数目域Cnum，计算各结点的子孙数目:
29
四十三、将用孩子兄弟链表示的树按以下格式输出：
30
四十四、约瑟夫问题33
四十五、中缀表达式变后缀表达式33
四十六、字符分类：
三种字符重排为字母、数字和其它字符33
四十七、已知二叉链表表示的二叉树结点数据类型为大写字母，从键盘输入前序遍历序列（无孩子用字符0表示），建立该二叉树。
34
四十八、二叉排序树的查找。
35
一、使用第二种存储结构求广义表的深度
intGListDepth（GListL）
{
if（!
L）return0;
if（L->
tag==ATOM）return0;
for（max=0,pp=L->
hp;
pp;
pp=pp->
tp）
dep=GListDepth（pp）;
if（dep>
max）max=dep;
}
returnmax+1;
二、使用第二种存储结构复制广义表
StatusCopyGList（GList&
T,GListL）
L）T=NULL;
else
if（!
（T=newGLNode））exit（OVERFLOW）;
T->
tag=L->
tag;
if（l->
tag==ATOM）T->
atom=L->
atom;
elseCopyGList（T->
hp,L->
hp）;
CopyGList（T->
tp,L->
tp）;
三、使用第二种存储结构建立广义表
StatusCreateGList（GList&
L,SStringS）
if（StrEmpty（S））L=NULL;
（L=newGLNode））exit（OVERFLOW）;
if（StrLength（S）==1）
{
L->
tag=ATOM;
atom=S;
}else
tag=LIST;
SubString（sub,S,2,StrLength（S）-2）;
sever（sub,hsub）;
CreateGList（L->
hp,hsub）;
p=L->
hp;
while（!
StrEmpty（sub））
CreateGList（p->
tp,hsub）;
p=p->
tp;
}
tp=NULL;
四、已知单链表的数据域为整型，试将其分解为奇数和偶数两个单链表
voidsep（linkedlistL,linkedlist&
A,linkedlist&
B）
A=B=NULL;
while（L）
H=L;
L=L->
next;
if（H->
data%2）
H->
next=A;
A=H;
next=B;
B=H;
五、将不带头结点的单链表置逆
linkedlistrever（linkedlistL）
H=NULL;
P=L;
P->
next=H;
H=P;
returnH;
六、求两个集合的交集
linkedlistintersection（linkedlist&
La,linkedlist&
Lb）
pa=La->
pb=Lb->
Lc=pc=newlnode;
while（pa&
&
pb）
if（pa->
data>
pb->
data）pb=pb->
data<
data）pa=pa->
ltemp=newlnode;
ltemp->
data=pa->
data;
pc->
next=ltemp;
pc=ltemp;
pa=pa->
pb=pb->
pc->
next=NULL;
returnLc
voidinsert（sqlist&
L,inti,elemtypee）
for（j=L.listsize;
j>
i;
j--）L.elem[j+1]=L.elem[j];
L.elem[i+1]=e;
L.listsize++;
intinsert（sqlist&
if（L.listsize==L.MAXLEN）return1;
for（j=L.listsize;
return0;
voidoutput（linkedlistL）
while（L）
cout<
<
L->
‘’;
endl;
voidadd（linkedlistA,linkedlistB,linkedlist&
C）
p=C=newstructlnode;
while（A&
B）
if（A->
exp>
B->
exp）
p->
next=newstructlnode;
p=p->
coef=A->
coef;
exp=A->
exp;
A=A->
exp<
coef=B->
exp=B->
B=B->
co=A->
coef+B->
if（co）
coef=co;
while（A）
while（B）
p=C;
C=C->
deletep;
linkedlistcreate（intn）
linkedlisthead,p1,p2;
head=NULL;
for（;
n;
n--）
p1=（linkedlist）malloc（sizeof（lnode））;
head）head=p1;
elsep2->
next=p1;
cin>
>
p1->
p2=p1;
p2->
return（head）;
{
linkedlisthead,p;
p=newstructlnode;
p->
next=head;
head=p;
returnhead;
voidPush（linkedstack&
top,elemtypee）
linkedstackp=newstructlnode;
data=e;
next=top;
top=p;
voidPop（linkedstack&
top,elemtype&
e）
linkedstackp=top；
e=p->
top=p->
deletep;
voidPush（sqstacks,int&
s[top++]=e;
voidPop（sqstacks,int&
e=s[--top];
listCopylist（listA）
{H=r=newnode;
p=A->
while（p）
{r->
next=newnode;
r=r->
r->
coef=p->
r->
exp=p->
p=p->
next=NULL;
returnH;
或
if（!
A）returnNULL;
p=newlnode;
coef=A->
exp=A->
next=Copylist（A->
next）;
returnp;
p=A;
r=H；
H=H->
Deleter;
{H=NULL;
{r=newnode;
if（!
H）H=r;
elseq->
next=r;
q=r;
If（!
H=newnode;
voidPolyMul（listA,listB,list&
C=newnode;
C->
q=B->
while（q）
p=Copylist（A）;
r=p->
while（r）
r->
exp+=q->
coef*=q->
r=r->
AddPloyn（C,p）;
q=q->
voidCopytree（bitptrt,bitptr&
nt）
t）nt=NULL;
nt=newnode;
nt->
data=t->
Copytree（t->
lc,nt->
lc）;
rc,nt->
rc）;
intSum（bitptrt）
t）return0;
returnt->
data+Sum（t->
lc）+Sum（t->
voidporder（bitptrt,bitptr&
mt）
if（t）
if（t->
mt->
data）mt=t;
porder（t->
lchild,mt）;
rchild,mt）;
voidmax（bitptrt,bitprt&
maxt）
//bitptrmax（bitptrt）
maxt=t;
porder（t,maxt）;
//returnmaxt;
voidvisit（bitptrt,int&
m,int&
n）
0）m+=t->
n+=t->
visit（t->
lc,m,n）;
rc,m,n）;
intMul（bitptrt）
m=n=0;
visit（t,m,n）;
returnm*n;
voidOutTree（bitptrt,intn）//n的初值为1
if（t）
n<
’:
’<
t->
’’;
OutTree（t->
lc,n+1）;
rc,n+1）;
voidhigh（bitptrt,intlevel,int&
hi）
//level初值为1，hi初值为0
if（level>
hi）hi=level;
high（t->
lchild,level+1,hi）;
rchild,level+1,hi）;
voidGetHigh（bitptrt,intn,int&
high,arp,ar&
path）
//n的初值为1,high的初值为0
if（t）{
p[n]=t->
if（high<
n）{
high=n;
for（i=1;
i<
=n;
i++）path[i]=p[i];
GetHigh（t->
lc,n+1,high,p,path）;
rc,n+1,high,p,path）;
intGetHigh（bitptrt）
returnMax（GetHigh（t->
lc）,GetHigh（t->
rc））+1
lc&
!
rc）returnt->
returnSum（t->
intsimilartree（bitptrt1,bitptrt2）
t1&
!
t2）return1;
if（t1&
t2||!
t1&
t2）return0;
returnsimilartree（t1->
lc,t2->
lc）&
similartree（t1->
rc,t2->
intequaltree（bitptrt1,bitptrt2）
return（t1->
data==t2->
data）&
equaltree（t1->
equaltree（t1->
bitptrForefather（bitptrt,bitptrp,bitptrq）
Fft=NULL;
Fpost（t,p,q,Fft）;
returnFft;
intFpost（bitptrt,bitptrq,bitptrq,bitptr&
Fft）
t||Fft）return0;
d=Fpost（t->
lc,p,q,Fft）+Fpost（t->
rc,p,q,Fft）;
if（d==2）if（!
Fft）Fft=t;
if（t==p||t==q）returnd+1;
elsereturnd;
intComptree（bitptrt）
Init（Q）;
if（t）Enqueue（Q,t）;
f=0;
while（!
Empty（Q））
p=Dequeue（Q）;
f）if（p->
lc）Enqueue（Q,p->
elsef=1;
elseif（p->
lc）return0;
rc）Enqueue（Q,p->
rc）return0;
return1;
if（t）Enqueue（Q,（t,1））;
（p,m）=Dequeue（Q）;
n++;
if（p->
lc）Enqueue（Q,（p->
lc,m*2））;
rc）Enqueue（Q,（p->
rc,m*2+1））;
if（m==n）return1;
elsereturn0;
voidbst1（bitptrt,bitptrp,int&
isbst）
if（t&
isbst）
bst1（t->
lc,p,isbst）;
if（p）if（p->
data>
t->
data）isbst=0;
p=t;
rc,p,isbst）;
intbst（bitptrt）
p=NULL;
isbst=1;
bst1（t,p,isbst）;
returnisbst;
voidReverse（linkedlist&
H）
q=NULL;
while（H）
p=H;
next=q;
q=p;
H=p;
}
p=H->
next=H->
pre;
pre=p;
p=H;
升级会员 