數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版上)課件

1、數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版清華大學(xué)出版社 2009年9月第 1 章 概 論 什么是數(shù)據(jù)結(jié)構(gòu) 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 算法和算法分析1.1.1 數(shù)據(jù)和數(shù)據(jù)元素?cái)?shù)據(jù)（data）是信息的載體，是對(duì)客觀事物的符號(hào)表示，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。1.1 什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)在計(jì)算機(jī)科學(xué)中指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。如圖像、數(shù)、字符、聲音、視頻等都可以通過編碼而由計(jì)算機(jī)處理，因此它們也屬于數(shù)據(jù)的范疇。是數(shù)據(jù)的基本單位。通常在計(jì)算機(jī)程序中作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)或記錄。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也稱字段、域）組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。數(shù)

2、據(jù)元素（data element）：數(shù)據(jù)對(duì)象（data object）： 是性質(zhì)相同的數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個(gè)子集。例如，所有的“數(shù)”構(gòu)成了數(shù)據(jù)集合，而正整數(shù)集合N=1，2，3，是“數(shù)”的數(shù)據(jù)對(duì)象；所有的字符是數(shù)據(jù)，大寫字母集合C=A，B，Z是該數(shù)據(jù)的數(shù)據(jù)對(duì)象。1.1.2 數(shù)據(jù)對(duì)象和數(shù)據(jù)類型 要注意的是：計(jì)算機(jī)中的正整數(shù)數(shù)據(jù)對(duì)象集合N1應(yīng)該是上述集合N的一個(gè)子集，N1=1，2，maxint，其中maxint是依賴于所使用的計(jì)算機(jī)和語(yǔ)言的最大整數(shù)。 數(shù)據(jù)類型（data type）是計(jì)算機(jī)程序中的數(shù)據(jù)對(duì)象以及定義在這個(gè)數(shù)據(jù)對(duì)象集合上的一組操作的總稱。可以看作是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。例如，C語(yǔ)言中的

3、整數(shù)類型是區(qū)間-maxint，maxint上的整數(shù)，在這個(gè)集合上可以進(jìn)行加、減、乘、整除、求余等操作。數(shù)據(jù)結(jié)構(gòu)（data structure） 是指數(shù)據(jù)對(duì)象（集合）以及該數(shù)據(jù)對(duì)象集合中的數(shù)據(jù)元素之間的相互關(guān)系的集合（即數(shù)據(jù)元素的組織形式）。一組數(shù)據(jù)元素和一組運(yùn)算（關(guān)系）兩個(gè)集合組成的集合1.1.3 數(shù)據(jù)結(jié)構(gòu)根據(jù)數(shù)據(jù)元素之間關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為兩大類： 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 集合：數(shù)據(jù)元素之間除了“屬于同一個(gè)集合”的關(guān)系以外，別無(wú)其他關(guān)系。 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。 樹型結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。 圖狀結(jié)構(gòu)（或稱網(wǎng)狀結(jié)構(gòu)）：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。 數(shù)據(jù)元素之

4、間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。是數(shù)據(jù)元素之間抽象化的相互關(guān)系。是用戶所看到的數(shù)據(jù)結(jié)構(gòu)，是面向問題的，它不考慮數(shù)據(jù)的存儲(chǔ)。數(shù)據(jù)的邏輯結(jié)構(gòu)通常有下列4類： 數(shù)據(jù)元素之間的運(yùn)算（關(guān)系）：對(duì)數(shù)據(jù)元素施加的操作，有時(shí)也直接稱為數(shù)據(jù)的運(yùn)算或操作。數(shù)據(jù)的物理結(jié)構(gòu)： 又稱存儲(chǔ)結(jié)構(gòu)。是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（又稱映象）。它屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。例1.1 學(xué)生成績(jī)表（表1.1）是一個(gè)數(shù)據(jù)結(jié)構(gòu)。表1.1 學(xué)生成績(jī)表(每行是一個(gè)數(shù)據(jù)元素)學(xué)號(hào)姓名計(jì)算機(jī)導(dǎo)論高等數(shù)學(xué)普通物理平均成績(jī)04081101陳小潔8090858504081102馬麗麗7568787404081103林春英8278

5、667504081104王澄娟9085938904081150張吉祥70887578 數(shù)據(jù)結(jié)構(gòu)可以理解為：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，應(yīng)用計(jì)算機(jī)語(yǔ)言，按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。數(shù)據(jù)結(jié)構(gòu)主要研究什么？（或者說數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象是什么？）數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分： 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合， 就叫做數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 運(yùn)算集合上述4種基本的存儲(chǔ)方法，既可以單獨(dú)使用，也可以組合起來對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映象。同一種邏輯結(jié)構(gòu)，若采用不同的

6、存儲(chǔ)方法，則可以得到不同的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（4種基本的存儲(chǔ)） 順序存儲(chǔ)方法 鏈接存儲(chǔ)方法 索引存儲(chǔ)方法 散列存儲(chǔ)方法算法+數(shù)據(jù)結(jié)構(gòu)=程序1.2 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)?1.2.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課。它主要討論在軟件開發(fā)中如何進(jìn)行數(shù)據(jù)的組織、數(shù)據(jù)的表示和數(shù)據(jù)的處理。它不僅為操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等后續(xù)課提供必要的知識(shí)，而且也為學(xué)習(xí)者提供必要的技能訓(xùn)練。例1.2 電話號(hào)碼的查詢問題。要求編寫一個(gè)電話號(hào)碼的查詢程序。對(duì)于任意給出的一個(gè)姓名，如果該人留有電話號(hào)碼，那么就找出他的電話號(hào)碼；否則就指出該人沒有電話號(hào)碼。1.2.2 數(shù)據(jù)結(jié)構(gòu)的應(yīng)

7、用舉例例1.3 n個(gè)城市之間鋪設(shè)光纜的問題。 假設(shè)需要在n個(gè)城市之間鋪設(shè)光纜，并且任意兩個(gè)城市之間都可以鋪設(shè)。大家知道，在n個(gè)城市之間只要鋪設(shè)n-1條光纜，即能將這n個(gè)城市連成網(wǎng)絡(luò)，只是由于地理位置的不同，所需經(jīng)費(fèi)也不同，問題是采用什么樣的設(shè)計(jì)方案能使總投資最省。 這個(gè)問題的數(shù)學(xué)模型如下頁(yè)所示的“圖”，圖中“頂點(diǎn)”表示城市，頂點(diǎn)之間的連線及其上面的數(shù)值表示可以鋪設(shè)的光纜及所需經(jīng)費(fèi)。 1.3 算法和算法分析1.3.1 什么是算法?由于數(shù)據(jù)的運(yùn)算是通過算法來描述的，因此，討論算法是數(shù)據(jù)結(jié)構(gòu)課程的重要內(nèi)容之一。算法（Algorithm）是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指

8、令表示一個(gè)或多個(gè)操作；此外，一個(gè)算法還具有下列5個(gè)特性： 1、有窮性 在有窮步內(nèi)結(jié)束 2、確定性 算法中的每一步不會(huì)產(chǎn)生二義性 3、可行性 每一步均可經(jīng)有限次運(yùn)算實(shí)現(xiàn) 4、輸入 有零個(gè)或多個(gè)輸入 5、輸出 有零個(gè)或多個(gè)輸出程序與算法的異同 在一個(gè)算法中，有些指令可能重復(fù)執(zhí)行，因而指令的執(zhí)行次數(shù)可能遠(yuǎn)遠(yuǎn)大于算法中的指令條數(shù)。由有窮性和可行性得知，對(duì)于任何輸入，一個(gè)算法在執(zhí)行了有限條指令后一定要終止，而且必須在有限時(shí)間內(nèi)完成。因此，一個(gè)程序如果對(duì)任何輸入都不會(huì)產(chǎn)生無(wú)限循環(huán)，則它就是一個(gè)算法。 盡管算法的含義與程序非常相似，但兩者還是有區(qū)別的。首先，一個(gè)程序不一定滿足有窮性，因此它不一定是算法。例如

9、，系統(tǒng)程序中的操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭受破壞，它就永遠(yuǎn)不會(huì)停止，即使沒有作業(yè)要處理，它仍處于等待循環(huán)中，以待一個(gè)新作業(yè)的進(jìn)入。因此操作系統(tǒng)就不是一個(gè)算法。其次，程序中的指令必須是計(jì)算機(jī)可以執(zhí)行的，而算法中的指令卻無(wú)此限止。如果一個(gè)算法采用機(jī)器可執(zhí)行的語(yǔ)言來書寫，那么它就是一個(gè)程序。1.3.2 算法的描述和設(shè)計(jì) 一個(gè)算法可以采用自然語(yǔ)言、數(shù)學(xué)語(yǔ)言或者約定的符號(hào)語(yǔ)言（如偽碼、框圖等）來描述。我們使用C語(yǔ)言來描述。 書中采用的一些預(yù)定義常量，簡(jiǎn)要說明如下：/*函數(shù)結(jié)果的狀態(tài)代碼*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 其他

10、有關(guān)C語(yǔ)言的知識(shí)，請(qǐng)參考專門介紹C語(yǔ)言的書籍。如何評(píng)價(jià)算法的優(yōu)劣？一般來說，設(shè)計(jì)一個(gè)“好”的算法應(yīng)該考慮以下幾點(diǎn)：1、正確性算法應(yīng)當(dāng)滿足具體問題的需求。2、健壯性當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈鞣磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫明其妙的輸出結(jié)果或出錯(cuò)信息，并中止程序的執(zhí)行。3、可讀性算法主要是為了方便人們的閱讀和交流，其次才是機(jī)器執(zhí)行。4、執(zhí)行算法所耗費(fèi)的時(shí)間。5、執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間。1.3.3 算法分析 評(píng)價(jià)一個(gè)程序優(yōu)劣的重要依據(jù)是看這個(gè)程序的執(zhí)行需要占用多少機(jī)器資源。在各種機(jī)器資源中，最重要的是時(shí)間資源和空間資源。因此，在進(jìn)行程序分析時(shí)，大家最關(guān)心兩點(diǎn)：程序所用

11、算法運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià) 時(shí)間復(fù)雜度程序中使用的數(shù)據(jù)結(jié)構(gòu)所占有的空間代價(jià) 空間復(fù)雜度通常，一個(gè)算法是由控制結(jié)構(gòu)（順序、選擇和循環(huán)）和基本語(yǔ)句構(gòu)成的，而算法時(shí)間取決于兩者的綜合效果。以基本語(yǔ)句重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。大部分情況下它是最深層循環(huán)語(yǔ)句內(nèi)的基本語(yǔ)句的執(zhí)行次數(shù)（頻度）。所謂語(yǔ)句的頻度，指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)。1、算法的時(shí)間復(fù)雜度分析 一般，我們把算法運(yùn)行的時(shí)間定義成函數(shù)T(n)，一個(gè)算法所耗費(fèi)的時(shí)間將隨輸入數(shù)據(jù)量n的增大而增大，n是該算法輸入數(shù)據(jù)的規(guī)模，這個(gè)數(shù)據(jù)規(guī)模不是某一個(gè)具體的輸入。T(n)的單位是不確定的，一般把它看成是在一個(gè)特定的計(jì)算機(jī)上執(zhí)行的指令條數(shù)。 當(dāng)討論

12、一個(gè)程序的運(yùn)行時(shí)間 T(n)時(shí)，注重的不是T(n)的具體值，而是它的增長(zhǎng)率。即求出T(n)隨輸入數(shù)據(jù)量n而增長(zhǎng)的趨勢(shì)(極限) 。 稱函數(shù)f(n)是T(n)增長(zhǎng)率的上界，是指存在一個(gè)常數(shù)M和一個(gè)整數(shù)n0，當(dāng)問題的規(guī)模nn0時(shí)，T(n)Mf(n)，記為T（n）=O(f(n),并稱該算法的時(shí)間復(fù)雜度為O(f(n)。 這時(shí)就稱該算法的時(shí)間代價(jià)為T(n)。 人們通常采用大O表示法來描述算法分析的結(jié)果。 f(n)是某個(gè)值非負(fù)的函數(shù)，這種說法意味著：當(dāng)n充分大時(shí)，該算法的復(fù)雜度不大于f(n)的一個(gè)常數(shù)倍。 評(píng)價(jià)算法的時(shí)間復(fù)雜性，就是設(shè)法找出 T(n)和n的關(guān)系，即求出T(n) 一個(gè)算法所耗費(fèi)的時(shí)間是算法中所

13、有語(yǔ)句執(zhí)行時(shí)間之和，而每條語(yǔ)句的執(zhí)行時(shí)間是該語(yǔ)句的執(zhí)行次數(shù)（頻度）與該語(yǔ)句執(zhí)行一次所需時(shí)間（略，因機(jī)器不同而不同）的乘積。求時(shí)間復(fù)雜度方法： 一般，求時(shí)間復(fù)雜度時(shí)，只考慮與程序規(guī)模有關(guān)的頻度最大的語(yǔ)句，如循環(huán)語(yǔ)句的循環(huán)體，多重循環(huán)的內(nèi)循環(huán)等。例1.4 有下列三個(gè)程序段： x=x+1; s=0; 頻度為1 for(i=1; i=n; i+) x=x+1; s=s+x; 頻度為n for(j=1; j=n; j+) for(k=1; k=n; k+) x=x+1; s=s+x; 頻度為n2 它們含基本操作“x加1”的語(yǔ)句的頻度分別為1、n和n2，因此，對(duì)于程序段來說，其時(shí)間復(fù)雜度為O(1)，程序段

14、的時(shí)間復(fù)雜度為O(n)，程序段的時(shí)間復(fù)雜度為O(n2)。例1.5 對(duì)n個(gè)記錄進(jìn)行升序排序的問題，采用最簡(jiǎn)單的選擇排序方法。 每次處理時(shí)，先從n個(gè)未排序的記錄中選出一個(gè)最小記錄，則第一次要經(jīng)過n-1次比較，才能選出最小記錄；第二次再?gòu)氖Ｏ碌膎-1個(gè)記錄中經(jīng)過n-2次比較，選出次小記錄；如此反復(fù)，直到只剩兩個(gè)記錄時(shí)，經(jīng)過1次比較就可以確定它們的大小。整個(gè)排序過程的基本操作（即“原操作”）是“比較兩個(gè)記錄的大小”，含“比較”的語(yǔ)句的頻度是： （n-1）+（n-2）+ +1= n （n-1）/2 因此，其時(shí)間復(fù)雜度為O（n2）。 在同一個(gè)算法處理兩個(gè)規(guī)模相同的問題，所花費(fèi)的時(shí)間和空間代價(jià)也不一定相同。

15、要全面分析一個(gè)算法，應(yīng)該考慮它在最壞情況下的代價(jià)（即對(duì)同樣規(guī)模的問題所花費(fèi)的最大代價(jià)）、最好情況下的代價(jià)和平均情況下的代價(jià)等。然而，要全面準(zhǔn)確地分析每個(gè)算法是相當(dāng)困難的，因此，我們?cè)诜治鏊惴〞r(shí)將主要考慮它們?cè)谧顗那闆r下的代價(jià)，個(gè)別地方也涉及到其他情況。 通常有如下的函數(shù)關(guān)系排序： c log2 n n n log2 n n2 n3 10 n 其中，c是與n無(wú)關(guān)的任意常數(shù)。上述函數(shù)排序與數(shù)學(xué)中對(duì)無(wú)窮大的分級(jí)完全一致，因?yàn)榭紤]的也是n值變化過程中的趨勢(shì)，參見圖1.4。 例1.6 要交換變量x和y中的內(nèi)容，其程序段為 temp=x; x=y; y=temp; 由于以上三條語(yǔ)句的頻度均為1，說明該程序

16、段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無(wú)關(guān)的常數(shù)，因此，算法的時(shí)間復(fù)雜度為O（1）。 例1.7 有程序段如下：x=1;for(i=1; i=n; i+) for(j=1; j=n; j+) for(k=1; k length=0; 刪除一個(gè)線性表 要?jiǎng)h除一個(gè)已經(jīng)存在的線性表，只需要把該線性表設(shè)置為空表，也就是把表長(zhǎng)置為0。算法2.2 刪除一個(gè)線性表void DestroyList(sequenlist *L) L-length=0; 本算法時(shí)間復(fù)雜度為O（1）。 順序表的基本操作定位(按值查找)： 要查找一個(gè)值，只需要從頭到尾的遍歷線性表，如果找到，則返回找到的位置，否則繼續(xù)，如果一直到最后一個(gè)位置都

17、沒有找到，則返回-1。 本算法中， n是線性表的長(zhǎng)度；可能找到值為Item的元素，也可能找不到Item，這時(shí)候，算法的比較次數(shù)為O(n)。因此，總結(jié)起來，本算法的時(shí)間復(fù)雜度為O(n)。順序表的基本操作 int Loc(sequenlist L，datatype item) int i,j; j=L.length; /*表的長(zhǎng)度*/ if( j= = 0) return FALSE; for(i=1;i=j;i+) if(L.elemi=item) return i; printf(“找不到該值！”); return 0; 算法2.3 定位（按值Item查找） 插入數(shù)據(jù) 要在線性表中第i個(gè)位置插

18、入一個(gè)數(shù)據(jù)元素，需要考慮以下因素： i是否在位置1和L.length之間，如果在，則把item插入到第i個(gè)位置，原來的第i個(gè)位置及以后的數(shù)據(jù)元素向后移動(dòng)一個(gè)位置，然后線性表長(zhǎng)度加上1，返回TRUE；如果不在位置1和L.length之間，則說明插入位置不合適，返回FALSE。如下圖所示： 順序表的基本操作插入前 插入后 a1a2baiai+1算法2.4 在表L的第i個(gè)位置插入數(shù)據(jù)itemint Ins(sequenlist *L，int i，datatype item)int j;if(iL-length) return FALSE； for(j=L-ength;ji-1;j-)/*因?yàn)閿?shù)組的下

19、標(biāo)從0開始*/ L-elemj=L-elemj-1; /*后移*/ L-elemi-1=item; /*插入*/ L-length+; /*元素個(gè)數(shù)增1*/ return TRUE; 本算法的時(shí)間主要花在移動(dòng)數(shù)據(jù)上，n是線性表的長(zhǎng)度。因此，本算法的時(shí)間復(fù)雜度為O(n)。刪除數(shù)據(jù) 刪除數(shù)據(jù)和插入數(shù)據(jù)很相似，都要求判斷i的值是否合適，如果位置合適，則把后面的數(shù)據(jù)向前移動(dòng)，刪除成功，表的長(zhǎng)度減1，返回TRUE，否則，返回FALSE。如下圖所示： 順序表的基本操作刪除前 刪除后 算法2.5 刪除線性表中第i個(gè)結(jié)點(diǎn)數(shù)據(jù)int Del(sequenlist *L，int i) int j; if(iL-l

20、ength-1) return FALSE； for(j=i;jlength-1;j+) L-elemj=L-elemj+1; L-length-; return TRUE；2.3 線性表的鏈?zhǔn)酱鎯?chǔ) 為了提高增加、刪除元素的效率，介紹線性表的另一種存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)。在鏈?zhǔn)酱鎯?chǔ)方式中，能夠方便地增加和刪除線性表中的元素，但是同時(shí)也使隨機(jī)存取、獲取直接前趨和直接后繼變得較為復(fù)雜。一個(gè)數(shù)據(jù)元素映射到內(nèi)存后叫結(jié)點(diǎn) 鏈表：以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表稱之為鏈表（Linked List） 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表的結(jié)點(diǎn)。也就是說，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)單元可以是相鄰的，也可以是不相鄰的；同時(shí)

21、，相鄰的存儲(chǔ)單元中的數(shù)據(jù)，不一定是相鄰的結(jié)點(diǎn)。 存儲(chǔ)地址數(shù)據(jù)域指針域1李407張15頭指針H15趙NULL20王140錢1414孫1313吳7例2.7 線性表（“王”，“李”，“錢”，“孫”，“吳”，“張”，“趙”）的單鏈表示意圖存放數(shù)據(jù)元素的結(jié)點(diǎn)至少包含兩個(gè)域數(shù)據(jù)域和指針域數(shù)據(jù)域 存放元素的數(shù)據(jù)指針域 存放其后繼元素的存儲(chǔ)地址指針域中存放的信息稱為指針或鏈，n個(gè)結(jié)點(diǎn)連接成一個(gè)鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 只有一個(gè)指針域的鏈表，稱為單鏈表。 用單鏈表表示線性表時(shí)，結(jié)點(diǎn)之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的，如下圖。 typedef struct LNode ElemType data；/數(shù)據(jù)域

22、 Struct LNode *next; /指針域 LinkList; LinkList *L, *head; 單鏈表的C語(yǔ)言描述：這里的L（或head）可以作為單鏈表的頭指針，它指向該鏈表的第一個(gè)結(jié)點(diǎn)。如果L=NULL，則表示該單鏈表為一個(gè)空表，其長(zhǎng)度為0。 為了更方便的判斷空表、插入和刪除結(jié)點(diǎn)，我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)前面加上一個(gè)附設(shè)的節(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)一些附加信息；而頭結(jié)點(diǎn)的指針域存儲(chǔ)鏈表第一個(gè)結(jié)點(diǎn)的地址。 如果頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?，即L-next=NULL，則表示該鏈表為空表。整個(gè)鏈表的存取必須從頭指針開始進(jìn)行！單鏈表的基本操作 清除帶頭單

23、鏈表的內(nèi)容 分析：要清除鏈表的內(nèi)容，就必須從頭結(jié)點(diǎn)開始，依次的釋放每一個(gè)節(jié)點(diǎn)所占有的存儲(chǔ)空間，然后把表長(zhǎng)設(shè)置為0，頭結(jié)點(diǎn)的next域設(shè)置為NULL。 int ClearList(LinkList *L)/*使線性表L變成空表*/ LinkList *temp; while(L-next != NULL) temp=L-next; /*使工作指針指向第1個(gè)結(jié)點(diǎn)*/ L-next=L-next-next; free(temp); return TRUE;算法2.6 清除帶表頭單鏈表內(nèi)容 本算法首先把頭結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)，然后釋放第一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間，依此類推。 要清除表的內(nèi)容，就必須對(duì)鏈表進(jìn)行一次

24、遍歷，因此，時(shí)間復(fù)雜度為O(n)，其中，n表示鏈表的長(zhǎng)度。 分析：由于在結(jié)點(diǎn)中沒有保存鏈表的長(zhǎng)度，因此，要獲得表長(zhǎng)，必須對(duì)鏈表進(jìn)行完整的遍歷。求表長(zhǎng)算法2.7 求帶表頭單鏈表長(zhǎng)度(結(jié)點(diǎn)數(shù)) int ListLength(LinkList *L) int len=0; LinkList *temp; temp=L; while(temp-next != NULL) len+;temp=temp-next; return len; 本算法時(shí)間復(fù)雜度為O(n)，其中n是鏈表的長(zhǎng)度。 單鏈表的基本操作 定位(按值查找)： 分析：與求鏈表長(zhǎng)度類似，要在鏈表中查找給定值的結(jié)點(diǎn)，也需要對(duì)鏈表進(jìn)行遍歷。算法2

25、.8 在帶表頭單鏈表中按值查找定位int Loc(LinkList *L，ElemType Item)int i=0; /*記值為Item 的結(jié)點(diǎn)在表中的位置*/ LinkList *temp;temp=L-next; /*使temp指向第一個(gè)結(jié)點(diǎn)*/while(temp!= NULL & temp-date != Item) i+; temp=temp-next; if(temp=NULL) return 0; else return i; 本算法的時(shí)間復(fù)雜度為O(n)。單鏈表的基本操作 插入數(shù)據(jù)（在第i個(gè)結(jié)點(diǎn)的后面插入）： 解決：插入時(shí)的新結(jié)點(diǎn)從何處取?鏈表與向量不同，向量建立時(shí)已定義好它

26、的存儲(chǔ)空間，而鏈表的結(jié)點(diǎn)數(shù)事先不確定。但我們?cè)O(shè)想：內(nèi)存中有一個(gè)可用空間表，要調(diào)用新結(jié)點(diǎn)時(shí)就到這個(gè)可用空間表中去取，刪除時(shí)就把這個(gè)結(jié)點(diǎn)歸還給這個(gè)可用空間。分析：在鏈表中插入數(shù)據(jù)比較方便，不需要進(jìn)行大量的數(shù)據(jù)移動(dòng)。只需要找到插入點(diǎn)即可，我們給出的是一個(gè)后插入的算法，也就是在插入點(diǎn)的后面添加結(jié)點(diǎn)，如圖所示。算法2.9 在帶表頭單鏈表第i個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn) int Ins(LinkList *L，int i，ElemType Item)int j=1; LinkList *node,*temp;node=(LinkList*)malloc(sizeof(LinkList);if(node=NULL)

27、return FALSE;node-data=Item; temp=L -next; /*使temp指向第一個(gè)結(jié)點(diǎn) */if(temp =NuLL) /*作為第一個(gè)結(jié)點(diǎn)插入*/ if( i=0) L-next=node;node-next=NULL;return TRUE;else/*插入位置不合理*/ return FALSE;while(jnext; j+; /*向后查找第i個(gè)結(jié)點(diǎn)*/if(temp=NULL) /*已找到表尾了*/return FALSE; node-next=temp-next; temp-next=node; return TRUE; 單鏈表的基本操作 刪除數(shù)據(jù)：刪除

28、第i個(gè)結(jié)點(diǎn) 分析：在帶表頭結(jié)點(diǎn)的單鏈表中，刪除數(shù)據(jù)和插入數(shù)據(jù)很相似。也是一個(gè)尋找刪除點(diǎn)，找到后進(jìn)行指針賦值的一種操作。算法2.10 刪除第i個(gè)結(jié)點(diǎn)int Del(LinkList *L，int i) LinkList *temp,*q; int j=0; temp=L; /*工作指針指向頭結(jié)點(diǎn)*/if(temp-next=NULL) /*空表*/ return FALSE;while(jnext!=NULL) j+; temp=temp-next;/*找第i-1個(gè)結(jié)點(diǎn)*/if(temp-next=NULL) /*第i個(gè)結(jié)點(diǎn)不存在*/ return FALSE;q=temp-next; /*q指

29、向第i個(gè)結(jié)點(diǎn)*/temp-next=q-next;free(q); /*釋放q結(jié)點(diǎn)*/return TRUE;本算法的時(shí)間復(fù)雜度也是O(n)。 是一種首尾相接的鏈表。在單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨∟ULL），如果使線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針域存放鏈表的表頭結(jié)點(diǎn)的地址，則能構(gòu)成一個(gè)單鏈形式的循環(huán)鏈表，簡(jiǎn)稱為單循環(huán)鏈表；如果鏈表中每個(gè)結(jié)點(diǎn)都具有兩個(gè)指針域，就稱為是雙向鏈表。循環(huán)鏈表（Circular Linked List）特點(diǎn)：在循環(huán)線性鏈表中，從表的任何一個(gè)結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的單循環(huán)鏈表單循環(huán)鏈表的操作 循環(huán)鏈表的建立 分析：循環(huán)鏈表是對(duì)單向鏈表的一種改善。單

30、向鏈表中末尾結(jié)點(diǎn)的next=NULL，只需要把這個(gè)結(jié)點(diǎn)的next域的值設(shè)置為頭結(jié)點(diǎn)的地址，就能夠獲得一個(gè)循環(huán)鏈表。 創(chuàng)建一個(gè)空循環(huán)鏈表的算法： 算法2.11 創(chuàng)建單循環(huán)鏈表int InitCList(LinkList *L)L=( LinkList *) malloc (sizeof (LinkList); if(L=NULL) /*申請(qǐng)結(jié)點(diǎn)不成功*/ return FALSE;L-next=L; return TRUE; 本算法時(shí)間復(fù)雜度為O(1)，和創(chuàng)建單向空鏈表相同，唯一的區(qū)別是： 帶頭結(jié)點(diǎn)單空鏈表中 L-next=NULL 帶頭結(jié)點(diǎn)空循環(huán)鏈表中 L-next=L （也就是指向了自身）

31、單循環(huán)鏈表的操作 空循環(huán)鏈表的判斷： 分析：在單向鏈表中，判斷一個(gè)鏈表是否為空，只需要看頭結(jié)點(diǎn)的next域是否為NULL；相似的，在循環(huán)鏈表中，要判斷一個(gè)鏈表是否為空，只需要看頭結(jié)點(diǎn)的next域是否等于自身。算法如下： 算法2.12 判斷單循環(huán)鏈表是否為空int isempty(LinkList *L) if(L-next=L) return TRUE; else return FALSE; 本算法時(shí)間復(fù)雜度為O(1)。 單循環(huán)鏈表的操作算法2.13 插入結(jié)點(diǎn)(在i位置)int InsertCList(LinkList *L，int i，ElemType e) int j; /*在單循環(huán)鏈表L

32、中的第i個(gè)位置插入值為e結(jié)點(diǎn)*/LinkList *temp,*node;temp=L;j=1;while(jnext!=L) j+; temp=temp-next; /*找第i-1位置后*/ /*使temp指向第i-1個(gè)結(jié)點(diǎn)，這時(shí)j=i*/if(jnext = =L) /*無(wú)合適的插入位置*/ return FALSE;node=( LinkList *)malloc(sizeof(LinkList);if(node=NULL) /*申請(qǐng)結(jié)點(diǎn)不成功*/ return FALSE;node-next=temp-next; temp-next=node;return TRUE; 本算法時(shí)間復(fù)雜度

33、為O(n)，其中n是鏈表的長(zhǎng)度。帶頭結(jié)點(diǎn)單循環(huán)鏈表的操作刪除結(jié)點(diǎn)(刪除第i個(gè)結(jié)點(diǎn)) :int DelCList(LinkList *L,int i) int j; LinkList *t1, *t2, j=1; /*定義兩個(gè)工作指針t1，t2*/ t1=L-next; /*工作時(shí)t1在前，t2在后*/ t2=L; if (t1=t2|i1) return FALSE; /*空表或i不合理*/ while(jnext; t2=t2-next; if(t1 = L ) return FALSE; /*查遍沒找到被刪除結(jié)點(diǎn)*/ t2-next=t1-next; free(t1); /*刪除t1所指結(jié)

34、點(diǎn)*/ return TRUE; 帶頭結(jié)點(diǎn)的雙向鏈表 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域：一個(gè)指向其直接前趨，另一個(gè)指向其直接后繼。如圖所示。 在C語(yǔ)言中，雙向鏈表的存儲(chǔ)結(jié)構(gòu)可定義如下：typedef struct DNode struct DNode *prior; /*指向前趨*/ ElemType data; /*結(jié)點(diǎn)數(shù)據(jù)域*/ Struct DNode *next; /*指向后繼*/ DLinkList; DLinkList *DL, *p; 若指針p指向雙向鏈表中的某一結(jié)點(diǎn)，則有如下關(guān)系： p-next-prior=p p-prior-next=p雙向鏈表的操作 雙向鏈表的建立 由于雙向

35、鏈表具有指向前趨和指向后繼的兩個(gè)指針，因此，在創(chuàng)建空雙向鏈表的時(shí)候，需要對(duì)兩個(gè)指針賦值為NULL。 算法2.15 建立一個(gè)空雙向鏈表int InitDList(DLinkList *DL)DL=(DLinkList *)malloc(sizeof(DNode);if(DL= =NULL) return FALSE;/*申請(qǐng)失敗*/DL-prior=DL-next=NULL;return TRUE; 本算法時(shí)間復(fù)雜度為O(1) 雙向鏈表的操作雙向鏈表為空表的判斷 雙向鏈表是否為空表，要看兩個(gè)指針域是否同時(shí)為NULL。 算法2.16 判斷雙向鏈表是否為空表int DlEmpty(DLinkList

36、 *DL)if(DL-prior=DL-next&DL-prior=NULL) return TRUE;else return FALSE;在雙向鏈表內(nèi)插入結(jié)點(diǎn) 分析：在雙向鏈表中插入新的結(jié)點(diǎn)，必須修改插入位置的前趨和后繼。雙向鏈表的操作算法2.17 在雙向鏈表中插入數(shù)據(jù)int DLInsert(DLinkList *DL,int i,ElemType e) int j=1; /*在帶頭雙向鏈表DL的第i個(gè)位置插入新結(jié)點(diǎn)e*/ DLinkList *temp，*node;temp=DL; while(jnext != NULL) j+; temp=temp-next; /* temp指向第i-

37、1個(gè)結(jié)點(diǎn)，j=i*/ if(jdata=e; /*輸入新結(jié)點(diǎn)的數(shù)據(jù)*/ node-prior=temp; /*修改鏈指針，通常要修改四個(gè)指針域，插入的結(jié)點(diǎn)地表尾修改三個(gè)指針域*/ node-next=temp-next; if(temp-next!=NULL ) temp-next -prior = node; temp-next=node; return TRUE; 在雙向鏈表內(nèi)刪除結(jié)點(diǎn) 分析：和插入結(jié)點(diǎn)相似，雙向鏈表中刪除結(jié)點(diǎn)，也是要注意指針的修改。雙向鏈表的操作算法2.18 在帶頭結(jié)點(diǎn)的雙向鏈表中刪除數(shù)據(jù)int DLDelete(DLinkList *DL,int i) int j=1;

38、 /*刪除雙向鏈表中第i個(gè)結(jié)點(diǎn)*/ DLinkList *temp; /*工作指針*/ temp=DL-next; while(jnext; if (jprior-next=temp-next; if (temp-next != NULL) /*被刪結(jié)點(diǎn)不是尾*/ temp-next-prior=temp-prior; free(temp); return TRUE; 本算法時(shí)間復(fù)雜度為O(n) 雙向循環(huán)鏈表 將雙向鏈表中的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，就構(gòu)成了雙向循環(huán)鏈表。如圖所示。雙向循環(huán)鏈表的操作算法2.19 在雙向循環(huán)鏈表中刪除結(jié)點(diǎn)eint DLClist(DLinkList *DL, El

39、emType e) DLinkList *temp; /*工作指針,指向被刪結(jié)點(diǎn)*/ temp=DL-next; if(temp-next= =temp)/*空表*/ return FALSE;while(temp-data != e & temp != DL) temp=temp-next; /*找結(jié)點(diǎn)e*/if(temp != DL) /* 找到需要?jiǎng)h除的結(jié)點(diǎn),而且要?jiǎng)h的節(jié)點(diǎn)不是表頭 */temp-prior-next=temp-next; /* 刪除結(jié)點(diǎn) */ temp-next-prior=temp-prior; free(temp); /* 釋放空間 */ return TRUE;e

40、lse return FALSE;靜態(tài)鏈表 在C語(yǔ)言中用標(biāo)準(zhǔn)函數(shù)malloc和free來動(dòng)態(tài)執(zhí)行內(nèi)存分配,并用指針實(shí)現(xiàn)鏈表，因此稱為動(dòng)態(tài)鏈表。而有的程序設(shè)計(jì)語(yǔ)言不支持指針類型，所以不能使用動(dòng)態(tài)鏈表，為此引入靜態(tài)鏈表的概念。 用數(shù)組描述的鏈表稱為靜態(tài)鏈表（Static Linked List） 線性表靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu)定義如下：#define MAXSIZE 1024typedef int ElemType;typedef struct SList ElemType data; int next; /*表示指針域,用來指向其下一個(gè)結(jié)點(diǎn)*/ /*下一個(gè)結(jié)點(diǎn)的下標(biāo)*/node;node SlinkL

41、istMAXSIZE;int av;例2.9 線性表（A,B,C,D,E）經(jīng)過修改，在B后面插入X和刪除D之后，成為線性表（A,B,X,C,E）。如圖所示。1A2B3C4D5E01A2B6C5D5E0X301234560123456data next data next修改前的狀態(tài) 修改后的狀態(tài)線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較 從時(shí)間的角度考慮，按位置查找數(shù)據(jù)時(shí)，查找元素的前趨和后繼等方面，順序存儲(chǔ)有著較大的優(yōu)勢(shì)。 線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較 在插入數(shù)據(jù)、刪除數(shù)據(jù)時(shí)，鏈?zhǔn)酱鎯?chǔ)就有較大的優(yōu)勢(shì)，這是由于在鏈表中只要修改指針即可做到；而在順序表中進(jìn)行插入和刪除，平均要移動(dòng)表中將近一半的結(jié)點(diǎn)。 線性

42、表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較 從空間的角度考慮，順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須規(guī)定其存儲(chǔ)規(guī)模。 而動(dòng)態(tài)鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，只要內(nèi)存空間有空閑，就不會(huì)產(chǎn)生溢出。線性表的應(yīng)用 約瑟夫問題 例2.10 設(shè)有n個(gè)人坐在圓桌周圍，從第s個(gè)人開始報(bào)數(shù)，數(shù)到m的人出列，然后再?gòu)南乱粋€(gè)人開始報(bào)數(shù)，同樣數(shù)到m的人出列，如此重復(fù)，直到所有人都出列為止。要求輸出出列的順序。 分析：本問題用一個(gè)鏈表來解決。設(shè)圓桌周圍的n個(gè)人組成一個(gè)帶表頭的循環(huán)鏈表。先找到第s個(gè)人對(duì)應(yīng)的結(jié)點(diǎn)，由此結(jié)點(diǎn)開始，順序掃描m個(gè)結(jié)點(diǎn)，將掃描到的第m個(gè)結(jié)點(diǎn)刪除。重復(fù)上述過程，直到鏈表為空。#include “stdio.h”Typedef char datatype;typede struct nodedatatype info;struct node *next;NODE; 定義表結(jié)點(diǎn)Info nextvoid