數(shù)據(jù)結(jié)構(gòu)Java版復(fù)習(xí)題解答

1、第 0章 Java 程序設(shè)計(jì)基礎(chǔ) 1第1章緒論第2章線性表第3章第4章習(xí) 0.1 】 習(xí) 0.2 】 習(xí) 0.3 】 習(xí) 0.4 】 習(xí) 0.5 】 習(xí) 0.6 】 習(xí) 0.7 】實(shí)驗(yàn) 0.1 實(shí)驗(yàn) 0.2 實(shí)驗(yàn) 0.3 實(shí)驗(yàn) 0.4 實(shí)驗(yàn) 0.5 實(shí)驗(yàn) 0.6 實(shí)驗(yàn) 0.8哥德巴赫猜想。 楊輝三角形。 金額的中文大寫形式。 下標(biāo)和相等的數(shù)字方陣。 找出一個二維數(shù)組的鞍點(diǎn) 復(fù)數(shù)類。 . 圖形接口與實(shí)現(xiàn)圖形接口的類 習(xí) 1.1 】 實(shí)驗(yàn) 1.1 判斷數(shù)組元素是否已按升序排序。習(xí) 1.2 】 實(shí)驗(yàn) 1.3 用遞歸算法求兩個整數(shù)的最大公因數(shù)。習(xí) 2.1 】習(xí) 2.2 】習(xí) 2.3 】習(xí) 2.4 】習(xí)

2、 2.5 】習(xí) 2.6 】習(xí) 2.7 】習(xí) 2.8 】習(xí) 2.9 】習(xí) 2.10 】習(xí) 2.11 】棧和隊(duì)列 .么？習(xí)2-5 圖2.19 的數(shù)據(jù)結(jié)構(gòu)聲明。習(xí) 2-6 如果在遍歷單鏈表時，將 p=p.next 語句寫成 p.next=p ，結(jié)果會怎樣？ 實(shí)驗(yàn) 2.2由指定數(shù)組中的多個對象構(gòu)造單鏈表。實(shí)驗(yàn) 2.2實(shí)驗(yàn) 2.2實(shí)驗(yàn) 2.2實(shí)驗(yàn) 2.2實(shí)驗(yàn) 2.2單鏈表的查找、包含、刪除操作詳見 單鏈表的替換操作。 首尾相接地連接兩條單鏈表。復(fù)制單鏈表。8.2.1 。單鏈表構(gòu)造、復(fù)制、比較等操作的遞歸方法。建立按升序排序的單鏈表(不帶頭結(jié)點(diǎn))。 實(shí)驗(yàn) 2.6 帶頭結(jié)點(diǎn)的循環(huán)雙鏈表類，實(shí)現(xiàn)線性表接口。實(shí)

3、驗(yàn) 2.5 建立按升序排序的循環(huán)雙鏈表。 習(xí) 3.1 】 習(xí) 3-5 棧和隊(duì)列有何異同？17習(xí) 3.2 】 能否將棧聲明為繼承線性表，入棧方法是add(0,e)習(xí) 3.3 】 能否用一個線性表作為棧的成員變量，入棧方法是remove(0) ？為什么？ 【習(xí)3.4 】 能否將隊(duì)列聲明為繼承線性表，入隊(duì)方法是 add(e)么？18習(xí) 4.1 】 實(shí)驗(yàn) 4.6 找出兩個字符串中所有共同的字符。，出棧方法是 remove(0)add(0,e) ，出棧方法是，出隊(duì)方法是 remove(0)1111222101417為什1717為什1718【習(xí)4.2】 習(xí)4-9(1) 已知目標(biāo)串為abbaba、模式串為a

4、ba，畫出其KM算法的匹配過程,并給出比較次數(shù)。 【習(xí) 4.3 】 習(xí)4-9(2) 已知 target=ababaab 、 pattern=aab ，求模式串的 next 數(shù)組，畫出其KM算法的匹配過程，并給出比較次數(shù)。 18第 5章 數(shù)組和廣義表. 20【習(xí) 5.1 】 求一個矩陣的轉(zhuǎn)置矩陣。 20第6章 樹和二叉樹 . 21【習(xí) 6.1 】畫出 3個結(jié)點(diǎn)的各種形態(tài)的樹和二叉樹。 21【習(xí)6.2 】找出分別滿足下面條件的所有二叉樹。 21【習(xí)6.3 】輸出葉子結(jié)點(diǎn)。 . 21【習(xí) 6.4 】求一棵二叉樹的葉子結(jié)點(diǎn)個數(shù)。 22【習(xí) 6.5 】判斷兩棵二叉樹是否相等。 22【習(xí)6.6 】復(fù)制一棵

5、二叉樹。 . 22【習(xí)6.7 】二叉樹的替換操作。 23【習(xí)6.8】后根次序遍歷中序線索二叉樹。 242526第 7章 圖 第 8章 查找【習(xí) 8.1 】實(shí)驗(yàn) 8.1 順序表的查找、刪除、替換、比較操作。 26【習(xí)8.2 】實(shí)驗(yàn)8.2 單鏈表的全部替換操作。 28【習(xí)8.3 】實(shí)驗(yàn)8.2 單鏈表的全部刪除操作。 28【習(xí)8.4 】折半查找的遞歸算法。 29【習(xí)8.5 】二叉排序樹查找的遞歸算法。 30【習(xí)8.6 】二叉排序樹插入結(jié)點(diǎn)的非遞歸算法。 30【習(xí) 8.7 】判斷一棵二叉樹是否為二叉排序樹。 31第9章 排序 33【習(xí) 9.1 】 判斷一個數(shù)據(jù)序列是否為最小堆序列。 33【習(xí)9.2 】

6、 歸并兩條排序的單鏈表。 33【習(xí)9.3 】 說明二叉排序樹與堆的差別。 35圖 0.1 下標(biāo)和相等的數(shù)字方陣算法描述 1圖 2.1 p.next=p 將改變結(jié)點(diǎn)間的鏈接關(guān)系 5圖4.1目標(biāo)串a(chǎn)bbaba和模式串a(chǎn)ba的KM算法模式匹配過程 18圖4.2目標(biāo)串a(chǎn)babaab和模式串a(chǎn)ab的KMF算法模式匹配過程 19圖 6.1 3 個結(jié)點(diǎn)樹和二叉樹的形態(tài) 21圖 6.2 單支二叉樹 21圖 9.2 歸并兩條排序的單鏈表 34表4.1模式串a(chǎn)ab的next數(shù)組19第0章Java程序設(shè)計(jì)基礎(chǔ)【習(xí)0.1】【習(xí)0.2】實(shí)驗(yàn)0.1實(shí)驗(yàn)0.2vr A只亠哥德巴赫猜想。楊輝三角形?！玖?xí)0.3】實(shí)驗(yàn)0.3金額

7、的中文大與形式。【習(xí)0.4】實(shí)驗(yàn)0.4下標(biāo)和相等的數(shù)字方陣。輸出下列方陣（當(dāng)n=4 時）。1267或134103581325911491214681215101115167131416采用二維數(shù)組實(shí)現(xiàn)。二維數(shù)組中，每一條斜線上各兀素下標(biāo)和相等,如圖01230.1所示。左上三角下標(biāo)和為0n-1-亠26 一7yr*358 j131J*14 z49Z1214*/ $10/+1115-416y下標(biāo)和為4下標(biāo)和為52下標(biāo)和為63j1i =0右下三角下標(biāo)和為n2*n-2/階數(shù)k是自然數(shù)，遞增變化/方向向上左上三角，sum表示行列的下標(biāo)和圖0.1下標(biāo)和相等的數(shù)字方陣算法描述程序如下。public class

8、 Upmatpublic static void main(String args)int n=4;int mat = new intnn;int k=1;boolean up = true;for (int sum=0; sum=0; i-) matisum-i = k+;elsefor (int i=0; i=sum; i+)matisum-i = k+;up=!up;for (int sum=n; sum2*n-1; sum+) / if (up)for (int j=sum-n+1; jsum-n; j-) matsum-jj = k+;up=!up;/k 先賦值后自加/ 方向求反右下

9、三角for (int i=0; imat.length; i+)for (int j=0; jmati.length; j+)System.out.print( +matij);System.out.println();/ 輸出二維數(shù)組元素/i 、 j 是行、列下標(biāo)習(xí) 0.5 】 實(shí)驗(yàn) 0.5找出一個二維數(shù)組的鞍點(diǎn)習(xí) 0.6】 實(shí)驗(yàn) 0.6 復(fù)數(shù)類。習(xí) 0.7 】 實(shí)驗(yàn) 0.8 圖形接口與實(shí)現(xiàn)圖形接口的類第1章緒論【習(xí)1.1】 實(shí)驗(yàn)1.1判斷數(shù)組元素是否已按升序排序。程序見例 1.4 的 SortedArray.java 。判斷整數(shù)數(shù)組是否已按升序/若已排序返回true，否則返回falsepu

10、blic static boolean isSorted(int table)/排序if (table=null)return false;for (int i=0; itablei+1)return false;return true;/判斷對象數(shù)組是否已按升序/若已排序返回true，否則返回falsepublic static boolean isSorted(Comparable table)排序if (table=null)return false;for (int i=0; i0)return false;return true;【習(xí)1.2】 實(shí)驗(yàn)1.3用遞歸算法求兩個整數(shù)的最大公因

11、數(shù)。public class Gcdpublic static int gcd(int a, int b)/ 返回 a,b 的最大公因數(shù)，遞歸方法if(b=0)return a;if(a0)return gcd(-a, b);if(b0)return gcd(a, -b);return gcd(b, a%b);public static void main(String args)int a=12, b=18, c=24;獲得 3 個整System.out.println(gcd(+a+,+b+,+c+)=+gcd(gcd(a,b),c); /數(shù)最大公因數(shù)第2章線性表【習(xí)2.1】 習(xí)2-5 圖

12、2.19的數(shù)據(jù)結(jié)構(gòu)聲明。table數(shù)組元素為單鏈表，聲明如下：SinglyLinkedList table【習(xí)2.2】 習(xí)2-6如果在遍歷單鏈表時，將p=p.next語句寫成p.next=p，結(jié)果會怎樣？使p.next指向p結(jié)點(diǎn)自己，改變了結(jié)點(diǎn)間的鏈接關(guān)系，丟失后繼結(jié)點(diǎn)，如圖2.1所示。p圖2.1 p.next=p將改變結(jié)點(diǎn)間的鏈接關(guān)系【習(xí)2.3】 實(shí)驗(yàn)2.2由指定數(shù)組中的多個對象構(gòu)造單鏈表。在SinglyLinkedList單鏈表類中，增加構(gòu)造方法如下。public SinglyLinkedList(E element)/由指定數(shù)組中的多個對象構(gòu)造單鏈表this.head = null;if

13、 (element!=null & element.length0)this.head = new Node(element0);Node rear=this.head;int i=1;while (ivelement.length)rear.next = new Node(elementi+);rear = rear.next;【習(xí)2.4】 實(shí)驗(yàn)2.2單鏈表的查找、包含、刪除操作詳見8.2.1。單鏈表的以下查找、包含、刪除等操作方法詳見8.2.1順序查找。public Node search(E element, Node start) /從單鏈表結(jié)點(diǎn) start 開始順序查找指定對象pub

14、lic Node search(E element) 回 nullpublic boolean contain(E element) 象public boolean remove(E element)/ 若查找到指定對象， 則返回結(jié)點(diǎn)， 否則返/ 以查找結(jié)果判斷單鏈表是否包含指定對/ 移去首次出現(xiàn)的指定對象【習(xí) 2.5】 實(shí)驗(yàn) 2.2 單鏈表的替換操作。 在 SinglyLinkedList 單鏈表類中，增加替換操作方法如下。public boolean replace(Object obj, E element) / 將元素值為 obj 的結(jié)點(diǎn)值替換為 element / 若替換成功返回 t

15、rue ，否則返回 false ， O(n)if (obj=null | element=null) return false;Node p=this.head;while (p!=null)if (obj.equals(p.data)p.data = element; return true; p = p.next; return false;【習(xí) 2.6】 實(shí)驗(yàn) 2.2 首尾相接地連接兩條單鏈表。 在 SinglyLinkedList 單鏈表類中，增加替換操作方法如下。public void concat(SinglyLinkedList list)/ 將指定單鏈表 list 鏈接在當(dāng)前單

16、鏈表之后if (this.head=null) this.head = list.head;elseNode p=this.head; while (p.next!=null) p = p.next;p.next = list.head;【習(xí) 2.7】 實(shí)驗(yàn) 2.2 復(fù)制單鏈表。在 SinglyLinkedList 單鏈表類中，增加構(gòu)造方法如下。public SinglyLinkedList(SinglyLinkedList list)/ 以單鏈表 list 構(gòu)造新的單鏈表 / 復(fù)制單鏈表this.head = null;if (list!=null & list.head!=null)thi

17、s.head = new Node(list.head.data);Node p = list.head.next;Node rear = this.head;while (p!=null)rear.next = new Node(p.data);rear = rear.next;p = p.next;【習(xí) 2.8】 實(shí)驗(yàn) 2.2 單鏈表構(gòu)造、復(fù)制、比較等操作的遞歸方法。 由指定數(shù)組中的多個對象構(gòu)造單鏈表的操作也可設(shè)計(jì)為以下的遞歸方法：public SinglyLinkedList(E element)/ 由指定數(shù)組中的多個對象構(gòu)造單鏈表this.head = null;if (element

18、!=null)this.head = create(element,0);private Node create(E element, int i)/ 由指定數(shù)組構(gòu)造單鏈表，遞歸方法Node p=null;if (ielement.length)p = new Node(elementi);p.next = create(element, i+1); return p; 單鏈表的復(fù)制操作也可設(shè)計(jì)為以下的遞歸方法： public SinglyLinkedList(SinglyLinkedList list) / 表 this.head = copy(list.head);private Node

19、 copy(Node p)Node q=null;if (p!=null)q = new Node(p.data); q.next = copy(p.next); return q; 比較兩條單鏈表是否相等的操作也可設(shè)計(jì)為以下的遞歸方法： public boolean equals(Object obj)if (obj = this) return true;if (obj instanceof SinglyLinkedList)SinglyLinkedList list = (SinglyLinkedList)obj; return equals(this.head, list.head);

20、return false;private boolean equals(Node p, Node q) 等，遞歸方法 if (p=null & q=null) return true;以單鏈表 list 構(gòu)造新的單鏈/ 復(fù)制單鏈表，遞歸方法/ 比較兩條單鏈表是否相等/ 比較兩條單鏈表是否相if (p!=null & q!=null) return p.data.equals(q.data) & equals(p.next, q.next); return false;【習(xí) 2.9】 建立按升序排序的單鏈表(不帶頭結(jié)點(diǎn)) 。 采用直接插入排序算法將一個結(jié)點(diǎn)插入到已排序的單鏈表中。import d

21、ataStructure.linearList.Node;import dataStructure.linearList.SinglyLinkedList;public class SortedSinglyLinkedList extends SinglyLinkedList public SortedSinglyLinkedList()super();public boolean add(E element)/適位置if (element=null | !(element instanceof Comparable)return false;/對象Comparable cmp = (Comp

22、arable)element;if (this.head=null | pareTo(this.head.data)=0)this.head = new Node(element,this.head);elseNode front=null, p=this.head;while (p!=null & pareTo(p.data)0)front = p;p = p.next;front.next = new Node(element, p);return true;public static void main(String args)/ 不帶頭結(jié)點(diǎn)的單鏈表類根據(jù)指定

23、對象的大小插入在合不能插入 null 或非 Comparable/ 頭插入/front 是 p 的前驅(qū)結(jié)點(diǎn)/ 中間 / 尾插入SortedSinglyLinkedListlist = new SortedSinglyLinkedList();int n=10;System.out.print(insertfor (int i=0; in; i+)int k = (int) (Math.random()*100);/if (list.add(new Integer(k)System.out.print(k+ );System.out.println(nlist: +list.toString()

24、; 程序多次運(yùn)行結(jié)果如下：insert ： 22 48 50 9 71 71 19 67 50 80 list: (9, 19, 22, 48, 50, 50, 67, 71, 71, 80)insert ： 42 33 52 89 13 11 50 29 78 34 list: (11, 13, 29, 33, 34, 42, 50, 52, 78, 89);產(chǎn)生隨機(jī)數(shù)insert ： 69 16 99 0 20 68 14 73 90 76 list1: (0, 14, 16, 20, 68, 69, 73, 76, 90, 99)習(xí) 2.10】 實(shí)驗(yàn) 2.6 帶頭結(jié)點(diǎn)的循環(huán)雙鏈表類，實(shí)現(xiàn)

25、線性表接口。package dataStructure.linearList;import dataStructure.linearList.DLinkNode;/ 導(dǎo)入雙鏈表結(jié)點(diǎn)類import dataStructure.linearList.LList;/ 導(dǎo)入線性表接口public class CHDoublyLinkedList implements LList 類protected DLinkNode head;/ 帶頭結(jié)點(diǎn)的循環(huán)雙鏈表/ 頭指針public CHDoublyLinkedList() /構(gòu)造空鏈表this.head = new DLinkNode();/this.he

26、ad.prev = head;this.head.next = head;創(chuàng)建頭結(jié)點(diǎn)，值為 nullpublic boolean isEmpty()/判斷雙鏈表是否為空return head.next=head;/ 以下算法同循環(huán)單鏈表，與單鏈表的差別在于，循環(huán)條件不同public int length()int i=0;DLinkNode p=this.head.next;while (p!=head)i+;p = p.next;return i;/ 返回雙鏈表長度/ 此句與單鏈表不同/ 循環(huán)條件與單鏈表不同public E get(int index)if (index=0)int j=0

27、;DLinkNode p=this.head.next; while (p!=head & j=0 & element!=null) / 設(shè) 置 index 序號對象為int j=0;DLinkNode p=this.head.next; while (p!=head & jindex) j+;p=p.next;if (p!=head)E old = (E)p.data;p.data = element; return old;return null;public String toString()String str=(;DLinkNode p = this.head.next; while

28、 (p!=head)str += p.data.toString();p = p.next;if (p!=head)str += , ;return str+);插入 element 對象，/ 若操作成功返回 true ，/ 不能添加空對象(插入后對象序號O(n)null )/ 雙鏈表的插入、刪除算法與單鏈表不同 public boolean add(int index, E element) / 為 index if (element=null) return false;int j=0;DLinkNode front = this.head;點(diǎn)之后j+;front = front.next

29、;插入在 frontDLinkNode q = new DLinkNode(element, front, front.next); /結(jié)點(diǎn)之后front.next.prev = q;front.next = q;return true;public boolean add(E element) / 在單鏈表最后添加對象， O(1) if (element=null)return false;/ 不能添加空對象( null )DLinkNode q = new DLinkNode(element, head.prev, head);head.prev.next = q; head.prev =

30、 q; return true;public E remove(int index) /nullE old = null;int j=0;DLinkNode p=this.head.next; while (p!=head & jindex) j+;p = p.next;if (p!=head)old = (E)p.data;p.prev.next = p.next;/ 插入在頭結(jié)點(diǎn)之前，相當(dāng)于尾插入/ 移除指定位置的對象， O(n)返回被移除的原對象，指定位置序號錯誤時返回/ 定位到待刪除結(jié)點(diǎn)/ 操作成功，返回原對象/ 刪除 p 結(jié)點(diǎn)自己p.next.prev = p.prev;return

31、 old;public void clear() / 清空線性表this.head.prev = head;this.head.next = head;/ 以上實(shí)現(xiàn) LList 接口public static void main(String args)int i=0;CHDoublyLinkedList list = new CHDoublyLinkedList();System.out.println( 刪除第 +i+ 個結(jié)點(diǎn) +list.remove(0);System.out.println(list.toString();for (i=5; i=0; i-)list.add(0, n

32、ew String(char)(A+i)+);for (i=0; i6; i+)list.add(new String(char)(A+i)+);/list.add(i, new String(char)(A+i)+);System.out.println(list.toString();System.out.println( 刪除第 +i+ 個結(jié)點(diǎn) +list.remove(i);System.out.println(list.toString();程序運(yùn)行結(jié)果如下：刪除第 0 個結(jié)點(diǎn) null()(A, B, C, D, E, F, A, B, C, D, E, F)刪除第 6 個結(jié)點(diǎn) A

33、(A, B, C, D, E, F, B, C, D, E, F)【習(xí) 2.11】 實(shí)驗(yàn) 2.5 建立按升序排序的循環(huán)雙鏈表。package dataStructure.linearList;/ 循環(huán)雙鏈表類import dataStructure.linearList.DLinkNode;import dataStructure.linearList.CHDoublyLinkedList;public class SortedCHDLinkedList extends CHDoublyLinkedList/ 根據(jù)指定對象的大小插入在合適位public SortedCHDLinkedList(

34、)super();public boolean add(E element)/ 按升序排序的循環(huán)雙鏈表類/ 若操作成功返回 true ， O(n)/ 不能插入 null 或非 Comparable 對if (element=null | !(element instanceof Comparable) return false;Comparable cmp = (Comparable)element;if (this.head.prev!=head & pareTo(this.head.prev.data)0) / 非空雙鏈表，插入在最后， O(1)DLinkNode q = n

35、ew DLinkNode(element, head.prev, head);head.prev.next = q; / 插入在頭結(jié)點(diǎn)之前，相當(dāng)于尾插入 head.prev = q;return true;DLinkNode p=this.head.next;while (p!=head & pareTo(p.data)0) / 尋找插入位置 p = p.next;DLinkNode q = new DLinkNode(element, p.prev, p);/ 插入在 p 結(jié)點(diǎn)之前p.prev.next = q;p.prev = q;return true;public boo

36、lean remove(E element)/ 刪除指定對象 / 若操作成功返回 true ， O(n)if (element=null | !(element instanceof Comparable) return false;Comparable cmp = (Comparable)element;DLinkNode p=this.head.next;while (p!=head & pareTo(p.data)0) p = p.next;/ 定位到待刪除的結(jié)點(diǎn)if (p!=head)p.prev.next = p.next;p.next.prev = p.prev; r

37、eturn true;return false;/ 刪除 p 結(jié)點(diǎn)自己/ 未找到指定結(jié)點(diǎn)，刪除不成功public static void main(String args)SortedCHDLinkedList list = new SortedCHDLinkedList(); int n=10;System.out.print(insert ： );for (int i=0; in; i+)int k = (int) (Math.random()*100);if (list.add(new Integer(k) System.out.print(k+ );System.out.println

38、(nlist: +list.toString();程序運(yùn)行結(jié)果如下：insert ： 53 1 92 84 24 3 2 73 99 99list: (1, 2, 3, 24, 53, 73, 84, 92, 99, 99)第3章棧和隊(duì)列【習(xí)3.1】 習(xí)3-5 棧和隊(duì)列有何異同？棧和隊(duì)列都是特殊的線性表，兩者的區(qū)別在于：棧的插入和刪除操作只允許在線性表的 一端進(jìn)行，而隊(duì)列的插入和刪除操作則分另恠線性表的兩端進(jìn)行?！玖?xí)3.2】能否將棧聲明為繼承線性表，入棧方法是add(O,e)，出棧方法是remove(O) ? 為什么？不行。棧不支持中間插入和刪除操作。【習(xí)3.3】能否用一個線性表作為棧的成員變

39、量，入棧方法是add(0,e)，出棧方法是remove(O) ?為什么？不行?！玖?xí)3.4】 能否將隊(duì)列聲明為繼承線性表，入隊(duì)方法是add(e)，出隊(duì)方法是remove(O) ?為什么？不行。隊(duì)列不支持中間插入和刪除操作。第4章串【習(xí)4.1】 實(shí)驗(yàn)4.6找出兩個字符串中所有共同的字符。public class SameCharpublic static void main(String args)String astr = integer, bstr = string;System.out.println(Two strings: +astr+ +bstr);System.out.print(S

40、ameChar:);for (int i=0; iastr.length(); i+)for (int j=0; jbstr.length(); j+)if (astr.charAt(i) = bstr.charAt(j)System.out.print(astr.charAt(i)+);System.out.println();程序運(yùn)行結(jié)果如下：Two strings: integer stringSamechar: i n t g r【習(xí)4.2】 習(xí)4-9(1) 已知目標(biāo)串為abbaba、模式串為aba，畫出其 KMP算法的匹 配過程，并給出比較次數(shù)。t0t1t2t3t4t5targeta

41、bbaba=工patternabaPoP1P2PoP1P2(b)第二次匹配，從t3開始比較KMP算法模式匹配過程如圖 4.1所示，比較6次。(a)第一次匹配，因P0=P2，可知上2工P0圖4.1 目標(biāo)串a(chǎn)bbaba和模式串a(chǎn)ba的KMP算法模式匹配過程【習(xí) 4.3】 習(xí) 4-9(2) 已知 target=ababaab 、pattern=aab，求模式串的 next 數(shù)組,畫出其KMP算法的匹配過程，并給出比較次數(shù)。模式串a(chǎn)ab的next數(shù)組見表4.1。表4.1模式串a(chǎn)ab的next數(shù)組j012模式串a(chǎn)abP0pj-1 中最長相同的前后綴長度k-101Pk與p比較=改進(jìn)的n ext j -1-

42、11其KMP算法的匹配過程如圖 4.2所示，比較7次。t0t1t2t3t4t5t6targetababaab=patternaabP0P1P2(a) t0=p0, t1 工 p1，比較 2次,next1=-1ababaabto t1t2t3t4t5t6工aabP0P1P2(b) t2=Po，tgH p,比較 2次,next1=-1PoP1P2(c) t4 = Po, t5二P1 , t6=p2，比較 3次，匹配成功圖4.2 目標(biāo)串a(chǎn)babaab和模式串a(chǎn)ab的KMP算法模式匹配過程第5章數(shù)組和廣義表【習(xí)5.1】求一個矩陣的轉(zhuǎn)置矩陣。在Matrix類中增加以下方法。返回轉(zhuǎn)置矩陣public Ma

43、trix transpose。/Matrix trans = new Matrix(valueO.length, value.length); for (int i=0; ithis.value .l ength; i+)for (int j=0; jthis.valuei.length; j+) trans.valueji=this.valueij;return trans;第6章樹和二叉樹【習(xí)6.1】 畫出3個結(jié)點(diǎn)的各種形態(tài)的樹和二叉樹。(a) Pb站點(diǎn)的廠種廉再山I;牛帖點(diǎn)的一.翼榔口旳飛種單卓僭再圖6.1 3個結(jié)點(diǎn)樹和二叉樹的形態(tài)【習(xí)6.2】 找出分別滿足下面條件的所有二叉樹。 先根遍

44、歷序列和中根遍歷序列相同：右單支二叉樹，如圖H.5(a)所示。 中根遍歷序列和后根遍歷序列相同：左單支二叉樹，如圖H.5 (b)所示。 先根遍歷序列和后根遍歷序列相同：空樹，只有一個根結(jié)點(diǎn)的二叉樹。圖6.2單支二叉樹【習(xí)6.3】輸出葉子結(jié)點(diǎn)。在BinaryTree類中增加以下方法。public void leaf()/遍歷輸出葉子結(jié)點(diǎn)leaf(root);public void leaf(BinaryNode p) /先根次序遍歷，輸出葉子結(jié)點(diǎn)，3種遍歷次序結(jié)果一樣if(p!=null)if (p.isLeaf()System.out.print(p.data+);leaf(p.left);l

45、eaf(p.right);【習(xí) 6.4】 求一棵二叉樹的葉子結(jié)點(diǎn)個數(shù)。 在 BinaryTree 類中增加以下方法。public int countLeaf() /return countLeaf(root);public int countLeaf(BinaryNode p)個數(shù)if (p=null)return 0;if (p.isLeaf()return 1;return countLeaf(p.left)+countLeaf(p.right); 【習(xí) 6.5】 判斷兩棵二叉樹是否相等。 public boolean equals(Object obj) 類中方法if (obj = th

46、is)return true;if (obj instanceof BinaryTree)BinaryTree bitree = (BinaryTree)obj; return equals(this.root, bitree.root);求一棵二叉樹中所有葉子結(jié)點(diǎn)個數(shù)/求以 p 結(jié)點(diǎn)為根的子樹的葉子結(jié)點(diǎn)/ 比較兩棵二叉樹是否相等， BinaryTreereturn false;private boolean equals(BinaryNode p, BinaryNode q) /判斷兩棵子樹是否相等，遞歸方法if(p=null & q=null) return true;if(p!=null

47、 & q!=null)return (p.data.equals(q.data) & equals(p.left, q.left) & equals(p.right,q.right);return false;習(xí) 6.6 】 復(fù)制一棵二叉樹。在 BinaryTree 類中增加以下構(gòu)造方法，以已知的 public BinaryTree(BinaryTree bitree) this.root = copy(bitree.root);public BinaryNode copy(BinaryNode p)BinaryNode q = null; if(p!=null) q = new BinaryNode(p.data);q.left = copy(p.left);q.right = copy(p.right); return q;【習(xí) 6.7】 二叉樹的替換操作。public boolean replace(E old, E value)/為 valueBinary