軟件技術(shù)基礎(chǔ)11章為第2數(shù)據(jù)結(jié)構(gòu)概述

2.1基本概念和術(shù)語(yǔ)2.2算法的描述和分析習(xí)題2本節(jié)將對(duì)數(shù)據(jù)結(jié)構(gòu)的一些基本概念和術(shù)語(yǔ)加以定義和解釋。

數(shù)據(jù)(data)是描述客觀事物的數(shù)字、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。例如，一個(gè)代數(shù)方程的求解程序中所用的數(shù)據(jù)是整數(shù)和實(shí)數(shù)；一個(gè)編譯程序或文本編輯程序中所使用的數(shù)據(jù)是字符串。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，數(shù)據(jù)的含義更為廣泛，如圖像、聲音等都可以通過編碼而屬于數(shù)據(jù)的范疇。

數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。有時(shí)，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)(DataItem)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的、不可再分割的最小標(biāo)識(shí)單位。2.1基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)(DataStructure)是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般來(lái)說，數(shù)據(jù)結(jié)構(gòu)所研究的主要內(nèi)容包括以下三個(gè)方面：

①數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)元素之間的邏輯關(guān)系；

②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)——數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方法；

③數(shù)據(jù)的運(yùn)算——對(duì)數(shù)據(jù)施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做是從具體問題抽象出來(lái)的數(shù)學(xué)模型。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)(亦稱為映像)，它是依賴于計(jì)算機(jī)語(yǔ)言的，對(duì)機(jī)器語(yǔ)言而言，存儲(chǔ)結(jié)構(gòu)是具體的，但我們只在高級(jí)語(yǔ)言的層次上來(lái)討論存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，每種邏輯結(jié)構(gòu)都有一組基本運(yùn)算，例如，對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、排序等運(yùn)算。這些基本運(yùn)算實(shí)際上是在抽象的數(shù)據(jù)上所進(jìn)行的一系列抽象的操作，我們只需要知道這些操作“做什么”，而不需要考慮“如何做”。只有確定了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)之后，我們才能夠具體實(shí)現(xiàn)這些基本運(yùn)算。在設(shè)計(jì)一般的算法時(shí)，通常我們可以調(diào)用有關(guān)的基本運(yùn)算來(lái)實(shí)現(xiàn)。在本書的數(shù)據(jù)結(jié)構(gòu)部分所討論的算法，均以類C語(yǔ)言來(lái)描述。數(shù)據(jù)類型(DataType)是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，它最早出現(xiàn)在高級(jí)語(yǔ)言中，用以描述程序操作對(duì)象的特性。在用高級(jí)語(yǔ)言編寫的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的確定的數(shù)據(jù)類型。定義某種數(shù)據(jù)類型，就確定了一個(gè)值域以及對(duì)該類型數(shù)據(jù)可以進(jìn)行的操作。例如，C語(yǔ)言中的“整數(shù)類型”，其值域?yàn)槟硞€(gè)區(qū)間上的整數(shù)(區(qū)間大小依賴于不同的機(jī)器)，對(duì)整型數(shù)據(jù)可以進(jìn)行加、減、乘、除和取模等操作。

按“值”是否可分解，可將數(shù)據(jù)類型劃分為兩類：原子類型，其值不可分解，如C語(yǔ)言中的基本類型(整型、實(shí)型、字符型等)、指針類型；結(jié)構(gòu)類型，其值可分解為若干個(gè)成分，如數(shù)組、結(jié)構(gòu)體等類型的數(shù)據(jù)還可以進(jìn)一步分解。為了加深對(duì)數(shù)據(jù)結(jié)構(gòu)的感性認(rèn)識(shí)，下面舉例說明有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念。

【例2.1】學(xué)生成績(jī)表。我們把學(xué)生成績(jī)表稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)，表中的每一行是一個(gè)數(shù)據(jù)元素，又稱為一個(gè)結(jié)點(diǎn)或記錄，它由學(xué)號(hào)、姓名、性別、各科成績(jī)及平均成績(jī)等數(shù)據(jù)項(xiàng)組成。該表中數(shù)據(jù)元素之間的邏輯關(guān)系是：對(duì)于表中任意一個(gè)結(jié)點(diǎn)，與它相鄰且在它前面的結(jié)點(diǎn)(稱為直接前趨結(jié)點(diǎn))最多只有一個(gè)；與表中任意一個(gè)結(jié)點(diǎn)相鄰且在其后的結(jié)點(diǎn)(稱為直接后繼結(jié)點(diǎn))最多只有一個(gè)。表中只有第一個(gè)結(jié)點(diǎn)沒有直接前趨結(jié)點(diǎn)，故稱為開始結(jié)點(diǎn)；只有最后一個(gè)結(jié)點(diǎn)沒有直接后繼結(jié)點(diǎn)，故稱為終端結(jié)點(diǎn)。例如，表中學(xué)生“馬二”所在結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)分別是學(xué)生“丁一”和“張三”所在的結(jié)點(diǎn)。結(jié)點(diǎn)之間的關(guān)系構(gòu)成了這張學(xué)生成績(jī)表的邏輯結(jié)構(gòu)。該表的存儲(chǔ)結(jié)構(gòu)則是用計(jì)算機(jī)語(yǔ)言表示結(jié)點(diǎn)之間的這種關(guān)系，可以順序鄰接地存儲(chǔ)在一段連續(xù)的存儲(chǔ)單元中，或者用指針將這些結(jié)點(diǎn)鏈接在一起。

在不會(huì)產(chǎn)生混淆的前提下，通常我們將數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

線性結(jié)構(gòu)的邏輯特征：若數(shù)據(jù)結(jié)構(gòu)是非空集，則第一個(gè)結(jié)點(diǎn)沒有直接前趨結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)沒有直接后繼結(jié)點(diǎn)，其余結(jié)點(diǎn)都有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。線性表、棧、隊(duì)列、串等都是線性結(jié)構(gòu)。

非線性結(jié)構(gòu)的邏輯特征：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。樹、圖等屬于非線性結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可以用以下四種基本的存儲(chǔ)方法得到：

(1)順序存儲(chǔ)方法。借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)(SequentialStorageStructure)。通常，順序存儲(chǔ)結(jié)構(gòu)是借助于程序語(yǔ)言的數(shù)組(又稱為向量)來(lái)描述的。

該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化的方法來(lái)實(shí)現(xiàn)順序存儲(chǔ)。

(2)鏈接存儲(chǔ)方法。借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯上相鄰的結(jié)點(diǎn)在物理位置上不一定相鄰，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(LinkedStorageStructure)，通常要借助于程序語(yǔ)言的指針類型來(lái)描述它。

(3)索引存儲(chǔ)方法。在存儲(chǔ)結(jié)點(diǎn)的同時(shí)，還應(yīng)建立附加的索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)，其一般形式為：(關(guān)鍵字，地址)。關(guān)鍵字是能夠唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱為稠密索引(DenseIndex)；若一組結(jié)點(diǎn)在索引表中對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引(SparseIndex)。稠密索引中的索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲(chǔ)位置，而稀疏索引中的索引項(xiàng)的地址則指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。

(4)散列存儲(chǔ)方法。該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。

上述四種基本存儲(chǔ)方法既可以單獨(dú)使用，也可以組合起來(lái)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)。同一種邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。至于選擇何種存儲(chǔ)結(jié)構(gòu)來(lái)表示相應(yīng)的邏輯結(jié)構(gòu)，應(yīng)當(dāng)考慮算法運(yùn)算的方便及時(shí)間和空間要求。2.2.1算法的概念

算法是對(duì)特定問題求解步驟的描述，是指令的有限序列。算法必須滿足以下性質(zhì)：

(1)輸入性：0至多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。

(2)輸出性：1至多個(gè)輸出，這些輸出是同輸入有著某種特定關(guān)系的量。

(3)有窮性：對(duì)于合法的輸入值，算法在執(zhí)行有窮步之后結(jié)束。

(4)確定性：?對(duì)于相同的輸入執(zhí)行相同的路徑，即對(duì)于相同的輸入只能得出相同的輸出。

2.2算法的描述和分析

(5)可行性：用于描述算法的操作都是足夠基本的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。

需要說明的是，算法與程序是有區(qū)別的。例如操作系統(tǒng)，只要系統(tǒng)不遭破壞，它就永遠(yuǎn)不會(huì)停止，即使沒有作業(yè)要處理，仍處于一個(gè)等待循環(huán)中，等待新作業(yè)的進(jìn)入。因此，操作系統(tǒng)程序不是一個(gè)算法。求解同一計(jì)算問題時(shí)可能有許多不同的算法，在算法正確的前提下，以下三個(gè)方面可以作為算法性能的評(píng)價(jià)標(biāo)準(zhǔn)：

①算法的時(shí)間特性，執(zhí)行算法所需的計(jì)算時(shí)間；

②算法的空間特性，執(zhí)行算法所需的輔助存儲(chǔ)空間；

③算法應(yīng)當(dāng)易于理解，易于編碼，易于調(diào)試等。當(dāng)然，我們希望選用一個(gè)所占存儲(chǔ)空間小、運(yùn)行時(shí)間短、其它性能也好的算法。然而，上述要求常常相互抵觸，要節(jié)約算法的執(zhí)行時(shí)間往往要以犧牲更多的空間為代價(jià)，而為了節(jié)省空間可能要耗費(fèi)更多的計(jì)算時(shí)間。算法的時(shí)間特性和空間特性都與問題的規(guī)模有關(guān)，因此我們只能根據(jù)具體情況而有所側(cè)重。本書主要討論算法的時(shí)間特性，偶爾也討論空間特性。2.2.2算法的時(shí)間特性

一個(gè)算法所需的計(jì)算時(shí)間，應(yīng)當(dāng)是該算法中每條語(yǔ)句的執(zhí)行時(shí)間之和，而每條語(yǔ)句的執(zhí)行時(shí)間是該語(yǔ)句的執(zhí)行次數(shù)(稱為頻度)與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。但是，當(dāng)算法轉(zhuǎn)換為程序之后，每條語(yǔ)句執(zhí)行一次所需的時(shí)間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量，這是很難確定的。我們假設(shè)每條語(yǔ)句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，一個(gè)算法的計(jì)算時(shí)間就是該算法中所有語(yǔ)句的頻度之和。于是，我們就可以獨(dú)立于機(jī)器的軟、硬件系統(tǒng)來(lái)分析算法的時(shí)間特性。

【例2.2】求兩個(gè)n階方陣的乘積C＝A×B，其算法如下：

#definen自然數(shù)

voidMATRIXMLT(intA[n][n],intB[n][n],intC[n][n])

{inti,j,k;

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

(2)for(j=0；j<n;j++){ n(n+1)

(3)C[i][j]=0; n2

(4)for(k=0;k<n;k++) n2(n+1)

(5)C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3

}

}其中，右邊列出的是各語(yǔ)句的頻度。語(yǔ)句(1)的循環(huán)控制變量i取值從0到n，語(yǔ)句執(zhí)行了n+1次，故它的頻度是n+1，但它的循環(huán)體只執(zhí)行了n次。語(yǔ)句(2)作為語(yǔ)句(1)的循環(huán)體內(nèi)的語(yǔ)句應(yīng)該執(zhí)行n次，但語(yǔ)句(2)本身要執(zhí)行n+1次，所以語(yǔ)句(2)的頻度是n(n+1)。同理可得，語(yǔ)句(3)、(4)和(5)的頻度分別是n2、n2(n+1)和n3。該算法中所有語(yǔ)句的頻度之和為：

T(n)=2n3+3n2+2n+1

算法的語(yǔ)句頻度之和T(n)是矩陣階數(shù)n的函數(shù)，n是算法求解方陣乘積問題的規(guī)模。

一般情況下，算法中基本操作重復(fù)執(zhí)行的時(shí)間是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的漸進(jìn)時(shí)間復(fù)雜度(簡(jiǎn)稱為時(shí)間復(fù)雜度(TimeComplexity))，記做

T(n)?=?O(f(n))(2-1)

它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，f(n)一般是算法中頻度最大的語(yǔ)句頻度。例如，算法MATRIXMLT的時(shí)間復(fù)雜度是T(n)=O(n3)，這里的f(n)=n3是該算法中語(yǔ)句(5)的頻度。由此可見，當(dāng)有循環(huán)嵌套時(shí)，算法的時(shí)間復(fù)雜度是由最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。

下面再舉幾例，說明如何求算法的時(shí)間復(fù)雜度。

【例2.3】

交換a和b的值。

temp=a;

a=b;

b=temp;

以上三條單個(gè)語(yǔ)句的頻度為1，該算法的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無(wú)關(guān)的常數(shù)，時(shí)間復(fù)雜度記做T(n)=O(1)。事實(shí)上，只要算法的執(zhí)行時(shí)間不隨著問題規(guī)模的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其時(shí)間復(fù)雜度也只是O(1)。

【例2.4】

判斷n是否為素?cái)?shù)。

voidprime(intn)

{inti=2;

while((n%i)!=0&&i<sqrt(n))

i++;

if(i>=sqrt(n))printf("%d是素?cái)?shù)",n);

elseprintf("%d不是素?cái)?shù)",n);

}

設(shè)語(yǔ)句i++；的頻度為f(n)，由i<sqrt(n)可知f(n)<sqrt(n)，時(shí)間復(fù)雜度應(yīng)考慮最壞的情況，所以

【例2.5】

變量計(jì)數(shù)。

i=1；1

while(i<=n)i=i*2;f(n)

由于2f(n)≤n，即f(n)≤lbn，取最大值f(n)=lbn，T(n)=O(f(n))=O(lbn)。

將常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列，則依次為：常量階O(1)、對(duì)數(shù)階O(lbn)、線性階O(n)、線性對(duì)數(shù)階O(nlbn)、平方階O(n2)、立方階O(n3)、…、k次方階O(nk)、指數(shù)階O(2n)。顯然，時(shí)間復(fù)雜度為指數(shù)階的算法效率極低，當(dāng)n值稍大時(shí)就無(wú)法應(yīng)用。

2.2.3算法的空間特性

類似于算法的時(shí)間復(fù)雜度，算法的空間復(fù)雜度(SpaceComplexity)可以作為算法所需輔助存儲(chǔ)空間的度量，記做

S(n)?=?O(f(n))(2-2)

它也是問題規(guī)模n的函數(shù)。若額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說是常量，則稱此算法為原地工作。如果所占空間量依賴于特定的輸入，則除了特別指明外，均應(yīng)按最壞情況來(lái)分析。

一、名詞解釋

數(shù)據(jù)，數(shù)據(jù)元素，邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，線性結(jié)構(gòu)，非線性結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，索引存儲(chǔ)結(jié)構(gòu)，散列存儲(chǔ)結(jié)構(gòu)，算法，時(shí)間復(fù)雜度

二、填空題

1．從某種意義上說，數(shù)據(jù)、數(shù)據(jù)元