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

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

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

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

4、針對所處理的樹：1、畫出雙向循環(huán)鏈表的存儲結(jié)構(gòu)prevdlatanext2、使用所選用語言的功能,描述該存儲結(jié)構(gòu)的實現(xiàn)privatestaticclassNodeAnyTypedata;Nodeprev;Nodenext;三、邏輯設(shè)計1、總體思路對于雙向循環(huán)鏈表,建立一個空表,然后實現(xiàn)雙向循環(huán)鏈表的插入,刪除操作.為了便于逆置的操作,選擇建立一個帶頭節(jié)點的雙向循環(huán)鏈表,插入第一個節(jié)點和插入最后一個節(jié)點,只需要在0號位置和size()位置插入節(jié)點就行.2、模塊劃分(以圖示的方法給出各個函數(shù)的調(diào)用關(guān)系)3、函數(shù)或類的具體定義和功能classNode/節(jié)點類定義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é)點類publicclassDlListprivateNodeheadNode=newNode();/頭標(biāo)記或頭節(jié)點privateinttheSize;/長度publicDlList()headNodenext=headNodeheadNodeprev=headNodetheSize=0;/創(chuàng)立一個空表publicintsize()returntheSize;設(shè)定表的長度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é)點賦值r. next=p;將p、q鏈表的前后域置換.q由p的后域變成前域p. prev=q;p=q;/置換后,將各個結(jié)點置換輸出.q

9、=l;q. next=p;p.prev=q;/當(dāng)p為頭結(jié)點時,直接將前后域置換/逆置privateNodegetNode(intidex)Nodep;if(idexsize()thrownewIndexOutOfBoundsException(getNodeidex:+idex+;size:+size();if(idexsize()/2)p=headNodefor(inti=0;iidex;i-)p=p.prev;returnp;/查找結(jié)點位置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(/選擇操作項1.插入第i個節(jié)點；2.刪除第i個節(jié)點；3.插入第一個節(jié)點;4.插入最后一個節(jié)點;5.逆置；publicstaticvoidmain(String口args)DlListdl=newDlList();Scannersc=newScanner(System.in);intxuanze;System.out

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

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

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

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

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

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

17、子樹方法,再調(diào)試.2、模塊劃分(以圖示的方法給出各個函數(shù)的調(diào)用關(guān)系)/1.先序遍歷建樹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先序建樹

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(層序建樹：(a,dmill,e,);creatPat

19、hTree(charsPath);先序遍歷結(jié)果：)；bt.preOrder();pln(r,)j2.實現(xiàn)二叉樹的層次遍歷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.將二叉樹左+右子樹相互交換(遞歸)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é)點類定義publicBiTNodecreatTree(AnyTypea)/先序建樹方法定義privatevoidcreatPathBinaryTree(AnyTypea)/層次遍歷建樹定義publicvoidpathOrder()/層次遍歷方法定義publicintcountLeafNode()/統(tǒng)計葉子節(jié)點個數(shù)方法定義四、編碼1.結(jié)點類定義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.先序遍歷建樹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.層次遍歷排序建樹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.實現(xiàn)二叉樹的層次遍歷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)計節(jié)點的個數(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)計葉子節(jié)點個數(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.將二叉樹左+

30、右子樹相互交換(遞歸)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;)/計算樹的深度publicintdepth()returndepth(rootNode);)privateintdepth(BiTNodet)/返回二叉樹的深度int

31、depthleft,depthright;if(t=null)return0;depthleft=depth(t.left);depthright=depth(t.right);returnMath.ma/depthleft,depthright)+1;)/橫向輸出樹狀圖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.測試函數(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(先序建樹：a,b,d,null,null,null,c,e,null,null,f);bt.creatTree(charsPre);pln(層序遍歷結(jié)果：)；bt.pathOrder();pln();pln(樹圖為(橫向)：);bt.showTree(bt.rootNode,1);pln();pln(層序建樹：a,b,c,d,null,e,f);bt.creatPathTree(char