《数据结构Java版》习题解答

I第0章JAVA程序设计基础1【习01】实验01哥德巴赫猜想。1【习02】实验02杨辉三角形。1【习03】实验03金额的中文大写形式。1【习04】实验04下标和相等的数字方阵。1【习05】实验05找出一个二维数组的鞍点2【习06】实验06复数类。2【习07】实验08图形接口与实现图形接口的类2第1章绪论3【习11】实验11判断数组元素是否已按升序排序。3【习12】实验13用递归算法求两个整数的最大公因数。3第2章线性表5【习21】习25图219的数据结构声明。5【习22】习26如果在遍历单链表时，将PPNEXT语句写成PNEXTP，结果会怎样5【习23】实验22由指定数组中的多个对象构造单链表。5【习24】实验22单链表的查找、包含、删除操作详见821。5【习25】实验22单链表的替换操作。6【习26】实验22首尾相接地连接两条单链表。6【习27】实验22复制单链表。6【习28】实验22单链表构造、复制、比较等操作的递归方法。7【习29】建立按升序排序的单链表（不带头结点）。8【习210】实验26带头结点的循环双链表类，实现线性表接口。10【习211】实验25建立按升序排序的循环双链表。14第3章栈和队列17【习31】习35栈和队列有何异同17【习32】能否将栈声明为继承线性表，入栈方法是ADD0,E，出栈方法是REMOVE0为什么17【习33】能否用一个线性表作为栈的成员变量，入栈方法是ADD0,E，出栈方法是REMOVE0为什么17【习34】能否将队列声明为继承线性表，入队方法是ADDE，出队方法是REMOVE0为什么17第4章串18【习41】实验46找出两个字符串中所有共同的字符。18【习42】习491已知目标串为“ABBABA“、模式串为“ABA“，画出其KMP算法的匹配过程，并给出比较次数。18II【习43】习492已知TARGET“ABABAAB“、PATTERN“AAB“，求模式串的NEXT数组，画出其KMP算法的匹配过程，并给出比较次数。18第5章数组和广义表20【习51】求一个矩阵的转置矩阵。20第6章树和二叉树21【习61】画出3个结点的各种形态的树和二叉树。21【习62】找出分别满足下面条件的所有二叉树。21【习63】输出叶子结点。21【习64】求一棵二叉树的叶子结点个数。22【习65】判断两棵二叉树是否相等。22【习66】复制一棵二叉树。23【习67】二叉树的替换操作。23【习68】后根次序遍历中序线索二叉树。24第7章图25第8章查找26【习81】实验81顺序表的查找、删除、替换、比较操作。26【习82】实验82单链表的全部替换操作。28【习83】实验82单链表的全部删除操作。28【习84】折半查找的递归算法。29【习85】二叉排序树查找的递归算法。29【习86】二叉排序树插入结点的非递归算法。30【习87】判断一棵二叉树是否为二叉排序树。31第9章排序32【习91】判断一个数据序列是否为最小堆序列。32【习92】归并两条排序的单链表。32【习93】说明二叉排序树与堆的差别。34图01下标和相等的数字方阵算法描述1图21PNEXTP将改变结点间的链接关系5图41目标串“ABBABA“和模式串“ABA“的KMP算法模式匹配过程18图42目标串“ABABAAB“和模式串“AAB“的KMP算法模式匹配过程19图613个结点树和二叉树的形态21图62单支二叉树21图92归并两条排序的单链表33III表41模式串“AAB“的NEXT数组191第0章JAVA程序设计基础【习01】实验01哥德巴赫猜想。【习02】实验02杨辉三角形。【习03】实验03金额的中文大写形式。【习04】实验04下标和相等的数字方阵。输出下列方阵（当N4时）。1267或134103581325911491214681215101115167131416采用二维数组实现。二维数组中，每一条斜线上各元素下标和相等，如图01所示。J12673581349121410115160123123I右下三角下标和为N2N左上三角下标和为0N1下标和为4下标和为5下标和为6图01下标和相等的数字方阵算法描述程序如下。PUBLICCLASSUPMATPUBLICSTATICVOIDMAINSTRINGARGSINTN4/阶数INTMATNEWINTNNINTK1/K是自然数，递增变化BOOLEANUPTRUE/方向向上FORINTSUM0SUM0IMATISUMIK/K先赋值后自加ELSEFORINTI0ISUMNJMATSUMJJKUPUPFORINTI0ITABLEI1RETURNFALSERETURNTRUEPUBLICSTATICBOOLEANISSORTEDCOMPARABLETABLE/判断对象数组是否已按升序排序/若已排序返回TRUE，否则返回FALSEIFTABLENULLRETURNFALSEFORINTI0I0RETURNFALSERETURNTRUE【习12】实验13用递归算法求两个整数的最大公因数。PUBLICCLASSGCDPUBLICSTATICINTGCDINTA,INTB/返回A,B的最大公因数，递归方法IFB0RETURNAIFATABLE【习22】习26如果在遍历单链表时，将PPNEXT语句写成PNEXTP，结果会怎样使PNEXT指向P结点自己，改变了结点间的链接关系，丢失后继结点，如图21所示。AHEADBCD图21PNEXTP将改变结点间的链接关系【习23】实验22由指定数组中的多个对象构造单链表。在SINGLYLINKEDLIST单链表类中，增加构造方法如下。PUBLICSINGLYLINKEDLISTEELEMENT/由指定数组中的多个对象构造单链表THISHEADNULLIFELEMENTNULLNODEREARTHISHEADINTI1WHILEISEARCHEELEMENT,NODESTART/从单链表结点START开始顺序查找指定对象PUBLICNODESEARCHEELEMENT/若查找到指定对象，则返回结点，否则返回6NULLPUBLICBOOLEANCONTAINEELEMENT/以查找结果判断单链表是否包含指定对象PUBLICBOOLEANREMOVEEELEMENT/移去首次出现的指定对象【习25】实验22单链表的替换操作。在SINGLYLINKEDLIST单链表类中，增加替换操作方法如下。PUBLICBOOLEANREPLACEOBJECTOBJ,EELEMENT/将元素值为OBJ的结点值替换为ELEMENT/若替换成功返回TRUE，否则返回FALSE，ONIFOBJNULL|ELEMENTNULLRETURNFALSENODEPTHISHEADWHILEPNULLIFOBJEQUALSPDATAPDATAELEMENTRETURNTRUEPPNEXTRETURNFALSE【习26】实验22首尾相接地连接两条单链表。在SINGLYLINKEDLIST单链表类中，增加替换操作方法如下。PUBLICVOIDCONCATSINGLYLINKEDLISTLIST/将指定单链表LIST链接在当前单链表之后IFTHISHEADNULLTHISHEADLISTHEADELSENODEPTHISHEADWHILEPNEXTNULLPPNEXTPNEXTLISTHEAD【习27】实验22复制单链表。7在SINGLYLINKEDLIST单链表类中，增加构造方法如下。PUBLICSINGLYLINKEDLISTSINGLYLINKEDLISTLIST/以单链表LIST构造新的单链表/复制单链表THISHEADNULLIFLISTNULLNODEPLISTHEADNEXTNODEREARTHISHEADWHILEPNULLREARNEXTNEWNODEPDATAREARREARNEXTPPNEXT【习28】实验22单链表构造、复制、比较等操作的递归方法。由指定数组中的多个对象构造单链表的操作也可设计为以下的递归方法PUBLICSINGLYLINKEDLISTEELEMENT/由指定数组中的多个对象构造单链表THISHEADNULLIFELEMENTNULLTHISHEADCREATEELEMENT,0PRIVATENODECREATEEELEMENT,INTI/由指定数组构造单链表，递归方法NODEPNULLIFILIST/以单链表LIST构造新的单链表8THISHEADCOPYLISTHEADPRIVATENODECOPYNODEP/复制单链表，递归方法NODEQNULLIFPNULLQNEWNODEPDATAQNEXTCOPYPNEXTRETURNQ比较两条单链表是否相等的操作也可设计为以下的递归方法PUBLICBOOLEANEQUALSOBJECTOBJ/比较两条单链表是否相等IFOBJTHISRETURNTRUEIFOBJINSTANCEOFSINGLYLINKEDLISTSINGLYLINKEDLISTLISTSINGLYLINKEDLISTOBJRETURNEQUALSTHISHEAD,LISTHEADRETURNFALSEPRIVATEBOOLEANEQUALSNODEP,NODEQ/比较两条单链表是否相等，递归方法IFPNULLIFPNULLRETURNFALSE【习29】建立按升序排序的单链表（不带头结点）。采用直接插入排序算法将一个结点插入到已排序的单链表中。IMPORTDATASTRUCTURELINEARLISTNODEIMPORTDATASTRUCTURELINEARLISTSINGLYLINKEDLIST/不带头结点的单链表类9PUBLICCLASSSORTEDSINGLYLINKEDLISTEXTENDSSINGLYLINKEDLISTPUBLICSORTEDSINGLYLINKEDLISTSUPERPUBLICBOOLEANADDEELEMENT/根据指定对象的大小插入在合适位置IFELEMENTNULL|ELEMENTINSTANCEOFCOMPARABLERETURNFALSE/不能插入NULL或非COMPARABLE对象COMPARABLECMPCOMPARABLEELEMENTIFTHISHEADNULL|CMPCOMPARETOTHISHEADDATAELEMENT,THISHEAD/头插入ELSENODEFRONTNULL,PTHISHEADWHILEPNULL/FRONT是P的前驱结点PPNEXTFRONTNEXTNEWNODEELEMENT,P/中间/尾插入RETURNTRUEPUBLICSTATICVOIDMAINSTRINGARGSSORTEDSINGLYLINKEDLISTLISTNEWSORTEDSINGLYLINKEDLISTINTN10SYSTEMOUTPRINT“INSERT“FORINTI0IIMPLEMENTSLLIST/带头结点的循环双链表类PROTECTEDDLINKNODEHEAD/头指针PUBLICCHDOUBLYLINKEDLIST/构造空链表THISHEADNEWDLINKNODE/创建头结点，值为NULLTHISHEADPREVHEADTHISHEADNEXTHEADPUBLICBOOLEANISEMPTY/判断双链表是否为空RETURNHEADNEXTHEAD/以下算法同循环单链表，与单链表的差别在于，循环条件不同PUBLICINTLENGTH/返回双链表长度INTI0DLINKNODEPTHISHEADNEXT/此句与单链表不同WHILEPHEAD/循环条件与单链表不同11IPPNEXTRETURNIPUBLICEGETINTINDEX/返回序号为INDEX的对象IFINDEX0INTJ0DLINKNODEPTHISHEADNEXTWHILEPHEADDLINKNODEPTHISHEADNEXTWHILEPHEADWHILEPHEADSTRPDATATOSTRINGPPNEXTIFPHEADSTR“,“RETURNSTR“/双链表的插入、删除算法与单链表不同PUBLICBOOLEANADDINTINDEX,EELEMENT/插入ELEMENT对象，插入后对象序号为INDEX/若操作成功返回TRUE，ONIFELEMENTNULLRETURNFALSE/不能添加空对象（NULL）INTJ0DLINKNODEFRONTTHISHEADWHILEFRONTNEXTHEAD/插入在FRONT结点之后FRONTNEXTPREVQFRONTNEXTQRETURNTRUE13PUBLICBOOLEANADDEELEMENT/在单链表最后添加对象，O1IFELEMENTNULLRETURNFALSE/不能添加空对象（NULL）DLINKNODEQNEWDLINKNODEELEMENT,HEADPREV,HEADHEADPREVNEXTQ/插入在头结点之前，相当于尾插入HEADPREVQRETURNTRUEPUBLICEREMOVEINTINDEX/移除指定位置的对象，ON/返回被移除的原对象，指定位置序号错误时返回NULLEOLDNULLINTJ0DLINKNODEPTHISHEADNEXTWHILEPHEADSYSTEMOUTPRINTLN“删除第“I“个结点“LISTREMOVE0SYSTEMOUTPRINTLNLISTTOSTRINGFORI5I0ILISTADD0,NEWSTRINGCHARAI“FORI0IEXTENDSCHDOUBLYLINKEDLIST/按升序排序的循环双链表类PUBLICSORTEDCHDLINKEDLISTSUPERPUBLICBOOLEANADDEELEMENT/根据指定对象的大小插入在合适位置/若操作成功返回TRUE，ONIFELEMENTNULL|ELEMENTINSTANCEOFCOMPARABLERETURNFALSE/不能插入NULL或非COMPARABLE对象15COMPARABLECMPCOMPARABLEELEMENTIFTHISHEADPREVHEADHEADPREVNEXTQ/插入在头结点之前，相当于尾插入HEADPREVQRETURNTRUEDLINKNODEPTHISHEADNEXTWHILEPHEADDLINKNODEQNEWDLINKNODEELEMENT,PPREV,P/插入在P结点之前PPREVNEXTQPPREVQRETURNTRUEPUBLICBOOLEANREMOVEEELEMENT/删除指定对象/若操作成功返回TRUE，ONIFELEMENTNULL|ELEMENTINSTANCEOFCOMPARABLERETURNFALSECOMPARABLECMPCOMPARABLEELEMENTDLINKNODEPTHISHEADNEXTWHILEPHEADIFPHEADPPREVNEXTPNEXT/删除P结点自己PNEXTPREVPPREVRETURNTRUERETURNFALSE/未找到指定结点，删除不成功PUBLICSTATICVOIDMAINSTRINGARGS16SORTEDCHDLINKEDLISTLISTNEWSORTEDCHDLINKEDLISTINTN10SYSTEMOUTPRINT“INSERT“FORINTI0IP/先根次序遍历，输出叶子结点，3种遍历次序结果一样IFPNULLIFPISLEAF22SYSTEMOUTPRINTPDATA“LEAFPLEFTLEAFPRIGHT【习64】求一棵二叉树的叶子结点个数。在BINARYTREE类中增加以下方法。PUBLICINTCOUNTLEAF/求一棵二叉树中所有叶子结点个数RETURNCOUNTLEAFROOTPUBLICINTCOUNTLEAFBINARYNODEP/求以P结点为根的子树的叶子结点个数IFPNULLRETURN0IFPISLEAFRETURN1RETURNCOUNTLEAFPLEFTCOUNTLEAFPRIGHT【习65】判断两棵二叉树是否相等。PUBLICBOOLEANEQUALSOBJECTOBJ/比较两棵二叉树是否相等，BINARYTREE类中方法IFOBJTHISRETURNTRUEIFOBJINSTANCEOFBINARYTREEBINARYTREEBITREEBINARYTREEOBJRETURNEQUALSTHISROOT,BITREEROOTRETURNFALSEPRIVATEBOOLEANEQUALSBINARYNODEP,BINARYNODEQ/判断两棵子树是否相等，递归方法IFPNULLIFPNULL23RETURNFALSE【习66】复制一棵二叉树。在BINARYTREE类中增加以下构造方法，以已知的BITREE构造二叉树构造一棵二叉树。PUBLICBINARYTREEBINARYTREEBITREE/以已知的BITREE构造二叉树THISROOTCOPYBITREEROOTPUBLICBINARYNODECOPYBINARYNODEP/复制以P根的子二叉树BINARYNODEQNULLIFPNULLQNEWBINARYNODEPDATAQLEFTCOPYPLEFT/复制左子树QRIGHTCOPYPRIGHT/复制右子树RETURNQ/返回建立子树的根结点【习67】二叉树的替换操作。PUBLICBOOLEANREPLACEEOLD,EVALUE/将首次出现的值为OLD结点值替换为VALUEBINARYNODEFINDSEARCHOLD/查找值为OLD的结点IFFINDNULLFINDDATAVALUE/替换结点元素值RETURNFINDNULLPUBLICVOIDREPLACEALLEOLD,EVALUE/将值为OLD的结点全部替换为VALUEREPLACEALLROOT,OLD,VALUEPUBLICVOIDREPLACEALLBINARYNODEP,EOLD,EVALUE/在以P为根的子树中实现全部替换IFPNULLIFPDATAEQUALSOLDPDATAVALUE24REPLACEALLPLEFT,OLD,VALUEREPLACEALLPRIGHT,OLD,VALUE【习68】后根次序遍历中序线索二叉树。在中序线索二叉树类THREADBINARYTREE中，增加以下方法，实现后根次序遍历。PUBLICTHREADBINARYNODEPOSTPREVIOUSTHREADBINARYNODEP/返回P在后根次序下的前驱IFPRTAG0/若右子树非空PPRIGHT/右孩子是P的前驱结点ELSE/否则，前驱是左兄弟或某个中序祖先的左孩子WHILEPLTAG1/寻找其某个中序祖先PPLEFT/左孩子是P的前驱结点RETURNPPUBLICVOIDPOSTORDER_PREVIOUS/后根次序遍历中序线索二叉树THREADBINARYNODEPROOTIFPNULLSYSTEMOUTPRINT“后根次序遍历（反序）“DOSYSTEMOUTPRINTPDATA“PPOSTPREVIOUSP/返回P在后根次序下的前驱结点WHILEPNULLSYSTEMOUTPRINTLN25第7章图26第8章查找【习81】实验81顺序表的查找、删除、替换、比较操作。程序见顺序表类SEQLISTJAVA。PUBLICINTLASTINDEXOFEELEMENT/返回OBJ对象最后出现位置，若未找到返回1IFOBJNULLFORINTITHISN1I0IIFOBJEQUALSTHISTABLEIRETURNIRETURN1PUBLICBOOLEANREMOVEEELEMENT/移去首次出现的OBJ对象，若操作成功返回TRUEIFTHISN0RETURNFALSEPUBLICBOOLEANREMOVEALLEELEMENT/移去线性表中所有OBJ对象BOOLEANDONEFALSEIFTHISN0WHILEILISTSEQLISTOBJFORINTI0IPTHISHEADWHILEPNULLIFOBJEQUALSPDATAPDATAELEMENTDONETRUEPPNEXTRETURNDONE【习83】实验82单链表的全部删除操作。在SINGLYLINKEDLIST单链表类中，增加删除操作方法如下。PUBLICBOOLEANREMOVEALLOBJECTOBJ/将所有元素值为OBJ的结点删除IFTHISHEADNULL|OBJNULLRETURNFALSEBOOLEANDONEFALSEWHILETHISHEADNULL/头删除DONETRUENODEFRONTTHISHEAD,PFRONTNEXT29WHILEPNULLIFOBJEQUALSPDATAFRONTNEXTPNEXT/删除P结点PFRONTNEXTDONETRUEELSEFRONTPPPNEXTRETURNDONE【习84】折半查找的递归算法。PUBLICSTATICINTBINARYSEARCHINTTABLE,INTVALUE/折半查找算法，数组元素已按升序排列/若查找成功返回元素下标，否则返回1IFTABLENULLRETURNBINARYSEARCHTABLE,VALUE,0,TABLELENGTH1RETURN1PRIVATESTATICINTBINARYSEARCHINTTABLE,INTVALUE,INTLOW,INTHIGH/折半查找，递归算法/LOW、HIGH指定查找范围的下界和上界IFLOWVALUE/给定值小RETURNBINARYSEARCHTABLE,VALUE,LOW,MID1/查找范围缩小到前半段ELSERETURNBINARYSEARCHTABLE,VALUE,MID1,HIGH/查找范围缩小到后半段RETURN1【习85】二叉排序树查找的递归算法。30将二叉排序树类BINARYSORTTREE中的SEARCHVALUE方法替换为以下方法。PUBLICBINARYNODESEARCHNODEEVALUE/查找值为VALUE的结点/若查找成功返回结点，否则返回NULLIFVALUENULL|VALUEINSTANCEOFCOMPARABLERETURNNULLRETURNSEARCHNODEVALUE,ROOTPRIVATEBINARYNODESEARCHNODEEVALUE,BINARYNODEP/查找值为VALUE的结点，递归算法IFPNULLCOMPARABLECMPOBJCOMPARABLEVALUEIFCMPOBJCOMPARETOPDATA0/若两个对象相等，查找成功RETURNPSYSTEMOUTPRINTPDATA“IFCMPOBJCOMPARETOPDATAVALUE/建立根结点ELSEBINARYNODEPTHISROOT,PARENTNULLCOMPARA