《數(shù)據(jù)結(jié)構(gòu)(Java版)(第2版)》習(xí)題解答

1、數(shù)據(jù)結(jié)構(gòu)（java版）（第2版）習(xí)題解答葉核亞 編著目錄第0章 java程序設(shè)計(jì)基礎(chǔ)1【習(xí)0.1】 實(shí)驗(yàn)0.1 哥德巴赫猜想。1【習(xí)0.2】 實(shí)驗(yàn)0.2 楊輝三角形。1【習(xí)0.3】 實(shí)驗(yàn)0.3 金額的中文大寫形式。1【習(xí)0.4】 實(shí)驗(yàn)0.4 下標(biāo)和相等的數(shù)字方陣。1【習(xí)0.5】 實(shí)驗(yàn)0.5 找出一個二維數(shù)組的鞍點(diǎn)2【習(xí)0.6】 實(shí)驗(yàn)0.6 復(fù)數(shù)類。2【習(xí)0.7】 實(shí)驗(yàn)0.8 圖形接口與實(shí)現(xiàn)圖形接口的類2第1章 緒論3【習(xí)1.1】 實(shí)驗(yàn)1.1 判斷數(shù)組元素是否已按升序排序。3【習(xí)1.2】 實(shí)驗(yàn)1.3 用遞歸算法求兩個整數(shù)的最大公因數(shù)。3第2章 線性表5【習(xí)2.1】 習(xí)2-5 圖2.19的數(shù)據(jù)結(jié)構(gòu)

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

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

4、算法的匹配過程，并給出比較次數(shù)。18【習(xí)4.3】 習(xí)4-9(2) 已知target=ababaab、pattern=aab，求模式串的next數(shù)組，畫出其kmp算法的匹配過程，并給出比較次數(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ù)制一棵二叉樹。23【習(xí)6.7】 二叉樹的替換操作。23【習(xí)6.8】 后根次序

5、遍歷中序線索二叉樹。24第7章 圖25第8章 查找26【習(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】 二叉排序樹查找的遞歸算法。29【習(xí)8.6】 二叉排序樹插入結(jié)點(diǎn)的非遞歸算法。30【習(xí)8.7】 判斷一棵二叉樹是否為二叉排序樹。31第9章 排序32【習(xí)9.1】 判斷一個數(shù)據(jù)序列是否為最小堆序列。32【習(xí)9.2】 歸并兩條排序的單鏈表。32【習(xí)9.3】 說明二叉排序樹與堆的差別。34圖0.1 下標(biāo)和相等的數(shù)字方陣算法描述1圖

6、2.1 p.next=p將改變結(jié)點(diǎn)間的鏈接關(guān)系5圖4.1 目標(biāo)串a(chǎn)bbaba和模式串a(chǎn)ba的kmp算法模式匹配過程18圖4.2 目標(biāo)串a(chǎn)babaab和模式串a(chǎn)ab的kmp算法模式匹配過程19圖6.1 3個結(jié)點(diǎn)樹和二叉樹的形態(tài)21圖6.2 單支二叉樹21圖9.2 歸并兩條排序的單鏈表33表4.1 模式串a(chǎn)ab的next數(shù)組19- iii -第0章 java程序設(shè)計(jì)基礎(chǔ)【習(xí)0.1】 實(shí)驗(yàn)0.1 哥德巴赫猜想。【習(xí)0.2】 實(shí)驗(yàn)0.2 楊輝三角形?！玖?xí)0.3】 實(shí)驗(yàn)0.3 金額的中文大寫形式?！玖?xí)0.4】 實(shí)驗(yàn)0.4 下標(biāo)和相等的數(shù)字方陣。輸出下列方陣（當(dāng)n=4時(shí)）。1267 或 134103581

7、3 25911491214 68121510111516 7131416采用二維數(shù)組實(shí)現(xiàn)。二維數(shù)組中，每一條斜線上各元素下標(biāo)和相等，如圖0.1所示。圖0.1 下標(biāo)和相等的數(shù)字方陣算法描述程序如下。public class upmat public static void main(string args) int n=4; /階數(shù) int mat = new intnn; int k=1; /k是自然數(shù)，遞增變化 boolean up = true; /方向向上 for (int sum=0; sum=0; i-) matisum-i = k+; /k先賦值后自加 else for (int

8、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; for (int i=0; imat.length; i+) /輸出二維數(shù)組元素 for (int j=0; jmati.length; j+) /i、j是行、列下標(biāo) system.out.print( +matij); system.out.println(); 【習(xí)0.5】 實(shí)驗(yàn)0.5 找出一個二維

9、數(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。public static boolean issorted(int table) /判斷整數(shù)數(shù)組是否已按升序排序 /若已排序返回true，否則返回false if (table=null) return false; for (int i=0; itablei+1) return false; return true;public static boolean issorted(c

10、omparable table) /判斷對象數(shù)組是否已按升序排序 /若已排序返回true，否則返回false if (table=null) return false; for (int i=0; i0) return false; return true;【習(xí)1.2】 實(shí)驗(yàn)1.3 用遞歸算法求兩個整數(shù)的最大公因數(shù)。public class gcd public 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);

11、return gcd(b, a%b); public static void main(string args) int a=12, b=18, c=24; system.out.println(gcd(+a+,+b+,+c+)=+gcd(gcd(a,b),c); /獲得3個整數(shù)最大公因數(shù) 第2章 線性表【習(xí)2.1】 習(xí)2-5 圖2.19的數(shù)據(jù)結(jié)構(gòu)聲明。table數(shù)組元素為單鏈表，聲明如下：singlylinkedlist table【習(xí)2.2】 習(xí)2-6 如果在遍歷單鏈表時(shí)，將p=p.next語句寫成p.next=p，結(jié)果會怎樣？使p.next指向p結(jié)點(diǎn)自己，改變了結(jié)點(diǎn)間的鏈接關(guān)系，丟失后繼

12、結(jié)點(diǎn)，如圖2.1所示。圖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 (element!=null & element.length0) this.head = new node(element0); node rear=this.head; int i=1; while (ielement.length) rear.next

13、 = 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開始順序查找指定對象public node search(e element) /若查找到指定對象，則返回結(jié)點(diǎn)，否則返回nullpublic boolean contain(e element) /以查找結(jié)果判斷單鏈表是否包含指定對象public boolean remove

14、(e element) /移去首次出現(xiàn)的指定對象【習(xí)2.5】 實(shí)驗(yàn)2.2 單鏈表的替換操作。在singlylinkedlist單鏈表類中，增加替換操作方法如下。public boolean replace(object obj, e element) /將元素值為obj的結(jié)點(diǎn)值替換為element /若替換成功返回true，否則返回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; retu

15、rn true; p = p.next; return false;【習(xí)2.6】 實(shí)驗(yàn)2.2 首尾相接地連接兩條單鏈表。在singlylinkedlist單鏈表類中，增加替換操作方法如下。public void concat(singlylinkedlist list) /將指定單鏈表list鏈接在當(dāng)前單鏈表之后 if (this.head=null) this.head = list.head; else node p=this.head; while (p.next!=null) p = p.next; p.next = list.head; 【習(xí)2.7】 實(shí)驗(yàn)2.2 復(fù)制單鏈表。在sin

16、glylinkedlist單鏈表類中，增加構(gòu)造方法如下。public singlylinkedlist(singlylinkedlist list) /以單鏈表list構(gòu)造新的單鏈表 /復(fù)制單鏈表 this.head = null; if (list!=null & list.head!=null) this.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;

17、 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!=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(

18、elementi); p.next = create(element, i+1); return p;單鏈表的復(fù)制操作也可設(shè)計(jì)為以下的遞歸方法：public singlylinkedlist(singlylinkedlist list) /以單鏈表list構(gòu)造新的單鏈表 this.head = copy(list.head);private node copy(node p) /復(fù)制單鏈表，遞歸方法 node q=null; if (p!=null) q = new node(p.data); q.next = copy(p.next); return q;比較兩條單鏈表是否相等的操作也可設(shè)計(jì)

19、為以下的遞歸方法：public boolean equals(object obj) /比較兩條單鏈表是否相等 if (obj = this) return true; if (obj instanceof singlylinkedlist) singlylinkedlist list = (singlylinkedlist)obj; return equals(this.head, list.head); return false;private boolean equals(node p, node q) /比較兩條單鏈表是否相等，遞歸方法 if (p=null & q=null) ret

20、urn true; 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 datastructure.linearlist.node; import datastructure.linearlist.singlylinkedlist; /不帶頭結(jié)點(diǎn)的單鏈表類public class sortedsinglylinkedlist extends sin

21、glylinkedlist public sortedsinglylinkedlist() super(); public boolean add(e element) /根據(jù)指定對象的大小插入在合適位置 if (element=null | !(element instanceof comparable) return false; /不能插入null或非comparable對象 comparable cmp = (comparable)element; if (this.head=null | pareto(this.head.data)=0) this.head = new node(e

22、lement,this.head); /頭插入 else node front=null, p=this.head; while (p!=null & pareto(p.data)0) front = p; /front是p的前驅(qū)結(jié)點(diǎn) p = p.next; front.next = new node(element, p); /中間/尾插入 return true; public static void main(string args) sortedsinglylinkedlist list = new sortedsinglylinkedlist(); int n=10; system.

23、out.print(insert： ); for (int i=0; in; i+) int k = (int) (math.random()*100); /產(chǎn)生隨機(jī)數(shù) if (list.add(new integer(k) system.out.print(k+ ); system.out.println(nlist: +list.tostring(); 程序多次運(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 5

24、0 29 78 34 list: (11, 13, 29, 33, 34, 42, 50, 52, 78, 89)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)線性表接口。package datastructure.linearlist;import datastructure.linearlist.dlinknode; /導(dǎo)入雙鏈表結(jié)點(diǎn)類import datastructure.linearlist.llist; /導(dǎo)

25、入線性表接口public class chdoublylinkedlist implements llist /帶頭結(jié)點(diǎn)的循環(huán)雙鏈表類 protected dlinknode head; /頭指針 public chdoublylinkedlist() /構(gòu)造空鏈表 this.head = new dlinknode(); /創(chuàng)建頭結(jié)點(diǎn)，值為null this.head.prev = head; this.head.next = head; public boolean isempty() /判斷雙鏈表是否為空 return head.next=head; /以下算法同循環(huán)單鏈表，與單鏈表的差

26、別在于，循環(huán)條件不同 public int length() /返回雙鏈表長度 int i=0; dlinknode p=this.head.next; /此句與單鏈表不同 while (p!=head) /循環(huán)條件與單鏈表不同 i+; p = p.next; return i; public e get(int index) /返回序號為index的對象 if (index=0) int j=0; dlinknode p=this.head.next; while (p!=head & j=0 & element!=null) int j=0; dlinknode p=this.head.n

27、ext; 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 (p!=head) str += p.data.tostring(); p = p.next; if (p!=head) str += , ; return str+); /雙鏈表的插入、刪除算法與單鏈表不同 p

28、ublic boolean add(int index, e element) /插入element對象，插入后對象序號為index /若操作成功返回true，o(n) if (element=null) return false; /不能添加空對象（null） int j=0; dlinknode front = this.head; while (front.next!=head & jindex) /尋找插入位置，若i=0，插入在頭結(jié)點(diǎn)之后 j+; front = front.next; dlinknode q = new dlinknode(element, front, front.

29、next); /插入在front結(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; /插入在頭結(jié)點(diǎn)之前，相當(dāng)于尾插入 head.prev = q; return true; public e remove

30、(int index) /移除指定位置的對象，o(n) /返回被移除的原對象，指定位置序號錯誤時(shí)返回null e old = null; int j=0; dlinknode p=this.head.next; while (p!=head & jindex) /定位到待刪除結(jié)點(diǎn) j+; p = p.next; if (p!=head) old = (e)p.data; /操作成功，返回原對象 p.prev.next = p.next; /刪除p結(jié)點(diǎn)自己 p.next.prev = p.prev; return old; public void clear() /清空線性表 this.head

31、.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, new string(char)(a+i)+); for (i=0; i6; i

32、+) 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(a, b, c, d, e, f, b, c, d, e, f)【習(xí)2.11】

33、實(shí)驗(yàn)2.5 建立按升序排序的循環(huán)雙鏈表。package datastructure.linearlist;import datastructure.linearlist.dlinknode;import datastructure.linearlist.chdoublylinkedlist; /循環(huán)雙鏈表類public class sortedchdlinkedlist extends chdoublylinkedlist /按升序排序的循環(huán)雙鏈表類 public sortedchdlinkedlist() super(); public boolean add(e element) /根據(jù)指

34、定對象的大小插入在合適位置 /若操作成功返回true，o(n) if (element=null | !(element instanceof comparable) return false; /不能插入null或非comparable對象 comparable cmp = (comparable)element; if (this.head.prev!=head & pareto(this.head.prev.data)0) /非空雙鏈表，插入在最后，o(1) dlinknode q = new dlinknode(element, head.prev, head); head.prev.

35、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 boolean remove(e element) /刪除指定對象 /若操作成功返回true，o(n) if

36、(element=null | !(element instanceof comparable) return false; comparable cmp = (comparable)element; dlinknode p=this.head.next; while (p!=head & pareto(p.data)0) /定位到待刪除的結(jié)點(diǎn) p = p.next; if (p!=head) p.prev.next = p.next; /刪除p結(jié)點(diǎn)自己 p.next.prev = p.prev; return true; return false; /未找到指定結(jié)點(diǎn)，刪除不成功 public

37、 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(nlist: +list.tostring(); 程序運(yùn)行結(jié)果如下：insert： 53 1 92

38、84 24 3 2 73 99 99 list: (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(0,e)，出棧方法是remove(0)？為什么？不行。棧不支持中間插入和刪除操作。【習(xí)3.3】 能否用一個線性表作為棧的成員變量，入棧方法是add(0,e)，出棧方法是remove(0)？為什么？不行。【習(xí)3.4】 能否將隊(duì)列聲明為繼承線性表，入隊(duì)方法是add(e)，出隊(duì)方法是remove(0)？為什么？不行。隊(duì)列不支持中間插入和刪除操作。第4章 串【習(xí)4.1】 實(shí)驗(yàn)4.6 找出兩個字符串中所有共同的字符。public class samechar publi