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

點(diǎn)擊此處結(jié)束第1章數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)算法及算法分析點(diǎn)擊此處結(jié)束“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)的一門重要基礎(chǔ)課程，它研究的問題是從實(shí)際需要中抽象出來的，是計(jì)算機(jī)科學(xué)各領(lǐng)域以及系統(tǒng)軟件都會(huì)用到的知識(shí)。本章是全書的基礎(chǔ)，主要介紹以下幾個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)處理算法的描述與分析。點(diǎn)擊此處結(jié)束1.1

數(shù)據(jù)的邏輯結(jié)構(gòu)點(diǎn)擊此處結(jié)束人們要讓計(jì)算機(jī)做事情，都必須涉及三個(gè)問題：一，確定所要加工處理的數(shù)據(jù)間的關(guān)系，以便進(jìn)行處理時(shí)，能夠知道一個(gè)數(shù)據(jù)的后面是哪一個(gè)數(shù)據(jù)，這是數(shù)據(jù)的邏輯結(jié)構(gòu)問題；二，確定要對數(shù)據(jù)做哪些處理，這是算法描述問題；三，確定以何種方式把數(shù)據(jù)存放到計(jì)算機(jī)的內(nèi)存，并反映出它們間的鄰接關(guān)系，這是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)問題。1.1.1

數(shù)據(jù)及數(shù)據(jù)間的鄰接關(guān)系點(diǎn)擊此處結(jié)束“數(shù)據(jù)”是信息的載體，是人們用符號(hào)來表示客觀事物的一種集合?，F(xiàn)在把“數(shù)據(jù)”定義為：所有能夠輸入到計(jì)算機(jī)中被計(jì)算機(jī)加工、處理的符號(hào)的集合。通常，數(shù)據(jù)由“數(shù)據(jù)元素”（簡稱“元素”）合而成的。數(shù)據(jù)元素也常被稱作“結(jié)點(diǎn)”、

“頂點(diǎn)”、“記錄”。每個(gè)數(shù)據(jù)元素都具有完確定的實(shí)際意義，是數(shù)據(jù)加工處理的對象。一個(gè)數(shù)據(jù)元素又可以細(xì)分成由若干個(gè)“數(shù)據(jù)項(xiàng)”組成。數(shù)據(jù)項(xiàng)也常稱作“字段”、

“域”，它是數(shù)據(jù)元素中不可再分割的最小標(biāo)識(shí)單位，通常不具備完整、確定的實(shí)際意義，只是反映數(shù)據(jù)元素某一方面的屬性。數(shù)據(jù)結(jié)構(gòu)關(guān)心的是從一個(gè)數(shù)據(jù)能夠找到另一個(gè)數(shù)據(jù)的那種“關(guān)系”，人們根據(jù)那種關(guān)系來組織和存儲(chǔ)數(shù)據(jù)，以便順利、有效地實(shí)現(xiàn)對數(shù)據(jù)的各種處理要求。點(diǎn)擊此處結(jié)束如果兩個(gè)數(shù)據(jù)結(jié)點(diǎn)間有著某種邏輯上的聯(lián)系，就稱這兩個(gè)結(jié)點(diǎn)是“鄰接的”。若用圓圈代表結(jié)點(diǎn)，用結(jié)點(diǎn)間的一條連線代表它們之間存在的邏輯關(guān)系，那么，就用圖1-1來表示結(jié)點(diǎn)A和B是“鄰接的”。圖1-1

結(jié)點(diǎn)的鄰接點(diǎn)擊此處結(jié)束常見的數(shù)據(jù)間的鄰接關(guān)系有三種：線性關(guān)系、樹型關(guān)系以及圖狀關(guān)系。數(shù)據(jù)間的鄰接關(guān)系，就是數(shù)據(jù)的“邏輯結(jié)構(gòu)”。點(diǎn)擊此處結(jié)束1.1.2

數(shù)據(jù)的邏輯結(jié)構(gòu)■1．線性關(guān)系所謂數(shù)據(jù)間具有“線性”關(guān)系，是指數(shù)據(jù)一個(gè)接一個(gè)地排列成一行。如果所要處理的數(shù)據(jù)間呈線性關(guān)系，那么就說它的邏輯結(jié)構(gòu)是線性的。在線性關(guān)系中，排在第1個(gè)位置的結(jié)點(diǎn)稱為起始結(jié)點(diǎn)，排在最后一個(gè)位置的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)，其余的結(jié)點(diǎn)稱為中間結(jié)點(diǎn)，如圖1-2所示。點(diǎn)擊此處結(jié)束圖1-2

線性關(guān)系中的各種結(jié)點(diǎn)點(diǎn)擊此處結(jié)束線性關(guān)系的特點(diǎn)是：除起始結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的前面和后面，都有且只有一個(gè)結(jié)點(diǎn)與它鄰接，起始結(jié)點(diǎn)的前面沒有鄰接的結(jié)點(diǎn)，終端結(jié)點(diǎn)的后面沒有鄰接的結(jié)點(diǎn)。簡單地說，線性關(guān)系的特點(diǎn)是：有頭有尾，順序排列。點(diǎn)擊此處結(jié)束■2．樹型關(guān)系所謂數(shù)據(jù)間具有“樹型”關(guān)系，是指在數(shù)據(jù)之間具有分支、層次的邏輯關(guān)系。如果所要處理的數(shù)據(jù)之間呈樹型關(guān)系，那么就說它的邏輯結(jié)構(gòu)是樹型的。文件目錄間的邏輯結(jié)構(gòu)就是樹型的。圖1-3所示為一個(gè)樹型目錄圖例。點(diǎn)擊此處結(jié)束圖1-3

文件目錄間的樹型關(guān)系點(diǎn)擊此處結(jié)束樹型關(guān)系的特點(diǎn)是：第1層只有一個(gè)結(jié)點(diǎn)，它是樹型關(guān)系的起點(diǎn)；除第1層結(jié)點(diǎn)和分支末端結(jié)點(diǎn)外，位于中間各層的結(jié)點(diǎn)的前面只有一個(gè)結(jié)點(diǎn)與它相鄰接，每個(gè)結(jié)點(diǎn)的后面可以有多個(gè)結(jié)點(diǎn)與它相鄰接；第1層結(jié)點(diǎn)的前面沒有結(jié)點(diǎn)與之鄰接，每個(gè)分支末端結(jié)點(diǎn)的后面沒有結(jié)點(diǎn)與之鄰接。點(diǎn)擊此處結(jié)束■3．圖狀關(guān)系如果數(shù)據(jù)中的任何兩個(gè)元素間都可能有鄰接關(guān)系，那么就說它們之間的關(guān)系是圖狀的。如果所要處理的數(shù)據(jù)之間呈圖狀關(guān)系，那么就說它的邏輯結(jié)構(gòu)是圖狀的。圖狀關(guān)系是數(shù)據(jù)間最復(fù)雜的關(guān)系。圖1-4所示為一張航空網(wǎng)絡(luò)圖。在圖狀關(guān)系中，找不到誰是起點(diǎn)，誰是終點(diǎn)，各個(gè)結(jié)點(diǎn)的地位可以說都是相同的。點(diǎn)擊此處結(jié)束圖1-4

航空網(wǎng)絡(luò)點(diǎn)擊此處結(jié)束圖狀關(guān)系的特點(diǎn)是：每個(gè)結(jié)點(diǎn)都可能與多個(gè)結(jié)點(diǎn)有鄰接關(guān)系。數(shù)據(jù)間的線性關(guān)系和樹型關(guān)系，都可以視為是圖狀關(guān)系的一個(gè)特例。點(diǎn)擊此處結(jié)束1.2

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)點(diǎn)擊此處結(jié)束在計(jì)算機(jī)里存放數(shù)據(jù)時(shí)，既要存儲(chǔ)數(shù)據(jù)本身，也要存儲(chǔ)數(shù)據(jù)間的鄰接關(guān)系。這樣，在對數(shù)據(jù)進(jìn)行加工處理時(shí)，才能夠方便、正確地從一個(gè)數(shù)據(jù)找到與之鄰接的另一個(gè)數(shù)據(jù)。數(shù)據(jù)的“存儲(chǔ)結(jié)構(gòu)”，就是研究數(shù)據(jù)在內(nèi)存中的存儲(chǔ)方式，也就是在內(nèi)存中有哪些存放數(shù)據(jù)的方法。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)也稱為數(shù)據(jù)的“物理結(jié)構(gòu)”。在把數(shù)據(jù)存儲(chǔ)到存儲(chǔ)器時(shí)，是以數(shù)據(jù)元素（即數(shù)據(jù)結(jié)點(diǎn)）為單位進(jìn)行的。分配給一個(gè)數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)區(qū)域，稱為一個(gè)“存儲(chǔ)結(jié)點(diǎn)”。在一個(gè)存儲(chǔ)結(jié)點(diǎn)里，除了要有數(shù)據(jù)本身的內(nèi)容外，還要有體現(xiàn)數(shù)據(jù)間鄰接關(guān)系的內(nèi)容。點(diǎn)擊此處結(jié)束所謂數(shù)據(jù)的“順序式存儲(chǔ)”結(jié)構(gòu)，即是為一組數(shù)據(jù)分配一個(gè)連續(xù)的存儲(chǔ)區(qū)，然后按照數(shù)據(jù)間的鄰接關(guān)系，相繼存放每個(gè)數(shù)據(jù)。這種存儲(chǔ)結(jié)構(gòu)，是借助存儲(chǔ)結(jié)點(diǎn)間的位置關(guān)系，來體現(xiàn)數(shù)據(jù)元素間的鄰接關(guān)系的。點(diǎn)擊此處結(jié)束1.2.1

順序式存儲(chǔ)結(jié)構(gòu)比如，圖1-5左側(cè)為一個(gè)數(shù)據(jù)元素所需要的存儲(chǔ)尺寸：size字節(jié)，圖1-5右側(cè)所示為在內(nèi)存里開辟了一個(gè)連續(xù)的存儲(chǔ)區(qū)，用來依次存放數(shù)據(jù)的若干個(gè)存儲(chǔ)結(jié)點(diǎn)。點(diǎn)擊此處結(jié)束圖1-5

順序存儲(chǔ)結(jié)構(gòu)點(diǎn)擊此處結(jié)束所謂數(shù)據(jù)的“鏈?zhǔn)酱鎯?chǔ)”結(jié)構(gòu)，即是存儲(chǔ)每個(gè)數(shù)據(jù)的存儲(chǔ)結(jié)點(diǎn)都由兩個(gè)部分組成，一部分用來存放數(shù)據(jù)元素本身的信息，另一部分用來存放與本數(shù)據(jù)元素鄰接的數(shù)據(jù)元素存儲(chǔ)結(jié)點(diǎn)的位置，即存儲(chǔ)指向與之鄰接的存儲(chǔ)結(jié)點(diǎn)的指針（起始地址），通過這些指針反映出數(shù)據(jù)間的邏輯關(guān)系。圖1-6給出的是一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。點(diǎn)擊此處結(jié)束1.2.2

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖1-6

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)點(diǎn)擊此處結(jié)束在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)結(jié)點(diǎn)里的指針并不局限于只能是一個(gè)，而應(yīng)根據(jù)問題的需要安排為一個(gè)或多個(gè)。如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，存儲(chǔ)結(jié)點(diǎn)里只有一個(gè)指針，則稱是單鏈?zhǔn)浇Y(jié)構(gòu)；如果存儲(chǔ)結(jié)點(diǎn)里有兩個(gè)指針，則稱是雙鏈?zhǔn)浇Y(jié)構(gòu)；如此等等。點(diǎn)擊此處結(jié)束1.3

算法及算法分析點(diǎn)擊此處結(jié)束實(shí)現(xiàn)數(shù)據(jù)的加工處理時(shí)，如果問題較大、較復(fù)雜，就應(yīng)該先通過分析列出與加工處理相關(guān)的各個(gè)步驟，然后再去用某種計(jì)算機(jī)程序設(shè)計(jì)語言編寫出程序在計(jì)算機(jī)上運(yùn)行。第一步就是所謂的算法描述，第二步就是所謂的程序?qū)崿F(xiàn)。1.3.1

算法及算法的描述點(diǎn)擊此處結(jié)束■1．算法和程序的區(qū)別算法和計(jì)算機(jī)程序是兩個(gè)不同的概念。所謂“算法”，是指解決問題的一種方法步驟或者一個(gè)過程。對于一個(gè)問題，可以用多種算法來解決；而一個(gè)給定的算法，則只解決一個(gè)特定的問題。一個(gè)算法應(yīng)該具有以下幾個(gè)重要的特征。輸入：一個(gè)算法應(yīng)該有n（n≥0）個(gè)初始的輸入數(shù)據(jù)。輸出：一個(gè)算法可以沒有或有一個(gè)或多個(gè)輸出信息，它們與輸入數(shù)據(jù)之間會(huì)有著某種特定的關(guān)系。點(diǎn)擊此處結(jié)束確定性：算法中的每一個(gè)步驟都必須具有確切的含義，不能有二義性?？尚行裕核惴ㄖ忻枋龅拿恳粋€(gè)操作步驟都必須是可以執(zhí)行的，也就是說，都可以通過計(jì)算機(jī)實(shí)現(xiàn)。有窮性：一個(gè)算法必須在經(jīng)歷有限個(gè)步驟之后正常結(jié)束，不能形成死循環(huán)。點(diǎn)擊此處結(jié)束例1-1點(diǎn)擊此處結(jié)束判斷下面用文字描述的計(jì)數(shù)過程是否構(gòu)成一個(gè)算法。（1）開始；（2）n=0；/*變量n賦初值0

*/（3）n=n+1；/*變量n增1*/（4）重復(fù)執(zhí)行（3）；/*循環(huán)執(zhí)行增1操作

*/（5）結(jié)束。例1-2

編寫一個(gè)算法，按照從小到大的順序排列兩個(gè)數(shù)值變量x、y的內(nèi)容，即要求最終有x≤y。解：用文字描述解決這個(gè)問題的算法如下：輸入變量x、y的數(shù)值；把兩個(gè)數(shù)值中的小者存放到x里；把兩個(gè)數(shù)值中的大者存放到y(tǒng)里；輸出x、y的值。可以看出，上面的描述符合算法的5個(gè)特征。點(diǎn)擊此處結(jié)束所謂“程序（Program）”，是指使用某種計(jì)算機(jī)程序設(shè)計(jì)語言對一個(gè)算法的具體實(shí)現(xiàn)。比如，例1-2的算法，可以用如下的C語言程序來實(shí)現(xiàn)。算法側(cè)重于對解決問題的方法描述，即要做些什么；而程序是算法在計(jì)算機(jī)程序設(shè)計(jì)語言中的實(shí)現(xiàn)，即具體要怎樣去做。點(diǎn)擊此處結(jié)束/*

從鍵盤

輸入兩點(diǎn)擊此處結(jié)束#include

"stdio"main(){int

x,

y,

temp;scanf

("%d%d",

&x,

&y);個(gè)整型數(shù)據(jù)

*/if

(x>y)

/*

對數(shù)據(jù)進(jìn)行比較

*//*{temp

=

x

;

x

=

y

;

y

=

temp

;

}printf

("x

=

%d,

y

=

%d\n",

x,

y);打印輸出

*/}■2．算法的描述算法是可以用不同方法來描述的，下面給出幾種常見的方法。算法描述方法1：使用人們習(xí)慣的自然語言來描述算法。算法描述方法2：使用人們熟悉的流程圖（即框圖）來描述算法。點(diǎn)擊此處結(jié)束例1-4

用流程圖描述輸出整數(shù)1、2、3、…、9、10的過程。解：用流程圖描述輸出整數(shù)1、2、3、…、

9、10的過程的算法如圖1-8所示。點(diǎn)擊此處結(jié)束圖1-7

流程圖的各種圖形名稱和作用點(diǎn)擊此處結(jié)束圖1-8

用流程圖描述算法點(diǎn)擊此處結(jié)束算法描述方法3：用“類C語言”來描述算本書將采用類C語言來描述算法。算法描述方法4：直接采用C語言來描述算法。點(diǎn)擊此處結(jié)束例1-5

分別用C語言和類C語言來描述輸出整數(shù)1、2、3、…、9、10的過程。解：（1）用C語言描述輸出整數(shù)1、2、3、…、9、10的過程的算法如下。void

num

(){int

i;i=1;while

(i<=

10){printf

("i

=

%d\n",

i

);i

=

i

+1;}}點(diǎn)擊此處結(jié)束（2）用類C語言描述輸出整數(shù)1、2、3、…、9、10的過程的算法如下。void

num

(){i=1;while

(i<=

10){printf

("i

=

%d\n",

i

);i

=

i

+1;}}點(diǎn)擊此處結(jié)束對同一個(gè)問題可以設(shè)計(jì)出不同的算法，它們之間當(dāng)然有好差之分。判定算法質(zhì)量時(shí)應(yīng)遵循下面的幾條原則：點(diǎn)擊此處結(jié)束1.3.2算法分析算法是否易讀，易于人們理解；算法的結(jié)構(gòu)是否簡明、清晰；算法的執(zhí)行效率是否高；算法的存儲(chǔ)利用率是否高；算法的可移植性是否好。點(diǎn)擊此處結(jié)束在算法分析中，人們最看重的是執(zhí)行效率（時(shí)間）和存儲(chǔ)利用率（空間）這兩個(gè)問題。在數(shù)據(jù)結(jié)構(gòu)里，對一個(gè)算法執(zhí)行效率的度量，稱為“時(shí)間復(fù)雜度”；對一個(gè)算法在執(zhí)行過程中所需占用存儲(chǔ)空間的度量，稱為“空間復(fù)雜度”。點(diǎn)擊此處結(jié)束例1-6

變量a、b、c、d中各存一個(gè)整數(shù)，求a、b、c中的最大者與d的乘積的算法。void

max1

(a,{b,

c,d)a

=

a*d;

b=

b*d;c=

c*d;if

(a>b)

x=

a;else

x

=b;if

(c>x)

x=

c;printf("%d\n",x);}圖1-9

max1的流程點(diǎn)擊此處結(jié)束算法2為：void

max2

(a,

b,

c,

d){if

(a>b)

x

=

a;else

x

=

b;if

(c>x)

x

=

c;x

=

x*d;printf

("%d\n",

x);}圖1-10

max2的流程點(diǎn)擊此處結(jié)束“基本操作”是指算法中那些所需時(shí)間與操作數(shù)的具體取值無關(guān)的操作。賦值、兩個(gè)數(shù)相加或兩個(gè)數(shù)比較大小等，都可以作為基本操作，這些操作的執(zhí)行時(shí)間與具體操作數(shù)是無關(guān)的。點(diǎn)擊此處結(jié)束例1-7

分析下面所給算法段中基本操作的執(zhí)行次數(shù)。for

(i

=

1;

i

<

n;

i++){y

=

y

+1;for

(j

=

0;

j<=

(2