雙向循環(huán)鏈表的創(chuàng)建及相關(guān)操作的實(shí)現(xiàn)課程說(shuō)明

1、課程設(shè)計(jì)說(shuō)明書(shū)題目：雙向鏈表的創(chuàng)立和操作的實(shí)現(xiàn)樹(shù)的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)課程：數(shù)據(jù)結(jié)構(gòu)與算法院部：計(jì)算機(jī)學(xué)院專業(yè)：網(wǎng)絡(luò)工程班級(jí)：網(wǎng)絡(luò)101學(xué)生姓名：王天未學(xué)號(hào)：學(xué)10111200指導(dǎo)教師：伊靜完成日期：2021-7-6課程設(shè)計(jì)任務(wù)書(shū)1II課程設(shè)計(jì)任務(wù)書(shū)2III雙向循環(huán)鏈表的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)4、問(wèn)題描述4二、數(shù)據(jù)結(jié)構(gòu)4三、邏輯設(shè)計(jì)5四、編碼6五、測(cè)試數(shù)據(jù)11六、測(cè)試情況11樹(shù)的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)15一、問(wèn)題描述15二、數(shù)據(jù)結(jié)構(gòu)15三、邏輯設(shè)計(jì)16四、編碼19五、測(cè)試數(shù)據(jù)26六、測(cè)試情況26結(jié)論28參考文獻(xiàn)29課程設(shè)計(jì)指導(dǎo)教師評(píng)語(yǔ)30課程設(shè)計(jì)任務(wù)書(shū)1指導(dǎo)教師簽字教研室主任簽字設(shè)計(jì)題目雙向循環(huán)鏈

2、表的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)技術(shù)參數(shù)和設(shè)計(jì)要求1、建立一個(gè)空表2、插入第i個(gè)結(jié)點(diǎn).3、刪除第i個(gè)結(jié)點(diǎn).4、插入第1個(gè)結(jié)點(diǎn).5、插入取后個(gè)結(jié)點(diǎn).6、逆置設(shè)計(jì)內(nèi)容與步驟1、設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)2、設(shè)計(jì)算法3、編寫(xiě)程序,進(jìn)行調(diào)試4、總結(jié)并進(jìn)行演示、講解設(shè)計(jì)工作計(jì)劃與進(jìn)度安排做雙向鏈表創(chuàng)立方法做雙向鏈表各種操作方法設(shè)計(jì)考核要求1、考勤20%2、課程設(shè)計(jì)說(shuō)明書(shū)50%3、成果展示30%課程設(shè)計(jì)任務(wù)書(shū)2指導(dǎo)教師簽字教研室主任簽字設(shè)計(jì)題目樹(shù)的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)技術(shù)參數(shù)和設(shè)計(jì)要求1、利用先序遍歷和層次遍歷的結(jié)果建立二叉樹(shù)2、實(shí)現(xiàn)二叉樹(shù)的層次遍歷3、統(tǒng)計(jì)二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)遞歸.4、將二叉樹(shù)左右子樹(shù)相互交換遞歸設(shè)計(jì)內(nèi)容與步

3、驟1 .建立結(jié)點(diǎn)類2 .構(gòu)造BinaryTree3 .建立線序遍歷樹(shù)4 .建立層次遍歷樹(shù)5 .實(shí)現(xiàn)樹(shù)的層次遍歷6 .統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)7 .交換左右子樹(shù)8 .輸出樹(shù)的方法設(shè)計(jì)工作計(jì)劃與進(jìn)度安排6月13日,實(shí)驗(yàn)課下完成先序遍歷建樹(shù),16月14日課程設(shè)計(jì)時(shí)間完成層次遍歷建樹(shù)6月16日課下完成層次遍歷和葉子節(jié)點(diǎn)個(gè)數(shù)統(tǒng)計(jì)6月18日課程設(shè)計(jì)時(shí)間完成二叉樹(shù)左右子樹(shù)相互交換6月19日完成測(cè)試函數(shù)及糾錯(cuò)設(shè)計(jì)考核要求1、考勤20%2、課程設(shè)計(jì)說(shuō)明書(shū)50%3、成果展示30%雙向循環(huán)鏈表的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)、問(wèn)題描述1、每個(gè)節(jié)點(diǎn)的next域構(gòu)成了一個(gè)循環(huán)單鏈表2、每個(gè)節(jié)點(diǎn)的prev域構(gòu)成了另一個(gè)循環(huán)單鏈表、數(shù)據(jù)結(jié)構(gòu)

4、針對(duì)所處理的樹(shù)：1、畫(huà)出雙向循環(huán)鏈表的存儲(chǔ)結(jié)構(gòu)prevdlatanext2、使用所選用語(yǔ)言的功能,描述該存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)privatestaticclassNodeAnyTypedata;Nodeprev;Nodenext;三、邏輯設(shè)計(jì)1、總體思路對(duì)于雙向循環(huán)鏈表,建立一個(gè)空表,然后實(shí)現(xiàn)雙向循環(huán)鏈表的插入,刪除操作.為了便于逆置的操作,選擇建立一個(gè)帶頭節(jié)點(diǎn)的雙向循環(huán)鏈表,插入第一個(gè)節(jié)點(diǎn)和插入最后一個(gè)節(jié)點(diǎn),只需要在0號(hào)位置和size()位置插入節(jié)點(diǎn)就行.2、模塊劃分(以圖示的方法給出各個(gè)函數(shù)的調(diào)用關(guān)系)3、函數(shù)或類的具體定義和功能classNode/節(jié)點(diǎn)類定義publicclassDlList/循

5、環(huán)鏈表主類publicbooleanadd(intidex,AnyTypex)/鏈表插入操作publicAnyTyperemove(intidex)/鏈表刪除操作privatevoidinverse()/鏈表逆置四、編碼importjava.util.Scanner;classNodepublicAnyTypedata;publicNodeprev;publicNodenext;publicNode()data=null;prev=null;next=null;publicNode(AnyTyped)data=d;prev=null;next=null;publicNode(AnyTyped,

6、Nodep,Noden)data=d;prev=p;next=n;/節(jié)點(diǎn)類publicclassDlListprivateNodeheadNode=newNode();/頭標(biāo)記或頭節(jié)點(diǎn)privateinttheSize;/長(zhǎng)度publicDlList()headNodenext=headNodeheadNodeprev=headNodetheSize=0;/創(chuàng)立一個(gè)空表publicintsize()returntheSize;設(shè)定表的長(zhǎng)度publicbooleanadd(AnyTypex)add(theSize,x);returntrue;/鏈表輸入操作publicbooleanadd(int

7、idex,AnyTypex)booleanflag;if(idextheSize)/判斷插入的位置是否大于0System.out.println(您輸入的要插入元素的位置不正確！)；flag=false;elseflag=true;if(flag)Nodep;p=getNode(idex);addBefore(p,x);/插入操作returnflag;privatevoidaddBefore(Nodep,AnyTypex)NodenewNode=newNode(x,p.prev,p);newNodeprev.next=newNode;p. prev=newNode;theSize+;插入方法p

8、ublicAnyTyperemove(intidex)returnremove(getNode(idex);privateAnyTyperemove(Nodep)p.prev.next=p.next;q. next.prev=p.prev;theSize-;returnp.data;/刪除操作privatevoidinverse()Nodep,q,l;p=headNodenext;q=p.next;while(p!=headNodel=q.next;/空置的中轉(zhuǎn)結(jié)點(diǎn)賦值r. next=p;將p、q鏈表的前后域置換.q由p的后域變成前域p. prev=q;p=q;/置換后,將各個(gè)結(jié)點(diǎn)置換輸出.q

9、=l;q. next=p;p.prev=q;/當(dāng)p為頭結(jié)點(diǎn)時(shí),直接將前后域置換/逆置privateNodegetNode(intidex)Nodep;if(idexsize()thrownewIndexOutOfBoundsException(getNodeidex:+idex+;size:+size();if(idexsize()/2)p=headNodefor(inti=0;iidex;i-)p=p.prev;returnp;/查找結(jié)點(diǎn)位置publicvoidprint()for(inti=0;ithis.theSize;i+)System.out.print(getNode(i).dat

10、a+)System.out.println();/結(jié)果輸出publicvoidchoose()System.out.println(System.out.println(System.out.println(System.out.println(System.out.println(/選擇操作項(xiàng)1.插入第i個(gè)節(jié)點(diǎn)；2.刪除第i個(gè)節(jié)點(diǎn)；3.插入第一個(gè)節(jié)點(diǎn);4.插入最后一個(gè)節(jié)點(diǎn);5.逆置；publicstaticvoidmain(String口args)DlListdl=newDlList();Scannersc=newScanner(System.in);intxuanze;System.out

11、.println(請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：)；intn=sc.nextInt();System.out.println(請(qǐng)輸入鏈表的+n+個(gè)元素：);for(inti=1;i=n;i+)intl=sc.nextInt();dl.add(l);/鏈表元素輸入System.out.println(您輸入的鏈表為：);dl.print();調(diào)用print方法,提示操作.System.out.println(請(qǐng)選擇操作項(xiàng)：);dl.choose();調(diào)用choose,選擇操作.while(true)xuanze=sc.nextInt();switch(xuanze)case 1:Syste

12、m.out.println(請(qǐng)輸入要插入的位置下標(biāo)和數(shù)據(jù)：);intidex=sc.nextInt();intdata=sc.nextInt();dl.add(idex,data);dl.print();break;case 2:System.out.println(請(qǐng)輸入要?jiǎng)h除節(jié)點(diǎn)的下標(biāo)：);intidex1=sc.nextInt();dl.remove(idex1);dl.print();break;case 3:System.out.println(請(qǐng)輸入插入第一個(gè)節(jié)點(diǎn)的元素：);intdata1=sc.nextInt();dl.add(0,data1);dl.print();break

13、;case 4:System.out.println(請(qǐng)輸入插入最后位置的元素：);intdata2=sc.nextInt();dl.add(dl.size(),data2);dl.print();break;case 5:dl.inverse();dl.print();break;default:System.out.println(你的輸入有誤,請(qǐng)重新輸入！);break;五、測(cè)試數(shù)據(jù)1、對(duì)每個(gè)函數(shù)的測(cè)試數(shù)據(jù)鏈表中的元素插入為1、2、3、4、5插入第二個(gè)結(jié)點(diǎn)的元素為6刪除第二個(gè)節(jié)點(diǎn)的位置的元素6插入第一個(gè)節(jié)點(diǎn)的元素為7插入最后一個(gè)節(jié)點(diǎn)的元素為6逆置鏈表2、對(duì)程序整體的測(cè)試數(shù)據(jù)輸入元素為1、

14、2、3、4、5的雙向循環(huán)鏈表六、測(cè)試情況請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：5請(qǐng)輸入鏈表的5個(gè)元素：1245您輸入的鏈表為：12345請(qǐng)選擇操作項(xiàng)：1 .插入第i個(gè)節(jié)點(diǎn)2 .刪除第i個(gè)節(jié)點(diǎn)3 .插入第一個(gè)節(jié)點(diǎn)4 .插入最后一個(gè)節(jié)點(diǎn)5 .逆置1請(qǐng)輸入要插入的位置下標(biāo)和數(shù)據(jù):26126345請(qǐng)輸入鏈表的元素的個(gè)數(shù)大于0個(gè)：5請(qǐng)輸入鏈表的5個(gè)元素：12345您輸入的鏈表為：12345請(qǐng)選擇操作項(xiàng)：1 .插入第i個(gè)節(jié)點(diǎn)2 .刪除第i個(gè)節(jié)點(diǎn)3 .插入第一個(gè)節(jié)點(diǎn)4 .插入最后一個(gè)節(jié)點(diǎn)5 .逆置2請(qǐng)輸入要?jiǎng)h除的位置下標(biāo)和數(shù)據(jù)：2612345請(qǐng)輸入鏈表的元素的個(gè)數(shù)大于0個(gè)：5請(qǐng)輸入鏈表的5個(gè)元素：12345您

15、輸入的鏈表為：12345請(qǐng)選擇操作項(xiàng)：1 .插入第i個(gè)節(jié)點(diǎn)2 .刪除第i個(gè)節(jié)點(diǎn)3 .插入第一個(gè)節(jié)點(diǎn)4 .插入最后一個(gè)節(jié)點(diǎn)5 .逆置3請(qǐng)輸入插入第一個(gè)節(jié)點(diǎn)的元素：7712345請(qǐng)輸入鏈表的元素的個(gè)數(shù)大于0個(gè)：5請(qǐng)輸入鏈表的5個(gè)元素：12345您輸入的鏈表為：12345請(qǐng)選擇操作項(xiàng)：1 .插入第i個(gè)節(jié)點(diǎn)2 .刪除第i個(gè)節(jié)點(diǎn)3 .插入第一個(gè)節(jié)點(diǎn)4 .插入最后一個(gè)節(jié)點(diǎn)5 .逆置4請(qǐng)輸入插入最后位置的元素：6請(qǐng)輸入鏈表的元素的個(gè)數(shù)5請(qǐng)輸入鏈表的5個(gè)元素:12345您輸入的鏈表為：12345請(qǐng)選擇操作項(xiàng)：1 .插入第i個(gè)節(jié)點(diǎn)2 .刪除第i個(gè)節(jié)點(diǎn)3 .插入第一個(gè)節(jié)點(diǎn)4 .插入最后一個(gè)節(jié)點(diǎn)5 .逆置5大于0個(gè)

16、：54321樹(shù)的創(chuàng)立及相關(guān)操作的實(shí)現(xiàn)一、問(wèn)題描述2、遍歷方法舉例：先序遍歷：ABDCEF層次遍歷：ABCDEF二、數(shù)據(jù)結(jié)構(gòu)針對(duì)所處理的樹(shù)：1、畫(huà)出存儲(chǔ)結(jié)構(gòu)Leftdataright2、使用所選用語(yǔ)言的功能,實(shí)現(xiàn)上述的該存儲(chǔ)結(jié)構(gòu)publicstaticclassBTNodeprivateAnyTypedata;privateBTNodeparent;privateBTNodeleftNode;privateBTNoderightNode;三、邏輯設(shè)計(jì)1、總體思路首先建立節(jié)點(diǎn)類,然后構(gòu)造BinaryTree(),再構(gòu)造先序遍歷建樹(shù)方法,層次遍歷建樹(shù)方法,層次遍歷樹(shù)的方法,統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)方法,交換

17、子樹(shù)方法,再調(diào)試.2、模塊劃分(以圖示的方法給出各個(gè)函數(shù)的調(diào)用關(guān)系)/1.先序遍歷建樹(shù)publicBiTModecreatTree(AnyType(a)returnroouNade=creacSinaryTree(a);privateBiTNodecreatBinaryTree(AnyTypea)Bj.TNodep=null;if(countLength)AnyTypedataacount;count+;if(data?=null)p=newBiTNode(AnyType)data);p.left=creatTre(a);p.right=creatTxee(a);retnrnp;pin先序建樹(shù)

18、:a,工l,mi工工,null,Fl,e,null,nu工,W);bt.creatTree(charsPre);pin(層序遍歷結(jié)果：)；bt.pathOrder();privateBiTNodecreatBinaryTree(AnyTypea)BiTNodep=null;if(counta.length)AnyTypudata-acount;count+;if(data!=null)p=newBiTNode(AnyType)data);p.left=creatTree(a);p.right=creatTree(a);returnp;pin(層序建樹(shù)：(a,dmill,e,);creatPat

19、hTree(charsPath);先序遍歷結(jié)果：)；bt.preOrder();pln(r,)j2.實(shí)現(xiàn)二叉樹(shù)的層次遍歷publicvoidpathOrder()if(rootNode!=null)pathOrder(rootNode);)publicvoidpathOrder(giTNodet)QueueBiTNodeAnyTypeq=newLinkedLis3BiTNodeAnyType();q.offer(t);while(Jq.isEmpry()if(q.element().left!=null)q.offer(q.element().left);if(q.element().righ

20、t!=null)q.offer(q.element().right);Syot;cin.out.prin(q.poll().daca+|p2h(層序遍歷結(jié)!bt.pathOrder();4.將二叉樹(shù)左+右子樹(shù)相互交換(遞歸)publicvoidexchangeTree()if(rootNode!=null)exchangeTree(rootNode);)privateBiTNodeexchangeTree(BiTNodet)if(t!=null)BiTNodep=t.right;t.right=t.left;t.left=p;exchangeTree(t.right);exchangeTree

21、(t.left);returnz;)、II/C.vr-*)；pin(交短后后次遍歷結(jié)果：bt.exchangeTree();bt.pathOrder();pin(nr,);3、函數(shù)或類的具體定義和功能BiTNode()/節(jié)點(diǎn)類定義publicBiTNodecreatTree(AnyTypea)/先序建樹(shù)方法定義privatevoidcreatPathBinaryTree(AnyTypea)/層次遍歷建樹(shù)定義publicvoidpathOrder()/層次遍歷方法定義publicintcountLeafNode()/統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)方法定義四、編碼1.結(jié)點(diǎn)類定義packagekcsj;publi

22、cclassBiTNodeimplementsComparableBiTNodeAnyTypedata;BiTNodeleft,right;intweight;BiTNode()data=null;left=right=null;BiTNode(AnyTypethedata)data=thedata;left=right=null;BiTNode(AnyTypethedata,BiTNodelt,BiTNodert)data=thedata;left=lt;right=rt;publicBiTNodegetLeft()returnleft;publicBiTNodegetRight()retu

23、rnright;publicObjectgetData()returndata;)publicdoublegetWight()returnweight;)OverridepublicintcompareTo(BiTNodeo)if(o.getWight()this.getWight()return1;if(o.getWight()this.getWight()return-1;return0;)2.BinaryTree()構(gòu)造packagekcsj;importjava.util.LinkedList;importjava.util.Queue;publicclassBinaryTreeAny

24、TypeextendsComparableAnyType口pre,in;BiTNoderootNode=newBiTNode();intcount=0;publicBinaryTree()rootNode=null;)publicBinaryTree(AnyTyperootNodeItem)rootNode.data=rootNodeItem;rootNode.left=rootNode.right=null)publicBinaryTree(BiTNodet)rootNode=t;)/1.先序遍歷建樹(shù)publicBiTNodecreatTree(AnyTypea)returnrootNode

25、=creatBinaryTree(a);privateBiTNodecreatBinaryTree(AnyTypea)BiTNodep=null;if(counta.length)AnyTypedata=acount;count+;if(data!=null)p=newBiTNode(AnyType)data);p.left=creatTree(a);p.right=creatTree(a);returnp;/1.層次遍歷排序建樹(shù)publicvoidcreatPathTree(AnyTypea)if(a!=null)creatPathBinaryTree(a);privatevoidcreat

26、PathBinaryTree(AnyTypea)QueueBiTNodeq=newLinkedListBiTNode();BiTNodenode=newBiTNode(a0);rootNode=node;q.offer(node);inti=1;while(ia.length)if(ai!=null)node=newBiTNode(ai);q.element().left=node;q.offer(q.element().left);if(ia.length-1)if(a+i!=null)node=newBiTNode(ai);q.element().right=node;q.offer(q.

27、element().right);q.poll();i+;/2.實(shí)現(xiàn)二叉樹(shù)的層次遍歷publicvoidpathOrder()if(rootNode!=null)pathOrder(rootNode);publicvoidpathOrder(BiTNodet)QueueBiTNodeq=newLinkedListBiTNode();q.offer(t);while(!q.isEmpty()if(q.element().left!=null)q.offer(q.element().left);if(q.element().right!=null)q.offer(q.element().right

28、);System.out.print(q.poll().data+);/先序遍歷publicvoidpreOrder()if(rootNode!=null)preOrder(rootNode);privatevoidpreOrder(BiTNodet)if(t!=null)System.out.print(t.data+);preOrder(t.left);preOrder(t.right);)/統(tǒng)計(jì)節(jié)點(diǎn)的個(gè)數(shù)publicintcountNode()returncountNode(rootNode);)privateintcountNode(BiTNodet)intm,n;if(t=null)

29、return0;m=countNode(t.left);n=countNode(t.right);returnm+n+1;)/3.統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)(遞歸)publicintcountLeafNode()returncountLeafNode(rootNode);)privateintcountLeafNode(BiTNodet)intm=0,n=0;if(t=null)return0;if(t.left=null&t.right=null)return1;)m=countLeafNode(t.left);n=countLeafNode(t.right);returnm+n;)/4.將二叉樹(shù)左+

30、右子樹(shù)相互交換(遞歸)publicvoidexchangeTree()if(rootNode!=null)exchangeTree(rootNode);privateBiTNodeexchangeTree(BiTNodet)if(t!=null)BiTNodep=t.right;t.right=t.left;t.left=p;exchangeTree(t.right);exchangeTree(t.left);)returnt;)/計(jì)算樹(shù)的深度publicintdepth()returndepth(rootNode);)privateintdepth(BiTNodet)/返回二叉樹(shù)的深度int

31、depthleft,depthright;if(t=null)return0;depthleft=depth(t.left);depthright=depth(t.right);returnMath.ma/depthleft,depthright)+1;)/橫向輸出樹(shù)狀圖publicvoidshowTree(BiTNodet,intn)if(t=null)return;showTree(t.right,+n);for(inti=0;in;i+)System.out.print();System.out.print(t.data+n);showTree(t.left,n+);3.測(cè)試函數(shù)pack

32、agekcsj;publicclassTestpublicstaticvoidpln(Objecto)System.out.println(o);publicstaticvoidmain(String口args)BinaryTreebt=newBinaryTree();Character口charsPre=a,b,d,null,null,null,c,enull,null,f;Character口charsPath=a,b,c,d,null,e,f;pln(先序建樹(shù)：a,b,d,null,null,null,c,e,null,null,f);bt.creatTree(charsPre);pln(層序遍歷結(jié)果：)；bt.pathOrder();pln();pln(樹(shù)圖為(橫向)：);bt.showTree(bt.rootNode,1);pln();pln(層序建樹(shù)：a,b,c,d,null,e,f);bt.creatPathTree(char