用c語言描述完整版課件全套ppt整本書電子講義全書電子課件最全教學(xué)教程

1、第1章 緒論1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語 1.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型1.4 算法描述與算法評價(jià) 本章將介紹數(shù)據(jù)結(jié)構(gòu)研究的對象、基本概念和術(shù)語、算法的概念及其描述方法（C語言描述）、數(shù)據(jù)類型以及抽象數(shù)據(jù)類型，并概述數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況及其在計(jì)算機(jī)科學(xué)中的地位。第1章 緒 論 隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，計(jì)算機(jī)處理的對象更多的是非數(shù)值計(jì)算問題，它們的數(shù)學(xué)模型無法用數(shù)學(xué)方程來進(jìn)行描述，此時(shí)就必須建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行描述，分析問題中所用到的數(shù)據(jù)是如何組織的，研究數(shù)據(jù)之間的關(guān)系如何，進(jìn)而為解決這些問題設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)。1.1 什么是數(shù)據(jù)結(jié)構(gòu)例1 職工信息管理圖1.1 職工花名

2、冊表編號(hào)姓 名性 別年 齡月 收 入1李 泉男519802王 怡女479453張 三男358704馬小丁男27840. 將每位職工的信息組織成如圖1.1所示的花名冊?；麅灾忻總€(gè)職工的信息由編號(hào)、姓名、性別、年齡、月收入等項(xiàng)目組成，占表的一行，表中的結(jié)點(diǎn)和結(jié)點(diǎn)之間是一種簡單的線性關(guān)系,這就是上述花名冊表的線性邏輯結(jié)構(gòu)。當(dāng)用計(jì)算機(jī)對上述花名冊表中的數(shù)據(jù)進(jìn)行運(yùn)算時(shí)，就要考慮那些結(jié)點(diǎn)在計(jì)算機(jī)中的存儲(chǔ)表示，即存儲(chǔ)結(jié)構(gòu)。另外，還必須考慮如何進(jìn)行結(jié)點(diǎn)的插入、刪除、修改、檢索或查找，這就涉及到數(shù)據(jù)的運(yùn)算 例2 旅游交通網(wǎng)絡(luò)圖 如圖1.2所示，為一個(gè)旅游交通網(wǎng)絡(luò)咨詢系統(tǒng)，可采用一種稱之為圖的結(jié)構(gòu)來表示實(shí)際的交

3、通網(wǎng)絡(luò)， 此時(shí)，這個(gè)交通網(wǎng)絡(luò)圖就表示一個(gè)數(shù)據(jù)結(jié)構(gòu)。在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)結(jié)點(diǎn)之間都可以相關(guān)。同樣，必須考慮構(gòu)造后將這張圖存放入計(jì)算機(jī)中，這就要涉及到圖的存儲(chǔ)結(jié)構(gòu)問題，以及圖的運(yùn)算。 從以上例子可見，要描述諸如此類的非數(shù)值計(jì)算問題的數(shù)學(xué)模型，涉及到一些諸如表、圖還有樹之類的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)課程實(shí)際上是一門研究非數(shù)值計(jì)算問題的程序設(shè)計(jì)中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和運(yùn)算操作等的一門學(xué)科。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)（特別是非數(shù)值計(jì)算的程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。

4、數(shù)據(jù)是指信息的載體，是對客觀事物的符號(hào)表示，是對有效地輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。如聲音、圖形、圖像。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。有時(shí)也稱之為結(jié)點(diǎn)、元素、頂點(diǎn)、記錄等。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成，如上面職工花名冊中的每個(gè)人的信息就是一個(gè)數(shù)據(jù)元素，而每個(gè)人的信息包括編號(hào)、姓名、性別、年齡、月收入等，這每一個(gè)項(xiàng)目就屬于數(shù)據(jù)項(xiàng)。1.2 基本概念和術(shù)語 數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)類型（數(shù)據(jù)類型）是對在計(jì)算機(jī)中表示的同一數(shù)據(jù)對象及其在該數(shù)據(jù)對象上的一組操作的總稱。 數(shù)據(jù)類型有時(shí)還分為原子數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型。

5、 數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)及數(shù)據(jù)之間的相互關(guān)系。一般地，數(shù)據(jù)結(jié)構(gòu)包括以下三個(gè)方面的內(nèi)容： （1）數(shù)據(jù)元素之間的邏輯關(guān)系，有時(shí)也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2）數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)存中的表示（又稱為映象），稱之為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，它包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素之間關(guān)系的表示。 （3）數(shù)據(jù)的運(yùn)算及實(shí)現(xiàn)，即對數(shù)據(jù)元素可以施加的操作及其這些操作在相應(yīng)的存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，可以看作是從具體問題抽象出來的數(shù)學(xué)模型。如上例中的職工花名冊表。根據(jù)數(shù)據(jù)元素之間的不同特性，通常有下列四類基本邏輯結(jié)構(gòu)： （1）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對一個(gè)的關(guān)系，即所

6、謂的線性關(guān)系。 （2）樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對多個(gè)的關(guān)系，是結(jié)點(diǎn)之間有分支、并具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。 （3）圖或網(wǎng)狀結(jié)構(gòu)：該結(jié)構(gòu)中的數(shù)據(jù)元素之間的關(guān)系存在多個(gè)對多個(gè)的關(guān)系，如交通網(wǎng)絡(luò)圖就是一個(gè)圖狀結(jié)構(gòu)。 （4）集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的相互關(guān)系外，別無其它關(guān)系。 有時(shí)將樹形結(jié)構(gòu)、集合和圖或網(wǎng)狀結(jié)構(gòu)稱為非線性結(jié)構(gòu)，此時(shí)數(shù)據(jù)邏輯結(jié)構(gòu)就可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)，就是數(shù)據(jù)元素及其關(guān)系如何存放入計(jì)算機(jī)內(nèi)存的問題。一般地，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可按以下四種基本存儲(chǔ)方法而得到： （1）順序存儲(chǔ)方法：

7、是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的相鄰關(guān)系而體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，通?？山柚?jì)算機(jī)語言的數(shù)組來描述。 （2）鏈狀存儲(chǔ)方式：不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，數(shù)據(jù)元素可以存儲(chǔ)在任意位置。為了實(shí)現(xiàn)數(shù)據(jù)元素之間邏輯關(guān)系的存儲(chǔ)，必須通過一些附加的手段來存儲(chǔ)這種相互關(guān)系，由此得到的存儲(chǔ)表示稱為鏈狀存儲(chǔ)結(jié)構(gòu)。一般可以用指針來實(shí)現(xiàn)，通?？山柚?jì)算機(jī)程序語言的指針類型或者游標(biāo)來來描述。 （3）索引存儲(chǔ)方法：該方法通常是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加的索引表。索引表一般有稠密索引和稀疏索引兩種。 （4）散列存儲(chǔ)方法：該方法是依據(jù)結(jié)點(diǎn)的關(guān)

8、鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，而后將結(jié)點(diǎn)按某種方式存入該地址的一種存儲(chǔ)方法。 數(shù)據(jù)的運(yùn)算是指定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的一組操作的集合。例如，檢索（查找）、插入、刪除、定位、修改、排序等。要注意的是，這些運(yùn)算實(shí)際上是在邏輯結(jié)構(gòu)上對抽象數(shù)據(jù)所施加的一系列抽象的操作，運(yùn)算的實(shí)現(xiàn)依賴于所選取的存儲(chǔ)結(jié)構(gòu)，是依賴于不同的計(jì)算機(jī)程序設(shè)計(jì)語言的。 數(shù)據(jù)類型是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個(gè)數(shù)據(jù)集合上的一組運(yùn)算。 在高級程序語言中，數(shù)據(jù)類型可以分為原子類型和結(jié)構(gòu)類型。原子類型即值不可分解的類型，如C語言中的整型、字符型、實(shí)型、指針類型等；而結(jié)構(gòu)類型則指的是其值可由若干成分按某種結(jié)構(gòu)組成的類型，是可以分解的

9、，如C語言中提供的結(jié)構(gòu)體。 抽象數(shù)據(jù)類型（ADT）是指一個(gè)數(shù)學(xué)模型及定義在該數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)模型的定義取決于它的一組邏輯特性，與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。1.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 算法是對特定問題求解方法和步驟的一種描述，它是指令的一組有限序列。一個(gè)算法必須具備以下五個(gè)重要特性： （1）輸入：一個(gè)算法必須具有零個(gè)或多個(gè)的外界輸入。 （2）輸出：一個(gè)算法必須有一個(gè)或多個(gè)的輸出。 （3）有窮性：一個(gè)算法對任何合法的輸入值必須總是在執(zhí)行有窮步之后結(jié)束，并且每步都必須在有窮時(shí)間內(nèi)完成。利用這一點(diǎn)，我們可以區(qū)別算法與程序。 （4）確定性：算法中每一條指令必須有確切的含義，不會(huì)

10、產(chǎn)生二義性。 （5）可行性：算法中描述的操作都必須可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)，而且算法必須在有限時(shí)間內(nèi)完成。 一個(gè)算法可以用自然語言、數(shù)學(xué)語言或約定的符號(hào)來描述，也可用計(jì)算機(jī)高級程序語言來描述，如PASCAl語言、C語言、C、Java或偽代碼等。本書選用C語言作為描述算法的工具。1.4.1 算法描述1.4 算法描述與算法評價(jià)1.4.2 算法的設(shè)計(jì)要求 設(shè)計(jì)一個(gè)好的算法可以從以下幾個(gè)方面考慮： （1）正確性。算法是為了針對解決具體問題而提出的，算法的正確與否必須滿足解決實(shí)際問題的需要，要經(jīng)得起一切可能的輸入數(shù)據(jù)的考驗(yàn)。（2）可讀性。算法要讓人閱讀得懂，程序要盡可能地簡單通俗，當(dāng)然

11、也必須有效。（3）健壯性。當(dāng)輸入數(shù)據(jù)非法時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理。（4）高效率。要求算法的執(zhí)行時(shí)間要盡可能地短，對于存儲(chǔ)空間要盡可能地少，即做到既省時(shí)又節(jié)省空間。 要設(shè)計(jì)一個(gè)好的算法，必須對這幾個(gè)方面綜合考慮，才可以設(shè)計(jì)出較好較優(yōu)的算法。 考慮算法的效率應(yīng)從下幾個(gè)方面考慮： （1）時(shí)間效率?？紤]算法所耗費(fèi)的運(yùn)行時(shí)間。 （2）空間效率?？紤]運(yùn)行算法需要耗費(fèi)的存儲(chǔ)空間，其中主要考慮算法所需的輔助存儲(chǔ)空間。 （3）算法應(yīng)盡可能地簡單，易于理解，易于編碼和調(diào)試并能得出正確結(jié)果。 一個(gè)算法的運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)行所耗費(fèi)的時(shí)間。它可以認(rèn)為是算法中每條語句的執(zhí)行時(shí)間之和。1.4.3

12、算法的評價(jià) 例如，兩個(gè)nn矩陣相乘的算法： for（i=1；i=n；i+） /* n+1次 */ for（j=1；j=n；j+） /* n（n+1）次*/ ci j = 0； /* nn次 */ for（k=1；k0時(shí)的線性表記為：（a1，a2，ai，an） 其中，a1是第一個(gè)數(shù)據(jù)元素，又稱為起始結(jié)點(diǎn)，an是最后一個(gè)數(shù)據(jù)元素，又稱為終端結(jié)點(diǎn)。當(dāng)i=1，2，n-1時(shí)，ai有且僅有一個(gè)直接后繼a i+1；當(dāng)i =2，3，n 時(shí)，ai有且僅有一個(gè)直接前趨a i-1。注意這里的ai（1 i n）僅僅是一個(gè)抽象的符號(hào)，其具體含義，在不同的情況下各不相同，它可以是一個(gè)數(shù)，一條記錄或一個(gè)符號(hào)，甚至是更復(fù)雜的

13、信息。例如，英文字母表(A，B，Z)是一個(gè)線性表，職工工資表等。 線性表的結(jié)點(diǎn)之間的邏輯關(guān)系符合線性結(jié)構(gòu)的邏輯特征，是一種線性結(jié)構(gòu)。 2.1.1 線性表的邏輯結(jié)構(gòu)2.1 線性表的基本概念 常見的線性表的基本運(yùn)算： （1）置空表SETNULL(L)：將線性表L置成空表。 （2）求長度LENGTH(L)：求給定線性表L中數(shù)據(jù)元素的個(gè)數(shù)。 （3）取元素GET(L,i)：結(jié)果是線性表L中的第i個(gè)數(shù)據(jù)元素。 （4）定位函數(shù)LOCATE(L,x)：當(dāng)線性表中存在一個(gè)值為x的數(shù)據(jù)元素，則結(jié)果是該數(shù)據(jù)元素在表中的位序，否則，表示值為x的數(shù)據(jù)元素不存在。 （5）前趨函數(shù)PRIOR(L,x)：若x為線性表中的一個(gè)

14、數(shù)據(jù)元素，且其位序大于1，則結(jié)果為L 的直接前趨，否則，給出一個(gè)特殊值示出該元素沒有直接前趨。 （6）后繼函數(shù)NEXT（L，x）：若x的位序小于LENGTH（L），則結(jié)果為該元素的直接后繼，否則，給出一個(gè)特殊值，示出x無直接后繼。 2.1.2 線性表的運(yùn)算 （7）插入INSERT(L,x,i)：函數(shù)功能為在線性表L中的第i 個(gè)位置上插入一個(gè)值為x 的新元素，使運(yùn)算前長度為n 的線性表變?yōu)殚L度為n+1的線性表。 （8）刪除DELETE(L,i)：函數(shù)功能為刪除線性表L中的第i 個(gè)數(shù)據(jù)元素，使在此之前長度為n 的線性表L變成長度為n1的線性表。 利用基本運(yùn)算可以實(shí)現(xiàn)線性表的其它復(fù)雜運(yùn)算。 需要指出

15、的是，這里給出的只是定義在邏輯結(jié)構(gòu)上的抽象運(yùn)算，即只關(guān)心這些運(yùn)算是“做什么”的，至于“怎樣實(shí)現(xiàn)”則依賴于所選定的存儲(chǔ)結(jié)構(gòu)。 順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，即按順序存儲(chǔ)方式構(gòu)成的線性表的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方式是：線性表的第一個(gè)元素存放在個(gè)一片連續(xù)的存儲(chǔ)空間開始位置處，第二個(gè)元素緊跟著存放在第一元素之后，以此類推。 利用順序表來存儲(chǔ)線性表，可借助數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的物理位置相鄰特性來表示線性表中數(shù)據(jù)元素之間的線性邏輯關(guān)系。 設(shè)線性表每個(gè)元素占c個(gè)存儲(chǔ)單元，若以第一個(gè)數(shù)據(jù)元素在存儲(chǔ)單元中的存儲(chǔ)地址作為起始地址，則可得出線性表中第i個(gè)數(shù)據(jù)元素的地址為： LOC(ai)=LOC(a1)+(i-1)* c

16、（1iLENGTH(L)） 這樣，一旦起始地址LOC（a1） （圖2.1中設(shè)為b）和一個(gè)數(shù)據(jù)元素占用的存儲(chǔ)單元的大?。╟值）確定下來，就可求出任一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，顯然，這種表便于進(jìn)行隨機(jī)訪問，因此，順序表是一種隨機(jī)存取的結(jié)構(gòu)。2. 2.1 順序表2.2 線性表的順序存儲(chǔ) 在具體實(shí)現(xiàn)時(shí)，可利用高級程序設(shè)計(jì)語言中的一維數(shù)組即向量來為線性表的順序存儲(chǔ)開辟存儲(chǔ)空間，存儲(chǔ)空間大小應(yīng)大于等于線性表長度，用一個(gè)整型變量來表示線性表的長度，從而可將順序表描述為： # define MAXSIZE 999 typedef int elemtype ； /* elemtype表示元素類型，此處設(shè)為 int

17、*/ typedef struct elemtype vecMAXSIZE； int len； sequenlist ； 在上面描述中，順序表是一個(gè)結(jié)構(gòu)體類型。其中，vec成員（又稱為數(shù)據(jù)域）指線性表數(shù)據(jù)元素所占用的存儲(chǔ)空間，而len成員（又稱為長度域）則用于存儲(chǔ)線性表長度，它表示線性表最后一個(gè)元素在向量中的位置，elemtype 則為線性表中數(shù)據(jù)元素類型。 本節(jié)討論在定義線性表順序存儲(chǔ)結(jié)構(gòu)之后，如何在這種結(jié)構(gòu)上實(shí) 現(xiàn)有關(guān)數(shù)據(jù)運(yùn)算。下面重點(diǎn)討論線性表的數(shù)據(jù)元素的插入和刪除運(yùn)算。 1插入運(yùn)算 線性表的插入運(yùn)算是指在表的第i個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素，插入的結(jié)果使得線性表的長度由n變?yōu)閚+1，

18、線性表的數(shù)據(jù)元素間的邏輯關(guān)系發(fā)生了變化，使得物理存儲(chǔ)順序也發(fā)生相應(yīng)的變化。插入過程如圖2.2所示。2.2.2 順序表上的基本運(yùn)算具體算法描述如下： int insert(sequenlist *L， int i，elemtype x) int j； if (*L).len)=MAXSIZE-1) printf(“the list is overflow!n”)； /*溢出判斷*/ return（0）； else if ( i(*L).len+1) printf(“position is not correct!n”)； return（0）；/*插入位置不正確*/ else for (j = (

19、*L).len；j =i-1；j-) /*后移元素*/ (*L).vec j+1 = (*L).vec j ； (*L).veci-1 = x； /*插入新元素x*/ (*L).len =(*L).len+1； /*修改表長*/ return(1); /*insert*/ 在本算法中是從最后一個(gè)元素開始后移，直到第i個(gè)元素為止。該算法時(shí)間主要花費(fèi)在for循環(huán)語句上，執(zhí)行的次數(shù)為n-i+1。當(dāng)i=1時(shí)，全部元素均參加移動(dòng)，共需要移動(dòng)n次；當(dāng)i = n+1時(shí)，不需移動(dòng)元素。 算法在最壞情況下，時(shí)間復(fù)雜度為O(n)，最好情況下時(shí)間復(fù)雜度為O(1)。顯然，元素移動(dòng)的次數(shù)直接影響了算法執(zhí)行時(shí)間。 平均移

20、動(dòng)次數(shù)。 假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，且為等概率，則平均移動(dòng)次數(shù)的期望值為： 其中，當(dāng)1in+1時(shí)，p1=p 2= =pn+1 = 可見，在順序存儲(chǔ)的線性表中插入一個(gè)元素，約平均移動(dòng)線性表中一半的元素，顯然，當(dāng)n較大時(shí)，算法效率較低，算法的平均時(shí)間復(fù)雜度為O(n)。2刪除運(yùn)算 刪除運(yùn)算是指將線性表中的第i個(gè)元素刪除，使線性表的長度由n變成n-1，由： (a1，a2，a i-1，ai，a i+1，an)變成為： (a1，a2，a i-1，a i+1，an) 其中， 1in。 線性表進(jìn)行刪除元素后，仍是一個(gè)線性表。刪除過程如圖2.3所示。具體算法如下： void delete(L

21、，i) sequenlist *L； int i； int j； if (i(*L).len+1) printf(“delete fail！n”)； /*刪除位置不正確*/ else *y =(*L).veci-1；/*y為一外部變量，用于接收被刪除的元素*/ for(j= i；j=(*L).len；j +) (*L).vecj-1=(*L).vecj； /*元素前移*/ (*L).Len-； /*修改表長*/ /*delete*/ 與插入算法相似，要?jiǎng)h除一個(gè)元素需向前移動(dòng)元素，刪除第i個(gè)元素時(shí)，將第i+1，i+2，n個(gè)元素依次前移，其移動(dòng)次數(shù)為n-i，假設(shè)刪除線性表中的任一位置上元素的概率相

22、等（等于1/n），則刪除運(yùn)算所需的移動(dòng)元素的平均移動(dòng)次數(shù)如下所示。 由此可見，對線性表刪除一個(gè)元素時(shí)，約需有一半的元素參加移動(dòng)。顯然，該算法的時(shí)間復(fù)雜度為(n)。 通過以上討論可以發(fā)現(xiàn)，當(dāng)表長較大時(shí)，對順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入和刪除運(yùn)算，由于要移動(dòng)元素，運(yùn)算效率低，但這種存儲(chǔ)結(jié)構(gòu)對于隨機(jī)存取元素卻十分方便。 例如，一個(gè)線性表中可能含有重復(fù)的元素（值相同），現(xiàn)要求刪除重復(fù)元素中的多余元素，只保留其中位序最小的一個(gè)。如線性表（5，2，2，3，5，2），經(jīng)過清除重復(fù)元素后變?yōu)? 5，2，3 )。 假定線性表以順序存儲(chǔ)方式存儲(chǔ)，則其算法可描述如下： void purge(sequenlist *L ) i

23、nt i=0，j ，k； while ( i=(*L).Len-1) j = i+1； while ( j=(*L).Len-1) if (*L).veci= =(*L).vecj) for ( k =j；knext =NULL； /* 生成頭結(jié)點(diǎn)*/ r = p ； /*建立單鏈表表尾指針 */ ch = getchar ( ) ； /*ch為建立與否標(biāo)志 */ while ( ch ! = ? ) /*? 為輸入結(jié)束標(biāo)志符 */ scanf ( “ % d ” , &x ) ； /*讀入新數(shù)據(jù)元素*/ p =（linklist *）malloc (sizeof (linklist )； p

24、-data = x ; p -next = NULL；/*生成新結(jié)點(diǎn)*/ r-next = p ； /*連接新結(jié)點(diǎn) */ r = r-next ； /*修改尾指針 */ ch = getchar ( ) ；/*讀入建立與否的標(biāo)志*/ return ( head ) ； /*返回表頭指針head */ /* creatlist */ （2）建立不帶頭結(jié)點(diǎn)的單鏈表 linklist * creatlist ( ) /*函數(shù)返回一個(gè)指向鏈表表頭的指針*/ char ch；int x ；linklist *head ， *p， *r head =NULL ；r =NULL ； /*設(shè)立尾指針r，其初值

25、為空 */ ch = getchar ( )； /*讀入建立與否標(biāo)志 */ while ( ch != ? ) /* ? 為輸入結(jié)束標(biāo)志符 */ p=(linklist *)malloc(sizeof(linklist)； /*申請新結(jié)點(diǎn)空間 */ scanf ( “ % d ”，&x ) ； p-data = x ; if (head = = NULL) head = p； else r-next = p； /*非空表，則新結(jié)點(diǎn)*p插入到*r之后 */ r = p ； /*尾指針移動(dòng)，指向新的表尾 */ ch = getchar ( )； /* 讀入建立與否的標(biāo)志 */ if ( r! =

26、NULL ) r-next = NULL； return head ；/*返回表頭指針head */ /* creatlist */ 在算法中引入頭結(jié)點(diǎn)可以不必區(qū)分空表與非空表，可以統(tǒng)一空鏈表與非空鏈表的處理。 上述兩個(gè)算法的時(shí)間復(fù)雜度都為O(n)。 2.單鏈表上元素的檢索 一般情況下，可以按某個(gè)元素的序號(hào)或按某給定值兩種方法檢索。 （1）按值檢索 按值檢索，即是檢索單鏈表中是否存在值為給定值k的結(jié)點(diǎn)，整個(gè)過程可以通過結(jié)點(diǎn)的值和給定值的比較而實(shí)現(xiàn)。 linklist *locate（ linklist *head ， elemtype k ） linklist *s； s= head-next

27、 ； /*從第一個(gè)結(jié)點(diǎn)起開始比較*/ while ( s!= NULL ) /*掃描整個(gè)鏈表*/ if ( s-data != k) s = s-next ； else break ； return s； /*返回結(jié)點(diǎn)的位置或NULL*/ /*Locate*/ 算法時(shí)間復(fù)雜度為O(n)。 （2） 按序號(hào)檢索 即利用被訪問結(jié)點(diǎn)的序號(hào)而檢索或查找結(jié)點(diǎn)的過程。 linklist *get(linklist *head，int i) int j； linklist *p ； p = head ；j = 0； while ( (p-next != NULL )&( i j ) p = p-next； j

28、 + ； if (i= =j) return p； else return NULL ； /*get */ 該算法中最壞情況下的時(shí)間復(fù)雜度為O(n)。 3單鏈表上元素的插入和刪除運(yùn)算 插入結(jié)點(diǎn)的指針變化圖2.8所示。指針的修改操作為： s-next=p-next； p-next=s； 上述指針進(jìn)行相互賦值的語句順序不能顛倒，若次序變化為： p-next=s； s-next=p-next；則會(huì)導(dǎo)致錯(cuò)誤。 同樣，要?jiǎng)h除單鏈表結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)也很簡單，只要用一個(gè)指針指向被刪除結(jié)點(diǎn)，修改*p的指針域，最后釋放結(jié)點(diǎn)*p即可，如圖2.9所示。刪除一個(gè)結(jié)點(diǎn)* p的后繼結(jié)點(diǎn)的指針操作為： p-next =

29、p-next -next ； 不難發(fā)現(xiàn)，在單鏈表存儲(chǔ)結(jié)構(gòu)中進(jìn)行元素的插入和刪除時(shí)，只需要修改有關(guān)的指針內(nèi)容，而不需要移動(dòng)元素。 （1） 插入算法 （a） insert (linklist *p ,elemtype x) /*將值為x的新結(jié)點(diǎn)插入*p之后 */ linklist *s； s =（linklist *）malloc ( sizeof( linklist) ； /* 生成x的新結(jié)點(diǎn)*s */ s-data=x； s-next=p-next ； /*新結(jié)點(diǎn)鏈入單鏈表 */ p-next=s； /*insert*/ （b） void insert (linklist *head,elem

30、type k,elemtype x) /*在單鏈表中值為k的結(jié)點(diǎn)之前插入一個(gè)值為x的新結(jié)點(diǎn)*/ linklist *q， *p， *r； r =(linklist *)malloc( sizeof( linklist)； / *生成新結(jié)點(diǎn) */ r-data = x； if ( head-next = =NULL) head-next = r ； r-next = NULL ； else q = head-next ； p = head-next-next ； while ( p ! = NULL ) if ( p-data ! = k ) */ q = p； p = p-next ； els

31、e break ； if ( p ! = NULL ) q -next = r ； r-next = p； else /*在鏈表表尾處插入新結(jié)點(diǎn) */ q -next = r； r-next =NULL； /* insert */ 該算法的時(shí)間主要耗費(fèi)在查找值為k的結(jié)點(diǎn)位置上，算法時(shí)間復(fù)雜度為O(n) 。（2）刪除算法（a） delete (linklist *p ) /*刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/ linklist *r； r = p-next ； if(r!=NULL) p-next = r-next； free (r)； /*delete*/（b）linklist *delete(lin

32、klist *head，int i) /*刪除單鏈表head的第i個(gè)結(jié)點(diǎn)*/ int j = 0 ； linklist *p，*s，*q； p = head ；j = 0 ； while ( p-next != NULL)& (jnext ； j + ； if ( p-next!=NULL ) q = p-next ； p-next = p-next-next ； free (q) ； else return NULL ； s = head ； return s ； /* delete */ 該算法時(shí)間復(fù)雜度為O(n) 。 例，將兩個(gè)遞增的單鏈表合并為一個(gè)遞增單鏈表，且要求不重新開辟空間，其算

33、法可描述如下： void *union (linklist *heada，linklist *headb ) /*合并單鏈表heada與headb */ linklist *p，*q，*r，*u ； p = heada-next ； q = headb-next ； r = heada ； while ( p ! = NULL )& (q ! = NULL ) if ( p-data q-data ； u = q-next ； r-next = q ； r = q ； q-next = p ； q = u ； else if ( p-data data ) r = p； p = p-next

34、； if ( q ! = NULL) r-next = q； /* union */2.3.3 循環(huán)鏈表 如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)（或第一個(gè)表結(jié)點(diǎn)）的地址值，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，如圖2.10所示，這樣的鏈表稱為循環(huán)鏈表。顯然，它是一種首尾相接的鏈表，從循環(huán)鏈表中任一個(gè)結(jié)點(diǎn)出發(fā)都可訪問到表中所有其它結(jié)點(diǎn)。對單鏈表的鏈接方式稍作一些改變，就可構(gòu)成一個(gè)新的存儲(chǔ)結(jié)構(gòu)單循環(huán)鏈表。同樣，也有多重鏈的循環(huán)鏈表。在循環(huán)鏈表中，為了使空表和非空表的處理一致，同樣可設(shè)置一個(gè)頭結(jié)點(diǎn)。 循環(huán)鏈表的基本運(yùn)算與單鏈表基本一致 ，差別只在于最后一個(gè)結(jié)點(diǎn)的循環(huán)處理上。只要將單鏈表算法中出現(xiàn)N

35、ULL處改為頭指針即可。 例如，將單循環(huán)鏈表倒置或逆置。 linklist *invert (head ) linklist *head； linklist *p，*q，*s; q = head； p= head-next； while ( p ! = head ) s = q ； q = p ； p = p-next ； q-next = s； p-next = q； return head； /* invert */2.3.4 雙向鏈表 在單循環(huán)鏈表中，從任一個(gè)已知結(jié)點(diǎn)出發(fā)可以找到其前趨結(jié)點(diǎn)，但時(shí)間耗費(fèi)需O(n )，若希望能快速確定一個(gè)結(jié)點(diǎn)的直接前趨，可以再加上一個(gè)指針域存儲(chǔ)其直接前趨的信

36、息，這樣就可以構(gòu)成雙向鏈表，它有兩個(gè)方向不同的鏈 ，如果將每個(gè)方向的鏈表構(gòu)成一個(gè)環(huán)，則可以構(gòu)成雙向循環(huán)鏈表。 雙向鏈表的C語言描述： typedef struct dupnode elemtype data ； struct dupnode *next，*prior ； dulinklist ； dulinklist *head ; 雙向循環(huán)鏈表也可由頭指針head唯一確定，同樣可增加頭結(jié)點(diǎn)，使得雙鏈表的某些運(yùn)算簡便一些，如圖2.11所示。 由于雙向鏈表在其結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)既有指向其直接前趨的指針域，又有指向其直接后繼的指針域，因此比起單鏈表來，要在一個(gè)雙向鏈表中檢索某一個(gè)已知結(jié)點(diǎn)的直接前趨和

37、后繼結(jié)點(diǎn)要方便得多。 結(jié)點(diǎn)*p可通過多種方式訪問，設(shè)指針p指向雙向鏈表中某個(gè)結(jié)點(diǎn)，則有：p-next-prior = p = p-prior-next 雙向鏈表中結(jié)點(diǎn)的插入情況如圖2.12所示。 在*p結(jié)點(diǎn)之前插入結(jié)點(diǎn)*s的正確步驟應(yīng)為： p-prior-next = s； s-prior = p-prior； s-next = p ； p-prior = s ； 由于雙向鏈表中每個(gè)結(jié)點(diǎn)涉及兩個(gè)指針的運(yùn)算，對于某些運(yùn)算要注意運(yùn)算順序。 在上面的步驟中指針p-prior的修改必須在 *p結(jié)點(diǎn)的前趨結(jié)點(diǎn) *(p-prior)的后繼指針修改之后方可改動(dòng)，否則會(huì)不能正確地插入結(jié)點(diǎn)。 在雙向鏈表中刪除一

38、個(gè)結(jié)點(diǎn)*p的指針變化如圖2.13所示。指針修改的運(yùn)算步驟為： p-prior-next= p-next； p-next-prior =p-prior； 1插入算法 void indulist (dulinklist *head ,int i, elemtype x)/*在雙向循環(huán)鏈表head中的第i個(gè)結(jié)點(diǎn)之前插入值為x的新結(jié)點(diǎn) */ dulinklist *p，*s ;int j ; p = head ; j = 0 ; while ( p-next! = head)&(j next ; j+ ; if ( i 0)&(j= =i-1) s = malloc (sizeof(dulinklis

39、t) ; s-data = x ; s-next = p-next ; s-prior = p ； p-next = s ； s-next-prior = s ; else printf ( “error！n” ) /* indulist */2刪除算法 void deledulist (dulinklist *head,int i) /* 刪除雙向鏈表head中的第i個(gè)結(jié)點(diǎn) */ dulinklist *p ; int j ; p = head ; j = 0 ; while (p-next! = head)&(j next ; j + ; if ( i 0)&(j = = i) p-pri

40、or-next = p-next ; p-next-prior = p-prior ; free(p) ; else printf (“errorn”); /*deledulist*/ 以上兩個(gè)算法的時(shí)間復(fù)雜度都為O(n)。 一般而言，對存儲(chǔ)結(jié)構(gòu)的選擇應(yīng)主要從存儲(chǔ)空間、運(yùn)算時(shí)間、程序設(shè)計(jì)語言三方面考慮。 （1）存儲(chǔ)空間。 （2） 運(yùn)算時(shí)間。 （3）程序設(shè)計(jì)語言。 線性表的順序?qū)崿F(xiàn)和鏈接實(shí)現(xiàn)各有優(yōu)缺點(diǎn)，只能根據(jù)實(shí)際問題的具體實(shí)現(xiàn)需要，對各個(gè)方面的優(yōu)缺點(diǎn)加以綜合平衡后來確定適宜的存儲(chǔ)結(jié)構(gòu)。2.4 線性表存儲(chǔ)結(jié)構(gòu)的選擇2.5 線性表的應(yīng)用舉例 在數(shù)學(xué)上，一個(gè)一元多項(xiàng)式Pn(x)可寫成： Pn(x)=

41、p0+p1x+p2x2+pnxn 顯然，該多項(xiàng)式可以由每項(xiàng)的系數(shù)p0，p1，pn唯一地確定，所以，可以將它用一個(gè)線性表P來表示成： P=(p0，p1，pi，pn) 若Qm(x)也是一元多項(xiàng)式，則其也可用線性表Q表示為： Q=(q0，q1，qm) 則Pn(x)+ Qm(x)同樣也可用線性表R表示。設(shè)mexpq-exp，此時(shí)*q結(jié)點(diǎn)應(yīng)為和多項(xiàng)式中的一項(xiàng)，*q 結(jié)點(diǎn)應(yīng)插在*p結(jié)點(diǎn)之前，然后q指針在原來的鏈表上后移。 （2）若p-exp=q-exp，則對應(yīng)項(xiàng)的系數(shù)相加，若系數(shù)和不為零，只要修改*p 結(jié)點(diǎn)的系數(shù)域，釋放q結(jié)點(diǎn)，否則，應(yīng)刪除*p 結(jié)點(diǎn)，釋放p 、q結(jié)點(diǎn)。 （ 3）若p-expexp，則*p

42、 應(yīng)為和多項(xiàng)式的一項(xiàng)，p指針在原來的鏈表上后移。 其算法描述如下： polynode *polyadd (pa，pb) polynode *pa , *pb ; polynode *p , *q ,*pre ,*r ; float x ; p = pa-next ; q = pb-next ; pre = pa ; while ( p ! = NULL)&( q ! = NULL) if (p-exp q-exp) r = q-next ; q-next = p ; pre-next = q ; pre = q ; q = r ; else if (p-exp = =q-exp) x = p-

43、coef + q-coef ; if ( x != 0) p-coef = x ; pre = p ; else pre-next = p-next ; free(p) ; p = pre-next ; r = q ; q = q-next ; free(r) ; else if (p-expexp) pre = p ; p = p-next ; / if ( q ! = NULL) / pre-next = q ; free (pb) ; return pa； /* polyadd */ 假設(shè)P多項(xiàng)式n項(xiàng)，Q多項(xiàng)式m項(xiàng)，則該算法的時(shí)間復(fù)雜度為O(m+n)。 圖2.15和圖2.16為兩多項(xiàng)式相

44、加和的示意圖，其中空白結(jié)點(diǎn)表示已被釋放的結(jié)點(diǎn)空間。第3章 棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用舉例3.3 隊(duì)列3.4 隊(duì)列的應(yīng)用舉例第3章 棧和隊(duì)列 棧和隊(duì)列是兩類特殊的線性表，其邏輯結(jié)構(gòu)仍然是線性結(jié)構(gòu)，但棧和隊(duì)列是運(yùn)算受限的線性表。棧和隊(duì)列結(jié)構(gòu)被廣泛應(yīng)用于各種程序設(shè)計(jì)中。 本章討論棧和隊(duì)列的定義、運(yùn)算及其實(shí)現(xiàn)等。 3.1.1 棧的定義及其運(yùn)算 棧是一類特殊的線性表，數(shù)據(jù)元素的插入和刪除運(yùn)算只能在表的一端進(jìn)行，通常將進(jìn)行插入和刪除的一端稱為棧頂，另一端稱為棧底。將元素的插入稱為入?；蜻M(jìn)棧，元素的刪除稱為出?；蛲藯?。 棧也稱為后進(jìn)先出的線性表（簡稱LIFO表）如圖3.1(a)所示。 在日常生活中，

45、棧的形式經(jīng)常出現(xiàn)。例如，一疊盤子或一疊書的取放、鐵路調(diào)度站，如圖3.1(b)所示。 棧的基本運(yùn)算： （1）置空棧setnull(s)：將棧s置成空棧，建立起棧頂指針。 （2）判?？誩mpty(s)：若s為空棧，則返回TRUE值，否則返回FALSE值。 （3）入棧push(s,x)：若s未滿，將x插入s棧棧頂，并使棧頂指針指向x。 （4）出棧pop(s)：若s棧非空，則從棧中刪去棧頂元素，返回原棧頂元素。 （5）取棧頂元素gettop(s)：若s棧非空，則返回當(dāng)前棧頂元素。3.1 棧3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu) 棧的順序存儲(chǔ)結(jié)構(gòu)又稱為順序棧，順序棧也可用向量來實(shí)現(xiàn)。順序棧的類型定義如下： #de

46、fine MAXSIZE 100 /*棧的最大容量，這里設(shè)為100*/ typedef struct datatype stackMAXSIZE; int top; seqstack; /*順序棧類型定義*/ seqstack *s; /*定義s為指向順序棧的指針變量*/ 在順序棧中進(jìn)?；虺鰲＿\(yùn)算時(shí)要注意空間的“溢出”。當(dāng)棧滿時(shí)，若再進(jìn)行入棧運(yùn)算，會(huì)產(chǎn)生空間“上溢” ；而當(dāng)?？諘r(shí)，再進(jìn)行出棧運(yùn)算，會(huì)產(chǎn)生空間“下溢” 。圖3.2說明了棧中元素與棧頂指針的關(guān)系。 在順序棧上實(shí)現(xiàn)的棧的基本運(yùn)算。 （1）置空棧 void setnull(seqstack *s) s-top=-1; （2）判?？账惴?

47、int empty(seqstack *s) if(s-toptop=MAXSIZE-1) printf(“stack overflow！n”); return(FALSE); else s-stack+s-top=x; return(TRUE); （4）出棧 datatype pop(seqstack *s) if(s-toptop-; return(s-stacks-top+1); （5）取棧頂元素算法 datatype gettop(seqstack *s) if(s-topstacks-top); 有時(shí)可以將多個(gè)棧安排在同一個(gè)順序存儲(chǔ)空間中，實(shí)現(xiàn)多個(gè)棧共享存儲(chǔ)空間。 假定兩個(gè)棧共享空間

48、，可以給它們分配一個(gè)長度為m的數(shù)組空間如圖3.3所示。 兩個(gè)棧共享的數(shù)據(jù)類型定義如下： typedef struct datatype stackm; int top2; /* top0和top1分別為兩棧的棧頂指針*/ sharedstack;兩個(gè)棧共享存儲(chǔ)單元的部分運(yùn)算算法如下： （1）置空棧 void setnull(sharedstack *s) s-top0=-1; s-top1=m; /*setnull*/（2）入棧 int push(sharedstack *s，int i，datatype x) if(i1|s-top0+1= =s-top1) return FALSE; el

49、se if(i=0) s-stack+s-top0=x; else s-stack-s-top1=x; return TRUE; /*push*/（3）出棧 datatype pop(sharedstack *s，int i) if(i1) return NULL; else if(i= =0) if (s-top0=-1) return NULL; else return（s-stacks-top0-）; else if(s-top1= =m) return NULL; else return（s-stacks-top1+）; /*pop*/ 3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱

50、為鏈棧。鏈棧是運(yùn)算受限的單鏈表，其運(yùn)算只能在鏈表頭部進(jìn)行，其頭指針就是棧頂指針。 鏈棧的數(shù)據(jù)類型定義： typedef struct node datatype data; struct node *next; linkstack; linkstack *top; /*鏈棧頭指針，即棧頂指針*/鏈棧如圖3.5所示，其中top是棧頂指針。當(dāng)top=NULL時(shí)，該鏈棧是空棧。 鏈棧的入棧和出棧運(yùn)算算法。（1）入棧 void push(linkstack *top，datatype x) linkstack *p; p=(linkstack *)malloc(sizeof(linkstack); /

51、*生成一個(gè)新結(jié)點(diǎn)*p*/ p-data=x; p-next=top; top=p; （2）出棧 datatype pop(linkstack *top) linkstack *p; datatype x; if(top= =NULL) printf(stack empty！n); return(NULL); else ptop； top=top-next; x=p-data; free(p); /*釋放p所指的結(jié)點(diǎn)*/ return(x); 3.2 棧的應(yīng)用舉例 3.2.1 表達(dá)式求值 一般的，一個(gè)表達(dá)式由操作數(shù)、運(yùn)算符和分界符組成。若運(yùn)算符出現(xiàn)在兩個(gè)運(yùn)算數(shù)或操作數(shù)之間（單目運(yùn)算符除外），稱為

52、中綴表達(dá)式。中綴表達(dá)式有利于人的理解，但不適合機(jī)器的實(shí)現(xiàn)。因此，在編譯系統(tǒng)中，要把中綴表達(dá)式變換成一種后綴表達(dá)式（也稱為逆波蘭式），在后綴表達(dá)式中，運(yùn)算符處在兩個(gè)操作數(shù)之后。后綴表達(dá)式一不需要使用括號(hào)；二不需要考慮運(yùn)算符的優(yōu)先級，只需從左到右掃描后綴表達(dá)式，當(dāng)掃描遇到運(yùn)算符時(shí)，就把它前面的兩個(gè)操作數(shù)取出，然后進(jìn)行運(yùn)算。如圖3.6所示。 把中綴表達(dá)式變換為相應(yīng)的后綴表達(dá)式，然后根據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值，這兩個(gè)步驟都可以利用棧結(jié)構(gòu)來實(shí)現(xiàn)。 運(yùn)算后綴表達(dá)式ABCD/-E*+T1C/DABT1-E*+T2B-T1AT2E*+T3T2*EAT3+T4A+T3T4 圖3.6 后綴表達(dá)式的計(jì)算過程 要把

53、中綴表達(dá)式轉(zhuǎn)變?yōu)楹缶Y表達(dá)式可以從左到右依次掃描中綴表達(dá)式，根據(jù)所讀到的是操作數(shù)還是運(yùn)算符，利用棧并結(jié)合各個(gè)運(yùn)算符之間的優(yōu)先級關(guān)系（表3-1 ）來進(jìn)行運(yùn)算。其算法思想是：設(shè)置一個(gè)棧并初始化，然后從左到右順序讀入中綴表達(dá)式。當(dāng)讀到的是操作數(shù)時(shí)就直接將其輸出，并接著讀下一個(gè)。當(dāng)讀到的是運(yùn)算符時(shí)，就將它賦給2，并根據(jù)運(yùn)算符的優(yōu)先級關(guān)系表3-1，比較2與當(dāng)前棧頂運(yùn)算符1的優(yōu)先級。若2的優(yōu)先級比1的高，則將2進(jìn)棧，繼續(xù)讀下一個(gè)；若2的優(yōu)先級比1的低，則將1出棧并作為后綴表達(dá)式的一部分輸出，然后繼續(xù)比較2與新的當(dāng)前棧頂運(yùn)算符1的優(yōu)先級；若2的優(yōu)先級與1的相同，且1為(，2為)，則將1出棧，并丟棄1和2，再繼

54、續(xù)讀下一個(gè)；若2的優(yōu)先級與1的相同，且1和2都是#，則表示表達(dá)式處理完畢，算法結(jié)束。 例如，圖3.7表示對中綴表達(dá)式A*(B+C)*D變換為后綴表達(dá)式，最后結(jié)果為ABC+*D*。表3-1 運(yùn)算符優(yōu)先級關(guān)系表2 1+()#+(#stack0=#; s-top=0; ch2=Rj; while (!(ch2= = # ) & (gettop(s)= =#) /*當(dāng)不是結(jié)束符#時(shí)循環(huán)*/ if(ch2!=+ ) & (ch2!=- ) & (ch2!=* ) & (ch2!=/)& (ch2!=( ) & (ch2!=) & (ch2!=#) printf(%c，ch2); ch2=R+j; els

55、e if(proceed(gettop(s)，ch2)= =) ch1=pop(s); printf(%c，ch1); else if(proceed(gettop(s),ch2)= = )&（gettop(s)= =(&ch2=)） ch1=pop(s); ch2=R+j; else printf(輸入表達(dá)式有語法錯(cuò)誤); /* postfix*/其中proceed( )函數(shù)實(shí)現(xiàn)表3-1的運(yùn)算符優(yōu)先級關(guān)系比較功能，其函數(shù)返回值為對應(yīng)的字符，取值為，front=-1; sq-rear=-1; （2）入隊(duì) int enqueue(sequeue *sq，datatype x) if (sq-re

56、ar= =MAXSIZE-1) return(FALSE); else sq-queue+sq-rear=x; return(TRUE); （3）出隊(duì) datatype delqueue(sequeue *sq) if(sq-front= =sq-rear) return(NULL); else return(sq-queue+sq-front); 以上算法在入隊(duì)運(yùn)算中，由于隊(duì)滿條件的限制會(huì)產(chǎn)生 “假上溢”現(xiàn)象，即當(dāng)前隊(duì)列并沒有滿但會(huì)產(chǎn)生“上溢”。如圖3.13所示。 為了更好地解決“假上溢” 問題，可以將順序隊(duì)列設(shè)想為一個(gè)首尾相接的圓環(huán)，稱為循環(huán)向量，隊(duì)列稱為循環(huán)隊(duì)列，如圖3.14所示。此時(shí)，

57、可以克服“假溢出”現(xiàn)象。 隊(duì)尾指針加1的運(yùn)算在循環(huán)意義下可描述為： if(sq-rear+1= =MAXSIZE) sq-rear=0; else sq-rear+; 也可以利用利用數(shù)學(xué)上的求模運(yùn)算描述為： sq-rear=(sq-rear+1) % MAXSIZE 同樣，出隊(duì)運(yùn)算時(shí)，在循環(huán)意義下的隊(duì)頭指針加1運(yùn)算可描述為： sq-front=(sq-front+1) % MAXSIZE 但在利用循環(huán)隊(duì)列時(shí)會(huì)出現(xiàn)隊(duì)空和隊(duì)滿兩種不同的狀態(tài)無法區(qū)別的情形，如圖3.14（b）和（c），利用等式sq-front=sq-rear都可以表示隊(duì)空和隊(duì)滿兩種不同的狀態(tài)。 一般的，可利用以下兩種方法解決這個(gè)問題

58、： （1）設(shè)置一個(gè)區(qū)別隊(duì)列滿與隊(duì)列空的標(biāo)志，該標(biāo)志用于標(biāo)記在隊(duì)列中執(zhí)行的最后一次運(yùn)算。不過，使用標(biāo)志會(huì)減慢隊(duì)列入隊(duì)和出隊(duì)的速度。 （2）第二種方法是在入隊(duì)運(yùn)算之前，先判斷(sq-rear+1)%MAXSIZE與sq-front是否相等，若相等，則認(rèn)為隊(duì)列滿。但這樣會(huì)使得在循環(huán)隊(duì)列中隊(duì)頭指針?biāo)傅奈恢檬冀K是空的，有MAXSIZE個(gè)分量的循環(huán)空間只能表示長度不超過MAXSIZE-1的隊(duì)列。但通過少利用一個(gè)元素空間而解決了隊(duì)滿與隊(duì)空條件相同的矛盾，總的來說是可行的。 循環(huán)隊(duì)列的入隊(duì)和出隊(duì)運(yùn)算算法描述如下：（1）入隊(duì)列算法 int encyque(sequeue *sq，datatype x) if(

59、sq-rear+1)%MAXSIZE=sq-front) return(FALSE); else sqrear=(sq-rear+1)%MAXSIZE; sq-queuesq-rear=x; return(TRUE); （2）出隊(duì)列算法 datatype delcyque(sequeue *sq) if(sq-front= =sq-rear) return(NULL); else sq-front=(sq-front+1)%MAXSIZE; return(sq-queuesq-front); 3.3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列，它是限制在表頭刪除即出隊(duì)和表尾插入即入隊(duì)

60、的單鏈表。它實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表。頭指針指向表頭結(jié)點(diǎn)，而尾指針則指向隊(duì)尾元素。一個(gè)鏈隊(duì)列可由一個(gè)隊(duì)頭指針和一個(gè)隊(duì)尾指針唯一地確定，如圖3.15。 鏈隊(duì)列定義如下：typedef struct nodedatatype data; struct node *next; queuenode; /*定義鏈隊(duì)列中的一個(gè)結(jié)點(diǎn)結(jié)構(gòu)*/typedef structqueuenode *front，*rear; linkqueue; /*定義鏈隊(duì)列結(jié)構(gòu)*/linkqueue *lq； 鏈隊(duì)列上的幾種基本運(yùn)算描述： （1）置空隊(duì) void inilinkque(linkqueue *l