線性數(shù)據(jù)結(jié)構(gòu)4動(dòng)態(tài)建立單鏈表的算法

1、在此幻燈片插入公司的徽標(biāo)從“插入菜單選擇圖片找到徽標(biāo)文件單擊“確定重新設(shè)置徽標(biāo)大小單擊徽標(biāo)內(nèi)任意位置?；諛?biāo)外部出現(xiàn)的方框是“調(diào)整控點(diǎn)使用這些重新設(shè)置對(duì)象大小如果在使用尺寸調(diào)整控點(diǎn)前按下 shift 鍵，那么對(duì)象改變大小但維持原比例。DATA1065865姓名 學(xué)號(hào) 成績(jī) 班級(jí) 李紅 9761059 95 機(jī)97.6 ABCDEFG數(shù)據(jù)結(jié)構(gòu)第2章 線性數(shù)據(jù)結(jié)構(gòu) 2.1 根本概念 2.1.1 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)2.1.2 算法的描述和評(píng)價(jià)2.2 線性表 2.2.1 線性表的定義及操作2.2.2 線性表的 順序存儲(chǔ)結(jié)構(gòu)2.2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.2.4 循環(huán)鏈表和雙向鏈表2.3 棧和隊(duì)列 2.3

2、.1 棧2.3.2 隊(duì)列2.4 串和數(shù)組 2.4.1 串2.4.2 數(shù)組習(xí)題 2.1 基 本 概 念 2.1.1 數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu) 現(xiàn)代數(shù)字計(jì)算機(jī)原是作為能快速地進(jìn)行復(fù)雜、耗時(shí)計(jì)算的工具而創(chuàng)造的。隨著計(jì)算機(jī)的開展，在計(jì)算機(jī)的絕大多數(shù)應(yīng)用中，能夠存取、處理大量信息的能力卻被認(rèn)為是計(jì)算機(jī)的首要特征，而它的計(jì)算能力在許多情況下已經(jīng)幾乎被人們忽略了。有位美國(guó)學(xué)者曾批評(píng)說：“計(jì)算機(jī)這個(gè)詞只告訴我們以前能做的事，卻未道出它的潛能。有鑒于此，人們常常把計(jì)算機(jī)稱作數(shù)據(jù)處理機(jī)。 什么是數(shù)據(jù)？數(shù)據(jù)就是是信息的載體,它可以用計(jì)算機(jī)表示并加工?？梢钥闯觯瑪?shù)據(jù)這個(gè)概念本身是隨著計(jì)算機(jī)的開展而不斷擴(kuò)展的概念。在計(jì)算機(jī)開展的

3、初期，由于計(jì)算機(jī)主要用于數(shù)值計(jì)算，數(shù)據(jù)指的就是數(shù)值。計(jì)算機(jī)硬件和軟件技術(shù)的不斷開展，擴(kuò)大了計(jì)算機(jī)的應(yīng)用領(lǐng)域，諸如字符、文字、表格、圖形、圖像、聲音等也屬于數(shù)據(jù)的范疇。 數(shù)據(jù)元素是數(shù)據(jù)集合中的一個(gè)個(gè)體，它是數(shù)據(jù)的根本單位。例如：全部學(xué)生的學(xué)籍登記卡組成學(xué)生的學(xué)籍?dāng)?shù)據(jù)，每個(gè)學(xué)生的學(xué)籍登記卡就是學(xué)籍?dāng)?shù)據(jù)的一個(gè)數(shù)據(jù)元素。 數(shù)據(jù)元素可以是一個(gè)數(shù)或字符串，也可以由假設(shè)干數(shù)據(jù)項(xiàng)組成(數(shù)據(jù)的最小單位)。在這種情況下，通常把數(shù)據(jù)元素稱為記錄。如表2-1所示的學(xué)生學(xué)籍登記表，在這個(gè)表中每一個(gè)學(xué)生的學(xué)籍登記卡作為一個(gè)數(shù)據(jù)元素，每一個(gè)元素由學(xué)號(hào)、姓名、性別、民族、籍貫、專業(yè)六個(gè)數(shù)據(jù)項(xiàng)組成。表2-1 學(xué)生學(xué)籍登記表學(xué)

4、號(hào)姓 名性 別民 族籍 貫專 業(yè)1王 安男漢北京計(jì)算機(jī)通信2李 華男回河北軟 件3張 莉女漢山西計(jì)算機(jī)應(yīng)用4張 平女漢廣東軟 件 什么是數(shù)據(jù)結(jié)構(gòu)？在任何問題中，構(gòu)成數(shù)據(jù)的數(shù)據(jù)元素并不是孤立存在的，它們之間存在著一定的關(guān)系以表達(dá)不同的事物及事物之間的聯(lián)系。所以簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)及數(shù)據(jù)元素之間關(guān)系的一門學(xué)科。它不僅是一般程序設(shè)計(jì)的根底，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要根底。它包括三個(gè)方面的內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的運(yùn)算。1. 數(shù)據(jù)的邏輯結(jié)構(gòu) 2. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3. 數(shù)據(jù)的運(yùn)算： 檢索、排序、插入、刪除、修改等。

5、 A . 線性結(jié)構(gòu) B . 非線性結(jié)構(gòu)A . 順序存儲(chǔ) B . 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面反映數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)部的組織方式C . 散列結(jié)構(gòu)散列表D . 索引結(jié)構(gòu)索引表 1. 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系。可以用一個(gè)二元組，給出其形式定義為 DataStructure =(D，R) 其中，D是組成數(shù)據(jù)的數(shù)據(jù)元素的有限集合，R是數(shù)據(jù)元素之間的關(guān)系集合。 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)結(jié)構(gòu)又可分為兩大類：線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。按照這種劃分原那么，本書介紹的所有數(shù)據(jù)結(jié)構(gòu)如圖2-1所示。圖2-1 數(shù)據(jù)結(jié)構(gòu)分類

6、2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯上來描述數(shù)據(jù)元素之間的關(guān)系的，是獨(dú)立于計(jì)算機(jī)的。然而討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的處理。因此還需要研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，這就是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 計(jì)算機(jī)的存儲(chǔ)器是由很多存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元有惟一的地址。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)要討論的就是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器上的存儲(chǔ)映像方法。 實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式。一般來說，數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)有四種根本的映像方法。 (1) 順序存儲(chǔ)結(jié)構(gòu)。這種存儲(chǔ)方式主要用于線性數(shù)據(jù)結(jié)構(gòu)，就是把數(shù)據(jù)元素按某種順序放在一塊連續(xù)的存儲(chǔ)單元中。其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)

7、元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中，元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來表達(dá)。 某些非線性數(shù)據(jù)結(jié)構(gòu)也可以采用順序方式存儲(chǔ)，例如完全二叉樹、多維數(shù)組等，具體方法將在后面介紹。 (2) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以把邏輯上相鄰的兩個(gè)元素存放在物理上不相鄰的存儲(chǔ)單元中。即可用一組任意的存儲(chǔ)單元來存儲(chǔ)數(shù)據(jù)元素，這些存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。另外對(duì)于非線性數(shù)據(jù)結(jié)構(gòu)，還可以在線性編址的計(jì)算機(jī)存儲(chǔ)器中表示結(jié)點(diǎn)之間的非線性關(guān)系。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)就是將存放每個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)分為兩局部：一局部存放數(shù)據(jù)元素(稱為數(shù)據(jù)域)：另一局部存放指示存儲(chǔ)地址的指針(稱為指針域)，借助指針表示數(shù)據(jù)元素之間的關(guān)系

8、。 (3) 索引存儲(chǔ)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素可以排成一個(gè)序列：R1、R2、R3、Rn ，每個(gè)數(shù)據(jù)元素Ri在序列里都有對(duì)應(yīng)的位置數(shù)據(jù)i，這就是元素的索引。索引存儲(chǔ)結(jié)構(gòu)就是通過數(shù)據(jù)元素的索引號(hào)i來確定數(shù)據(jù)元素Ri的存儲(chǔ)地址。一般索引存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方法是建立附加的索引表，索引表里第i項(xiàng)的值就是第i個(gè)元素的存儲(chǔ)地址。 (4) 散列存儲(chǔ)結(jié)構(gòu)。這種存儲(chǔ)方法就是在數(shù)據(jù)元素與其在存儲(chǔ)器上的存儲(chǔ)位置之間建立一個(gè)映像關(guān)系F。根據(jù)這個(gè)映像關(guān)系F，某數(shù)據(jù)元素就可以得到它的存儲(chǔ)地址。即D=F(E)，這里E是要存放的數(shù)據(jù)元素，D是該數(shù)據(jù)元素的存儲(chǔ)位置。可見，這種存儲(chǔ)結(jié)構(gòu)的關(guān)鍵是設(shè)計(jì)這個(gè)函數(shù)F。但函數(shù)F不可能解決數(shù)據(jù)存儲(chǔ)

9、中的所有問題，還應(yīng)有一套意外事件的處理方法，它們共同實(shí)現(xiàn)數(shù)據(jù)的散列存儲(chǔ)結(jié)構(gòu)。本書第4章中介紹的哈希表，就是散列存儲(chǔ)結(jié)構(gòu)的一個(gè)實(shí)例。 3. 數(shù)據(jù)的運(yùn)算 數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上的操作，每種數(shù)據(jù)結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。常用的運(yùn)算有檢索、插入、刪除、更新、排序等。運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。 數(shù)據(jù)的運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。討論任何一種數(shù)據(jù)結(jié)構(gòu)時(shí)都離不開對(duì)該結(jié)構(gòu)上的數(shù)據(jù)運(yùn)算及實(shí)現(xiàn)算法的討論。 2.1.2 算法的描述和評(píng)價(jià) 算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。有時(shí)，把運(yùn)算的實(shí)現(xiàn)稱之為算法。運(yùn)算是定義在邏輯結(jié)構(gòu)上的操作，是獨(dú)立于計(jì)算

10、機(jī)的，而運(yùn)算的具體實(shí)現(xiàn)那么是在計(jì)算機(jī)上進(jìn)行的，因此算法要依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 作為算法應(yīng)具有下述的五個(gè)重要特性： (1) 有窮性。一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，且每一步都能在有限的時(shí)間內(nèi)完成。 (2) 確定性。算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性。并且，在任何條件下，算法只有惟一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得到相同的輸出。 (3) 可行性。一個(gè)算法必須是可行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的根本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。 (4) 輸入。一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。 (5) 輸出。一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。 1. 算法的描述 算法需要用一種工具來描述

11、，同時(shí)，算法可有各種描述方法以滿足不同的需求。 常用的描述方法有自然語言描述、偽碼描述、流程圖描述、類PASCAL語言描述、C語言描述等。本書中使用C語言作為描述算法的工具。 2. 算法的評(píng)價(jià) 在算法是“正確性 + 易讀性 + 健壯性的前提下，評(píng)價(jià)算法主要有兩個(gè)指標(biāo)： (1) 時(shí)間復(fù)雜度性：依據(jù)算法編制成程序后，在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間。 (2) 空間復(fù)雜度性：依據(jù)算法編制成程序后，在計(jì)算機(jī)執(zhí)行過程中所需要的最大存儲(chǔ)空間。 要確定實(shí)現(xiàn)算法在運(yùn)行時(shí)所花的時(shí)間和所占用的存儲(chǔ)空間，最直接的方法就是測(cè)試，即將依據(jù)算法編制的程序在計(jì)算機(jī)上運(yùn)行，所得到的結(jié)果就是算法運(yùn)行時(shí)所花的時(shí)間。這種方法有時(shí)也稱為

12、事后統(tǒng)計(jì)的方法。同一算法在不同檔次的計(jì)算機(jī)上運(yùn)行所花的時(shí)間肯定不同，這取決于計(jì)算機(jī)系統(tǒng)的速度。 另外一種方法就是事前分析估算的方法，這是人們常常采用的一種方法，下面將詳細(xì)討論之。 (1) 時(shí)間復(fù)雜度。假定知道算法中每一條語句執(zhí)行一次所花的平均時(shí)間，那么有： 算法運(yùn)行所花的時(shí)間= 語句執(zhí)行一次所花的時(shí)間 語句執(zhí)行次數(shù) 其中語句執(zhí)行一次所花的平均時(shí)間取決于計(jì)算機(jī)系統(tǒng)中硬件、軟件等環(huán)境因素，而一個(gè)算法中語句的執(zhí)行次數(shù)一般來說是確定的。因此，對(duì)于事前分析估算方法，我們討論的目標(biāo)集中在確定語句的執(zhí)行頻度上，即把算法的語句執(zhí)行頻度作為衡量一個(gè)算法時(shí)間復(fù)雜度的依據(jù)。 在實(shí)際分析中，關(guān)注的是頻度的數(shù)量級(jí)，即按

13、重復(fù)執(zhí)行次數(shù)最多的語句確定算法的時(shí)間復(fù)雜度。引入符號(hào)“O來表示這種數(shù)量級(jí)，算法的時(shí)間復(fù)雜度記作： T (n) = O (f ( n ) ) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和函數(shù)f (n) 的增長(zhǎng)率相同，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 按數(shù)量級(jí)遞增次序排列，常見的幾種時(shí)間復(fù)雜度有：O(1)，O(logn)，O(n)，O(nlogn)，O(n2)，O(n3)，O(2n)，這里，n表示問題的規(guī)模。 例如，在以下三個(gè)程序段中： (1) +x；s = 0； T(n)= O(1) (2) for ( i = 1；i=n；+i ) (常量階) +x；s += x； T(n)= O

14、(n) (3) for ( j = 1；j=n； +j ) (線性階) for ( k = 1；k=n；+k ) T(n)= O(n2) +x；s +=x； (平方階) 含根本操作“x增1的語句的頻度分別為1，n和n2 ，那么這三個(gè)程序段的時(shí)間復(fù)雜度分別為O(1)，O(n)和O(n2)，它們分別稱為常量階、線性階和平方階。 需要指出的是，有些算法的根本操作的頻度不僅僅依賴于問題的規(guī)模n，還取決于它所處理的輸入數(shù)據(jù)集的狀態(tài)i，即T(n,i)。對(duì)于這一類算法，一般按每種情況發(fā)生的概率求出其數(shù)學(xué)期望值作為算法的平均時(shí)間復(fù)雜度，或者按最壞情況下根本操作的執(zhí)行頻度得出算法最壞情況下的時(shí)間復(fù)雜度，以此作為

15、該算法的時(shí)間復(fù)雜度。 (2) 空間復(fù)雜度。一個(gè)算法的實(shí)現(xiàn)所占用的存儲(chǔ)空間大致有這樣三個(gè)方面：其一是指令、常數(shù)、變量所占用的存儲(chǔ)空間；其二是輸入數(shù)據(jù)所占用的存儲(chǔ)空間；其三是算法執(zhí)行時(shí)必需的輔助空間。前兩種空間是計(jì)算機(jī)運(yùn)行時(shí)所必須的。因此，把算法在執(zhí)行時(shí)所需的輔助空間的大小作為分析算法空間復(fù)雜度的依據(jù)。 與算法時(shí)間復(fù)雜度的表示一致，也用輔助空間大小的數(shù)量級(jí)來表示算法的空間復(fù)雜度，仍然記為：S(n)=O(f(n)。常見的幾種空間復(fù)雜度有：O(1)，O(n)，O(n2)，O(n3)等。 事實(shí)上，一個(gè)問題的算法實(shí)現(xiàn)，時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互矛盾的，要降低算法的執(zhí)行時(shí)間就要以使用更多的空間為代價(jià)，

16、要節(jié)省空間就可能要以增加算法的執(zhí)行時(shí)間作為代價(jià)，兩者很難兼顧。因此，只能根據(jù)具體情況有所側(cè)重。2.2 線 性 表 2.2.1 線性表的定義及操作 定義2-1 線性表(Linear-list)是n(n0)個(gè)數(shù)據(jù)元素的有限序列。記為： (a1，a2, ., an) 其中，數(shù)據(jù)元素個(gè)數(shù)n稱為表的長(zhǎng)度，n = 0時(shí)，稱此線性表為空表。 線性表的結(jié)構(gòu)僅涉及諸元素的線性相對(duì)位置，即第i個(gè)元素ai處在第i-1個(gè)元素ai-1的后面和第i+1個(gè)元素ai+1的前面，這種位置上的有序性就是一種線性關(guān)系，所以線性表是一種線性結(jié)構(gòu)。 線性表中每個(gè)數(shù)據(jù)元素ai的具體含義，在不同情況下各不相同，它可以是一個(gè)數(shù)，或是一個(gè)符號(hào)

17、，也可以是一頁(yè)書，甚至是其它更復(fù)雜的信息。但在同一個(gè)線性表中的數(shù)據(jù)元素必須具有相同的特性(或者說具有相同的類型)。 線性表的邏輯結(jié)構(gòu)：假設(shè)線性表是非空表，那么第一個(gè)元素a1無前趨，最后一個(gè)元素an無后繼，其它元素ai(1in)均只有一個(gè)直接前驅(qū)ai-1和一個(gè)直接后繼ai+1。 下面給出幾個(gè)線性表的例子： 例2-1 26個(gè)大寫的英文字母表：(A，B，C，.，Z) 例2-2 某校從1996年到2002年各種型號(hào)計(jì)算機(jī)擁有量的變化情況，可以用線性表給出： (200，220，250，300，400，700，1200) 例2-3 某單位職工政治面貌登記表如表2-2所示，每個(gè)職工的情況為一條記錄，它由職工

18、號(hào)、姓名、性別、職稱、工齡、政治面貌六個(gè)數(shù)據(jù)項(xiàng)組成。 在表2-2中，一個(gè)數(shù)據(jù)元素由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表又稱為文件。表2-2 職工政治面貌登記表 職工號(hào)姓 名性 別職 稱工 齡政治面貌 0001 0002 0003 張 忠王 平李 林男女男工程師助 工助 工1222黨員團(tuán)員團(tuán)員 線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長(zhǎng)度可以根據(jù)需要增減，操作也比較靈活方便。線性表的根本操作有以下幾種： (1) INITIATE(L)。初始化操作，設(shè)定一個(gè)空的線性表L。 (2) LENGTH(L)。求表長(zhǎng)，求出線性表L中數(shù)據(jù)元素個(gè)數(shù)。 (3) GET(L，i)

19、。取元素函數(shù)，假設(shè)1iLENGTH(L)， 那么函數(shù)值為給定線性表L中第i個(gè)數(shù)據(jù)元素，否那么為空元素NULL。 (4) PRIOR(L，elm)。求前趨函數(shù)，假設(shè)elm的位序大于1，那么函數(shù)值為elm的前趨，否那么為空元素。 (5) NEXT(L，elm)。求后繼函數(shù)，假設(shè)elm的位序小于LENGTH(L)，那么函數(shù)值為elm的后繼，否那么為空元素。 (6) LOCATE(L，x)。定位函數(shù)，返回元素x在線性表L中的位置。假設(shè)L中有多個(gè)x，那么只返回第一個(gè)x的位置，假設(shè)在L中不存在x，那么返回0。 (7) INSERT(L，i，x)。插入操作，在線性表L中的第i個(gè)位置上插入元素x，運(yùn)算結(jié)果使得

20、線性表的長(zhǎng)度增加1。 (8) DELETE(L，i)。刪除操作，假設(shè)1iLENGTH(L)，刪除給定線性表L中的第i個(gè)數(shù)據(jù)元素，使得線性表的長(zhǎng)度減1。 (9) EMPTY(L)。判空表函數(shù)，假設(shè)L為空表，那么返回布爾值“true，否那么返回布爾值“false。 對(duì)線性表還有一些更為復(fù)雜的操作，如將兩個(gè)線性表合并成一個(gè)線性表；把一個(gè)線性表拆分成兩個(gè)或兩個(gè)以上的線性表；重新復(fù)制一個(gè)線性表；對(duì)線性表中的元素按值的大小重新排序等。這些運(yùn)算都可以通過上述根本運(yùn)算來實(shí)現(xiàn)。 2.2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)內(nèi)可以用不同的方式來表示線性表，其中最簡(jiǎn)單和最常用的方式是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線

21、性表中的元素。圖2-2 線性表順序存儲(chǔ)結(jié)構(gòu)示意圖(設(shè)每個(gè)數(shù)據(jù)元素占有1個(gè)存儲(chǔ)單元) 線性表的順序存儲(chǔ)結(jié)構(gòu)就是將線性表的元素按其邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。 (1) 設(shè)有線性表(a1，a2，.，an)，假設(shè)1個(gè)數(shù)據(jù)元素只占1個(gè)存儲(chǔ)單元，那么這種分配方式如圖2-2所示。 假設(shè)用Loc表示某元素的地址，那么線性表中第i個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為： Loc(ai)= Loc(a1)+(i-1) 其中，Loc(a1)是線性表第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，通常稱做線性表的起始地址或者基地址。 (2) 假設(shè)1個(gè)數(shù)據(jù)元素占d個(gè)存儲(chǔ)單元，那么有 Loc(ai)= Loc(a1)+(i-1)*d Loc(

22、ai+1)= Loc(ai)+ d 可見，線性表中每個(gè)元素的存儲(chǔ)地址是該元素在表中序號(hào)的線性函數(shù)。只要確定了線性表的起始地址，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰來表示線性表中數(shù)據(jù)元素之間相鄰的邏輯關(guān)系。即順序存儲(chǔ)結(jié)構(gòu)線性表的邏輯關(guān)系的存儲(chǔ)是隱含的。 線性表的順序存儲(chǔ)結(jié)構(gòu)通常稱為向量(Vector)?？捎米帜竀來表示，用Vi表示向量V的第i個(gè)分量，設(shè)向量下界為1，上界為線性表的長(zhǎng)度ni=1n，那么可以用此向量來表示長(zhǎng)度為n的線性表。向量的第i個(gè)分量Vi是線性表的第i個(gè)數(shù)據(jù)元素ai在計(jì)算機(jī)內(nèi)存中的映像

23、。 在C語言中，向量即一維數(shù)組，所以可用一維數(shù)組來描述順序存儲(chǔ)結(jié)構(gòu)。#define maxlen 100 typedef int datatype;struct sqlisttp int elemmaxlen; datatype elemmaxlen; int last; ; 其中， maxlen是線性表的最大長(zhǎng)度，它可以根據(jù)實(shí)際需要而修改。這里假設(shè)線性表的數(shù)據(jù)元素是整數(shù)，當(dāng)然也可以根據(jù)需要取其它類型, 甚至還可以是一種結(jié)構(gòu)(即每個(gè)數(shù)據(jù)元素有多個(gè)數(shù)據(jù)項(xiàng))。 數(shù)據(jù)域elem描述了線性表中數(shù)據(jù)元素占用的數(shù)組空間，線性表的各個(gè)元素a1，a2，an依次存放在一維數(shù)組elem的各個(gè)分量elem1，ele

24、m2，elemn中。 數(shù)據(jù)域last指示最后一個(gè)數(shù)據(jù)元素在數(shù)組中的相對(duì)位置。 在這種存儲(chǔ)結(jié)構(gòu)中，線性表的某些操作很容易實(shí)現(xiàn)。如線性表的長(zhǎng)度即為last域的值等。 下面著重討論線性表的插入和刪除兩種操作。 算法2-1 線性表的插入算法。 線性表的當(dāng)前狀態(tài)是(a1，a2，ai-1，ai，an)，要在第i個(gè)位置插入一個(gè)元素x，線性表變?yōu)?a1，a2，ai-1，x，ai，an)。 其實(shí)施步驟為： (1) 將第n至第i個(gè)元素后移一個(gè)存儲(chǔ)位置； (2) 將x插入到第i個(gè)位置； (3) 線性表的長(zhǎng)度加1。.a2a1an.ai+1ai01i-1in-1在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。

25、ai-1.a2a1alast ai+1ai x ai-1. a2 a1 ai ai+1 alast alast ai+1 ai x#define maxlen 100struct sqlisttpint elemmaxlen; /* maxlen=n, elem=a */int last; /* last=length */;sqlisttp v;void insert(sqlisttp v, int i, int x) int k;if (iv.last+1) printf( 插入位置不適宜！n );else if (v.last=maxlen-1)printf( 線性表已滿！n );els

26、e for( k = v.last; k = i; k- )v.elemk+1 = v.elemk; v.elemi = x; v.last+;演示 算法2-2 線性表的刪除算法。 線性表的當(dāng)前狀態(tài)是(a1，a2，ai-1，ai，ai+1，an)，假設(shè)要?jiǎng)h除第i個(gè)元素ai，那么線性表成為(a1，a2，ai-1，ai+1，an)。 具體實(shí)施步驟為： (1) 假設(shè)i值合法，那么將第i+1至第n個(gè)位置上的元素依次向前移動(dòng)一個(gè)存儲(chǔ)單位； (2) 將線性表的長(zhǎng)度減1。.a2a1an.ai+1ai01i-1in-1刪除線性表的第i個(gè)元素，后面所有元素前移。ai-1.a2a1alastai+1ai ai-1

27、. a2 a1 ai ai+1 alast刪除結(jié)點(diǎn)ai ai+1 alast#define maxlen 100struct sqlisttpint elemmaxlen;int last;sqlisttp v;void delete(sqlisttp v, int i) int k;if (iv.last) printf( 刪除位置不適宜！n );演示else for( k = i+1; k next; while ( p!=NULL) & (counter next; counter+; if ( p!= NULL) & (counter = i ) /* 找到,1=in或inext =

28、p-next；p-next = s。 插入結(jié)點(diǎn)s后單鏈表的邏輯狀態(tài)如圖2-7所示。圖2-7 在單鏈表中插入結(jié)點(diǎn)S 算法2-4void insert(NODE *head, int i, int x)NODE *p, *s;int j=0;p = head;while ( p!=NULL) & (j next; j+; if (p = NULL) | (j i-1)printf( i值不合法 n); /* 找不到,in或i data = x; /* */ s - next = p - next; /* */ p - next = s; /* */ 如果事先告之p指針?biāo)傅奈恢?，那么這種在p指針后

29、插入一個(gè)元素算法的時(shí)間復(fù)雜度T(n)=O(1)，否那么平均時(shí)間復(fù)雜度T(n)=O(n)。 3) 單鏈表的刪除 刪除操作和插入操作一樣， (1) 首先要搜索單鏈表以找到指定刪除結(jié)點(diǎn)的前趨結(jié)點(diǎn)(假設(shè)為p)； (2) 然后改變鏈接，即只要將待刪除結(jié)點(diǎn)的指針域內(nèi)容賦予p結(jié)點(diǎn)的指針域即可。 設(shè)有線性表(a1，a2，.，ai-1，ai，ai+1，.，an)，用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，刪除前的邏輯狀態(tài)如圖2-8所示。 刪除元素ai所在的結(jié)點(diǎn)之后，單鏈表的邏輯狀態(tài)如圖2-9所示。圖2-8 帶頭結(jié)點(diǎn)的單鏈表圖2-9 在單鏈表中刪除一個(gè)結(jié)點(diǎn)算法2-5void delete(NODE *head, int i)NOD

30、E *p, *s;int j=0;p = head;while ( p-next != NULL) & (j next; j+; if (p-next = NULL) | (j i-1)printf(“i值不合法 n); /* 找不到,in或i next; p - next = s - next; free(s); 如果事先告之p指針?biāo)傅奈恢?，那么這種在p指針后刪除一個(gè)元素算法的時(shí)間復(fù)雜度T(n)=O(1)，否那么平均時(shí)間復(fù)雜度T(n)=O(n)。 4) 動(dòng)態(tài)建立單鏈表的算法 要對(duì)單鏈表進(jìn)行操作，首先要掌握怎樣建立單鏈表。鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，所需的存儲(chǔ)空間只有在程序執(zhí)行malloc之后，

31、才可能申請(qǐng)到一個(gè)可用結(jié)點(diǎn)空間；free(p)的作用是系統(tǒng)回收一個(gè)結(jié)點(diǎn)，回收后的空間可以備作再次生成結(jié)點(diǎn)時(shí)用。整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共同享用，每個(gè)鏈表占用的空間不需預(yù)先分配劃定，而是由系統(tǒng)應(yīng)需求即時(shí)生成。因此，建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程。即從“空表的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。 動(dòng)態(tài)建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有兩種根本方法，分別適用于不同的場(chǎng)合。可根據(jù)所建鏈表結(jié)點(diǎn)的順序要求選擇采用一種方法。 單鏈表建立方法一：反向建立鏈表頭插法。 思想：假設(shè)線性表的元素已順序存放在一維數(shù)組AN中，建表方法是從線性表的最后一個(gè)元素開始，從后向前依次插入到當(dāng)前鏈

32、表的第一個(gè)結(jié)點(diǎn)之前。算法2-6#define N m /* m為鏈表中數(shù)據(jù)元素的個(gè)數(shù),如m=10 */int AN;NODE * creatlink1( )NODE *head, *s;int i;head = (NODE *)malloc(sizeof(NODE); /*生成頭結(jié)點(diǎn)*/head - next = NULL; /* 置空表 */for(i=N-1; i=0; i-) /* 插入10個(gè)數(shù)據(jù) */ s = (NODE *)malloc(sizeof(NODE); /*生成新結(jié)點(diǎn)*/ s - data = Ai; /*將輸入數(shù)據(jù)放入新結(jié)點(diǎn)數(shù)據(jù)域*/ s - next = head -

33、 next; /*新結(jié)點(diǎn)與原首結(jié)點(diǎn)鏈接*/ head - next = s; /* 將新結(jié)點(diǎn)插入到表頭 */ return head; /* 返回單鏈表頭指針 */算法的時(shí)間復(fù)雜度為：T(n)=O(n) 單鏈表建立方法二：正向建立單鏈表尾插法。 思想：依次讀入線性表的元素，從前往后依次將元素插入到當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)之后。圖B 新結(jié)點(diǎn)*s插入到單鏈表head的尾上算法2-7NODE * creatlink2( )NODE *head, *p, *s;int num;head = (NODE *)malloc(sizeof(NODE); /*生成頭結(jié)點(diǎn)*/scanf(“%d, &num); /

34、* 讀入第一個(gè)結(jié)點(diǎn)值*/p = head; /* 頭指針=尾指針 */while (num!=0) /* 輸入為0為輸入結(jié)束符*/ s = (NODE *)malloc(sizeof(NODE);/*生成新結(jié)點(diǎn)*/ s - data = num; /* 新結(jié)點(diǎn)上填入輸入值 */ p - next = s; /* 新結(jié)點(diǎn)*s插入到尾結(jié)點(diǎn)*p之后 */ p = s; /* 尾指針p指向新的表尾 */ scanf(“%d, &num); /* 讀入下一個(gè)結(jié)點(diǎn)值 */ p - next = NULL; /* 將尾結(jié)點(diǎn)的指針置空 */return head; /* 返回單鏈表頭指針 */算法的時(shí)間復(fù)雜度

35、：T(n)=O(n) 3. 線性鏈表算法例如 例2-5 求不帶頭結(jié)點(diǎn)的頭指針為head的單鏈表中的結(jié)點(diǎn)數(shù)目。 解： int length(NODE *head) NODE *p; int j; p = head; j = 0; while ( p != NULL ) p = p - next; j+; return j;算法的平均時(shí)間復(fù)雜度：T(n)=O(n) 例2-6 設(shè)計(jì)算法：將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，使得A表中含有原表中序號(hào)為奇數(shù)的元素，B表中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序。解：void disA(NODE *A, NODE *B)NODE

36、*r, *p, *q;B = (NODE *)malloc(sizeof(NODE); /*建立單鏈表B的頭結(jié)點(diǎn)*/r = B;p = A-next;while (p!=NULL) & (p-next!=NULL) q = p-next; p-next = q-next; r-next = q; r = q; p = p-next;r-next = NULL;p-next = NULL; 例2-7 兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表A、B分別表示兩個(gè)集合，其元素遞增有序。試設(shè)計(jì)算法求出A與B的交集C。要求C另外開辟存儲(chǔ)空間，并同樣以元素值遞增的帶頭結(jié)點(diǎn)的單鏈表形式存儲(chǔ)。解：void intersectio

37、nset(NODE *A, NODE *B, NODE *C)NODE *r, *p, *q, *s;C = (NODE *)malloc(sizeof(NODE);r = C;p = A;q = B;while (p!=NULL) & (q!=NULL) if (p-data data) p = p-next;else if (p-data q-data)q = q-next;else if (p-data = q-data) s = (NODE *)malloc(sizeof(NODE); s-data = p-data; r-next = s; r = s; p = p-next; q

38、= q-next;r-next = NULL; 2.2.4 循環(huán)鏈表和雙向鏈表 1. 循環(huán)鏈表 如果鏈表最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這樣的鏈表稱為循環(huán)鏈表。 這樣，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)，其邏輯狀態(tài)圖如圖2-10。圖2-10 循環(huán)單鏈表 循環(huán)鏈表一般設(shè)表頭結(jié)點(diǎn)，這樣鏈表將永不為空，這將使空表和非空表的邏輯狀態(tài)及運(yùn)算統(tǒng)一起來。 循環(huán)鏈表的操作和線性鏈表根本一致，差異僅在于算法中的循環(huán)條件不是p或p-next是否為空，而是它們是否等于頭指針。 與單鏈表比較，循環(huán)鏈表有以下特點(diǎn)： (1) 在循環(huán)單鏈表中，從表中任何一個(gè)結(jié)點(diǎn)出發(fā)都能訪問到其它所有的結(jié)點(diǎn)；而單鏈表

39、一般把頭指針作為入口點(diǎn)，從某一結(jié)點(diǎn)出發(fā)，只能訪問到其所有后繼結(jié)點(diǎn)。 (2) 循環(huán)單鏈表的空表判定條件是： head-next=head。 2雙向鏈表 前面討論的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中只有一個(gè)指示直接后繼的指針域，所以從某結(jié)點(diǎn)出發(fā)只能順指針往后查找其它結(jié)點(diǎn)。假設(shè)要查找結(jié)點(diǎn)的直接前趨，那么應(yīng)從頭指針出發(fā)(或在循環(huán)單鏈表中從p結(jié)點(diǎn)出發(fā))一直往后找，直到結(jié)點(diǎn)q滿足q-next=p，那么q是p的前趨結(jié)點(diǎn)。為克服鏈表這種單向性的缺點(diǎn)，為有更大的靈活性來操作線性鏈表，可采用雙向鏈表存儲(chǔ)結(jié)構(gòu)。 在每個(gè)結(jié)點(diǎn)上增加另一個(gè)指向線性表中每個(gè)元素的前趨結(jié)點(diǎn)的指針域prior，就得到雙向鏈表。其結(jié)點(diǎn)的結(jié)構(gòu)如圖2-11所示。 其中

40、，prior是指向前趨結(jié)點(diǎn)的指針域；data是數(shù)據(jù)域；next是指向后繼結(jié)點(diǎn)的指針域。 圖2-11 雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)圖2-12 帶頭結(jié)點(diǎn)的空雙向鏈表 和循環(huán)單鏈表類似，也可將雙向鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來組成雙向循環(huán)鏈表。 雙向鏈表的幾種不同狀態(tài)如圖2-12，圖2-13，圖2-14和圖2-15所示。圖2-13 帶頭結(jié)點(diǎn)的非空雙向鏈表 圖2-14 空的雙向循環(huán)鏈表 圖2-15 非空雙向循環(huán)鏈表 在非空雙向循環(huán)鏈表中，設(shè)p是指向鏈表中任一結(jié)點(diǎn)的指針，那么有： p-next-prior = p-prior-next = p 這個(gè)等式反映了這種鏈表的本質(zhì)，在此鏈表上進(jìn)行插入或刪除操作是十分方便的。雙

41、向鏈表雖然多花了存儲(chǔ)空間，但卻換得了操作上的更大靈活性。 雙向鏈表的運(yùn)算如LENGTH(Head)，GET(Head, i)，LOCATE(Head, x)等操作，僅涉及一個(gè)方向的指針，操作類似單鏈表。但插入INSERT、刪除DELETE時(shí)要同時(shí)修改兩個(gè)方向的指針。 (1) 插入。在鏈表中第i個(gè)結(jié)點(diǎn)前插入元素x。 步驟：首先搜索插入位置，找到第i個(gè)結(jié)點(diǎn)用指p指示，然后申請(qǐng)新結(jié)點(diǎn)并改變鏈接。插入結(jié)點(diǎn)時(shí)指針變化狀況如圖2-16所示。圖2-16 在雙向鏈表中插入結(jié)點(diǎn) 插入時(shí)相關(guān)操作序列為： s-prior = p-prior; (p-prior)-next = s; s-next = p; p-pr

42、ior = s。 (2) 刪除。在鏈表中刪除第i個(gè)結(jié)點(diǎn)。 步驟：首先找到刪除位置P，然后改變鏈接，最后釋放被刪結(jié)點(diǎn)P。刪除結(jié)點(diǎn)時(shí)指針變化狀況如圖2-17所示。 圖2-17 在雙向鏈表中刪除結(jié)點(diǎn)刪除時(shí)相關(guān)操作序列為： (p-prior)-next = p-next; (p-next)-prior = p-prior; 例2-8 設(shè)計(jì)算法：判斷帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表head按元素值是否對(duì)稱(所謂對(duì)稱，就是在線性表中a1=an，a2=an-1，.)。 int symmetry(DNODE *head) DNODE *p, *q; p = head-next; /* p指向首元素 */ q = hea

43、d-prior; /* q指向尾元素 */ while (p-data = q-data) if (p = q) | (p-next = q) /* 0個(gè)或1個(gè)元素*/ return 1;else p = p-next; /* p向左掃描 */ q = q-prior; /* q向右掃描 */ return 0;2.3 棧 和 隊(duì) 列 棧(stack)和隊(duì)列(queue)是經(jīng)常遇到的兩種數(shù)據(jù)結(jié)構(gòu)，它們都是特殊情況下的線性表。前面介紹的線性表的向量及鏈表存儲(chǔ)，進(jìn)行插入、刪除時(shí)是比較麻煩的。向量導(dǎo)致數(shù)據(jù)元素的大量移動(dòng)，而鏈表中那么要順鏈尋找指定位置。如果能夠把插入、刪除操作都限制在線性表的端部進(jìn)行

44、，那么運(yùn)算效率可以大大提高。本節(jié)要討論的就是這種限制存取位置的線性表?xiàng)：完?duì)列。 2.3.1 棧也稱堆棧 1棧的定義 棧stack是限定只能在表的同一端進(jìn)行插入和刪除操作的線性表。其中允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，而表中固定的一端稱為棧底(bottom)。棧中元素個(gè)數(shù)為零時(shí)稱為空棧。 由于棧中元素的插入和刪除只能在棧頂進(jìn)行，所以總是后進(jìn)棧的元素先出來，即棧具有后進(jìn)先出(Last In First Out，縮寫為L(zhǎng)IFO)的特性，故棧又稱為“后進(jìn)先出表(LIFO表)。 在日常生活中，有不少類似棧的例子。例如食堂中盤子的疊放，如果限定一次疊放一只，那么每次都是疊放到原來一疊盤子的頂

45、上，這相當(dāng)于入棧操作；而當(dāng)取用一只盤子時(shí)，也是從這一疊盤子的頂上取用，這相當(dāng)于出棧操作。 棧的五種根本運(yùn)算： (1) Inistack(S)。初始化棧S為空棧。 (2) Empty(S)。判定S是否為空棧。假設(shè)S是空棧那么返回值為真(Ture)，否那么返回值為假(False)。 (3) Push(S，x)。進(jìn)棧操作。在棧S的棧頂插入數(shù)據(jù)元素x。 (4) Pop(S)。出棧操作。假設(shè)棧S不是空棧，那么刪除棧頂元素。 (5) Gettop(S)。取棧頂元素。它只讀取棧頂元素，不改變棧中的內(nèi)容。 圖2-18 三個(gè)元素可能的出棧序列例2-9 有三個(gè)元素的進(jìn)棧序列是1，2，3，舉出此三個(gè)元素可能的出棧序

46、列，并寫出相應(yīng)的進(jìn)棧和出棧操作序列如圖2-18所示(假設(shè)以I和O表示進(jìn)棧和出棧操作)。 2棧的表示和實(shí)現(xiàn) 因?yàn)闂Ｊ蔷€性表的一種特例，所以線性表的存儲(chǔ)結(jié)構(gòu)對(duì)它都適用。一般稱采用順序存儲(chǔ)結(jié)構(gòu)的棧為順序棧；采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧為鏈棧。 1) 棧的順序存儲(chǔ)結(jié)構(gòu)順序棧 利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)指針top指示棧頂元素的當(dāng)前位置?？諚５臈ｍ斨羔樦禐?1。設(shè)用數(shù)組StackMAXSIZE表示棧，那么對(duì)非空棧，Stack0為最早進(jìn)入棧的元素，Stacktop為最遲進(jìn)入棧的元素，即棧頂元素。 當(dāng)top= MAXSIZE-1時(shí)意為棧滿，此時(shí)假設(shè)有元素入棧那么將產(chǎn)生“數(shù)組越界的

47、錯(cuò)誤，稱為棧的“上溢(overflow)； 反之，top= -1意為?？?，假設(shè)此時(shí)再作退棧操作，那么發(fā)生“下溢(underflow)。 圖2-19展示了順序棧中數(shù)據(jù)元素和棧頂指針之間的對(duì)應(yīng)關(guān)系，設(shè) MAXSIZE =m。圖2-19 棧頂指針和棧中元素之間的關(guān)系 順序棧的C語言描述如下： typedef int datatype；#define MAXSIZE m #define maxsize 64int stackMAXSIZE; typedef struct int top；int top=-1; datatype datamaxsize； seqstack； seqstack *s;注意

48、:上述定義中,假設(shè)數(shù)據(jù)元素的類型為整型，m為棧中數(shù)據(jù)元素個(gè)數(shù)的最大可能值。 通常對(duì)棧進(jìn)行的運(yùn)算是進(jìn)棧和出棧，這些運(yùn)算都比較簡(jiǎn)單，下面給出進(jìn)棧和出棧操作的實(shí)現(xiàn)算法。算法2-8 進(jìn)棧算法。步驟：step1. 判斷棧是否已滿，假設(shè)滿那么輸出棧溢出信息，并停 止執(zhí)行；否那么，執(zhí)行step2。step2. 棧頂指針top后移。step3. 在棧頂指針?biāo)府?dāng)前位置插入元素x。 #define MAXSIZE m int stackMAXSIZE; int top=-1;void push(int x)if (top = MAXSIZE-1) printf(棧滿溢出 n); exit(1);else top

49、+; stacktop=x;算法2-9 出棧算法。步驟：step1. 判斷棧是否為空棧，假設(shè)為空那么輸出棧下溢信 息，并停止執(zhí)行；否那么，執(zhí)行step2。step2. 彈出(刪除)棧頂元素。step3. 棧頂指針top下移。 #define MAXSIZE m int stackMAXSIZE; int top;int pop( ) int x;if (top = -1) printf(?？找绯?n); exit(1); else x=stacktop; top-;return x; 棧的使用非常廣泛，常常會(huì)出現(xiàn)在一個(gè)程序中需要同時(shí)使用多個(gè)棧的情形，為了不因棧上溢而產(chǎn)生錯(cuò)誤中斷，必須給每個(gè)棧預(yù)

50、分一個(gè)較大的空間，但這并不容易做到，因?yàn)楦鱾€(gè)棧實(shí)際所用空間很難估計(jì)?？紤]到在實(shí)際進(jìn)程中，當(dāng)一個(gè)棧發(fā)生上溢時(shí)，其它棧可能還留有很多空間，所以可設(shè)法動(dòng)態(tài)地加以調(diào)整，以到達(dá)多個(gè)棧共享內(nèi)存時(shí)，只要有一個(gè)棧未滿，其它任何棧的入棧操作均不會(huì)發(fā)生上溢。 圖2-20 兩個(gè)棧共享空間示意圖 現(xiàn)在以兩個(gè)棧為例，討論其共享內(nèi)存時(shí)的順序分配方法。 當(dāng)有兩個(gè)棧共享大小為m的內(nèi)存空間時(shí)，可以把兩個(gè)棧的棧底分別設(shè)在給定內(nèi)存空間的兩端。然后，各自棧頂向中間伸展，僅當(dāng)兩個(gè)棧頂相遇時(shí)才發(fā)生溢出。這種分配方式，在每個(gè)棧的動(dòng)態(tài)變化過程中，使每個(gè)?？衫玫淖畲罂臻g均有可能超過m/2。這種分配方法如圖2-20所示。 2) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)

51、構(gòu)鏈棧 采用順序存儲(chǔ)結(jié)構(gòu)，對(duì)于一個(gè)棧、兩個(gè)?？梢郧宄匀坏乇磉_(dá)，但當(dāng)遇到多個(gè)棧共享空間的問題或棧的最大容量事先不能估計(jì)時(shí)，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是有效的方法。圖2-21 鏈棧示意圖 類似于單鏈表，鏈棧的C語言描述如下： struct snode int data; struct snode *link; ; typedef struct snode SNODE; 棧頂指針仍是top，其類型為SNODE *，相當(dāng)于單鏈表的頭指針，可惟一確定一個(gè)鏈棧。當(dāng)top=NULL，表示一個(gè)空鏈棧。鏈棧的邏輯示意圖如圖2-21所示。 SNODE ； 對(duì)于鏈棧，不會(huì)產(chǎn)生單個(gè)棧滿而其余棧空的情形，只有當(dāng)整個(gè)可用空間都被

52、占滿，malloc函數(shù)無法實(shí)現(xiàn)時(shí)才會(huì)發(fā)生上溢。因此多個(gè)鏈棧共享空間也就是自然的事了。 鏈棧的出、入棧操作類似于單鏈表，下面給出相應(yīng)的算法。 算法2-10 進(jìn)棧操作push(stack,x)。步驟：step1. 申請(qǐng)一鏈棧結(jié)點(diǎn)，假設(shè)無可用內(nèi)存空間，那么表示 棧滿，否那么執(zhí)行step2；step2. 在top所指結(jié)點(diǎn)之前插入新結(jié)點(diǎn)，并將top指向 新申請(qǐng)的結(jié)點(diǎn)。void push(SNODE *top, int x)SNODE *p;p = (SNODE *)malloc(sizeof(SNODE); if (p = NULL) printf( 內(nèi)存中無可用空 間，棧溢出! n); exit(1)

53、;else p-data = x; p-link = top; top = p;算法2-11 出棧操作pop(stack)。步驟：step1. 假設(shè)判斷鏈棧為空，那么輸出棧溢出信息；否 那么執(zhí)行step2；step2. 刪除top所指結(jié)點(diǎn)，并使top指向被刪結(jié)點(diǎn) 的后繼結(jié)點(diǎn)。void pop(SNODE *top)int x; SNODE *p;if (top = NULL) printf(?？找绯?下溢) n); exit(1);else p = top; top = top-link; x = p-data; free(p); 2.3.2 隊(duì)列 隊(duì)列(Queue)是一種先進(jìn)先出(FIFO，

54、First In First Out)的線性表。它只允許在表的一端進(jìn)行插入元素操作，而在另一端進(jìn)行刪除元素操作。 這和日常生活中的排隊(duì)是一致的，最早進(jìn)入隊(duì)列的元素最早離開。在隊(duì)列中，允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端那么稱為隊(duì)頭(front)。如圖2-22所示。圖2-22 隊(duì)列的示意圖隊(duì)列的五種根本運(yùn)算：(1) Iniqueue(Queue)。初始化隊(duì)列Queue，即置Queue為空隊(duì)列。(2) Empty(Queue)。判定隊(duì)列Queue是否為空。假設(shè)Queue是空隊(duì)列那么返回值為真(True)，否那么返回值為假(False)。(3) Addqueue(Queue，x)。入隊(duì)

55、操作。假設(shè)隊(duì)列未滿，那么在Queue的隊(duì)尾插入元素x。(4) Delqueue(Queue)。出隊(duì)操作。假設(shè)隊(duì)列非空，那么將Queue的隊(duì)頭元素刪除。(5) Getheadqueue(Queue)。讀取隊(duì)列Queue的隊(duì)頭元素，不改變隊(duì)列中的內(nèi)容。 1隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 用一組地址連續(xù)的空間存放隊(duì)列中的元素。即用一個(gè)能容納最大容量元素的向量，另外還需要兩個(gè)指針(front和rear)分別指示隊(duì)頭元素和隊(duì)尾元素的存儲(chǔ)位置。順序隊(duì)列的C語言描述如下：typedef int datatype；#define MAXSIZE m #define MAXSIZE m int queueMAXSIZE；

56、typedef struct int front，rear；int front, rear； datatype datamaxsize； sequeue； sequeue *sq； 上面定義中，假設(shè)數(shù)據(jù)元素的類型為整型，m為隊(duì)列中數(shù)據(jù)元素個(gè)數(shù)的最大可能值。 約定：隊(duì)頭指針front指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素在隊(duì)列中的當(dāng)前位置。假設(shè)不作上述約定，會(huì)出現(xiàn)： 在實(shí)現(xiàn)出隊(duì)列的操作時(shí)，第一個(gè)元素和其它元素的處理方法不一致，如 front+； 讀第一個(gè)元素： x = queuefront； front+； 讀其它元素：x = queuefront；front+； 隊(duì)列空的

57、判別條件復(fù)雜化。 圖2-23展示了順序結(jié)構(gòu)隊(duì)列中頭、尾指針的變化情況。一開始時(shí)，隊(duì)列的頭、尾指針都指向向量空間下界的前一個(gè)位置，在此設(shè)為-1。假設(shè)不考慮溢出，那么 入隊(duì)操作為： rear+；/* 尾指針加1*/ queuerear = x； /* x入隊(duì)*/ 出隊(duì)操作為： front+； /* 頭指針加1*/ 在順序結(jié)構(gòu)隊(duì)列中，值得考慮的是隊(duì)列滿(即上溢)的判定條件是什么？ 假設(shè)當(dāng)前隊(duì)列處在圖2-23中(d)的狀態(tài)，即MAXSIZE=6，rear=5，front=3，顯然不能作入隊(duì)列操作，因?yàn)閞ear+1 MAXSIZE-1，出現(xiàn)上溢，但隊(duì)列中還有空間，我們稱這種現(xiàn)象為“假溢出。 圖2-23

58、順序隊(duì)列中頭、尾指針變化(設(shè)MAXSIZE=m=6 ) 解決“假溢出的方法有兩種： (1) 將全部元素向前移動(dòng)直至隊(duì)頭指針front為-1，使隊(duì)列的第一個(gè)元素重新位于queue0。這種方案是比較費(fèi)時(shí)的。 (2) 設(shè)想queue0接在queueMAXSIZE-1之后，使一維數(shù)組成為一個(gè)首尾相接的環(huán)，即如果rear+1=maxsize，那么令rear=0，這就是循環(huán)隊(duì)列的概念。循環(huán)隊(duì)列如圖2-24所示。 在循環(huán)隊(duì)列中，需要解決兩類問題，即 1隊(duì)頭指針及隊(duì)尾指針的后移； 2如何判定隊(duì)列的空與滿。 圖2-24 循環(huán)隊(duì)列示意圖 隊(duì)頭指針和隊(duì)尾指針的后移實(shí)際上就是如何從隊(duì)列的第maxsize-1個(gè)位置移到

59、第0個(gè)位置。這很容易地通過“求模運(yùn)算實(shí)現(xiàn)。 1對(duì)于隊(duì)頭指針front： if (front + 1 = maxsize) front = 0 else front = front + 1 或者 front = (front + 1)% maxsize2對(duì)于隊(duì)尾指針rear： if (rear + 1 = maxsize) rear = 0 else rear = rear + 1 或者： rear =(rear + 1)% maxsize 在循環(huán)隊(duì)列中，習(xí)慣上我們采用保存一個(gè)空閑位置來區(qū)別空和滿。 1隊(duì)空時(shí)，采用的判定條件為： rear=front 2隊(duì)滿時(shí)，以隊(duì)尾指針加1等于隊(duì)頭指針作為判定

60、條件尾追頭，即 front = (rear+1)% maxsize 當(dāng)隊(duì)列滿時(shí)，隊(duì)列中實(shí)際上只有maxsize-1個(gè)元素。 假假設(shè)想利用全部循環(huán)隊(duì)列中的maxsize個(gè)存儲(chǔ)位置，此時(shí)隊(duì)列滿時(shí)front=rear與隊(duì)列空時(shí)的關(guān)系相同，因而需要另外設(shè)一標(biāo)志tag來區(qū)別隊(duì)列的空和滿。 (1)初始時(shí)front=rear，說明隊(duì)列空，tag=0置隊(duì)列空標(biāo)志； (2)假設(shè)隨著元素的入隊(duì)再次滿足條件front=rear，說明隊(duì)列滿，tag=1置隊(duì)列滿標(biāo)志。 由于另設(shè)標(biāo)志增加了判別標(biāo)志所需的時(shí)間，通常不采用此法。而前一種方法雖留有一個(gè)空額損失了一個(gè)空間，但防止了由于判別另設(shè)標(biāo)志造成的時(shí)間損失，加快了算法的執(zhí)行