雙向循環(huán)鏈表的創(chuàng)建與相關(guān)操作的實(shí)現(xiàn)課程設(shè)計(jì)說(shuō)明書(shū)

1、山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(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é)院專(zhuān) 業(yè)： 網(wǎng)絡(luò)工程班 級(jí)： 網(wǎng)絡(luò)101學(xué)生： 王天未學(xué) 號(hào)： 2010111200指導(dǎo)教師： 伊靜完成日期：2013-7-628 / 29 目 錄課程設(shè)計(jì)任務(wù)書(shū)1III課程設(shè)計(jì)任務(wù)書(shū)2IV雙向循環(huán)鏈表的創(chuàng)建與相關(guān)操作的實(shí)現(xiàn)6一、問(wèn)題描述6二、數(shù)據(jù)結(jié)構(gòu)6三、邏輯設(shè)計(jì)7四、編碼8五、 測(cè)試數(shù)據(jù)13六、測(cè)試情況13樹(shù)的創(chuàng)建與相關(guān)操作的實(shí)現(xiàn)17一、問(wèn)題描述17二、數(shù)據(jù)結(jié)構(gòu)17三、邏輯設(shè)計(jì)18四、編碼21五、 測(cè)試數(shù)據(jù)28六、測(cè)試情況28結(jié) 論30參

2、考文獻(xiàn)31課程設(shè)計(jì)指導(dǎo)教師評(píng)語(yǔ)32山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(shè)計(jì)任務(wù)書(shū)1設(shè)計(jì)題目雙向循環(huán)鏈表的創(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ì)容與步驟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%指導(dǎo)教師（簽字）： 教研室主任（簽字）山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(shè)計(jì)任務(wù)書(shū)2設(shè)計(jì)題目樹(shù)的創(chuàng)建與相關(guān)操作的實(shí)現(xiàn)

3、已知技術(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ì)容與步驟1.建立結(jié)點(diǎn)類(lèi)2.構(gòu)造BinaryTree（）3.建立線序遍歷樹(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

4、%3、成果展示30%指導(dǎo)教師（簽字）： 教研室主任（簽字）雙向循環(huán)鏈表的創(chuàng)建與相關(guān)操作的實(shí)現(xiàn)一、問(wèn)題描述 a0 a1 a2 a3 a41、每個(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)針對(duì)所處理的樹(shù)：1、畫(huà)出雙向循環(huán)鏈表的存儲(chǔ)結(jié)構(gòu) prev data next2、使用所選用語(yǔ)言的功能，描述該存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)private static class Node<AnyType> AnyType data;Node<AnyType> prev;Node<AnyType> next;三、邏輯設(shè)計(jì)1、總體思路對(duì)于雙向循

5、環(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)系）建立一個(gè)空表刪除節(jié)點(diǎn)插入節(jié)點(diǎn)逆置主函數(shù)3、函數(shù)或類(lèi)的具體定義和功能 class Node<AnyType>/節(jié)點(diǎn)類(lèi)定義public class DlList < AnyType>/循環(huán)鏈表主類(lèi)public boolean add(int idex, AnyType x)/鏈表插入操作public AnyType remove(

6、int idex )/鏈表刪除操作private void inverse()/鏈表逆置四、編碼import java.util.Scanner;class Node<AnyType>public AnyType data;public Node<AnyType> prev;public Node<AnyType> next;public Node()data=null;prev=null;next=null; public Node(AnyType d)data=d;prev=null;next=null; public Node(AnyType d,No

7、de<AnyType> p,Node<AnyType> n)data=d;prev=p;next=n; /節(jié)點(diǎn)類(lèi)publicclass DlList < AnyType>private Node<AnyType> headNode=new Node<AnyType>(); /頭標(biāo)記或頭節(jié)點(diǎn)privateinttheSize;/長(zhǎng)度public DlList()headNode.next=headNode;headNode.prev=headNode;theSize=0; /創(chuàng)建一個(gè)空表publicint size()returnthe

8、Size; /設(shè)定表的長(zhǎng)度publicboolean add(AnyType x) add(theSize, x);returntrue;/鏈表輸入操作publicboolean add(int idex, AnyType x) boolean flag;if (idex < 0 | idex > theSize) /判斷插入的位置是否大于0System.out.println("您輸入的要插入元素的位置不正確!");flag = false; elseflag = true;if (flag) Node<AnyType> p;p = getNode

9、(idex);addBefore(p, x);/插入操作return flag;privatevoid addBefore(Node<AnyType> p, AnyType x) Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);newNode.prev.next = newNode;p.prev = newNode;theSize+;/插入方法public AnyType remove(int idex ) return remove(getNode(idex); private AnyType

10、 remove( Node<AnyType> p ) p.prev.next=p.next; p.next.prev=p.prev;theSize-;return p.data; /刪除操作privatevoid inverse() Node<AnyType> p,q,l; p=headNode.next; q=p.next;while(p!=headNode)l=q.next;/空置的中轉(zhuǎn)結(jié)點(diǎn)賦值q.next=p;/將p、q鏈表的前后域置換。q由p的后域變成前域p.prev=q;p=q;/置換后，將各個(gè)結(jié)點(diǎn)置換輸出。q=l; q.next=p; p.prev=q;/當(dāng)

11、p為頭結(jié)點(diǎn)時(shí)，直接將前后域置換。 /逆置private Node<AnyType> getNode(int idex)Node<AnyType> p;if(idex<0|idex>size()thrownew IndexOutOfBoundsException("getNode idex:"+idex+"size:"+size();if(idex<size()/2) p=headNode;for(int i=0;i<=idex;i+) p=p.next; elsep=headNode;for(int i=s

12、ize();i>idex;i-)p=p.prev;return p; /查找結(jié)點(diǎn)位置publicvoid print()for(int i=0;i<this.theSize;i+) System.out.print(getNode(i).data+" "); System.out.println(); /結(jié)果輸出publicvoid choose() System.out.println("1.插入第i個(gè)節(jié)點(diǎn)"); System.out.println("2.刪除第i個(gè)節(jié)點(diǎn)"); System.out.println(&q

13、uot;3.插入第一個(gè)節(jié)點(diǎn)"); System.out.println("4.插入最后一個(gè)節(jié)點(diǎn)"); System.out.println("5.逆置"); /選擇操作項(xiàng)publicstaticvoid main(String args) DlList<Integer> dl=new DlList<Integer>(); Scanner sc=new Scanner(System.in);int xuanze; System.out.println("請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：");int

14、n=sc.nextInt(); System.out.println("請(qǐng)輸入鏈表的"+n+"個(gè)元素：");for(int i=1;i<=n;i+)int l=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.nextI

15、nt();switch(xuanze)case 1: System.out.println("請(qǐng)輸入要插入的位置下標(biāo)和數(shù)據(jù)：");int idex=sc.nextInt();int data=sc.nextInt(); dl.add(idex, data); dl.print();break;case 2: System.out.println("請(qǐng)輸入要?jiǎng)h除節(jié)點(diǎn)的下標(biāo)：");int idex1=sc.nextInt(); dl.remove(idex1); dl.print();break;case 3: System.out.println(&quo

16、t;請(qǐng)輸入插入第一個(gè)節(jié)點(diǎn)的元素：");int data1=sc.nextInt(); dl.add(0,data1); dl.print();break;case 4: System.out.println("請(qǐng)輸入插入最后位置的元素：");int data2=sc.nextInt(); dl.add(dl.size(), data2); dl.print();break;case 5: dl.inverse(); dl.print();break;default: System.out.println("你的輸入有誤，請(qǐng)重新輸入！");bre

17、ak; 5、 測(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、2、3、4、5的雙向循環(huán)鏈表六、測(cè)試情況請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：5請(qǐng)輸入鏈表的5個(gè)元素：12345您輸入的鏈表為：1 2 3 4 5 請(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ù)：261 2 6 3 4 5請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：5請(qǐng)輸入鏈表的5個(gè)元素：12345

18、您輸入的鏈表為：1 2 3 4 5 請(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ù)：261 2 3 4 5請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：5請(qǐng)輸入鏈表的5個(gè)元素：12345您輸入的鏈表為：1 2 3 4 5 請(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)的元素：77 1 2 3 4 5請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：5請(qǐng)輸入鏈表的5個(gè)元素：12345您輸入的鏈表為：1 2 3 4 5 請(qǐng)選擇操作項(xiàng)：1.插入第i個(gè)節(jié)點(diǎn)2.刪除第i個(gè)節(jié)點(diǎn)3

19、.插入第一個(gè)節(jié)點(diǎn)4.插入最后一個(gè)節(jié)點(diǎn)5.逆置4請(qǐng)輸入插入最后位置的元素：61 2 3 4 5 6 請(qǐng)輸入鏈表的元素的個(gè)數(shù)(大于0個(gè))：5請(qǐng)輸入鏈表的5個(gè)元素：12345您輸入的鏈表為：1 2 3 4 5 請(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.逆置55 4 3 2 1 樹(shù)的創(chuàng)建與相關(guān)操作的實(shí)現(xiàn)一、問(wèn)題描述A1.先遍序遍歷建樹(shù)CBNULLEFDNULLNULLNULLNULL2、 遍歷方法舉例：先序遍歷 ：A BD CEF層次遍歷 ：A BC DEF二、數(shù)據(jù)結(jié)構(gòu)針對(duì)所處理的樹(shù)：1、畫(huà)出存儲(chǔ)結(jié)構(gòu) Left data right 2、使用所選用語(yǔ)言

20、的功能，實(shí)現(xiàn)上述的該存儲(chǔ)結(jié)構(gòu)public static class BTNode<AnyType> private AnyType data;private BTNode<AnyType> parent;private BTNode<AnyType> leftNode;private BTNode<AnyType> rightNode;三、邏輯設(shè)計(jì)1、總體思路首先建立節(jié)點(diǎn)類(lèi)，然后構(gòu)造BinaryTree（），再構(gòu)造先序遍歷建樹(shù)方法，層次遍歷建樹(shù)方法，層次遍歷樹(shù)的方法，統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)方法，交換子樹(shù)方法，再調(diào)試。2、 模塊劃分（以圖示的方法給出各個(gè)

21、函數(shù)的調(diào)用關(guān)系）3、 函數(shù)或類(lèi)的具體定義和功能 BiTNode()/節(jié)點(diǎn)類(lèi)定義 public BiTNode<AnyType> creatTree(AnyType a)/先序建樹(shù)方法定義 privatevoid creatPathBinaryTree(AnyType a)/層次遍歷建樹(shù)定義publicvoid pathOrder()/層次遍歷方法定義publicint countLeafNode()/ 統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)方法定義四、編碼1.結(jié)點(diǎn)類(lèi)定義package kcsj;publicclass BiTNode<AnyType> implements Comparabl

22、e<BiTNode<AnyType>> AnyType data;BiTNode<AnyType> left, right;intweight;BiTNode() data = null;left = right = null;BiTNode(AnyType thedata) data = thedata;left = right = null;BiTNode(AnyType thedata, BiTNode<AnyType> lt, BiTNode<AnyType> rt) data = thedata;left = lt;righ

23、t = rt;public BiTNode<AnyType> getLeft() returnleft;public BiTNode<AnyType> getRight() returnright;public Object getData() returndata;publicdouble getWight() returnweight;Overridepublicint compareTo(BiTNode<AnyType> o) if (o.getWight() > this.getWight()return 1;if (o.getWight()

24、< this.getWight()return -1;return 0;2. BinaryTree()構(gòu)造package kcsj;import java.util.LinkedList;import java.util.Queue;publicclass BinaryTree<AnyType extends Comparable<? super AnyType>> AnyType pre, in;BiTNode<AnyType> rootNode = newBiTNode<AnyType>();intcount = 0;public Bi

25、naryTree() rootNode = null;public BinaryTree(AnyType rootNodeItem) rootNode.data = rootNodeItem;rootNode.left = rootNode.right = null;public BinaryTree(BiTNode<AnyType> t) rootNode = t;/1. 先序遍歷建樹(shù)publicBiTNode<AnyType> creatTree(AnyType a) returnrootNode = creatBinaryTree(a);privateBiTNod

26、e<AnyType> creatBinaryTree(AnyType a) BiTNode<AnyType> p = null;if (count < a.length) AnyType data = acount;count+;if (data != null) p = newBiTNode<AnyType>(AnyType) data);p.left = creatTree(a);p.right = creatTree(a);return p;/1.層次遍歷排序建樹(shù)publicvoid creatPathTree(AnyType a) if (a

27、!= null) creatPathBinaryTree(a);privatevoid creatPathBinaryTree(AnyType a) Queue<BiTNode<AnyType>> q = new LinkedList<BiTNode<AnyType>>();BiTNode<AnyType> node = newBiTNode<AnyType>(a0);rootNode = node;q.offer(node);int i = 1;while (i < a.length) if (ai != null

28、) node = newBiTNode<AnyType>(ai);q.element().left = node;q.offer(q.element().left);if (i < a.length - 1) if (a+i != null) node = newBiTNode<AnyType>(ai);q.element().right = node;q.offer(q.element().right);q.poll();i+;/2.實(shí)現(xiàn)二叉樹(shù)的層次遍歷publicvoid pathOrder() if (rootNode != null)pathOrder(r

29、ootNode);publicvoid pathOrder(BiTNode<AnyType> t) Queue<BiTNode<AnyType>> q = new LinkedList<BiTNode<AnyType>>();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);System.out.pri

30、nt(q.poll().data + " ");/ 先序遍歷publicvoid preOrder() if (rootNode != null)preOrder(rootNode);privatevoid preOrder(BiTNode<AnyType> t) if (t != null) System.out.print(t.data+" ");preOrder(t.left); preOrder(t.right);/ 統(tǒng)計(jì)節(jié)點(diǎn)的個(gè)數(shù)publicint countNode() return countNode(rootNode);pri

31、vateint countNode(BiTNode<AnyType> t) int m, n;if (t = null)return 0;m = countNode(t.left);n = countNode(t.right);return m + n + 1;/ 3.統(tǒng)計(jì)葉子節(jié)點(diǎn)個(gè)數(shù)（遞歸）publicint countLeafNode() return countLeafNode(rootNode);privateint countLeafNode(BiTNode<AnyType> t) int m = 0, n = 0;if (t = null)return 0;

32、if (t.left = null && t.right = null) return 1;m = countLeafNode(t.left);n = countLeafNode(t.right);return m + n;/ 4.將二叉樹(shù)左+右子樹(shù)相互交換（遞歸）publicvoid exchangeTree() if (rootNode != null) exchangeTree(rootNode);privateBiTNode<AnyType> exchangeTree(BiTNode<AnyType> t) if (t != null) BiTN

33、ode<AnyType> p = t.right;t.right = t.left;t.left = p;exchangeTree(t.right);exchangeTree(t.left);return t;/ 計(jì)算樹(shù)的深度publicint depth() return depth(rootNode);privateint depth(BiTNode<AnyType> t) / 返回二叉樹(shù)的深度int depthleft, depthright;if (t = null)return 0;depthleft = depth(t.left);depthright =

34、depth(t.right);return Math.max(depthleft, depthright) + 1;/橫向輸出樹(shù)狀圖publicvoid showTree(BiTNode<AnyType> t,int n)if (t=null) return; showTree(t.right,+n);for (int i = 0; i < n; i+) System.out.print(" ");System.out.print(t.data+"n"); showTree(t.left,n+);3. 測(cè)試函數(shù)package kcsj;

35、publicclass Test publicstaticvoid pln(Object o) System.out.println(o);publicstaticvoid main(String args) BinaryTree<Character> bt = new BinaryTree<Character>();Character charsPre = 'a', 'b', 'd', null, null, null, 'c', 'e',null, null, 'f' ;

36、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(" &

37、quot;);pln("樹(shù)圖為(橫向)：");bt.showTree(bt.rootNode, 1);pln(" ");pln("層序建樹(shù)：'a','b','c','d',null,'e','f'");bt.creatPathTree(charsPath);pln("先序遍歷結(jié)果：");bt.preOrder();pln(" ");pln("樹(shù)圖為(橫向)：");bt.showTree(bt.rootNode, 1);pln(" ");pln("葉子節(jié)點(diǎn)數(shù)：" +