專題九：數(shù)據(jù)構(gòu)造知識(shí)

數(shù)據(jù)構(gòu)造是計(jì)算機(jī)軟件的一門基礎(chǔ)課程,計(jì)算機(jī)科學(xué)各個(gè)領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到

多種數(shù)據(jù)構(gòu)造.語言編譯要使用棧、散列表及語法樹；操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄

樹等；數(shù)據(jù)庫系統(tǒng)運(yùn)用線性表、多鏈表及索引樹等進(jìn)行數(shù)據(jù)管理；而在人工智能領(lǐng)域，依求解

問題性質(zhì)的差異將波及到多種不一樣的數(shù)據(jù)構(gòu)造，如廣義表、集合、搜索樹及多種有向圖等等。

學(xué)習(xí)數(shù)據(jù)構(gòu)造目的是要熟悉某些最常用的數(shù)據(jù)構(gòu)造，明確數(shù)據(jù)構(gòu)造內(nèi)在的邏輯關(guān)系，懂得它們

在計(jì)算機(jī)中的存儲(chǔ)表達(dá)，并結(jié)合多種經(jīng)典應(yīng)用闡明它們在進(jìn)行多種操作時(shí)的動(dòng)態(tài)性質(zhì)及實(shí)際的

執(zhí)行算法，深入提高軟件計(jì)和編程水平。通過對不一樣存儲(chǔ)構(gòu)造和對應(yīng)算法的對比，增強(qiáng)我們

根據(jù)求解問題的性質(zhì)選擇合理的數(shù)據(jù)構(gòu)造，并將問題求解算法的空間、時(shí)間及復(fù)雜性控制在一

定范圍的能力。

軟件設(shè)計(jì)師考試大綱對數(shù)據(jù)構(gòu)造部分的規(guī)定是純熟掌握常用數(shù)據(jù)構(gòu)造和常用算法，因此，

本專題從數(shù)據(jù)構(gòu)造的概述出發(fā)，對基本的概念引出常用的數(shù)據(jù)構(gòu)造類型的簡介和講解，同步在

講解多種數(shù)據(jù)構(gòu)造中間采用算法與數(shù)據(jù)構(gòu)造相結(jié)合的方式，在算法環(huán)節(jié)中使用數(shù)據(jù)構(gòu)造，對數(shù)

據(jù)構(gòu)造的重點(diǎn)、難點(diǎn)進(jìn)行了分析，最終講解了與數(shù)據(jù)構(gòu)造緊密有關(guān)的排序和查找算法，以及某

些以往考試題的分析。

1.數(shù)據(jù)構(gòu)造概述

數(shù)據(jù)構(gòu)造研究了計(jì)算機(jī)需要處理的數(shù)據(jù)對象和對.象之間的關(guān)系；刻畫了應(yīng)用中波及

到的數(shù)據(jù)的邏輯組織；也描述了數(shù)據(jù)在計(jì)算機(jī)中怎樣存儲(chǔ)、傳送、轉(zhuǎn)換。

學(xué)習(xí)數(shù)據(jù)構(gòu)造注意的問題：

■系統(tǒng)掌握基本數(shù)據(jù)構(gòu)造的特點(diǎn)及其不一樣實(shí)現(xiàn)。

■理解并掌握多種數(shù)據(jù)構(gòu)造上重要操作的實(shí)現(xiàn)及其性能（時(shí)間、空間）的分析。

■掌握多種數(shù)據(jù)構(gòu)造的使用特性，在算法設(shè)計(jì)中可以進(jìn)行選擇。

■掌握常用的遞歸、回溯、迭代、遞推等措施的設(shè)計(jì)

■掌握自頂向下、逐漸求精的程序設(shè)計(jì)措施。

■掌握自頂向下、逐漸求精的程序設(shè)計(jì)措施。

在學(xué)習(xí)數(shù)據(jù)構(gòu)造的知識(shí)之前，我們要理解一下數(shù)據(jù)構(gòu)造中的基本概念。

數(shù)據(jù)：對客觀事物的符號(hào)表達(dá)，在計(jì)算機(jī)中就是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序

所處理的符號(hào)的總稱。

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)的不可分割的最小單位;

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中一般作為一種整體進(jìn)行處理；一種數(shù)據(jù)元素

可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。

數(shù)據(jù)對象：是性質(zhì)相似的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一種子集。

數(shù)據(jù)構(gòu)造上的基本操作：

?插入操作?刪除操作?更新操作?查找操作?排序操作

數(shù)據(jù)構(gòu)造是指數(shù)據(jù)對象及互相關(guān)系和構(gòu)造措施，一種數(shù)據(jù)構(gòu)造B形式上可以用一種

二元組表達(dá)為B=（A,R）o其中，A是數(shù)據(jù)構(gòu)造中的數(shù)據(jù)（稱為結(jié)點(diǎn)）的#空有限集合，

R是定義在A上的關(guān)系的非空有限集合。

根據(jù)數(shù)據(jù)元素之間的關(guān)系的不一樣特性，一般有下列4類基本構(gòu)造。

>集合一一構(gòu)造中的數(shù)據(jù)元素除了“同屬于一種集合”的關(guān)系外，別無其他

關(guān)系。

>線性構(gòu)造一一構(gòu)造中的數(shù)據(jù)元素之間存在一種對一種的關(guān)系。

>樹形構(gòu)造一一構(gòu)造中的元素之間存在一種對多種的關(guān)系。

>圖狀構(gòu)造或網(wǎng)狀構(gòu)造一一構(gòu)造中的元素之間存在多種對多種的關(guān)系。

數(shù)據(jù)構(gòu)造中，結(jié)點(diǎn)與結(jié)點(diǎn)間的互相關(guān)系是數(shù)據(jù)的邏輯構(gòu)造。數(shù)據(jù)構(gòu)造在計(jì)算機(jī)中的

表達(dá)（又稱為映象）稱為數(shù)據(jù)的物理構(gòu)造，也稱存儲(chǔ)構(gòu)造。

數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不一樣的表達(dá)方式：次序映象和非次序映象，

并由此得到兩種不一樣的存儲(chǔ)構(gòu)造：次序存儲(chǔ)構(gòu)造和旌式存儲(chǔ)構(gòu)造。

任何一種算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）構(gòu)造，而算法的實(shí)現(xiàn)依賴于采用的

存儲(chǔ)構(gòu)造。

數(shù)據(jù)的邏輯構(gòu)造分為兩類：

線性構(gòu)造：線性表、棧、隊(duì)列和串

非線性構(gòu)造：樹、圖

數(shù)據(jù)的存儲(chǔ)措施有四類：

次序存儲(chǔ)措施

鏈接存儲(chǔ)措施

索引存儲(chǔ)措施

散列存儲(chǔ)措施

2.常用數(shù)據(jù)構(gòu)造

2.1線性表

在數(shù)據(jù)構(gòu)造中，線性構(gòu)造常稱為線性表，是最簡樸、最常用的一種數(shù)據(jù)構(gòu)造，它

是由n個(gè)相似數(shù)據(jù)類型的結(jié)點(diǎn)構(gòu)成的有限序歹h

其特點(diǎn)是：在數(shù)據(jù)元素的非空有限集合中，

?存在唯一的一種被稱做“第一種”的數(shù)據(jù)元素

?存在唯一的一種被稱做“最終一種”的元素?cái)?shù)據(jù)元素

?除第一種之外，集合中的每個(gè)數(shù)據(jù)元素均只有一種前驅(qū)

?除最終一種之外，集合中每個(gè)數(shù)據(jù)元素均只有一種后繼

一種由n個(gè)結(jié)點(diǎn)eO,el…,enT構(gòu)成的線性表記為:(eO,el…，en-1)。線

性表的結(jié)點(diǎn)個(gè)數(shù)稱為線怛表的K度，長度為0的線性衣稱為空的線性表，簡稱空表。對

于非空線性表，。0是線性表的第一種結(jié)點(diǎn)，a?是線性表的最終一種結(jié)點(diǎn)。線性表的結(jié)

點(diǎn)構(gòu)成了一種序列，對序列中兩個(gè)相鄰結(jié)點(diǎn)ei和CL,稱前者是后者的前驅(qū)結(jié)點(diǎn)，后者

是前者的后繼結(jié)點(diǎn)。

線性表最重要的性質(zhì)是線性表中結(jié)點(diǎn)和相對位置是確定的。

線性表的結(jié)點(diǎn)也稱為表元，或稱為記錄，規(guī)定線性表的結(jié)點(diǎn)一定是同一類型

的數(shù)據(jù)。線性表的結(jié)點(diǎn)可由若干個(gè)成分構(gòu)成，其中唯一標(biāo)識(shí)表元的成提成為關(guān)鍵字，簡

稱鍵。

線性表是一種相稱靈活的數(shù)據(jù)構(gòu)造，它的長度可以根據(jù)需要增長或縮短。對

線性表的基本運(yùn)算如卜.：

INITIATE(L)初始化操作

LENGTH(L)求長度函數(shù)

GET(L,i)取元素函數(shù)

PRIOR(L,elm)求前驅(qū)函數(shù)

NEXT(L,elm)求后繼函數(shù)

LOCATE(L,x)定位函數(shù)

INSERT(L,i,b)插入操作

DELETE(L,i)刪除操作

有多種存儲(chǔ)方式能將線性表存儲(chǔ)在計(jì)算機(jī)內(nèi)，其中最常用的是次序存儲(chǔ)和鏈接存儲(chǔ)。

根據(jù)存儲(chǔ)方式的不一樣，其上述的運(yùn)算實(shí)現(xiàn)也不一樣樣。

?次序存儲(chǔ)：是最簡樸的存儲(chǔ)方式，其特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位

置上也相鄰。一般使用一種足夠大的數(shù)組，從數(shù)組的第一種元素開始，將線性表的結(jié)點(diǎn)

依次存儲(chǔ)在數(shù)組中。

次序存儲(chǔ)方式長處：能直接訪問線性表中的任意結(jié)點(diǎn)。

線性表的第i個(gè)元素a[i]的存儲(chǔ)位置可以使用如下公式求得：LOC(a.)=LOC(al)

+(i-1)*1

式中LOC(al)是線性表的第一種數(shù)據(jù)元素al的存儲(chǔ)位置，一般稱做線性表的起始位置

或基地址。

次序存儲(chǔ)的缺陷：

1)線性表的大小固定，揮霍大量的存儲(chǔ)空間，不利于節(jié)點(diǎn)的增長和減少；

執(zhí)行線性表的插入和刪除操作要移動(dòng)其他元素，不夠以便；

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

線性表鏈接存儲(chǔ)是用鏈表來存儲(chǔ)線性表。

單鏈表(線性鏈表)：

從鏈表的第一種表元開始，將線性表的結(jié)點(diǎn)依次存儲(chǔ)在鏈表的各表元中。鏈表的每

個(gè)表元除要存儲(chǔ)線性表結(jié)點(diǎn)的信息以外，還要有一種成分來存儲(chǔ)其后繼結(jié)點(diǎn)的指針。

線性鏈表的特點(diǎn)是：每個(gè)鏈表均有一種頭指針，整個(gè)鏈表的存取必須從頭指針開始,

頭指針指向第一種數(shù)據(jù)元素的位置，最終的節(jié)點(diǎn)指針為空。當(dāng)鏈表為空時(shí)，頭指針為空

值；鏈表非空時(shí)，頭指針指向第一種節(jié)點(diǎn)。

鏈?zhǔn)酱鎯?chǔ)的缺陷：

1)由于要存儲(chǔ)地址指針，因此揮霍空間；

直接訪問節(jié)點(diǎn)不以便；

循環(huán)鏈表：

循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)構(gòu)造，是單鏈表的變形。它的特點(diǎn)就是表中最終

一種結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一種環(huán)。因此，從表中任意一種結(jié)點(diǎn)出發(fā)

都可以找到衣中的其他給點(diǎn)。

循環(huán)鏈表和單向鏈表基本一致，差異僅在于算法中循環(huán)的條件不是結(jié)點(diǎn)的指針與否

為空，而是他們的指針與否等于頭指針，

循環(huán)鏈表最終一種結(jié)點(diǎn)的萬〃5指針不為0(A0〃)，而是指向了表的前端。

為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。

循環(huán)鏈表的特點(diǎn)是：只要懂得表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。

循環(huán)鏈表的示例：

first

帶表頭結(jié)點(diǎn)的循環(huán)鏈表：

first—^廠廠-i-IV

last

雙向鏈表：

雙向鏈表是另一種形式的鏈?zhǔn)綐?gòu)造，雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直

接后繼，另一指向直接前趨。雙向鏈表克服了單鏈表的單向性的缺陷。

--------?前驅(qū)方向后繼方向

ILinkdata?Link

（左位指針）（數(shù)據(jù)）（右修指針）

雙向鏈表也可以有循環(huán)表，鏈表中存在兩個(gè)環(huán)。一種結(jié)點(diǎn)的前趨的后繼和該結(jié)點(diǎn)的后繼

的前趨都是指向該結(jié)點(diǎn)的。

P-*ZLtinkP

p==p-^lLink-^rLink==p-^rLink-^lLink

2.2棧

棧（Stack）是限定僅在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱棧頂（tc，p）,

表頭端稱棧底（bottom）o

若有棧S=（so,Sl，…，Sn-j）則So為棧底結(jié)點(diǎn)，Sn-l為棧頂結(jié)點(diǎn)。一般稱棧的結(jié)點(diǎn)

插入為進(jìn)棧，棧的結(jié)點(diǎn)刪除為出棧。由于最終進(jìn)棧的結(jié)點(diǎn)必然最先出棧，因此棧具有后

進(jìn)先出的特點(diǎn)?？梢杂靡幌乱环N圖形來形象的表達(dá)：

ML極

（JR入）

棧有兩種存儲(chǔ)構(gòu)造：次序棧和鏈棧

次序棧即棧的次序存儲(chǔ)構(gòu)造是，運(yùn)用?組地址持續(xù)的存儲(chǔ)單元依次寄存自棧底到棧

頂?shù)臄?shù)據(jù)元素，同步設(shè)指針top指示棧頂元素的目前位置。

棧也可以用鏈表實(shí)現(xiàn)，鏈?zhǔn)酱鎯?chǔ)構(gòu)造的棧簡稱鏈棧。若同步需兩個(gè)以上的棧，則最

佳采用這種構(gòu)造。對于棧上的操作，總結(jié)如下，大家可以仔細(xì)看一下這些程序，一種大

的程序都是由某些對數(shù)據(jù)構(gòu)造的小的操作構(gòu)成的。

次序存儲(chǔ)的棧的基本操作如卜.：

判斷棧滿：

intstackful1(seqstack*s)

(

return(s->top==stacksize-l);

}

進(jìn)棧：

voidpush(seqstack*s,datatypex)

{

if(stackfull(s))

error("stackverflow");

s->data[++s->top]=x;

)

top一ktop-k

■■ee

dd

cc

top-bbb

top—?a?aaa

top—?空棧a進(jìn)棧b進(jìn)棧在進(jìn)棧l進(jìn)棧源用

判斷?？?

intstackempty(seqstazk*s)

return(s->top==-1)

出棧:

datatypepop(seqstack*s)

{

if(stackempty(s))

error("stackunderflowv);

x=s->data[top];

s->top一;

return(x);

.k

top?ee

dtop—?d

d???

cctop-c

bbbb

aaaa

A退棧e退棧diU棧top-ajH棧top—空棧

鏈接存儲(chǔ)棧：用鏈表實(shí)現(xiàn)的棧，鏈表第一種元素是枝頂元素，鏈表的末尾是棧底節(jié)點(diǎn)，

鏈表的頭指針就是棧頂指針，棧頂指針為空則是空棧。若同步需要兩個(gè)以上的棧，最佳

采用鏈表作存儲(chǔ)構(gòu)造

top

鏈接存儲(chǔ)的棧的操作如下：

進(jìn)棧：

Voidpush(linkstack*p,datatypex)

(

stacknode*qq=(stacknode*)malloc(sizeo:(stacknode));

q->data=x;

q->next=p->top;

P->top=q;

)

出棧:

Datatypepop(linkstack*p)

(

datatypex;

stacknode*q=p->top;

if(stackempty(p)

error(wstackunderflow.n);

x=q->data;

p->top=q->next;

free(q);

returnx;

)

多棧處理?xiàng)８?dòng)技術(shù)：

n個(gè)棧共享一種數(shù)組空間r[同

n設(shè)置棧頂指針數(shù)組t[〃+1]和棧底指針數(shù)組b[山1]

,H力和瓦力分別指示第/個(gè)棧的棧頂與棧底，瓦，]作為控制量，指到數(shù)組最高下標(biāo)

各棧初始分派空間s=m/n指針初始值t[0]=Z>[0]=-1b\_n\=nr\

t\_/]=b\_/]=A[/-l]+s,i-1,2,,,,,n~\

maxSke1

初始狀態(tài)

40)UHt[2]t[3]W

maxSiuJ

V某時(shí)刻狀態(tài)

t

MO]一川]T[4]

maxSi"1

插入力之后

2.3隊(duì)列

隊(duì)列是只容許在一端進(jìn)行插入，另一端進(jìn)行刪除運(yùn)算的線性表。容許刪除的那一端

稱為隊(duì)首(front),容許插入運(yùn)算的另一端稱為隊(duì)尾(rear)<,一般稱隊(duì)列的結(jié)點(diǎn)插

入為進(jìn)隊(duì)，隊(duì)列的結(jié)點(diǎn)刪除為出隊(duì)。若有隊(duì)列

Q=(qo,q”…，qi)則q0為隊(duì)首結(jié)點(diǎn)，qi為隊(duì)尾結(jié)點(diǎn)。因最先進(jìn)入隊(duì)列的結(jié)點(diǎn)將

最先出隊(duì)，因此隊(duì)列具有先進(jìn)先出的特性。

frontrear

可以用次序存儲(chǔ)線性表來表達(dá)隊(duì)列，也可以用鏈表實(shí)現(xiàn)，用鏈表實(shí)現(xiàn)的隊(duì)列稱為鏈隊(duì)

列。

隊(duì)列操作：

①inipush(PNODE*top,inte)是進(jìn)棧函數(shù)，形參lop是棧頂指針的指針，形參e

是入棧元素。

②intpop(PNODE*top,intoe)是出棧函數(shù)，形參top是棧頂指針的指針，形參e

作為返回出棧元素使用。

③intenQucue(PNODE*tail,inte)是入隊(duì)函數(shù),形參tail是隊(duì)尾指針的指針，

形參c是入隊(duì)元素。

?intdeQueue(PNODE*tail,int*e)是出隊(duì)函數(shù)，形參tail是隊(duì)尾指針的指針,

形參e作為返回出隊(duì)元素使用。

front二front-front-fronts

空網(wǎng)做隊(duì)B進(jìn)隊(duì)CD進(jìn)隊(duì)A出隊(duì)B出隊(duì)EF進(jìn)隊(duì)

定義結(jié)點(diǎn)的構(gòu)造如下：

typedefstructnode{

intvalue;

structnode*next：

INODE,*PNODE;

[函數(shù)①]

intpush(PNODE*top,inte)

PNODEp=(PNODE)malloc(sizeof(NODE));

if(!p)return-1;

p->value=e;

p->noxt=*top;〃指向棧頂指針

*top=p;

return0;

)

[函數(shù)②]

intpop(PNODE*top；int*e)

{

PNODEp=*top;

if(p==NULL)return-1;

*o=p->value;

*top=p->ncxl;〃棧頂指向取出的數(shù)的指針

free(p);

return0;

)

[函數(shù)③]

intenQueue(PNODE火tail,inte)

{PNODEp,t：

t=*tail;

p=(PNODE)ma11oc(sizeof(NODE))；

if(!p)return_1;

p->value=e;

p->next=t—>next;

t->next=p;〃將元素加在尾指針后

*tail=p;

return0;

)

[函數(shù)④]

intdeQueue(PNODE-tail,inte)

{

PNODEp,q；

if((*tail)->next==*tail)return-1;〃隊(duì)列已經(jīng)空

p=(*tail)->next;〃p獲得尾指針

q=p->next;

e=q->value;

p->next-q->ncxt;

if(*tai1=q)

*tail=p;//'尾指針指向最終節(jié)點(diǎn)

free(q);

return0;

)

循環(huán)隊(duì)列(CircularQueue):

存儲(chǔ)隊(duì)列的數(shù)組被當(dāng)作首尾相接的表處理。

隊(duì)頭、隊(duì)尾指針加1時(shí)從rS/ze-1直接進(jìn)到0,可用語言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。

隊(duì)頭指針進(jìn)1:front-(front+1)%maxSize\

隊(duì)尾指針進(jìn)1：real'=(rear+1)%maxSize;

隊(duì)列初始化：front=rear=0:

隊(duì)空條件：front==rear,

隊(duì)滿條件：｛rear+1)%maxSize==front

循環(huán)隊(duì)列的進(jìn)隊(duì)和出隊(duì)：

優(yōu)先級(jí)隊(duì)列：是不一樣于先進(jìn)先出隊(duì)列的另一-種隊(duì)列。每次從隊(duì)列中取出的是具有最

高優(yōu)先權(quán)的元素

2.4串

字符串是非數(shù)值處理應(yīng)用中重要的處理對象。字符串是由某字符集上的字符所構(gòu)成

的任何有限字符序列。

當(dāng)一種字符串不包括任何字符時(shí)，稱它為空字符自。一?種字符串所包括的有效字符

個(gè)數(shù)稱為這個(gè)字符串的長度。一種字符串中任一持續(xù)的子序列稱為該字符串的子串。包

括子串的字符串對應(yīng)稱為主串。一般稱該字符在序列中的序號(hào)為該字符在串中的位置。

字符串的串值必須用單引號(hào)括，'C&C3…Cn起來，但單引號(hào)自身不屬于串，它的作

用是為了防止于變量名和數(shù)的常量混淆。在C語言中，字符串常量是用一對雙引號(hào)括住

若干字符來表達(dá),如“Iamastudent"

字符串一般存于字符數(shù)組中，每個(gè)字符串最終一種有效字符后跟一種字符串結(jié)束符

“\0”.系統(tǒng)提供的庫函數(shù)形成的字符串會(huì)自動(dòng)加結(jié)束符號(hào)，而顧客的應(yīng)用程序中形成

的字符串必須由程序自行負(fù)責(zé)添加字符串結(jié)束符號(hào)。

兩個(gè)串相等當(dāng)且僅當(dāng)兩個(gè)串的值相等，長度相等并且各個(gè)對應(yīng)位置的字符都相等。

常用的字符串的基本操作有7種。

ASSING(s,t)和CREAT(s,ss)賦值操作

EQUAL(s,t)判等函數(shù)

LENGTH(s)求長度函數(shù)

CONCAT(s,t)聯(lián)接函數(shù)

SUBSTR(s,start,len)求子串函數(shù)

INDEX(s,t)定位函數(shù)

REPLACE(s,t,v)置換函數(shù)

INSERT(s,pos,t)插入函數(shù)

DELETE(s,pos,t)刪除函數(shù)

(1)求字符串長,intstrlen(chars)

(2)串復(fù)制(copy)

char*strcpy(charto,charfrom);

該函數(shù)將串from復(fù)制到串to中，并且返回一種指向串to的開始處的指針。

(3)聯(lián)接(concatenation)

charstrcat(charto,charfrom)

該函數(shù)將串from復(fù)制到串to的末尾，并且返回一種指向串to的開始處的指針。

(4)串比較(compare)

intstrcmp(chars1,chars2);

該函數(shù)比較串si和串s2的大小，當(dāng)返回值不不小于0,等于0或不小于0時(shí)分別

表達(dá)sl<s2或sl=s2或sl>s2

例如：result:strcmp("baker"，"Bakerw)result>0

result=strcmp(“12","12")；result=0

result=strcmp(“Joe”Joseph");result<0

(5)字符定位(index)

charstrehr(chars,charc);

該函數(shù)是找c在字符串中第一次出現(xiàn)的位置，若找到則返回該位置，否則返回NULL。

字符串的靜態(tài)存儲(chǔ)：次序存儲(chǔ)、用一組地址持續(xù)的地址單元存儲(chǔ)率的字符序列，尤其是

在PASCAL程序語言中還可以采用緊縮數(shù)組來實(shí)現(xiàn)。

字符串的動(dòng)態(tài)存儲(chǔ)：采用鏈表的方式存儲(chǔ)字符串，節(jié)點(diǎn)的大小可以不一樣，即每個(gè)節(jié)點(diǎn)

可以寄存的字符數(shù)是不一樣的。對于節(jié)點(diǎn)大小不小于1的鏈表，需要設(shè)置頭指針和尾指

針來定位和串連接。

存儲(chǔ)密度：串值所站的存儲(chǔ)位/實(shí)際分派的存儲(chǔ)位

實(shí)際應(yīng)用的串處理系統(tǒng)中采用的是動(dòng)態(tài)存儲(chǔ)構(gòu)造，每個(gè)串的值各自存儲(chǔ)在一組地址

持續(xù)的存儲(chǔ)單元中，存儲(chǔ)地址布程序執(zhí)行過程中動(dòng)態(tài)分派。運(yùn)用串名和串值之間的的對

應(yīng)關(guān)系來建立存儲(chǔ)吠象來訪問串。

2.5數(shù)組

數(shù)組是最常用的數(shù)據(jù)構(gòu)造之一，在程序中，數(shù)組常用來實(shí)現(xiàn)次序存儲(chǔ)的線性表。數(shù)

組由固定個(gè)數(shù)的元素構(gòu)成，所有元素的類型相似，元素依次次序存儲(chǔ)。每個(gè)元素對應(yīng)一

種下標(biāo)，數(shù)組元素按數(shù)組名和元素的下標(biāo)引用，引用數(shù)組元素的下標(biāo)個(gè)數(shù)稱為數(shù)組的維

數(shù)。

在C語言中，n個(gè)元素的數(shù)組中，第一種元素的下標(biāo)為0,最終一種的下標(biāo)為nT;

數(shù)組可以分為一維、二維……N維數(shù)組，取決于引用數(shù)組元素的下標(biāo)的個(gè)數(shù)；

一維數(shù)組：

O____12345678____9

?[35廠27I4廠]18I石(J廠％I77I8丁丁”廠I(J21

IIIIll\lll

l?W+4Ti-

二維數(shù)組和三維數(shù)組:

數(shù)組可以分為靜態(tài)數(shù)組和動(dòng)態(tài)數(shù)組兩類，所謂靜態(tài)就是指數(shù)組的空間存儲(chǔ)分派是在

使用之前還是在程序運(yùn)行當(dāng)中分派，靜態(tài)數(shù)組就是在定義時(shí)必須進(jìn)行空間分派，也就是

固定數(shù)組的大小，這樣就不利于數(shù)組的擴(kuò)展。同樣動(dòng)態(tài)數(shù)組就是在程序運(yùn)行過程中進(jìn)行

數(shù)組的賦值或者是空間的分派，動(dòng)態(tài)數(shù)組一般采用鏈表的存儲(chǔ)構(gòu)造，而靜態(tài)數(shù)組一般采

用次序存儲(chǔ)構(gòu)造。

數(shù)組元素可以是任何類型的，當(dāng)元素白身又是數(shù)紐時(shí)，就構(gòu)成多維數(shù)組。多維數(shù)組

是一維數(shù)組的推廣，多維數(shù)組中最常用的是二維數(shù)組c多維數(shù)組的所有元素并未排在一

種線性序列里.，要次序存儲(chǔ)多維數(shù)組按需要按一定次序把所有的數(shù)組元素排在一種線性

序列里，常用的排列次序有行優(yōu)先次序和列優(yōu)先次序.對于多維數(shù)組，C語言按行優(yōu)先

次序寄存。

對于數(shù)組，一般只有兩種操作：

?給定一種下標(biāo)，存取對應(yīng)的數(shù)據(jù)元素

?給定一組下標(biāo)，修改對應(yīng)數(shù)據(jù)元素的某一種或兒種數(shù)據(jù)項(xiàng)的值。

一般用多維數(shù)組表達(dá)矩隴，詳細(xì)有如下幾種類型：

對稱矩陣:A[i,j]==A[j,i]

三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。

上三角矩陣中，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣恰好相

反，它的主對角線上方均為常數(shù)，在大多數(shù)狀況下，三角矩陣常數(shù)為零。

三角矩陣可壓縮存儲(chǔ)到向量sa[0..n(n+l)/2]中,sa[k]和aij的對應(yīng)關(guān)系是：

fi(2n-i+l)/2+j-i當(dāng)iMj時(shí)

k=|n(n4-1)/2當(dāng)1＞」時(shí)

3、對角矩陣

對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除

了土對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其他元素皆為零。

當(dāng)時(shí)，元素二0。

LOC(i,j)=L0C(0,0)+[3*i-l+(j-i+1)]=L0C(0,0)+(2i+j)

4.稀疏矩陣

簡樸說，設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)不不小于矩陣元素的總數(shù)(即s^mXn),

并且分布沒有一定規(guī)律。用次序存儲(chǔ)構(gòu)造的三元組對稀疏矩陣進(jìn)行存儲(chǔ)，分別記錄行、

列和值

彳r5J

|<>|o322

111oG1與

|2|111

11-7

23<?

3手

|C|<>?>1

§2

0000910

0110000<<,<>/>

轉(zhuǎn)置矩陣

0000028l<>1<>

111111

220?6000|2|N2K

000000|3|322

川3

01703900

1^1不1~7

1500000IEr

|7|61<?

十字鏈表:

由于非零元的位置和個(gè)數(shù)變化,因此用鏈表存儲(chǔ)更恰當(dāng)；在這種狀況下采用十字鏈

表來表達(dá)，每個(gè)非零元用一種節(jié)點(diǎn)表達(dá)，節(jié)點(diǎn)中有行、列尚有向下的域和線右的域;

此外還需要一種指向列鏈表的表頭節(jié)點(diǎn)和指向行鏈表的表頭節(jié)點(diǎn)。還可以設(shè)置i種指向

整個(gè)十字鏈表的表頭節(jié)點(diǎn)。還可以把列表頭和行表頭節(jié)點(diǎn)構(gòu)成數(shù)組，便于操作；

多種廣義表達(dá)意圖

2.6樹

2.6.1概述

樹型構(gòu)造是一類重要的非線性數(shù)據(jù)構(gòu)造。其中以樹和二叉樹最為常用，直觀看來，樹是

以分支關(guān)系定義的層次構(gòu)造。

樹是由一種或多種結(jié)點(diǎn)構(gòu)成的有限集7\它滿足如下兩個(gè)條件：

I.有一種特定的結(jié)點(diǎn)，成為根結(jié)點(diǎn)

II.其他的結(jié)點(diǎn)提成/〃（加>=0）個(gè)互不相交的有限集以刀，…，北大其中每個(gè)集合又

都是一棵樹，稱T。,刀，…，北”為根結(jié)點(diǎn)的子樹。

這里可以看出樹的定義是遞歸的，即一棵樹由子樹構(gòu)成，子樹又由更小的子樹構(gòu)成。一

種結(jié)點(diǎn)的子樹數(shù)目，稱為結(jié)點(diǎn)的度。樹中各結(jié)點(diǎn)的度的最大值則稱為樹的度。樹中結(jié)點(diǎn)

的最大層次稱為樹的深度。

假如將樹中結(jié)點(diǎn)的各子樹當(dāng)作從左到右是有次序的（即不能互換），則稱該樹為有序樹,

否則為無序樹。森林是m（m>=0）棵互不相交的樹的集合。

存儲(chǔ)構(gòu)造

樹是非線性的構(gòu)造，不能簡樸地用結(jié)點(diǎn)的線性衣來表達(dá)。樹有多種形式地存儲(chǔ)構(gòu)造，最

常用的是原則存儲(chǔ)形式和帶逆存儲(chǔ)形式。在樹的原則存儲(chǔ)構(gòu)造中，樹中的結(jié)點(diǎn)可提成兩

部分：結(jié)點(diǎn)的數(shù)據(jù)和指向子結(jié)點(diǎn)的指針。當(dāng)程序需從結(jié)點(diǎn)返回到其父結(jié)點(diǎn)時(shí)，需要在樹

的結(jié)點(diǎn)中存儲(chǔ)其父結(jié)點(diǎn)的位置信息，這種存儲(chǔ)形式就是帶逆存儲(chǔ)構(gòu)造。

詳細(xì)使用的鏈表構(gòu)造有：

?雙親表達(dá)法：運(yùn)用每個(gè)節(jié)點(diǎn)只有一種雙親的特點(diǎn)；求節(jié)點(diǎn)的孩子時(shí)要遍歷整個(gè)

向帚

?孩子表達(dá)法：把每個(gè)節(jié)點(diǎn)的孩子都排列起來，一單鏈表存儲(chǔ)，則n個(gè)節(jié)點(diǎn)有n

個(gè)孩子鏈表，而n個(gè)頭指針又構(gòu)成了一種線性表。

?孩子兄弟表達(dá)法（又稱二叉樹表達(dá)法，或二叉鏈表表達(dá)法）：節(jié)點(diǎn)兩個(gè)指針分

別指向該節(jié)點(diǎn)的第一種孩子和下一種兄弟節(jié)點(diǎn)。

樹的遍歷

在應(yīng)用樹構(gòu)造時(shí)，常規(guī)定按某種次序獲得樹中所有結(jié)點(diǎn)的信息、，這可通過樹

的遍歷操作來實(shí)現(xiàn)。常用的樹的遍歷措施有：

樹的前序遍歷：首先訪問根結(jié)點(diǎn)，然后從左到右遍歷根結(jié)點(diǎn)的各棵子樹。

樹的后序遍歷：首先從左到右按后序遍歷根結(jié)點(diǎn)的各棵子樹，然后訪問根結(jié)

點(diǎn)。

樹的層次遍歷：首先訪問處在0層上的根結(jié)點(diǎn)，然后從左到右依次訪問處在

1層、2層……上的結(jié)點(diǎn)，即自上而下從左到右逐層訪問樹各層上

的結(jié)點(diǎn)。

2.6.2二叉樹

概述

與一般的樹的構(gòu)造比較，二叉樹在構(gòu)造上更規(guī)范和更有確定性，應(yīng)用也比樹更為廣

泛。

二叉樹的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹（即二叉樹中不存在度不小于2的結(jié)點(diǎn)），

并且，二叉樹的子樹有左右之分，另一方面序不能任意顛倒。二叉樹與樹不一樣的地方

在于，首先一叉樹可認(rèn)為空，空的一叉樹沒有結(jié)點(diǎn)；比外，在一叉樹中，結(jié)點(diǎn)的子樹是

有序的，分左右兩棵子二叉樹。

二叉樹采用類似樹的原則存儲(chǔ)形式來存儲(chǔ)。

二叉樹的性質(zhì)：

二叉樹具有下列重要特性。

?在二叉樹的第i層至多有個(gè)結(jié)點(diǎn)（i>=1）o

?深度為k的二叉樹至多有22-1個(gè)結(jié)點(diǎn)（k>=Do

?對任何一棵二叉樹T,假如其終端結(jié)點(diǎn)數(shù)為no,度為2的結(jié)點(diǎn)數(shù)為n2,則nO=n2+l.

?具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為U°g2〃」+L

二叉樹的遍歷

樹的所有遍歷措施都合用于二叉樹，常用的二叉樹遍歷措施有3種。

#include<stdio.h>

#include<stdlib.h>

^defineNULL0

Typedefstructnode(

chardata;

structnode*lchild,*rchild;

}TREENODE;

TREENODE*root;

前序遍歷：

?訪問根結(jié)點(diǎn)，

?按前序遍歷根結(jié)點(diǎn)的左子樹，

?按前序遍歷根結(jié)點(diǎn)的右子樹。

中序遍歷：

?按中序遍歷根結(jié)點(diǎn)的左子樹，

?訪問根結(jié)點(diǎn)，

?按中序遍歷根結(jié)點(diǎn)的右子樹。

中序遍歷算

法：

Voidinorder(TREENODE*p)

(

if(p!=NULL)

{inorder(p->lchild);

printf(a%cw,p->data)

inorder(p->rchild);

)

)

后序遍歷：

?按后序遍歷根結(jié)點(diǎn)的左子樹，

?按后序遍歷根結(jié)點(diǎn)的右子樹，

?訪問根結(jié)點(diǎn)。

以上3種遍歷措施都是遞歸定義的。

哈夫曼及其應(yīng)用：又稱為最優(yōu)樹，是一類帶權(quán)途徑長度最短的樹

途徑長度：從樹中一種干點(diǎn)到另一種節(jié)點(diǎn)之間的分支構(gòu)成的這兩個(gè)節(jié)點(diǎn)之間的途徑，途

徑上的分支樹木就稱為途徑長度；

樹的途徑長度：從樹根到每一節(jié)點(diǎn)的途徑長度之和；

樹的帶權(quán)途徑長度：樹中所有葉子節(jié)點(diǎn)的帶權(quán)途徑長度之和；

哈夫曼樹就是一棵n個(gè)P-子節(jié)點(diǎn)的二義樹，所有葉子節(jié)點(diǎn)的帶權(quán)之和最小。

算法描述：

給定n個(gè)節(jié)點(diǎn)的集合，每個(gè)節(jié)點(diǎn)都帶權(quán)值；

選兩個(gè)權(quán)值最小的節(jié)點(diǎn)構(gòu)造一棵新的二叉樹，新二叉樹的根節(jié)點(diǎn)的權(quán)值就是兩個(gè)子節(jié)點(diǎn)

權(quán)值之和；

從n個(gè)節(jié)點(diǎn)中刪除剛剛使用的兩個(gè)節(jié)點(diǎn)，同步將新產(chǎn)生的二叉樹根節(jié)點(diǎn)放在節(jié)點(diǎn)集合中。

反復(fù)2,3步，懂得只有一棵樹為止。

I*'t<7><5><2><4>I**t<7><5><6>

田田田卬ELJ(D看\

<n)初始

<?>>令用｛2〉<4>

<<l><111

例題：己知節(jié)點(diǎn)的前序序列和中序序列分別為:

前序序列：ABCDEFG

中序序列：CBEDAFG

求出整個(gè)一叉樹，以及構(gòu)造過程

2.7圖

基本概念：

圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)構(gòu)造。在圖形構(gòu)造中，結(jié)點(diǎn)之間的關(guān)系可以是任

意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都也許有關(guān)。

一種圖G由非空有限的頂點(diǎn)集合V和有限的邊的集合E構(gòu)成，記為G=(V,E)。圖一般

分為兩種類型。

無向圖

無向圖的邊是頂點(diǎn)的無序偶，用(i,j)來表達(dá)頂點(diǎn)i和j之間的邊。

有向圖

有向圖的邊是頂點(diǎn)的有序偶，有向圖的邊也成為弧，用＜i,j〉來表達(dá)頂點(diǎn)i和j之間的

弧。

其中，有2條邊的無向圖稱為完全圖，而具有n(n-l)條弧的有向圖成為有向完全

圖。

有時(shí)圖的邊或弧具有與它有關(guān)的樹，這種與圖的邊或弧有關(guān)的數(shù)稱作權(quán)。帶權(quán)圖也簡稱

為網(wǎng)。

假如同為無向圖或同為有向圖的兩個(gè)圖Gl=(V.,Ei)和G2=(V2,E2)滿足

V.CV.E二GEI則稱圖G2是圖

G1的子圖。

頂點(diǎn)的度就是指和頂點(diǎn)有關(guān)聯(lián)的邊的數(shù)目。在有向圖中，以頂點(diǎn)v為頭的弧的數(shù)據(jù)成為

v的入度；以v為尾的弧成為v的出度。這里有一種重要的公式反應(yīng)了頂點(diǎn)和邊的關(guān)系。

1?

其中，e表達(dá)邊的數(shù)目，n表達(dá)頂點(diǎn)個(gè)數(shù)，TD(Vi)表達(dá)頂點(diǎn)明的度。

在圖G=(V,E)中，假如存在頂點(diǎn)序列(vo,V),???,v。，其中Vo=p,vk=q,

且(vo,V)),(vi,v2)—>(Vk-i,vk)都在E中，則稱頂點(diǎn)p到頂點(diǎn)q有一條途

徑，并用(V。，v?Vk)表達(dá)這條途徑，途徑的長度就是途徑上的邊或弧的數(shù)目，

這條途徑的長度為k。假如第一種頂點(diǎn)和最終一種頂點(diǎn)相似的途徑稱為回路或

環(huán)。序列中頂點(diǎn)不反復(fù)出現(xiàn)的途徑稱為簡樸途徑。

對無向圖而言，假如從任意兩個(gè)不一樣頂點(diǎn)i和j之間均有途徑，則該無向圖是連

通的。無向圖中的極大連通子圖為該圖的連通分量。

對有向圖而言，假如任意兩個(gè)不一樣頂點(diǎn)i到j(luò)有途經(jīng)，同步j(luò)到i也有途徑，則該有

向圖是強(qiáng)連通的。同樣，無向圖中的極大連通強(qiáng)子圖為該圖的強(qiáng)連通分量。

存儲(chǔ)構(gòu)造:最常用的存儲(chǔ)構(gòu)造是有兩種。

鄰接矩陣：

這是反應(yīng)頂點(diǎn)間鄰接關(guān)系的矩陣。定義如下：

設(shè)6=(V,E)是具有n(n21)個(gè)頂點(diǎn)的圖，G的鄰接矩陣M是一種n行n列的矩陣，

若(i,j)或<i,j>￡E,5WM[i][j]=l；否則M[i][j]=O°

鄰接表:這是圖的鏈?zhǔn)酱鎯?chǔ)構(gòu)造。

圖的每個(gè)頂點(diǎn)都建立了一種鏈表，且第i個(gè)鏈表口的結(jié)點(diǎn)代表與頂點(diǎn)i有關(guān)聯(lián)的一

條邊或由頂點(diǎn)i出發(fā)的一條弧。而這些鏈表的頭指針則構(gòu)成一種次序線性表。

此外，尚有其他的某些存儲(chǔ)構(gòu)造，如十字鏈表和鄰接多重表，分別用來存儲(chǔ)有向圖和無

向圖。

圖的遍歷：

圖的遍歷是指從圖中的某個(gè)頂點(diǎn)出發(fā)，沿著圖中的邊或弧訪問圖中的每個(gè)頂點(diǎn)，并

且每個(gè)頂點(diǎn)只被訪問一次。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵途

徑等算法的基礎(chǔ)。

一般有兩種措施，它們對無向圖和有向圖都合用。

深度優(yōu)先搜索：

類似于樹的先根遍歷。

廣度優(yōu)先搜索：

類似于樹的層次遍歷。

這兩種算法的時(shí)間復(fù)雜度相似，不一樣之處僅僅在于對頂點(diǎn)訪問的次序不一樣。

■圖的有關(guān)算法

波及到圖的有關(guān)算法比較多，這里只簡樸歸納簡介一下，詳細(xì)算法但愿大家參照有關(guān)

資料。

?求最小代價(jià)生成樹

設(shè)G=(V,E)是一種連通的無向圖，若Gi是包括G中所有頂點(diǎn)的一種無回路的連通子圖,

則稱Gi為G的一棵生成樹。其中代價(jià)最小(各條邊的權(quán)值之和最小)的生成樹就稱為最小

代價(jià)牛.成樹(簡稱最小生成樹)。

這里提供兩種算法來求解這一問題：普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法。

分別合用于求邊稠密的網(wǎng)的最小生成樹和邊稀疏的網(wǎng)的最小生成樹，其時(shí)間復(fù)雜度分別是

0(/)和O(eloge)(e為網(wǎng)中邊的數(shù)目)。

其中prim算法基本思想：任選一種頂點(diǎn)V。開始，連接與v。近來的頂點(diǎn)力,得子樹

T.,再連接與「近來的頂點(diǎn)V2,得子樹％,如此進(jìn)行下去，直到所有頂點(diǎn)都用到為止。

L(v):v到子樹T。的直接距離。E是邊集合。

輸入加權(quán)連通圖的帶權(quán)鄰接矩陣C=(CG的.

(1)To?空集,C(To)<-0,Vi={v0}

(2)對每一點(diǎn)v屬于V-Vi,L(v)<-C(v,Vo);［假如(v,Vo)不屬于E,則C(v,%)=無

窮大］

(3)若%=V,則輸出T。，C(To)，停機(jī)°否則轉(zhuǎn)到下一步;

(4)在V-%中找一點(diǎn)u,使L(炎=min{L(v)|v屬于(V-%)},并記在％中與u相鄰的點(diǎn)

為w,e=(w,u)

⑸To<-T0U,C(L)<-C(To)+C(e),%T】U{〃)

(6)對所有的v屬于V-%,若C(v,u)〈L(v),則L(v)<-C(v,u),否則L(v)不

變。

⑺轉(zhuǎn)3

克魯斯卡爾(Kruskal)算法基本思想：最初把圖的n個(gè)頂點(diǎn)看作n個(gè)分離的部分樹，

每個(gè)樹具有一種頂點(diǎn)，算法的每一步選擇可連接兩分離樹的邊中權(quán)最小的邊連接兩個(gè)部

分樹，合二為一，部分樹逐漸減少，直到只有一種部分樹，便得到最小生成樹。

克魯斯卡爾(Kruskal)算法環(huán)節(jié):

T。：寄存生成樹的邊的集合，初態(tài)為空；

C(To):最小生成樹的權(quán),初值為0：

VS：部分樹的頂點(diǎn)集合,其初值為{{v0}{v.}……{V.)}

輸入邊的端點(diǎn)數(shù)組A(e),邊的權(quán)值w(e);

(1)T。為空，C(T0)<-O;VS為空，將E中的邊按從小到大的次序排列成隊(duì)列Q；

(2)對所有的v屬于V,VS<-{v};

(3)若|VS|=1,輸出To,C(T。)，停止，否則轉(zhuǎn)下一步；

(4)從Q中取出排頭邊(u,v),并從Q中刪除(u,v);

(5)如u,v雜VS的同一種元素集V,中，則轉(zhuǎn)4,否則分屬于兩個(gè)幾種1丫2,

進(jìn)行下一步；

(6)T0<-T。U{(〃,")},v<-ViUy2>C(L)<-C(To)+C(u,v),轉(zhuǎn)3

?求最短途徑

在圖中求最短途徑問題有兩種提法，一是求從某個(gè)源點(diǎn)到其他頂點(diǎn)的最短途徑，二是求每一對

頂點(diǎn)之間的最短途徑■>

對于前者，一般采用迪杰斯特拉(Dijkstra)算法，按途徑長度遞增的次序產(chǎn)生最短途徑。時(shí)

間復(fù)雜度為0(/)。

迪杰斯特拉(Dijkstra)算法的基本思想：生長一棵以V。為根的最短路樹，在這棵樹上

每一頂點(diǎn)與根之間的途徑都是最短途徑。由于網(wǎng)絡(luò)不存在負(fù)權(quán)，最短路樹的生長過程中

各頂點(diǎn)將按照距V。的遠(yuǎn)近及頂點(diǎn)的相鄰關(guān)系，逐次長入樹中，先近后遠(yuǎn)，直至所有頂點(diǎn)

都已經(jīng)在樹中。

處理背面一種問題的措施是：每次以一種頂點(diǎn)為源點(diǎn)，反復(fù)執(zhí)行迪杰斯特拉算法n次。

此外還可以使用一種弗洛伊德(Floyd)算法，其時(shí)叵復(fù)雜度也是0(n，

弗洛伊德(Floyd)算法基本思想：直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的措施依次

構(gòu)造出n個(gè)矩陣，口”刀,2，..。句,使最終得到的矩陣。<"成為圖的距離矩陣，同步也求出

插入點(diǎn)矩陣以便得到兩點(diǎn)見的最短途徑。

?拓?fù)渑判?/p>

拓?fù)渑判虻乃惴ㄔ韺?shí)后很簡樸。

I.在有向圖中選i種沒芍前驅(qū)的頂點(diǎn)且輸出之

II.從圖中刪除該頂點(diǎn)和所有以它為尾的弧

反復(fù)執(zhí)行以上兩步，直至所有頂點(diǎn)均已輸出，或者目前圖中不存在無前驅(qū)的頂點(diǎn)為

止。后一種狀況則闡明有向圖中存在環(huán)。

?求關(guān)鍵途徑

在AOE網(wǎng)絡(luò)中的某些活動(dòng)可以并行的進(jìn)行，因此完畢工程的至少時(shí)間是從開始頂點(diǎn)到

結(jié)束頂點(diǎn)的最長途徑K度，稱從開始頂點(diǎn)到結(jié)束頂點(diǎn)的最K途徑為關(guān)鍵途徑，關(guān)鍵途徑

上的活動(dòng)即為關(guān)鍵活動(dòng)。

3.數(shù)據(jù)構(gòu)造有關(guān)算法

3.1排序算法

基本概念

排序(Sorting)是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，其功能是對一種數(shù)據(jù)元素集合

或序列重新排列成一種按數(shù)據(jù)元素某個(gè)項(xiàng)值有序的序列。作為排序根據(jù)的數(shù)據(jù)項(xiàng)稱為

“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。為了便于查找，一般但愿計(jì)算機(jī)中的數(shù)據(jù)表是按

關(guān)鍵碼有序的。如有序表的折半查找，查找效率較高。尚有，二叉排序樹、B-樹和B+

樹的構(gòu)造過程就是一種排序過程。若關(guān)鍵碼是主關(guān)鍵碼，則對于任意待排序序列，經(jīng)排

序后得到的成果是唯一的；若關(guān)鍵碼是次關(guān)鍵碼，排序成果也許不唯一，這是由于具有

相似關(guān)鍵碼的數(shù)據(jù)元素，這些元素在排序成果中，它們之間的的位置關(guān)系與排序前不能

保持。

若對任意的數(shù)據(jù)元素序列，使用某個(gè)排序措施，對它按關(guān)鍵碼進(jìn)行排序：若相似關(guān)

鍵碼元素間的位置關(guān)系，排序前與排序后保持一致，稱此排序措施是穩(wěn)定的；而不能保

持一致的排序措施則稱為不穩(wěn)定的。

排序分為兩類：內(nèi)排序和外排序。

內(nèi)排序：指待排序列完全寄存在內(nèi)存中所進(jìn)行的排序過程，適合不太大的元素序列。

外排序：指排序過程中還需訪問外存儲(chǔ)器，足夠大的元素序列，因不能完全放入內(nèi)存，

只能使用外排序。

對于有n個(gè)結(jié)點(diǎn)的線性表(cO,el,en-1),將結(jié)點(diǎn)中某些數(shù)據(jù)項(xiàng)的值按遞增

或遞減的次序，重新排列線性表結(jié)點(diǎn)的過程，稱為排序。排序時(shí)參照的數(shù)據(jù)項(xiàng)稱為排序

碼，?般選擇結(jié)點(diǎn)的鍵值作為排序碼。

若線性表中排序碼相等的結(jié)點(diǎn)經(jīng)某種排序措施進(jìn)行排序后，仍能保持它們在排序之前的

相對次序，稱這種排序措施是穩(wěn)定的；否則，稱這種排序措施是不穩(wěn)定的。

在排序過程中，線性表的所有結(jié)點(diǎn)都在內(nèi)存，并在內(nèi)存中調(diào)整它們在線性表中的存儲(chǔ)次

序，稱為內(nèi)排序。在排序過程中，線性表只有部分結(jié)點(diǎn)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整結(jié)

點(diǎn)在外存中的寄存次序的排序措施成為外排序。

下面通過一種表格簡樸簡介幾種常見的內(nèi)排序措施，以及比較一下它們之間的性能特

點(diǎn)。

排序措施簡介平均時(shí)最壞狀輔助存與否穩(wěn)

間況儲(chǔ)定

反復(fù)從尚未排好序的那部分線

性表中選出鍵值最小的結(jié)點(diǎn)，并

按從線性表中選出的次序排列

選擇

結(jié)點(diǎn)，重料構(gòu)成線性表。直至未0(吟。（爐）0(1)不穩(wěn)定

排序

排序的那部分為空，則重新形成

的線性表是一種有序的線性表。

（單項(xiàng)選擇擇排序）

假設(shè)線性表的前面I個(gè)結(jié)點(diǎn)序列

eO,el,…，el-1是已排序的。對

簡結(jié)點(diǎn)在這有序結(jié)點(diǎn)ei序列中找插

直接

樸入位置，并將ei插入，而使i+1

插入0(吟0(*0(1)穩(wěn)定

排個(gè)結(jié)點(diǎn)序列eO,el,…，ei也變

排序

序成排序的。依次對i=l>2,…，

n-1分別執(zhí)行這樣的播入環(huán)節(jié)，最

然眼照榭姍序。

對目前尚未排好序的范圍內(nèi)的

所有結(jié)點(diǎn)，自上而下對相鄰的兩

個(gè)結(jié)點(diǎn)依次進(jìn)行比較和調(diào)整，讓

冒泡

鍵值大的結(jié)點(diǎn)往下沉，鍵值小的0(*0(*0(1)穩(wěn)定

排序

結(jié)點(diǎn)往上冒。即，每當(dāng)兩相鄰比

較后發(fā)現(xiàn)它們的排列次序與排

序規(guī)定相反時(shí)，就將它們互換。

對直接才由入排序一種改善，又稱

“縮小增量排序”。為1有整個(gè)副F

序列分割成為若干子序列分別進(jìn)

行直接插入排序,待整個(gè)序列中的

希爾排序knInnO(logn)不穩(wěn)定

記錄“基本有序”時(shí)，再對全體記。(*

錄進(jìn)行一次直接插入排序。，假如

待排序記錄序列為“正序”時(shí)，復(fù)

雜度可至肱O（n）

對冒泡排序的一種木質(zhì)的改善。通

過使副F序序列的長

度能大幅度的減少。在一趟掃視

后，使某個(gè)結(jié)點(diǎn)移到中間的對的位

置,并便在它左邊序列的結(jié)點(diǎn)的鍵

值都比它的小,而它右邊序列的結(jié)

點(diǎn)的鍵值都不比它的小。稱這樣一

迅速排序O(nlogn)0(*O(logn)不穩(wěn)定

冽個(gè)財(cái)“劃分”。每彼吩（吏一

利張序列變成兩個(gè)新的較小子序

列,對這兩個(gè)小的子序列分別作同

樣的劃分,直至新的子序列的長度

為1使才不再劃分。當(dāng)所有子序列

長度都為1時(shí)，序列已是排好序的

了。

一種樹形選擇排序，是對直接

堆排序（有兩選擇排序的有效改善。一種堆

種狀況：堆頂是這樣一棵次序存儲(chǔ)的二叉

元素是最大樹，它的所有父結(jié)點(diǎn)（e[ij）O(nlogn)O(nlogn)0(1)不穩(wěn)定

值和堆頂元的鍵值均不不不小于它的左

素是最小值）子結(jié)點(diǎn)（e[2*i+l]）和右子結(jié)

點(diǎn)（e[2*i+2]）的鍵值。初始

時(shí)，若把待排序序列的n個(gè)結(jié)

點(diǎn)看作是一棵次序存儲(chǔ)的二

叉樹;調(diào)整它們的存儲(chǔ)次序，

使之成為一種堆，這時(shí)堆的根

結(jié)點(diǎn)鍵值是最大者。然后將根

結(jié)點(diǎn)與堆的最終一種結(jié)點(diǎn)互換，

并對少了一種結(jié)點(diǎn)后的n-1結(jié)點(diǎn)

重新作調(diào)整，使之再次成為堆。

這樣，在根結(jié)點(diǎn)得到結(jié)點(diǎn)序列鍵

值次最大值。依次類推，直到只

有兩個(gè)結(jié)點(diǎn)的堆，并對它們作互

換,最終得到有序的n個(gè)結(jié)點(diǎn)序

歹1」。

將兩個(gè)或兩個(gè)以上的有序子表

合并成一種新的有序表。對于兩

個(gè)有序子表合并一種有序表的

兩路合并排序來說，初始時(shí)，把

含n個(gè)結(jié)點(diǎn)的待排序序列看作有

歸并排序O(nlogn)O(nlogn)O(n)稔定

n個(gè)長度都為1的有序子表所構(gòu)

成，將它們依次兩兩合并得到長

度為2的若干有序子表，再對它

們作兩兩合并……直到得到長

度為n的有序表，排序即告完畢。

背面根據(jù)多手?排序算法，給出了C語言的實(shí)現(xiàn)，大家在復(fù)習(xí)的時(shí)候可以做下參照。

?選擇排序

voidss_sort(inte[l,intn)

{inti,j,k,t;

for(i=0;i<n-1;i++)(

for(k=i,j=i+1;j<n;j++)

if(e[k]>e[j])k=j;

if(k!=i){

t=e[il；e[i]=e[k];e[k]=t;

}

)

?直接插入排序

voidsi_sort(inte[J.intn)

{inli,j,t;

for(i=0;i<n;i++){

for(t=e[i],j=i-l;j>=O&&t<e[j];j-)

e[j+l]=e[j];

c[j+1]=t；

)

)

?冒泡排序

voidsb_sort(inte[],intn)

{intj,p,h