算法與數(shù)據(jù)結(jié)構(gòu)

1、.1 .2 目前，計(jì)算機(jī)已深入到社會(huì)生活的各個(gè)領(lǐng)域，其應(yīng)目前，計(jì)算機(jī)已深入到社會(huì)生活的各個(gè)領(lǐng)域，其應(yīng) 用已不再僅僅局限于科學(xué)計(jì)算，而更多的是用于控制，用已不再僅僅局限于科學(xué)計(jì)算，而更多的是用于控制， 管理及數(shù)據(jù)處理等非數(shù)值計(jì)算領(lǐng)域。計(jì)算機(jī)是一門研究管理及數(shù)據(jù)處理等非數(shù)值計(jì)算領(lǐng)域。計(jì)算機(jī)是一門研究 用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩 個(gè)問題：信息的個(gè)問題：信息的表示表示，信息的，信息的處理處理。 信息的表示和組織又直接關(guān)系到處理信息的程序的信息的表示和組織又直接關(guān)系到處理信息的程序的 效率。隨著應(yīng)用問題的不斷復(fù)雜，導(dǎo)致信息量劇增與信效

2、率。隨著應(yīng)用問題的不斷復(fù)雜，導(dǎo)致信息量劇增與信 息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大， 結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問題中的對(duì)象結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問題中的對(duì)象 的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門 課所要研究的問題。課所要研究的問題。 .3 編寫解決實(shí)際問題的程序的一般過程： 如何用數(shù)據(jù)形式描述問題?即由問題抽象出一個(gè) 適當(dāng)?shù)臄?shù)學(xué)模型; 問題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系; 如何在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系? 處理問題時(shí)需要對(duì)數(shù)據(jù)作何

3、種運(yùn)算? 所編寫的程序的性能是否良好? 上面所列舉的問題基本上由數(shù)據(jù)結(jié)構(gòu)這門課程來回答。 計(jì)算機(jī)求解問題的一般步驟計(jì)算機(jī)求解問題的一般步驟 .4 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中的一門綜合性是計(jì)算機(jī)科學(xué)中的一門綜合性 專業(yè)基礎(chǔ)課。是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三專業(yè)基礎(chǔ)課。是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三 者之間的一門核心課程，不僅是一般程序設(shè)計(jì)的基礎(chǔ)，者之間的一門核心課程，不僅是一般程序設(shè)計(jì)的基礎(chǔ)， 而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及 其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。

4、.5 姓名電話號(hào)碼 陳李四。 例例1：電話號(hào)碼查詢系統(tǒng)：電話號(hào)碼查詢系統(tǒng) 設(shè)有一個(gè)電話號(hào)碼薄，它記錄了設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其個(gè)人的名字和其 相應(yīng)的電話號(hào)碼，假定按如下形式安排：相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中其中ai, bi(i=1，2n) 分別表示某人的分別表示某人的 名字和電話號(hào)碼。名字和電話號(hào)碼。 本問題是一種典型的表格問題本問題是一種典型的表格問題。如如 表表1-1，數(shù)據(jù)與數(shù)據(jù)成簡單的一對(duì)一的，數(shù)據(jù)與數(shù)據(jù)成簡單的一對(duì)一的線性關(guān)系線性關(guān)系。 表表1-1線

5、性表結(jié)構(gòu)線性表結(jié)構(gòu) .6 例2：磁盤目錄文件系統(tǒng) 磁盤根目錄下有很多子目錄及文件， 每個(gè)子目錄里又可以包含多個(gè)子目錄 及文件，但每個(gè)子目錄只有一個(gè)父目 錄，依此類推： 本問題是一種典型的樹型結(jié)構(gòu)問 題，如圖1-1 ，數(shù)據(jù)與數(shù)據(jù)成一對(duì)多 的關(guān)系，是一種典型的非線性關(guān)系結(jié) 構(gòu)樹形結(jié)構(gòu)。 樹形樹形 .7 例3：交通網(wǎng)絡(luò)圖 從一個(gè)地方到另外一個(gè)地方可以有多條路徑。本問題是一種 典型的網(wǎng)狀結(jié)構(gòu)問題，數(shù)據(jù)與數(shù)據(jù)成多對(duì)多的關(guān)系，是一種非線 性關(guān)系結(jié)構(gòu)。 佛山 惠州 廣州 中山 東莞 深圳 珠海 圖圖1-2 網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu) .8 數(shù)據(jù)(Data) ：是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指 的是所有能輸入到計(jì)

6、算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素(Data Element) ：是數(shù)據(jù)的基本單位，在程序中 通常作為一個(gè)整體來進(jìn)行考慮和處理。 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng) 是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特 性的數(shù)據(jù)描述。 數(shù)據(jù)對(duì)象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是 數(shù)據(jù)的一個(gè)子集。如字符集合C=A,B,C, 。 .9 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是指相互之間具有：是指相互之間具有(存在存在) 一定聯(lián)系一定聯(lián)系(關(guān)系關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)

7、系系(關(guān)系關(guān)系)稱為稱為邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四 種基本類型。種基本類型。 集合集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合同屬于一個(gè)集合”外，外， 沒有其它關(guān)系。沒有其它關(guān)系。 線性結(jié)構(gòu)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。 樹型結(jié)構(gòu)樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì) 多的關(guān)系。多的關(guān)系。 .10 數(shù)據(jù)結(jié)構(gòu)的形式定義是一個(gè)二元

8、組： Data-Structure=(D，S) 其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。 例2：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)B=（K，R） K=k1, k2, , k9 R= ， 畫出這邏輯結(jié)構(gòu)的圖示，并確定那些是起點(diǎn)，那些是終點(diǎn) 圖圖1-3四類基本四類基本 .11 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和 元素之間的關(guān)系的表示。 元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表 示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu) 和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置 來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。 數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義數(shù)

9、據(jù)元素之間的關(guān)系可以是元素之間代表某種含義 的自然關(guān)系，也可以是為處理問題方便而人為定義的的自然關(guān)系，也可以是為處理問題方便而人為定義的 關(guān)系，這種關(guān)系，這種自然或人為定義的自然或人為定義的 “關(guān)系關(guān)系”稱為數(shù)據(jù)元素稱為數(shù)據(jù)元素 之間的之間的邏輯關(guān)系邏輯關(guān)系，相應(yīng)的，相應(yīng)的結(jié)構(gòu)結(jié)構(gòu)稱為稱為邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。 .12 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放 另一個(gè)元素地址的指針(pointer )，用該指針來表示 數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。 例：設(shè)有數(shù)據(jù)集合A=3.0,2.3,5.0,-8.5,11.0 ，兩種不同的存 儲(chǔ)結(jié)構(gòu)。 順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的； 鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)

10、元素存放的地址是否連續(xù)沒有要 求。 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè) 算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采 用的存儲(chǔ)結(jié)構(gòu)。 在C語言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類型 表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 .13 數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分： 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)： 數(shù)據(jù)元素之間邏輯關(guān)系的描述數(shù)據(jù)元素之間邏輯關(guān)系的描述 D_S=（D，S） 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)： 數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯 關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。 數(shù)據(jù)操作數(shù)據(jù)操作： 對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算對(duì)數(shù)據(jù)要

11、進(jìn)行的運(yùn)算。 本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲(chǔ)本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲(chǔ) 結(jié)構(gòu)如圖結(jié)構(gòu)如圖1-4所示。所示。 .14 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 集合圖狀結(jié)構(gòu) 有向圖無向圖 樹形結(jié)構(gòu) 一般樹二叉樹 線性結(jié)構(gòu)線性結(jié)構(gòu) 一般線性表 線性表推廣 廣義表數(shù)組串 受限線性表 棧和隊(duì)列 圖1-5數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖 圖圖1-4 邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu) 線性表線性表 樹樹 圖圖 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 復(fù)合存儲(chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)物理結(jié)構(gòu) .15 數(shù)據(jù)

12、類型(Data Type)：指的是一個(gè)值的集合和定義在該值 集上的一組操作的總稱。 數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念。 在C語言中 數(shù)據(jù)類型有：基本類型和構(gòu)造類型。 數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)象，它不僅要 描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相 互關(guān)系。 .16 數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括： 建立(Create)一個(gè)數(shù)據(jù)結(jié)構(gòu)； 消除(Destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu)； 從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個(gè)數(shù)據(jù)元素； 把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中； 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(Access)； 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改 (Modif

13、y)； 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(Sort)； 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(Search)。 .17 抽象數(shù)據(jù)類型(Abstract Data Type ，簡稱ADT)：是指一 個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。 ADT的定義僅是一組邏輯特性描述， 與其在計(jì)算機(jī)內(nèi)的表 示和實(shí)現(xiàn)無關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù) 學(xué)特性不變，都不影響其外部使用。 ADT的形式化定義是三元組：ADT=(D，S，P) 其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。 .18 ADT的一般定義形式是： ADT 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作： ADT 其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描

14、述。 基本操作的定義是： () 初始條件： 操作結(jié)果： .19 初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng) 滿足的條件滿足的條件;若不滿足，則操作失敗，返回相應(yīng)的出若不滿足，則操作失敗，返回相應(yīng)的出 錯(cuò)信息。錯(cuò)信息。 操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的 變化狀況和變化狀況和 應(yīng)返回的結(jié)果。應(yīng)返回的結(jié)果。 .20 1.3.1 算法 算法(Algorithm)：是對(duì)特定問題求解方法(步驟)的一種描述，是 指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 算法具有以下五個(gè)特性 有窮性： 一個(gè)算法必須總是在執(zhí)

15、行有窮步之后結(jié) 束，且每一步都在有窮時(shí)間內(nèi)完成。 確定性：算法中每一條指令必須有確切的含義。 不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。 可行性： 一個(gè)算法是能行的。即算法描述的操作 都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。 .21 輸入： 一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入 取自于某個(gè)特定的對(duì)象集合。 輸出： 一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出 是同輸入有著某些特定關(guān)系的量。 一個(gè)算法可以用多種方法描述，主要有：使用自然語言描 述；使用形式語言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語言描述。 算法和程序是兩個(gè)不同的概念。一個(gè)計(jì)算機(jī)程序是對(duì)一個(gè)算 法使用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。算法必須可終止意味

16、著不 是所有的計(jì)算機(jī)程序都是算法。 在本門課程的學(xué)習(xí)、作業(yè)練習(xí)、上機(jī)實(shí)踐等環(huán)節(jié)，算法都 用C語言來描述。在上機(jī)實(shí)踐時(shí)，為了檢查算法是否正確，應(yīng)編 寫成完整的C語言程序。 .22 評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn) 正確性(Correctness )： 算法應(yīng)滿足具體問題 的需求。 可讀性(Readability)： 算法應(yīng)容易供人閱讀和 交流。可讀性好的算法有助于對(duì)算法的理解和修改。 健壯性(Robustness)： 算法應(yīng)具有容錯(cuò)處理。 當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇?應(yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。 通用性(Generality)： 算法應(yīng)具有一般性 ，即 算法的處理

17、結(jié)果對(duì)于一般的數(shù)據(jù)集合都成立。 .23 算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行 所消耗的時(shí)間來度量。其方法通常有兩種： 事后統(tǒng)計(jì)：計(jì)算機(jī)內(nèi)部進(jìn)行執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)。 問題：必須先運(yùn)行依據(jù)算法編制的程序；依賴軟硬件環(huán)境， 容易掩蓋算法本身的優(yōu)劣；沒有實(shí)際價(jià)值。 事前分析：求出該算法的一個(gè)時(shí)間界限函數(shù)。 效率與存儲(chǔ)量需求效率與存儲(chǔ)量需求： 效率指的是算法執(zhí)行的時(shí)效率指的是算法執(zhí)行的時(shí) 間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存 儲(chǔ)空間。一般地，這兩者與問題的規(guī)模有關(guān)。儲(chǔ)空間。一般地，這兩者與問題的規(guī)模有關(guān)。 .24 與此相關(guān)的因

18、素有： 依據(jù)算法選用何種策略； 問題的規(guī)模； 程序設(shè)計(jì)的語言； 編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量； 機(jī)器執(zhí)行指令的速度； 撇開軟硬件等有關(guān)部門因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行 工作量”的大小，只依賴于問題的規(guī)模（通常用n表示），或者 說，它是問題規(guī)模的函數(shù)。 .25 算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)， 其時(shí)間量度記作 T(n)=O(f(n)，稱作算法的漸近時(shí)間復(fù)雜度 (Asymptotic Time complexity)，簡稱時(shí)間復(fù)雜度。 一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度 (重復(fù)執(zhí)行的次數(shù))來表示。 “O”的定義： 若f(n)是正整數(shù)n的一個(gè)函數(shù)，則 O(f

19、(n)表示 M0 ，使得當(dāng)n n0時(shí)，| f(n) | M | f(n0) | 。 表示時(shí)間復(fù)雜度的階有： O(1) ：常量時(shí)間階 O (n)：線性時(shí)間階 O(n) ：對(duì)數(shù)時(shí)間階 O(nn) ：線性對(duì)數(shù)時(shí)間階 .26 O (nk)： k2 ，k次方時(shí)間階 例 兩個(gè)n階方陣的乘法 for(i=1，i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik*bkj ; 由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為： nnn=n3時(shí)間復(fù)雜度為T(n)=O(n3) 例 +x; s=0 ; 將x自增看成是基本操作，則語句頻度為，即時(shí)間復(fù)

20、雜度 為(1) 。 .27 如果將s=0也看成是基本操作，則語句頻度為，其時(shí)間復(fù)雜度 仍為(1)，即常量階。 例 for(i=1; i=n; +i) +x; s+=x ; 語句頻度為：2n，其時(shí)間復(fù)雜度為：O(n) ，即為線性階。 例 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 語句頻度為：2n2 ，其時(shí)間復(fù)雜度為：O(n2) ，即為平方階。 .28 定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一個(gè)m次多 項(xiàng)式，則A(n)=O(n m) 例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x

21、; ai,j=x; 語句頻度為： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 時(shí)間復(fù)雜度為O(n2)，即此算法的時(shí)間復(fù)雜度為平方階。 一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行 的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即 零次多項(xiàng)式）來限界。而一個(gè)時(shí)間為O(n2)的算法則 由一個(gè)二次多項(xiàng)式來限界。 .29 以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為： O(1)O(n)O(n)O(nn)O(n2)O(n3) 指數(shù)時(shí)間的關(guān)系為： O(2n)O(n!)O(nn) 當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需 時(shí)間上非常懸殊。因此

22、，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任 何一個(gè)算法化簡為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。 有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還 隨問題的輸入數(shù)據(jù)集不同而不同。 .30 例1：素?cái)?shù)的判斷算法。 Void prime( int n) /* n是一個(gè)正整數(shù) */ int i=2 ; while ( (n% i)!=0 else printf(“ 嵌套的最深層語句是i+；其頻度由條件( (n% i)!=0 -i) for (j=0; jaj+1) if (ajaj+1) aj aj+1 ; change=TURE ; aj aj+1 ; change=TURE ; 最好情況：0次 最壞情

23、況：1+2+3+ +n-1=n(n-1)/2 平均時(shí)間復(fù)雜度為： O(n2) .32 空間復(fù)雜度(Space complexity) ：是指算法編寫成程序 后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記作： S(n)=O(f(n) 其中： n為問題的規(guī)模(或大小) 該存儲(chǔ)空間一般包括三個(gè)方面： 指令常數(shù)變量所占用的存儲(chǔ)空間; 輸入數(shù)據(jù)所占用的存儲(chǔ)空間; 輔助(存儲(chǔ))空間。 一般地，算法的空間復(fù)雜度指的是輔助空間。 一維數(shù)組an： 空間復(fù)雜度 O(n) 二維數(shù)組anm： 空間復(fù)雜度 O(n*m) .33 1 簡要回答術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型。 2 數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)？

24、邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的 區(qū)別和聯(lián)系是什么？ 3 數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括哪些？ 4 算法分析的目的是什么？算法分析的主要方面是什么？ 5 分析以下程序段的時(shí)間復(fù)雜度，請說明分析的理由或原因。 .34 Sum1( int n ) int p=1, sum=0, m ; for (m=1; m=n; m+) p*=m ; sum+=p ; return (sum) ; Sum2( int n ) int sum=0, m, t ; for (m=1; m=n; m+) p=1 ; for (t=1; t=m; t+) p*=t ; sum+=p ; return (sum) ; 遞歸函數(shù)遞歸函數(shù) fa

25、ct( int n ) if (n0時(shí)，將非空的線性表記作：時(shí)，將非空的線性表記作： (a1，a2，an) a1稱為線性表的稱為線性表的第一個(gè)第一個(gè)( (首首) )結(jié)點(diǎn)，結(jié)點(diǎn)，an稱為線性表的稱為線性表的最后最后 一個(gè)一個(gè)( (尾尾) )結(jié)點(diǎn)。結(jié)點(diǎn)。 2.1.1 線性表的定義線性表的定義 a1，a2，ai-1都是都是ai(2in)的的前驅(qū)前驅(qū)，其中，其中ai-1是是ai的的直接直接 前驅(qū)前驅(qū); ai+1，ai+2，an都是都是ai(1i n-1)的的后繼后繼，其中，其中ai+1是是ai的的 直接后繼直接后繼。 線性表中的數(shù)據(jù)元素線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)所代表的具體含義隨具

26、體應(yīng) 用的不同而不同，在線性表的定義中，只不過是一個(gè)抽用的不同而不同，在線性表的定義中，只不過是一個(gè)抽 象的表示符號(hào)。象的表示符號(hào)。 線性表中的線性表中的結(jié)點(diǎn)結(jié)點(diǎn)可以是可以是單值元素單值元素(每個(gè)元素只有一每個(gè)元素只有一 個(gè)數(shù)據(jù)項(xiàng)個(gè)數(shù)據(jù)項(xiàng)) 。 例例1: 26個(gè)英文字母組成的字母表：個(gè)英文字母組成的字母表： (A，B，C、Z） 例2 ： 某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化 情況：(6，17，28，50，92，188） 例3 ： 一副撲克的點(diǎn)數(shù) (2，3，4，J，Q，K，A) 線性表中的結(jié)點(diǎn)可以是記錄型元素，每個(gè)元素含 有多個(gè)數(shù)據(jù)項(xiàng) ，每個(gè)項(xiàng)稱為結(jié)點(diǎn)的一個(gè)域 。每個(gè)元 素有

27、一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組，稱為 關(guān)鍵字。 例4 ： 某校2001級(jí)同學(xué)的基本情況：(2001414101， 張里戶，男，06/24/1983)， (2001414102， 張化司，男，08/12/1984) ， (2001414102， 李利辣，女，08/12/1984) 若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到 大(或由大到小)排列的，稱線性表是有序的。 ADT List 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D = ai | aiElemSet, i=1,2,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R = | ai-1, aiD, i=2,3,n 基本操作：基本操作： InitList( 數(shù)據(jù)元素之間

28、的關(guān)系是以元素在計(jì)算機(jī)內(nèi)數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理物理 位置相鄰位置相鄰”來體現(xiàn)。來體現(xiàn)。 設(shè)有非空的線性表：設(shè)有非空的線性表：(a1，a2，an) 。順序存儲(chǔ)如圖。順序存儲(chǔ)如圖 2-1所示。所示。 2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu) 在具體的機(jī)器環(huán)境下：設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ) 單元，以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。 則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元 素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系： LOC(ai+1)=LOC(ai)+l 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為： LOC(ai)=

29、LOC(a1)+(i-1)*l a1 a2 ai an Loc(a1) Loc(ai)+(i-1)* l 圖圖2-1 線性表的順序存儲(chǔ)表示線性表的順序存儲(chǔ)表示 在高級(jí)語言(如C語言)環(huán)境下：數(shù)組具有隨機(jī)存取的特性， 因此，借助數(shù)組來描述順序表。除了用數(shù)組來存儲(chǔ)線性表的元素 之外，順序表還應(yīng)該有表示線性表的長度屬性，所以用結(jié)構(gòu)類型 來定義順序表類型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int Status ; typedef int ElemType ; typedef struct sqlist ElemTyp

30、e Elem_arrayMAX_SIZE ; int length ; SqList ; 順序存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作：初始化、 賦值、查找、修改、插入、刪除、求長度等。 以下將對(duì)幾種主要的操作進(jìn)行討論。 1 順序線性表初始化 Status Init_SqList( SqList *L ) L-elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L - elem_array ) return ERROR ; else L-length= 0 ; return OK ; 2 順序線性表的插入 在

31、線性表 L= (a1，a i-1，ai， ai+1，an) 中的第 i(1in)個(gè)位置上插入一個(gè)新結(jié)點(diǎn)e，使其成為線性表： L=(a1，a i-1，e，ai，ai+1，an) 實(shí)現(xiàn)步驟 (1) 將線性表L中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置。 (2) 將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。 (3) 線性表長度加1。 算法描述 Status Insert_SqList(Sqlist *L，int i ，ElemType e) int j ; if ( iL-length-1) return ERROR ; if (L-length=MAX_SIZE) printf(“線性表溢出!n”); return

32、ERROR ; for ( j=L-length1; j=i-1; -j ) L-Elem_arrayj+1=L-Elem_arrayj; / /* * i-1 i-1位置以后的所有結(jié)點(diǎn)后移位置以后的所有結(jié)點(diǎn)后移 * */ / L-Elem_arrayi-1=e; /* 在i-1位置插入結(jié)點(diǎn) */ L-length+ ; return OK ; 時(shí)間復(fù)雜度分析 在線性表L中的第i個(gè)元素之前插入新結(jié)點(diǎn)，其時(shí)間主要耗 費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來估計(jì)算法 的時(shí)間復(fù)雜度。 設(shè)在線性表L中的第i個(gè)元素之前插入結(jié)點(diǎn)的概率為Pi，不 失一般性，設(shè)各個(gè)位置插入是等概率，則Pi=1/(n+

33、1)，而插入時(shí) 移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i+1。 總的平均移動(dòng)次數(shù)： Einsert=pi*(n-i+1) (1in) Einsert=n/2 。 即在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表 長n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為 O(n)。 3 順序線性表的刪除 在線性表 L=(a1，a i-1，ai， ai+1，an) 中刪除結(jié)點(diǎn) ai(1in)，使其成為線性表： L= (a1，ai-1，ai+1，an) 實(shí)現(xiàn)步驟 (1) 將線性表L中的第i+1個(gè)至第n個(gè)結(jié)點(diǎn)依此向前移 動(dòng)一個(gè)位置。 (2) 線性表長度減1。 算法描述 ElemType Delete_SqList(

34、Sqlist *L，int i) int k ; ElemType x ; if (L-length=0) printf(“線性表L為空!n”); return ERROR; else if ( iL-length ) printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!n”) ; return ERROR ; return ERROR ; else x=L-Elem_arrayi-1 ; /*保存結(jié)點(diǎn)的 值*/ for ( k=i ; klength ; k+) for ( k=i ; klength ; k+) L-Elem_arrayk-1=L- L-Elem_arrayk-1=L- Elem_ar

35、rayk;Elem_arrayk; / /* * i i位置以后的所有結(jié)點(diǎn)前移位置以后的所有結(jié)點(diǎn)前移 * */ / L-length-; return (x);L-length-; return (x); 時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析 刪除線性表刪除線性表L中的中的第第i個(gè)個(gè)元素，其時(shí)間主要耗費(fèi)在表元素，其時(shí)間主要耗費(fèi)在表 中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來估計(jì)算中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來估計(jì)算 法的時(shí)間復(fù)雜度。法的時(shí)間復(fù)雜度。 設(shè)設(shè)在線性表在線性表L中中刪除第刪除第i個(gè)個(gè)元素的概率為元素的概率為Pi，不失，不失 一般性，設(shè)刪除各個(gè)位置是等概率，則一般性，設(shè)刪除各個(gè)位置

36、是等概率，則Pi=1/n，而刪除，而刪除 時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i。 則總的平均移動(dòng)次數(shù)：則總的平均移動(dòng)次數(shù)： Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 即即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié)在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié) 點(diǎn)。當(dāng)表長點(diǎn)。當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法?平均時(shí)間復(fù)雜度為平均時(shí)間復(fù)雜度為O(n)。 4 順序線性表的查找定位刪除 在線性表 L= (a1，a2，an) 中刪除值為x的第一個(gè)結(jié)點(diǎn)。 實(shí)現(xiàn)步驟 (1) 在線性表L查找值為x的第一個(gè)數(shù)據(jù)元素。 (2

37、) 將從找到的位置至最后一個(gè)結(jié)點(diǎn)依次向前移動(dòng)一 個(gè)位置。 (3) 線性表長度減1。 算法描述 Status Locate_Delete_SqList(Sqlist *L，ElemType x) /* 刪除線性表L中值為x的第一個(gè)結(jié)點(diǎn) */ int i=0 , k ; while (ilength) /*查找值為x的第一個(gè)結(jié)點(diǎn)*/ if (L-Elem_arrayi!=x ) i+ ; else else for ( k=i+1; klength; k+) for ( k=i+1; klength; k+) L-Elem_arrayk-1=L- L-Elem_arrayk-1=L- Elem_a

38、rrayk; Elem_arrayk; L-length-; break ; L-length-; break ; if (iL-length) printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!n”) ; return ERROR ; return ERROR ; return OK; 時(shí)間復(fù)雜度分析時(shí)間復(fù)雜度分析 時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的比較和移動(dòng)操作上。時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的比較和移動(dòng)操作上。 首先，首先，在線性表在線性表L中查找值為中查找值為x的的結(jié)點(diǎn)是否存在結(jié)點(diǎn)是否存在; 其次，若其次，若值為值為x的的結(jié)點(diǎn)存在，且在結(jié)點(diǎn)存在，且在線性表線性表L中的位置為中的位置為i ， 則在則在線性表線性表

39、L中刪除中刪除第第i個(gè)個(gè)元素。元素。 設(shè)設(shè)在線性表在線性表L刪除刪除數(shù)據(jù)元素概率為數(shù)據(jù)元素概率為Pi，不失一般性，不失一般性， 設(shè)各個(gè)位置是等概率，則設(shè)各個(gè)位置是等概率，則Pi=1/n。 比較的平均次數(shù)比較的平均次數(shù)： Ecompare=pi*i (1in) Ecompare=(n+1)/2 。 刪除時(shí)平均移動(dòng)次數(shù)刪除時(shí)平均移動(dòng)次數(shù)：Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 平均時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度：Ecompare+Edelete=n ， 即為即為O(n) 2.3.1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) ：用用一組任意的存儲(chǔ)單元存儲(chǔ)一組任意的

40、存儲(chǔ)單元存儲(chǔ)線性表線性表 中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡稱中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡稱線性鏈線性鏈 表表。 存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連 續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中 的任意位置上的。的任意位置上的。 鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。 為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)， 還必須存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的地址(或位置)，稱為指針 (pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)

41、點(diǎn)結(jié)構(gòu)，如圖 2-2所示。 鏈表是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯 次序鏈接在一起的。 每一個(gè)結(jié)只包含一個(gè)指針域的鏈表，稱為單鏈表。 為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn) (頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任 何信息(或鏈表長度等信息)。 data next 圖圖2-2 鏈表結(jié)點(diǎn)結(jié)構(gòu)鏈表結(jié)點(diǎn)結(jié)構(gòu) data ：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。next ：指針：指針 域，存放結(jié)點(diǎn)的直接后繼的地址。域，存放結(jié)點(diǎn)的直接后繼的地址。 3695 head fat 1100 bat 1300 cat 1305 eat 3700 hat NU

42、LL 1100 3700 1300 1305 bat cat eat fat hat head 圖圖2-3 帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式 單鏈表是由表頭唯一確定，因此單單鏈表是由表頭唯一確定，因此單 鏈表可以用頭指針的名字來命名。鏈表可以用頭指針的名字來命名。 例例1 1、線性表、線性表L=(bat，cat，eat，fat， hat) 其其帶頭結(jié)點(diǎn)的單帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理鏈表的邏輯狀態(tài)和物理 存儲(chǔ)方式如圖存儲(chǔ)方式如圖2-3所示。所示。 1 結(jié)點(diǎn)的描述與實(shí)現(xiàn)結(jié)點(diǎn)的描述與實(shí)現(xiàn) C語言中用語言中用帶指針的結(jié)構(gòu)體類型帶指針的結(jié)構(gòu)體類型來描

43、述來描述 typedef struct Lnode ElemType data; /*數(shù)據(jù)域，保存結(jié)點(diǎn)的值數(shù)據(jù)域，保存結(jié)點(diǎn)的值 */ struct Lnode *next; /*指針域指針域*/ LNode; /*結(jié)點(diǎn)的類型結(jié)點(diǎn)的類型 */ 2 結(jié)點(diǎn)的實(shí)現(xiàn)結(jié)點(diǎn)的實(shí)現(xiàn) 結(jié)點(diǎn)是通過動(dòng)態(tài)分配和釋放來的實(shí)現(xiàn)結(jié)點(diǎn)是通過動(dòng)態(tài)分配和釋放來的實(shí)現(xiàn)，即需要時(shí)分，即需要時(shí)分 配，不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用配，不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用C語言提供的標(biāo)語言提供的標(biāo) 準(zhǔn)函數(shù)：準(zhǔn)函數(shù)：malloc() ，realloc()，sizeof() ，free() 。 動(dòng)態(tài)分配 p=(LNode*)malloc(size

44、of(LNode); 函數(shù)malloc分配了一個(gè)類型為LNode的結(jié)點(diǎn)變量的空間，并將其 首地址放入指針變量p中。 動(dòng)態(tài)釋放 free(p) ; 系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。P必須是最近一次調(diào)用 malloc函數(shù)時(shí)的返回值。 3 最常用的基本操作及其示意圖 結(jié)點(diǎn)的賦值結(jié)點(diǎn)的賦值 LNode *p; p=(LNode*)malloc(sizeof(LNode); p-data=20; p-next=NULL ; p 20NULL 常見的指針操作常見的指針操作 q=p ; p a 操作前 p a q 操作后 q=p-next ; b p a 操作前操作后 q b p a p=p-next

45、; b p a 操作前操作后 p ba q-next=p ; c p b q a 操作前操作后 q ba c p (a) q-next=p-next ; (a) xy p b q a 操作前 操作后 q ba xy p 操作前 y p xb q a 操作后 y p xb q a (b) 操作前 y p xb q a 操作后 y p xb q a (b) 1 建立單鏈表 假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是整型，以32767作為結(jié)束 標(biāo)志。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：頭插入法，尾 插入法。 頭插入法建表 從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入 數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)

46、插入到當(dāng)前鏈表的 表頭上，直到讀入結(jié)束標(biāo)志為止。即每次插入的結(jié)點(diǎn)都作為鏈表 的第一個(gè)結(jié)點(diǎn)。 算法描述 LNode *create_LinkList(void) /* 頭插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值 */ int data ; LNode *head, *p; head= (LNode *) malloc( sizeof(LNode); head-next=NULL; /* 創(chuàng)建鏈表的表頭結(jié)點(diǎn)head */ while (1) scanf(“%d”, if (data=32767) break ;if (data=32767) break ; p= (LNode p= (LN

47、ode * *)malloc(sizeof(LNode);)malloc(sizeof(LNode); pdata=data; pdata=data; / /* * 數(shù)據(jù)域賦值數(shù)據(jù)域賦值 * */ / pnext=headnext ; headnext=p ; pnext=headnext ; headnext=p ; / /* * 鉤鏈鉤鏈，新創(chuàng)建，新創(chuàng)建的結(jié)點(diǎn)總是作為第一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)總是作為第一個(gè)結(jié)點(diǎn) * */ / return (head); (2) 尾插入法建表 頭插入法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點(diǎn) 的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法 建表。該方法是將

48、新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，使其成為當(dāng)前 鏈表的尾結(jié)點(diǎn)。 算法描述 LNode *create_LinkList(void) /* 尾插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值 */ int data ; LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode); p-next=NULL; /* 創(chuàng)建單鏈表的表頭結(jié)點(diǎn)head */ while (1) scanf(“%d”, if (data=32767) break ;if (data=32767) break ; q= (LNode q= (LNode * *)malloc(s

49、izeof(LNode); )malloc(sizeof(LNode); qdata=data; qdata=data; / /* * 數(shù)據(jù)域賦值數(shù)據(jù)域賦值 * */ / qnext=pnext; pnext=q; p=q ; qnext=pnext; pnext=q; p=q ; / /* *鉤鏈鉤鏈，新創(chuàng)建，新創(chuàng)建的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)* */ / return (head); 無論是哪種插入方法，如果要插入建立的單線性鏈表的結(jié) 點(diǎn)是n個(gè)，算法的時(shí)間復(fù)雜度均為O(n)。 對(duì)于單鏈表，無論是哪種操作，只要涉及到鉤鏈(或重新鉤 鏈)，如果沒有明確給出直接后繼，鉤鏈

50、(或重新鉤鏈)的次序必 須是“先右后左”。 2 單鏈表的查找 (1) 按序號(hào)查找 取單鏈表中的第i個(gè)元素。 對(duì)于單鏈表，不能象順序表中那樣直接按序號(hào)i訪問結(jié)點(diǎn)， 而只能從鏈表的頭結(jié)點(diǎn)出發(fā)，沿鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直 到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。 設(shè)單鏈表的長度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1in 時(shí)，i的值是合法的。 算法描述 ElemType Get_Elem(LNode *L ， int i) int j ; LNode *p; p=L-next; j=1; /* 使p指向第一個(gè)結(jié)點(diǎn) */ while (p!=NULL j+; /* 移動(dòng)指針p , j計(jì)

51、數(shù) */ if (j!=i) return(-32768) ; else return(p-data); /* p為NULL 表示i太大; ji表示i為0 */ 移動(dòng)指針p的頻度： in：n次。 時(shí)間復(fù)雜度: O(n)。 (2) 按值查找 按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的 結(jié)點(diǎn)? 若有，則返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否 則返回NULL。查找時(shí)從開始結(jié)點(diǎn)出發(fā)，沿鏈表逐個(gè)將結(jié)點(diǎn)的值 和給定值key作比較。 算法描述 LNode *Locate_Node(LNode *L，int key) /* 在以L為頭結(jié)點(diǎn)的單鏈表中查找值為key的第一個(gè)結(jié)點(diǎn) */ LNode

52、 *p=Lnext; while ( p!=NULL if (pdata=key) return p; else printf(“所要查找的結(jié)點(diǎn)不存在!n”); retutn(NULL); retutn(NULL); 算法的執(zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。 3 單鏈表的插入 插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置 上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結(jié)點(diǎn) p，然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q，q結(jié)點(diǎn)作為p的直接后繼 結(jié)點(diǎn)。 算法描述 void Insert_LNode(LNode *L，int i，ElemType e) /* 在以L為

53、頭結(jié)點(diǎn)的單鏈表的第i個(gè)位置插入值為e的結(jié)點(diǎn) */ int j=0; LNode *p，*q; p=Lnext ; while ( p!=NULL j+; if (j!=i-1) printf(“i太大或i為0!n ”); else q=(LNode *)malloc(sizeof(LNode); qdata=e; qnext=pnext;qdata=e; qnext=pnext; pnext=q;pnext=q; 設(shè)鏈表的長度為n，合法的插入位置是1in。算法的時(shí)間 主要耗費(fèi)移動(dòng)指針p上，故時(shí)間復(fù)雜度亦為O(n)。 4 單鏈表的刪除 按序號(hào)刪除 刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。 為了刪除第i個(gè)結(jié)點(diǎn)a

54、i，必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地 址是在其直接前趨結(jié)點(diǎn)ai-1的next域中，因此，必須首先找到ai-1 的存儲(chǔ)位置p，然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i 從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。 設(shè)單鏈表長度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1in時(shí)是合法 的。則當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在， 是終端結(jié)點(diǎn)。故判斷條件之一是pnext!=NULL。顯然此算法 的時(shí)間復(fù)雜度也是O(n)。 算法描述 void Delete_LinkList(LNode *L， int i) /* 刪除以L為頭結(jié)點(diǎn)的單鏈表中的第i個(gè)結(jié)點(diǎn) */ int j=1;

55、LNode *p，*q; p=L; q=L-next; while ( p-next!=NULL j+; if (j!=i) printf(“i太大或i為0!n ”); else pnext=qnext; free(q); 按值刪除 刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。 與按值查找相類似，首先要查找值為key的結(jié)點(diǎn)是否存在? 若存在，則刪除；否則返回NULL。 算法描述 void Delete_LinkList(LNode *L，int key) /* 刪除以L為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn) */ LNode *p=L, *q=Lnext; while ( q!=NULL q=qne

56、xt; if (qdata=key) p-next=q-next; free(q); else printf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在!n”); 算法的執(zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。 從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無需 移動(dòng)結(jié)點(diǎn)，僅需修改指針。解決了順序表的插入或刪除操作需要 移動(dòng)大量元素的問題。 變形之一： 刪除單鏈表中值為key的所有結(jié)點(diǎn)。 與按值查找相類似，但比前面的算法更簡單。 基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開始，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢 查，若結(jié)點(diǎn)的值為key，則刪除之，然后檢查下一個(gè)結(jié)點(diǎn)，直到所 有的結(jié)點(diǎn)都檢查。 算法描述 void Delete_Link

57、List_Node(LNode *L，int key) /* 刪除以L為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn) */ LNode *p=L, *q=Lnext; while ( q!=NULL) if (qdata=key) p-next=q-next; free(q); q=p- p-next=q-next; free(q); q=p- next; next; elseelse p=q; q=qnext; p=q; q=qnext; 變形之二： 刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn)，使得所有結(jié)點(diǎn)的值都不相 同。 與按值查找相類似，但比前面的算法更復(fù)雜。 基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開始，對(duì)每個(gè)結(jié)點(diǎn)

58、進(jìn)行檢 查：檢查鏈表中該結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，只要有值和該結(jié)點(diǎn)的值 相同，則刪除之；然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。 算法描述 void Delete_Node_value(LNode *L) /* 刪除以L為頭結(jié)點(diǎn)的單鏈表中所有值相同的結(jié)點(diǎn) */ LNode *p=L-next, *q, *ptr; while ( p!=NULL) /* 檢查鏈表中所有結(jié)點(diǎn) */ *q=p, *ptr=pnext; / /* * 檢查結(jié)點(diǎn)檢查結(jié)點(diǎn)p p的所有后繼結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)ptr ptr * */ / while (ptr!=NULL)while (ptr!=NULL) if (ptrdata

59、=p-data) if (ptrdata=p-data) q-next=ptr-next; free(ptr); q-next=ptr-next; free(ptr); ptr=q-next; ptr=q-next; else q=ptr; ptr=ptrnext; else q=ptr; ptr=ptrnext; p=p-next ;p=p-next ; 5 單鏈表的合并 設(shè)有兩個(gè)有序的單鏈表，它們的頭指針分別是La 、 Lb， 將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2- 4所示。 15 圖圖2-4 兩個(gè)有序的單鏈表兩個(gè)有序的單鏈表La ，Lb的初始狀態(tài)的初始狀態(tài) -2 4

60、 9 Lb pb -7 3 12 23 La Lc pa pc 合并了值為-7，-2的結(jié)點(diǎn)后示意圖如圖2-5所示。 圖圖2-5 合并了值為合并了值為-7 ，-2的結(jié)點(diǎn)后的狀態(tài)的結(jié)點(diǎn)后的狀態(tài) -2 4 9 15 Lb pc pb Lc -7 3 12 23 La pa 算法說明 算法中pa ，pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，pc是 合并過程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。 算法描述 LNode *Merge_LinkList(LNode *La， LNode *Lb) /* 合并以La, Lb為頭結(jié)點(diǎn)的兩個(gè)有序單鏈表 */ LNode *Lc, *pa , *pb , *pc, *ptr ;