Thesoftwarebasic

ofcomputer

■■頁工

計算機教學(xué)實驗中心

第2單元線性數(shù)據(jù)結(jié)構(gòu)（一）|

教學(xué)目標：

?了解數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念

-什么是線性DS、線性表

?了解線性DS的特點

?了解線性DS的邏輯結(jié)構(gòu)、物理結(jié)

上一頁

構(gòu)以及操作

停止放映

下一頁

第2頁

學(xué)習(xí)要求

通過本單元的學(xué)習(xí)，了解并掌握：

?有關(guān)數(shù)據(jù)結(jié)構(gòu)（DS）的基本概念

-數(shù)據(jù)元素、DS、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、

DS的分類及特點、算法、時間復(fù)雜度等

?線性DS的常用存儲結(jié)構(gòu)

-順序、鏈表、索引、散列存儲結(jié)構(gòu)

上一頁-單向、雙向、循環(huán)鏈表等

停止放映?線性DS的有關(guān)算法

下一頁-增、冊h改

第3頁

涉及的章節(jié)

第1章的

1.1數(shù)據(jù)結(jié)構(gòu)概述

(P13-P17)

1.2線性表

(P17-P32)

上一頁

停止放映

下一頁

第4頁

數(shù)據(jù)結(jié)構(gòu)問題的由來

數(shù)

計算機求解問題過程步驟：據(jù)

邏

輯

數(shù)據(jù)類型、格式、

運

算

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

、實際分析抽象問題模型求解求解,

*3問題.模型—?算法

、命令

編程

上一頁求解,運彳亍1編制

結(jié)果結(jié)果輸出程序調(diào)試程序程序

停止放映

下一頁數(shù)據(jù)的物理

操作

第

5頁

問題模型

?結(jié)構(gòu)分析線性方程組

?人口預(yù)報——微分方程

?優(yōu)化問題——線性規(guī)劃、非線性規(guī)劃

?震動問題——矩陣分析；特征值、特征

向量

?信息管理——二維數(shù)據(jù)表

上一頁?下棋——人工智能（樹型結(jié)構(gòu)）

停止放映?交通管理——最佳道路選擇（圖型結(jié)構(gòu)）

下一頁

第6頁

下棋問題

?、基本概念_|

?數(shù)據(jù)(Data)

能存于計算機、并被計算機處理的符號的集合。

它是客觀事物的符號表示。

?數(shù)據(jù)元素(Element)

是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個體。

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

是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合；它有三個

要素：

口5二數(shù)據(jù)的邏輯結(jié)構(gòu)+存儲結(jié)構(gòu)+數(shù)據(jù)的運算

上一頁

數(shù)據(jù)結(jié)構(gòu)是以數(shù)據(jù)為加工對象，研究數(shù)據(jù)組織

停止放映方式和相關(guān)操作方法的學(xué)問。也可以說：怎樣

去組織一批特定的數(shù)據(jù)。

下一頁

第8頁

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

線性

表

堆

棧

隊

列

「線性結(jié)構(gòu)V串

組

數(shù)

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

DS<

樹

二

樹

叉

上一頁I非線性結(jié)構(gòu)圖

停止放映

下一貢一

第9頁

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

它是描述數(shù)據(jù)間的順序(邏輯)關(guān)系,

只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而

不管它們在計算機中如何存放。一般

用下列二元組來描述：

DS=(D,R)

其中：

上一頁D：是數(shù)據(jù)元素的有限集合；

停止放映R：是數(shù)據(jù)元素之間關(guān)系的集合。

卜一頁

第10頁

舉例

?課題組由1名教師、1~3名研究生、1~6

名本科生組成；成員關(guān)系是：教師指導(dǎo)

研究生、研究生指導(dǎo)1~2名本科生。

定義DS如下：

Group=(D,R)

其中：

D={T,G1,...,Gn,S11,...Snm}1<n<3,1<m<2

R={R1,R2}

上一頁

R1={<T,Gi>|1<i<n,1<n<3}

停止放映R2={<Gi,Sij>|1<i<n,1<n<3,1<m<2}

下一頁

第ii頁

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

?又稱物理結(jié)構(gòu)

?是指數(shù)據(jù)結(jié)構(gòu)在計算機中

的表示（又稱映象），即數(shù)據(jù)

在計算機中的存放。

上一頁

停止放映

下一頁

第12頁

邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系I

*數(shù)據(jù)的邏?獐金坡是從邏輯關(guān)系（某種順

序）上觀察數(shù)據(jù)，它是獨立于計算機的；

可以在理論上、形式上進行研究、推理、

運算等各種操作。

*數(shù)據(jù)的存儲緒麴是邏輯結(jié)構(gòu)在計算機中

的實現(xiàn)，是依賴于計算機的；離開了機器,

則無法進行任何操作。

上一頁

?任何一個算法的度才取決于選定的邏輯

停止放映結(jié)構(gòu)；而算法展演終實現(xiàn)依賴于采用的

下一頁存儲結(jié)構(gòu)。

第13頁

數(shù)據(jù)存儲結(jié)構(gòu)分類I

?順序存儲結(jié)構(gòu)

?鏈式存儲結(jié)構(gòu)

?索引存儲結(jié)構(gòu)

上一頁

停止放映?散列存儲結(jié)構(gòu)

下一頁

第14頁

順序存儲結(jié)構(gòu)

把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲

單元中的存儲形式。數(shù)據(jù)結(jié)點結(jié)構(gòu)：

數(shù)據(jù)域

dld2dn

上一頁特點:

停止放映*連續(xù)存放;邏輯上相鄰，物理上也相鄰。

*結(jié)構(gòu)簡單，易實現(xiàn)。

下一頁

*插入、刪除操作不便（需大量移動元素）。

第15頁

鏈式存儲結(jié)構(gòu)

以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中,

可連續(xù)存放，也可以不連續(xù)存放，以指針實現(xiàn)

鏈表間的聯(lián)系。數(shù)據(jù)結(jié)點結(jié)構(gòu)：

數(shù)據(jù)域指針域

上一頁

特點:

停止放映*非連續(xù)存放，借助指針來表示元素間的關(guān)系；

下一頁*插入、刪除操作簡單，只要修改指針即可；

*結(jié)構(gòu)較復(fù)雜，需要額外存儲空間。

第16頁

索引存儲結(jié)構(gòu)

數(shù)據(jù)按索引形式存放。存儲時分為：數(shù)據(jù)項和索引

號；通過索引表記錄邏輯號（記錄號）和物理號

（存儲序號）之間的對應(yīng)關(guān)系。數(shù)據(jù)結(jié)點結(jié)構(gòu)：

數(shù)據(jù)域索引順序號

序號:1234567

數(shù)據(jù)項:

索引號:122135245510

上一頁4327165

停止放映

卜一頁*非連續(xù)存放；

*檢索速度快；

?增、刪操作簡單。第17頁

散列存儲結(jié)構(gòu)

?在數(shù)據(jù)元素與存儲位置之間建立一種存儲

關(guān)系F,根據(jù)這種關(guān)系F,已知元素E,就

可以得到它的存儲地址，即D=F(E)o

?哈希查找中的哈希表就是這樣一種存儲結(jié)

構(gòu)。

特點:

*數(shù)據(jù)元素間無內(nèi)在聯(lián)系；

上一頁

*存儲形式不定。

停止放映

下一頁

第18頁

3.數(shù)據(jù)運算

?數(shù)據(jù)運算是指對存放在物理結(jié)構(gòu)上

的數(shù)據(jù)，按定義的邏輯結(jié)構(gòu)進行的各

種操作。

常見操作有：

—輸入、檢索、插入、刪除、修改、

排序等。

上一頁

停止放映

下一頁

第19頁

4、算法與算法分析

算法(Algorithm)

-是對特定問題求解步驟的一種描述；

-是一組指令的有限集合。

算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系

為了充分地利用系統(tǒng)資源；既要效率高、

速度快，又要存儲空間少。顯然，這是

矛盾的。

上一頁

研究算法追求的目標是:

停止放映時間和空間的適當和諧

下一頁

第20頁

算法的特性

?有窮性一個算法必須總是在執(zhí)行有窮步后

結(jié)束，且每一步都可在有窮時間內(nèi)完成；

?確定性算法中的每一個指令比須有明確的

含義，不能有二義性；

?初廳性算法中描述的操作都是可通過已經(jīng)

實現(xiàn)的基本運算、執(zhí)行有限次實現(xiàn)的；

?輸入一個算法應(yīng)有。個或多個輸入；

上一頁

?輸出一個算法應(yīng)有1個或多個輸出。

停止放映

下一頁

第21頁

算法的設(shè)計要求

?正確性(Correctness)

?可讀性(Readability)

?健壯性(Robustness)

?高效率與低存儲量

上一頁

停止放映

下一頁

第22頁

正確性(Correctness)

?有4個層次：

A.程序不含語法錯誤；

B.程序?qū)捉M輸入數(shù)據(jù)能夠得出滿

足規(guī)格要求的結(jié)果；

C.程序?qū)倪x擇的、典型的、苛

刻的、帶有刁難性的幾組輸入數(shù)據(jù)

上一頁能夠得出滿足規(guī)格要求的結(jié)果；

程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能

停止放映D.

產(chǎn)生滿足規(guī)格要求的結(jié)果。

下一頁

第23頁

可讀性(Readability)|

?算法的第一目的是為了閱讀和交流;

?可讀性有助于對算法的理解；

?可讀性有助于對算法的調(diào)試和修改。

上一頁

停止放映

下一頁

第24頁

健壯性(Robustness)

?當輸入非法數(shù)據(jù)時，算法也能適

當?shù)刈鞒龇磻?yīng)或進行處理；并且,

處理出錯的方法應(yīng)該是返回一個

表示錯誤或錯誤性質(zhì)的值并中止

程序的執(zhí)行，以便在更高的抽象

層次上進行處理。

上一頁

停止放映

下一頁

第25頁

高效率與低存儲量J

?處理速度快

?存儲容量小

?時間和空間是矛盾的、實際問題

的求解往往是求得時間和空間的

統(tǒng)一、折中。

上一頁

停止放映

下一頁

第26頁

算法的描述

算法的描述方式（常用的）：

r自然語言

流程圖特定的表示算法的圖形

符號

算法描述《為港言包括程序設(shè)計語言的三

大基本結(jié)構(gòu)及自然語言

上一頁的一種語言

1類語言類似高級語言的語言，

停止放映

下一頁例如，類PASCAL、類

C語言。

第27頁

算法的評價

算法評價的標準：時間復(fù)雜度和空間復(fù)雜度。

時間復(fù)雜度

指在計算機上運行該算法所花費的時間。用

“0(數(shù)量級)”來表示，稱為“階”。常

見的時間復(fù)雜度有：

0(1)0(logn)0(n)0(n2)

常數(shù)階對數(shù)階線性階平方階

上一頁空間復(fù)雜度

停止放映指算法在計算機上運行所占用的存儲空間。

度量同時間復(fù)雜度。

下一頁

第28頁

時間復(fù)雜度舉例

(a)X：=X+1；O(1)

(b)FORI：=1TOnDO

X：=X+1；0(n)

(c)FORI：=1TOnDO

FORJ：=1TOnDO0(n2)

上一頁X：=X+1；

停止放映

下一頁

第29頁

二、線性表

是指數(shù)據(jù)元素之間的關(guān)系為一一對應(yīng)

的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。例如，一星

期七天的英文縮寫表示：

(Sun,Mon,The,wed,Thu,Fri,Sat)

是一個線性表，其中的元素是字符串,

表的長度為7。

線性表雖然簡單，但是應(yīng)用范圍非常

上一頁廣泛。

停止放映

下一頁

第30頁

(一)、線性表的邏輯結(jié)構(gòu)I

定義:線性表是n(n>0)個元素a1,a2,…,an的有

限序列;表中每個數(shù)據(jù)元素,除了第1個和最后1個外，

有且僅有一個前趨元素和后繼元素。

形式定義:

含有n個數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表示為:

Linearjist=(D,R)

其中：D={ai|ai￡Do，i=1,2,3,???,n,n>0}

上一頁

R={N},N={<ai-1,ai>|ai-1,aieD0

停止放映D是數(shù)據(jù)元素的有限集合,R是D上邏輯關(guān)系的有限集

合。關(guān)系N是一個有序偶對的集合。

下一頁

第31頁

相互關(guān)系描述

1)L的長度為n(n>0),當n為。時，

表不是空表；

2)每個元素(除了第1個和最后一個元素

外)，有唯一的前趨和后繼；

3)線性表中各元素間存在著線性關(guān)系；

4)均勻性；各元素數(shù)據(jù)類型必須相同；

5)有序性；各元素是有序的，不可交換次序。

上一頁

停止放映

下一頁

第32頁

線性表的基本操作

Setnull(L)置空表

Length(L)求表長度；求表中元素個數(shù)

Get(L,i)取表中第i個元素（住i?n）

Prior(L,i)取i的前趨元素

Next(L,i)取i的后繼元素

Locate(L,x)返回指定元素在表中的位置

Insert(L,i,x)插入元素

上一頁Delete(L,x)刪除元素

停止放映Empty(L)判別表是否為空

卜一頁

第33頁

(二)、線性表的順序存儲結(jié)構(gòu)

?將表中元素一個接一個的存入一組連續(xù)的

存儲單元中，這種存儲結(jié)構(gòu)是順序結(jié)構(gòu)。

?采用順序存儲結(jié)構(gòu)的線性表簡稱為“順序

表”。順序表的存儲特點是：只要確定了

起始位置，表中任一元素的地址都通過下

列公式得到：

LOC(ai)=LOC(a1)+(i-1)*L

1<i<n

上一頁其中，L是元素占用存儲單元的長度。

停止放映

卜一頁

第34頁

線性表元素存儲示意圖

元素序號內(nèi)存狀態(tài)存儲地址

上一頁

停止放映

下一頁

第35頁

算法1?1插入算法

算法步驟：

stepl將第n至第i個元素后移一個存儲位置；

step2將x插入到a2之后；

step3表的長度+1。

線性表采用一維數(shù)組存放。C語言描述為：

#defineMAXLENGTH100

上一頁intlist[MAXLENGTH]；

intlast=-1；/*last指示表中最后一個元素的序號7

停止放映

下一頁

第36頁

算法1“插入算法

insert(inti,intx)

{intk；

if(last==MAXLENGTH)

{printf(“線性表已滿！\n")；exit(-

1)；)

if(i<1||i>last+1)

{printf(“插入位置錯誤!\n");exit(-2);}

else

上一頁{for(k=last-1;K>=i-1;k-)

list[k+1]=list[k];

停止放映

list[i-1]=x;

下一頁

++last;

}第37頁

算法1“插入算法主程序I

#defineMAXLENGTH100/*例1-1主程序7

intlist[MAXLENGTH]={5,3,1,10,7,8,-1,4);

intlast=8;

mainO

{intx,j,loc;

printf(uEnterx>loc\n^^);

scanf("％d,%d”,&x,&loc);

for(j=O;j<MAXLENGTH,j++)

print.%du,list[j]);

上一頁

printf("\rT);

停止放映insert(loc,x);/*插入操作子函數(shù)*/

下一頁forQ=O;j<MAXLENGTH,j++)

print.%d“Jist[j]);printf(^^\n^^);

)第38頁

算法12——線性表刪除算法|

算法步驟：

stepl判別指定的位置是否合法；

step2若合法，則將位置i+1至n上的元素前

移一個存儲位置；

step3表的長度

線性表采用一維數(shù)組存放。

C語言描述為：

上一頁#defineMAXLENGTH100

停止放映intlist[MAXLENGTH]；

intlast；/*last指示表中最后一個元素的序號7

下一頁

第39頁

I考線性表刪除算法I

delete(inti)

{intk;

if(i<1||i>last)

{printf("表中不存在位置為i的元素\n");

exit(-1);

)

for(k=i-1;k<=last-2;k++)

上一頁list[k]=last[k+1];

last-;

停止放映

下一頁)

第40頁

算法L2——線性表刪除算法|

#defineMAXLENGTH100/*例1-2主程序7

intlist[MAXLENGTH]={5,3,1,10,7,8,-1,4);

intlast=8;

mainO

{intj,loc;

printf(uEnterloc\nJ,);

scanf("％d”,&loc);

for(j=O;j<MAXLENGTH,j++)

print.%du,list[j]);

上一頁

printf("\rT);

停止放映delete(5);/*刪除操作子函數(shù)7

下一頁forQ=O;j<MAXLENGTH,j++)

print.%d“Jist[j]);printf(^^\n^^);

}第41頁

順序存儲結(jié)構(gòu)的特點I

?數(shù)據(jù)連續(xù)存放、隨機存取

邏輯上相鄰，物理上也相鄰

?存儲結(jié)構(gòu)簡單、易實現(xiàn)

?插入、刪除操作不便

?存儲密度大，空間利用率高

結(jié)論：

上一頁順序存儲結(jié)構(gòu)適合于表中元素

變動較少的情況。

停止放映

下一頁

第42頁

（三）線性表的鏈式存儲結(jié)構(gòu)I

?線性表的順序存儲結(jié)構(gòu)容易實現(xiàn)，

可以隨機存取表中的任意元素。

?順序表9點、是:

-難于插入、刪除操作；

-需要預(yù)先分配空間，不管這些空

間能否最大限度地利用。

?卷麥布商務(wù)彩在這兩個方面恰好是

上一頁優(yōu)點：

停止放映-容易插入、刪除操作

下一頁-不需要預(yù)分空間。

第43頁

1、鏈表有關(guān)基本概念

結(jié)點(NODE)表中元素的存儲單元。

鏈表存儲結(jié)構(gòu)形式為：

datanext

數(shù)據(jù)域指針域

鏈表結(jié)構(gòu)的C語言描述為：

structnode{

上一頁intdata;

停止放映structnode*next;

下一頁）；

typedefstructnodeNODE；

第44頁

基本概念

鏈表(Link)由結(jié)點組成的表。

頭指針(head)指向鏈表中第1個結(jié)點的指針。

頭結(jié)點為方便操作，在頭指針和頭結(jié)點之間設(shè)置

的結(jié)點。

首元結(jié)點第一個結(jié)點(a1)o

上一頁頭指針

頭結(jié)點首元結(jié)點第i個結(jié)點

停止放映head

卜一頁alai

第45頁

表示形式的統(tǒng)一

空表和非空表表示形式在頭結(jié)點上得到統(tǒng)一

空表的形式：headT.next=NILL

非空表的形式：headT.Next=Address

上一頁

停止放映

下一頁

第46頁

表示形式不統(tǒng)一

?若沒有頭結(jié)點，空表和非空表的表示形式

將不統(tǒng)一。

?空表形式:head=NULL

head

?非空表形式:headT?next=address

上一頁

head

停止放映al

下一頁

第47頁

鏈表舉例

?由食品組成的單鏈表

(biscuit,butter,cheese,eggs5grapes,jam)

不帶頭結(jié)點。

上一頁

停止放映

下一頁

第48頁

單鏈表在存儲區(qū)的物理狀態(tài)I

存儲地址數(shù)據(jù)域（data）指針域（next）

1Grapes60

biscuit61

cheese13

eggs1

上一頁

停止放映

頭指針60jamNULL

head

下一頁61butter12

第49頁

2、單鏈表的操作|

-指針的基本操作

-單鏈表的查找get

-單鏈表的的插入insert

-單鏈表的刪除delete

上一頁

停止放映

下一頁

第50頁

指針的基本操作

?設(shè)指針變量p、q的定義為：NODE*p,*q；

?對鏈表的操作實際上是對指針的操作。例如,

要刪除結(jié)點首先要使指針P指向即：

上一頁

A

停止放映

下一頁

第51頁

指針的基本操作列表

?p=(NODE*)malloc(sizeof(NODE))

申請一個結(jié)點空間,并將地址送入p中.

?free(p)釋放p指針所指結(jié)點的空間

?p=q指針p指向指針q所指的結(jié)點

?p=q->next指針P指向指針q所指結(jié)點的后繼

?p=p->next指針P向后移動一個結(jié)點

?p->next=q將指針q所指結(jié)點改接為指針p所指

結(jié)點的后繼

上一頁?p->next=NULL將指針p所指結(jié)點與后繼結(jié)點斷開

停止放映

下一頁

第52頁

指針操作的舉例

p=q->nextp指向q所指結(jié)點的后繼

操作后狀態(tài)

上一頁

停止放映

下一頁

第53頁

單鏈表的查找算法

單鏈表查找算法操作步驟：

?stepl初始化，指針P指向頭指針,

計數(shù)器置0

?step2P非空且計數(shù)器小于i循環(huán)

?step3每循環(huán)一次,P后移一個位置，

計數(shù)器加1

上一頁

?step4循環(huán)結(jié)束，返回指向aj的指針P.

停止放映

下一頁

第54頁

單鏈表查找算法程序

NODE*get(NODE*head,inti)

【NODE*p;

intcounter=0;

p=head->next;

while((p!=NULL)&&(counter<i))

{p=p->next;counter++;}

if((p!=NULL)&&(counter==i))

上一頁returnp;

停止放映else

returnNULL;

下一頁

)

第55頁

單鏈表插入算法1?3

單鏈表插入算法操作步驟：

?stepl找到a2的位置，使指針p指向

?step2申請并生成新結(jié)點s

?step3使s插入到a2和aj之間

p

s->next=p->next

上一頁ai-i'p->next=s

停止放映-------s->data=x

下一頁

第56頁

單鏈表的插入算法程序

insert(NODE*head,inti,intx)

{NODE*p,*s;

if(i==1)p=head;/*若i=LP指向頭指針*/

else

p=get(head,i-1);/*令P指向人打*/

if(p==NULL)/*P為空，說明找不到i位置*/

{printf(“插入位置錯\n")；exit(O);}

elsei*P定位成功*/

上一頁{s=(NODE*)malloc(sizeof(NODE));

停止放映s->data=x;s->next=P->next;

下一頁p->next=s;

)

}第57頁

單鏈表刪除算法1?4

算法14操作步驟：

?stepl找到a2的位置，使指針p指向

?step2使指針t指向p所指結(jié)點的后或

?step3使t所指結(jié)點aj脫鏈

?step4釋放t

P1

-------?a；-------?a計］-----?

上一頁--------1-------k

t=p->next

停止放映p->next=t->next

下一頁free(t)

第58頁

單鏈表的刪除算法程序

delete(NODE*head,inti)

{NODE

if(i==1)p=head;.

elsep=get(head,i-1);}/*P定位操作*/

if(p==NULL),

{printf("i<1或i>表長+1,無此結(jié)點\rT);exit(O);}

if(p->next==NULL)

{printf("i=表長+1,無此結(jié)點\n")；exit(O);}

上一頁else/*P定位成功*/

停止放映{t=p->next;p->next=t->next;

下一頁free(t);

}

}第59頁

3、循環(huán)單鏈表和雙向鏈表|

?鏈表檢索只能從頭指針開始，且只能順

鏈表方向移動。

?在單鏈表中，從表的任一結(jié)點小找其前

趨結(jié)點，時間復(fù)雜度是O(n)。

?如果讓鏈表首尾相接，構(gòu)成環(huán)形，這

就是單循環(huán)鏈表。

鏈表可以從兩個方向檢索，效果更佳;

上一頁這就是雙向循環(huán)鏈表。

停止放映

下一頁

第60頁

單循環(huán)鏈表

單循環(huán)鏈表表示形式:

head

單循環(huán)鏈表為空的條件：headT.next-head

上一頁表示形式為：

停止放映head

下一頁

第61頁

單循環(huán)鏈表特點

?從表中任一結(jié)點出發(fā)，均可以找

到表中其它結(jié)點。

?找其前趨結(jié)點的時間復(fù)雜度是

O(n)o

上一頁

停止放映

下一頁

第62頁

雙向循環(huán)鏈表

?在單向循環(huán)鏈表中，也存在檢索前趨結(jié)點

費時的問題(所需時間是O(n))O

?雙向循環(huán)鏈表，其存儲結(jié)構(gòu)：

structdnode{

intdata；

structdnode*prior,*next；

上一頁};

typedefstructdnodeDNODE；

停止放映

下一頁

第63頁

雙向循環(huán)鏈表結(jié)點結(jié)構(gòu)I

priordatanext

|兼響后繼結(jié)點

------數(shù)據(jù)域指針域

—指向前趨結(jié)點

上一頁

指針域

停止放映

下一頁

第64頁

雙向循環(huán)鏈表表示形式

雙向循環(huán)鏈表表示形式:

head

A???

a1a2一???

單循環(huán)鏈表為空的條件：

headT.prior=headT.next=head

上一頁

表示形式為：

停止放映

下一頁AA---------------

第65頁

雙向循環(huán)鏈表特點

?適合于兩個方向的移動。

?找其前趨結(jié)點的時間復(fù)雜度是

0(1)O

上一頁

停止放映

下一頁

第66頁

十字鏈表I

[上指針

up

前趨結(jié)II后繼結(jié)

點指針一prior[data]next一點指針

down

上一頁特點：

停止放映■四個方向可

下一頁下指針以自由移動

第67頁

4、鏈表結(jié)點及標識符

約定：設(shè)指針p指向結(jié)點aj,

*aj作為一個變量，其標識符為pT

*由于pT是記錄類型，它的分量分別表示為:

數(shù)據(jù)域標識符為pT.data

后繼結(jié)點指針域為pT.next

上一頁

停止放映

pT.datapt.next

下一頁

第68頁