數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)歸納和習(xí)題解答

第1章緒論

一、數(shù)據(jù)結(jié)構(gòu)的基本概念

1.基礎(chǔ)概念和術(shù)語(yǔ)

(1)數(shù)據(jù)(Data)：數(shù)據(jù)是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被

計(jì)算機(jī)程序處理的符號(hào)的總稱。

(2)數(shù)據(jù)元素(DataElement)：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮

和處理。

(3)數(shù)據(jù)項(xiàng)(DataItem)：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位，數(shù)據(jù)項(xiàng)是對(duì)客觀事物的某一方面的

數(shù)據(jù)描述。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(DataItem)組成。

(4)數(shù)據(jù)對(duì)象(DataObject)：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符

集合C=rA7B：C,...)

(5)數(shù)據(jù)結(jié)構(gòu)(DataStructure)：數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。

元素之間的相互聯(lián)系(關(guān)系)稱為邏輯結(jié)構(gòu)。

2.數(shù)據(jù)結(jié)構(gòu)的形式定義

數(shù)據(jù)結(jié)構(gòu)的形式定義是一個(gè)二元組：

DataStructure=(D,S)

其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。

數(shù)據(jù)元素之間的關(guān)系可以是元素之間本身代表的某種自然關(guān)系，也可以是為了處理問(wèn)題方便而人為定義

的關(guān)系，這種自然或人為定義的關(guān)系稱為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。

3.數(shù)據(jù)結(jié)構(gòu)的組成

數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：

(1)邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系的描述。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型：

①集合：結(jié)構(gòu)中的數(shù)據(jù)除了“同屬于一個(gè)集合''外，沒有其它關(guān)系。

②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。

③樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。

④圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。

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

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)際表達(dá)方式，它包括對(duì)數(shù)據(jù)元素的表示和對(duì)關(guān)系的表示。存儲(chǔ)結(jié)構(gòu)主要有：順

序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。

①順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)。數(shù)據(jù)元素存放的

地址是連續(xù)的。其優(yōu)點(diǎn)是可以實(shí)現(xiàn)隨機(jī)存取，存儲(chǔ)空間??；缺點(diǎn)是只能使用相鄰的一整塊存儲(chǔ)單元，容

易產(chǎn)生碎片。

②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針，用該指針來(lái)表示數(shù)據(jù)元素

之間的邏輯結(jié)構(gòu)。對(duì)數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。其優(yōu)點(diǎn)是能充分利用所有存儲(chǔ)單元；缺點(diǎn)

是每個(gè)結(jié)點(diǎn)都需要額外的存儲(chǔ)空間，且只能實(shí)現(xiàn)順序存取。

③索引存儲(chǔ)結(jié)構(gòu)：在存儲(chǔ)元素信息的同時(shí).還建立附加的索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)，索引

項(xiàng)的一般形式是：（關(guān)鍵字.地址），關(guān)鍵字唯一標(biāo)識(shí)一個(gè)元素，地址作為指向元素的指針。其優(yōu)點(diǎn)是

檢索速度快；缺點(diǎn)是需要額外的存儲(chǔ)空間來(lái)存放索引表。

④散列（或哈希）存儲(chǔ)結(jié)構(gòu)：根據(jù)元素的關(guān)鍵字通過(guò)哈希函數(shù)直接計(jì)算出該元素的存儲(chǔ)地址。其優(yōu)點(diǎn)是

檢索速度快，缺點(diǎn)是可能存在沖突，而解決沖突會(huì)增加時(shí)空開銷。

（3）數(shù)據(jù)操作

對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算。

【例】下列有關(guān)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的敘述中，正確的是（）。

A.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)

B.順序存儲(chǔ)方式的優(yōu)點(diǎn)是占用存儲(chǔ)空間小，插入、刪除等操作效率高

C.鏈表的每個(gè)結(jié)點(diǎn)中都恰好含有一個(gè)指針

D.Hash存儲(chǔ)的基本思想是由關(guān)鍵詞的值決定數(shù)據(jù)的存儲(chǔ)地址

【答案】D

【解析】順序存儲(chǔ)方式除了用于存儲(chǔ)線性結(jié)構(gòu)外，還能存儲(chǔ)數(shù)組或完全二叉樹等非線

性結(jié)構(gòu)，但在插入、刪除操作時(shí)，由于要移動(dòng)大量的數(shù)據(jù)，執(zhí)行效率低。鏈表的形式有單鏈表、雙鏈表

和多重鏈表，除了單鏈表外，其他鏈表中的結(jié)點(diǎn)需要兩個(gè)以上的指針。

二、抽象數(shù)據(jù)類型

1.數(shù)據(jù)類型

數(shù)據(jù)類型（DataType）：數(shù)據(jù)類型是一個(gè)值的集合和定義在該集合上的一組操作的總稱。

2.抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型（ADT）：是指一個(gè)數(shù)學(xué)模型以及定義在該數(shù)據(jù)模型上的一組操作。

ADT的定義僅是一組邏輯特性的描述，與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無(wú)關(guān)。因此，不論ADT內(nèi)部結(jié)構(gòu)如

何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。

ADT的形式化定義是三元組：ADT={D,S,P}。

其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。

三、算法分析

1.算法

（1）概念

算法（Algorithm）：算法是對(duì)特定問(wèn)題求解方法（步驟）的一種描述，是指令的有限序列，其中每一

條指令表示一個(gè)或多個(gè)操作。

（2）特性

算法由五個(gè)特性：

①有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。

②確定性：算法中每一條指令必須有確切的含義，不存在二義性，且算法只有一個(gè)入口和出口。

③可行性：算法描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。

④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。

⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出同輸入有著某些特定關(guān)系的量。

(3)評(píng)價(jià)標(biāo)準(zhǔn)

評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)：

①正確性：算法應(yīng)滿足具體問(wèn)題的需求。

②可讀性：算法應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改。

③健壯性：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理。

④通用性：算法應(yīng)具有一般性，處理結(jié)果對(duì)于一般數(shù)據(jù)集合都成立。

⑤效率和存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指的是執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空

間。

2.效率的度量

(1)時(shí)間復(fù)雜度

算法中的基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，其時(shí)間度量記做T(n)=O(f(n))(其

中“O”是指T(n)的數(shù)量級(jí))，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

算法的時(shí)間復(fù)雜度一般用最深層循環(huán)內(nèi)的語(yǔ)句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來(lái)表示。

常用的時(shí)間復(fù)雜度的關(guān)系：

0(1)<0(log2n)<0(n)<0(nlog2n)<0(n2)<O(n3)

指數(shù)時(shí)間復(fù)雜度關(guān)系為：O(2n)<O(n!)<O(nn)

有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)會(huì)隨問(wèn)題的輸入數(shù)據(jù)集的不同而不同

(2)空間復(fù)雜度

空間復(fù)雜度指的是算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記做：S(n)

=0(f(n)),其中n為問(wèn)題的規(guī)模。

空間復(fù)雜度一般包括三個(gè)方面：

①指令常數(shù)變量所占用的存儲(chǔ)空間。

②輸入數(shù)據(jù)所占用的存儲(chǔ)空間。

③輔助存儲(chǔ)空間。

【例】有以下算法，其時(shí)間復(fù)雜度為()。

voidfun(intn)

(

mtp=1,d=n,f=n；

while(d>0)

(

if(d%2==i)

p=p*f；

f=f*f:d=d2;

)

}

A.O(1)

B.O(log2n)

C.0(n)

D.(nlog2n)

【答案】Bo

【解析】基本運(yùn)算語(yǔ)句為(1=皿2(或,設(shè)其執(zhí)行時(shí)間為T(n),則有：

d=ii2：安士1,2T：0：＜n

則T(n)Slog2n=0(log2n)。

注意算法中while循環(huán)的if條件中包含的尸p*f語(yǔ)句可以不考慮.因?yàn)樗鼒?zhí)行的次數(shù)不超過(guò)d=d/2語(yǔ)句的執(zhí)行

次數(shù)。

練習(xí)題一、單項(xiàng)選擇題

1.下列程常段的時(shí)間復(fù)雜度是()。［2014年聯(lián)考真題］

count=0:

fork*2)

for

count—;

A.0(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】C

【解析】外部循環(huán)的退出條件是k>n,而對(duì)于k,每次循環(huán)都執(zhí)行1<=1<*2,所以循環(huán)次數(shù)為log,n；內(nèi)部循環(huán)

的退出條件是j>n,對(duì)于j,每次循環(huán)都執(zhí)行)可+1,所以每次循環(huán)次數(shù)為n次。所以此程序段的時(shí)間復(fù)雜度

為O(nlog2n),即選C。

2.求整數(shù)n(n>0)階乘的算法如下，其時(shí)間復(fù)雜度是()。［2012年聯(lián)考真題］

intfact(intn)

(if(nV=1)return11

returnn?fact(n-1)?

A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】B

【解析】設(shè)fact(n)的運(yùn)行時(shí)間函數(shù)是T(n).

intfact<intn){

if(nV=l)return11〃語(yǔ)句

returnn?fact(n-1)>//語(yǔ)句

該函數(shù)中語(yǔ)句①的運(yùn)行時(shí)間是0(1),語(yǔ)句②的運(yùn)行時(shí)間是T(n-1)+O(1),其中O(1)為乘法運(yùn)算

的時(shí)間。

因此，當(dāng)旺1時(shí)，T(n)-0(1)；當(dāng)n>l時(shí)，T(n)=T(n-1)+0(1)。則，T(n)=0(1)+T(n-1)

=2x0(1)+T(n-2)=(n-1)xQ(1)+T(1)=nxO(1)

=0(n)

即fact(n)的時(shí)間復(fù)雜度為O(n)。

3.設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是()。［2011年聯(lián)考真題］

while(x<n.2)

x=2Xx；

A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)

【答案】A

【解析】其中，以基本的原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。題目中的基本運(yùn)算是語(yǔ)句

(n)

x=2xx,設(shè)其執(zhí)行時(shí)間為T(n),則有2T<n/2即T(n)<log2(n/2)=O(log2n)?

4.算法的計(jì)算量的大小稱為計(jì)算的()。［北京郵電大學(xué)2000研］

A.效率

B.復(fù)雜性

C.現(xiàn)實(shí)性

D.難度

【答案】B

【解析】算法復(fù)雜度通常分為時(shí)間復(fù)雜度和空間復(fù)雜度，算法的計(jì)算量的大小可以用時(shí)間復(fù)雜度衡量,

即可以稱為計(jì)算的復(fù)雜度。

5.下列說(shuō)法錯(cuò)誤的是()。［南京理工大學(xué)2000研］

(1)算法原地工作的含義是指不需要任何額外的輔助空間

(2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2D的算法

(3)所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界

(4)同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低

A.(1)

B.(1),(2)

C.(1),(4)

D.(3)

【答案】A

【解析】算法原地工作的含義不是指不需要任何額外的輔助,而是算法所需要的輔助空間不隨著問(wèn)題的

規(guī)模而變化，是一個(gè)確定的值。

6.以下屬于邏輯結(jié)構(gòu)的是()。

A.順序表

B.哈希表

C.有序表

D.單鏈表

【答案】C

【解析】數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)之

間關(guān)系的描述，與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、所含結(jié)點(diǎn)個(gè)數(shù)都無(wú)關(guān)。順序表、哈希表、單

鏈表都涉及到數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，有序表是指表中數(shù)據(jù)有序，與邏輯結(jié)構(gòu)無(wú)關(guān)。

7.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將其分為（）。［中南大學(xué)2005研］

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

【答案】D

【解析】數(shù)據(jù)結(jié)構(gòu)從邏輯上可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。常見的線性結(jié)構(gòu)為棧和隊(duì)列，非線性結(jié)構(gòu)

為樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。

8.一個(gè)算法應(yīng)該是（）。

A.程序

B.問(wèn)題求解步驟的描述

C.要滿足五個(gè)基本要求

D.A和C

【答案】B

【解析】程序不一定滿足有窮性，如死循環(huán)，操作系統(tǒng)等，而算法必須有窮。算法代表了對(duì)問(wèn)題求解步

驟的描述，而程序是算法在計(jì)算機(jī)上的特定實(shí)現(xiàn)。

9.數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系被稱為（）。［北京理工大學(xué)2005研］

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

B.數(shù)據(jù)的基本操作

C.程序的算法

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

【答案】D

10.下面程序段中，執(zhí)行S語(yǔ)句的次數(shù)為（）。

for（inti=l；i<=n；D

for（mtj?lj<=i;jj）

S;

A.n2

B.n2/2C.n

（n+1）

D.n(n+1)/2

【答案】D

【解析】i的變化范圍是從1到n,對(duì)于每個(gè)已確定值的i,j的變化范圍是從1到i,相當(dāng)于求一個(gè)公差為1的

等差數(shù)列1,2，…，n的前n項(xiàng)和，即：n(n+1)②

II.可以用()定義一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)。［中山大學(xué)2004研］

A.數(shù)據(jù)元素

B.數(shù)據(jù)對(duì)象

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

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

【答案】D

【解析】抽象數(shù)據(jù)類型可以定義一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)。包括數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系，以及可以

進(jìn)行的操作。

12.以下算法的時(shí)間復(fù)雜度()。

\bidfirn(intn)

(

inti-1;

While(ion)

}

A.0(n)

B.O(n2)

C.O(nlog2n)

D.O(logjn)

【答案】D

【解析】基本運(yùn)算為i=i*2,設(shè)其執(zhí)行時(shí)間為T(n),則2,⑴<=n,即T(n)<=log2n=D.O(log2n)

二、綜合題

1,已知一個(gè)整數(shù)序列,其中OVQ,,若存a,”7且,

則稱X為A的主元素。例如人(。-5.5),則稱5為主元素；又如.—》；*,一則A中沒有主元素。假設(shè)

A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元

素，則輸出該元素；否則輸出-1。要求：

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。

(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。［2013年聯(lián)考真題〕

解：(1)算法的策略是從前向后掃描數(shù)組元素,標(biāo)記出一個(gè)可能成為主元素的元素Num。然后重新計(jì)

數(shù)，確認(rèn)Num是否是主元素。

算法可分為以下兩步：

①選取候選的主元素；依次掃描所給數(shù)組中的每個(gè)整數(shù)，將第一個(gè)遇到的整數(shù)Num保存到c中，記錄

Num的出現(xiàn)次數(shù)為1；若遇到的下一個(gè)整數(shù)仍等于Num,則計(jì)數(shù)加1否則計(jì)數(shù)減1；當(dāng)計(jì)數(shù)減到0時(shí)，將遇

到的下一個(gè)整數(shù)保存到C中，計(jì)數(shù)重新記為1,開始新一輪計(jì)數(shù)，即從當(dāng)前位置開始重復(fù)上述過(guò)程，直到

掃描完全部數(shù)組元素。

②判斷c中元素是否是真正的主元素，再次掃描該數(shù)組，統(tǒng)計(jì)c中元素出現(xiàn)的次數(shù)，若大于n/2,則為主

元素；否則，序列中不存在主元素。

(2)算法實(shí)現(xiàn)如下：

mtM^ority(intA[],iiirn){

mti,c,count=l;c用來(lái)保存候選主元素，count用來(lái)計(jì)數(shù)

oA(0];設(shè)置A[。]為候選主元素

for>{查找候選壬元素

jfc)

count—;為A中的候選主元素計(jì)數(shù)

eles{

if(countX))處理不是候選壬元素的情況

count-;

elsM更換候選主元素

count=l;

)

)

)

if(count>0)

for(i-count-0,i<n,i-){統(tǒng)計(jì)候選王元素的實(shí)際出現(xiàn)次數(shù)

if(Ad)

count**;

)

if(counun2)確認(rèn)候選王元素

returnc;

else

return1;不存在主元素

)

(3)時(shí)間復(fù)雜度為0(n)，空間復(fù)雜度為0(1).

2閱讀下面的程序，指出過(guò)程pp完成的功能及結(jié)果數(shù)據(jù)結(jié)構(gòu)的名稱.并估計(jì)算法的時(shí)間復(fù)雜度

0(?),說(shuō)明理由。設(shè)單鏈表長(zhǎng)度為n。

C語(yǔ)言

Typedefcharelemtype；

Typedefstructnode

Elemtypekey：

Strcutnode*nextx

}node.?*link?

1inkla：

voidpp《linkp)；

if(p)

pp(p->next)sp-next=lanext：

la->next=p$la=p：

}returnj

main()

1inkqj

建立用la指出的帶頭結(jié)點(diǎn)的單鏈長(zhǎng):

q=lanext；lanext=la；pp<q)；

輸出用la指出的總式結(jié)構(gòu)的數(shù)據(jù)兒索；

return1：

答：(1)程序的功能是將單鏈表逆置;

(2)結(jié)果數(shù)據(jù)結(jié)構(gòu)為存入一個(gè)帶頭結(jié)點(diǎn)、用尾指針表示的單向循環(huán)鏈表；

(3)算法時(shí)間復(fù)雜度為O(n)o理由：因?yàn)榇顺绦蛲ㄟ^(guò)遞歸方法達(dá)到單鏈表的逆置，遞歸深度與表的

節(jié)點(diǎn)數(shù)相當(dāng)，回退時(shí)處理插入，每層復(fù)雜度為0(1),故總的復(fù)雜度為O(n)。

第2章線性表

一、線性表的定義和操作

1.線性表的定義

線性表(LinearList)：是由n(nSO)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a］，a2,…an組成的有限序列。該序列中的

所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度。

當(dāng)n=O時(shí)，稱為空表。

當(dāng)n>0時(shí)，將非空的線性表記作：L=(aPa2,...an),其中a1稱為線性表的第一個(gè)(首)結(jié)點(diǎn)，an稱為

線性表的最后一個(gè)(尾)結(jié)點(diǎn)。a,,a2,…a^i都是由(2WiWn)的前驅(qū)，其中a”是為的直接前驅(qū)：ai+P

aj+2，…an都是aj(1=i=n-l)的后繼，其中西+L是aj的直接后繼。

2.線性表的基本操作

一個(gè)數(shù)據(jù)結(jié)構(gòu)的基本操作是指其最核心、最基本的操作。其它較為復(fù)雜的操作可以通過(guò)調(diào)用基本操作來(lái)

實(shí)現(xiàn)。線性表的主要操作如下：

InitList(&L)初始化線性表：構(gòu)造一個(gè)空的線性表L。

DestroyList(&L)銷毀線性表：釋放線性表L占用的內(nèi)存空間。

LislEmpty(L)判斷線性表是否為空表：若L是空表，則返回真，否則返回假。

ListLength(L)求線性表長(zhǎng)度：返回L中元素的個(gè)數(shù)。

DispList(L)輸出線性表：當(dāng)線性表L不為空時(shí)，順序顯示L的各結(jié)點(diǎn)的值域。

GetElem(L,i,&e)求線性表L中指定位置的某個(gè)元素：用e返回L中第i(1WiWListLength(L))個(gè)

元素的值。

LocateElem(L,e)定位查找：返回L中第1個(gè)值域與e相等的為序。不存在則返回0。

Listinsert(&L,i,e)插入數(shù)據(jù)元素：在L的第i(1SiSListLength(L)+1)個(gè)元素之前插入新的元素

e,L的長(zhǎng)度增加1。

ListDelete(&L,i,&e)刪除數(shù)據(jù)元素：刪除L的第i(1二iWListLength(L))個(gè)元素，并用e返回其

值，L的長(zhǎng)度減少1。

二、線性表的實(shí)現(xiàn)

1.順序存儲(chǔ)

(1)線性表的順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)就是把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一塊地址連續(xù)的存儲(chǔ)單元里。用這種

方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。

順序存儲(chǔ)的線性表的特點(diǎn)：

①線性表的邏輯順序與物理順序一致。

②數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰''來(lái)體現(xiàn)。

假設(shè)線性表存儲(chǔ)的起始位置是LOC(A),元素類型為ElemType,則每個(gè)元素所占用存儲(chǔ)空間的大小

(即字節(jié)數(shù))為sizeof(ElemType),整個(gè)線性表所占用存儲(chǔ)空間的大小為n*sizeof(ElemType)，其

中，n表示線性表的長(zhǎng)度。線性表的存儲(chǔ)如圖1-1所示。

下標(biāo)位置線性表存儲(chǔ)空間存儲(chǔ)地址

0LOC(A)

LOC(A)+sizeofi(ElemType)

LOC(A)+<i-l)*sizeof(EfemType)

LOC(A)+(n-l)*sizeof(ElemType)

MaxSize-1LOC(A)+(MaxSize-1)*sizeof(IkmType)

圖1-1線性表的順序存儲(chǔ)結(jié)構(gòu)

為在邏輯序列中的位置稱為邏輯位序，在順序表中的位置稱為物理位序。

在定義一個(gè)線性表的順序存儲(chǔ)類型時(shí)，需要定義一個(gè)數(shù)組來(lái)存儲(chǔ)線性表中的所有元素和定義一個(gè)整型變

量來(lái)存儲(chǔ)線性表的長(zhǎng)度。

假定數(shù)組用data[MaxSize]表示，長(zhǎng)度整型變量用length表示，并采用結(jié)構(gòu)體類型表示，則元素類型為通用

類型標(biāo)識(shí)符:ElemType的線性表的順序存儲(chǔ)類型可描述如下：

sdefineOK1

^defineERROR-1

defineMAX_SIZE100

n-pedefmtStatus;

typedefstructsqlist

(

ElemlXpeElem_anay(\IAX_SIZEJ;

intlength;

}SqList;

其中，Elem_array成員存放元素，length成員存放線性表的實(shí)際長(zhǎng)度。

(2)順序表的基本操作

由于順序表的操作比較簡(jiǎn)單，在這里只給出建立、插入、刪除和按值查找的操作的算法。

①建立順序表

其方法是將給定的含有n個(gè)元素?cái)?shù)組的每個(gè)元素依次放入到順序表中，并將n賦給順序表的長(zhǎng)度成員。算

法如下：

voidCreateList(SqList*<S:L,ElemTypea[],mtn)

*建立順序表.

(

inti;

L-(SqList?)malloc(sizeof(SqList));為順序表分配存儲(chǔ)空間

for—)

L->length=n;

}

②插入操作

該運(yùn)算在順序表L的第i個(gè)位置(iWiWListLength(L)+1)上插入新的元素e。

思路：如果i值不正確，則顯示相應(yīng)錯(cuò)誤信息；否則將順序表原來(lái)第i個(gè)元素及其后面元素均后移一個(gè)位

置，騰出一個(gè)空位置插入新元素，順序表長(zhǎng)度增1。

StatusInsert_SqList(Sqlist*L,inti,Eieml^pee)

(

inrj;

if(i<li>L->length)

returnERROR;

if(L->length>-MAX_SIZE)

(

printf(“線性表溢出!n”)；

returnERROR;

)

for(j=L->length-1:j>=i:-j)

L->Eiem_array[j-l]=L->Elem_array[j]：

*i位置以后的所有結(jié)點(diǎn)后移*

L->Elem_ana>li-1]-e,

*在1位*插入結(jié)點(diǎn)*

L->length—;

returnOK,

在線性表L中的第i個(gè)位置插入新結(jié)點(diǎn)，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移

動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。

設(shè)在線性表L中的第i個(gè)位置插入結(jié)點(diǎn)的概率為R,不失一般性，設(shè)各個(gè)位置插入是等概率，則Pi=l/

(n+1),而插入時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i+10

總的平均移動(dòng)次數(shù)：

即在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算?/p>

的平均時(shí)間復(fù)雜度為O(n)。

③刪除操作

刪除順序表L中的第i(l<i<ListLength(L))個(gè)元素。

思路：如果i值不正確，則顯示相應(yīng)錯(cuò)誤信息；否則將線性表第i個(gè)元素及其后面元素均向前移動(dòng)一個(gè)位

置，這樣覆蓋了原來(lái)的第i個(gè)元素，達(dá)到刪除該元素的目的，最后順序表長(zhǎng)度減1。

ElemTypeDel?e_SqList(Sqlist*L,inti)

(

mtk;

Elemiypex;

if(L->length?-0)

(

prrntf(“線性表L為空!n”),

returnERROR;

}

elseif(i<l；|i>L->length)

(

pnntf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!n”)；

returnERROR;

x=L->Elem_array-[i-l]:*保存結(jié)點(diǎn)的值*

for(k-i;k<L->length;k**)

L->E!em_array[k-1卜L->Elem_anay[k];

*?位重以后的所有結(jié)點(diǎn)前看*

L->length—;

return(x);

刪除線性表L中的第i個(gè)元素，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)

算法的時(shí)間復(fù)雜度。

設(shè)在線性表L中刪除第i個(gè)元素的概率為B，不失一般性，設(shè)刪除各個(gè)位置是等概率，則Pj=l/n,而刪除

時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i。

則總的平均移動(dòng)次數(shù)：

v-1,1、1>：-1

Er=2P.5-1n)=_-(>3-1)=―；-=

>1>17~~

即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算?/p>

的平均時(shí)間復(fù)雜度為O(n)。

④按值查找

該運(yùn)算順序查找第1個(gè)值與e相等的元素的位序。若這樣的元素不存在，則返回值為0。

intLocateElem(SqList*L,Elemlypee)

(

inti-0;

while(i<L->length&&L->data[i]!-e)

if

if(i>-L->length)

return0:

else

returni-1;

}

假設(shè)Pi(Pi=l/n)是查找元素在第i個(gè)位置上的概率，則在長(zhǎng)度為n的線性表中查找值為e的元素所需要比

較的平均次數(shù)為：

因此，線性表按值查找算法的平均時(shí)間復(fù)雜度為O(n)。

2.鏈?zhǔn)酱鎯?chǔ)

(1)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性

表簡(jiǎn)稱線性鏈表。

在鏈?zhǔn)酱鎯?chǔ)中，每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅包含所存元素本身的信息(稱之為數(shù)據(jù)域)，而且還需包含元素之間

邏輯關(guān)系的信息，比如前驅(qū)結(jié)點(diǎn)包含后繼結(jié)點(diǎn)的地址信息，這稱為指針域，這樣可以通過(guò)前驅(qū)結(jié)點(diǎn)的指

針域很方便地找到后繼結(jié)點(diǎn)的位置，提高數(shù)據(jù)查找速度。

一般地，每個(gè)結(jié)點(diǎn)都有一個(gè)或多個(gè)這樣的指針域。若一個(gè)結(jié)點(diǎn)中的某個(gè)指針域不需要任何結(jié)點(diǎn)，則僅它

的值為空，用常量NULL表示。

為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)(頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的

數(shù)據(jù)域可以不存儲(chǔ)任何信息(或鏈表長(zhǎng)度等信息)。

(2)單鏈表

由于順序表中的每個(gè)元素至多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素，即數(shù)據(jù)元素之間是一對(duì)一的邏輯關(guān)

系，所以當(dāng)進(jìn)行鏈?zhǔn)酱鎯?chǔ)時(shí)，一種最簡(jiǎn)單也最常用的方法是：

在每個(gè)結(jié)點(diǎn)中除包含有數(shù)據(jù)域外，只設(shè)置一個(gè)指針域，用以指向其后繼結(jié)點(diǎn)，這樣構(gòu)成的鏈接表稱為線

性單向鏈接表，簡(jiǎn)稱單鏈表。帶頭結(jié)點(diǎn)的單鏈表如圖1-2所示。

頭結(jié)點(diǎn)開始結(jié)點(diǎn)終端結(jié)點(diǎn)

headT|a/-Ha?|->|ar|A|

圖1-2帶頭結(jié)點(diǎn)的單鏈表單

鏈表中結(jié)點(diǎn)類型描述為：

typedefstructLnode

(

El?nT\pedata.啜據(jù)域，保存結(jié)點(diǎn)的值*

structLnode*next;*指針域*

}LNode;逐點(diǎn)的類型*/

單鏈表中基本操作為：

①建立單鏈表

假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是整型，以32767作為結(jié)束標(biāo)志。假設(shè)我們通過(guò)一個(gè)含有n個(gè)數(shù)據(jù)的數(shù)組來(lái)

建立單鏈表。建立單鏈表的常用方法有如下兩種：

a.頭插法建表

從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插

入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。即每次插入的結(jié)點(diǎn)都作為鏈表的第一個(gè)結(jié)點(diǎn)。

LNode*creaie_LinkList(void)

*頭插入法?建單道表,捱表的擔(dān)點(diǎn)head作為返回值*

(

intdata;

LNode*head,*p;

head-(LNode*)malloc(sizeof(INode));

head->next-NULL;*創(chuàng)建i鰥的表頭結(jié)點(diǎn)head*

while(1)

(

scanf("*?d",&dau).

if(data-32767)

break;

p-(LNode*)malloc(sizeof(LNode));

p->data-data;*數(shù)據(jù)i/值*

p->next-head->next;

head->next-p;

廣構(gòu)施，新創(chuàng)建幅點(diǎn)總是作為第一個(gè)結(jié)點(diǎn)*

)

return(head);

}

b.尾插法建表

頭插入法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一

致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，使其成為當(dāng)前鏈表的尾結(jié)點(diǎn)。

LNode*create_L4nkList(void)

*尾插入法制0單漣表，道表的頭結(jié)點(diǎn)head作為返回值*

(

intdata;

LNode*head,*p,*q;

head-p-(INode*)malloc(sizeof(LNode));

p->next-NULL;?創(chuàng)建單道表的表頭結(jié)點(diǎn)head?

while(1)

{

scanf(,&data);

if(data=32767)

break,

q?(INode")malloc(sizeof(LNode〉)；

q->data=data;*數(shù)據(jù)域賦值*

q->next=p->next:

p->next=qT

p-q；

*構(gòu)漣，新創(chuàng)建的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)*

}

return(head);

)

無(wú)論是哪種插入方法，如果要插入建立的單線性鏈表的結(jié)點(diǎn)是n個(gè)，算法的時(shí)間復(fù)雜度均為O(n)。

②單鏈表查找

a.按序號(hào)查找

即取單鏈表中的第i個(gè)元素。

對(duì)于單鏈表，不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭結(jié)點(diǎn)出發(fā)，沿鏈域next逐個(gè)

結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。

設(shè)單鏈表的長(zhǎng)度為n,要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)IWiWn時(shí)，i的值是合法的。

Elemly-peGet_Elan(LNode*L,inri)

(

intj;

LNode*p;

p-L->next;

jT；產(chǎn)使P指向第一個(gè)結(jié)點(diǎn).

while(p!-NULL&&j<i)

(

p-p->next;

)?移朝旨針p.j計(jì)數(shù)*

if(j!-i)

return(-32768);

else

return(p->data);

*p為NULL表示i太大;j>i表示i為0.

)

按序號(hào)查找單鏈表的時(shí)間復(fù)雜度為O(n)。

b.按值查找

按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)。若有，則返回首次找到的值為key的結(jié)

點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找時(shí)從開始結(jié)點(diǎn)出發(fā)，沿鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。

LNode*Locate_Node(LNode,L:mtkey)

?在以L為誦點(diǎn)的單道表中查找值為key?的第一個(gè)結(jié)點(diǎn)?

(

LNode*p=L->next;

while(p!?NULL±&p->data*-key)

p-p->nexi,

if(p-xlau-kejO

returnp;

else

(

pnntf("所要查找儲(chǔ)點(diǎn)不存在!!；

return(NULL).

}

)

算法的執(zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。

③單鏈表的插入

插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ar與比之間。因此，必須首先找

到為」所在的結(jié)點(diǎn)p,然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q,q結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)。

voidInsert_LNode(LNode*L,mti,ElemI>pee)

*在以1為頭結(jié)點(diǎn)的單薄表的第1個(gè)位置插入值為e儲(chǔ)點(diǎn)*

(

intj-O;

LNode*p,*q;

p?L->next;

while(p!-MULL&&j<i-l)

(

p-p->next;

j**；

)

if(j!?i-l)

prmtfLi太大或訪0!!n”；

else

(

q-(LNode*)malloc(sizeof(LNode));

q->data?e;

q->next??p->next;

p->next=q;

)

}

設(shè)鏈表的長(zhǎng)度為n,合法的插入位置是IWiWn。算法的時(shí)間主要耗費(fèi)移動(dòng)指針p上，故時(shí)間復(fù)雜度亦為

0(n)。

④單鏈表的刪除

a.按序號(hào)刪除

刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。

為了刪除第i個(gè)結(jié)點(diǎn)為，必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)?！沟膎ext域中，因

此，必須首先找到ar的存儲(chǔ)位置p,然后令p->next指向西的直接后繼結(jié)點(diǎn)，即把可從鏈上摘下。最后釋放

結(jié)點(diǎn)研的空間，將其歸還給“存儲(chǔ)池

設(shè)單鏈表長(zhǎng)度為n,則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)lWi=n時(shí)是合法的。則當(dāng)i=n+l時(shí)，雖然被刪結(jié)點(diǎn)不存在，但

其前趨結(jié)點(diǎn)卻存在，是終端結(jié)點(diǎn)。故判斷條件之一是p->next!=NULL。

voidDelete_LinkList(LNodeeL,inti)

*刪除為嵋點(diǎn)的單道表中的第i個(gè)結(jié)點(diǎn)*

(

intj-1;

LNode*p,*q;

P=L；

q=L->next;

while(p->next!=NVLL&4fcj<i)

(

p-q；

q*q->next;

)

if(j!-i)

printf(一太大或i為0!!W);

else

{

p->next=q->nexti

free(q);

}

)

b,按值刪除

刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。

與按值查找相類似，首先要查找值為key的結(jié)點(diǎn)是否存在？若存在，則刪除；否則返回NULL。

voidDelete_LinkList(LNode*L,mtkey)

*刪除以工為脂點(diǎn)的單繪表中值為key的第一個(gè)結(jié)點(diǎn)*

(

LNode*p?L,*q=L->next;

while(q!?NULL&&q->dara!=key)

(

L；

q-q->next;

)

if(q->data—ke>>)

(

p->next?q->next;

free<q);

}

else

prmtf("所要JU除留給點(diǎn)不存在!！n")；

}

單鏈表的刪除結(jié)點(diǎn)時(shí)間都耗費(fèi)在查找結(jié)點(diǎn)的操作上。時(shí)間復(fù)雜度為O(n)。

⑤求表長(zhǎng)

返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

intListLength(LmkList*L)

(

LmkList*p=L;inti=0;

while(p->next?-NULL)

(

i**；

p?p->nect;

}

return(i);

}

時(shí)間復(fù)雜度為0(n)。單鏈表的長(zhǎng)度不包括頭結(jié)點(diǎn)。

【例】已知指針P所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*P之后插入結(jié)點(diǎn)*S,則應(yīng)執(zhí)行下列哪一個(gè)操作

()O

A.S->NEXT=P；P->NEXT=S；

B.S->NEXT=P->NEXT；P->NEXT=S；

C.S->NEXT=P->NEXT；P=S；

D.P->NEXT=S；S->NEXT=P；

【答案】B

【解析】插入結(jié)點(diǎn)S是的情況如下圖所示：在斷開P—>next之前必須先將S—>next指向P的直接后繼，否則

由于是單鏈表結(jié)構(gòu)，會(huì)無(wú)法找到P的后繼結(jié)點(diǎn)，然后才能將P的直接后繼修改為S。

(3)循環(huán)鏈表

循環(huán)鏈表就是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指

針域鏈接成一個(gè)環(huán)。圖1-3是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖。

headhead____________

等空表

圖L3單循環(huán)鏈表

從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。

對(duì)于單循環(huán)鏈表，基本操作都跟單鏈表差不多，僅僅需要在單線性鏈表操作算法基礎(chǔ)上做以下修改：

①判斷是否為空鏈表?xiàng)l件改為：head->next==head;

②判斷是否為表尾結(jié)點(diǎn)條件改為：p->next==head?

(4)雙向鏈表

雙向鏈表指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior,一個(gè)指向

其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。其結(jié)點(diǎn)形式如圖

1一4所示。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。帶頭結(jié)點(diǎn)的

雙向鏈表如圖1-5所示。

|prior|data|next|

圖1-4雙向鏈表結(jié)點(diǎn)形式

hea<Jhead

空雙向能妻非電雙向鏈表

圖1-5帶頭結(jié)點(diǎn)的雙向鏈表

雙鏈表中結(jié)點(diǎn)的類型定義描述如下：

typedefstructDuinode

(

ElemT>-pedata;

stmctDuinodeapnor「next:

JDulNode;

雙向鏈表結(jié)構(gòu)具有對(duì)稱性，設(shè)p指向雙向鏈表中的某一結(jié)點(diǎn)，則其對(duì)稱性可用下式描述：

(p->prior)->next=p=(p->next)->prior;

點(diǎn)p的存儲(chǔ)位置存放在其直接前趨結(jié)點(diǎn)p->prior的直接后繼指針域中，同時(shí)也存放在其直接后繼結(jié)點(diǎn)p-

>next的直接前趨指針域中。

雙向鏈表的操作

①雙向鏈表的插入

將值為e的結(jié)點(diǎn)插入雙向鏈表中。插入前后鏈表的變化如圖1-6所示。

,上~一r，，，，

|a,-=naT"lI加k

息

圖1-6雙向鏈表的插入

a.插入時(shí)僅僅指出直接前驅(qū)結(jié)點(diǎn)，鉤鏈時(shí)必須注意先后次序是：“先右后左部分語(yǔ)句組如下：

S=(DulNode*)malloc(sizeof(DulNode));

S->data=e;

S->next-p->next;

p->next->pnor-S,

p->next?S;

Aprimp;尸翎聯(lián)淵陶重要*

b.插入時(shí)同時(shí)指出直接前驅(qū)結(jié)點(diǎn)p和直接后繼結(jié)點(diǎn)q,鉤鏈時(shí)無(wú)須注意先后次序。部分語(yǔ)句組如下：

S=(DulNode?)malloc(sizeof(DulNode));

S->dat^e;

p->next?S;

S->next-q;

S->prior-p,

q->pnor3gS;

②雙向鏈表的結(jié)點(diǎn)刪除

設(shè)要?jiǎng)h除的結(jié)點(diǎn)為p,刪除時(shí)可以不引入新的輔助指針變量，可以直接先斷鏈，再釋放結(jié)點(diǎn)。部分語(yǔ)句

組如下：

p->prior->next=p->next;

p->next->prior-p->pnor;

笈ee(p)；

與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針域的指

向。

(5)靜態(tài)鏈表

靜態(tài)鏈表借用一維數(shù)組來(lái)描述線性鏈表。數(shù)組中的一個(gè)分量表示一個(gè)結(jié)點(diǎn)，同時(shí)使用游標(biāo)(指示器cur

即為偽指針)代替指針以指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置。數(shù)組中的第0個(gè)分量可以看成頭結(jié)點(diǎn)，其指針

域指示靜態(tài)鏈表的第一個(gè)結(jié)點(diǎn)。

這種存儲(chǔ)結(jié)構(gòu)仍然需要預(yù)先分配一個(gè)較大空間，但是在進(jìn)行線性表的插入和刪除操作時(shí)不需要移動(dòng)元

素，僅需要修改“指針”，因此仍然具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn)。

【例】如果對(duì)含有n(n>l)個(gè)元素的線性表的運(yùn)算只有4種：刪除第一個(gè)元素，刪除最后一個(gè)元素，在

第一個(gè)元素前面插入新元素，在最后一個(gè)元素的后面插入新元素，則最好使用()。

A.只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的循環(huán)單鏈表

B.只有尾結(jié)點(diǎn)指針沒有頭結(jié)點(diǎn)指針的非循環(huán)單鏈表

C.只有頭結(jié)點(diǎn)指針沒有尾結(jié)點(diǎn)指針的循環(huán)單鏈表

D.既有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表

【答案】C

【解析】對(duì)于A項(xiàng)的鏈表，刪除最后一個(gè)結(jié)點(diǎn)P時(shí)，需要找到P的前一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(n)；

對(duì)于B項(xiàng)的鏈表，刪除第一個(gè)結(jié)點(diǎn)的P時(shí)，需找到頭結(jié)點(diǎn)，這里沒給出頭結(jié)點(diǎn)指針，故無(wú)法實(shí)現(xiàn)這種操

作。

對(duì)于C項(xiàng)的鏈表，這4種操作的時(shí)間復(fù)雜度都為0(1)。

對(duì)于D項(xiàng)的鏈表，刪除最后一個(gè)結(jié)點(diǎn)P時(shí)，需要找到P的前一個(gè)結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(n)。

3.線性表的應(yīng)用

(1)一元多項(xiàng)式的表示

2n

一元多項(xiàng)式p(x)=p()+p|X+p2x+...+pnx,由n+1個(gè)系數(shù)唯一確定。則在計(jì)算機(jī)中可用線性表

(P0，Pl，P2,...,Pn)表示。既然是線性表，就可以用順序表和鏈表來(lái)實(shí)現(xiàn)。兩種不同實(shí)現(xiàn)方式的元素類型

定義如下：

①順序存儲(chǔ)表示的類型

typcdefstruct

(

floatcoef;?系數(shù)部分?

mtexpo;嘴數(shù)部分?

}Elemiype;

②鏈?zhǔn)酱鎯?chǔ)表示的類型

typedefstructploy

(

floatcoef,?系數(shù)部分"

intexpo;?指數(shù)部分?

structployenext,

}Ploy;

(2)一元多項(xiàng)式相加

①順序存儲(chǔ)的一元多項(xiàng)式相加

線性表的定義

typedefstruct

(

Elemiypea[MAX_SIZE];

intlength;

}Sqlist;

用順序表表示則相加非常簡(jiǎn)單。訪問(wèn)第5項(xiàng)可直接訪問(wèn)：L.a[4].coef,L.a[4].expn

②鏈?zhǔn)酱鎯?chǔ)表示的一元多項(xiàng)式相加

當(dāng)采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，根據(jù)結(jié)點(diǎn)類型定義，凡是系數(shù)為0的項(xiàng)不在鏈表中出現(xiàn)，從而可以大大減少鏈

表的長(zhǎng)度。

一元多項(xiàng)式相加的實(shí)質(zhì)是：指數(shù)不同時(shí)是鏈表的合并；指數(shù)相同時(shí)系數(shù)相加，和為0,去掉結(jié)點(diǎn)，和不

為0,修改結(jié)點(diǎn)的系數(shù)域。

現(xiàn)在提供一種算法，在原來(lái)兩個(gè)多項(xiàng)式鏈表的基礎(chǔ)上進(jìn)行相加，相加后原來(lái)兩個(gè)多項(xiàng)式鏈表就不再存

在。當(dāng)然再要對(duì)原來(lái)兩個(gè)多項(xiàng)式進(jìn)行其它操作就不允許了。

Ploy*add_J)toy(ploy*La.ploy*Lb)

*將以La,Lb為頭指針裘示的一元多項(xiàng)式相腑

(

ploy*Le.*pc,,p%*pb,*ptr.

finatx;

Lo=po=La;

pa-La->next:

pLb->next;

while(pal-NULL&&pb;-NULL)

(

if(pa->^pn<pb->expn)

(

pc->next=pa;

po=pa;

pa-pa->next;

}

，“將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)火

if(pa->cxpn>pb->expn)

(

pc->n這可b;

pv=pb;

ppb->nexl;

else

(

x-pa->coef+pb->coef:

if(abs(x)<-1.0e-6)

*如果系韻和為0.刪除兩個(gè)結(jié)點(diǎn)*

{

PtP=pa-

pa"Ja->nexi:

free(ptr):p

扛可)b;

pbaapb->next;

free(ptr):

)

else*如果系防和不為O,修改其中一個(gè)結(jié)點(diǎn)的系數(shù)域，刪除另一個(gè)蕪點(diǎn)*

(

pc->next=pa;

pa->coef=x;

pc=pa;

pa41a->next:

ptr=pb:

pb=pl>->next;

fr(pb):

}*endofwhile*

if(pa=NULL)

pc->next=pb;

else

pc->nexl叩a:

return(Le)；

J

練習(xí)題一、單項(xiàng)選擇題

1.已知兩個(gè)長(zhǎng)度分別為m和n的升序鏈表，若將它們合并為一個(gè)長(zhǎng)度為m+n的降序鏈表，則最壞情況下

的時(shí)間復(fù)雜度是()。［2013年聯(lián)考真題］

A.O(n)B.O

(m*n)C.O(min

(m,n))D.O

(max(m,n))

【答案】D

【解析】m