第2基本數(shù)據(jù)結(jié)構及其運算

2.1數(shù)據(jù)結(jié)構的基本概念

22線性表

2?3棧及其應用

2.4隊列及其應用

25線性鏈表

26數(shù)組與字符串

27樹與二叉樹

28圖

25索弓］存儲結(jié)構

數(shù)據(jù)是計算機化的信息，即計算機處

理的對象是數(shù)據(jù)。

各數(shù)據(jù)之間的一定關系，稱為數(shù)據(jù)的

邏輯結(jié)構，數(shù)據(jù)在計算機中的存儲位置有

著一定的關系，稱為數(shù)據(jù)的物理結(jié)構（或

存儲結(jié)構）。

V冏〉同

數(shù)據(jù)結(jié)構作為計算機的一門學科，它

研究的內(nèi)容，通常要涉及以下三個方面的

問題:

①數(shù)據(jù)的邏輯結(jié)構;

②數(shù)據(jù)的存儲結(jié)構;

③對各種數(shù)據(jù)結(jié)構進行的運算。

V冏〉同

主要目的是為了提高數(shù)據(jù)處理的效

包括兩個方面：一是提高數(shù)據(jù)處理

的速度，二是盡量節(jié)省在數(shù)據(jù)處理過程

中所占用的計算機存儲空間。

V冏〉同

2.1數(shù)據(jù)結(jié)構的基本概念

數(shù)據(jù)結(jié)構是指相互有關聯(lián)的數(shù)據(jù)元素

的集合。

組成該數(shù)據(jù)結(jié)構（包括邏輯結(jié)構和存

儲結(jié)構）的數(shù)據(jù)元素稱為一個結(jié)點。

在數(shù)據(jù)處理領域中，每一個需要處理

的對象都可以抽象成數(shù)據(jù)元素。

在具有相同特征的數(shù)據(jù)元素集合中,

各個數(shù)據(jù)元素之間存在有某種關系，反映

了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構。

數(shù)據(jù)元素之間的任何關系都可以用前

后件關系來描述。

V冏〉同

Hl.數(shù)據(jù)的邏輯結(jié)構

所謂結(jié)構實際上就是指數(shù)據(jù)元素之間

的前后件關系。

一個數(shù)據(jù)結(jié)構應包含以下兩方面的信

息：

①表示數(shù)據(jù)元素的信息。

②表示各數(shù)據(jù)元素之間的前后件關系

的信息。

V冏〉同

數(shù)據(jù)元素之間的前后件關系是指它們

的邏輯關系，而與它們在計算機中的存儲

位置無關。

數(shù)據(jù)結(jié)構實際上是數(shù)據(jù)的邏輯結(jié)構。

數(shù)據(jù)的邏輯結(jié)構，是指反映數(shù)據(jù)元素

之間邏輯關系的數(shù)據(jù)結(jié)構。

V冏〉同

數(shù)據(jù)的邏輯結(jié)構有兩個要素：一是數(shù)

據(jù)元素的集合，通常記為D；二是）上的

關系，它反映了D中各數(shù)據(jù)元素之間的前

后件關系，通常記為

即一個數(shù)據(jù)結(jié)構可以表示成

B=(O/?)

V冏〉同

例2.3〃維向量

X=仕142,???內(nèi)〃)

也是一種數(shù)據(jù)結(jié)構。即X=(O,A),其

中數(shù)據(jù)元素的集合為：

D="142,???2}

關系為：

R={(xl5x2),(x25x3)5...,(xn一\^xn)}

V冏〉同

例如，/MX〃的矩陣

???

?■?

A=

???

求黑

WV合〉以

是一個數(shù)據(jù)結(jié)構。在這個數(shù)據(jù)結(jié)構中,

矩陣的每一行

Ai=(ail,ail，

可以看成是它的一個數(shù)據(jù)元素。即這

個數(shù)據(jù)結(jié)構的數(shù)據(jù)元素的集合為：

D={Al,A2,…，Am}

D上的一個關系為：

A={(NLA2),(A2,A3),

i+1),...Am-1,Am}}

V冏〉同

顯然，數(shù)據(jù)結(jié)構A中的每一個數(shù)據(jù)元

素士（i=1,2,…切）又是另一個數(shù)據(jù)結(jié)構,

即數(shù)據(jù)元素的集合為：

Di={ailj山2,…，ain}

。上的一個關系為：

Ai={（〃〃，山2）,（山2,山3）,…，（山,

(ai,n-1,ain)}

一個數(shù)據(jù)結(jié)構除了用二元關系表示外,

還可以直觀地用圖形表示。

V冏〉同

.秋-----------?冬

圖2.1一年四季數(shù)據(jù)結(jié)構的圖形表示

反映家庭成員間輩份關系的數(shù)據(jù)結(jié)構

可以用圖2.2所示的圖形表示。

例2.4用圖形表示數(shù)據(jù)結(jié)構6=(D,

R),其中

D={di\l<i<7}={dl."2,d3,d4,

d5,d6,dl}

R={(dl,〃3),("1,d7),(d2,"4),

(d3,d6),(d4,〃5)}

這個數(shù)據(jù)結(jié)構的圖形表示如圖2.3所示。

9

小輾1整利

心

A

d.

S23例2.4數(shù)據(jù)結(jié)構的圖形表示

在數(shù)據(jù)結(jié)構中，沒有前件的結(jié)點稱為

根結(jié)點；沒有后件的結(jié)點稱為終端結(jié)點

（也稱為葉子結(jié)點）。

通常，一個數(shù)據(jù)結(jié)構中的元素結(jié)點可

能是在動態(tài)變化的。

數(shù)據(jù)結(jié)構中的結(jié)點（即數(shù)據(jù)元素）個

數(shù)在動態(tài)地變化，而且，各數(shù)據(jù)元素之間

的關系也有可能在動態(tài)地變化。

V冏〉同

如果在一個數(shù)據(jù)結(jié)構中一個數(shù)據(jù)元

素都沒有，則稱該數(shù)據(jù)結(jié)構為空的數(shù)據(jù)

結(jié)構。

在一個空的數(shù)據(jù)結(jié)構中插入一個新

的元素后就變?yōu)榉强?；在只有一個數(shù)據(jù)

元素的數(shù)據(jù)結(jié)構中，將該元素刪除后就

變?yōu)榭盏臄?shù)據(jù)結(jié)構。

W,

將數(shù)據(jù)結(jié)構分為兩大類型：線性結(jié)構

與非線性結(jié)構。

如果一個非空的數(shù)據(jù)結(jié)構滿足下列兩

個條件：

①有且只有一個根結(jié)點；

②每一個結(jié)點最多有一個前件，也最

多有一個后件。

則稱該數(shù)據(jù)結(jié)構為線性結(jié)構。

,線性結(jié)構又稱線性表。

V冏〉同

例如，圖2.4所示的數(shù)據(jù)結(jié)構顯然是滿

足上述兩個條件的，但它不屬于線性結(jié)構

這個類型，因為如果在這個數(shù)據(jù)結(jié)構中刪

除結(jié)點A后，就不滿足上述的條件①。

V冏〉同

B----------------C."-------------------kD

圖2.4不是線性結(jié)構的數(shù)據(jù)結(jié)構特例

一個數(shù)據(jù)結(jié)構不是線性結(jié)構，則稱之

為非線性結(jié)構。

線性結(jié)構與非線性結(jié)構都可以是空的

數(shù)據(jù)結(jié)構。

如果對該數(shù)據(jù)結(jié)構的運算是按線性結(jié)

構的規(guī)則來處理的，則屬于線性結(jié)構；否

則屬于非線性結(jié)構。

9

小輾1整利

一個數(shù)據(jù)結(jié)構中的各數(shù)據(jù)元素在計算

機存儲空間中的位置關系與邏輯關系是有

可能不同的。

數(shù)據(jù)的邏輯結(jié)構在計算機存儲空間中

的存放形式稱為數(shù)據(jù)的存儲結(jié)構。

V冏〉同

在數(shù)據(jù)的存儲結(jié)構中，不僅要存放各

數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素

之間的前后件關系的信息。

常用的存儲結(jié)構有順序、鏈接、索弓

散列等存儲結(jié)構。

V冏〉同

@(1)順序存儲結(jié)構

順序存儲結(jié)構主要用于線性結(jié)構。在

這種存儲方式中，把邏輯上相鄰的數(shù)據(jù)元

素結(jié)點存儲在物理上相鄰的存儲單元中，

各結(jié)點之間的關系由存儲單元的鄰接關系

來體現(xiàn)。

圖2.5是將線性結(jié)構｛(KLK2),(K2,

K3),(K3,K4),(K4,K5),(K5,K6),

(K6,K7)｝順序地存放在存儲單元中的示

觸董圖。

V冏〉同

圖2.5順序存儲結(jié)構存儲線性結(jié)構示意圖

0(2)鏈接存儲結(jié)構

在鏈接存儲結(jié)構中，每個存儲結(jié)

點要有兩部分組成：一部分用于存放

數(shù)據(jù)信息，另一部分用于存放指針。

其中指針用于指向該結(jié)點的前件

或后件。

V冏〉同

地址

2000

2001

2002

20?0?3

2004

2005

2006

2007

2008

32.6鏈接存儲結(jié)構存儲線性結(jié)構示意圖

利用鏈接存儲方式也可以存儲非線性

結(jié)構。

圖2.7(a)和(b)分別為一棵二叉樹

的邏輯結(jié)構與鏈接存儲結(jié)構的示意圖。

V冏〉同

地址.左指針信息右指針

2000AIG2006

,君2001AK3A

方12002

./\2003

K2K32004

\20052007K32000?R

/\\2006AK3A

伍2007

K4K62001K32008

2008AK3A

(b)

圖2.7鏈接存儲結(jié)構存儲二叉樹邏輯結(jié)構示意圖

0(3)索引存儲結(jié)構

索引存儲結(jié)構是指將數(shù)據(jù)元素按索引

函數(shù)值進行分組，具有相同索引函數(shù)值的

數(shù)據(jù)元素被分在同一組中，而同一組中的

元素再按某種存儲方式(順序存儲或鏈接

存儲)進行存儲。

0(4)散列存儲結(jié)構

散列存儲結(jié)構是指根據(jù)數(shù)據(jù)元素的關

鍵字值來確定其存儲地址。

W,

2.2線性表

線性表順序存儲結(jié)構

線性表由一組數(shù)據(jù)元素構成。

數(shù)據(jù)元素可以是簡單項（如上述例子

中的數(shù)、字母、季節(jié)名等）。在稍微復雜

的線性表中，一個數(shù)據(jù)元素還可以由若干

個數(shù)據(jù)項組成。

單擊鼠標左鍵換頁R|G|>P

例如，某班的學生情況登記表，如表

2.1所示。

學生情況登記表就是一個文件，其中

每一個學生的情況就是一個記錄。

V冏〉同

表2.1學生情況登記表

姓名學號性另U年齡健康伏況

王小平00156男19良好

趙大剛00134男20一般

李艷00272女19良好

馬文華00167男21較差

■■■?■

?■■*?■*■*?

綜上所述，線性表是由〃(n>0)個數(shù)

據(jù)元素〃2,???,即組成的一個有限序

列。表中的每一個數(shù)據(jù)元素，除了第一個

外，有且只有一個前件；除了最后一個外,

有且只有一個后件。即線性表或是一個空

表，或可以表示為：

(al,〃2,…，〃i,an)

其中山(i=l,2,???,")是屬于數(shù)據(jù)對

象的元素，通常也稱其為線性表中的一個

結(jié)點。

V冏〉同

非空線性表有如下一些結(jié)構特征：

①有且只有一個根結(jié)點”1,它無前件。

②有且只有一個終端結(jié)點am它無后

件。

③除根結(jié)點與終端結(jié)點外，其他所有

結(jié)點有且只有一個前件，也有且只有一個

后件。線性表中結(jié)點的個數(shù)"稱為線性表

的長度。當〃=0時，稱為空表。

V冏〉同

在計算機中存放線性表，一種最簡單

的方法是順序存儲，也稱為順序分配。順

序存儲的線性表通常稱為順序表。

線性表的順序存儲結(jié)構具有以下兩個

基本特點：

①線性表中所有元素所占的存儲空間

是連續(xù)的。

②線性表中各數(shù)據(jù)元素在存儲空間中

是按邏輯順序依次存放的。

W,

在計算機中的順序存儲結(jié)構如圖

2.8所示。

占歸個字節(jié)

占歸個字節(jié)

占上個字節(jié)

占上個字節(jié)

圖2.8線性表的順序存儲結(jié)構

在程序設計語言中，通常定義一個一

維數(shù)組來表示線性表的順序存儲空間。

因為程序設計語言中的一維數(shù)組與計

算機中實際的存儲空間結(jié)構是類似的，這

就便于用程序設計語言對線性表進行各種

運算處理。

V冏〉同

建立一個空線性表的順序存儲空間

(即初始化線性表的順序存儲空間)的c

語言描述如下：

#include"stdlib.h"

voidinitsl(v,m,n)/*初始化順序表*/

ET*v；/*v返回順序表空間的首地址,ET表示元

素的數(shù)據(jù)類型*/

intm,*n；/*m為順序表的空間容量(字節(jié)

數(shù))返回線性表的長度*/

{v=malloc(m*sizeof(ET))；/*申請順序表空間*/

*11=0；/*線性表長度為o*/

return；

}

V冏〉同

風1：10)中：10）網(wǎng)1：10)

129129129

眼-2182872,⑻

35631S3；1S

463456456

535563563

624635635

7317247?：24

847331g31

9回f947■914

10______101047

（a）長度為8的統(tǒng)性表（b）插入元素87后（c）又插入元素14后1

圖2.9順序表的插入示意圖

一般來說，設長度為"的線性表為:

（?！傅?…?,…,4）

要在線性表的第i個元素質(zhì)之前插入一

個新元素〃，插入后得到長度為〃+1的線

性表為：

…7&J7j+1」,?，4,劭+1）

夠螂陵

wE示左鍵換頁V冏〉同

則插入前后的兩線性表中的元素滿足

如下關系：

%1W/W"1

Cti=vb

j+1WJWX+1

w小1輾1整利V合〉以

在線性表順序存儲的情況下，要插入

一個新元素，由于數(shù)據(jù)元素的移動而消耗

較多的處理時間，因此其效率是很低的，

特別是在線性表比較大的情況下更為突出。

下面是線性表在順序存儲結(jié)構下插入

算法的C語言描述。

V冏〉同

voidinsl(v,m,nj,b)/*順序表的插入*/

ETv[],b；/*v為順序表空間,b為插

入的元素*/

intm,*n,i；/*m為順序表空間容量

為指向線性表長度的指針，

i為插入元素的序號*/

{if(*n==m)/*順序表空間已滿，上溢

錯誤，返回*/

{printf(noverflow\n'>return；}

V冏〉同

if（i〉*n—1）i=*n+l；/*在線性表的

最后插入*/

if(i<l=i=l；/*在線性表的第1個

元素之前插入*/

for(j=wn；j<=i；j——=/*插入位

置以后的元素依次往后移動一個位置*/

vDl=v[j-l]；

v[i-l]=b；/*插入元素b*/

*n=*n+l；/*線性表長度加1*/

return；

單擊鼠標左鍵換頁RIlGlOllM

?2,順序表的刪除運算

首先舉一個例子來說明如何在順序存

儲結(jié)構的線性表中刪除一個元素。

*1：10)網(wǎng)1：10)鞏1:10)

129118118

一|182362學

3563633盛

463435435

535524524

624631647

7317477

24788

999

101010

—

（a）長度為8的線性表（b）刪除元素29后（c）又刪除元素31后

圖2.10線性表在順序存儲結(jié)構下的刪除示意圖

一般來說，設長度為"的線性表為:

現(xiàn)要刪除第i個元素，刪除后得到長度

為h-1的線性表為：

⑷遇,…，可，…,*-1)

小1輾1整利

w示左鍵換頁V冏〉同

則刪除前后的兩線性表中的元素滿足

如下關系:

lWjWi-1

在線性表順序存儲的情況下，要刪除

一個元素，由于數(shù)據(jù)元素的移動而消耗較

多的處理時間，其效率也是很低的，特別

是在線性表比較大的情況下更為突出。

下面是線性表在順序存儲結(jié)構下刪除

算法的C語言描述。

W,

voiddesl(v5m5n4)/*順序表的刪除*/

ETv[]；/*順序表空間*/

intm,*n,i；/*m為順序表空間容量再

為指向線性表長度的指針，

i為刪除元素的序號*/

{if(*n==0)/*線性表為空，下溢錯誤,

返回*/

printf(nunderflow\nn)；

return；}

V冏〉同

if((i<l)||(i>*n))/*線性表中沒有

這種下標的元素，返回*/

printf(nNotthiselementinthelist

\nn)；return；}

for(j=i；j<=*n-l；j++=/*第i個以

后的元素依次往前移動一個位置*/

vU-l]=v[j]；

*n=*n-1；/*線性表長度減1*/

return；

)

V冏〉同

2電棧及其應用

Hz5.7棧的基本概念

棧實際上也是線性表，只不過是一種

特殊的線性表。

棧(stack)是限定在一端進行插入與刪

除的線性表。

往棧中插入一個元素稱為入棧運

算，從棧中刪除一個元素（即刪除棧

頂元素）稱為退棧運算。

棧頂指針top動態(tài)反映了棧中元

素的變化情況。

圖2.11是棧的不意圖o

V冏〉同

圖2.11棧示意圖

圖2.12中給出了具有嵌套調(diào)用關系的

五個程序，其中主程序要調(diào)用子程序

SUB1,SUB1要調(diào)用子程序SUB2,SUB2

要調(diào)用子程序SUB3,SUB3要調(diào)用子程序

SUB4,SUB4不再調(diào)用其他子程序了。

V冏〉同

MAINSUB1SUB2SUB3SUB4

CALLSUB1CALLSUB2CALLSUB3CALLSUB4■■■■■■

A：...B：……C：-D：……

ENDRETURNRETURNRETURNRETURN

圖2.12主程序與子程序之間的調(diào)用關系

計算機系統(tǒng)在處理時要用一個棧來動

態(tài)記憶調(diào)用過程中的路徑，其基本原則如

下：

①在開始執(zhí)行程序前，建立一個棧，

其初始狀態(tài)為空。

②當發(fā)生調(diào)用時，將當前調(diào)用的返回

點地址（在圖2.12中用語句標號表示）入

棧。

③當遇到從某個子程序返回時，從棧

項取出返回點地址。

W,

棧的順序存儲及其運

在棧的順序存儲空間S(1：加)中，S

(bottom)通常為棧底元素(在棧非空的

情況下)，S(top)為棧頂元素。top=0

:■表示棧空；top=加表示棧滿。

V冏〉同

S（1：10）S（1：10）S（1：10）

1010：：10

999

StopfgY含

77Xtopf7X

top-6F6F6F

5E5E5E

4D4口.4D

3C3C33C

iBB2B

bottomf1Abottom-*-1Abottomf1A

（&）有6個元素的棧（b）插入X與Y后的棧（c）退出一個元素后的棧

圖2.13棧在順序存儲結(jié)構下的運篁

建立一個空棧的順序存儲空間（即初

始化棧的順序存儲空間）的C語言描述如

下：

#includenstdlib.hn

voidinit_stack(s,m,top)/*初始化棧空間*/

ET*s；/*?？臻g*/

intm,*top；/*m為?？臻g容量,top為棧頂指針*/

{s=malloc(m*sizeof(ET))；/*申請容量為m的棧

空間*/

*top=0；/*置?？?/

return；

}

V冏〉同

棧的基本運算有三種：入棧、退棧與

讀棧頂元素。下面分別介紹在順序存儲結(jié)

構下棧的這三種運算。

0(1)入棧運算

入棧運算是指在棧頂位置插入一個新

元素。

V冏〉同

入棧運算的C語言描述。

voidpush(s,m,top,x)/*在容量為m的棧S中插入一

個元素x(入棧運算)*/

ETs[],x；/*s為棧空間,x為入棧元素*/

intm,*top；/*m為?？臻g容量,top為棧頂指針*/

{if(*top==m)/*棧滿，上溢錯誤，返回*/

{printf(uStack-overflow\nn)；return；}

*top=*top+l；/*棧頂指針進一*/

s[*top-l]=x；/*將元素X插入到棧頂位置*/

return；

W1

0(2)退棧運算

退棧運算是指取出棧頂元素并賦給一

個指定的變量。這個運算有兩個基本操作:

首先將棧頂元素(棧頂指針指向的元素)

賦給一個指定的變量，然后將棧頂指針退

（即top減1）O

V冏〉同

退棧運算的C語言描述。

voidpop(s,m,top,y)/*在容量為m的棧S中刪除棧

頂元素(退棧運算)*/

ETs[]/y；/*s為?？臻g,y指向存放退棧元素的地

址*/

intm/top；/*m為?？臻g容量,top為棧頂指針*/

{if(*top==0)/*?？眨乱珏e誤，返回*/

{printf(nStack-underflow\nn)；return；}

*y=s[*top-1]；/*讀取棧頂元素*/

*top=*top-l；/*棧頂指針退一*/

return；

wV冏〉同

⑥(3)讀棧頂元素

讀棧頂元素是指將棧頂元素賦給一

個指定的變量。必須注意，這個運算不

刪除棧頂元素，只是將它的值賦給一個

變量，因此，在這個運算中，棧頂指針

不會改變。

V合〉E

讀棧頂元素算法的C語言描述。

voidtop(s,m,top,y)/*讀棧頂元素*/

ETs[]/y；/*s為?？臻g,y指向存放棧頂元

素的地址*/

intmJtop；/*m為棧空間容量,top為棧頂

指針*/

{if(氣op==0)/*?？斟e誤,返回刃

{printf(nStackempty\nn)；return；}

*y=s[*top-1]；/*讀取棧頂元素*/

Ireturn；

V冏〉同

S2.3.3棧的應用

231中討論的子程序嵌套調(diào)用就是棧

的一個實際應用。

棧還用于實現(xiàn)遞歸調(diào)用過程、表達式

的處理和中斷的處理。

?1.遞歸過程的實現(xiàn)

例如，在本書的第1章例L5中提到，

對于輸入的參數(shù)"，依次打印輸出自然數(shù)1

到"。為了不使用局部變量，其C函數(shù)如下:

#include''stdio.h''

wrtl(intn)

{if(n!=0)

{wrtl(n-l)；printf(n%d\n!\n)；}

return；

V冏〉同

■2.表達式的計算

在編譯系統(tǒng)或解釋系統(tǒng)中，常利用棧

來處理表達式的計算問題。

V冏〉同

toppf*topvfC

+B

??

toppf9A

OPStopvfOVSOPSOVS

(a)初始狀態(tài)(b)讀出A、+、Bs*、C

toppf+topv—71

；Atopp一topvfT2

OPSOVSOPSOVS

(c)讀出“-”>作運苴T1=B*c(d)重新考慮“.作運菖A=A+n

單擊鼠標左鍵換頁

toppf/topv一E

—Dtoppf—topvfR

■?

9X9

UPSOVSOPSOVS

(e)重新考慮，并讀出D、人E:(f)讀出“；”，作運算U=D/E

■?

topp一?topvf??toppf?

OPSOVSOPStopvfOVS

□

(g)重新考慮“；”，作運篁A=Tf(h)重新考慮七”，結(jié)束＞幾為結(jié)果

?1圖2.14表達式A+B*C-D近的計算過程

2.4隊列及其應用

粵241隊列的基本概念

隊列（equeue）是指允許在一端進行

插入、而在另一端進行刪除的線性表。

允許插入的一端稱為隊尾，允許刪除

的一端稱為排頭。

單擊鼠標左鍵換頁

在隊列這種數(shù)據(jù)結(jié)構中，最先插入的

元素將最先能夠被刪除，反之，最后插入

的元素將最后才能被刪除。

往隊列的隊尾插入一個元素稱為入隊

運算，從隊列的排頭刪除一個元素稱為退

隊運算。

圖2.16是在隊列中進行插入與刪除的

示意圖。

W,

W：'

郎左

與棧類似，在程序設計語言中，用一

維數(shù)組作為隊列的順序存儲空間。

在操作系統(tǒng)中，用一個隊列來組織管

理用戶程序的排隊執(zhí)行，原則是：

①初始時隊列為空。

②當有用戶程序來到時，將該用戶程

序加入到隊列的末尾進行等待。

③當計算機系統(tǒng)執(zhí)行完當前的用戶程

序后，就從隊列的頭部取出一個用戶程序

隊行。

W,【嚓靴蟒示左鍵換V冏〉同

92.4.2循環(huán)隊列及其運算

在實際應用中，隊列的順序存儲結(jié)構

一般采用循環(huán)隊列的形式。

所謂循環(huán)隊列，就是將隊列存儲空間

的最后一個位置繞到第一個位置，形成邏

輯上的環(huán)狀空間，供隊列循環(huán)使用，如圖

2.17所示。

小1輾1整利

nearfm

Rontf

圖二1了循環(huán)隊列存儲空間示意圖

Q(1:8)Q(1⑶Qd:8)

88*X謳X

rear-*-7F7FF

6E&E-6E

5D5D5D

4C44c

3B3B3B

2A2*front-*2

front-*-1front-*1Yrear-*1Y

(a)具有6個元素的循環(huán)隊列(b)加入X、丫后(c)退出一個元素后

圖2.18循環(huán)隊列運算例

由圖2.18中循環(huán)隊列動態(tài)變化的過程

可以看出，當循環(huán)隊列滿時有front=rear,

而當循環(huán)隊列空時也有front=rear。

為了能區(qū)分隊列滿還是隊列空，通常

還需增加一個標志s,s值的定義如下：

0表示隊列空

1表示隊列非空

示左鍵換頁V冏〉同

建立一個循環(huán)隊列順序存儲空間(即

初始化循環(huán)隊列順序存儲空間)的C語言

描述如下：

#includenstdlib.hn

voidinit_queue(q,m9front9rear9s)/*初始化

循環(huán)隊列*/一

ET*q；/*循環(huán)隊列空間*/

intm,"front,*rear,*s；/*m為循環(huán)隊列容

量,front為排頭指針，

rear為隊尾指針,s為標

*1

W1

{q=malloc(mwsizeof(ET))；/*申請容

量為m的循環(huán)隊列空間*/

*front=m；*rear=m；/*置頭尾指

針初值刃

*§=0；/*置隊列空標志*/

return；

V冏〉同

⑥(1)入隊運算

入隊運算是指在循環(huán)隊列的隊尾加入

一個新元素。

這個運算有兩個基本操作：首先將隊

尾指針進一(即rear=rear+1），并當rear

+1時置超2「=1;然后將新元素插入

到隊尾指針指向的位置。

下面是入隊運算的C語言描述。

V冏〉同

/*在容量為m的循環(huán)隊列Q中插入一個

元素x(入隊運算)*/

voidaddcq(q,m,rear,front,s,x)

ETq[],x；/*q為循環(huán)隊列空間,x為

入隊的元素*/

intm/rear/front/s；/*m為循環(huán)隊

列容量,front為排頭指針，

rear為隊尾指針產(chǎn)

為標志刃

V冏〉同

{if((*s==l)&&(*rear==*front))/*隊列

滿，上溢錯誤，返回*/

{printf(nQueue-OVERFLOW\nn)；

return；}

*rear=*rear+l；/*隊尾指針進一*/

if(*rear==m+l)*rear=l；/*隊尾指針循

環(huán)*/

q[*rear-l]=x；/*元素x插入到隊尾*/

*s=l；/*置隊列非空標志*/

return；

V冏〉同

0(2)退隊運算

退隊運算是指在循環(huán)隊列的排頭位置

退出一個元素并賦給指定的變量。這個運

算有兩個基本操作：首先將排頭指針進一

(BPfront=front+1)，并當front=m+1

時置front=1；然后將排頭指針指向的元

素賦給指定的變量。

下面是退隊運算的C語言描述。

小1輾1整利

/*在容量為m的循環(huán)隊列中刪除一個

元素(退隊運算)*/

voiddelcq(q,m,rear,front凡y)

ETq[],*y；/*q為循環(huán)隊列空間,y存

放退隊的元素*/

intm/rear/front/s；/*m為循環(huán)隊

列容量,front為排頭指針，

rear為隊尾指針產(chǎn)

為標志刃

V冏〉同

{if(*s==O)/*隊列空，下溢錯誤，返回*/

{printf(''Queue—UNDERFLOW\iT)；

return；}

*front=*front+l；/*排頭指針進一*/

if(*front==m+l)*front=l；/*排頭指針

循環(huán)*/

*y=q[*front-l]；/*讀出排頭元素*/

if(*front==*rear)*s=0；/*置隊列空標

志*/

return；

V冏〉同

隊列的應用

凡是按“先來先服務”（即“先進先

出”）原則處理的問題，都可以用隊列結(jié)

構來解決。

下面再介紹三個用模擬隊列結(jié)構來解

決的問題。

H1.給工人分配工作的模擬

V冏〉同

為了解決上述這種兩個設備操作速度

不匹配的矛盾，通常是在兩個設備之間設

置一個緩沖區(qū)，如圖2.19所示。

V冏〉同

利用循環(huán)隊列結(jié)構的緩沖區(qū)，就解決

了計算機處理數(shù)據(jù)與打印機打印輸出的速

度不匹配的矛盾，實現(xiàn)了兩個設備之間數(shù)

據(jù)的正常傳送。

?3.汽車加油站的工作模擬

V冏〉同

2.5線性鏈表

92.5.1線性鏈表的基本概念

H1.線性健表

線性表的鏈式存儲結(jié)構稱為線性鏈表。

為了適應線性表的鏈式存儲結(jié)構，計算

機存儲空間被劃分為一個一個小塊，每一

小塊占若干字節(jié)，通常稱這些小塊為存儲

j吉點。

!單擊鼠標左鍵換頁

將存儲空間中的每一個存儲結(jié)點分為

兩部分：一部分用于存儲數(shù)據(jù)元素的值，

稱為數(shù)據(jù)域；另一部分用于存放下一個數(shù)

據(jù)元素的存儲序號（即存儲結(jié)點的地址），

即指向后件結(jié)點，稱為指針域。

線性鏈表中存儲結(jié)點的結(jié)構如圖2.20

所示。

存儲序號數(shù)據(jù)域指針域

i'fWEI7W

圖2.20線性捱表的一個存儲結(jié)點

線性誄表的邏輯結(jié)構如圖2.21所不。

HEAD—>數(shù)據(jù)I》數(shù)據(jù)2，數(shù)據(jù)nNULL

圖2.21線性鏈表的邏輯結(jié)構

19

HEAD2]

133一<211

4

5%10

：6

7

3

95

；m的0

(a)線性鏈表的物理狀態(tài)

3T9510

444

HEAD..

<21的0

(b)線性鏈表的邏輯狀態(tài)

圖2.22線性鏈表例

指向線性表中第一個結(jié)點的指針

HEAD稱為頭指針。

當HEAD=NULL（或0）時稱為

空表。

對于線性鏈表，可以從頭指針開始,

沿各結(jié)點的指針掃描到鏈表中的所有結(jié)

V冏〉同

為了彌補線性單鏈表的這個缺點，在

某些應用中，對線性鏈表中的每個結(jié)點設

置兩個指針，一個稱為左指針(Llink),

用以指向其前件結(jié)點；另一個稱為右指針

(Rlink),用以指向其后件結(jié)點。

這樣的線性鏈表稱為雙向鏈表，其邏

輯狀態(tài)如圖2.23所示。

HEAD

圖2.23雙向鏈表示意圖

?2.帶徒的棧

棧也是線性表，也可以采用鏈式存儲

結(jié)構。

圖2.24是棧在鏈式存儲時的邏輯狀態(tài)

示意圖。

在實際應用中，帶鏈的?？梢杂脕硎?/p>

集計算機存儲空間中所有空閑的存儲結(jié)點,

這種帶鏈的棧稱為可利用棧。

,如圖2.25所示。

W,

(a)將結(jié)點p送回可利用棧

0

(b)在從可利用棧取得一個結(jié)點p

圖2.25可利用棧及其運算

展3.帶鏈的隊列

與棧類似，隊列也是線性表，也可以

采用鏈式存儲結(jié)構。

圖2.26(a)是隊列在鏈式存儲時的邏

輯狀態(tài)示意圖。

(a)帶鏈的隊列

圖2.26(b)是將新結(jié)點p入隊的示

意圖。

圖2.26(c)是將排頭結(jié)點p退出隊列

的示意圖。

p

(C)在帶微的隊列中刪除一個結(jié)點

圖2.26帶梃的隊列及其運算

92.5.2線性鏈表的基本運算

線性鏈表的運算主要有以下幾個：

①在線性鏈表中包含指定元素的結(jié)點

之前插入一個新元素。

②在線性鏈表中刪除包含指定元素的

結(jié)點O

③將兩個線性鏈表按要求合并成一個

線性鏈表。

小1輾1整利

④將一個線性鏈表按要求進行分解。

⑤逆轉(zhuǎn)線性鏈表。

⑥復制線性鏈表。

⑦線性鏈表的排序。

⑧線性鏈表的查找。

V冏〉同

1.在線性鏈表中查找指定元素

對線性鏈表進行掃描查找，在線性鏈

表中尋找包含指定元素值的前一個結(jié)點。

V冏〉同

H2.線性f

線性鏈表的插入是指在鏈式存儲結(jié)構

下的線性表中插入一個新元素。

為了要在線性鏈表中插入一個新元素,

首先要給該元素分配一個新結(jié)點，然后將

存放新元素值的結(jié)點鏈接到線性鏈表中指

定的位置。

V冏〉同

（b）從可利用棧取得結(jié)點p,在線性鏈表中找到包含元素x的前一個結(jié)點q

（c）p插入到q之后

圖2.27線性鏈表的插入

V合〉以

S3.線性鏈表的刪除

線性鏈表的刪除指在鏈式存儲結(jié)構下

的線性表中刪除包含指定元素的結(jié)點。

為了在線性鏈表中刪除包含指定元素

的結(jié)點，首先要在線性鏈表中找到這個結(jié)

點，然后將要刪除結(jié)點放回到可利用棧。

V冏〉同

(c)將被刪除的結(jié)點p送回可利用棧后

圖2.28線性鏈表的刪除

92.5.3循環(huán)鏈表

循環(huán)鏈表的結(jié)構與前面所討論的線性

鏈表相比，具有以下兩個特點：

①循環(huán)鏈表的頭指針指向表頭結(jié)點。

②在循環(huán)鏈表中，所有結(jié)點的指針構

成了一個環(huán)狀鏈。

圖2.29是循環(huán)鏈表的示意圖。

W,

S2.29循環(huán)鏈表的邏輯狀態(tài)

在實際應用中，循環(huán)鏈表與線性單鏈

表相比主要有以下兩個方面的優(yōu)點：

①在循環(huán)鏈表中，只要指出表中任何

一個結(jié)點的位置，就可以從它出發(fā)訪問到

表中其他所有的結(jié)點。

②由于在循環(huán)鏈表中設置了一個表頭

結(jié)點，因此，在任何情況下，循環(huán)鏈表中

至少有一個結(jié)點存在，從而使空表與非空

表的運算統(tǒng)一。

W,

92.5.4多項式的表示及其運算

設多項式為：

Pn(x)=anxn+an-lxn-1+...+alx+aO

在采用鏈表表示多項式時，對于多項

式中每一個非零系數(shù)的項構成鏈表中的一

個結(jié)點，而對于系數(shù)為零的項就不用表示。

多項式中非零系數(shù)項所構成的結(jié)點如圖

.30所示。

w

EXP(S)COEFF[(i)

圖230多項式非零系數(shù)項的結(jié)點結(jié)構

設只表示非零系數(shù)項的多項式為:

馬0)=%二。+為_］產(chǎn)=+…+勾短

其中ak#O(k=l52v..5/M),e/w>em-1>...

>el>Oo

若用線性單鏈表表示，其邏輯狀態(tài)如

圖2.31(a)所示。

若用循環(huán)鏈表表示，其邏輯狀態(tài)如圖

.31(b)所示。

V冏〉同

--------A-%j?―■~?eiai0

(a)多項式的線性單鏈表表示］

-1?a冊——―?…1-----?a.!

(b)多項式的循環(huán)捱表表示

圖2.31多項式的鏈式結(jié)構

多項式的運算主要有以下五種：

①多項式鏈表的生成。

②多項式鏈表的釋放。

③多項式的輸出。

④多項式的相加。

⑤多項式的相乘。

下面以循環(huán)鏈表表示的多項式為例來

討論各種運算。

V合〉E

展L多項式鏈表的生成

主要包括以下兩步：

①建立一個表頭結(jié)點，其指數(shù)域值為

-1,指針域指向表頭結(jié)點自身，頭指針也

指向表頭結(jié)點。

②按降塞順序以數(shù)偶形式依次輸入多

項式中非零系數(shù)項的指數(shù)ek和系數(shù)ak(k=

m,m-1,???,1),最后以輸入指數(shù)值-1

為結(jié)束。

V冏〉同

?2.多項式鏈表的釋放

從表頭結(jié)點開始，逐步釋放鏈表中的

各結(jié)點。

展3.多項式的輸出

從表頭結(jié)點后的第一個結(jié)點開始，以

數(shù)偶形式順鏈輸出各結(jié)點中的指數(shù)域與系

數(shù)域的內(nèi)容。

v冏〉同

H4.多項式的相加

多項式相加的運算規(guī)則很簡單，只

要從兩個多項式鏈表的第一個元素結(jié)點

開始檢測。

展5.多項式的相乘

V冏〉同

2.6數(shù)組與字符串

要2.6./數(shù)組的順序存儲結(jié)構

數(shù)學中的矩陣在程序設計語言中用二

維數(shù)組表示。

二維數(shù)組在計算機中是順序存儲的。

單擊鼠標左鍵換頁

1.二維數(shù)組以行為主的順序存儲

二維數(shù)組以行為主的順序存儲是指將數(shù)組

中的元素一行接一行地順序存儲在計算機的連續(xù)

存儲空間中。

例如，一個MX〃的矩陣

J4=

在計算機中以行為主的順序存儲形式如圖

.32所示。

wV冏〉同

1

1

ADR(?U)口111

fill;第1行的正個兀素

1

?J

如

幻1］第2行的“個元素

如

1

1?

%J

1

1

｝第m行的m個元素

1

1J

%.*

1

1

圖2.32黑火月矩陣的以行為主存儲形式

2.二維數(shù)組以列為主的順序存儲

二維數(shù)組以列為主的順序存儲是指將數(shù)組

中的元素一列接一列地順序存儲在計算機的連續(xù)

存儲空間中。

例如，一個陽x〃的矩陣

在計算機中以列為主的順序存儲形式如圖

AD%D

第1列的m個元素

第2列的m個元素

第力列的m個元素

QtiA

圖233mx月矩陣的以列為主存儲能式

要2.6.2規(guī)則矩陣的壓縮

規(guī)則矩陣是指，矩陣中非零元素的

分布是有規(guī)律的。

在存儲一個規(guī)則矩陣時，只需存儲

非零元素即可，而對于大部分的零元素

或者重復的非零元素（如對稱矩