关闭

关闭

关闭

封号提示

内容

首页 数据结构习题集答案(C语言版严蔚详细版敏)(1).doc

数据结构习题集答案(C语言版严蔚详细版敏)(1).doc

数据结构习题集答案(C语言版严蔚详细版敏)(1).doc

上传者: merry爽 2017-09-19 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《数据结构习题集答案(C语言版严蔚详细版敏)(1)doc》,可适用于综合领域,主题内容包含数据结构第章 绪论简述下列术语:数据数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解:数据是对客观事物的符号表示。在计算机科学中是符等。

数据结构第章 绪论简述下列术语:数据数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。  数据元素是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理。  数据对象是性质相同的数据元素的集合是数据的一个子集。  数据结构是相互之间存在一种或多种特定关系的数据元素的集合。  存储结构是数据结构在计算机中的表示。  数据类型是一个值的集合和定义在这个值集上的一组操作的总称。  抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解:抽象数据类型包含一般数据类型的概念但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义直接提供给编程者定义用户数据因此称它们为预定义数据类型。抽象数据类型通常由编程者定义包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时要求只定义到数据的逻辑结构和操作说明不考虑数据的存储结构和操作的具体实现这样抽象层次更高更能为其他用户提供良好的使用接口。设有数据结构(D,R)其中试按图论中图的画法惯例画出其逻辑结构图。解:试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。  解:ADTComplex{    数据对象:D={r,i|r,i为实数}  数据关系:R={<r,i>}    基本操作:      InitComplex(C,re,im)操作结果:构造一个复数C其实部和虚部分别为re和im      DestroyCmoplex(C)操作结果:销毁复数C      Get(C,k,e)        操作结果:用e返回复数C的第k元的值      Put(C,k,e)        操作结果:改变复数C的第k元的值为e      IsAscending(C)        操作结果:如果复数C的两个元素按升序排列则返回否则返回      IsDescending(C)        操作结果:如果复数C的两个元素按降序排列则返回否则返回      Max(C,e)        操作结果:用e返回复数C  else{        在A中插入一个新结点        p=newOLNode        p>row=pb>row        p>col=pb>col        p>e=pb>e        pb=pb>right        if(!pre){          p>right=pa          RHeadi=p        }        else{          p>right=pre          pre>right=p        }        处理列指针        qpre=        q=CHeadp>col        while(qq>row<i){          qpre=q          q=q>down        }        if(!qpre){          p>down=q          CHeadp>col=p        }        else{          p>down=pre          pre>down        }        k      }    }endwhile(pb)  }endfor  mnNum=mnNumk}voidCCrossListMat::ShowMat(){  inti,j  OLinkp  for(i=i<mnRowi){    p=RHeadi    for(j=j<mnColj){      if(pp>row==ip>col==j){        cout<<p>e<<""        p=p>right      }      else        cout<<<<""    }    cout<<endl  }}intmain(){  CCrossListMatA(,,),B(,,)  AAdd(B)  AShowMat()  return}以下是关于广义表算法涉及的描述及方法#include"DSConsth"  常量定义头文件#include"StrStath"  字符串定义头文件广义表数据结构声明typedefcharAtomTypetypedefenum{ATOM,LIST}ElemTagtypedefstructGLNode{  ElemTagtag  union{    AtomTypeatom    structGLNode*hp  }  structGLNode*tp}*GList将非空串Str分割成两部分HStr为第一个TStr为之后的子串intStrDistrict(CStringStr,CStringHStr,CStringTStr){  intn,i,k  CStrings  CStrings(","),s("("),s(")")  定义常量串  n=StrStrLength()  i=  k=  while(i<=nsStrCompare(s)||k!=){    s=StrSubString(i,)    if(!sStrCompare(s))k    elseif(!sStrCompare(s))k    i  }  if(i<=n){    HStr=StrSubString(,i)    TStr=StrSubString(i,ni)  }  else{    HStr=Str    TStrStrClear()  }  returnOK}用串s建立广义表LintCreateGList(GListL,CStrings){            CStringSub,HSub,TSub  子串表头串表尾串  if(sStrEmpty())L=  else{  非空串建立广义表    L=newGLNode  开辟一个结点    if(!L)exit(OVERFLOW)    if(sStrLength()>){  如果串长大于说明是表结点      L>tag=LIST      Sub=sSubString(,sStrLength())  取括号内子串      if(!SubStrEmpty()){  建立子表        StrDistrict(Sub,HSub,TSub)        if(!HSubStrEmpty())  表头不空          CreateGList(L>hp,HSub)        elseL>hp=        if(!TSubStrEmpty())  表尾不空          CreateGList(L>tp,TSub)        elseL>tp=      }      else{  空表        L>hp=        L>tp=      }    }    else{  建立原子结点      L>tag=ATOM      L>atom=sGetStr()      L>tp=    }  }  returnOK}显示广义表串voidShowGList(GListL){  if(L){    if(L>tag==LIST){      cout<<"("      if(L>hp)        ShowGList(L>hp)      if(L>tp){        cout<<","        ShowGList(L>tp)      }      cout<<")"    }    elsecout<<L>atom  }}解:求广义表深度的递归算法intGListDepth(GListL){  intDepth=  intHDepth,TDepth  表头深度表尾深度  if(!L)returnDepth  广义表不存在  if(L>tag==ATOM)returnDepth  原子结点深度为  else{    Depth  表结点深度为    HDepth=DepthGListDepth(L>hp)    TDepth=DepthGListDepth(L>tp)    returnHDepth>TDepthHDepth:TDepth  }}解:由广义表L复制广义表TintCopyGList(GListT,GListL){  if(!L)T=  else{    T=newGLNode    if(!T)exit(OVERFLOW)    T>tag=L>tag    if(L>tag==ATOM)T>atom=L>atom    else{      CopyGList(T>hp,L>hp)      CopyGList(T>tp,L>tp)    }  }  returnOK}解:判两广义表是否相等相等返回OK否则返回FALSEStatusGListCompare(GListL,GListL){  if(!L!L)returnOK  L和L均为空表  if((!LL)||(L!L))returnFALSE  else{  L和L均非空表    if(L>tag==L>tag){  表属性相同      if(L>tag==ATOM){  均为原子结点        if(L>atom==L>atom)returnOK        elsereturnFALSE      }      else{  均为表结点        if(GListCompare(L>hp,L>hp)          GListCompare(L>tp,L>tp))          returnOK  表头、表尾均相同        elsereturnFALSE      }    }    elsereturnFALSE  表属性不同  }}解:章树和二叉树已知一棵树边的集合为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<A,C>}请画出这棵树并回答下列问题:  ()哪个是根结点?  ()哪些是叶子结点?  ()哪个是结点G的双亲?  ()哪些是结点G的祖先?  ()哪些是结点G的孩子?  ()哪些是结点E的子孙?  ()那些是结点E的子孙?  ()结点B和N的层次号分别是什么?  ()树的深度是多少?  ()以结点C为根的子树的深度是多少?一棵度为的树与一棵二叉树有何区别?解:二叉树是颗有序树但度为的树则未必有序。试分别画出具有个结点的树和个结点的二叉树的所有不同形态。一棵深度为H的满k叉树有如下性质:第H层上的结点都是叶子结点其余各层上每个结点都有k棵非空子树。如果按层次顺序从开始对全部结点编号问:  ()各层的结点数目是多少?  ()编号为p的结点的父结点(若存在)的编号是多少?  ()编号为p的结点的第i个儿子结点(若存在)的编号是多少?  ()编号为p的结点有右兄弟的条件是什么?其右兄弟的编号是多少?解:()()如果p是其双亲的最小的孩子(右孩子)则p减去根结点的一个结点应是k的整数倍该整数即为所在的组数每一组为一棵满k叉树正好应为双亲结点的编号。如果p是其双亲的最大的孩子(左孩子)则pk为其最小的弟弟再减去一个根结点除以k即为其双亲结点的编号。综合来说对于p是左孩子的情况i=(pk)k对于p是右孩子的情况i=(p)k如果左孩子的编号为p则其右孩子编号必为pk所以其双亲结点的编号为     向下取整如向下取整为  ()结点p的右孩子的编号为kp左孩子的编号为kpk=k(p)第i个孩子的编号为k(p)i=kpki。  ()当(p)k!=时结点p有右兄弟其右兄弟的编号为p。已知一棵度为k的树中有个度为的结点个度为的结点…个度为k的结点问该树中有多少个叶子结点?解:根据树的定义在一颗树中除树根结点外每个结点有且仅有一个前驱结点也就是说每个结点与指向它的一个分支一一对应所以除树根结点之外的结点树等于所有结点的分支数即度数从而可得树中的结点数等于所有结点的度数加。总结点数为而度为的结点数就应为总结点数减去度不为的结点数的总和即已知在一棵含有n个结点的树中只有度为k的分支结点和度为的叶子结点。试求该树含有的叶子节点数目。解:利用上题结论易得结果。设度为k的结点个数为则总结点数为。叶子结点的数目应等于总结点数减去度不为的结点的数目即  一棵含有n个结点的k叉树可能达到的最大深度和最小深度各为多少?解:能达到最大深度的树是单支树其深度为n。满k叉树的深度最小其深度为      (证明见徐孝凯著数据结构实用教程P)证明:一棵满k叉树上的叶子结点数和非叶子结点数之间满足以下关系:      解:一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为其总结点数为则非叶子结点数从而得    试分别推导含有n个结点和含个叶子结点的完全三叉树的深度H。解:()根据完全三叉树的定义                      ()设总的结点数为n非叶子结点数为注意到每个非叶子结点的度均为则        由      对于那些所有非叶子结点均含有左右子数的二叉树:  ()试问:有n个叶子结点的树中共有多少个结点?  ()试证明:其中n为叶子结点的个数表示第i个叶子结点所在的层次(设根节点所在层次为)。解:()总结点数为其中为非叶子结点数则叶子结点数为所以总结点数为。  ()用归纳法证明。  i=说明二叉树只有一个叶子结点则整棵树只有一个根结点,    结论成立。  设有n个叶子结点时也成立即现假设增加一个叶子结点这意味着在某叶子结点p上新生两个叶子结点而结点p则成为非叶子结点可见总结点数增叶子结点数增。此时所有叶子结点是原结点除去p然后加上两个深度为的新叶子结点由此  则当i=n时也成立由此即得到证明。在二叉树的顺序存储结构中实际上隐含着双亲的信息因此可和三叉链表对应。假设每个指针域占个字节每个信息域占k个字节。试问:对于一棵有n个结点的二叉树且在顺序存储结构中最后一个节点的下标为m在什么条件下顺序存储结构比三叉链表更节省空间?解:采用三叉链表结构需要n(k)个字节的存储空间。采用顺序存储结构需要mk个字节的存储空间则当mk<n(k)时即时采用顺序存储比采用三叉链表更节省空间。对题所得各种形态的二叉树分别写出前序、中序和后序遍历的序列。假设n和m为二叉树中两结点用、或#(分别表示肯定、恰恰相反或不一定)填写下表:  问已知前序遍历时n在m前?中序遍历时n在m前?后序遍历时n在m前?n在m左方   n在m右左方   n是m祖先   n是m子孙     注:如果()离a和b最近的共同祖先p存在且()a在p的左子树中b在p的右子树中则称a在b的左方(即b在a的右方)。找出所有满足下列条件的二叉树:  (a)它们在先序遍历和中序遍历时得到的节点访问序列相同  (b)它们在后序遍历和中序遍历时得到的结点访问序列相同  (c)它们在先序遍历和后序遍历时得到的节点访问序列相同。解:(a)不含左子树的二叉树。  (b)不含右子树的二叉树。  (c)即不含左子树也不含右子树的二叉树。  解:解:                       InfoABCDEFGHIJKLMNLtagLchildRtagRchild解:其错误在于中序遍历应先访问其左子树可做如下修改:BiTreeInSucc(BiTreeq){  一直q是指向中序线索二叉树上某个结点的指针  本函数返回指向*q的后继的指针。  r=q>rchild  if(!r>ltag)    while(!r>ltag)r=r>lchild  returnr}InSucc解:如果p是根结点则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历如果某结点的左指针域等于p说明该结点是p的双亲结点且p是它的左孩子如果某结点的右指针域等于p说明该结点是p的双亲结点且p是它的右孩子如此即可确定访问次序。若是右孩子其后继是双亲结点若是左孩子其后继是其兄弟最左下的子孙如果兄弟不存在其后继是其双亲结点。分别画出和下列树对应的各个二叉树:解:解:  ()先序:  ()中序:  ()后序:解:树的先根序列为GFKDAIEBCHJ后根序列为DIAEKFCJHBG可以先转化成二叉树再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同二叉树的中序序列对应着树的后根序列。GFKDAIEBCHJ为所求二叉树的先序序列DIAEKFCJHBG为二叉树的中序序列。通过观察先序序列G为二叉树的根结点再由中序序列G的左子树序列为DIAEKFCJHB右子为空。可以表示成如下形式:G(DIAEKFCJHB)对于子树先序序列为FKDAIEBCHJ中序序列为DIAEKFCJHB显然子树根为F。再由中序序列可以看到F的左子树是DIAEK右子树为CJHB。进一步表示成:  G(F(DIAEK,CJHB),)对于DIAEK(中序表示)先序为KDAIEK为根左子为DIAE右子为空对于CJHBB为根左子为CJH右子为空。进一步表示成:  G(F(K(DIAE,),B(CJH,)),)  G(F(K(D(,IAE),),B(C(,JH),)),)  G(F(K(D(,A(I,E)),),B(C(,H(J,)),)),)由此画出二叉树进而画出树。      解:本题应注意下列转换:  树      森林      二叉树  先根    先序      先序  后根    中序      中序  解用归纳法证明。当n=时要使其成为最优二叉树必须使两个结点都成为叶子结点。设n=k时成立则当n=k时要使其成为最优必须用k个结点的哈夫曼树与第k个结点组成一个新的最优二叉树所以n=k时也成立。解:不妨设这个结点为A、B、C、D、E、F、G、H其相应的权为、、、、、、、。A: B: C: D: E: F: G: H:  采用这种方式编码电文最短。解:解:intVisit(intu,intv){  if(u==v)return  if(Lv==){左子树不存在    if(Rv==)右子树也不存在      return    else{右子树存在继续访问右子树      if(Visit(u,Rv))return      elsereturn    }  }  else{左子树存在    if(Visit(u,Lv))左子树中存在目标      return    else{左子树中没有目标需访问右子树      if(Rv==)没有右子树        return      else{右子树存在继续访问右子树        if(Visit(u,Rv))return        elsereturn      }    }  }}解:intVisit(intu,intv){  intNv  Nv=NumElem(v)返回结点v的下标  if(Nv==)exit()结点v不存在退出  if(u==v)return  if(LNv==){左子树不存在    if(RNv==)右子树也不存在      return    else{右子树存在继续访问右子树      if(Visit(u,RNv))return      elsereturn    }  }  else{左子树存在    if(Visit(u,LNv))左子树中存在目标      return    else{左子树中没有目标需访问右子树      if(RNv==)没有右子树        return      else{右子树存在继续访问右子树        if(Visit(u,RNv))return        elsereturn      }    }  }}返回结点在数组T中的下标intNumElem(intx){  inti=  while(i<NTi!=x)i  if(Ti==x)returni  elsereturn}解:#defineNcharTN={'','a','b','c','d','e','f','g'}用顺序数组存储为头结点a为根结点b为左子树c为右子树若某结点编号为奇数则它必为其双亲的右孩子否则为左孩子编号为k的结点的双亲结点的编号为kintNumTree(charc)求结点在树中的编号intExp(inta,intb)求a的b次方intNumElem(charc)返回元素在数组中的下标intmain(){  charc  cout<<"请输入结点的值:"  cin>>c  cout<<NumTree(c)<<endl  return}intNumTree(charc)求结点在树中的编号{  intk,i=  intCodeN  k=NumElem(c)返回结点c的下标  if(k==)exit()结点c不存在退出  while(k){    如果k为偶数记录一个代码    if(k==)Codei=    elseCodei=    k=k    i  }  intx=,j  for(j=j<ij)    x=xCodej*Exp(,j)  returnx}intExp(inta,intb){  inti  intx=  for(i=i<bi)    x=x*a  returnx}返回结点在数组T中的下标intNumElem(charc){  inti=  while(i<NTi!=c)i  if(Ti==c)returni  elsereturn}解:StatusSimilarTree(BiTreeT,BiTreeT){  if(!T){T是空树    if(!T)returnTRUET是空树    elsereturnFALSE  }  else{T是非空树    if(!T)returnFALSE    else{T是非空树      if(SimilarTree(T>lchild,T>lchild)        SimilarTree(T>rchild,T>rchild))        returnTRUE      elsereturnFALSE    }  }}解:先序遍历的非递归算法StatusPOTraverse(BiTreeT,Status(*Visit)(TElemTypee)){  BiTreep  Stacks  InitStack(s)  p=T  while(p||!StackEmpty(s)){    if(p){        如果根指针不空访问根结点      右指针域压栈继续遍历左子树      if(!Visit(p>data))returnERROR      Push(s,p>rchild)      p=p>lchild    }根指针已空本子树已遍历完毕     退栈返回上一层继续遍历未曾访问的结点    elsePop(s,p)  }  returnOK}解:求位于先序序列中第k个位置的结点的值e中存放结点的返回值i为计数器StatusPONodeK(TElemTypee,inti,intk,BiTreeT){  if(T){    i    if(i==k)e=T>data    else{      PONodeK(e,i,k,T>lchild)      PONodeK(e,i,k,T>rchild)    }  }  returnOK}解:求二叉树中叶子结点的数目StatusPOLeafNodeNum(inti,BiTreeT){  if(T){    if(!T>lchild!T>rchild)i    POLeafNodeNum(i,T>lchild)    POLeafNodeNum(i,T>rchild)  }  returnOK}解:按先序交换二叉树的左右子树StatusExchangeBiTree(BiTreeT){  BiTreep  if(T){    p=T>lchild    T>lchild=T>rchild    T>rchild=p    ExchangeBiTree(T>lchild)    ExchangeBiTree(T>rchild)  }  returnOK}解:求二叉树中以元素值为x的结点为根的子树的深度StatusChildTreeDepth(BiTreeT,TElemTypex,intdepth){  BiTreeT  if(PreOrderLocate(T,x,T)){    depth=BiTDepth(T)    returnOK  }  elsereturnERROR}按先序在树中查找根为x的子树T为指向子树根的指针StatusPreOrderLocate(BiTreeT,TElemTypex,BiTreeT){  if(T){    if(T>data==x){      T=T      returnOK    }    else{      if(PreOrderLocate(T>lchild,x,T))        returnOK      else{        if(PreOrderLocate(T>rchild,x,T))          returnOK        elsereturnERROR      }    }  }  elsereturnERROR}求二叉树的深度intBiTDepth(BiTreeT){  intldep,rdep  if(!T)return  else{    ldep=BiTDepth(T>lchild)    rdep=BiTDepth(T>rchild)    returnldep>rdepldep:rdep  }}解:删除以元素值为x的结点为根的子树StatusDelChildTree(BiTreeT,TElemTypex){  if(T){    if(T>data==x){      DelBTree(T)      T=      returnOK    }    else{      if(DelChildTree(T>lchild,x))        returnOK      else{        if(DelChildTree(T>rchild,x))          returnOK        elsereturnERROR      }    }  }  elsereturnERROR}删除二叉树StatusDelBTree(BiTreeT){  if(T){    DelBTree(T>lchild)    DelBTree(T>rchild)    deleteT    returnOK  }  elsereturnERROR}解:复制一棵二叉树StatusCopyBiTree(BiTreeT,BiTreeT){  BiTreep  if(T){    p=newBiTNode    if(!p)returnERROR    p>data=T>data    T=p    CopyBiTree(T>lchild,T>lchild)    CopyBiTree(T>rchild,T>rchild)  }  else{    T=T  }  returnOK}解:typedefBiTreeQElemType#include"c:YinincludeQueueh"StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){  QElemTypep  Queueq  InitQueue(q)  if(T)EnQueue(q,T)  while(!QueueEmpty(q)){    DeQueue(q,p)    Visit(p>data)    if(p>lchild)EnQueue(q,p>lchild)    if(p>rchild)EnQueue(q,p>rchild)  }  returnOK}解:在二叉树T中求结点*p和*q的共同最小祖先eStatusMinComAncst(BiTreeT,TElemTypee,TElemType*p,TElemType*q){  if(!T)returnERROR  BiTreeT,T,pt=  if(!CopyBiTree(T,T))returnERROR  if(!CopyBiTree(T,T))returnERROR  if(!PathTree(T,p))    returnERROR求根结点到结点p的路径树T  elseShowBiTree(T)  cout<<endl  if(!PathTree(T,q))    returnERROR求根结点到结点q的路径树T  elseShowBiTree(T)  cout<<endl  while(TTT>data==T>data){    pt=T    if(T>lchild){      T=T>lchild      T=T>lchild    }    else{      if(T>rchild){        T=T>rchild        T=T>rchild      }    }  }  if(!pt)returnERROR  else{    e=pt>data    returnOK  }}在二叉树T中求根到结点p的路径树该操作将剪去除路径之外的所有分支StatusPathTree(BiTreeT,TElemType*p){  if(!T||!p)returnERROR  if(T>data==*p){找到目标删除目标的左右子树    if(T>lchild)DelBiTree(T>lchild)    if(T>rchild)DelBiTree(T>rchild)    returnOK  }  else{没找到目标继续递归查找    if(PathTree(T>lchild,p)){目标在左子树中删除右子树      if(T>rchild)DelBiTree(T>rchild)      returnOK    }    else      if(PathTree(T>rchild,p)){目标在右子树中删除左子树        if(T>lchild)DelBiTree(T>lchild)        returnOK      }      elsereturnERROR找不到目标  }}解:StatusCompleteBiTree(BiTreeT){  intd  if(T){    d=BiTDepth(T>lchild)BiTDepth(T>rchild)    if(d<||d>)returnERROR    else{      if(CompleteBiTree(T>lchild)        CompleteBiTree(T>rchild))returnOK      elsereturnERROR    }  }  elsereturnOK}解:StatusShowBiTExpress(BiTreeT){  if(T){    if(T>lchild){      if(Low(T>lchild>data,T>data)){        cout<<'('        ShowBiTExpress(T>lchild)        cout<<')'      }      elseShowBiTExpress(T>lchild)    }    cout<<T>data    if(T>rchild){      if(Low(T>rchild>data,T>data)){        cout<<'('        ShowBiTExpress(T>rchild)        cout<<')'      }      elseShowBiTExpress(T>rchild)    }  }  returnOK}StatusLow(chara,charb){  if((a==''||a=='')(b=='*'||b==''))returnTRUE  elsereturnFALSE}.解:intBiTreeThrive(BiTreeT){  inti,d,nn  d=BiTDepth(T)  BiTreep=T  Stacks,s  InitStack(s)  InitStack(s)  for(i=i<i){    nni=  每层结点个数  }  if(p)Push(s,p)  elsereturn  for(i=i<di){    if(!StackEmpty(s)StackEmpty(s)){      while(!StackEmpty(s)){        Pop(s,p)  nnis中存放第i层的结点        if(p>lchild)Push(s,p>lchild)s中存放第i层结点        if(p>rchild)Push(s,p>rchild)      }    }    else{      if(StackEmpty(s)!StackEmpty(s)){        while(!StackEmpty(s)){          Pop(s,p)  nni          if(p>lchild)Push(s,p>lchild)          if(p>rchild)Push(s,p>rchild)        }      }    }  }  intmax=nn  for(i=i<di)    if(max<nni)max=nni  returnmax*d}解:所有从根到叶子最长路径树StatusMaxPathBiTree(BiTreeT){  if(T){    if(BiTDepth(T)BiTDepth(T>lchild)!=)      DelBiTree(T>lchild)    else      MaxPathBiTree(T>lchild)    if(BiTDepth(T)BiTDepth(T>rchild)!=)      DelBiTree(T>rchild)    else      MaxPathBiTree(T>rchild)  }  returnOK}从根到叶子最长路径中最左方的路径树StatusLMaxPathBiTree(BiTreeT){  if(T){    if(BiTDepth(T)BiTDepth(T>lchild)==){      DelBiTree(T>rchild)      LMaxPathBiTree(T>lchild)    }    else{      DelBiTree(T>lchild)      if(BiTDepth(T)BiTDepth(T>rchild)==)        LMaxPathBiTree(T>rchild)      else        DelBiTree(T>rchild)    }  }  returnOK}解:根据完全二叉顺序树创建完全二叉链表树StatusCreateCompleteBiTree(SqList<TElemType>ST,BiTreeLT){  BiTreep  inti=,len  if(STLength==)returnOK  p=newBiTNode  if(!p)returnERROR  p>data=STGet(i)  p>lchild=  p>rchild=  LT=p  Queueq  InitQueue(q)  EnQueue(q,p)  len=STLength()    while(!QueueEmpty(q)i<len){    DeQueue(q,p)    if(i<leni==){      p>lchild=newBiTNode      if(!p>lchild)returnERROR      p>lchild>data=STGet(i)      p>lchild>lchild=      p>lchild>rchild=      EnQueue(q,p>lchild)    }    if(i<leni==){      p>rchild=newBiTNode      if(!p>rchild)returnERROR      p>rchild>data=STGet(i)      p>rchild>lchild=      p>rchild>rchild=      EnQueue(q,p>rchild)    }  }  returnOK}解:StatusPreOrderTraverse(BiTreeT){  if(T){    T>DescNum=DescendNum(T)    PreOrderTraverse(T>lchild)    PreOrderTraverse(T>rchild)  }  returnOK}intDescendNum(BiTreeT){  if(!T)return  if(!T>lchild){    if(!T>rchild)return    elsereturnDescendNum(T>rchild)  }  else{    if(!T>rchild)returnDescendNum(T>lchild)    elsereturnDescendNum(T>rchild)DescendNum(T>lchild)  }}解:先对二叉树T进行先序线索得到先序线索二叉树Thrt。然后再进行查找。先序线索二叉树算法StatusPreOrderThreading(BiThrTreeThrt,BiThrTreeT){  BiThrTreepre  Thrt=newBiThrNode为线索二叉树建立头结点  if(!Thrt)exit(OVERFLOW)  Thrt>LTag=Thread  Thrt>RTag=Link  Thrt>lchild=Thrt左子树回指  if(!T)Thrt>rchild=Thrt若二叉树空右子树回指  else{    Thrt>rchild=T    pre=Thrt    PreThreading(T,pre)先序遍历进行先序线索化    pre>rchild=Thrt最后一个结点线索化    pre>RTag=Thread    Thrt>lchild=pre  }  returnOK}StatusPreThreading(BiThrTreeT,BiThrTreepre){  if(T){    if(!T>lchild){      T>LTag=Thread      T>lchild=pre    }    if(pre!pre>rchild){      pre>RTag=Thread      pre>rchild=T    }    pre=T    if(T>LTag==Link)PreThreading(T>lchild,pre)    if(T>RTag==Link)PreThreading(T>rchild,pre)  }  returnOK}从二叉线索树上任一结点q开始查找结点*p。如果找到将*p的后继结点指针存于q中返回TRUE否则返回FALSEStatusFindNextInBiThrTree(BiThrTreeq,TElemType*p){  BiThrTreept=q  if(!pt)returnFALSE  if(pt>data==*p){    if(pt>LTag==Link)q=pt>lchild    elseq=pt>rchild    returnOK  }  pt=q>rchild  while(pt!=qpt>data!=*p){    if(pt>LTag==Link)pt=pt>lchild    elsept=pt>rchild  }  if(pt==q)returnFALSE  if(pt>data==*p){    if(pt>LTag==Link)q=pt>lchild    elseq=pt>rchild  }  returnOK}解:StatusPostOrderThreading(BiThrTreeT,BiThrTreepre)首先建立后序线索树StatusFindNextInBiThrTree(BiThrTreeq,TElemType*p)再进行查找后序线索二叉树的算法StatusPostOrderThreading(BiThrTreeThrt,BiThrTreeT){  BiThrTreepre  Thrt=newBiThrNode为线索二叉树建立头结点  if(!Thrt)exit(OVERFLOW)  Thrt>LTag=Link  Thrt>RTag=Thread  Thrt>rchild=Thrt右子树回指  if(!T)Thrt>lchild=Thrt若二叉树空左子树回指  else{    Thrt>lchild=T    pre=Thrt    PostThreading(T,pre)后序遍历进行后序线索化    pre>rchild=Thrt最后一个结点线索化    pre>RTag=Thread    Thrt>rchild=pre  }  returnOK}StatusPostThreading(BiThrTreeT,BiThrTreepre){  if(T){    if(T>LTag==Link)PostThreading(T>lchild,pre)    if(T>RTag==Link)PostThreading(T>rchild,pre)    if(!T>lchild){      T>LTag=Thread      T>lchild=pre    }    if(pre!pre>rchild){      pre>RTag=Thread      pre>rchild=T    }    pre=T  }  returnOK}解:typedefcharTElemTypetypedefstructCSNode{  TElemTypedata  structCSNode*firstchild,*nextsibling}CSNode,*CSTree建立树的二叉链表表示StatusCreateTree(CSTreeT){  charch  cout<<"输入结点的值(一个字符''表示空树)"  cin>>ch  if(ch==''){    T=  }  else{    T=newCSNode    if(!T)returnERROR    T>data=ch    CreateTree(T>firstchild)    CreateTree(T>nextsibling)  }  returnOK}输出树的各边StatusShowTree(CSTreeT,CSTreeFather){  if(TFather)    cout<<"("<<Father>data<<","<<T>data<<")"  if(T>firstchild)ShowTree(T>firstchild,T)  if(T>nextsibling)ShowTree(T>nextsibling,Father)  returnOK}解:intLeafNum(CSTreeT){  if(T){    if(!T>firstchild)      returnLeafNum(T>nextsibling)    else      returnLeafNum(T>firstchild)LeafNum(T>nextsibling)  }  elsereturn}解:intDegreeNum(CSTreeT){  intd,dl,dr  if(T){    if(!T>firstchild)d=    elsed=RSiblingNum(T>firstchild)    dl=DegreeNum(T>firstchild)    dr=DegreeNum(T>nextsibling)    returnMax(d,dl,dr)三数中求最大者  }  elsereturn}返回当前结点的兄弟数intRSiblingNum(CSTreeT){  inti=  while(T>nextsibling){    i    T=T>nextsibling  }  returni}解:树的深度intDepth(CSTreeT){  intd,d  if(T){    d=Depth(T>firstchild)    d=Depth(T>nextsibling)    returnd>dd:d  }  elsereturn}第章 图解:()  ID()=    OD()=      ID()=    OD()=      ID()=    OD()=      ID()=    OD()=      ID()=    OD()=      ID()=    OD()=  ()                                                                                  ()    ()        ()有三个连通分量、、解:k=说明了各结点之间的相互连通关系k=说明了结点之间按路径长度为的相互连通关系。解:邻接表:      邻接多重表:  深度优先搜索的顺序为  广度优先搜索的顺序为    解:StatusCreateAG(ALGraphG){  intn,e,k,i,j  cout<<"请输入顶点数:"  cin>>n  cout<<"请输入边数:"  cin>>e  Gvernum=n  Garcnum=e  建立顶点数组  for(k=k<Gvernumk){    cout<<"请输入顶点信息:"    cin>>Gverticeskdata    Gverticeskfirstarc=  }  建立邻接表  VertexTypev,v  ArcNode*p,*q  for(k=k<Garcnumk){    cout<<"请输入弧的始点和终点信息中间用空格分开:"    cin>>v>>v    i=LocateVex(G,v)    if(i<||i>Gvernum)returnERROR    j=LocateVex(G,v)    if(j<||j>Gvernum)returnERROR    if(i==j)returnERROR    p=newArcNode    if(!p)returnERROR    p>adjvex=j    p>nextarc=    q=Gverticesifirstarc    if(!q)Gverticesifirstarc=p    else{      while(q>nextarc)q=q>nextarc  指针定位于邻接表的尾结点      q>nextarc=p    }  }  returnOK}intLocateVex(ALGraphG,VertexTypev){  inti=  while(Gverticesidata!=vi<Gvernum)i  if(Gverticesidata==v)returni  elsereturn}解第章 查找解:()相同平均查找长度为  ()相同平均查找长度为  ()对于有序顺序表平均查找长度为对于无序顺序表则为。解:查找e的过程如下:  解:  解:  解:  解:              解:()    (

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/134
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部