數(shù)據(jù)結(jié)構(gòu)(Java版)-習(xí)題解答與實(shí)驗(yàn)指導(dǎo)

數(shù)據(jù)結(jié)構(gòu)（Java版）習(xí)題解答與實(shí)驗(yàn)指導(dǎo)目錄第1章 緒論11.1 數(shù)據(jù)結(jié)構(gòu)的基本概念11.2 算法2第2章 線 性 表32.1 線性表抽象數(shù)據(jù)類型32.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)42.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)42.2.2 順序表42.2.3 排序順序表62.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)72.3.1 單鏈表7【習(xí)題2-8】單鏈表結(jié)點(diǎn)類問題討論。7【習(xí)2.1】 使用單鏈表求解Josephus環(huán)問題。9【習(xí)2.2】 集合并運(yùn)算，單鏈表深拷貝的應(yīng)用。102.3.2 雙鏈表12【習(xí)2.3】 循環(huán)雙鏈表的迭代方法。13【習(xí)2.4】 循環(huán)雙鏈表合并連接。14第3章 串153.1 串抽象數(shù)據(jù)類型153.2 串的存儲(chǔ)和實(shí)現(xiàn)153.2.1 串的存儲(chǔ)結(jié)構(gòu)153.2.2 常量字符串類15【習(xí)3.1】 C/C+語言，string.h中的strcpy()和strcat()函數(shù)存在下標(biāo)越界錯(cuò)誤。15【思考題3-1】逆轉(zhuǎn)String串，分析算法效率。17【實(shí)驗(yàn)題3-1】MyString類，比較串大小，忽略字母大小寫。17【例3.2思考題3-2】MyInteger整數(shù)類，返回value的radix進(jìn)制原碼字符串。18【實(shí)驗(yàn)題3-9】浮點(diǎn)數(shù)類。193.2.3 變量字符串類20【實(shí)驗(yàn)題3-11】刪除變量串中的所有空格。 4-樣卷203.3 串的模式匹配213.3.1 Brute-Force模式匹配算法213.3.2 模式匹配應(yīng)用22【思考題3-4，實(shí)驗(yàn)題3-13】MyString類，replaceAll(pattern,s)改錯(cuò)。223.3.3 KMP模式匹配算法22第4章 棧和隊(duì)列264.1 棧264.2 隊(duì)列274.3 遞歸29【習(xí)4.1】 打印數(shù)字塔。29第5章 數(shù)組和廣義表315.1 數(shù)組315.2 特殊矩陣的壓縮存儲(chǔ)325.2.1 三角矩陣、對稱矩陣和對角矩陣的壓縮存儲(chǔ)325.2.2 稀疏矩陣的壓縮存儲(chǔ)335.3 廣義表35第6章 樹和二叉樹366.2 二叉樹366.3 線索二叉樹406.4 Huffman樹446.5 樹的表示和實(shí)現(xiàn)45第7章 圖467.1 圖及其抽象數(shù)據(jù)類型467.2 圖的表示和實(shí)現(xiàn)467.3 圖的遍歷487.4 最小生成樹507.5 最短路徑51第8章 查 找538.1 查找的基本概念538.2 二分法查找548.4 散列558.5 二叉排序樹56【實(shí)驗(yàn)8-1】判斷一棵二叉樹是否為二叉排序樹，改錯(cuò)。56第9章 排序579.1 插入排序579.2 交換排序589.3 選擇排序599.4 歸并排序609.5 線性表的排序算法609.5.1 順序表的排序算法60【實(shí)驗(yàn)題9-2】歸并兩條排序順序表。60第10章 綜合應(yīng)用設(shè)計(jì)6210.1 Java集合框架62【習(xí)10.1】 Collection整數(shù)集合元素求和。6210.2 課程設(shè)計(jì)補(bǔ)充選題63- III -第1章 緒論目的：勾勒數(shù)據(jù)結(jié)構(gòu)課程的輪廓，了解本課程的目的、性質(zhì)和主要內(nèi)容。內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和算法概念，算法設(shè)計(jì)與分析。要求：理解數(shù)據(jù)結(jié)構(gòu)基本概念，理解抽象數(shù)據(jù)類型概念；熟悉算法設(shè)計(jì)和分析方法。重點(diǎn)：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)概念。難點(diǎn)：抽象數(shù)據(jù)類型，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，算法分析方法。實(shí)驗(yàn)：簡單算法設(shè)計(jì)，回顧Java語言的基本語法和面向?qū)ο蠡靖拍睢?.1 數(shù)據(jù)結(jié)構(gòu)的基本概念習(xí)1-2 什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)概念包括哪些部分？習(xí)1-3 數(shù)據(jù)的邏輯結(jié)構(gòu)主要有哪三種？三者之間存在怎樣的聯(lián)系？習(xí)1-4 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有哪些？各有何特點(diǎn)？習(xí)1-5 不同數(shù)據(jù)結(jié)構(gòu)之間共同的操作有哪些？【答】上述1-11-4問題說明如下。 數(shù)據(jù)結(jié)構(gòu)，指數(shù)據(jù)元素之間存在關(guān)系的數(shù)據(jù)元素集合。 數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)操作三方面概念。 數(shù)據(jù)的邏輯結(jié)構(gòu)主要有三種：線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)，線性結(jié)構(gòu)是樹的特例，樹結(jié)構(gòu)是圖的特例。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，兩者特點(diǎn)分別是數(shù)據(jù)元素?cái)?shù)據(jù)連續(xù)存儲(chǔ)、分散存儲(chǔ)。 數(shù)據(jù)操作主要有：求數(shù)據(jù)元素個(gè)數(shù)，訪問、查找、插入、刪除數(shù)據(jù)元素等。數(shù)據(jù)結(jié)構(gòu)概念描述如圖1.1所示。圖1.1 數(shù)據(jù)結(jié)構(gòu)概念習(xí)1-6 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別？為什么要將數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)成抽象數(shù)據(jù)類型？【答】數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型概念本質(zhì)相同，使用數(shù)據(jù)類型描述數(shù)據(jù)特性，使用數(shù)據(jù)結(jié)構(gòu)描述數(shù)據(jù)之間關(guān)系。將數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)成抽象數(shù)據(jù)類型，是為了“定義和實(shí)現(xiàn)相分離”，這也是數(shù)據(jù)類型的特點(diǎn)。1.2 算法習(xí)1-8 什么是算法？怎樣描述算法？怎樣衡量算法的性能？ 【答】算法是對問題求解過程的一種描述，是為解決一類問題給出的一個(gè)確定的、有限長的操作序列。算法特征包括：有窮性、確定性、輸入、輸出和可行性?？梢圆捎米匀徽Z言或偽碼描述算法的設(shè)計(jì)思想，采用程序設(shè)計(jì)語言實(shí)現(xiàn)算法。采用漸進(jìn)分析法衡量算法性能，用時(shí)間復(fù)雜度O(f(n)表示所花費(fèi)時(shí)間的量級，即時(shí)間效率；用空間復(fù)雜度O(S(n)表示算法執(zhí)行過程中所需要的額外空間。第2章 線 性 表目的：實(shí)現(xiàn)線性表抽象數(shù)據(jù)類型。內(nèi)容：將線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)分別封裝成順序表類、單鏈表類、循環(huán)雙鏈表類等，比較這兩種實(shí)現(xiàn)的特點(diǎn)以及各種基本操作算法的效率。要求：理解線性表抽象數(shù)據(jù)類型，掌握順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的方法。重點(diǎn)：順序表、單鏈表、循環(huán)雙鏈表等線性表設(shè)計(jì)訓(xùn)練。難點(diǎn)：使用對象引用方式實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，改變結(jié)點(diǎn)間的鏈接關(guān)系。實(shí)驗(yàn)：掌握單鏈表的遍歷、插入、刪除、復(fù)制等操作算法，熟悉循環(huán)單鏈表、雙鏈表和循環(huán)雙鏈表的結(jié)構(gòu)和基本操作。掌握MyEclipse集成開發(fā)環(huán)境的程序調(diào)試技術(shù)。2.1 線性表抽象數(shù)據(jù)類型2-1 什么是線性表？線性表主要采用哪兩種存儲(chǔ)結(jié)構(gòu)？它們是如何存儲(chǔ)數(shù)據(jù)元素的？各有什么優(yōu)缺點(diǎn)？畫出線性表的各種存儲(chǔ)結(jié)構(gòu)示意圖。它們是否是隨機(jī)存取結(jié)構(gòu)？為什么？【答】 線性表是數(shù)據(jù)元素之間具有線性關(guān)系的一種線性結(jié)構(gòu)，對線性表的基本操作主要有獲得元素值、設(shè)置元素值、插入、刪除、查找、替換和排序等，插入和刪除操作可以在線性表的任意位置進(jìn)行。 線性表可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示。線性表()的兩種存儲(chǔ)結(jié)構(gòu)見教材圖1.4所示。線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）用一組連續(xù)的存儲(chǔ)單元順序存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲(chǔ)次序與它們在線性表中的邏輯次序相同。順序表的特點(diǎn)是數(shù)據(jù)元素連續(xù)存儲(chǔ)，元素的存儲(chǔ)地址是它在線性表中位置i的線性函數(shù)，計(jì)算一個(gè)元素地址花費(fèi)常量時(shí)間，即存取任何一個(gè)元素的時(shí)間復(fù)雜度是O(1)。因此，順序表是隨機(jī)存取結(jié)構(gòu)，這是順序表最大的優(yōu)點(diǎn)。順序表缺點(diǎn)是插入或刪除操作效率低，每插入或刪除一個(gè)元素平均需要移動(dòng)線性表一半元素。線性表的鏈?zhǔn)酱鎯?chǔ)用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，必須采用附加信息表示數(shù)據(jù)元素之間的順序關(guān)系。特點(diǎn)是數(shù)據(jù)元素分散存儲(chǔ)，優(yōu)點(diǎn)是插入或刪除操作不需要移動(dòng)其他元素；缺點(diǎn)是，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不是隨機(jī)存取結(jié)構(gòu)，獲得第i個(gè)元素地址的時(shí)間復(fù)雜度是O(n)，因?yàn)榫€性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（單鏈表）由若干結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)采用指針域保存其后繼結(jié)點(diǎn)的地址，獲得第i個(gè)元素地址平均需要遍歷單鏈表一半結(jié)點(diǎn)。 第2章線性表存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)的各種類描述如圖2.1所示。圖2.1 線性表的存儲(chǔ)結(jié)構(gòu)2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn)2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)2-2 解釋順序存儲(chǔ)結(jié)構(gòu)的線性表（順序表）與數(shù)組在概念上的差別。 【答】數(shù)組是高級程序設(shè)計(jì)語言中的一種構(gòu)造數(shù)據(jù)類型，具有存儲(chǔ)單元連續(xù)的特點(diǎn)。順序表利用數(shù)組的這個(gè)特點(diǎn)，將順序表中的數(shù)據(jù)元素在數(shù)組中連續(xù)存放，以數(shù)據(jù)元素的存儲(chǔ)位置體現(xiàn)線性表數(shù)據(jù)元素之間的邏輯關(guān)系，所以數(shù)組是實(shí)現(xiàn)順序表的基礎(chǔ)。雖然數(shù)組的存儲(chǔ)單元是連續(xù)的，但數(shù)組元素不一定連續(xù)。而用數(shù)組實(shí)現(xiàn)順序表時(shí)，數(shù)據(jù)元素必須連續(xù)存放，否則無法體現(xiàn)出線性表中數(shù)據(jù)元素之間的前驅(qū)和后繼關(guān)系。習(xí)2-4 為什么順序表的插入和刪除操作必須移動(dòng)元素？平均需要移動(dòng)多少元素？【答】順序表中數(shù)據(jù)元素連續(xù)存儲(chǔ)，元素之間沒有空位置，邏輯上相鄰的數(shù)據(jù)元素在存儲(chǔ)位置上也相鄰。因此，插入數(shù)據(jù)元素時(shí)，必須將指定位置之后的數(shù)據(jù)元素向后移動(dòng)，以留出空位置；刪除數(shù)據(jù)元素時(shí)，必須將刪除位置之后的數(shù)據(jù)元素向前移動(dòng)，以填補(bǔ)空位置。2.2.2 順序表【思考題2-3】 SeqList類如果聲明get(i)方法如下，與返回類型為T有何區(qū)別？ public Object get(int i) /返回第i個(gè)元素，0in。若i越界，返回null【答】 SeqList類如果聲明get(i)方法如下，返回類型為Object。public Object get(int i) /返回第i個(gè)元素，0i=0 & ithis.n) return this.elementi; /返回?cái)?shù)組元素elementi引用的對象 return null;上述聲明的調(diào)用語句如下：SeqList list = new SeqList(n); /順序表元素類型是字符串Object obj = list.get(0); /父類Object對象obj引用子類Integer的實(shí)例，類型多態(tài)obj.toString() /obj調(diào)用Object類聲明且被子類覆蓋的方法，運(yùn)行時(shí)多態(tài)Value() /編譯錯(cuò)，obj不能調(diào)用Integer類的成員方法(T)obj).intValue() /(T)obj是Integer類的對象此時(shí)，obj對象只能調(diào)用Object類聲明且被子類覆蓋的方法，只有toString()和equals()方法，表現(xiàn)出運(yùn)行時(shí)多態(tài)，實(shí)際執(zhí)行obj引用實(shí)例所屬Integer類提供的方法實(shí)現(xiàn)；而不能調(diào)用Integer類聲明的成員方法。 SeqList類聲明get(i)方法如下，返回類型為T。public T get(int i) /返回第i個(gè)元素，0i=0 & ithis.n) return (T)this.elementi; /返回?cái)?shù)組元素引用的對象，必須進(jìn)行強(qiáng)制類型轉(zhuǎn)換 return null;其中，數(shù)組元素elementi的類型是Object，實(shí)際引用實(shí)例的類型是T。上述聲明的調(diào)用語句如下：SeqList list = new SeqList(n); /順序表元素類型是整數(shù)對象Integer iobj = list.get(0); /Integer類對象iobj引用本類的實(shí)例Value() /iobj能夠調(diào)用Integer類的成員方法此時(shí)，iobj對象不僅能夠調(diào)用Object類聲明的toString()等方法，表現(xiàn)出運(yùn)行時(shí)多態(tài)；還能夠調(diào)用Integer類聲明的成員方法。也可調(diào)用語句如下：SeqList list = new SeqList(n); String str = list.get(0); str.length() /str能夠調(diào)用String類的成員方法習(xí)2-5 順序表類以下聲明有什么錯(cuò)誤？為什么？public boolean equals(Object obj) /比較兩個(gè)順序表是否相等 return this.n=list.n & this.element=obj.element;【答】在深拷貝的含義下，兩個(gè)順序表相等意味著：兩個(gè)順序表長度相同且所有元素值相等。而不是兩個(gè)順序表對象的所有成員變量值對應(yīng)相等。比較兩個(gè)順序表對象是否相等的多種情況如圖2.2所示，方法實(shí)現(xiàn)見教材第30頁。 圖2.2 比較兩個(gè)順序表對象是否相等2.2.3 排序順序表【思考題2-4】 SeqList類聲明以下方法，子類SortedSeqList是否可用？為什么？/返回將this與list所有元素合并連接的順序表，不改變this和listSeqList union(SeqList list)【答】 SeqList類聲明以下成員方法：public void addAll(SeqList list) /在this之后添加list所有元素，集合并。見例2.5public SeqList union(SeqList list) SeqList result = new SeqList(this); /深拷貝this，無法創(chuàng)建子類實(shí)例 result.addAll(list); /順序表合并連接，尾插入 return result; /只能返回SeqList對象%注意：雖然union(list)方法與addAll(list)方法功能相同，但不能將它們重載如下，因?yàn)?，參?shù)列表相同而返回值不同，產(chǎn)生二義性，編譯器不能根據(jù)方法的參數(shù)列表確定執(zhí)行重載方法中的哪一個(gè)。public void addAll(SeqList list) public SeqList addAll(SeqList list) /語法錯(cuò)，參數(shù)列表相同時(shí)不能重載 排序順序表表示可重復(fù)的排序集合，元素按關(guān)鍵字大小排序。SortedSeqList類繼承SeqList類的以下成員方法：public void addAll(SeqList list) /可用，參數(shù)list可引用SortedSeqList實(shí)例。 /其中，執(zhí)行insert(x)方法運(yùn)行時(shí)多態(tài)，當(dāng)this引用子類實(shí)例時(shí)，執(zhí)行排序順序表按值插入 /合并結(jié)果this仍然是排序順序表public SeqList union(SeqList list) /算法正確，不可用。希望返回排序順序表 /因?yàn)?，?dāng)this引用子類實(shí)例時(shí)，聲明result和創(chuàng)建的仍然是SeqList實(shí)例，無法創(chuàng)建子類 /實(shí)例，就無法實(shí)現(xiàn)運(yùn)行時(shí)多態(tài)，總是執(zhí)行SeqList類的插入因此，SortedSeqList類需要覆蓋union(list)方法如下：/覆蓋，返回值類型不同但賦值相容。能與父類實(shí)例運(yùn)算public SortedSeqList union(SeqList list) SortedSeqList result = new SortedSeqList(this); /創(chuàng)建子類實(shí)例。只此一句不同 result.addAll(list); /繼承父類方法，運(yùn)行時(shí)多態(tài)，排序順序表合并，按值插入 return result; /返回SortedSeqList對象綜上所述，SeqList類對于集合并操作的“有所為，有所不為”原則如下。 聲明void addAll(list)方法，子類繼承，運(yùn)行時(shí)多態(tài)。 不聲明SeqList union(list)方法，因?yàn)椋瑹o法運(yùn)行時(shí)多態(tài)。一個(gè)類為一個(gè)功能只需提供一種實(shí)現(xiàn)，至于是否返回對象，由調(diào)用者決定，通過深拷貝和addAll(list)方法可得到。2.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)2.3.1 單鏈表1. 單鏈表的結(jié)點(diǎn)習(xí)2-6 寫出圖2.3所示數(shù)據(jù)結(jié)構(gòu)的聲明。圖2.3 一種數(shù)據(jù)結(jié)構(gòu)【答】table可聲明為數(shù)組或順序表，元素為結(jié)點(diǎn)或單鏈表，聲明為以下4種之一：Node table; /一維數(shù)組，元素為結(jié)點(diǎn)SinglyList table; /一維數(shù)組，元素為單鏈表SeqListNode table; /順序表，元素為結(jié)點(diǎn)SeqListSinglyList table; /順序表，元素為單鏈表 【習(xí)題2-8】單鏈表結(jié)點(diǎn)類問題討論。 Node類聲明構(gòu)造方法當(dāng)一個(gè)類沒有聲明構(gòu)造方法時(shí)，Java提供默認(rèn)構(gòu)造方法。例如：public Node() /提供默認(rèn)構(gòu)造方法 super(); /默認(rèn)調(diào)用父類的無參數(shù)構(gòu)造方法當(dāng)一個(gè)類聲明了構(gòu)造方法時(shí)，Java不再提供默認(rèn)構(gòu)造方法。例如，當(dāng)Node類聲明了Node(T data,Node next)構(gòu)造方法時(shí)，Java不再提供默認(rèn)構(gòu)造方法Node()。如果Node類需要Node()構(gòu)造方法，必須自己聲明。Java方法參數(shù)沒有默認(rèn)值。例如，Node類可以聲明以下構(gòu)造方法：public Node(T data) this(data,null);但不能將Node(T data,Node next)構(gòu)造方法聲明為如下形式：public Node(T data,Node next=null) Node類不需要聲明析構(gòu)方法Node類從Object父類繼承了析構(gòu)方法，并且Java語言將自動(dòng)釋放不再使用的存儲(chǔ)空間。因此，Node類不需要聲明析構(gòu)方法。 Node類不需要聲明拷貝構(gòu)造方法Java不提供默認(rèn)拷貝構(gòu)造方法。Node類如果聲明拷貝構(gòu)造方法以下：public Node(Node p) /拷貝構(gòu)造方法，復(fù)制p引用的結(jié)點(diǎn) this(p.data,p.next); 相當(dāng)于如下：public Node(Node p) this.data = p.data; /this.data引用p.data，對象引用賦值，兩個(gè)結(jié)點(diǎn)引用同一個(gè)元素 this.next = p.next; /this.next指向p的后繼結(jié)點(diǎn)，結(jié)點(diǎn)對象引用賦值，邏輯錯(cuò)誤由于Java的賦值=采用引用模型，執(zhí)行結(jié)果如圖2.4所示，this.next指向p的后繼結(jié)點(diǎn)，并沒有創(chuàng)建結(jié)點(diǎn)，只將p的后繼結(jié)點(diǎn)作為當(dāng)前結(jié)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，產(chǎn)生邏輯錯(cuò)誤。因此，Node類不能聲明淺拷貝構(gòu)造方法。圖2.4 Node類淺拷貝由于創(chuàng)建結(jié)點(diǎn)是單鏈表執(zhí)行的操作，所以，Node類不需要聲明拷貝構(gòu)造方法。 Node類可聲明以下方法：public boolean equals(Object obj) /比較兩個(gè)結(jié)點(diǎn)值是否相等，覆蓋Object類的equals(obj)方法 return obj=this | obj instanceof Node & this.data.equals(Node)obj).data); 比較對象大小Node是單鏈表和排序單鏈表的結(jié)點(diǎn)類。單鏈表不需要比較元素大小，所以Node類不能聲明實(shí)現(xiàn)Comparable接口。排序單鏈表需要比較元素大小，以下排序單鏈表類聲明，約定能夠比較T對象大小。/排序單鏈表類（升序），繼承單鏈表類，T或T的某個(gè)祖先類實(shí)現(xiàn)Comparable接口public class SortedSinglyListT extends Comparable extends SinglyList2. 單鏈表的基本操作【思考題2-6】 遍歷單鏈表，如果將p=p.next語句寫成p.next=p，結(jié)果會(huì)怎樣？畫出示意圖?！敬稹空Z句p=p.next使p移動(dòng)到后繼結(jié)點(diǎn)，此時(shí)結(jié)點(diǎn)間的鏈接關(guān)系沒有改變。如果寫成p.next=p，則使p.next指向p結(jié)點(diǎn)自己，改變了結(jié)點(diǎn)間的鏈接關(guān)系，并丟失后繼結(jié)點(diǎn)，如圖2.5所示，遍歷算法也變成死循環(huán)。圖2.5 p.next=p改變結(jié)點(diǎn)間的鏈接關(guān)系【思考題2-7】 設(shè)front指向非空單鏈表中的某個(gè)結(jié)點(diǎn)，在front結(jié)點(diǎn)之后插入p結(jié)點(diǎn)，執(zhí)行以下語句結(jié)果會(huì)怎樣？畫出示意圖。Node p = new Node(x);front.next = p; /p.next = front.next; /【答】句相當(dāng)于p.next = p;，產(chǎn)生錯(cuò)誤，結(jié)點(diǎn)間的鏈接關(guān)系如圖2.6所示。圖2.6 插入語句次序錯(cuò)誤錯(cuò)誤原因：上述后兩條語句次序顛倒。對front.next賦值將改變結(jié)點(diǎn)間的鏈接關(guān)系，從而丟失后繼結(jié)點(diǎn)地址。因此，在改變結(jié)點(diǎn)鏈接關(guān)系時(shí)，應(yīng)該先獲得front.next的值，再對其賦值。頭插入存在同樣問題。3. 帶頭結(jié)點(diǎn)的單鏈表【習(xí)2.7】 使用單鏈表求解Josephus環(huán)問題。將例2.1程序中創(chuàng)建SeqList對象的語句替換為如下，其余代碼不變，則使用單鏈表也可求解Josephus環(huán)問題。SinglyList list = new SinglyList();上述程序雖然能夠運(yùn)行，但是，效率太低。一是，每次循環(huán)調(diào)用單鏈表的size()和remove(i)方法，都要從頭開始再次遍歷單鏈表，時(shí)間復(fù)雜度都是O(n)；再有，每次計(jì)數(shù)，欲刪除第i個(gè)結(jié)點(diǎn)，需要再次查找使front指向第i個(gè)結(jié)點(diǎn)的前驅(qū)。修改例2.1程序，使用單鏈表求解Josephus環(huán)問題，遍歷次數(shù)最少。/求解Josephus環(huán)，n（0）指定長度；s指定計(jì)數(shù)的起始位置，0sn；d計(jì)數(shù)，0dnpublic Josephus(int n, int s, int d) if (n=0 | s=n | d=n) throw new java.lang.IllegalArgumentException(n=+n+，s=+s+，d=+d); /無效參數(shù)異常 System.out.print(Josephus(+n+,+s+,+d+)，); SinglyList list = new SinglyList(); /構(gòu)造空單鏈表 for (int i=n-1; i=0; i-) list.insert(0, (char)(A+i)+); /單鏈表頭插入，O(1) System.out.println(list.toString(); /輸出單鏈表的描述字符串，O(n) /以下求解Josephus環(huán) Node front = list.head; /front指向頭結(jié)點(diǎn) for (int j=0; front!=null & j1) /多于一個(gè)元素時(shí)循環(huán) for (int j=1; jd; j+) /計(jì)數(shù)，尋找刪除結(jié)點(diǎn)。少數(shù)一個(gè)，front指向待刪除結(jié)點(diǎn)的前驅(qū) front = front.next; if (front=null) /實(shí)現(xiàn)循環(huán)計(jì)數(shù) front = list.head.next; if (front.next=null) /若front指向最后一個(gè)結(jié)點(diǎn)，則刪除第0個(gè)結(jié)點(diǎn) front = list.head; System.out.print(刪除+front.next.data.toString()+，); front.next = front.next.next; /刪除front的后繼結(jié)點(diǎn)，包括頭、中間/尾刪除 n-; System.out.println(list.toString(); System.out.println(被赦免者是+list.get(0).toString();/get(0)獲得元素，O(1)執(zhí)行new Josephus(5,0,3)，單鏈表的變化過程如圖2.7所示。圖2.7 使用單鏈表求解Josephus(5,0,3)環(huán)問題的執(zhí)行過程【習(xí)2.8】 集合并運(yùn)算，單鏈表深拷貝的應(yīng)用。本題目的： 單鏈表作為方法參數(shù)與返回值，傳遞對象引用； 單鏈表深拷貝應(yīng)用。當(dāng)對象作為方法的參數(shù)或返回值時(shí)，參數(shù)傳遞原則同賦值，“引用參數(shù)傳遞對象引用”，即形式參數(shù)獲得實(shí)際參數(shù)的對象引用。SinglyList單鏈表類聲明以下成員方法，實(shí)現(xiàn)集合并運(yùn)算。/在this單鏈表之后連接list的所有結(jié)點(diǎn)，集合并；設(shè)置list為空，O(n) public void concat(SinglyList list) Node rear=this.head; while (rear.next!=null) /尋找this單鏈表的最后一個(gè)結(jié)點(diǎn) rear = rear.next; rear.next = list.head.next; /尾插入list單鏈表 list.head.next=null; /設(shè)置list為空，否則邏輯錯(cuò)。方法體內(nèi)可改變參數(shù)list引用的單鏈表/復(fù)制list所有結(jié)點(diǎn)插入到this單鏈表之后，集合并，不改變listpublic void addAll(SinglyList list) this.concat(new SinglyList(list); /先執(zhí)行單鏈表深拷貝，再連接復(fù)制的list/返回復(fù)制this和list合并連接的單鏈表，并集，不改變this和listpublic SinglyList union(SinglyList list) SinglyList result = new SinglyList(this); /深拷貝this單鏈表 result.addAll(list); return result; /返回result引用的單鏈表，釋放result變量設(shè)創(chuàng)建單鏈表lista和listb，分別調(diào)用上述方法，算法描述如圖2.14所示。圖2.8 集合并運(yùn)算，單鏈表深拷貝的應(yīng)用4. 循環(huán)單鏈表【思考題2-10】能否使用以下語句創(chuàng)建循環(huán)單鏈表的頭結(jié)點(diǎn)？為什么？head = new Node(null, head); /創(chuàng)建循環(huán)單鏈表的頭結(jié)點(diǎn)【答】不能。因?yàn)樯暾埥Y(jié)點(diǎn)存儲(chǔ)空間時(shí)head沒有初始化，不是null。實(shí)際語義需要的是將該結(jié)點(diǎn)地址作為其next域值，做不到。2.3.2 雙鏈表1. 雙鏈表結(jié)點(diǎn)習(xí)2-11 DoubleNode類能否聲明如下，繼承單鏈表結(jié)點(diǎn)類Node？為什么？public class DoubleNode extends Node /雙鏈表結(jié)點(diǎn)類，繼承單鏈表結(jié)點(diǎn)類 public DoubleNode prev; /指向前驅(qū)結(jié)點(diǎn)的地址域【答】不能。 雖然該聲明沒有語法錯(cuò)，但有語義錯(cuò)，因?yàn)閺母割惱^承來的next類型為Node，仍然指向單鏈表結(jié)點(diǎn)，等價(jià)于以下聲明：public class DoubleNode /雙鏈表結(jié)點(diǎn)類 public T data; public Node next; /邏輯錯(cuò)誤 public DoubleNode prev; ;此處需要next指向雙鏈表結(jié)點(diǎn)，類型是DoubleNode，兩者結(jié)點(diǎn)結(jié)構(gòu)不同。 雖然從語法上DoubleNode可以聲明如下，將next重新聲明為DoubleNode類型，但是雙鏈表結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)無關(guān)，并不是兩個(gè)具有包含關(guān)系的概念。public class DoubleNode extends Node public DoubleNode prev,next; /prev指向前驅(qū)結(jié)點(diǎn)，next指向后繼結(jié)點(diǎn) public DoubleNode(T data,DoubleNode prev,DoubleNode next) / super(data,next); /語義錯(cuò)，賦值super.next（類型為Node） super(data,null); this.next = next; /賦值this.next（類型為DoubleNode） this.prev = prev; %注意：此時(shí)DoubleNode類有兩個(gè)next，使用this和super引用可區(qū)分兩者，從父類繼承來的super.next類型為Node；子類重新聲明的this.next類型為DoubleNode，this.next隱藏super.next，構(gòu)造方法中super(data,next);語句對super.next賦值。如此聲明，沒有意義。習(xí)2-12 DoubleNode類是否需要聲明析構(gòu)方法和拷貝構(gòu)造方法？為什么？【答】參見前述【習(xí)題2-8】。2. 雙鏈表【思考題2-11】設(shè)p指向雙鏈表某個(gè)結(jié)點(diǎn)，寫出在p結(jié)點(diǎn)之后插入值為x結(jié)點(diǎn)的語句?！敬稹空Z句如下：DoubleNode q = new DoubleNode(x,p,p.next); /插入在p結(jié)點(diǎn)之后if (p.next!=null) /中間插入 p.next.prev = q; /p.next = q; /再問：如果后兩條語句次序顛倒，將會(huì)怎樣？【答】導(dǎo)致錯(cuò)誤，如圖2.10所示，p.next.prev = q相當(dāng)于q.prev = q。 圖2.9 雙鏈表后插入結(jié)點(diǎn)時(shí)語句次序錯(cuò)誤3. 循環(huán)雙鏈表習(xí)2-13 循環(huán)雙鏈表類能否聲明為如下繼承單鏈表類，繼承head成員變量？為什么？public class CirDoublyList extends SinglyList /循環(huán)雙鏈表類，繼承單鏈表類【答】不能。因?yàn)?，如果繼承，等價(jià)于以下聲明：public class CirDoublyList extends SinglyList /循環(huán)雙鏈表類，繼承單鏈表類 Node head; /繼承父類的成員變量，數(shù)據(jù)類型錯(cuò)誤;其中，head的數(shù)據(jù)類型是Node，指向單鏈表結(jié)點(diǎn)，類型錯(cuò)誤。應(yīng)該是DoubleNode。再者，循環(huán)雙鏈表和單鏈表是實(shí)現(xiàn)線性表的兩種存儲(chǔ)結(jié)構(gòu)，兩者之間沒有關(guān)聯(lián)，不是繼承關(guān)系?？梢灾挥醒h(huán)雙鏈表，而沒有單鏈表?！玖?xí)2.10】 循環(huán)雙鏈表的迭代方法。以下4個(gè)方法實(shí)現(xiàn)循環(huán)雙鏈表的迭代功能，時(shí)間復(fù)雜度都是O(1)，這就是設(shè)計(jì)循環(huán)雙鏈表的目的。public DoubleNode first() /返回循環(huán)雙鏈表第一個(gè)結(jié)點(diǎn)，O(1) return (head.next=head) ? null : head.next;public DoubleNode next(DoubleNode p) /返回p的后繼結(jié)點(diǎn)，O(1) return (head.next=head | p=null | p=head | p=head.prev) ? null : p.next;public DoubleNode previous(DoubleNode p) /返回p的前驅(qū)結(jié)點(diǎn)，O(1) return (head.next=head | p=null | p=head | p=head.next) ? null : p.prev;public DoubleNode last() /返回循環(huán)雙鏈表最后一個(gè)結(jié)點(diǎn)，O(1) return (head.prev=head) ? null : head.prev;【習(xí)2.11】 循環(huán)雙鏈表合并連接。設(shè)已創(chuàng)建兩條循環(huán)雙鏈表，CirDoublyList類聲明以下成員方法，將它們首尾相接實(shí)現(xiàn)合并連接，算法描述如圖2.11所示。/在this循環(huán)雙鏈表之后，合并連接list中所有結(jié)點(diǎn)，并設(shè)置list為空public void addAll(CirDoublyList list) 圖2.10 合并連接兩條循環(huán)雙鏈表第3章 串目的：串作為特殊線性表的實(shí)現(xiàn)與應(yīng)用。內(nèi)容：字符串的基本概念，串抽象數(shù)據(jù)類型，順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串的特點(diǎn)；采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)串的各種操作算法；兩種串的模式匹配算法及應(yīng)用：Brute-Force算法和KMP算法。要求：掌握順序串類的基本操作實(shí)現(xiàn)方法，掌握串的模式匹配算法及應(yīng)用。重點(diǎn)：串?dāng)?shù)據(jù)類型的各種操作實(shí)現(xiàn)，兩種串的模式匹配算法及應(yīng)用。難點(diǎn)：KMP模式匹配算法，next數(shù)組在KMP算法中的作用及產(chǎn)生過程。實(shí)驗(yàn)：順序串類的基本操作及串的模式匹配算法。3.1 串抽象數(shù)據(jù)類型3-1 和 有什么差別？ 【答】是空串，長度為0； 是空格串。3-2 什么是串？串和線性表在概念上有何差別？串操作的主要特點(diǎn)有哪些？【答】字符串（string，簡稱串）是數(shù)據(jù)元素的數(shù)據(jù)類型為字符的線性表。從邏輯結(jié)構(gòu)看，串是一種特殊的線性表，其特殊性在于線性表中的每個(gè)元素是一個(gè)字符。作為一種抽象數(shù)據(jù)類型，串有自己的一組操作，其操作特點(diǎn)與線性表不同。3-3 串的存儲(chǔ)結(jié)構(gòu)有幾種？串通常采用什么存儲(chǔ)結(jié)構(gòu)？【答】串可采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，串通常采用順序存儲(chǔ)結(jié)構(gòu)。3-4 哪些操作會(huì)改變串的長度？當(dāng)串的存儲(chǔ)空間不夠時(shí)，應(yīng)該如何處理？【答】插入、刪除子串會(huì)改變串的長度。當(dāng)串的存儲(chǔ)空間不夠時(shí)，應(yīng)該申請一個(gè)容量更大的數(shù)組，并將原串中的所有字符復(fù)制到新串中。3.2 串的存儲(chǔ)和實(shí)現(xiàn)3.2.1 串的存儲(chǔ)結(jié)構(gòu)3-5 Java語言的a和a有什么差別？它們的存儲(chǔ)結(jié)構(gòu)有什么不同？【答】數(shù)據(jù)類型不同，存儲(chǔ)結(jié)構(gòu)不同。a是char字符常量，占用2個(gè)字節(jié)存儲(chǔ)字符的Unicode編碼；a是字符串常量，數(shù)據(jù)類型是java.lang.String類，采用字符數(shù)組存儲(chǔ)。3.2.2 常量字符串類1. 設(shè)計(jì)字符串類的必要性【習(xí)3.3】 C/C+語言，string.h中的strcpy()和strcat()函數(shù)存在下標(biāo)越界錯(cuò)誤。本題目的：strcpy()和strcat()函數(shù)存在下標(biāo)越界錯(cuò)誤；設(shè)計(jì)字符串類的必要性。#include using namespace std;#include int main() char src=abcdefghijlkmn,dest3=,*p; p = strcpy(dest,src); /復(fù)制src串（包括0）到dest，返回dest地址 coutsrc=src,dest=dest,p=pendl; return 0;程序運(yùn)行結(jié)果如下，復(fù)制前后src和dest兩個(gè)字符串占用的存儲(chǔ)單元如圖3.1所示。src=mn,dest=abcdefghijklmn,p=abcdefghijklmn /有錯(cuò)誤 （a）復(fù)制前（b）復(fù)制后圖3.1 調(diào)用C/C+語言string.h中的strcpy()函數(shù)復(fù)制字符串存在下標(biāo)越界錯(cuò)誤程序運(yùn)行時(shí)，系統(tǒng)為src和dest字符數(shù)組分配了存儲(chǔ)空間，dest空串的元素為0，如圖3.1(a)所示。執(zhí)行復(fù)制語句后，p指針也指向dest數(shù)組，如圖3.1(b)所示，src和dest的復(fù)制結(jié)果都有錯(cuò)誤，src是被復(fù)制者，復(fù)制后卻被改變；dest數(shù)組只聲明了3個(gè)字節(jié)的存儲(chǔ)空間，實(shí)際卻保存了14個(gè)字符。錯(cuò)誤原因是src串較長，dest數(shù)組空間不足，strcpy()函數(shù)復(fù)制過程中，沒有檢查下標(biāo)是否越界，復(fù)制字符超出dest數(shù)組范圍，導(dǎo)致更改了src數(shù)組內(nèi)容，如圖3.2所示。printf()函數(shù)輸出字符串以0字符結(jié)束。Visual C+2008編譯strcpy()函數(shù)時(shí)，有警告：“strcpy函數(shù)不安全”。圖3.2 strcpy()函數(shù)存在下標(biāo)越界錯(cuò)誤的解釋以字符數(shù)組方式表示字符串是不健壯、不安全的，它沒有對數(shù)組所使用的存儲(chǔ)空間進(jìn)行控制，也沒有對數(shù)組下標(biāo)進(jìn)行越界檢查，會(huì)產(chǎn)生更改字符串結(jié)束符0等錯(cuò)誤，strcpy(char *,char *)函數(shù)甚至可以將一個(gè)長字符串復(fù)制到一個(gè)短字符串的字符數(shù)組中，字符數(shù)組使用超出其預(yù)定范圍的存儲(chǔ)空間，非法占用本不屬于它的存儲(chǔ)空間，導(dǎo)致隨意更改其他變量值等嚴(yán)重錯(cuò)誤，strcat(char *,char *)函數(shù)同樣存在下標(biāo)越界錯(cuò)誤。字符串不等同于字符數(shù)組，字符串只是采用字符數(shù)組作為其存儲(chǔ)結(jié)構(gòu)，它要實(shí)現(xiàn)字符串抽象數(shù)據(jù)類型所要求的操作。應(yīng)該將字符串及其操作封裝成字符串類，實(shí)現(xiàn)字符串抽象數(shù)據(jù)類型。2. 常量字符串類實(shí)現(xiàn)【思考題3-1】逆轉(zhuǎn)String串，分析算法效率。本題以逆轉(zhuǎn)String串為例，聲明對String串操作的靜態(tài)方法，分析算法效率。 聲明對String對象操作的靜態(tài)方法如下，算法基于求子串和串連接。public static String reverse(String str) /返回str逆轉(zhuǎn)后的串對象。算法基于求子串和串連接 String temp = ; for (int i=0; istr.length(); i+