It計(jì)算機(jī)課件 第02章-線性表I

第1章概論

數(shù)據(jù)結(jié)構(gòu)討論的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)方式

以及相關(guān)操作的實(shí)現(xiàn)等問(wèn)題，為學(xué)習(xí)后續(xù)專業(yè)課程

打下基礎(chǔ)。本章講述數(shù)據(jù)結(jié)構(gòu)的基本概念及相關(guān)術(shù)

語(yǔ)，介紹數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型之間

的聯(lián)系，介紹了算法的特點(diǎn)及算法的時(shí)間與空間復(fù)

雜性。

1」數(shù)據(jù)結(jié)構(gòu)

1.1.1數(shù)據(jù)結(jié)構(gòu)

隨著計(jì)算機(jī)軟、硬件的發(fā)展，計(jì)算機(jī)的應(yīng)用范

圍在不斷擴(kuò)大，計(jì)算機(jī)所處理的數(shù)據(jù)的數(shù)量也在不

斷擴(kuò)大，計(jì)算機(jī)所處理的數(shù)據(jù)已不再是單純的數(shù)值

數(shù)據(jù)，而更多的是非數(shù)值數(shù)據(jù)。

需要處理的數(shù)據(jù)并不是雜亂無(wú)章的，它們一定

有內(nèi)在的聯(lián)系，只有弄清楚它們之間的本質(zhì)的聯(lián)系,

才能使用計(jì)算機(jī)對(duì)大量的數(shù)據(jù)進(jìn)行有效的處理。

某電信公司的市話用戶信息表格如下圖所示:

用戶住址

序號(hào)用戶名電話號(hào)碼

街道名門牌號(hào)

00001萬(wàn)方林3800235北京西路1659

r--------A---------―________._>_、一一一，1-------_1

這里序號(hào)、用戶名、電話號(hào)碼等項(xiàng)稱為基本項(xiàng)，它

是有獨(dú)立意義的最小標(biāo)識(shí)單位，而用戶住址稱為組合項(xiàng)，

組合項(xiàng)是由一個(gè)或多個(gè)基本項(xiàng)或組合項(xiàng)組成，是有獨(dú)立

意義的標(biāo)識(shí)單位，每一行稱為一個(gè)結(jié)點(diǎn)，每一個(gè)組合項(xiàng)

稱為一個(gè)字段。

使用計(jì)算機(jī)處理用戶信息表中的數(shù)據(jù)時(shí)，必須弄清楚

下面3個(gè)問(wèn)題：

1數(shù)據(jù)的邏輯結(jié)構(gòu)

這些數(shù)據(jù)之間有什么樣的內(nèi)在聯(lián)系？

除最前和最后兩個(gè)結(jié)點(diǎn)之外，表中所有其它的結(jié)點(diǎn)

都有且僅有一個(gè)和它相鄰位于它之前的一個(gè)結(jié)點(diǎn)，也有

且僅有一個(gè)和它相鄰位于它之后的一個(gè)結(jié)點(diǎn)，這些就是

用戶信息表的邏輯結(jié)構(gòu)。

2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

將用戶信息表中的所有結(jié)點(diǎn)存入計(jì)算機(jī)時(shí)，就必須

考慮存儲(chǔ)結(jié)構(gòu)，使用C語(yǔ)言進(jìn)行設(shè)計(jì)時(shí)，常見的方式是

用一個(gè)結(jié)構(gòu)數(shù)組來(lái)存儲(chǔ)整個(gè)用戶信息表，每一個(gè)數(shù)組元

素是一個(gè)結(jié)構(gòu)，它對(duì)應(yīng)于用戶信息表中的一個(gè)結(jié)點(diǎn)。數(shù)

據(jù)在計(jì)算機(jī)的存儲(chǔ)方式稱為存儲(chǔ)結(jié)構(gòu)。

3數(shù)據(jù)的運(yùn)算集合

數(shù)據(jù)處理必涉及到相關(guān)的運(yùn)算，在上述用戶信息表

中，可以有刪除一個(gè)用戶、增加一個(gè)用戶和查找某個(gè)用

戶等操作。應(yīng)該明確指明這些操作的含義。比如刪除操

作，是刪除序號(hào)為5的用戶還是刪除用戶名為王三的用

戶是應(yīng)該明確定義的，如果需要可以定義兩個(gè)不同的刪

除操作，為一批數(shù)據(jù)定義的所有運(yùn)算（或稱操作）構(gòu)成

一個(gè)運(yùn)算（操作）集合。

對(duì)待處理的數(shù)據(jù)，只有分析清楚上面3個(gè)方面的問(wèn)

題，才能進(jìn)行有效的處理！

數(shù)據(jù)結(jié)構(gòu)就是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù),

使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在

這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合。

1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)

例如，有5個(gè)人,分別記為a,b,c,d,e，其中a是b的父親,

b是c的父親，c是d的父親,d是e的父親，如果只討論他們

之間所存在的父子關(guān)系，則可以用下面的二元組形式化

地予以表達(dá)。

B=(K,R)

其中：K={a,b,c,d,e}

R={r}

r={<a,b>,<b,c>,<c,d>,<d,e>}

邏輯結(jié)構(gòu)的圖形表示方式，對(duì)K中的每個(gè)結(jié)點(diǎn)I用一

個(gè)方框表示，而結(jié)點(diǎn)之間的關(guān)系用帶箭頭的線段表示,

這5人之間的邏輯結(jié)構(gòu)用圖形的方式表達(dá)如下圖所示。

若女產(chǎn)（kj￡R,<kj,kj>er,貝1稱％是％的相對(duì)

于關(guān)系r的前驅(qū)結(jié)點(diǎn)，耳是與的相對(duì)于關(guān)系r的后繼結(jié)點(diǎn)，

因?yàn)橐话阒挥懻摼哂幸环N關(guān)系的邏輯結(jié)構(gòu)，即R={r},

所以簡(jiǎn)稱％是%前驅(qū)，％是K的后繼。如果某個(gè)結(jié)點(diǎn)沒有

前驅(qū)結(jié)點(diǎn)，稱之為開始結(jié)點(diǎn)；如果某個(gè)結(jié)點(diǎn)沒有后繼

結(jié)點(diǎn)，稱之為終端結(jié)點(diǎn)；既不是開始結(jié)點(diǎn)也不是終端

結(jié)點(diǎn)的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。

14,3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的，它與數(shù)據(jù)在

計(jì)算機(jī)中的存儲(chǔ)無(wú)關(guān)，要對(duì)數(shù)據(jù)進(jìn)行處理，就必須將

數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中。如果將數(shù)據(jù)在計(jì)算機(jī)中無(wú)規(guī)律

地存儲(chǔ)，那么在處理時(shí)是非常糟的，是沒有用的。試

想一下，如果一本英漢字典中的單詞是隨意編排的，

這本字典誰(shuí)會(huì)用！

對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)B=(K,R),必須建立從結(jié)點(diǎn)

集合到計(jì)算機(jī)某個(gè)存儲(chǔ)區(qū)域M的一個(gè)映象，這個(gè)映象

要直接或間接地表達(dá)結(jié)點(diǎn)之間的關(guān)系R。數(shù)據(jù)在計(jì)算

機(jī)中的存儲(chǔ)方式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有4種o

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有4種o存儲(chǔ)地址M

1001

1順序存儲(chǔ)

1002

順序存儲(chǔ)通常用于存儲(chǔ)具有線性結(jié)構(gòu)水1003

邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在連續(xù)存儲(chǔ)區(qū)域M的1004

儲(chǔ)單元中，使得邏輯相鄰的結(jié)點(diǎn)一定是物靈1005k5

1006

對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)B=(K,R)1007%

1008%

其中K={1＜］,］＜2，］＜3，］＜4，］＜5太6水7，］＜8，%}

1009%

R={r}

r={<kpk2>,<k2,k3>?<k3,k4>?<k4,k5>?<k59k6>?<k6?k7>?<k7?

卜8>,<卜8，%>}

它的順序存儲(chǔ)方式如圖所示

2鏈?zhǔn)酱鎯?chǔ)存儲(chǔ)地址infonext

鏈?zhǔn)酱鎯?chǔ)方式是給每個(gè)結(jié)點(diǎn)附加一/

個(gè)結(jié)點(diǎn)的指針?biāo)傅氖窃摻Y(jié)點(diǎn)的后繼的培

為一個(gè)結(jié)點(diǎn)可能有多個(gè)后繼，所以指針寫

指針，也可以是一個(gè)多個(gè)指針。

例，數(shù)據(jù)的邏輯結(jié)構(gòu)B=(K,R)

其中K={kpk2?k39k49k5}

R={r}

R={vkpk2>?<k2?k3>?<k3,k4>?<k4?k5>}

這是一個(gè)線性結(jié)構(gòu)，它的鏈?zhǔn)酱鎯?chǔ)如圖所示。

3索引存儲(chǔ)

在線性結(jié)構(gòu)中，設(shè)開始結(jié)點(diǎn)的索引號(hào)為1,其它結(jié)

點(diǎn)的索引號(hào)等于其前繼結(jié)點(diǎn)的索引號(hào)加1,則每一個(gè)結(jié)

點(diǎn)都有唯一的索引號(hào)，索引號(hào)就是根據(jù)結(jié)點(diǎn)的索引號(hào)

確定該結(jié)點(diǎn)的存儲(chǔ)地址。

4散列存儲(chǔ)

散列存儲(chǔ)的思想是構(gòu)造一個(gè)從集合K到存儲(chǔ)區(qū)域M

的一個(gè)函數(shù)h,該函數(shù)的定義域?yàn)镵,值域?yàn)镸,K中的

每個(gè)結(jié)點(diǎn)(在計(jì)算機(jī)中的存儲(chǔ)地址由h(k)確定。

114數(shù)據(jù)的運(yùn)算集合

對(duì)于一批數(shù)據(jù)，數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏

輯結(jié)構(gòu)之上的，而運(yùn)算的具體實(shí)現(xiàn)就依賴于數(shù)據(jù)的存

儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的運(yùn)算集合要視情況而定，一般而言，數(shù)據(jù)

的運(yùn)算包括插入、刪除、檢索、輸出、排序等。

插入：在一個(gè)結(jié)構(gòu)中增加一個(gè)新的結(jié)點(diǎn)。

刪除：在一個(gè)結(jié)構(gòu)刪除一個(gè)結(jié)點(diǎn)。

檢索：在一個(gè)結(jié)構(gòu)中查找滿足條件的結(jié)點(diǎn)。

輸出：將一個(gè)結(jié)構(gòu)中所有結(jié)點(diǎn)的值打印、輸出。

排序：將一個(gè)結(jié)構(gòu)中所有結(jié)點(diǎn)按某種順序重新排列。

L2數(shù)據(jù)類型和抽象數(shù)據(jù)類型

在程序設(shè)計(jì)中，數(shù)據(jù)和運(yùn)算是兩個(gè)不可缺少的因

素。所有的程序設(shè)計(jì)活動(dòng)都是圍繞著數(shù)據(jù)和其上的相

關(guān)運(yùn)算而進(jìn)行的。從機(jī)器指令、匯編語(yǔ)言中的數(shù)據(jù)沒

有類型的概念，到現(xiàn)在的面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言中抽

象數(shù)據(jù)類型概念的出現(xiàn)，程序設(shè)計(jì)中的數(shù)據(jù)經(jīng)歷了一

次次抽象，數(shù)據(jù)的抽象經(jīng)歷了三個(gè)發(fā)展階段。

A從無(wú)類型的二進(jìn)制數(shù)到基本數(shù)據(jù)類型的產(chǎn)生

A從基本數(shù)據(jù)類型到用戶自定義類型的產(chǎn)生

?從用戶自定義類型到抽象數(shù)據(jù)類型的出現(xiàn)

121數(shù)據(jù)類型

數(shù)據(jù)類型（或簡(jiǎn)稱類型）反映了數(shù)據(jù)的取值范圍以

及對(duì)這類數(shù)據(jù)可以施加的運(yùn)算。

1.2.2數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中廣泛使用的一個(gè)術(shù)語(yǔ)，在

計(jì)算機(jī)科學(xué)中具有非常重要的作用。數(shù)據(jù)結(jié)構(gòu)包括三個(gè)

方面的內(nèi)容：一組數(shù)據(jù)中各數(shù)據(jù)之間的邏輯關(guān)系；這組

數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式；對(duì)這組數(shù)據(jù)所能施加的運(yùn)

算的集合。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。所有的數(shù)據(jù)都

是按照數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類的。簡(jiǎn)單數(shù)據(jù)類型對(duì)應(yīng)于簡(jiǎn)單

的數(shù)據(jù)結(jié)構(gòu)；構(gòu)造數(shù)據(jù)類型對(duì)應(yīng)于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

1.2.3抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型是與表示無(wú)關(guān)的數(shù)據(jù)類型，是一個(gè)數(shù)

據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)

類型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符

名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定

義了一個(gè)抽象數(shù)據(jù)類型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以

像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類

型。

1.2.4抽象數(shù)據(jù)類型的描述和實(shí)現(xiàn)

抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的名稱、

數(shù)據(jù)的集合、數(shù)據(jù)之間的關(guān)系和操作的集合等方面的描

述。抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具

體實(shí)現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象

數(shù)據(jù)類型。

抽象數(shù)據(jù)類型描述的一般形式如下:

ADT抽象數(shù)據(jù)類型名稱{

數(shù)據(jù)對(duì)象：

數(shù)據(jù)關(guān)系：

操作集

操作名1:

操作名n：

}ADT抽象數(shù)據(jù)類型名稱

1.3算法和算法分析

1.3.1算法

為了求解某問(wèn)題，必須給出一系列的運(yùn)算規(guī)則，

這一系列的運(yùn)算規(guī)則是有限的，表達(dá)了求解問(wèn)題方

法和步驟，這就是一個(gè)算法。

一個(gè)算法可以用自然語(yǔ)言描述，也可以用高級(jí)

程序設(shè)計(jì)語(yǔ)言描述，也可以用偽代碼描述。本書采

用c語(yǔ)言對(duì)算法進(jìn)行描述。

算法具有五個(gè)基本特征：

①有窮性，算法的執(zhí)行必須在有限步內(nèi)結(jié)束。

②確定性，算法的每一個(gè)步驟必須是確定的無(wú)二義性

的。

③輸入，算法可以有0個(gè)或多個(gè)輸入。

④輸出，算法一定有輸出結(jié)果

⑤可行性，算法中的運(yùn)算都必須是可以實(shí)現(xiàn)的。

算法具有有窮性，程序不需要具備有窮性。一般

的程序都會(huì)在有限時(shí)間內(nèi)終止，但有的程序卻可以不

在有限時(shí)間內(nèi)終止，如一個(gè)操作系統(tǒng)在正常情況下是

永遠(yuǎn)都不會(huì)終止的。

1.3.2算法的時(shí)間和空間復(fù)雜性

一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需

要占用的存儲(chǔ)空間兩個(gè)方面衡量，算法執(zhí)行時(shí)間的度

量不是采用算法執(zhí)行的絕對(duì)時(shí)間來(lái)計(jì)算的，因?yàn)橐粋€(gè)

算法在不同的機(jī)器上執(zhí)行所花的時(shí)間不一樣，在不同

時(shí)刻也會(huì)由于計(jì)算機(jī)資源占用情況的不同，使得算法

在同一臺(tái)計(jì)算機(jī)上執(zhí)行的時(shí)間也不一樣，所以對(duì)于算

法的時(shí)間復(fù)雜性，采用算法執(zhí)行過(guò)程中其基本操作的

執(zhí)行次數(shù)，稱為計(jì)算量來(lái)度量。

算法中基本操作的執(zhí)行次數(shù)一般是與問(wèn)題規(guī)模

有關(guān)的，對(duì)于結(jié)點(diǎn)個(gè)數(shù)為n的數(shù)據(jù)處理問(wèn)題，用T(n)

表示算法基本操作的執(zhí)行次數(shù)。

在評(píng)價(jià)算法的時(shí)間復(fù)雜性時(shí)，不考慮兩算法執(zhí)行

次數(shù)之間的細(xì)小區(qū)別，而只關(guān)心算法的本質(zhì)差別。為

此，引入一個(gè)所謂的0()記號(hào)，則

T1(n)=2n=O(n),T2(n)=n+1=0(n)o

一個(gè)函數(shù)f(n)是O(g(n))的，則一定存在正常數(shù)c和

m,使對(duì)所有而n>m,都舄足f(n)vc*g(n)。

下面的表格給出了一些具體函數(shù)的0()的表示，如圖

所示。f(n)O(g(n))量級(jí)

35。⑴■wn

2n+7O(n)線性階

n2+10O(n2)

2n3+n0(1?)立方階

算法的時(shí)間復(fù)雜性不僅和問(wèn)題的規(guī)模大小有關(guān)，

還與問(wèn)題數(shù)據(jù)的初始狀態(tài)有關(guān)。

這樣就有了算法在最好、最壞以及在平均狀態(tài)下的

時(shí)間復(fù)雜性的概念。

①算法在最好情況下的時(shí)間復(fù)雜性是指算法計(jì)算量的

最小值。

②算法在最壞情況下的時(shí)間復(fù)雜性是指算法計(jì)算量的

最大值。

③算法的平均情況下的時(shí)間復(fù)雜性是指算法在所有可

能的情況下的計(jì)算量經(jīng)過(guò)加權(quán)計(jì)算出的平均值。

本書在對(duì)算法進(jìn)行分析時(shí)，會(huì)用到如下兩個(gè)記號(hào):

[x]:表示不大于X的最大整數(shù)；

LxJ：表示不小于X的最小整數(shù)。

第2章線性表及其順序存儲(chǔ)

線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，本章介紹線性表

及其順序存儲(chǔ)，并對(duì)棧和隊(duì)列及它們的順序?qū)崿F(xiàn)給出

了詳細(xì)的設(shè)計(jì)描述。

2.1線性表

線性表是一個(gè)線性結(jié)構(gòu)，它是一個(gè)含有nNO個(gè)結(jié)

點(diǎn)的有限序列，對(duì)于其中的結(jié)點(diǎn)，有且僅有一個(gè)開

始結(jié)點(diǎn)沒有前驅(qū)但有一個(gè)后繼結(jié)點(diǎn)，有且僅有一個(gè)

終端結(jié)點(diǎn)沒有后繼但有一個(gè)前驅(qū)結(jié)點(diǎn)，其它的結(jié)點(diǎn)

都有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。一般地，一

個(gè)線性表可以表示成一個(gè)線性序列：尤卜2,…,勺，其

中I是開始結(jié)點(diǎn)，K是終端結(jié)點(diǎn)。

2.21頓序表

2.2.1順序表

線性表采用順序存儲(chǔ)的方式存儲(chǔ)就稱之為順序表。

順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組

地址連續(xù)的存儲(chǔ)單元中。

如順序表的每個(gè)結(jié)點(diǎn)占用len個(gè)內(nèi)存單元，用

location(kJ表示順序表中第i個(gè)結(jié)點(diǎn)(所占內(nèi)存空間的

第1個(gè)單元的地址。則有如下的關(guān)系

location(ki+1)=location(kJ+len

location(kJ=locatio^kj+(i-l)len

順序表的存儲(chǔ)結(jié)構(gòu)如下圖所示:

存儲(chǔ)地址

location(ki)location(k1)+(i-1)1en

內(nèi)存狀況&kn

lenlenlenlen

結(jié)點(diǎn)序號(hào)12

存儲(chǔ)結(jié)構(gòu)要體現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)，順序表的存儲(chǔ)

結(jié)構(gòu)中，內(nèi)存中物理地址相鄰的結(jié)點(diǎn)一定具有順序表

中的邏輯關(guān)系。

順序表類型的描述如下：

ADTsequence_list{

數(shù)據(jù)集合K:K={k1,k2,...,彩},眾0,K中的元素是datatype類型

數(shù)據(jù)關(guān)系R:R={r},r={<ki,ki+1>|i=l,2,...,n-l}

操作集合：

(1)voidinit_sequence_list(sequence_list*slt)順序表的初始化---置空表

(2)voidinsert_sequence」ist(sequence_list*slt,datatypex)后部插入值為x結(jié)點(diǎn)

(3)voidprint_sequence_list(sequence_listsit)打印順序表的各結(jié)點(diǎn)值

(4)intis_empty_sequence_list(sequence_listsit)判斷順序表是否為空

(5)intfind_num_sequence_list(sequence_listsit,datatypex)查找值為x結(jié)點(diǎn)位置

(6)intget_data_pos(sequence_listsit,inti)取得順序表中第i個(gè)結(jié)點(diǎn)的值

(7)voidinsertjpos_sequence_list(sequence_list*sit,intposition,datatypex)

(8)voiddeletejpos_sequence_list(sequence_list*sit,intposition)

}ADTsequence_list;

222順序表的實(shí)現(xiàn)

用C語(yǔ)言中的數(shù)組存儲(chǔ)順序表。C語(yǔ)言中數(shù)組的下標(biāo)

是從0開始的，即數(shù)組中下標(biāo)為0的元素對(duì)應(yīng)的是順序

表中的第1個(gè)結(jié)點(diǎn)，數(shù)組中下標(biāo)為i的元素對(duì)應(yīng)的是順序

表中的第i+1個(gè)結(jié)點(diǎn)。為了方便，將順序表中各結(jié)點(diǎn)的

序號(hào)改為和對(duì)應(yīng)數(shù)組元素的下標(biāo)序號(hào)一致，即將順序

表中各結(jié)點(diǎn)的序號(hào)從0開始編號(hào)。這樣，一個(gè)長(zhǎng)度為n

的順序表可以表示為

順序表的存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下：

<X><x><x><X><x><x><X><X><J>

^T**T*^7*^T**Tw^T?

/*順序表的頭文件，文件名sequlist.h*/

^f>

/^TW^TW^TW

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

intsize;

}sequence_list;

順序表的幾個(gè)基本操作的具體實(shí)現(xiàn)：

<x^^f>^f><x>

*T*^|W^T*

/*順序表的初始化一置空表*/

/*文件名seqlinit.c,函數(shù)名init_sequence_list()*/

<^j><^>/

<T^^T**T*^Tw*Tw^p?*T*^p?/

voidinit_sequencejist(sequence_list*slt)

slt->size=0;

)

算法2.1順序表的初始化一置空表

>f^>t^^1^^t>^t>>i^>i^>t^>i^^t>^t>

在順序表后部進(jìn)行插入操作*/

/*文件名seqlinse.c,函數(shù)名insert_sequence」ist()*/

/^x>^x>^x>^x>^x><x><t>^x><t><X><x><X><x><J>^x><x><J>^x><x>

/^Tw^TwtfTw^Tw^T*^T**T?

voidinsert_sequence_list(sequence_list*slt,datatypex)

(

if(slt->size==MAXSIZE)

{printf("順序表是滿的!n);exit(1);}

slt->size=slt->size+1;

slt->a[slt->size]=x;

)

算法2.2在順序表后部進(jìn)行插入操作

%f^^i#^i#<J^^f>%i>^f>%f^%i>%f^

<T**T*<T**7**TM<]M<1^*T*

*打印順序表的各結(jié)點(diǎn)值*/

/*文件名seqlprin.c,函數(shù)名print_sequence」ist()*/

//^f><^TL*?*^7V*><X*<A>*<Txw>^T**??7!<*><x>*T**<7x*>*<Tx*><X>^<Tt>w^x><x><<xT>k*Tw*^**<TXw>^x>^x>*<Tx*>//

voidprint_sequence_list(sequence_listsit)

(

inti;

if(!slt.size)printf("\n順序表是空的!");

else

for(i=0;i<slt.size;i++)printf(,,%5d,,,slt.a[i]);

)

算法2.3打印順序表的各結(jié)點(diǎn)值

<x><x><X><^>^x><x><x><^><x>^x><x^^X><x><^><x><x><x>

^Tw^Tw<T^<^w<T*<^*^T?^T?^T**Tw*T**T?*Tw^T*^T?*Tw^T*^T?*^**T?

判斷順序表是否為空*/

/*文件名seqlempt.c,函數(shù)名is_empty_sequence_list()*/

/<A???x><x><x><x>/

/*T**T*^T**T*^TwtfT*^T**T*/

intis_empty_sequencejist(sequence_listsit)

return(slt.size==O?0:1);

)

算法2.4判斷順序表是否為空

^1#^t#>i^%f^%l^%f^%f^%i>%i^%l^^iO/

<T**T**7*/

/*查找順序表中值為X的結(jié)點(diǎn)位置*/

/*文件名seqlfind.c,函數(shù)名find_num_sequence_list()*/

<x><^><x>^x><x><x*<A>^x><x><1>^x><X>^x><x><j^^x><^>/

*7*^T**Tw*7**7*<^*^7**Tw*T**7**T**Tw*TM^Tw/

intfind_num_sequence_list(sequencejistsit,datatypex)

(

inti=0;

while(slt.a[i]!=x&&i<slt.size)i++;

return(i<slt.size?i:-1);

)

算法2.5查找順序表中值為x的結(jié)點(diǎn)位置

<x>^x><x><x>^x><x>^x><x><x><x>^x><^>/

*T*<T**T*^Tw^T?^T?^T?^T**^*<^**T**T*/

/*取得順序表中第i個(gè)結(jié)點(diǎn)的值*/

/*文件名seqlget.c,函數(shù)名get_data_pos_sequence_list()*/

^f><X>^X><x><X>^X><x><x><x><X>^X><X><x>/

/^r**T*^7*^Tw^Tw^T*^T**T*^T*tfT**T**T*/

intget_data_pos(sequencejistsltjnti)

(

if(i<O||i>=slt.size)

{printf(”\n指定位置的結(jié)點(diǎn)不存在!");exit(1);}

else

returnslt.a[i];

)

算法2.6取得順序表中第i個(gè)結(jié)點(diǎn)的值

順序表的插入運(yùn)算是將一個(gè)值為X的結(jié)點(diǎn)插入到順序

表的第i個(gè)位置OWiWn,即將x插入到跖和匕之間，如果

i=n,則表示插入到表的最后，一般地可表示為：

才擊人.麗：{1,占,k1_pk|,..kn_j}

插入后：{k0,勺，…，kM,x,kpKJ}

插入過(guò)程的圖示見下圖：

voidinsert_pos_sequence_list(sequence_list*slt,int

position,datatypex)

{inti;

if(slt->size==MAXSIZE)

{printf(“\n順序表是滿的!沒法插入!)exit。);}

if(position<0||position>slt->size)

{printf(”\n指定的插入位置不存在!)exit。);}

for(i=slt->size;i>position;i-)slt->a[i]=slt->a[i-1];

slt->a[position]=x;

slt->size++;

)

算法2.7在順序表的position位置插入值為x的結(jié)點(diǎn)

算法2.7中，所花費(fèi)的時(shí)間主要是元素后移操作，對(duì)

于在第i個(gè)位置上插入一個(gè)新的元素，需要移動(dòng)(n-i)

個(gè)元素，設(shè)在第i個(gè)位置上插入一個(gè)元素的概率為加且

在任意一個(gè)位置上插入元素的概率相手，即

Po=p1=p2=..尸P:1/n+L則在一個(gè)長(zhǎng)度為n的順序表中插

入一個(gè)元素所需的平均移動(dòng)次數(shù)為：

11H(77+1)n

ZP-￡--------(n-i)=--------x---------------=-

；n..八〃+1n+\22

即在長(zhǎng)度為n的順序表中插入一個(gè)元素平均需要

移動(dòng)表中的一半元素。該算法的時(shí)間復(fù)雜度為O(n)。

順序表的刪除操作是指刪除順序表中的第i個(gè)結(jié)點(diǎn),

0<i<n-l,一般地可表示為：

刪除前：｛k0K..m，…,D

刪除后：｛k0,…，kg,kj+1，…，n

刪除過(guò)程的圖示見下圖：

刪除前kgk]

i-ln-1

前移開始前移結(jié)束位置

刪除后kg瓦

“叼+1n-1

刪除操作的具體實(shí)現(xiàn)見算法2.8

voiddelete_pos_sequencejist(sequence_list*slt,intposition)

(

inti;

if(slt->size==O)

{printf("\n順序表是空的!H);exit(1);}

if(position<0||position>=slt->size)

{printf(”\n指定的刪除位置不存在!)exit。);}

for(i=position;i<slt->size-1;i-)slt->a[i]=slt->a[i+1];

slt->size-;

)

算法2.8刪除順序表中第position位置的結(jié)點(diǎn)

要?jiǎng)h除順序表中的第i個(gè)結(jié)點(diǎn)，則需要稱動(dòng)（n-i-1）

個(gè)元素，設(shè)刪除表中第i個(gè)結(jié)點(diǎn)的概率為且在表中每

一個(gè)位置刪除的概率相等，即：

q（）=qi=?,尸qn.i=i/n

則在一個(gè)長(zhǎng)度為n的順序表中刪除一個(gè)結(jié)點(diǎn)的平均

移動(dòng)次數(shù)為：

￡q.{n—i—1)=￡—(n—i—1)=-x---------=----

i=oZ=on〃22

這表明，在一個(gè)長(zhǎng)為n的順序表中刪除一個(gè)元素平

均需要移動(dòng)表中大約一半的元素。該算法的時(shí)間復(fù)雜

度為O（n）o

2.3棧

231棧

棧是一種特殊的線性表，對(duì)于這種線性表規(guī)定它

的插入運(yùn)算和刪除運(yùn)算均在線性表的同一端進(jìn)行，進(jìn)

行插入和刪除的那一端稱為棧頂，另一端稱為棧底。

棧的插入操作和刪除操作也分別簡(jiǎn)稱進(jìn)棧和出棧。

如果棧中有n個(gè)結(jié)點(diǎn)

{k°,k],k2，■■■,

k0為我底，kn/是我頂,

則棧中結(jié)點(diǎn)的進(jìn)棧順

序?yàn)閗。,kp卜2，.??,kn/5

而出我的順序?yàn)閗n."

kn.2,k1,k0o如圖

:所示。

棧類型的描述如下：

ADTsequence_stack{

數(shù)據(jù)集合K：K={kvk2,...,kn},n>0,K中的元素是datatype類型

數(shù)據(jù)關(guān)系R:R={r}

r={<kj,ki+1>|i=1,2,...,n-1)

操作集合：

(1)voidinit_sequence_stack(sequence_stack*st)(4頁(yè)序存儲(chǔ))

初始化

(2)intis_empty_stack(sequence_stackst)判斷棧(順序存儲(chǔ))

是否為空一—一

(3)voidprint_sequence_stack(sequence_stackst)打印棧(順

序存儲(chǔ))的眼>、值—一

(4)datatypeget_top(sequence_stackst)取得棧頂(順序存

儲(chǔ))結(jié)點(diǎn)值——

(5)voidpush(sequence_stack*st,datatypex)棧(順序存儲(chǔ))

的插入操作

(6)voidpop(sequence_stack*st)棧(順序存儲(chǔ))的刪除操

作

}ADTsequence_stack

2.3,2順序棧及其實(shí)現(xiàn)

棧的實(shí)現(xiàn)方式一般有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

本小節(jié)將給出棧的順序存儲(chǔ)實(shí)現(xiàn)。

棧的順序存儲(chǔ)方式就是在順序表的基礎(chǔ)上對(duì)插入

和刪除操作限制它們?cè)陧樞虮淼耐欢诉M(jìn)行，所以同

順序表一樣也可用一維數(shù)組表示。

一般地，可以設(shè)定一個(gè)足夠大的一維數(shù)組存儲(chǔ)棧,

數(shù)組中下標(biāo)為。的元素就是棧底，對(duì)于棧頂，可以設(shè)一

個(gè)指針top指示它。

為了方便，設(shè)定top所指的位置是下一個(gè)將要插入

的結(jié)點(diǎn)的存儲(chǔ)位置，這樣，當(dāng)top=0時(shí)就表示是一個(gè)空

的棧。一個(gè)棧的幾種狀態(tài)以及在這些狀態(tài)下棧頂指針

top和棧中結(jié)點(diǎn)的關(guān)系如下圖所示。

數(shù)組下標(biāo)數(shù)組下標(biāo)數(shù)組下標(biāo)

topf

(a)空棧(b)有兩個(gè)結(jié)點(diǎn)的棧⑹棧已滿

棧的順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下:

/*****************************/

/*棧（順序存儲(chǔ)）的頭文件*/

/*文件名seqstack.h*/

/*****************************/

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

inttop;

}sequence_stack;

下面是順序存儲(chǔ)棧的幾個(gè)基本操作的具體實(shí)現(xiàn)

/***********************************************************I

棧（順序存儲(chǔ)）初始化*/

r文件名seqsinit.c,函數(shù)名init_sequence_stack()*/

/***********************************************************I

voidinit_sequence_stack(sequence_stack*st)

st->top=0;

}

算法2.9棧（順序存儲(chǔ)）初始化

/***************************************************/

/*判斷棧(順序存儲(chǔ))是否為空*/

/*文件名seqsempt.c,函數(shù)名is_empty_sequence_stack()*/

/***************************************************/

intis_empty_stack(sequence_stackst)

(

return(st.top?0:1);

}

算法2.10判斷棧（順序存儲(chǔ)）是否為空

*************************************************

/*取得棧頂(順序存儲(chǔ))結(jié)點(diǎn)值*/

/*文件名seqsfirs.c,函數(shù)名get_top()*/

/***************************************************/

datatypeget_top(sequence_stackst)

(

if(empty_stack(st))

{printf("\n棧是空的!");exit(1);}

else

returnst.a[st.top-1];

)

算法2.11取得棧頂（順序存儲(chǔ)）結(jié)點(diǎn)值

/***************************************************/

/*棧(順序存儲(chǔ))的插入操作*/

/*文件名seqspush.c,函數(shù)名push。7

/***************************************************/

voidpush(sequence_stack*st,datatypex)

(

if(st->top==MAXSIZE)

{printf("\nThesequencestackisfull!H);exit(1);}

st->a[st->top]=x;

st->top++;

)

算法2.12棧（順序存儲(chǔ)）的插入操作

***********************************************

/*棧(順序存儲(chǔ))的刪除操作*/

/*文件名seqspop.c,函數(shù)名pop()*/

/***************************************************/

voidpop(sequence_stack*st)

(

if(st->top==0)

{printf("\nThesequencestackisempty!H);exit(1);}

st4top一；

)

算法2.13棧（順序存儲(chǔ)）的刪除操作

233棧的應(yīng)用之一——括號(hào)匹配

設(shè)一個(gè)表達(dá)式中可以包含三種括號(hào)：小括號(hào)、中括

號(hào)和大括號(hào)，各種括號(hào)之間允許任意嵌套，如小括號(hào)內(nèi)

可以嵌套中括號(hào)、大括號(hào)，但是不能交叉。舉例如下：

([]{})正確的

([()])正確的

{([])}正確的

{[(])}不正確的

{(}[])不正確的

如何去檢驗(yàn)一'個(gè)表達(dá)式的括號(hào)是否匹配呢？大家

知道當(dāng)自左向右掃描一個(gè)表達(dá)式時(shí)，凡是遇到的開括號(hào)

（或稱左括號(hào)）都期待有一個(gè)和它對(duì)應(yīng)的閉括號(hào)（或稱

右括號(hào)）與之匹配。

按照括號(hào)正確匹配的規(guī)則，在自左向右掃描一個(gè)表

達(dá)式時(shí)，后遇到的開括號(hào)比先遇到的開括號(hào)更加期待有

一個(gè)閉括號(hào)與之匹配。

可能會(huì)連續(xù)遇到多個(gè)開括號(hào)，且它們都期待尋求

匹對(duì)的閉括號(hào)，所以必須將遇到的開括號(hào)存放好。又

因?yàn)楹笥龅降拈_括號(hào)的期待程度高于其先前遇到的開

括號(hào)的期待程度，所以應(yīng)該將所遇到的開括號(hào)存放于

一個(gè)棧中。這樣，當(dāng)遇到一個(gè)閉括號(hào)時(shí)，就查看這個(gè)

棧的棧頂結(jié)點(diǎn)，如果它們匹配，則刪除棧頂結(jié)點(diǎn)，如

果不匹配，則說(shuō)明表達(dá)式中括號(hào)是不匹配的，如果掃

描它整個(gè)表達(dá)式后，這個(gè)棧是空的，則說(shuō)明表達(dá)式中

的括號(hào)是匹配的，否則表達(dá)式的括號(hào)是不匹配的。

判斷表達(dá)式括號(hào)是否匹配的具體實(shí)現(xiàn)見算法2.14。

/

/

/*判斷表達(dá)式括號(hào)是否匹配*/

/*文件名seqmatch.c,函數(shù)名match_huohao()*/

//

/<TW^TW<TW^XW/

intmatch_kuohao(charc[])

inti=0;

sequence_stacks;

init_sequence_stack(&s);

while(c[i]!=,#i)

(

switch(c[i])

case

case

case'(,:push(&s,c[i]);break;

case'}':if(!is_empty_sequence_stack(s)&&get_top(s)==,{'}

{pop(&s);break;}elsereturn0;

case,]'：if(!is_empty_sequence_stack(s)&&get_top(s)=='[,]

{pop(&s);break;}elsereturn0;

case,),:if(!is_empty_sequence_stack(s)&&get_top(s)=='(,)

{pop(&s);break;}elsereturn0;

)

i++;

)

return(is_empty_sequence_stack(s));/*棧空貝U匹配，否貝U不匹配*/

)

算法2.14判斷表達(dá)式括號(hào)是否匹配

234棧的應(yīng)用之二——算術(shù)表達(dá)式求值

2.4隊(duì)列

2.4.1隊(duì)列

隊(duì)列是一種特殊的線性表，它的特殊性在于隊(duì)列

的插入和刪除操作分別在表的兩端進(jìn)行。插入的那一

端稱為隊(duì)尾，刪除的那一端稱為隊(duì)首。隊(duì)列的插入操

作和刪除操作也分別簡(jiǎn)稱進(jìn)隊(duì)和出隊(duì)。

對(duì)于一個(gè)隊(duì)列：

如果k°那端是隊(duì)首，那端是隊(duì)尾，則k0是這些結(jié)點(diǎn)

中最先插入的結(jié)點(diǎn)，若要做刪除操作，q將首先被刪

除，所以說(shuō)，隊(duì)列是具有“先進(jìn)先出”(FIFO,First

InFirstOut)特點(diǎn)的線性結(jié)構(gòu)。

隊(duì)列類型的描述如下：

ADTsequence_queue{

數(shù)據(jù)集合K：K={kvk2,...,kn},n>0,K中的元素是datatype類型

數(shù)據(jù)關(guān)系R:R={r}

r={<kj,ki+1>|i=1,2,...,n-1)

操作集合：

(1)voidinitsequencequeue(sequencequeue*sq)隊(duì)列(順

序存儲(chǔ))初據(jù)化——

(2)intis_empty_sequence_queue(sequence_queuesq)判斷

隊(duì)列(順序存儲(chǔ)1是否為空一一

(3)voidprintsequencequeue(sequencequeuesq)打印隊(duì)歹U

(順序存儲(chǔ))一的結(jié)點(diǎn)值—一

(4)datatypeget_first(sequence_queuesq)取得隊(duì)歹(用頁(yè)序存

儲(chǔ))的隊(duì)首結(jié)點(diǎn)殖一

(5)voidinsert_sequence_queue(sequence_queue

*sq,datatypex)隊(duì)列(順序存儲(chǔ))插入操作

(6)voiddelete_sequence_queue(sequence_queue*sq)隊(duì)列

(順序存儲(chǔ))留前除操作—一

}ADTsequence_queue;

2.4.2順序隊(duì)列及其實(shí)現(xiàn)

隊(duì)列的順序存儲(chǔ)在C語(yǔ)言中可以用一維數(shù)組表示,

為了標(biāo)識(shí)隊(duì)首和隊(duì)尾，需要附設(shè)兩個(gè)指針front和rear,

front指示的是隊(duì)列中最前面，即隊(duì)首結(jié)點(diǎn)在數(shù)組中元

素的下標(biāo)，rea「指示的是隊(duì)尾結(jié)點(diǎn)在數(shù)組中元素的下

標(biāo)的下一個(gè)位置，也就是說(shuō)rear指示的是即將插入的

結(jié)點(diǎn)在數(shù)組中的下標(biāo)。

的幾種狀態(tài)：

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下:

/*****************************/

/*隊(duì)列（順序存儲(chǔ)）的頭文件*/

/*文件名seqqueue.h*/

/*****************************/

#defineMAXSIZE100

typedefintdatatype;

typedefstruct{

datatypea[MAXSIZE];

intfront;

intrear;

}sequence_queue;

順序存儲(chǔ)隊(duì)列的幾個(gè)基本操作的具體實(shí)現(xiàn):

/************************************************I

隊(duì)列（順序存儲(chǔ)）初始化*/

/*文件名seqqinitc函數(shù)名init_sequence_queue()*/

/************************************************I

voidinit_sequence_queue(sequence_queue*sq)

sq->front=sq->rear=0;

}

算法2.20隊(duì)列（順序存儲(chǔ)）初始化

*************************************************

/*判斷隊(duì)列(順序存儲(chǔ))是否為空*/

/*文件名seqqempt.c,函數(shù)名is_empty_sequence_queue()*/

/***************************************************/

intis_empty_sequence_queue(sequence_queuesq)

(

return(sq.front==sq.rear?1:0);

)

算法2.21判斷隊(duì)列（順序存儲(chǔ)）是否為空

/***************************************************/

/*打印隊(duì)列(順序存儲(chǔ))的結(jié)點(diǎn)值*/

/*文件名seqqprin.c,函數(shù)名print_sequence_queue()*/

/***************************************************/

voidprint_sequence_queue(sequence_queuesq)

(

inti;

if(is_empty_sequence_queue(sq))

(

printf(”\n順序隊(duì)列是空的!)

)

else

for(i=sq.front;i<sq.rear;i++)printf("%5d",sq.a[i]);

}

算法2.22打印隊(duì)列(順序存儲(chǔ))的結(jié)點(diǎn)值

/*********************************************/

/*隊(duì)列(順序存儲(chǔ))的插入操作*/

/*文件名seqqinse.c,函數(shù)名insert_sequence_queue()*/

/********************************************/

voidinsert_sequence_queue(sequence_queue*sq,datatypex)

inti;

if(sq->rear==MAXSIZE)

{printf(”\n順序循環(huán)隊(duì)列是滿的!)exit。);}

sq->a[sq->rear]=x;

sq->rear=sq->rear+1;

)

算法2.24隊(duì)列（順序存儲(chǔ)）的插入操作

/***************************************************/

/*隊(duì)列(順序存儲(chǔ))的刪除操作7

/*文件名seqqdele.c,函數(shù)名delete_sequence_queue()*/

/***************************************************/

voiddelete_sequence_queue(sequence_queue*sq)

(

if(sq->front==sq->rear)

(

printfCn順序隊(duì)列是空的!不能做刪除操作！)exit(1);

)

sq->front++;

)

算法2.25隊(duì)列（順序存儲(chǔ)）的刪除操作

在隊(duì)列的幾種狀態(tài)圖的(e)狀態(tài)中，隊(duì)列是一種

隊(duì)滿狀態(tài)，將不能再插入新的結(jié)點(diǎn)，而實(shí)際上數(shù)組的

前部還有許多空的位置。為了充分地利用空間，可以

將隊(duì)列看作一個(gè)循環(huán)隊(duì)列，在數(shù)組的前部繼續(xù)作插入

運(yùn)算，這就是循環(huán)隊(duì)列。

首、隊(duì)尾指針frontrear

DEX

下標(biāo)01234MAXSIZE>1

(e)連續(xù)插入若干結(jié)點(diǎn)后的狀態(tài)一此時(shí)隊(duì)列呈現(xiàn)滿的狀態(tài),但數(shù)姻前部有空位子

243順序循環(huán)隊(duì)列及其實(shí)現(xiàn)

給定一個(gè)大小為MAXSIZE的數(shù)組存儲(chǔ)一個(gè)隊(duì)列

時(shí)，經(jīng)過(guò)若干次插入和刪除操作后，當(dāng)隊(duì)尾指指

rear二MAXSIZE時(shí)，呈現(xiàn)隊(duì)列滿的狀態(tài)，而事實(shí)上數(shù)

組的前部可能還有空閑的位置。為了有效利用空間，

將順序存儲(chǔ)的隊(duì)列想象為一個(gè)環(huán)狀，把數(shù)組中的最前

和最焉兩個(gè)元素看作是相鄰的，這就是循環(huán)隊(duì)列。

循環(huán)隊(duì)列的幾種狀態(tài)表示:

front

⑥初始狀態(tài)一空的循環(huán)隊(duì)列

rear

——front

(b)剩余一個(gè)空間的狀態(tài)⑹循環(huán)隊(duì)列中只有一個(gè)結(jié)點(diǎn)的狀態(tài)

在(b)狀態(tài)中，如果再插入一個(gè)新的結(jié)點(diǎn)，則數(shù)

組空間將被全部占用，隊(duì)列已滿，且rear二front,而在

(c)XK態(tài)中，若刪除一個(gè)結(jié)點(diǎn)隊(duì)列成為空隊(duì)列，it匕時(shí)

也有rear二front,這就是說(shuō)循環(huán)隊(duì)列滿與空的條件都是

rear=front0

解決方法是犧牲一個(gè)數(shù)組元素的空間，即若數(shù)組的大

小是MAXSIZE,則該數(shù)組所表示的循環(huán)隊(duì)列最多允許存

儲(chǔ)MAXSIZE-1個(gè)結(jié)點(diǎn)。這樣，循環(huán)隊(duì)列滿的條件是

(rear+l)%MAXSIZE=front

循環(huán)隊(duì)列空的條件是rear=front

循環(huán)隊(duì)列的插入與刪除操作的實(shí)現(xiàn):

/***************************************************/

/*循環(huán)隊(duì)列(順序存儲(chǔ))的插入操作*/

/*文件名secqinst.c,函數(shù)名insert_sequence_cqueue()*/

/***************************************************/

voidinsert_sequence_cqueue(sequence_queue*sq,datatypex)

inti;

if((sq->rear+1)%MAXSIZE==sq->front)

{printf(”\n順序循環(huán)隊(duì)列是滿的！無(wú)法進(jìn)行插入操作！H);exit(1);}

sq->a[sq->rear]=x;

sq->rear=(sq->rear+1)%MAXSIZE;

}

算法2.27循環(huán)隊(duì)列（順序存儲(chǔ)）的插入操作

,***************************************************/

/*循環(huán)隊(duì)列(順序存儲(chǔ))的刪除操作7

/*文件名secqdele.c,函數(shù)名delete_sequence_cqueiie()*/

/***************************************************/

voiddelete_sequence_cqueue(sequence_queue*sq)

(

if(sq->front==sq->rear)

(

printf("\n循環(huán)隊(duì)列是空的！無(wú)法進(jìn)行刪除！)exit(1);

)

sq->front=(sq->front+1)%MAXSIZE;

)

算法2.28循環(huán)隊(duì)列（順序存儲(chǔ)）的刪除操作

第3章線性表的鏈?zhǔn)酱鎯?chǔ)

線性表的存儲(chǔ)方式除了常用的順序存儲(chǔ)外，采用

鏈?zhǔn)椒绞酱鎯?chǔ)也是一種常見的方式。本章將介紹一般

線性表的幾種鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)方式，如單鏈表、帶頭結(jié)

點(diǎn)單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表一

■棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)。

3」鏈?zhǔn)酱鎯?chǔ)

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式必須體現(xiàn)它的邏輯關(guān)系。

在鏈?zhǔn)酱鎯?chǔ)方式下，實(shí)現(xiàn)中除存放一個(gè)結(jié)點(diǎn)的信息外,

還需附設(shè)指針，用指針體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。如

果一個(gè)結(jié)點(diǎn)有多個(gè)后繼或多個(gè)前驅(qū)，那么可以附設(shè)相

應(yīng)個(gè)數(shù)的指針，一個(gè)結(jié)點(diǎn)附設(shè)的指針指向的是這個(gè)結(jié)

點(diǎn)的某個(gè)前驅(qū)或后繼。

線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)

后繼，這里暫且設(shè)定更關(guān)心它的后繼，這樣在存儲(chǔ)時(shí)除

了存放該結(jié)點(diǎn)的信息外，只要附設(shè)一個(gè)指針即可，該指

針指向它的后繼結(jié)點(diǎn)的存放位置。每個(gè)結(jié)點(diǎn)的存儲(chǔ)形式

3.2鏈表

單鏈表是線性表鏈?zhǔn)酱鎯?chǔ)的一種形式，其中的結(jié)點(diǎn)

一般含有兩個(gè)域，一個(gè)是存放數(shù)據(jù)信息的info域，另一

個(gè)是指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的存放地址的指針域next。

一個(gè)單鏈表必須有一個(gè)首指針指向單鏈表中的第一個(gè)結(jié)

點(diǎn)。圖3.3給出了空的單鏈表和非空的單鏈表的圖示。

head—?A

⑶空的單捱表

head

A

(b)一個(gè)非空的單捱表

ADTlinkjist{

(6)node*insert_x_after_y(node*head,datatypex,datatypey)

在單鏈表中值為y的結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)

(7)node*insert_x_afterj(node*head,datatypex,inti)

在單鏈表中第i個(gè)結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)

(8)node*delete_numjinkjist(node*head,datatypex)在單鏈

表中刪除一個(gè)值為x的好點(diǎn)一

(9)node*delete_pos_linkjist(node*head,inti)在單鏈表中刪除

第i個(gè)結(jié)點(diǎn)一一一

}ADTIink_list;

322單鏈表的實(shí)現(xiàn)

單鏈表結(jié)構(gòu)的C語(yǔ)言描述如下：

/**********************************/

/*鏈表實(shí)現(xiàn)的頭文件，文件名slnklist.h7

/**********************************/

typedefintdatatype;

typedefstructlink_node{

datatypeinfo;

structlink_node*next;

}node;

單鏈表幾個(gè)基本操作的具體實(shí)現(xiàn)：

/*****************************************************/

/*建立一個(gè)空的單鏈表*/

/*文件名slnkinit.c,函數(shù)名init_link_list()*/

/*****************************************************/

node*initjink_list()/*建立一個(gè)空的單鏈表*/

(

returnNULL;

)

算法3.1建立一個(gè)空的單鏈表

/*****************************************************/

/*輸出單鏈表中各個(gè)結(jié)點(diǎn)的值*/

/*文件名slnkprin.c,函數(shù)名print_link_list()*/

/*****************************************************/

voidprint_link_list(node*head)

{node*p;

p=head;

if(!p)printf(”\n單鏈表是空的！)

else

{printf(”\n單鏈表各個(gè)結(jié)點(diǎn)的值為：\nu);

while(p){printf(,'%5d",p->info);p=p->next;}

)

)

算法3.2輸出單鏈表中各個(gè)結(jié)點(diǎn)的值

/*****************************************************

/*在單鏈表中查找一個(gè)值為X的結(jié)點(diǎn)*/

/*文件名slnkfinxc函數(shù)名find_num」ink_list()*/

***************************************************/

node*find_numJinkJist(node*head,datatypex)

node*p;

p=head;

while(p&&p->info!=x)p=p->next;

returnp;

)

算法3.3在單鏈表中查找一個(gè)值為x的結(jié)點(diǎn)

/*****************************************************/

/*在單鏈表中查找第i個(gè)結(jié)點(diǎn)*/

/*文件名slnkfinic函數(shù)名find_pos」ink_list()*/

/*****************************************************/

node*find__posjink_list(node*head,inti)

{---

intj=1;

node*p=head;

if(i<1){printf(H\nError!\n");exit(1);}

while(p&&i!=j){p=p->next;j++;}

returnp;

)

算法3.4在單鏈表中查找第i個(gè)結(jié)點(diǎn)

單鏈表的插入過(guò)程見下圖所示:

/*****************************************************/

/*插入一個(gè)值為X的結(jié)點(diǎn)作為單鏈表的第一個(gè)結(jié)點(diǎn)*/

/*文件名slnkinfx.c,函數(shù)名insertjn_front_link_list()*/

/*****************************************************/

node*insert_i