數(shù)據(jù)結(jié)構(gòu)-Java語言描述(上)ppt

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第1頁。第1章緒論

第二章線性表

第三章堆棧和隊列

第四章串

第五章數(shù)組，集合和矩陣

第六章遞歸算法數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第2頁。第1章緒論

1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.2抽象數(shù)據(jù)類型1.3算法和算法的時間復(fù)雜度1.4算法的空間復(fù)雜度分析1.5Java語言的工具包數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第3頁。本章主要知識點：數(shù)據(jù)結(jié)構(gòu)的基本概念，包括數(shù)據(jù)、數(shù)據(jù)元素、抽象數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的操作類型、數(shù)據(jù)類型和抽象數(shù)據(jù)類型的概念算法的基本概念，包括算法的定義、性質(zhì)和算法的設(shè)計目標(biāo)算法的時間復(fù)雜度分析，包括O()函數(shù)的定義，幾種典型算法的時間復(fù)雜度分析方法數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第4頁。1.1數(shù)據(jù)結(jié)構(gòu)的基本概念

1數(shù)據(jù)和數(shù)據(jù)元素

數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的抽象描述。表示一個事物的一組數(shù)據(jù)稱作一個數(shù)據(jù)元素；構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)稱作該數(shù)據(jù)元素的數(shù)據(jù)項。數(shù)據(jù)結(jié)構(gòu)課程在討論一種類型的數(shù)據(jù)結(jié)構(gòu)問題時，通常說的是抽象意義上的數(shù)據(jù)元素，是沒有實際含義的。我們把沒有實際含義的數(shù)據(jù)元素稱作抽象數(shù)據(jù)元素。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第5頁。2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的相互聯(lián)系方式稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。按照數(shù)據(jù)元素之間的相互聯(lián)系方式，數(shù)據(jù)的邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)。線性結(jié)構(gòu)的一般定義是：除第一個和最后一個數(shù)據(jù)元素外每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素。樹結(jié)構(gòu)的一般定義是：除根結(jié)點外每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素，可有零個或若干個后繼數(shù)據(jù)元素。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第6頁。

圖結(jié)構(gòu)的一般定義是：每個數(shù)據(jù)元素可有零個或若干個前驅(qū)數(shù)據(jù)元素和零個或若干個后繼數(shù)據(jù)元素。

(a)線性結(jié)構(gòu)；(b)樹結(jié)構(gòu)；(c)圖結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第7頁。數(shù)據(jù)的存儲結(jié)構(gòu)任何需要計算機進(jìn)行管理和處理的數(shù)據(jù)元素都必須首先按某種方式存儲在計算機中。數(shù)據(jù)元素在計算機中的存儲方式稱為數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)存儲結(jié)構(gòu)的基本形式有兩種：一種是順序存儲結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)是把數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存中，程序設(shè)計方法是使用數(shù)組。順序存儲結(jié)構(gòu)的特點是，邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素的存儲位置關(guān)系上。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第8頁。

鏈?zhǔn)酱鎯Y(jié)構(gòu)是用對象的引用把相互直接關(guān)聯(lián)的結(jié)點（即直接前驅(qū)結(jié)點或直接后繼結(jié)點）鏈接起來。鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是，邏輯上相鄰的數(shù)據(jù)元素在物理上（即內(nèi)存存儲位置上）不一定相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點的鏈接關(guān)系上。下圖是包含數(shù)據(jù)元素a0,a1,…,an-1的線性結(jié)構(gòu)的鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖.其中，上一個結(jié)點到下一個結(jié)點的箭頭表示上一個結(jié)點中對象變量域所表示的下一個結(jié)點對象。對象變量head表示了鏈?zhǔn)酱鎯Y(jié)構(gòu)中的第一個結(jié)點對象。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第9頁。

(a)順序存儲結(jié)構(gòu)；(b)鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第10頁。4數(shù)據(jù)的操作對一種類型的數(shù)進(jìn)行的某種方法的處理稱作數(shù)據(jù)的操作，一種類型的數(shù)據(jù)所有的操作集合稱作數(shù)據(jù)的操作集合。數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程主要討論線性表、堆棧、隊列、串、數(shù)組、樹、二叉樹、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)，在討論這些典型的常用數(shù)據(jù)結(jié)構(gòu)時，主要從它們的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)操作三個方面進(jìn)行分析討論。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第11頁。1.2抽象數(shù)據(jù)類型

類型是一組值的集合。

數(shù)據(jù)類型是指一個類型和定義在這個類型上的操作集合。在數(shù)據(jù)結(jié)構(gòu)課程中，通常把在已有的數(shù)據(jù)類型基礎(chǔ)上設(shè)計新的數(shù)據(jù)類型的過程稱作數(shù)據(jù)結(jié)構(gòu)設(shè)計，在這里，數(shù)據(jù)結(jié)構(gòu)的含義和數(shù)據(jù)類型的含義相同。

抽象數(shù)據(jù)類型（AbstractDataType,縮寫為ADT）是指一個邏輯概念上的類型和這個類型上的操作集合。數(shù)據(jù)類型和抽象數(shù)據(jù)類型的不同之處僅僅在于：數(shù)據(jù)類型指的是高級程序設(shè)計語言支持的基本數(shù)據(jù)類型，而抽象數(shù)據(jù)類型指的是在基本數(shù)據(jù)類型支持下用戶新設(shè)計的數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)課程主要討論表、堆棧、隊列、串、數(shù)組、樹、二叉樹、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)，這些典型的常用數(shù)據(jù)結(jié)構(gòu)就是一個個不同的抽象數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第12頁。

1.3算法和算法的時間復(fù)雜度1.3.1算法算法的定義和算法的表示方法算法是描述求解問題方法的操作步驟集合。算法要用某種語言來描述。描述算法的語言主要有三種形式：文字形式：使用文字語言偽碼形式：使用類似于程序設(shè)計語言的語言程序設(shè)計語言形式：使用程序設(shè)計語言數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第13頁。算法的性質(zhì)

算法滿足以下性質(zhì)：（1）輸入性：具有零個或若干個輸入量；（2）輸出性：至少產(chǎn)生一個輸出或執(zhí)行一個有意義操作；（3）有限性：執(zhí)行語句的序列是有限的；（4）確定性：每一條語句的含義明確，無二義性；（5）可執(zhí)行性：每一條語句都應(yīng)在有限的時間內(nèi)完成。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第14頁。

程序和算法的惟一區(qū)別是程序允許無限循環(huán)，而算法不允許無限循環(huán)。構(gòu)成無限循環(huán)的一組語句可以如下：

while(1) //循環(huán)條件永真

{ ...... //任意語句序列

}Java是一種純面向?qū)ο蟪绦蛟O(shè)計語言，在Java中，一個具體的算法表示為類中的一個成員函數(shù)。帶關(guān)鍵字static的成員函數(shù)是可以直接調(diào)用的成員函數(shù)；不帶關(guān)鍵字static的成員函數(shù)要先定義對象，通過向?qū)ο蟀l(fā)消息來調(diào)用成員函數(shù)。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第15頁。

1.3.2算法設(shè)計目標(biāo)算法設(shè)計應(yīng)滿足以下五條目標(biāo)：（1）正確性（2）可讀性（3）健壯性（4）高時間效率（5）高空間效率

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第16頁。

1.3.3算法的時間復(fù)雜度分析

1算法的時間效率度量方法算法的時間效率反映了算法執(zhí)行時間的長短。度量一個算法在計算機上的執(zhí)行時間通常有如下兩種方法：（1）事后統(tǒng)計方法。計算機內(nèi)部均設(shè)有計時功能，可設(shè)計一組或若干組測試數(shù)據(jù)，然后分別運行根據(jù)不同的算法編制的程序，并比較這些程序的實際運行時間，從而確定算法時間效率的優(yōu)劣。

（2）事前分析方法。用數(shù)學(xué)方法直接對算法的時間效率進(jìn)行分析。因為這種分析方法是在計算機上實際運行該算法之前進(jìn)行的，所以稱為事前分析方法。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第17頁。

根據(jù)算法編制的程序在計算機上運行時所消耗的時間與下列因素有關(guān)：

a．書寫算法的程序設(shè)計語言

b．編譯產(chǎn)生的機器語言代碼質(zhì)量

c．機器執(zhí)行指令的速度

d．問題的規(guī)模，即算法的時間效率與算法所處理的數(shù)據(jù)元素個數(shù)n的函數(shù)關(guān)系

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第18頁。O()函數(shù)表示算法的時間效率與算法所處理的數(shù)據(jù)元素個數(shù)n函數(shù)關(guān)系的最常用函數(shù)是O()函數(shù)（O()讀做大O）。該函數(shù)表示算法和所處理數(shù)據(jù)元素個數(shù)n的數(shù)量級關(guān)系。

[定義]算法的時間復(fù)雜度T(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對所有的n(n≥n0)滿足T(n)≤c*f(n)。上述定義表示，算法的時間復(fù)雜度T(n)隨數(shù)據(jù)元素個數(shù)n的增長率和函數(shù)f(n)的增長率在數(shù)量級上相同。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第19頁。3算法的時間復(fù)雜度分析分析一個算法中基本語句執(zhí)行次數(shù)和數(shù)據(jù)元素個數(shù)n的函數(shù)關(guān)系，就可得出該算法的時間復(fù)雜度T(n)。4指數(shù)級時間復(fù)雜度的問題算法的時間復(fù)雜度是衡量一個算法好壞的重要指標(biāo)。一般來說，具有多項式時間復(fù)雜度的算法，是可接受、可實際使用的算法；具有指數(shù)時間復(fù)雜度的算法，是只有當(dāng)n足夠小時才可使用的算法。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第20頁。

1.4算法的空間復(fù)雜度分析算法的空間復(fù)雜度分析主要是分析算法在運行時所需要的內(nèi)存空間的數(shù)量級。算法的空間復(fù)雜度通常也采用O()函數(shù)。算法的空間復(fù)雜度分析方法和算法的時間復(fù)雜度分析方法類同。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第21頁。

1.5Java語言的工具包數(shù)據(jù)結(jié)構(gòu)課程討論的數(shù)據(jù)結(jié)構(gòu)問題都是軟件設(shè)計的基本結(jié)構(gòu)問題。數(shù)據(jù)結(jié)構(gòu)課程討論的基本數(shù)據(jù)結(jié)構(gòu)都可以設(shè)計成通用軟件模塊（如線性表、堆棧、隊列、串、二叉樹等）。

Java類庫（即JavaAPI）提供了許多系統(tǒng)定義的包。其中，工具包（java.util包）中給出了包括順序表、單鏈表、堆棧、隊列、串、二叉樹、哈希表等功能豐富、使用方便的類。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第22頁。第2章線性表2.1線性表2.2順序表2.3單鏈表2.4循環(huán)單鏈表2.5雙向鏈表2.6仿真鏈表2.7面向?qū)ο蟮能浖O(shè)計方法數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第23頁。本章主要知識點：線性表的定義，順序存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)順序表類的設(shè)計方法，順序表插入和刪除操作的實現(xiàn)方法，順序表插入和刪除操作的時間復(fù)雜度單鏈表類的設(shè)計方法，單鏈表插入和刪除操作的實現(xiàn)方法，單鏈表插入和刪除操作的時間復(fù)雜度，順序表和單鏈表的特點對比循環(huán)單鏈表和循環(huán)雙向鏈表的結(jié)構(gòu)和特點數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第24頁。2.1線性表

2.1.1線性表的定義

如果一個數(shù)據(jù)元素序列滿足：（1）除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素；（2）第一個數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素；（3）最后一個數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。則稱這樣的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第25頁。

線性表是一種可以在任意位置進(jìn)行插入和刪除數(shù)據(jù)元素操作的、由n（n≥0）個相同類型數(shù)據(jù)元素a0,a1,a2,...,an-1組成的線性結(jié)構(gòu)。一個有n個數(shù)據(jù)元素a0,a1,a2,...,an-1的線性表通常用符號（a0,a1,a2,...,an-1）表示，其中符號ai（0≤i≤n-1）表示第i個抽象數(shù)據(jù)元素?？站€性表用符號（）表示。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第26頁。數(shù)據(jù)集合線性表的數(shù)據(jù)元素集合可以表示為序列a0,a1,a2,...,an-1，每個數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。操作集合

（1）求當(dāng)前數(shù)據(jù)元素個數(shù)length()

（2）插入數(shù)據(jù)元素insert(i,obj)

（3）刪除數(shù)據(jù)元素delete(i)

（4）取數(shù)據(jù)元素getData(i)

（5）線性表是否空isEmpty()2.1.2線性表抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第27頁。順序存儲結(jié)構(gòu)的線性表稱作順序表。

2.2.1順序表存儲結(jié)構(gòu)實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組。對于線性表，數(shù)組把線性表的數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中。這樣線性表中，邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰，數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲單元的物理前后位置關(guān)系上。

2.2順序表數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第28頁。

順序表的存儲結(jié)構(gòu)如圖所示。其中，a0,a1,a2等表示順序表中存儲的數(shù)據(jù)元素，listArray表示存儲數(shù)據(jù)元素的數(shù)組，maxSize表示數(shù)組的最大允許數(shù)據(jù)元素個數(shù)，size表示數(shù)組的當(dāng)前數(shù)據(jù)元素個數(shù)。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第29頁。2.2.2順序表類

類包含成員變量和成員函數(shù)。成員變量用來表示抽象數(shù)據(jù)類型中定義的數(shù)據(jù)集合，成員函數(shù)用來表示抽象數(shù)據(jù)類型中定義的操作集合。順序表類實現(xiàn)接口List。順序表類的public成員函數(shù)主要是接口List中定義的成員函數(shù)。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第30頁。

2.2.3順序表的效率分析插入和刪除是順序表中時間復(fù)雜度最高的成員函數(shù)。插入時，主要的耗時部分是循環(huán)移動數(shù)據(jù)元素部分。循環(huán)移動數(shù)據(jù)元素的效率和插入的位置i有關(guān)，最壞情況是i=0，需移動size個數(shù)據(jù)元素；最好情況是i=size，需移動0個數(shù)據(jù)元素。平均次數(shù)為：數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第31頁。類似地，刪除時，平均次數(shù)為：

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第32頁。

順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此在順序表中插入和刪除一個數(shù)據(jù)元素成員函數(shù)的時間復(fù)雜度為O（n）。順序表支持隨機讀取，因此，順序表取數(shù)據(jù)元素的時間復(fù)雜度為O（1）。順序表的主要優(yōu)點是：支持隨機讀取，以及內(nèi)存空間利用效率高。順序表的主要缺點是：需要預(yù)先給出（很難準(zhǔn)確）數(shù)組的最大數(shù)據(jù)元素個數(shù)，另外，插入和刪除操作時需要移動較多的數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第33頁。

2.3

單鏈表

指針表示一個數(shù)據(jù)元素邏輯意義上的存儲位置。鏈?zhǔn)酱鎯Y(jié)構(gòu)是基于指針實現(xiàn)的。我們把一個數(shù)據(jù)元素和一個指針稱為一個結(jié)點。

鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針把相互直接關(guān)聯(lián)的結(jié)點（即直接前驅(qū)結(jié)點或直接后繼結(jié)點）鏈接起來。鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為鏈表。根據(jù)結(jié)點構(gòu)造鏈的方法不同，鏈表主要有單鏈表、單循環(huán)鏈表和循環(huán)雙向鏈表三種。這樣，一個數(shù)據(jù)元素集就可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第34頁。

2.3.1單鏈表的結(jié)構(gòu)

單鏈表是構(gòu)成鏈表的每個結(jié)點只有一個指向直接后繼結(jié)點的指針。

1單鏈表的表示方法單鏈表中每個結(jié)點的結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第35頁。單鏈表有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種。我們把指向單鏈表的指針稱為單鏈表的頭指針。頭指針?biāo)傅牟淮娣艛?shù)據(jù)元素的第一個結(jié)點稱作頭結(jié)點。存放第一個數(shù)據(jù)元素的結(jié)點稱作第一個數(shù)據(jù)元素結(jié)點，或稱首元結(jié)點。（a）空鏈；（b）非空鏈數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第36頁。

2帶頭結(jié)點單鏈表和不帶頭結(jié)點單鏈表的比較從線性表的定義可知，線性表要求允許在任意位置進(jìn)行插入和刪除。當(dāng)選用帶頭結(jié)點的單鏈表時，插入和刪除操作的實現(xiàn)方法比不用帶頭結(jié)點單鏈表的實現(xiàn)方法簡單。設(shè)頭指針用head表示，在單鏈表中任意結(jié)點（但不是第一個數(shù)據(jù)元素結(jié)點）前插入一個新結(jié)點的方法如圖2-6所示。算法實現(xiàn)時，首先把插入位置定位在要插入結(jié)點的前一個結(jié)點位置，然后把s表示的新結(jié)點插入單鏈表中。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第37頁。在單鏈表非第一個結(jié)點前插入結(jié)點過程

要在第一個數(shù)據(jù)元素結(jié)點前插入一個新結(jié)點，若采用不帶頭結(jié)點的單鏈表結(jié)構(gòu)，則結(jié)點插入后，頭指針head就要等于新插入結(jié)點s，這和在非第一個數(shù)據(jù)元素結(jié)點前插入結(jié)點時的情況不同。另外，還有一些不同情況需要考慮。因此，算法對這兩種情況就要分別設(shè)計實現(xiàn)方法。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第38頁。

而如果采用帶頭結(jié)點的單鏈表結(jié)構(gòu)，算法實現(xiàn)時，p指向頭結(jié)點，改變的是p指針的next指針的值，而頭指針head的值不變。因此，算法實現(xiàn)方法比較簡單。在帶頭結(jié)點單鏈表中第一個數(shù)據(jù)元素結(jié)點前插入一個新結(jié)點的過程如圖所示。圖在帶頭結(jié)點單鏈表第一個結(jié)點前插入結(jié)點過程數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第39頁。

2.3.2結(jié)點類單鏈表是由一個一個結(jié)點組成的，因此，要設(shè)計單鏈表類，必須先設(shè)計結(jié)點類。結(jié)點類的成員變量有兩個：一個是數(shù)據(jù)元素，另一個是表示下一個結(jié)點的對象引用（即指針）。2.3.3單鏈表類單鏈表類的成員變量至少要有兩個：一個是頭指針，另一個是單鏈表中的數(shù)據(jù)元素個數(shù)。但是，如果再增加一個表示單鏈表當(dāng)前結(jié)點位置的成員變量，則有些成員函數(shù)的設(shè)計將更加方便。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第40頁。2.3.4單鏈表的效率分析

在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第41頁。刪除單鏈表的一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：

因此，單鏈表插入和刪除操作的時間復(fù)雜度均為O（n）。另外，單鏈表取數(shù)據(jù)元素操作的時間復(fù)雜度也為O（n）。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第42頁。2.3.5順序表和單鏈表的比較順序表的主要優(yōu)點是支持隨機讀取，以及內(nèi)存空間利用效率高；順序表的主要缺點是需要預(yù)先給出數(shù)組的最大數(shù)據(jù)元素個數(shù)，而這通常很難準(zhǔn)確作到。當(dāng)實際的數(shù)據(jù)元素個數(shù)超過了預(yù)先給出的個數(shù)，會發(fā)生異常。另外，順序表插入和刪除操作時需要移動較多的數(shù)據(jù)元素。和順序表相比，單鏈表的主要優(yōu)點是不需要預(yù)先給出數(shù)據(jù)元素的最大個數(shù)。另外，單鏈表插入和刪除操作時不需要移動數(shù)據(jù)元素。單鏈表的主要缺點是每個結(jié)點中要有一個指針，因此單鏈表的空間利用率略低于順序表的。另外，單鏈表不支持隨機讀取，單鏈表取數(shù)據(jù)元素操作的時間復(fù)雜度為O（n）；而順序表支持隨機讀取，順序表取數(shù)據(jù)元素操作的時間復(fù)雜度為O（1）。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第43頁。

循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針不再是結(jié)束標(biāo)記，而是指向整個鏈表的第一個結(jié)點，從而使單鏈表形成一個環(huán)。和單鏈表相比，循環(huán)單鏈表的長處是從鏈尾到鏈頭比較方便。當(dāng)要處理的數(shù)據(jù)元素序列具有環(huán)型結(jié)構(gòu)特點時，適合于采用循環(huán)單鏈表。2.4

循環(huán)單鏈表數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第44頁。

和單鏈表相同，循環(huán)單鏈表也有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種，帶頭結(jié)點的循環(huán)單鏈表實現(xiàn)插入和刪除操作時，算法實現(xiàn)較為方便。帶頭結(jié)點的循環(huán)單鏈表結(jié)構(gòu)如下：（a）空鏈表；（b）非空鏈表數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第45頁。

帶頭結(jié)點的循環(huán)單鏈表的操作實現(xiàn)方法和帶頭結(jié)點的單鏈表的操作實現(xiàn)方法類同，差別僅在于：（1）在構(gòu)造函數(shù)中，要加一條head.next=head語句，把初始時的帶頭結(jié)點的循環(huán)單鏈表設(shè)計成圖2-11（a）所示的狀態(tài)。（2）在index(i)成員函數(shù)中，把循環(huán)結(jié)束判斷條件current!=null改為current!=head。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第46頁。

雙向鏈表是每個結(jié)點除后繼指針外還有一個前驅(qū)指針。和單鏈表類同，雙向鏈表也有帶頭結(jié)點結(jié)構(gòu)和不帶頭結(jié)點結(jié)構(gòu)兩種，帶頭結(jié)點的雙向鏈表更為常用；另外，雙向鏈表也可以有循環(huán)和非循環(huán)兩種結(jié)構(gòu)，循環(huán)結(jié)構(gòu)的雙向鏈表更為常用。

2.5

雙向鏈表數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第47頁。

在雙向鏈表中，每個結(jié)點包括三個域，分別是element域、next域和prior域，其中element域為數(shù)據(jù)元素域，next域為指向后繼結(jié)點的對象引用，prior域為指向前驅(qū)結(jié)點的對象引用。圖2-12為雙向鏈表結(jié)點的圖示結(jié)構(gòu)。雙向鏈表結(jié)點的圖示結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第48頁。圖2-13是帶頭結(jié)點的循環(huán)雙向鏈表的圖示結(jié)構(gòu)。從圖2-13可見，循環(huán)雙向鏈表的next和prior各自構(gòu)成自己的循環(huán)單鏈表。帶頭結(jié)點的循環(huán)雙向鏈表（a）空鏈表；（b）非空鏈表數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第49頁。

在雙向鏈表中，有如下關(guān)系：設(shè)對象引用p表示雙向鏈表中的第i個結(jié)點，則p.next表示第i+1個結(jié)點，p.next.prior仍表示第i個結(jié)點，即p.next.prior==p；同樣地，p.prior表示第i-1個結(jié)點，p.prior.next仍表示第i個結(jié)點，即p.prior.next==p。圖2-14是雙向鏈表上述關(guān)系的圖示。圖2-14雙向鏈表的關(guān)系數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第50頁。

循環(huán)雙向鏈表的插入過程如圖2-15所示。圖中的指針p表示要插入結(jié)點的位置，s表示要插入的結(jié)點，①、②、③、④表示實現(xiàn)插入過程的步驟。圖2-15循環(huán)雙向鏈表的插入過程數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第51頁。循環(huán)雙向鏈表的刪除過程如圖2-16所示。圖中的指針p表示要插入結(jié)點的位置，①、②表示實現(xiàn)刪除過程的步驟。循環(huán)雙向鏈表的刪除過程數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第52頁。2.6

仿真鏈表在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，我們實現(xiàn)數(shù)據(jù)元素之間的次序關(guān)系依靠指針。我們也可以用數(shù)組來構(gòu)造仿真鏈表。方法是在數(shù)組中增加一個（或兩個）int類型的變量域，這些變量用來表示后一個（或前一個）數(shù)據(jù)元素在數(shù)組中的下標(biāo)。我們把這些int類型變量構(gòu)造的指針稱為仿真指針。這樣，就可以用仿真指針構(gòu)造仿真的單鏈表（或仿真的雙向鏈表）。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第53頁。（a）常規(guī)單鏈表；（b）仿真單鏈表一；（c）仿真單鏈表二數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第54頁。2.7

面向?qū)ο蟮能浖O(shè)計方法

面向?qū)ο筌浖O(shè)計方法是一種和人類認(rèn)識事物、分析事物方法一致的軟件設(shè)計方法。不僅如此，面向?qū)ο笤O(shè)計方法的模塊化軟件、數(shù)據(jù)封裝、信息隱藏等特點，還可以使軟件設(shè)計可以像其他工業(yè)產(chǎn)品一樣，可以大規(guī)模協(xié)作開發(fā)。模塊化軟件設(shè)計的基本思想是：把基礎(chǔ)軟件設(shè)計成可重復(fù)使用的模塊，這些模塊提供外部調(diào)用的接口，其他程序通過接口使用這些基礎(chǔ)軟件模塊。這樣，軟件工業(yè)將擺脫了小作坊工作方式，像現(xiàn)代的其他工業(yè)一樣，可以進(jìn)行大規(guī)模的協(xié)作生產(chǎn)或開發(fā)。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第55頁。第3章堆棧和隊列3.1堆棧3.2堆棧的應(yīng)用3.3隊列3.4優(yōu)先級隊列數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第56頁。本章主要知識點：

堆棧的基本概念，堆棧的用途順序堆棧類的設(shè)計方法，鏈?zhǔn)蕉褩ｎ惖脑O(shè)計方法隊列的基本概念，隊列的用途順序循環(huán)隊列的基本實現(xiàn)原理，順序循環(huán)隊列的隊空和隊滿判斷方法，順序循環(huán)隊列類的設(shè)計方法鏈?zhǔn)蕉褩ｎ惖脑O(shè)計方法優(yōu)先級隊列的概念，優(yōu)先級隊列的用途，順序優(yōu)先級隊列的入隊列和出隊列操作設(shè)計方法數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第57頁。

3.1

堆棧3.1.1堆棧的基本概念

堆棧（也簡稱作棧）是一種特殊的線性表，堆棧的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其差別是線性表允許在任意位置進(jìn)行插入和刪除操作，而堆棧只允許在固定一端進(jìn)行插入和刪除操作。堆棧中允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。堆棧的插入和刪除操作通常稱為進(jìn)棧或入棧，堆棧的刪除操作通常稱為出棧或退棧。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第58頁。

從輸入和輸出數(shù)據(jù)元素的位置關(guān)系看，堆棧的功能和一種火車調(diào)度裝置的功能類同。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第59頁。3.1.2堆棧抽象數(shù)據(jù)類型１數(shù)據(jù)集合

堆棧的數(shù)據(jù)集合可以表示為a0,a1,…,an-1，每個數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。２操作集合

（1）入棧push(obj)：把數(shù)據(jù)元素obj插入堆棧。（2）出棧pop()：出棧,刪除的數(shù)據(jù)元素由函數(shù)返回。（3）取棧頂數(shù)據(jù)元素getTop()：取堆棧當(dāng)前棧頂?shù)臄?shù)據(jù)元素并由函數(shù)返回。（4）非空否notEmpty()：若堆棧非空則函數(shù)返回true，否則函數(shù)返回false。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第60頁。

3.1.3順序堆棧

1順序堆棧的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的堆棧稱作順序堆棧。順序堆棧的存儲結(jié)構(gòu)示意圖如圖所示。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第61頁。3.1.4鏈?zhǔn)蕉褩ｆ準(zhǔn)酱鎯Y(jié)構(gòu)的堆棧稱作鏈?zhǔn)蕉褩！?/p>

1鏈?zhǔn)蕉褩５拇鎯Y(jié)構(gòu)和單鏈表相同，鏈?zhǔn)蕉褩Ｒ彩怯梢粋€個結(jié)點組成的，每個結(jié)點由兩個域組成，一個是存放數(shù)據(jù)元素的數(shù)據(jù)元素域element，另一個是存放指向下一個結(jié)點的對象引用（即指針）域next。堆棧有兩端，插入數(shù)據(jù)元素和刪除數(shù)據(jù)元素的一端為棧頂，另一端為棧底。鏈?zhǔn)蕉褩６荚O(shè)計成把靠近堆棧頭head的一端定義為棧頂。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第62頁。

依次向鏈?zhǔn)蕉褩Ｈ霔?shù)據(jù)元素a0,a1,a2,...,an-1后，鏈?zhǔn)蕉褩５氖疽鈭D如圖所示。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第63頁。

堆棧是各種軟件系統(tǒng)中應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。括號匹配和表達(dá)式計算是編譯軟件中的基本問題，其軟件設(shè)計中都需要使用堆棧。3.2.1括號匹配問題3.2.2表達(dá)式計算問題3.2堆棧的應(yīng)用數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第64頁。3.3隊列3.3.1隊列的基本概念

隊列（簡稱作隊）也是一種特殊的線性表，隊列的數(shù)據(jù)元素以及數(shù)據(jù)元素間的邏輯關(guān)系和線性表完全相同，其差別是線性表允許在任意位置插入和刪除，而隊列只允許在其一端進(jìn)行插入操作在其另一端進(jìn)行刪除操作。隊列中允許進(jìn)行插入操作的一端稱為隊尾，允許進(jìn)行刪除操作的一端稱為隊頭。隊列的插入操作通常稱作入隊列，隊列的刪除操作通常稱作出隊列。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第65頁。

下圖是一個依次向隊列中插入數(shù)據(jù)元素a0,a1,...,an-1后的示意圖，其中，a0是當(dāng)前隊頭數(shù)據(jù)元素，an-1是當(dāng)前隊尾數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第66頁。3.3.2隊列的抽象數(shù)據(jù)類型1數(shù)據(jù)集合

隊列的數(shù)據(jù)集合可以表示為a0,a1,…,an-1，每個數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。2操作集合（1）入隊列append(obj)：把數(shù)據(jù)元素obj插入隊尾。（2）出隊列delete()：把隊頭數(shù)據(jù)元素刪除并由函數(shù)返回。（3）取隊頭數(shù)據(jù)元素getFront()：取隊頭數(shù)據(jù)元素并由函數(shù)返回。（4）非空否notEmpty()：非空否。若隊列非空，則函數(shù)返回true，否則函數(shù)返回false。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第67頁。隊列抽象數(shù)據(jù)類型的Java接口定義如下：publicinterfaceQueue{ publicvoidappend(Objectobj)throwsException; publicObjectdelete()throwsException; publicObjectgetFront()throwsException; publicbooleannotEmpty();} 數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第68頁。3.3.3順序隊列1順序隊列的存儲結(jié)構(gòu)下圖是一個有6個存儲空間的順序隊列的動態(tài)示意圖，圖中front指示隊頭，rear指示隊尾。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第69頁。2順序隊列的“假溢出”問題順序隊列因多次入隊列和出隊列操作后出現(xiàn)的有存儲空間但不能進(jìn)行入隊列操作的溢出稱作假溢出。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第70頁。順序循環(huán)隊列的基本原理假溢出是由于隊尾rear的值和隊頭front的值不能由所定義數(shù)組下界值自動轉(zhuǎn)為數(shù)組上界值而產(chǎn)生的。因此，解決的方法是把順序隊列所使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。

當(dāng)rear和front達(dá)到maxSize-1后，再加1就自動到0。這樣，就不會出現(xiàn)順序隊列數(shù)組的頭部已空出許多存儲空間，但隊尾卻因數(shù)組下標(biāo)越界而引起溢出的假溢出問題。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第71頁。4順序循環(huán)隊列的隊空和隊滿判斷問題

順序循環(huán)隊列的隊列滿和隊列空狀態(tài)（a）初始化狀態(tài)；（b）隊列滿狀態(tài)；（c）隊列空狀態(tài)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第72頁。

解決順序循環(huán)隊列的隊列滿和隊列空狀態(tài)判斷問題通常有三種方法：（1）少用一個存儲空間當(dāng)少用一個存儲空間時，以隊尾rear加1等于隊頭front為隊列滿的判斷條件，即隊列滿的判斷條件此時為：

(rear+1)%maxSize==front

隊列空的判斷條件仍然為：

rear==front數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第73頁。（2）設(shè)置一個標(biāo)志位添加一個標(biāo)志位。設(shè)標(biāo)志位為tag，初始時置tag=0；每當(dāng)入隊列操作成功就置tag=1；每當(dāng)出隊列操作成功就置tag=0。則隊列空的判斷條件為：

rear==front&&tag==0

隊列滿的判斷條件為：

rear==front&&tag==1數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第74頁。（3）設(shè)置一個計數(shù)器添加一個計數(shù)器。設(shè)計數(shù)器為count，初始時置count=0；每當(dāng)入隊列操作成功就使count加1；每當(dāng)出隊列操作成功就使count減1。這樣，該計數(shù)器不僅具有計數(shù)功能，而且還具有像標(biāo)志位一樣的標(biāo)志作用，則此時隊列空的判斷條件為：

count==0

隊列滿的判斷條件為：

count>0&&rear==front

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第75頁。3.3.4順序循環(huán)隊列類3.3.5鏈?zhǔn)疥犃墟準(zhǔn)酱鎯Y(jié)構(gòu)的隊列稱作鏈?zhǔn)疥犃小?/p>

1鏈?zhǔn)疥犃械拇鎯Y(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第76頁。3.4優(yōu)先級隊列優(yōu)先級隊列是帶有優(yōu)先級的隊列。用順序存儲結(jié)構(gòu)實現(xiàn)的優(yōu)先級隊列稱作順序優(yōu)先級隊列。用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的優(yōu)先級隊列稱作鏈?zhǔn)絻?yōu)先級隊列。3.4.1順序優(yōu)先級隊列類順序優(yōu)先級隊列和順序循環(huán)隊列相比主要有兩點不同：（1）對于順序優(yōu)先級隊列來說，出隊列操作不是把隊頭數(shù)據(jù)元素出隊列，而是把隊列中優(yōu)先級最高的數(shù)據(jù)元素出隊列。（2）對于順序優(yōu)先級隊列來說，數(shù)據(jù)元素由兩部分組成，一部分是原先意義上的數(shù)據(jù)元素，另一部分是優(yōu)先級。通常設(shè)計優(yōu)先級為int類型的數(shù)值，并規(guī)定數(shù)值越小優(yōu)先級越高。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第77頁。3.4.2優(yōu)先級隊列的應(yīng)用操作系統(tǒng)中的進(jìn)程管理軟件中就使用了優(yōu)先級隊列。操作系統(tǒng)中使用一個優(yōu)先級隊列來管理進(jìn)程。當(dāng)優(yōu)先級隊列中有若干個進(jìn)程排隊等待系統(tǒng)響應(yīng)，并且CPU資源空閑時，進(jìn)程管理系統(tǒng)就可從優(yōu)先級隊列中找出優(yōu)先級最高的進(jìn)程首先出隊列，從而既達(dá)到了當(dāng)系統(tǒng)繁忙時，所有進(jìn)程都排隊等待，又達(dá)到了實時性要求高的進(jìn)程先被服務(wù)的雙重要求。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第78頁。第4章串4.1串的基本概念及其抽象數(shù)據(jù)

4.2串的存儲結(jié)構(gòu)

4.3串類

4.4串的模式匹配算法數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第79頁。本章主要知識點：串的基本概念串的存儲結(jié)構(gòu)串類的設(shè)計方法，主要是拷貝、插入子串和刪除子串的設(shè)計方法串的模式匹配算法，包括Brute-Force算法和KMP算法數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第80頁。4.1串的基本概念及其抽象數(shù)據(jù)類型4.1.1串的基本概念

串（也稱作字符串）是由n（n≥0）個字符組成的有限序列。

一個串中任意個連續(xù)的字符組成的子序列稱為該串的子串。包含子串的串稱為該子串的主串。一個字符在一個串中的位置序號（為大于等于0的正整數(shù)）稱為該字符在串中的位置。當(dāng)且僅當(dāng)這兩個串的值完全相等時，稱這兩個串相等。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第81頁。4.1.2串的抽象數(shù)據(jù)類型數(shù)據(jù)集合：串的數(shù)據(jù)集合可以表示為字符序列s0,s1,…,sn-1，每個數(shù)據(jù)元素的數(shù)據(jù)類型為字符類型。操作集合：（1）取字符charAt(index)：取index下標(biāo)的字符返回。（2）求長度length()：返回串的長度。（3）比較compareTo(anotherString)：比較當(dāng)前對象串和串a(chǎn)notherString的Unicode碼值的大小。（4）取子串substring(beginIndex,endIndex)：取當(dāng)前對象串中從beginIndex下標(biāo)開始、至endIndex下標(biāo)的前一下標(biāo)止的子串?dāng)?shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第82頁。（5）連接concat(str)：把串str連接到當(dāng)前對象串的末尾。（6）插入子串insert(str,pos)：在當(dāng)前對象串的第pos個字符前插入子串str。（7）刪除子串delete(beginIndex,endIndex)：刪除當(dāng)前對象串中從beginIndex下標(biāo)開始、至endIndex下標(biāo)的前一下標(biāo)止的子串。（8）輸出串值myPrint()：輸出當(dāng)前對象的串值。（9）查找子串index(subStr,start)：在當(dāng)前對象串的start下標(biāo)開始，查找是否存在子串subStr。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第83頁。4.2串的存儲結(jié)構(gòu)1串的順序存儲結(jié)構(gòu)串的順序存儲結(jié)構(gòu)就是用字符類型數(shù)組存放串的所有字符。表示串的長度通常有兩種方法：（1）設(shè)置一個串的長度參數(shù)。（2）在串值的末尾添加結(jié)束標(biāo)記。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第84頁。

串值長度的第一種表示方法下，串的成員變量應(yīng)包括如下兩項：

char[]value;intcount;

其中，value為存儲串值的字符類型數(shù)組名，count表示串值的長度。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第85頁。

2串的鏈?zhǔn)酱鎯Y(jié)構(gòu)串的鏈?zhǔn)酱鎯Y(jié)構(gòu)就是把串值分別存放在構(gòu)成鏈表的若干個結(jié)點的數(shù)據(jù)元素域上。有單字符結(jié)點鏈和塊鏈兩種。單字符結(jié)點鏈就是每個結(jié)點的數(shù)據(jù)元素域只包括一個字符。塊鏈就是每個結(jié)點的數(shù)據(jù)元素域包括若干個字符。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第86頁。4.3串類4.3.1MyString類4.3.2MyString類的測試4.3.3MyStringBuffer類4.3.4MyStringBuffer類的測試數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第87頁。4.4串的模式匹配算法4.4.1Brute-Force算法（1）從主串s的第一個字符開始和模式串t的第一個字符比較,若相等則繼續(xù)比較后續(xù)字符；（2）若主串s的第一個字符和模式串t的第一個字符比較不相等，則從主串s的第二個字符開始重新與模式串t的第一個字符比較，若相等則繼續(xù)比較后續(xù)字符

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第88頁。（3）若主串s的第二個字符與模式串t的第一個字符比較不相等，則從主串s的第三個字符開始重新與模式串t的第一個字符比較；（4）如此不斷繼續(xù)。若存在模式串t中的每個字符依次和主串s中的一個連續(xù)字符序列相等，則模式匹配成功，函數(shù)返回模式串t的第一個字符在主串s中的下標(biāo)；若比較完主串s的所有字符序列，不存在一個和模式串t相等的子串，則模式匹配失敗，函數(shù)返回-1。設(shè)主串s=“cddcdc”,模式串t=“cdc”,模式匹配過程如圖：數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第89頁。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第90頁。Brute-Force算法模式匹配的一般性過程如圖：數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第91頁。4.4.2KMP算法Brute-Force算法的缺點以及解決方法分析

KMP算法是在Brute-Force算法基礎(chǔ)上的改進(jìn)算法。KMP算法的特點主要是，消除了Brute-Force算法的主串比較位置在相當(dāng)多個字符比較相等后，只要有一個字符比較不相等，主串位置便需要回退的缺點。

Brute-Force算法的匹配過程可以發(fā)現(xiàn)，算法中的主串比較位置的回退并非一定必要。這可分兩種情況:數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第92頁。

（1）第一種情況。主串s=“cddcdc”、模式串t=“cdc”的模式匹配過程為：當(dāng)s0=t0，s1=t1，s2≠t2時，算法中下一次的比較位置為i=1,j=0，即下來比較s1和t0。但是因t0≠t1，而s1=t1，所以一定有s1≠t0。所以此時比較s1和t0無意義，實際上隨后可直接比較s2和t0。（2）第二種情況。主串s=“abacabab”、模式串t=“abab”的第一次匹配過程如圖4-5所示。此時有s0＝t0＝’a’，s1＝t1＝’b’，s2＝t2＝’a’，s3≠t3。因有t0≠t1，s1=t1，所以必有s1≠t0。又因有t0=t2，s2=t2，所以必有s2=t0，因此下來可直接比較s3和t1。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第93頁。KMP算法的改進(jìn)模式串中是否存在可相互重疊的真子串，只與模式串自身有關(guān)，與主串無關(guān)。因此，對于主串s=“s0s1…sn-1”，子串t=“t0t1…tm-1”，可以首先計算出模式串t中每個字符的最大真子串的字符個數(shù)k。當(dāng)模式匹配比較到si≠tj（0≤i<n,0≤j<m）時，隨后要比較的主串的下標(biāo)值不變，模式串的下標(biāo)值即為k。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第94頁。3模式串中最大真子串的求法模式串中每個字符的最大真子串構(gòu)成一個數(shù)組，定義為模式串的next[j]函數(shù)。模式串的next[j]函數(shù)定義如下：

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第95頁。4KMP函數(shù)設(shè)計KMP算法的模式匹配過程如圖所示

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第96頁。

KMP函數(shù)可按如下方法設(shè)計：設(shè)s為主串，t為模式串，i為主串當(dāng)前比較字符的下標(biāo)，j為模式串當(dāng)前比較字符的下標(biāo)。令i的初值為start，j的初值為0。當(dāng)si=tj時，i和j分別增1再繼續(xù)比較；否則i不變，j改變?yōu)閚ext[j]值再繼續(xù)比較。比較過程有兩種情況：一是j增加到某個值或j退回到某個j=next[j]值時有si=tj，則此時i和j分別增1再繼續(xù)比較；二是j退回到j(luò)=-1時，令主串和子串的下標(biāo)各增1，隨后比較si+1和t0。這樣的循環(huán)過程直到變量i大于等于主串s的長度或變量j大于等于子串t的長度終止。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第97頁。5計算next[j]值的函數(shù)設(shè)計方法設(shè)有next[j]=k，即在模式串t中存在“t0t1…tk-1”=“tj-ktj-k+1…tj-1”（0<k<j），其中k為滿足等式的最大值，則計算next[j+1]的值有兩種情況：（1）若tk=tj，則表明在模式串t中有“t0t1…tk”=“tj-ktj-k+1…tj”，且不可能存在任何一個k’>k滿足上式，因此有：next[j+1]=next[j]+1=k+1

（2）若tk≠tj，則可把計算next[j+1]值的問題看成是一個如圖4-7的模式匹配問題，即把模式串t’向右滑動至k’=next[k]（0<k’<k<j）。若此時tk’＝tj，則表明在模式串t中有“t0t1…tk’”=“tj-k’tj-k’+1…tj”（0<k’<k<j），因此有：

next[j+1]=k’+1=next[k]+1數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第98頁。求next[j+1]的模式匹配數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第99頁。第5章數(shù)組、集合和矩陣5.1數(shù)組5.2向量類5.3集合5.4矩陣類5.5特殊矩陣5.6稀疏矩陣數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第100頁。本章主要知識點：數(shù)組的定義、實現(xiàn)機制和Java語言支持的數(shù)組功能向量類擴充的數(shù)組功能以及這些擴充功能的實現(xiàn)方法集合的概念和集合類的設(shè)計方法矩陣類的設(shè)計方法特殊矩陣的概念和特殊矩陣的壓縮存儲方法稀疏矩陣的概念和稀疏矩陣的壓縮存儲方法，主要是稀疏矩陣的三元組以及三元組的幾種典型存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第101頁。5.1數(shù)組

5.1.1數(shù)組的定義

數(shù)組是n（n≥1）個相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,...,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限集合。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第102頁。5.1.2數(shù)組的實現(xiàn)機制數(shù)組通常以字節(jié)為內(nèi)部計數(shù)單位。對一個有n個數(shù)據(jù)元素的一維數(shù)組，設(shè)a0是下標(biāo)為0的數(shù)組元素，Loc(a0)是a0的內(nèi)存單元地址，k是每個數(shù)據(jù)元素所需的字節(jié)個數(shù)，則數(shù)組中任一數(shù)據(jù)元素ai的內(nèi)存單元地址Loc(ai)可由下面公式求出：

Loc(ai)=Loc(a0)+i×k(0≤i＜n)5-

對一個m行n列的二維數(shù)組，設(shè)a00是行下標(biāo)和列下標(biāo)均為0的數(shù)組元素，Loc(a00)是a00的存儲地址，k是每個數(shù)據(jù)元素所需的字節(jié)個數(shù)，則數(shù)組中任一數(shù)據(jù)元素aij的內(nèi)存單元地址Loc(aij)可由下面公式求出：

Loc(aij)=Loc(a00)+(i×n+j)×k(0≤i＜m,0≤j＜n）數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第103頁。二維數(shù)組的順序存儲結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第104頁。5.1.3數(shù)組抽象數(shù)據(jù)類型

數(shù)據(jù)集合

數(shù)組的數(shù)據(jù)集合可以表示為a0,a1,a2,...,an-1，且限定數(shù)組元素必須存儲在地址連續(xù)的內(nèi)存單元中。

操作集合：（1）分配內(nèi)存空間acclocate()：為數(shù)組分配用戶所需的內(nèi)存空間。（2）取數(shù)組長度getLength()：取數(shù)組的長度。（3）存數(shù)組元素set(i,x)：把數(shù)據(jù)元素x存入下標(biāo)為i的數(shù)組中。其約束條件為：0≤i≤getLength()-1。（4）取數(shù)組元素get(i)：取出數(shù)組中下標(biāo)為i的數(shù)據(jù)元素。其約束條件為：0≤i≤getLength()-1。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第105頁。5.1.4Java語言支持的數(shù)組功能

1基本數(shù)據(jù)類型的數(shù)組

由于數(shù)組是非常基礎(chǔ)的程序設(shè)計語言要素，所以Java語言設(shè)計實現(xiàn)了數(shù)組功能。Java語言（以及大部分高級程序設(shè)計語言）支持的數(shù)組操作有：（1）分配內(nèi)存空間（2）獲得數(shù)組長度（3）存數(shù)組元素（4）取數(shù)組元素

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第106頁。2

對象數(shù)組

除了可以定義基本數(shù)據(jù)類型的數(shù)組外，Java語言還可以定義對象數(shù)組。

對象數(shù)組的存取操作

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第107頁。5.2向量類

Java語言只直接支持上述基本的數(shù)組操作。如果程序開始時定義的數(shù)組長度為10，且數(shù)組中已經(jīng)存放了若干數(shù)據(jù)元素，要在程序運行過程中擴充數(shù)組長度為20，且把數(shù)組中原先存放的數(shù)據(jù)元素原樣保存，則系統(tǒng)不提供直接支持，需要應(yīng)用程序自己實現(xiàn)。為了擴充數(shù)組功能，Java類庫還定義了Vector類。要說明的是，國內(nèi)的大部分教材和科技書籍都把Vector類翻譯為向量類，但這里的向量和數(shù)學(xué)上的向量概念完全不同。

向量類Vector擴充了數(shù)組的功能，提供了自動擴充數(shù)組長度、且把數(shù)組中原先存放的數(shù)據(jù)元素原樣保存的功能。Vector類在java.util包中

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第108頁。5.3集合5.3.1集合的概念

集合（Set）是具有某種相似特性的事物的全體。換一種說法，也可以說，集合是某種具有相同數(shù)據(jù)類型的數(shù)據(jù)元素全體。如果一個數(shù)據(jù)元素x在一個集合A中，則說數(shù)據(jù)元素x屬于集合A；如果一個數(shù)據(jù)元素x不在一個集合A中，就說數(shù)據(jù)元素x不屬于集合A。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第109頁。

如果集合A中的所有數(shù)據(jù)元素都在集合B中，則說集合B包含集合A。

集合的運算主要有三種：兩個集合的并A∪B、兩個集合的交A∩B、兩個集合的差A(yù)-B。沒有一個數(shù)據(jù)元素的集合稱做空集合數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第110頁。5.3.2集合抽象數(shù)據(jù)類型

數(shù)據(jù)集合

數(shù)據(jù)元素集合可以表示為{a0,a1,a2,...,an-1}，每個數(shù)據(jù)元素的數(shù)據(jù)類型可以是任意的類類型。操作集合

（1）添加add(obj)：在集合中添加數(shù)據(jù)元素obj。（2）刪除remove(obj)：刪除集合中的數(shù)據(jù)元素obj。（3）屬于contain(obj)：數(shù)據(jù)元素obj是否屬于集合。是則返回true,否則返回false。（4）包含include(otherSet)：當(dāng)前對象集合是否包含集合otherSet。是則返回true,否則返回false。（5）相等eqauls(otherSet)：當(dāng)前對象集合是否和集合otherSet相等。是則返回true,否則返回false。（6）數(shù)據(jù)元素個數(shù)size()：返回集合中的數(shù)據(jù)元素個數(shù)。（7）集合空否isEmpty()：若集合空返回true，否則返回false。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第111頁。5.3.3集合類

集合的特點是數(shù)據(jù)元素?zé)o序且不重復(fù)。集合類既可以基于向量類來實現(xiàn)，也可以用其他方法實現(xiàn)。常用的另一種實現(xiàn)方法是基于哈希表來實現(xiàn)?；谙蛄款惖募项悓崿F(xiàn)方法:1MyVector類增加的成員函數(shù)

2集合類MySet3集合類MySet的測試

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第112頁。5.4矩陣類矩陣是工程設(shè)計中經(jīng)常使用的數(shù)學(xué)工具。矩陣用兩維數(shù)組處理最為方便。二維數(shù)組存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第113頁。5.5特殊矩陣

特殊矩陣是指這樣一類矩陣，其中有許多值相同的元素或有許多零元素，且值相同的元素或零元素的分布有一定規(guī)律。一般采用二維數(shù)組來存儲矩陣元素。但是，對于特殊矩陣，可以通過找出矩陣中所有值相同元素的數(shù)學(xué)映射公式，只存儲相同元素的一個副本，從而達(dá)到壓縮存儲數(shù)據(jù)量的目的。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第114頁。5.5.1特殊矩陣的壓縮存儲

1只存儲相同矩陣元素的一個副本此種壓縮存儲方法是：找出特殊矩陣數(shù)據(jù)元素的分布規(guī)律，只存儲相同矩陣元素的一個副本。

n階對稱矩陣的壓縮存儲對應(yīng)關(guān)系

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第115頁。2采用不等長的二維數(shù)組

Java語言支持不等長的二維數(shù)組，對于n階對稱矩陣，也可以通過只申請存儲下三角（或上三角）矩陣元素所需的二維數(shù)組，來達(dá)到壓縮存儲的目的。

不等長的二維數(shù)組結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第116頁。5.6稀疏矩陣

對一個m×n的矩陣，設(shè)s為矩陣元素個數(shù)的總和，有s=m*n，設(shè)t為矩陣中非零元素個數(shù)的總和，滿足t＜＜s的矩陣稱作稀疏矩陣。符號“＜＜”讀作小于小于。簡單說，稀疏矩陣就是非零元素個數(shù)遠(yuǎn)遠(yuǎn)小于元素個數(shù)的矩陣。相對于稀疏矩陣來說，一個不稀疏的矩陣也稱作稠密矩陣。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第117頁。5.6.1稀疏矩陣的壓縮存儲

稀疏矩陣的壓縮存儲方法，是只存儲矩陣中的非零元素。稀疏矩陣中每個非零元素及其對應(yīng)的行下標(biāo)和列下標(biāo)構(gòu)成一個三元組，稀疏矩陣中所有這樣的三元組構(gòu)成一個以三元組為數(shù)據(jù)元素的線性表。

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第118頁。稀疏矩陣和對應(yīng)的三元組線性表數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第119頁。

稀疏矩陣的壓縮存儲結(jié)構(gòu)主要有三元組的數(shù)組結(jié)構(gòu)存儲和三元組的鏈表結(jié)構(gòu)存儲兩大類型。三元組的數(shù)組結(jié)構(gòu)存儲就是把稀疏矩陣的所有三元組按某種規(guī)則存儲在一個一維數(shù)組中。三元組的鏈表結(jié)構(gòu)存儲就是把稀疏矩陣的所有三元組存儲在一個鏈表中。5.6.2數(shù)組結(jié)構(gòu)的稀疏矩陣類

1三元組類

三元組的數(shù)組結(jié)構(gòu)存儲，就是把所有三元組存儲在一個數(shù)組中。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第120頁。2稀疏矩陣類對于稀疏矩陣來說，矩陣的行數(shù)、列數(shù)和非零元個數(shù)是矩陣操作的基本數(shù)據(jù)，因此，這些成分要設(shè)計為成員變量。另外，要用數(shù)組保存所有三元組，因此，要把MyVector類的對象設(shè)計為成員變量。數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第121頁。

數(shù)組結(jié)構(gòu)稀疏矩陣三元組的內(nèi)存示意圖

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第122頁。

轉(zhuǎn)置操作的內(nèi)存示意圖（a）無序轉(zhuǎn)置；（b）有序轉(zhuǎn)置數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第123頁。5.6.3三元組鏈表

稀疏矩陣的所有三元組也可采用鏈表結(jié)構(gòu)存儲。用鏈表存儲的稀疏矩陣三元組簡稱三元組鏈表。在三元組鏈表中每個結(jié)點的數(shù)據(jù)域由稀疏矩陣非零元的行號、列號和元素值組成。

帶頭結(jié)點的三元組鏈表結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第124頁。

行指針數(shù)組結(jié)構(gòu)的三元組鏈表

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第125頁。

三元組十字鏈表

數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第126頁。第6章遞歸算法6.1遞歸的概念6.2遞歸算法的執(zhí)行過6.3遞歸算法的設(shè)計方法6.4遞歸過程和運行時棧6.5遞歸算法的效率分析6.6遞歸算法到非遞歸算法的轉(zhuǎn)換6.7設(shè)計舉例數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第127頁。本章主要知識點：遞歸的概念遞歸算法的設(shè)計方法遞歸算法的執(zhí)行過程遞歸算法的效率數(shù)據(jù)結(jié)構(gòu)——Java語言描述(上)ppt全文共150頁，當(dāng)前為第128頁。6.1遞歸的概念

若一個算法直接地或間接地調(diào)用自己本身，則稱這個算法是遞歸算法。

1.問題的定義是遞歸的例如：階乘函數(shù)的定義

1

當(dāng)n=0時

n=n*(n-1)當(dāng)n>0時數(shù)