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

1、C語言算法與數(shù)據(jù)結(jié)構(gòu)第一章 概論根底知識(shí)時(shí)間復(fù)雜度空間復(fù)雜度 數(shù)據(jù)(Data) ：是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。 數(shù)據(jù)元素(Data Element) ：是數(shù)據(jù)的根本單位，在程序中通常作為一個(gè)整體來進(jìn)展考慮和處理。 一個(gè)數(shù)據(jù)元素可由假設(shè)干個(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, 。 根本概念和術(shù)語 數(shù)據(jù)構(gòu)造(Data Structure)：是指相互之間

2、具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱為邏輯構(gòu)造。數(shù)據(jù)元素之間的邏輯構(gòu)造有四種根本類型，如圖1-3所示。 集合：構(gòu)造中的數(shù)據(jù)元素除了“同屬于一個(gè)集合外，沒有其它關(guān)系。 線性構(gòu)造：構(gòu)造中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。 樹型構(gòu)造：構(gòu)造中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。 圖狀構(gòu)造或網(wǎng)狀構(gòu)造：構(gòu)造中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。 數(shù)據(jù)構(gòu)造的形式定義是一個(gè)二元組： Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例2：設(shè)數(shù)據(jù)邏輯構(gòu)造B=K，R K=k1, k2, , k9 R= ， 畫出這邏輯構(gòu)造的圖示，并確定那些是起點(diǎn)，

3、那些是終點(diǎn) 數(shù)據(jù)構(gòu)造的形式定義圖1-3 四類根本構(gòu)造圖 數(shù)據(jù)構(gòu)造的存儲(chǔ)方式 數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問題方便而人為定義的關(guān)系，這種自然或人為定義的 “關(guān)系稱為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的構(gòu)造稱為邏輯構(gòu)造。 數(shù)據(jù)構(gòu)造在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的表示。 元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)構(gòu)造：順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。 順序存儲(chǔ)構(gòu)造：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯構(gòu)造(關(guān)系)。 鏈?zhǔn)酱鎯?chǔ)構(gòu)造：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針

4、(pointer )，用該指針來表示數(shù)據(jù)元素之間的邏輯構(gòu)造(關(guān)系)。例：設(shè)有數(shù)據(jù)集合A=3.0,2.3,5.0,-8.5,11.0 ，兩種不同的存儲(chǔ)構(gòu)造。 順序構(gòu)造：數(shù)據(jù)元素存放的地址是連續(xù)的； 鏈?zhǔn)綐?gòu)造：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。 數(shù)據(jù)的邏輯構(gòu)造和物理構(gòu)造是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯構(gòu)造，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)構(gòu)造。 在C語言中，用一維數(shù)組表示順序存儲(chǔ)構(gòu)造；用構(gòu)造體類型表示鏈?zhǔn)酱鎯?chǔ)構(gòu)造。數(shù)據(jù)構(gòu)造的三個(gè)組成局部：邏輯構(gòu)造： 數(shù)據(jù)元素之間邏輯關(guān)系的描述 D_S=D，S存儲(chǔ)構(gòu)造： 數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲(chǔ)構(gòu)造或物理構(gòu)造。數(shù)

5、據(jù)操作： 對(duì)數(shù)據(jù)要進(jìn)展的運(yùn)算。 本課程中將要討論的三種邏輯構(gòu)造及其采用的存儲(chǔ)構(gòu)造如圖1-4所示。數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列圖1-5 數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖圖1-4 邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性表樹圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu) 數(shù)據(jù)類型(Data Type)：指的是一個(gè)值的集合和定義在該值集上的一組操作的總稱。 數(shù)據(jù)類型是和數(shù)據(jù)構(gòu)造密切相關(guān)的一個(gè)概念。 在C語言中數(shù)據(jù)類型有：根本類型和構(gòu)造類型。 數(shù)據(jù)構(gòu)造不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象，

6、而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。 數(shù)據(jù)類型 數(shù)據(jù)構(gòu)造的主要運(yùn)算包括： 建立(Create)一個(gè)數(shù)據(jù)構(gòu)造； 消除(Destroy)一個(gè)數(shù)據(jù)構(gòu)造； 從一個(gè)數(shù)據(jù)構(gòu)造中刪除(Delete)一個(gè)數(shù)據(jù)元素； 把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)構(gòu)造中； 對(duì)一個(gè)數(shù)據(jù)構(gòu)造進(jìn)展訪問(Access)； 對(duì)一個(gè)數(shù)據(jù)構(gòu)造(中的數(shù)據(jù)元素)進(jìn)展修改(Modify)； 對(duì)一個(gè)數(shù)據(jù)構(gòu)造進(jìn)展排序(Sort)； 對(duì)一個(gè)數(shù)據(jù)構(gòu)造進(jìn)展查找(Search)。 數(shù)據(jù)構(gòu)造的運(yùn)算 抽象數(shù)據(jù)類型(Abstract Data Type ，簡(jiǎn)稱ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。 ADT的定義僅是一組邏輯特性描

7、述， 與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無關(guān)。因此，不管ADT的內(nèi)部構(gòu)造如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。 ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的根本操作集。 抽象數(shù)據(jù)類型ADT的一般定義形式是：ADT 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 根本操作： ADT 其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述。 根本操作的定義是：()初始條件： 操作結(jié)果： 初始條件：描述操作執(zhí)行之前數(shù)據(jù)構(gòu)造和參數(shù)應(yīng)滿足的條件;假設(shè)不滿足，那么操作失敗，返回相應(yīng)的出錯(cuò)信息。 操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)構(gòu)造的變化狀況和 應(yīng)返回的結(jié)果。 算法算法(Algorit

8、hm)：是對(duì)特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性 有窮性： 一個(gè)算法必須總是在執(zhí)行有窮步之后完畢，且每一步都在有窮時(shí)間內(nèi)完成。 確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。 可行性： 一個(gè)算法是能行的。即算法描述的操作都可以通過已經(jīng)實(shí)現(xiàn)的根本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。 算法分析初步 輸入： 一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。 輸出： 一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。 一個(gè)算法可以用多種方法描述，主要有：使用自然語言描述；使用形式

9、語言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語言描述。 算法和程序是兩個(gè)不同的概念。一個(gè)計(jì)算機(jī)程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。算法必須可終止意味著不是所有的計(jì)算機(jī)程序都是算法。 評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn) 正確性(Correctness )： 算法應(yīng)滿足具體問題的需求。 可讀性(Readability)： 算法應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改。 強(qiáng)健性(Robustness)： 算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇错懟蜻M(jìn)展處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。 通用性(Generality)： 算法應(yīng)具有一般性 ，即算法的處理結(jié)果對(duì)于一

10、般的數(shù)據(jù)集合都成立。 算法設(shè)計(jì)的要求 算法執(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ù)。1.3.3 算法效率的度量 效率與存儲(chǔ)量需求： 效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。一般地，這兩者與問題的規(guī)模有關(guān)。與此相關(guān)的因素有： 依據(jù)算法選用何種策略； 問題的規(guī)模； 程序設(shè)計(jì)的語言； 編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量； 機(jī)器執(zhí)行指令的速度；

11、撇開軟硬件等有關(guān)部門因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量的大小，只依賴于問題的規(guī)模通常用n表示，或者說，它是問題規(guī)模的函數(shù)。算法分析應(yīng)用舉例 算法中根本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作 T(n)=O(f(n)，稱作算法的漸近時(shí)間復(fù)雜度(Asymptotic Time complexity)，簡(jiǎn)稱時(shí)間復(fù)雜度。 一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示。 “O的定義： 假設(shè)f(n)是正整數(shù)n的一個(gè)函數(shù)，那么 O(f(n)表示 M0 ，使得當(dāng)n n0時(shí)，| f(n) | M | f(n0) | 。表示時(shí)間復(fù)雜度的階有： O(1) ：常量時(shí)間

12、階 O (n)：線性時(shí)間階 O(n) ：對(duì)數(shù)時(shí)間階 O(nn) ：線性對(duì)數(shù)時(shí)間階 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ù)雜度為(1) 。如果將s=0也看成是根本操作，那么語句頻度為，其時(shí)間復(fù)雜度仍為(1)，即常量階。例 for(i=1; i=n; +i)

13、+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) ，即為平方階。 定理：假設(shè)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; 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)，即此算

14、法的時(shí)間復(fù)雜度為平方階。 一個(gè)算法時(shí)間為O(1)的算法，它的根本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)即零次多項(xiàng)式來限界。而一個(gè)時(shí)間為O(n2)的算法那么由一個(gè)二次多項(xiàng)式來限界。 以下六種計(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í)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。 有的情況下，算法中根本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例1：素?cái)?shù)的

15、判斷算法。Void prime( int n)/* n是一個(gè)正整數(shù) */ int i=2 ; while ( (n% i)!=0 & i*1.0sqrt(n) )printf(“&d 是一個(gè)素?cái)?shù)n , n) ;elseprintf(“&d 不是一個(gè)素?cái)?shù)n , n) ; 嵌套的最深層語句是i+；其頻度由條件( (n% i)!=0 & i*1.0 sqrt(n) ) 決定，顯然i*1.01 & change; -i)for (j=0; jaj+1) aj aj+1 ; change=TURE ; 最好情況：0次 最壞情況：1+2+3+n-1=n(n-1)/2 平均時(shí)間復(fù)雜度為： O(n2) 算法的

16、空間分析 空間復(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)第2章 線性表 線性構(gòu)造是最常用、最簡(jiǎn)單的一種數(shù)據(jù)構(gòu)造。而線性表是一種典型的線性構(gòu)造。其根本特點(diǎn)是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種構(gòu)造中： 存在一個(gè)唯一的被稱為“第一個(gè)的數(shù)

17、據(jù)元素； 存在一個(gè)唯一的被稱為“最后一個(gè)的數(shù)據(jù)元素； 除第一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接前驅(qū)； 除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼。 線性表的邏輯構(gòu)造 線性表(Linear List) ：是由n(n0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2， an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有一樣的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱為空表。 當(dāng)n0時(shí)，將非空的線性表記作： (a1，a2，an) a1稱為線性表的第一個(gè)(首)結(jié)點(diǎn)，an稱為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。 線性表的定義a1，a2，ai-1都是ai(2in)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai

18、+2，an都是ai(1i n-1)的后繼，其中ai+1是ai的直接后繼。 線性表的邏輯構(gòu)造 線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同，在線性表的定義中，只不過是一個(gè)抽象的表示符號(hào)。 線性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng)) 。例1: 26個(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è)元素有一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的

19、數(shù)據(jù)項(xiàng)組，稱為關(guān)鍵字。例4 ： 某校2001級(jí)同學(xué)的根本情況：(2001414101，張里戶，男，06/24/1983)， (2001414102，張化司，男，08/12/1984) ， (2001414102，李利辣，女，08/12/1984) 假設(shè)線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。 線性表的抽象數(shù)據(jù)類型定義ADT List數(shù)據(jù)對(duì)象：D = ai | aiElemSet, i=1,2,n, n0 數(shù)據(jù)關(guān)系：R = | ai-1, aiD, i=2,3,n 根本操作：InitList( &L )操作結(jié)果：構(gòu)造一個(gè)空的線性表L； 線性表是一種相當(dāng)

20、靈活的數(shù)據(jù)構(gòu)造，其長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。 對(duì)線性表的數(shù)據(jù)元素可以訪問、插入和刪除。ListLength( L )初始條件：線性表L已存在；操作結(jié)果：假設(shè)L為空表，那么返回TRUE，否那么返回FALSE；.GetElem( L, i, &e )初始條件：線性表L已存在，1iListLength(L)；操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值；ListInsert ( L, i, &e )初始條件：線性表L已存在，1iListLength(L) ；操作結(jié)果：在線性表L中的第i個(gè)位置插入元素e； ADT List 線性表的順序存儲(chǔ) 順序存儲(chǔ) ：把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)

21、單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。順序存儲(chǔ)的線性表的特點(diǎn)： 線性表的邏輯順序與物理順序一致; 數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰來表達(dá)。 設(shè)有非空的線性表：(a1，a2，an) 。順序存儲(chǔ)如圖2-1所示。 線性表的順序存儲(chǔ)構(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)=LOC(a1)+(i-

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

23、h ; SqList ; 順序表的根本操作 順序存儲(chǔ)構(gòu)造中，很容易實(shí)現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長(zhǎng)度等。以下將對(duì)幾種主要的操作進(jìn)展討論。1 順序線性表初始化 Status Init_SqList( SqList *L ) L-length= 0 ; return OK ; 2 順序線性表的插入 在線性表 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

24、之后。 (3) 線性表長(zhǎng)度加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 ERROR ; for ( j=L-length1; j=i-1; -j )L-Elem_arrayj+1=L-Elem_arrayj;/* i-1位置以后的所有結(jié)點(diǎn)后移 */L-Elem_arrayi-1=e; /* 在i-1位置插入結(jié)點(diǎn) */L-length+ ;return OK

25、 ; 時(shí)間復(fù)雜度分析 在線性表L中的第i個(gè)元素之前插入新結(jié)點(diǎn)，其時(shí)間主要消耗在表中結(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+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)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)汀Ｒ虼怂惴ǖ钠骄鶗r(shí)間復(fù)雜度為O(n)。3 順序線性表的刪除 在線性表 L=(a1，a i-1，ai， ai+1，an) 中刪除

26、結(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) 線性表長(zhǎng)度減1。算法描述ElemType Delete_SqList(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 ; else x=L-Elem_arrayi-1 ; /*保存結(jié)點(diǎn)的值*/f

27、or ( k=i ; klength ; k+) L-Elem_arrayk-1=L-Elem_arrayk; /* i位置以后的所有結(jié)點(diǎn)前移 */L-length-; return (x); 時(shí)間復(fù)雜度分析 刪除線性表L中的第i個(gè)元素，其時(shí)間主要消耗在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來估計(jì)算法的時(shí)間復(fù)雜度。 設(shè)在線性表L中刪除第i個(gè)元素的概率為Pi，不失一般性，設(shè)刪除各個(gè)位置是等概率，那么Pi=1/n，而刪除時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i。那么總的平均移動(dòng)次數(shù)： Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié)

28、點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。4 順序線性表的查找定位刪除 在線性表 L= (a1，a2，an) 中刪除值為x的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)步驟(1) 在線性表L查找值為x的第一個(gè)數(shù)據(jù)元素。(2) 將從找到的位置至最后一個(gè)結(jié)點(diǎn)依次向前移動(dòng)一個(gè)位置。 (3) 線性表長(zhǎng)度減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

29、+ ; else for ( k=i+1; klength; k+) L-Elem_arrayk-1=L-Elem_arrayk; L-length-; break ; if (iL-length) printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!n) ; return ERROR ; return OK; 時(shí)間復(fù)雜度分析 時(shí)間主要消耗在數(shù)據(jù)元素的比較和移動(dòng)操作上。首先，在線性表L中查找值為x的結(jié)點(diǎn)是否存在;其次，假設(shè)值為x的結(jié)點(diǎn)存在，且在線性表L中的位置為i ，那么在線性表L中刪除第i個(gè)元素。 設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設(shè)各個(gè)位置是等概率，那么Pi=1/n。 比較的平均次數(shù)：

30、Ecompare=pi*i (1in) Ecompare=(n+1)/2 。 刪除時(shí)平均移動(dòng)次數(shù)：Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 平均時(shí)間復(fù)雜度：Ecompare+Edelete=n ，即為O(n) 線性表的鏈?zhǔn)酱鎯?chǔ) 線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造 鏈?zhǔn)酱鎯?chǔ) ：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱線性鏈表。 存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。 鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定一樣。 為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指

31、示其直接后繼結(jié)點(diǎn)的地址(或位置)，稱為指針(pointer)或鏈(link)，這兩局部組成了鏈表中的結(jié)點(diǎn)構(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ǔ)任何信息(或鏈表長(zhǎng)度等信息)。data next圖2-2 鏈表結(jié)點(diǎn)結(jié)構(gòu)data ：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。next ：指針域，存放結(jié)點(diǎn)的直接后繼的地址。 3695headfat1100bat1300cat1305eat3700hatNULL110

32、0370013001305bat cat eat fat hat head 圖2-3 帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式 單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如圖2-3所示。1 結(jié)點(diǎn)的描述與實(shí)現(xiàn) C語言中用帶指針的構(gòu)造體類型來描述typedef struct Lnode ElemType data; /*數(shù)據(jù)域，保存結(jié)點(diǎn)的值 */struct Lnode *next; /*指針域*/LNode; /*結(jié)點(diǎn)的類型 */2 結(jié)點(diǎn)的實(shí)現(xiàn) 結(jié)點(diǎn)是通過動(dòng)態(tài)分配和釋放來的實(shí)現(xiàn)，

33、即需要時(shí)分配，不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用C語言提供的標(biāo)準(zhǔn)函數(shù)：malloc() ，realloc()，sizeof() ，free() 。動(dòng)態(tài)分配 p=(LNode*)malloc(sizeof(LNode);函數(shù)malloc分配了一個(gè)類型為L(zhǎng)Node的結(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)的賦值 LNode *p;p=(LNode*)malloc(sizeof(LNode); p-data=20; p-next=NULL ;p20NU

34、LL 常見的指針操作 q=p ;pa操作前paq操作后 q=p-next ;bpa操作前操作后qbpa p=p-next ;bpa操作前操作后pba q-next=p ;cpbqa操作前操作后qbacp(a) q-next=p-next ;(a)xypbqa操作前操作后qbaxyp操作前ypxbqa操作后ypxbqa(b)操作前ypxbqa操作后ypxbqa(b) 單線性鏈?zhǔn)降母静僮? 建立單鏈表 假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是整型，以32767作為完畢標(biāo)志。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：頭插入法，尾插入法。 頭插入法建表 從一個(gè)空表開場(chǎng)，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)

35、點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入完畢標(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, &data) ;if (data=32767) break ;p= (LNode *)malloc(sizeof(

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

37、LNode *)malloc(sizeof(LNode); p-next=NULL; /* 創(chuàng)立單鏈表的表頭結(jié)點(diǎn)head */while (1) scanf(“%d,& data);if (data=32767) break ;q= (LNode *)malloc(sizeof(LNode); qdata=data; /* 數(shù)據(jù)域賦值 */qnext=pnext; pnext=q; p=q ; /*鉤鏈，新創(chuàng)立的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)*/return (head); 無論是哪種插入方法，如果要插入建立的單線性鏈表的結(jié)點(diǎn)是n個(gè)，算法的時(shí)間復(fù)雜度均為O(n)。 對(duì)于單鏈表，無論是哪種操作，只要涉

38、及到鉤鏈(或重新鉤鏈)，如果沒有明確給出直接后繼，鉤鏈(或重新鉤鏈)的次序必須是“先右后左。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ī)存取構(gòu)造。 設(shè)單鏈表的長(zhǎng)度為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 &

39、jnext; j+; /* 移動(dòng)指針p , j計(jì)數(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)? 假設(shè)有，那么返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否那么返回NULL。查找時(shí)從開場(chǎng)結(jié)點(diǎn)出發(fā)，沿鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。算法描述LNode *Locate_Node(LNode *L，int key)/* 在以L為頭結(jié)點(diǎn)的單鏈表中查找值為key

40、的第一個(gè)結(jié)點(diǎn) */ LNode *p=Lnext;while ( p!=NULL& pdata!=key) p=pnext;if (pdata=key) return p;else printf(“所要查找的結(jié)點(diǎn)不存在!n); 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，ElemTy

41、pe e) /* 在以L為頭結(jié)點(diǎn)的單鏈表的第i個(gè)位置插入值為e的結(jié)點(diǎn) */ int j=0; LNode *p，*q;p=Lnext ;while ( p!=NULL& jnext; j+; if (j!=i-1) printf(“i太大或i為0!n ); else q=(LNode *)malloc(sizeof(LNode);qdata=e; qnext=pnext;pnext=q; 設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1in。算法的時(shí)間主要消耗移動(dòng)指針p上，故時(shí)間復(fù)雜度亦為O(n)。4 單鏈表的刪除 按序號(hào)刪除 刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。 為了刪除第i個(gè)結(jié)點(diǎn)ai，必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該

42、存儲(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è)單鏈表長(zhǎng)度為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; LNode *p，*q;p=L; q=L-

43、next;while ( p-next!=NULL& jnext; j+; if (j!=i) printf(“i太大或i為0!n ); else pnext=qnext; free(q); 按值刪除 刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。 與按值查找相類似，首先要查找值為key的結(jié)點(diǎn)是否存在? 假設(shè)存在，那么刪除；否那么返回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& qdata!=key) p=q; q=qn

44、ext; 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)。 與按值查找相類似，但比前面的算法更簡(jiǎn)單。根本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開場(chǎng)，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)展檢查，假設(shè)結(jié)點(diǎn)的值為key，那么刪除之，然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。 算法描述void Delete_LinkList_

45、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-next; else p=q; q=qnext; 變形之二： 刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn)，使得所有結(jié)點(diǎn)的值都不一樣。 與按值查找相類似，但比前面的算法更復(fù)雜。根本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開場(chǎng)，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)展檢查：檢查鏈表中該結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，只要有值和該結(jié)點(diǎn)的值一樣，那么刪除之；然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。 算

46、法描述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)p的所有后繼結(jié)點(diǎn)ptr */while (ptr!=NULL) if (ptrdata=p-data) q-next=ptr-next; free(ptr); ptr=q-next; else q=ptr; ptr=ptrnext; p=p-next ; 5 單鏈表的合并 設(shè)有兩個(gè)有序的單鏈表，它們的頭指

47、針分別是La 、 Lb，將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2-4所示。15 圖2-4 兩個(gè)有序的單鏈表La ，Lb的初始狀態(tài)-2 4 9 Lb pb-7 3 12 23 La Lcpapc合并了值為-7，-2的結(jié)點(diǎn)后示意圖如圖2-5所示。圖2-5 合并了值為-7 ，-2的結(jié)點(diǎn)后的狀態(tài)-2 4 9 15 Lb pcpbLc-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

48、為頭結(jié)點(diǎn)的兩個(gè)有序單鏈表 */ LNode *Lc, *pa , *pb , *pc, *ptr ;Lc=La ; pc=La ; pa=La-next ; pb=Lb-next ; while (pa!=NULL& pb!=NULL) if (pa-datadata) pc-next=pa ; pc=pa ; pa=pa-next ; /* 將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn) */if (pa-datapb-data) pc-next=pb ; pc=pb ; pb=pb-next ; /* 將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn) */if (pa-data=pb-data) pc-

49、next=pa ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; free(ptr) ; /* 將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除 */ if (pa!=NULL) pc-next=pa ;else pc-next=pb ; /*將剩余的結(jié)點(diǎn)鏈上*/free(Lb) ;return(Lc) ;算法分析 假設(shè)La ，Lb兩個(gè)鏈表的長(zhǎng)度分別是m，n，那么鏈表合并的時(shí)間復(fù)雜度為O(m+n) 。 循環(huán)鏈表 循環(huán)鏈表(Circular Linked List)：是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)。

50、從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。 圖2-6是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖?？毡韴D2-6 單循環(huán)鏈表示意圖非空表a1 a2 anhead head 循環(huán)鏈表的操作 對(duì)于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線性鏈表根本上一致，僅僅需要在單線性鏈表操作算法根底上作以下簡(jiǎn)單修改： 判斷是否是空鏈表：head-next=head ; 判斷是否是表尾結(jié)點(diǎn)：p-next=head ; 雙向鏈表 雙向鏈表(Double Linked List) :指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior，一個(gè)指向其直接后繼的指針域ne

51、xt。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。 和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。 將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。 雙向鏈表是為了抑制單鏈表的單向性的缺陷而引入的。1 雙向鏈表的結(jié)點(diǎn)及其類型定義 雙向鏈表的結(jié)點(diǎn)的類型定義如下。其結(jié)點(diǎn)形式如圖2-7所示，帶頭結(jié)點(diǎn)的雙向鏈表的形式如圖2-8所示。typedef struct Dulnode ElemType data ;struct Dulnode *prior , *next ;DulNode ;datanextprior圖2-7 雙向鏈表結(jié)點(diǎn)形式非空雙向鏈表hea

52、da2a1an空雙向鏈表head圖2-8 帶頭結(jié)點(diǎn)的雙向鏈表形式 雙向鏈表構(gòu)造具有對(duì)稱性，設(shè)p指向雙向鏈表中的某一結(jié)點(diǎn)，那么其對(duì)稱性可用下式描述：(p-prior)-next=p=(p-next)-prior ; 結(jié)點(diǎn)p的存儲(chǔ)位置存放在其直接前趨結(jié)點(diǎn)p-prior的直接后繼指針域中，同時(shí)也存放在其直接后繼結(jié)點(diǎn)p-next的直接前趨指針域中。2 雙向鏈表的根本操作(1) 雙向鏈表的插入 將值為e的結(jié)點(diǎn)插入雙向鏈表中。插入前后鏈表的變化如圖2-9所示。Sepaiai+1Sepaiai+1圖2-9 雙向鏈表的插入 插入時(shí)僅僅指出直接前驅(qū)結(jié)點(diǎn)，鉤鏈時(shí)必須注意先后次序是： “先右后左 。局部語句組如下：

53、S=(DulNode *)malloc(sizeof(DulNode); S-data=e;S-next=p-next; p-next-prior=S;p-next=S; S-prior=p; /* 鉤鏈次序非常重要 */ 插入時(shí)同時(shí)指出直接前驅(qū)結(jié)點(diǎn)p和直接后繼結(jié)點(diǎn)q，鉤鏈時(shí)無須注意先后次序。局部語句組如下：S=(DulNode *)malloc(sizeof(DulNode);S-data=e;p-next=S; S-next=q;S-prior=p; q-prior=S; (2) 雙向鏈表的結(jié)點(diǎn)刪除 設(shè)要?jiǎng)h除的結(jié)點(diǎn)為p ，刪除時(shí)可以不引入新的輔助指針變量，可以直接先斷鏈，再釋放結(jié)點(diǎn)。局部語

54、句組如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);注意： 與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針域的指向。 一元多項(xiàng)式的表示和相加1 一元多項(xiàng)式的表示 一元多項(xiàng)式 p(x)=p0+p1x+p2x2+ +pnxn ，由n+1個(gè)系數(shù)唯一確定。那么在計(jì)算機(jī)中可用線性表(p0 ，p1 ，p2 ， ，pn )表示。既然是線性表，就可以用順序表和鏈表來實(shí)現(xiàn)。兩種不同實(shí)現(xiàn)方式的元素類型定義如下：(1) 順序存儲(chǔ)表示的類型typedef struct float coef; /*系數(shù)局部*/int expn

55、; /*指數(shù)局部*/ ElemType ;(2) 鏈?zhǔn)酱鎯?chǔ)表示的類型typedef struct ploy float coef ; /*系數(shù)局部*/int expn ; /*指數(shù)局部*/struct ploy *next ; Ploy ;2 一元多項(xiàng)式的相加 不失一般性，設(shè)有兩個(gè)一元多項(xiàng)式：P(x)=p0+p1x+p2x2+ +pnxn ，Q(x)=q0+q1x+q2x2+ +qmxm (mnext ; pb=Lb-next ;while (pa!=NULL&pb!=NULL) if (pa-expnexpn) pc-next=pa ; pc=pa ; pa=pa-next ; /* 將pa

56、所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn) */if (pa-expnpb-expn) pc-next=pb ; pc=pb ; pb=pb-next ; /* 將pb所指的結(jié)點(diǎn)合并，pb指向下一個(gè)結(jié)點(diǎn) */else x=pa-coef+pb-coef ; if (abs(x)next ; free(ptr) ; ptr=pb ; pb=pb-next ; free(ptr) ; else /* 如果系數(shù)和不為0，修改其中一個(gè)結(jié)點(diǎn)的系數(shù)域，刪除另一個(gè)結(jié)點(diǎn) */ pc-next=pa ; pa-coef=x ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; fre

57、e(pb) ; /* end of while */ if (pa=NULL) pc-next=pb ;else pc-next=pa ;return (Lc) ; 算法之二： 對(duì)兩個(gè)多項(xiàng)式鏈表進(jìn)展相加，生成一個(gè)新的相加后的結(jié)果多項(xiàng)式鏈表，原來兩個(gè)多項(xiàng)式鏈表依然存在，不發(fā)生任何改變，如果要再對(duì)原來兩個(gè)多項(xiàng)式進(jìn)展其它操作也不影響。算法描述Ploy *add_ploy(ploy *La， ploy *Lb) /* 將以La ，Lb為頭指針表示的一元多項(xiàng)式相加，生成一個(gè)新的結(jié)果多項(xiàng)式 */ ploy *Lc , *pc , *pa , *pb , *p ; float x ;Lc=pc=(ploy

58、*)malloc(sizeof(ploy) ; pa=La-next ; pb=Lb-next ;while (pa!=NULL&pb!=NULL) if (pa-expnexpn) p=(ploy *)malloc(sizeof(ploy) ; p-coef=pa-coef ; p-expn=pa-expn ; p-next=NULL ; /* 生成一個(gè)新的結(jié)果結(jié)點(diǎn)并賦值 */ pc-next=p ; pc=p ; pa=pa-next ; /* 生成的結(jié)點(diǎn)插入到結(jié)果鏈表的最后，pa指向下一個(gè)結(jié)點(diǎn) */if (pa-expnpb-expn) p=(ploy *)malloc(sizeof(p

59、loy) ; p-coef=pb-coef ; p-expn=pb-expn ; p-next=NULL ; /* 生成一個(gè)新的結(jié)果結(jié)點(diǎn)并賦值 */ pc-next=p ; pc=p ; pb=pb-next ; /* 生成的結(jié)點(diǎn)插入到結(jié)果鏈表的最后，pb指向下一個(gè)結(jié)點(diǎn) */if (pa-expn=pb-expn) x=pa-coef+pb-coef ; if (abs(x)next ; pb=pb-next ; else /* 假設(shè)系數(shù)和不為0，生成的結(jié)點(diǎn)插入到結(jié)果鏈表的最后， pa, pb分別直接后繼結(jié)點(diǎn) */ p=(ploy *)malloc(sizeof(ploy) ; p-coef=

60、x ; p-expn=pb-expn ; p-next=NULL ; /* 生成一個(gè)新的結(jié)果結(jié)點(diǎn)并賦值 */ pc-next=p ; pc=p ; pa=pa-next ; pb=pb-next ; /* end of while */ if (pb!=NULL) while(pb!=NULL) p=(ploy *)malloc(sizeof(ploy) ; p-coef=pb-coef ; p-expn=pb-expn ; p-next=NULL ; /* 生成一個(gè)新的結(jié)果結(jié)點(diǎn)并賦值 */ pc-next=p ; pc=p ; pb=pb-next ; if (pa!=NULL) while