教學(xué)課件-軟件技術(shù)基礎(chǔ)(鮑有文)

1.1數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容

1.2基本概念和術(shù)語

1.3算法

1.4本章小結(jié)

自測(cè)習(xí)題1.1數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容

【例1-1】某學(xué)校課程表管理。表1-1中的課程表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。課程表管理的主要功能包括：查找、瀏覽、插入、修改和刪除。如果把表1-1中的一行看成一個(gè)記錄，則在此表中，結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系是一種最簡(jiǎn)單的線性關(guān)系。

【例1-2】家譜問題。圖1-1所示為我國(guó)唐王朝初期的家譜，它像一棵倒立的樹，清楚地描述了唐王朝家庭人員的繼承關(guān)系。圖1-1唐王朝初期的家譜

【例1-3】最短路徑問題。如圖1-2所示，有8個(gè)城市，以0~7為其編號(hào)，帶箭頭的線表示城市之間的連接關(guān)系，線上的數(shù)字表示兩個(gè)城市之間的距離。問題是如何確定一個(gè)城市與其他城市的最短距離。由上面三個(gè)例子可見，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中相關(guān)問題的學(xué)科，具體包括數(shù)據(jù)之間的邏輯關(guān)系和對(duì)數(shù)據(jù)的操作，同時(shí)還研究如何將具有邏輯關(guān)系的數(shù)據(jù)按一定的存儲(chǔ)方式存放到計(jì)算機(jī)中。圖1-2城市之間的距離和連接關(guān)系1.2基本概念和術(shù)語1.2.1數(shù)據(jù)、數(shù)據(jù)元素及數(shù)據(jù)項(xiàng)數(shù)據(jù)(Data)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能夠被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)是計(jì)算機(jī)程序加工的“原料”。例如，一個(gè)利用數(shù)值分析方法解代數(shù)方程的程序，其處理對(duì)象是整數(shù)和實(shí)數(shù)；編譯程序或文字處理程序的處理對(duì)象是字符串。因此，對(duì)計(jì)算機(jī)科學(xué)而言，數(shù)據(jù)的含義極為廣泛，如圖像、聲音等都可以通過編碼而歸于數(shù)據(jù)的范疇。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)或記錄。數(shù)據(jù)項(xiàng)(DataItem)是數(shù)據(jù)的不可分割的、含有獨(dú)立意義的最小單位。數(shù)據(jù)項(xiàng)也被稱為字段或域。以學(xué)生成績(jī)表為例，如表1-2所示，整張表是數(shù)據(jù)，每一行記錄稱為數(shù)據(jù)元素，每一個(gè)字段稱為數(shù)據(jù)項(xiàng)。

1.2.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。這是對(duì)數(shù)據(jù)結(jié)構(gòu)的一種簡(jiǎn)單解釋。從1.1節(jié)中的三個(gè)例子可以看到，在任何問題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)。

(1)集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無其他關(guān)系。

(2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。

(3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。

(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。圖1-3為上述四類基本結(jié)構(gòu)的關(guān)系圖。由于“集合”是數(shù)據(jù)元素之間關(guān)系極為松散的一種結(jié)構(gòu)，因此在本書中不對(duì)其進(jìn)行討論。圖1-3四類基本結(jié)構(gòu)上述數(shù)據(jù)結(jié)構(gòu)的定義只是對(duì)操作對(duì)象的一種數(shù)學(xué)描述，換句話說，是將操作對(duì)象抽象出來的數(shù)學(xué)模型。結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)(DataLogicalStructure)。然而，討論數(shù)據(jù)結(jié)構(gòu)是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的操作，因此還需研究如何在計(jì)算機(jī)中表示它。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映像)稱為數(shù)據(jù)的物理結(jié)構(gòu)(DataPhysicalStructure)，又稱存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和關(guān)系的表示。在計(jì)算機(jī)中，表示信息的最小單位是二進(jìn)制數(shù)的一位，稱為位(Bit)。在計(jì)算機(jī)中，可以用一個(gè)由若干位組合起來形成的一個(gè)位串表示一個(gè)數(shù)據(jù)元素(如用一個(gè)字長(zhǎng)的位串表示一個(gè)整數(shù)，用8位二進(jìn)制數(shù)表示一個(gè)字符等)，通常稱這個(gè)位串為元素(Element)或結(jié)點(diǎn)(Node)。當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí)，位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串稱為數(shù)據(jù)域(DataField)。因此，元素或結(jié)點(diǎn)可看成是數(shù)據(jù)元素在計(jì)算機(jī)中的映像。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序存儲(chǔ)映像和非順序存儲(chǔ)映像，由此可得到兩種主要的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)的特點(diǎn)是：在內(nèi)存中開辟一組連續(xù)的存儲(chǔ)單元，借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。例如，有一個(gè)數(shù)組A，含有n個(gè)元素，這n個(gè)數(shù)據(jù)元素的存儲(chǔ)如圖1-4所示。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是：借助指示元素存儲(chǔ)地址的指針Pointer)表示數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)元素的存儲(chǔ)并不一定是連續(xù)的。例如，有兩個(gè)數(shù)據(jù)元素，一個(gè)為“王家”，另一個(gè)為“李家”，二者的存儲(chǔ)并不連續(xù)。為了能由數(shù)據(jù)元素“李家”找到數(shù)據(jù)元素“王家”，還需要存儲(chǔ)數(shù)據(jù)元素“王家”的地址0023，這樣兩個(gè)數(shù)據(jù)元素之間的鄰接關(guān)系就能表示了，如圖1-5所示。數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個(gè)方面，以后讀者會(huì)看到，任何一個(gè)算法的設(shè)計(jì)都取決于選定的數(shù)據(jù)(邏輯)結(jié)構(gòu)，而算法的實(shí)現(xiàn)則依賴于所采用的存儲(chǔ)結(jié)構(gòu)。圖1-4順序存儲(chǔ)示例圖圖1-5鏈?zhǔn)酱鎯?chǔ)示例圖數(shù)據(jù)類型(DataType)是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念，它最早出現(xiàn)在高級(jí)程序語言中，用以刻畫(程序)操作對(duì)象的特性。在用高級(jí)程序語言編寫的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的確定的數(shù)據(jù)類型。這些類型明顯或隱含地規(guī)定了在程序執(zhí)行期間變量或表達(dá)式所有可能取值的范圍，以及在這些值上允許進(jìn)行的操作。因此數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)取值范圍上的一組操作的總稱。例如，C語言中的整型變量，其取值范圍為某個(gè)區(qū)間上的整數(shù)(區(qū)間大小依賴于不同的機(jī)器)，定義在其上的操作為：加、減、乘、除和取模等算術(shù)運(yùn)算。

按照數(shù)據(jù)元素所取值的不同特性，高級(jí)程序語言中的數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，原子類型的值是不可分解的，如C語言中的基本類型(整型、實(shí)型、字符型和枚舉類型)、指針類型和空類型；另一類是結(jié)構(gòu)類型，結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的，例如數(shù)組的值由若干分量組成，每個(gè)分量可以是整數(shù)，也可以是數(shù)組等。在某種意義上，如果把數(shù)據(jù)結(jié)構(gòu)看成是“一組具有相同結(jié)構(gòu)的值”，則結(jié)構(gòu)類型就可以看成由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成。引入“數(shù)據(jù)類型”概念的目的，從硬件的角度來看，是作為解釋計(jì)算機(jī)內(nèi)存中信息含義的一種手段，而對(duì)使用數(shù)據(jù)類型的用戶來說，則實(shí)現(xiàn)了信息的隱蔽，即將一切用戶不必了解的細(xì)節(jié)都封裝在數(shù)據(jù)類型中。例如，用戶在使用“整數(shù)”類型時(shí)，既不需要了解“整數(shù)”在計(jì)算機(jī)內(nèi)部是如何表示的，也不需要知道其操作是如何實(shí)現(xiàn)的。從上面的分析可以得到數(shù)據(jù)結(jié)構(gòu)的概念。數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式，主要包括以下三方面的內(nèi)容：

(1)數(shù)據(jù)元素之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。

(2)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(StorageStructure)。

(3)數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作。這也是數(shù)據(jù)結(jié)構(gòu)的主要研究?jī)?nèi)容，即非數(shù)值應(yīng)用問題中數(shù)據(jù)之間的邏輯關(guān)系，同時(shí)數(shù)據(jù)結(jié)構(gòu)還研究如何將具有邏輯關(guān)系的數(shù)據(jù)按一定的存儲(chǔ)結(jié)構(gòu)存放在計(jì)算機(jī)內(nèi)，并確定對(duì)數(shù)據(jù)施加的操作及實(shí)現(xiàn)方式。1.3算法1.3.1算法的概念及特性

【例1-4】

main()

{

printf(″請(qǐng)稍等…您將知道世界的末日…″)；

while(1)

{}

}

【例1-5】

getsum(intnum)

{

inti，sum=0；

for(i=1；i<=num；i++)

sum+=i；

}仔細(xì)分析例1-4的程序可以看到，while循環(huán)語句的判斷條件永遠(yuǎn)為“真”，結(jié)果是循環(huán)沒有結(jié)束的時(shí)候，執(zhí)行的時(shí)候?qū)⑾萑胨姥h(huán)。分析例1-5可以知道，函數(shù)雖然進(jìn)行了累加運(yùn)算，但是沒有任何輸出，無輸出的算法沒有任何意義。那么什么是算法呢？一個(gè)算法應(yīng)該滿足哪些特性呢？

算法(Algorithm)是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，每一條指令表示一個(gè)或多個(gè)操作。此外，一個(gè)算法還具有下列五個(gè)重要特性：

(1)有窮性：一個(gè)算法必須總是(對(duì)任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮的時(shí)間內(nèi)完成。

(2)確定性：算法中每一條指令必須有確切的含義，讀者理解時(shí)不會(huì)產(chǎn)生二義性，并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得出相同的輸出。

(3)可行性：一個(gè)算法是可行的，即算法中描述的操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。

(4)輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定對(duì)象的集合。

(5)輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。

1.正確性(Correctness)算法應(yīng)當(dāng)滿足具體問題的需求。通常一個(gè)大型問題的需求要以特定的規(guī)格說明方式給出，而一個(gè)實(shí)習(xí)問題或練習(xí)題往往就不那么嚴(yán)格，目前多數(shù)采用自然語言來描述需求，至少應(yīng)當(dāng)包括對(duì)于輸入、輸出和加工處理等的明確的無歧義性描述。

算法是否正確，通常要將其轉(zhuǎn)化為程序，通過上機(jī)來檢驗(yàn)?！罢_”一詞的含義通常有很大差別，大體可分為以下四個(gè)層次：程序不含語法錯(cuò)誤；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；程序?qū)τ诰倪x擇的典型、苛刻的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。顯然，達(dá)到第四層意義下的正確是極為困難的，所有不同輸入數(shù)據(jù)的數(shù)量大得驚人，逐一驗(yàn)證的方法是不現(xiàn)實(shí)的。對(duì)于大型軟件需要進(jìn)行專業(yè)測(cè)試，而在一般情況下，通常以第三層意義的正確性作為衡量一個(gè)程序是否合格的標(biāo)準(zhǔn)。

2.可讀性(Readability)算法主要是為了人們進(jìn)行閱讀與交流，其次才是機(jī)器執(zhí)行?？勺x性好有助于人們對(duì)算法的理解；晦澀難懂的程序易于隱藏較多錯(cuò)誤，難以調(diào)試和修改。

3.健壯性(Robustness)

當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫明其妙的輸出結(jié)果并中止程序的執(zhí)行，以便在更高的抽象層次上進(jìn)行處理。

4.效率與低存儲(chǔ)量需求

通俗地說，效率指的是算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問題如果有多個(gè)算法可以解決，則執(zhí)行時(shí)間短的算法效率高。存儲(chǔ)量需求是指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。效率與低存儲(chǔ)量需求這兩者都與問題的規(guī)模有關(guān)。例如，求100個(gè)人的平均分與求1000個(gè)人的平均分所花的執(zhí)行時(shí)間或運(yùn)行空間顯然有一定的差別。

1.3.2算法的描述方法算法的描述方法很多，根據(jù)描述語言的不同，可以分為框圖算法描述、非形式算法描述、類C語言算法描述、C語言編寫的程序或函數(shù)。本書采用的是類C語言算法描述方法，類C語言不拘泥于C語言的細(xì)節(jié)，又容易轉(zhuǎn)換成C或者C＋＋程序，這使得數(shù)據(jù)結(jié)構(gòu)和算法的描述及討論變得簡(jiǎn)明清晰。本書采用的類C語言精選了C語言的一個(gè)核心子集，同時(shí)作了若干擴(kuò)充修改，從而增強(qiáng)了語言的描述功能，以下對(duì)其作簡(jiǎn)要說明。表1-3所示為類C語言的常用語法。

1.3.3算法的性能分析前面已經(jīng)提到，好的算法要求高效率和低存儲(chǔ)量。目前，隨著計(jì)算機(jī)硬件的迅速發(fā)展，計(jì)算機(jī)的存儲(chǔ)空間越來越大，所花的費(fèi)用越來越低，討論算法空間復(fù)雜度的必要性不大，因此，本書主要討論算法的時(shí)間特性。時(shí)間特性通過算法執(zhí)行時(shí)間進(jìn)行描述，算法執(zhí)行時(shí)間需依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量。顯然，同一個(gè)算法用不同的語言實(shí)現(xiàn)，或者用不同的編譯程序進(jìn)行編譯，或者在不同的計(jì)算機(jī)上運(yùn)行時(shí)，執(zhí)行時(shí)間均不相同。這表明使用絕對(duì)的執(zhí)行時(shí)間衡量算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法執(zhí)行時(shí)間的大小只依賴于問題的規(guī)模(通常用整數(shù)n表示)，或者說，它是問題規(guī)模的函數(shù)。一個(gè)算法是由控制結(jié)構(gòu)(順序、分支和循環(huán))和基本操作構(gòu)成的，算法時(shí)間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對(duì)于所研究的問題來說是基本操作的操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度，記做Ο(n)=Ο(f(n))其中，f(n)為基本操作重復(fù)執(zhí)行的次數(shù)，是問題規(guī)模n的非遞減函數(shù)，隨著問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同；Ο(n)稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。例如，求4×4矩陣元素和，“加法”運(yùn)算是矩陣元素求和問題的基本操作。整個(gè)算法的執(zhí)行時(shí)間與該基本操作(加法)重復(fù)執(zhí)行的次數(shù)成正比，記做Ο(4)=Ο(f(4))其中，f(4)＝4×4＝16。算法描述如下：

intsum(intnum［4］［4］)

{

inti，j，r=0；

for(i=0；i<4；i++) for(j=0；j<4；j++) r+=num［i］［j］；/*基本操作*/

returnr；

}顯然，被稱做問題的基本操作重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間是成正比的。在多數(shù)情況下，重復(fù)執(zhí)行是最深層循環(huán)內(nèi)的語句中的基本操作，其執(zhí)行次數(shù)和包含它的語句的頻度相同(語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù))。例如，程序段1:

for(i=1；i<=n；++i)

++x；程序段2：

for(j=1；j<=n；++j)

for(k=1；k<=n；++k)

++x；程序段1的語句頻度為n，時(shí)間復(fù)雜度為Ο(n)；程序段2的語句頻度為n2，時(shí)間復(fù)雜度為Ο(n2)。常見函數(shù)的增長(zhǎng)率如圖1-6所示。對(duì)于算法來說，隨著問題規(guī)模的增加，其時(shí)間復(fù)雜度變化或增加得越緩慢，則性能越好。圖1-6常見函數(shù)的增長(zhǎng)率1.4本章小結(jié)

本章首先從實(shí)例出發(fā)介紹了數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容，然后介紹了有關(guān)的基本概念和術(shù)語，最后介紹了算法的概念、特性、描述方法及性能分析。在深入學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前，首先了解數(shù)據(jù)結(jié)構(gòu)的意義、研究?jī)?nèi)容以及一些相關(guān)概念，對(duì)于深入了解后面章節(jié)的內(nèi)容會(huì)有很大的幫助。自測(cè)習(xí)題

1-1解釋下列術(shù)語:數(shù)據(jù)數(shù)據(jù)項(xiàng)數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)算法

1-2數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？

1-3根據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系，一般分為哪幾類基本的數(shù)據(jù)結(jié)構(gòu)？

1-4算法有哪幾個(gè)特性？

1-5有下列運(yùn)行時(shí)間函數(shù)：

(1)T1(n)=1000；(2)T2(n)=n2+1000n；

(3)T3(n)=3n3+100n2+n+1。試分別寫出相應(yīng)的用Ο表示的時(shí)間復(fù)雜度。

1-6試給出下面兩個(gè)算法的時(shí)間復(fù)雜度。

(1)fori＝1tondo

x＝x+1；

(2)fori＝1tondo

forj＝1tondo x＝x+1；2.1線性結(jié)構(gòu)

2.2樹和二叉樹

2.3本章小結(jié)

自測(cè)習(xí)題2.1線性結(jié)構(gòu)2.1.1線性表及邏輯結(jié)構(gòu)

線性表(Linear_List)是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)言之，一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。每個(gè)數(shù)據(jù)元素的具體含義在不同的情況下各不相同，它可以是一個(gè)數(shù)或一個(gè)符號(hào)，也可以是一頁書，甚至其他更復(fù)雜的信息。例如，26個(gè)英文字母的字母表：(A，B，C，…，Z)是一個(gè)線性表，表中的數(shù)據(jù)元素是單個(gè)字母字符。又如，目前全國(guó)重點(diǎn)大學(xué)的校名可以用線性表的形式給出：

(“清華大學(xué)”，“北京大學(xué)”，“北京交通大學(xué)”，“上海復(fù)旦大學(xué)”，…)表中的數(shù)據(jù)元素是字符串。在較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)(Item)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄(Record)，含有大量記錄的線性表又稱文件(File)。例如，某公司人員登記表如表2-1所示，表中每個(gè)員工的情況為一個(gè)記錄，它由姓名、性別、年齡、工作證號(hào)、部門五個(gè)數(shù)據(jù)項(xiàng)組成。綜上可見，線性表中的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素必定具有相同的特性，即屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在著序鄰接關(guān)系。若將線性表記為(a1，…，ai-1

，ai，ai+1，…，an)則表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當(dāng)i＝1，2，…，n-1時(shí)，ai有且僅有一個(gè)直接后繼，當(dāng)i＝2，3，…，n時(shí)，ai有且僅有一個(gè)直接前驅(qū)。由此可以總結(jié)出線性結(jié)構(gòu)的特點(diǎn)是：在數(shù)據(jù)元素的非空有限集中，

(1)存在唯一的一個(gè)被稱做“第一個(gè)”的數(shù)據(jù)元素；

(2)存在唯一的一個(gè)被稱做“最后一個(gè)”的數(shù)據(jù)元素；

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

(4)除最后一個(gè)之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。線性表中元素的個(gè)數(shù)n(n≥0)定義為線性表的長(zhǎng)度，n＝0時(shí)稱為空表。在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短，即對(duì)線性表的數(shù)據(jù)元素不僅可以進(jìn)行訪問，還可進(jìn)行插入和刪除等。對(duì)線性表進(jìn)行的操作有以下幾種：

(1)初始化：創(chuàng)建一個(gè)空的線性表。

(2)計(jì)數(shù)：求線性表的長(zhǎng)度。

(3)讀?。鹤x取線性表的第i個(gè)元素。

(4)刪除：刪除線性表的第i個(gè)元素。

(5)歸并：把兩個(gè)或更多的線性表按一定的要求合并成一個(gè)新表。

(6)插入：在第i個(gè)位置插入新的數(shù)據(jù)元素。

(7)查找：確定在線性表中是否存在數(shù)據(jù)元素x。2.1.2線性表的順序存儲(chǔ)結(jié)構(gòu)

1.順序存儲(chǔ)結(jié)構(gòu)的概念及特點(diǎn)

一個(gè)線性表可以采用多種不同的存儲(chǔ)方式存儲(chǔ)到計(jì)算機(jī)中，其中，最簡(jiǎn)單的方法就是順序存儲(chǔ)。線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。假設(shè)線性表的每個(gè)元素需要占用d個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置，則線性表中第i＋1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai＋1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系：LOC(ai＋1)＝LOC(ai)＋d一般來說，線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為L(zhǎng)OC(ai)＝LOC(a1)＋(i-1)×d式中，LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。假設(shè)一個(gè)線性表含有n個(gè)元素，分別為a0，a1，…，ai，…，an-1，當(dāng)采用順序存儲(chǔ)的時(shí)候，數(shù)據(jù)元素的邏輯地址、數(shù)據(jù)元素以及存儲(chǔ)地址的關(guān)系如圖2-1所示。圖2-1順序存儲(chǔ)示意圖線性表的這種計(jì)算機(jī)內(nèi)表示稱做線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像(SequentialMapping)，相應(yīng)地，稱這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。順序表的特點(diǎn)是：表中相鄰的元素ai和ai+1被賦以相鄰的存儲(chǔ)位置LOC(ai)和LOC(ai+1)，即以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。由此，只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

2.順序存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)類型定義高級(jí)程序設(shè)計(jì)語言中有一種數(shù)據(jù)類型為數(shù)組類型，系統(tǒng)開辟了一片連續(xù)的存儲(chǔ)單元對(duì)其進(jìn)行存儲(chǔ)，此外，數(shù)組也具有隨機(jī)存取的特性，因此，通常都用數(shù)組來描述數(shù)據(jù)結(jié)構(gòu)中的順序存儲(chǔ)結(jié)構(gòu)。在此，由于線性表的長(zhǎng)度可變，且所需最大存儲(chǔ)空間隨問題的不同而不同，因此在類C語言中描述如下:

#defineMAXSIZE100

/*表的最大長(zhǎng)度*/

#defineDataTypeint

/*數(shù)據(jù)元素(結(jié)點(diǎn))類型*/

typedefstruct

{

DataTypedata［MAXSIZE］；

/*數(shù)組Data下標(biāo)為0，1，…，MAXSIZE-1*/

intlast；/*last為表長(zhǎng)*/

}SeqList；/*SeqList即為順序表的類型*/

3.基本操作在順序表上的實(shí)現(xiàn)在這種存儲(chǔ)結(jié)構(gòu)中，容易實(shí)現(xiàn)線性表的某些操作，如隨機(jī)存取第i個(gè)數(shù)據(jù)元素等。要特別注意的是，C語言中數(shù)組的下標(biāo)從“0”開始，因此，若L是SeqList類型的順序表，則表中第j個(gè)數(shù)據(jù)元素是L.data［j-1］。下面重點(diǎn)討論線性表的基本操作在順序表上的實(shí)現(xiàn)方法。

1)順序表的初始化執(zhí)行順序表的初始化函數(shù)，結(jié)果返回一個(gè)空的順序表。

SeqListInti_Sequenlist(SeqLista)

{

a.last=0；

returna；/*通過返回值，帶回結(jié)果*/

}

2)順序表上元素的插入插入操作是指在長(zhǎng)度為n的線性表中第i(1≤i≤n)個(gè)元素之前插入一個(gè)元素x，使長(zhǎng)度為n的線性表變?yōu)殚L(zhǎng)度為n＋1的線性表。算法的思路是：因?yàn)橐共迦朐睾蟮木€性表仍具有線性表的結(jié)構(gòu)特征，所以必須將元素ai，…，an逐一向后移動(dòng)一個(gè)位置，然后將x放置到第i個(gè)位置，表長(zhǎng)加1。這里移動(dòng)的順序十分重要，從邏輯上考慮，只能按an，…，ai的順序進(jìn)行移位操作，先將an向后移一位，再將an-1移到an原來的位置上，以此類推，直到ai移到ai+1的位置。例如，圖2-2表示一個(gè)線性表在進(jìn)行插入操作前后其數(shù)據(jù)元素在存儲(chǔ)空間中的位置變化。為了在線性表的第2個(gè)和第3個(gè)元素之間插入一個(gè)值為38的數(shù)據(jù)元素，需將第3個(gè)至第6個(gè)數(shù)據(jù)元素依次往后移動(dòng)一個(gè)位置，并且表長(zhǎng)變?yōu)?。圖2-2線性表在進(jìn)行插入操作前后其數(shù)據(jù)元素在存儲(chǔ)空間中的位置變化順序表的第i個(gè)位置插入數(shù)據(jù)元素的算法如下:

intinsert(SeqListL，DataTypex，inti)

{

intk；

/*判斷位置是否合法*/

if(i<1||i>(L.last+1)||L.last>=MAXSIZE)

{

printf(″e(cuò)rror″)；

return0；

}

else

{

for(k=L.last；k>=i；k)

L.data［k］=L.data［k-1］；

L.data［i-1］=x；

L.last=L.last+1；

return(1)；/*成功返回1*/

}

}一般情況下，在第i(1≤i≤n)個(gè)元素之前插入一個(gè)元素時(shí)，需將第n個(gè)至第i個(gè)(共n－i＋1個(gè))元素向后移動(dòng)一個(gè)位置。由以上算法可見，當(dāng)在順序存儲(chǔ)結(jié)構(gòu)的線性表中某個(gè)位置上插入一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)元素上(換句話說，移動(dòng)元素的操作為預(yù)估算法時(shí)間復(fù)雜度的基本操作)，而移動(dòng)元素的個(gè)數(shù)則取決于插入元素的位置。假設(shè)pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值(平均次數(shù))為一般地，可以假定在線性表的任何位置上插入元素都是等概率的，即

則

由上式可見，在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)數(shù)據(jù)元素，約平均移動(dòng)表中的一半元素。若表長(zhǎng)為n，則算法的時(shí)間復(fù)雜度為O(n)。對(duì)后面的各種算法，不再詳細(xì)分析和推導(dǎo)算法的時(shí)間復(fù)雜度，只給出推導(dǎo)的結(jié)果。

3)順序表上元素的刪除在順序表上實(shí)現(xiàn)刪除操作也必須移動(dòng)元素才能使刪除后的線性表仍具有線性結(jié)構(gòu)的特征。這里移動(dòng)順序也是十分重要的，從邏輯上考慮，只能按ai+1，…，an的順序進(jìn)行移位操作，先將ai+1向前移一位，覆蓋掉被刪除的元素，再將ai+2移到ai+1原來的位置上，以此類推，直到an移到an-1的位置上，并將表長(zhǎng)減1。例如，圖2-3所示為一個(gè)線性表在進(jìn)行刪除操作前后其數(shù)據(jù)元素在存儲(chǔ)空間中的位置變化。為了在線性表中刪除第3個(gè)數(shù)據(jù)元素，需將第4個(gè)至第7個(gè)數(shù)據(jù)元素依次往前移動(dòng)一個(gè)位置，且表長(zhǎng)變?yōu)?。圖2-3線性表在進(jìn)行刪除操作前后其數(shù)據(jù)元素在存儲(chǔ)空間中的位置變化順序表的第i個(gè)位置刪除數(shù)據(jù)元素的算法如下:

intDelete(SeqListL，inti)

{

intj；

if((i<1)||(i>L.last)||(L.last==0))

{

printf(″Error!″)；

return0；

}

else

{

for(j=i；j<L.last；j++)//第j+1個(gè)元素前移

L.data［j-1］=L.data［j］；

L.last；

return1；

}

}線性表的刪除操作是使長(zhǎng)度為n的線性表(a1，…，ai-1，ai，ai+1，…，an)變成長(zhǎng)度為n-1的線性表(a1，…，ai-1，ai+1，…，an)。數(shù)據(jù)元素ai-1、ai和ai+1之間的邏輯關(guān)系發(fā)生了變化，為了在存儲(chǔ)結(jié)構(gòu)上反映這個(gè)變化，同樣需要移動(dòng)元素。一般情況下，刪除第i(1≤i≤n)個(gè)元素時(shí)需將第i+1個(gè)至第n個(gè)(共n-i個(gè))元素依次向前移動(dòng)一個(gè)位置。當(dāng)在順序存儲(chǔ)結(jié)構(gòu)的線性表中某個(gè)位置上刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)元素上(換句話說，移動(dòng)元素的操作為預(yù)估算法時(shí)間復(fù)雜度的基本操作)，而移動(dòng)元素的個(gè)數(shù)則取決于刪除元素的位置。在順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除一個(gè)數(shù)據(jù)元素，平均約移動(dòng)表中的一半元素。若表長(zhǎng)為n，則算法的時(shí)間復(fù)雜度為O(n)。

4)順序表上元素的查找在順序表上查找某個(gè)元素時(shí)，對(duì)線性表上的元素只有訪問，沒有變動(dòng)，所以無移動(dòng)元素的操作。基本操作是判斷表中的元素是否和給定的元素值x相等。順序表上元素的查找算法如下：

intLocate(SeqLista，DataTypex)

{

/*在順序表a中查找值為x的元素，返回其位置*/

intk=1；

while(k<=a.last&&a.data［k-1］!=x)

k++；

if(k<=a.last)

returnk；

else

return0；//找不到元素

}順序表上元素的查找算法的時(shí)間復(fù)雜度為O(n)。線性表還可進(jìn)行一些更復(fù)雜的操作，如將兩個(gè)或兩個(gè)以上的線性表合并成一個(gè)線性表，把一個(gè)線性表拆開成兩個(gè)或兩個(gè)以上的線性表，重新復(fù)制一個(gè)線性表等等。有些操作將在應(yīng)用舉例部分給出例題。

4.應(yīng)用舉例

【例2-1】假設(shè)利用兩個(gè)線性表la和lb分別表示兩個(gè)集合a和b(線性表中的數(shù)據(jù)元素即為集合中的成員)，現(xiàn)要求一個(gè)新的集合a＝a∪b。算法分析：題目要求對(duì)線性表進(jìn)行如下操作：擴(kuò)大線性表la，將存在于線性表lb中而不存在于線性表la中的數(shù)據(jù)元素插入到線性表la中。只需從線性表lb中依次取得每個(gè)數(shù)據(jù)元素，并按值在線性表la中進(jìn)行查找，若不存在，則將其插入。上述操作過程可用下列算法來描述。

voidunite_seqlist(SeqLista，SeqListb)

{

inti，j，k；

for(i=1；i<=b.last；i++)

{

k=1；

while(k<=a.last&&a.data［k-1］!=b.data［i-1］)

k++；

if(k>a.last)//找不到元素

if(a.last<MAXSIZE)/*判斷線性表是否滿*/

{

a.data［a.last］=x；

a.last=a.last+1；

}

else

{

printf(″overflow!″)；

break；

}

}

}

【例2-2】已知線性表la和lb中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將la和lb歸并為一個(gè)新的線性表lc，且lc中的數(shù)據(jù)元素仍按值非遞減有序排列。例如，設(shè)

la=(3，5，8，13)lb=(6，9，11，15，20)lc＝(3，5，6，8，9，11，13，15，20)算法分析：由題目要求可知，lc中的數(shù)據(jù)元素或是la中的數(shù)據(jù)元素，或是lb中的數(shù)據(jù)元素，只要先設(shè)lc為空表，然后將la或lb中的元素逐個(gè)插入到lc中即可。為使lc中元素按值非遞減有序排列，可設(shè)兩個(gè)指針i和j分別指向la和lb中的某個(gè)元素，若設(shè)i當(dāng)前所指的元素為a，j當(dāng)前所指的元素為b，則當(dāng)前應(yīng)插入到lc中的元素c為上述操作過程可用下列算法來描述。

voidmerge_seqlist(SeqListla，SeqListlb，SeqListlc)

{

inti，j，k；

i=j=k=1；

while(i<=la.last&&j<=lb.last)if(la.data［i-1］<=lb.data［j-1］){lc.data［k-1］=la.data［i-1］；

k++；

i++；

}

else{lc.data［k-1］=lb.data［j-1］；

k++；

j++；

}

while(i<=la.last){lc.data［k-1］=la.data［i-1］；

k++；

i++；

}

while(i<=lb.last){

lc.data［k-1］=lb.data［j-1］；

k++；

j++；

}

lc.last=k-1；

}2.1.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

1.鏈表的概念及類型定義

從2.1.2節(jié)的討論中可知，線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是：邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰，因此可以隨機(jī)存取表中任一個(gè)元素，它的存儲(chǔ)位置可用一個(gè)簡(jiǎn)單、直觀的公式來表示。然而，從另一方面來看，這個(gè)特點(diǎn)也造成了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)：在進(jìn)行插入或刪除操作時(shí)，需要移動(dòng)大量元素。本節(jié)將討論線性表的另一種表示方法——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由于這種結(jié)構(gòu)不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的缺點(diǎn)，但同時(shí)也失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是：可用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的)。因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息(即直接后繼的存儲(chǔ)位置)。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)(Node)。結(jié)點(diǎn)包括兩個(gè)域：存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域;存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱做指針或鏈。n個(gè)結(jié)點(diǎn)連接成一個(gè)鏈表，即為線性表(a1，a2，…，an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，因此又稱線性鏈表或單鏈表(本書后面內(nèi)容中出現(xiàn)的“鏈表”指的就是單鏈表)。

例如，圖2-4所示為線性表(A，B，C，D，E，F(xiàn)，G)的線性鏈表存儲(chǔ)結(jié)構(gòu)，整個(gè)鏈表的存取必須從頭指針開始進(jìn)行，頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)(即第一個(gè)數(shù)據(jù)元素的存儲(chǔ)映像)的存儲(chǔ)位置。同時(shí)，由于最后一個(gè)數(shù)據(jù)元素沒有直接后繼，因此線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針為“空”(NULL)。用線性鏈表表示線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針來指示的。換句話說，指針為數(shù)據(jù)元素之間的邏輯關(guān)系的映像，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素其存儲(chǔ)的物理位置不要求緊鄰，因此，這種存儲(chǔ)結(jié)構(gòu)為非順序映像或鏈?zhǔn)接诚?。圖2-4線性鏈表存儲(chǔ)結(jié)構(gòu)通常把鏈表畫成用箭頭相連接的結(jié)點(diǎn)的序列，結(jié)點(diǎn)之間的箭頭表示鏈域中的指針。圖2-4所示的線性鏈表可畫成如圖2-5所示的形式，這是因?yàn)樵谑褂面湵頃r(shí)，關(guān)心的只是它所表示的線性表中數(shù)據(jù)元素之間的邏輯順序，而不是每個(gè)數(shù)據(jù)元素在存儲(chǔ)器中的實(shí)際位置。圖2-5線性鏈表舉例由此可見，單鏈表可由頭指針唯一確定，在C語言中可用“結(jié)構(gòu)指針”來描述。下面就是線性表的單鏈表存儲(chǔ)結(jié)構(gòu)的結(jié)點(diǎn)類型定義：

typedefstructnode//結(jié)點(diǎn)類型定義

{

DataTypedata；

structnode*next；

}LinkList；假設(shè)L是LinkList型變量，則L為單鏈表的頭指針，它指向表中的第一個(gè)結(jié)點(diǎn)。若L為“空”(L＝NULL)，則它所表示的線性表為“空”表，其長(zhǎng)度n為“零”。有時(shí)在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如線性表的長(zhǎng)度等附加信息。頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針(即第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置)。如圖2-6(a)所示，單鏈表的頭指針指向頭結(jié)點(diǎn)。若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?，如圖2-6(b)所示。圖2-6帶頭結(jié)點(diǎn)的單鏈表在線性表的順序存儲(chǔ)結(jié)構(gòu)中，由于邏輯上相鄰的兩個(gè)元素在物理位置上緊鄰，因此每個(gè)元素的存儲(chǔ)位置都可從線性表的起始位置計(jì)算得到。在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都沒有固定的聯(lián)系。然而，每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的信息之中。

2.基本操作在單鏈表上的實(shí)現(xiàn)假設(shè)p是指向線性表中第i個(gè)數(shù)據(jù)元素(結(jié)點(diǎn)ai)的指針，則p->next是指向第i＋1個(gè)數(shù)據(jù)元素(結(jié)點(diǎn)ai+1)的指針。換句話說，若p->data＝ai，則p->next->data＝ai+l。由此可知，在單鏈表中，取得第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找，因此，單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

1)單鏈表初始化操作算法思想：建立一個(gè)單鏈表，首先要生成一個(gè)結(jié)點(diǎn)，空鏈表就是只包含頭結(jié)點(diǎn)的鏈表，如圖2-7所示。圖2-7單鏈表初始化操作示意圖單鏈表初始化操作的算法如下:

voidInitList(LinkList*head)

{

LinkList*t；

t=(LinkList*)malloc(sizeof(LinkList))；

head=t；

t->next=NULL；

}

2)建立單鏈表操作設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型為字符，依次輸入這些字符，并以“$”作為輸入結(jié)束的標(biāo)志。動(dòng)態(tài)地建立單鏈表有兩種常用方法：尾插入法和頭插入法。下面詳細(xì)講解這兩種方法的算法實(shí)現(xiàn)。

(1)尾插入法建表。算法思路：從一個(gè)空表開始，反復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域，然后將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上，直到讀入結(jié)束標(biāo)志符為止。圖2-8描述了插入一個(gè)新結(jié)點(diǎn)的過程。圖2-8帶頭結(jié)點(diǎn)的尾插入法建表過程示意圖分析尾插入法建表的過程：一般情況下，插入一個(gè)元素對(duì)應(yīng)的指針操作是

last->next＝t；

last＝t；但若單鏈表為空鏈表，則在插入第一個(gè)元素的時(shí)候，對(duì)應(yīng)的指針操作是

head＝t；

last＝t；由此可見，當(dāng)單鏈表為空鏈表而又插入第一個(gè)元素時(shí)，情況比較特殊。為了使鏈表上的操作簡(jiǎn)單、一致，可以采用帶頭結(jié)點(diǎn)的單鏈表。下面為帶頭結(jié)點(diǎn)的尾插入法建表算法。voidCreateList1(LinkList*head)

{LinkList*last，*t；

charch；

t=(LinkList*)malloc(sizeof(LinkList))；

head=t；

last=t；//建立表的頭結(jié)點(diǎn)

t->next=NULL；

while((ch=getchar())!=′$′){t=(LinkList*)malloc(sizeof(LinkList))；

t->data=ch；

last->next=t；

last=t；

t->next=NULL；

}}通過上面的算法可以總結(jié)出，帶有頭結(jié)點(diǎn)的單鏈表通常具有以下優(yōu)點(diǎn)：①線性表中第一個(gè)元素結(jié)點(diǎn)的地址被存放到頭結(jié)點(diǎn)的指針域中，這樣表中所有結(jié)點(diǎn)的地址均放到前驅(qū)結(jié)點(diǎn)中，算法對(duì)所有元素結(jié)點(diǎn)的處理可一致化；②無論鏈表是否為空，頭指針均指向頭結(jié)點(diǎn)，這給算法的處理帶來了方便。指針變量和結(jié)點(diǎn)變量是兩個(gè)容易混淆但又必須搞清楚的概念。head是LinkList類型的指針變量，head中指針域存放的為L(zhǎng)inkList類型的某個(gè)結(jié)點(diǎn)的地址。在建表算法中，每個(gè)新結(jié)點(diǎn)都是在需要的時(shí)候動(dòng)態(tài)生成的，是通過標(biāo)準(zhǔn)函數(shù)malloc即malloc(sizeof(LinkList))生成的。當(dāng)某個(gè)變量不再需要的時(shí)候，可以通過free()函數(shù)釋放掉結(jié)點(diǎn)所占用的空間。在C語言中，對(duì)指針?biāo)赶蚪Y(jié)點(diǎn)的成員進(jìn)行訪問，通常用運(yùn)算符->。例如，如果某個(gè)結(jié)點(diǎn)的指針為p，則訪問該結(jié)點(diǎn)的兩個(gè)分量的語句為p->data，p->next。

(2)頭插入法建表。算法思路：從一個(gè)空表開始，反復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域，然后將新結(jié)點(diǎn)插到當(dāng)前鏈表的第一個(gè)結(jié)點(diǎn)位置上，直到讀入結(jié)束標(biāo)志符為止圖2-9描述了插入一個(gè)新結(jié)點(diǎn)的過程。圖2-9帶頭結(jié)點(diǎn)的頭插入法建表過程示意圖

voidCreateList2(LinkList*head)

{

LinkList*t；

charch；

t=(LinkList*)malloc(sizeof(LinkList))；

head=t；//建立頭結(jié)點(diǎn)

t->next=NULL；

while((ch=getchar())!=′$′)

{

t=(LinkList*)malloc(sizeof(LinkList))；

t->data=ch；

t->next=head->next；

head->next=t；

}

}

3)查找操作

(1)按序號(hào)查找。算法思路：在鏈表結(jié)構(gòu)中，只能從鏈表的頭指針出發(fā)，順著指針往下搜索，直至搜索結(jié)束。下面是在帶頭結(jié)點(diǎn)的單鏈表中查找第i個(gè)結(jié)點(diǎn)的算法：若找到第i個(gè)結(jié)點(diǎn)(1≤i≤n)，則返回這個(gè)結(jié)點(diǎn)的指針，否則返回NULL。

LinkList*get(inti；LinkList*head)

{

intj；

linklist*p；

j=0；

p=head；

while(j<i)&&(p->next!=NULL))

{

p=p->next；

j++；

}

if(j==i)

returnp；

else

returnNULL；

}

(2)按值查找。算法思路：從鏈表的頭結(jié)點(diǎn)出發(fā)，順著指針往下搜索，若搜索到給定的值，則返回第一個(gè)找到的結(jié)點(diǎn)的指針，否則返回NULL。

算法如下:

LinkList*locate(datatypex，LinkList*head)

{

LinkList*p；

p=head->next；

while(p!=NULL)

if(p->data==x)

returnp；

else

p=p->next；

returnNULL；

}

4)插入操作(在已知結(jié)點(diǎn)的后面插入新的結(jié)點(diǎn))算法思想：假設(shè)要在線性表的兩個(gè)數(shù)據(jù)元素a和b之間插入一個(gè)數(shù)據(jù)元素x，設(shè)指針p指向值為a的結(jié)點(diǎn)，指針s指向值為x的結(jié)點(diǎn)，在值為a的結(jié)點(diǎn)后面插入指針s指向值為x的結(jié)點(diǎn)時(shí)，需要改變兩個(gè)結(jié)點(diǎn)的指針域，從而實(shí)現(xiàn)三個(gè)元素a、b和x之間邏輯關(guān)系的變化。在已知結(jié)點(diǎn)的后面插入新的結(jié)點(diǎn)時(shí)指針的變化情況如圖2-10所示。圖2-10在已知結(jié)點(diǎn)的后面插入新的結(jié)點(diǎn)時(shí)指針的變化情況算法如下：

voidinsertafter(datatypex，LinkList*p)

{

LinkList*s；

s=malloc(sizeof(LinkList))；

s->data=x；

s->next=p->next；

p->next=s；

}

5)刪除操作(刪除已知結(jié)點(diǎn)的后繼結(jié)點(diǎn))算法思想：如圖2-11所示，在線性表中刪除元素b時(shí)，為了在單鏈表中實(shí)現(xiàn)元素a、b和c之間邏輯關(guān)系的變化，僅需修改結(jié)點(diǎn)a中的指針域。假設(shè)p為指向結(jié)點(diǎn)a的指針，則修改指針的語句為

p->next＝p->next->next圖2-11在單鏈表中刪除結(jié)點(diǎn)時(shí)指針的變化情況算法如下：

intdeleteafter(LinkList*p)

{

LinkList*t；

intr=1；

if(p->next!=NULL)

{

t=p->next；

p->next=t->next；

free(t)；

}

else

r=0；

returnr；

}由此可見，若已知鏈表中元素插入或刪除的確切位置，則在單鏈表中插入或刪除一個(gè)結(jié)點(diǎn)時(shí)，僅需修改指針而不需要移動(dòng)元素。容易看出，在已知結(jié)點(diǎn)的后面插入新的結(jié)點(diǎn)算法和刪除已知結(jié)點(diǎn)的后繼結(jié)點(diǎn)算法的時(shí)間復(fù)雜度均為O(n)。這是因?yàn)椋诘趇-1個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)或刪除第i-1個(gè)結(jié)點(diǎn)，都必須首先找到第i-1個(gè)結(jié)點(diǎn)，即需修改指針的結(jié)點(diǎn)，從算法的實(shí)現(xiàn)中已經(jīng)得知，它的時(shí)間復(fù)雜度為O(n)。在插入和刪除算法中會(huì)引用到C語言中的兩個(gè)標(biāo)準(zhǔn)函數(shù)malloc()和free()。執(zhí)行p＝(LinkList)malloc(sizeof(LinkList))的作用是由系統(tǒng)生成一個(gè)LinkList型的結(jié)點(diǎn)，同時(shí)將該結(jié)點(diǎn)的起始位置賦給指針變量p；反之，執(zhí)行free(q)的作用是由系統(tǒng)回收一個(gè)LinkList型的結(jié)點(diǎn)，回收后的空間可以備作再次生成結(jié)點(diǎn)時(shí)使用。因此，與順序存儲(chǔ)結(jié)構(gòu)不同，單鏈表是一種動(dòng)態(tài)結(jié)構(gòu)。整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共同享用，每個(gè)鏈表占用的空間不能預(yù)先分配，而是由系統(tǒng)根據(jù)需求即時(shí)生成。因此，建立線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程，即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。

3.應(yīng)用舉例

【例2-3】計(jì)算鏈表中結(jié)點(diǎn)的個(gè)數(shù)并打印其值。算法思想：計(jì)算鏈表中結(jié)點(diǎn)的個(gè)數(shù)并打印其值的操作就是通過從鏈表的頭指針出發(fā)，順著指針往下搜索，直到整個(gè)鏈表結(jié)束。算法如下：

voidcount(LinkList*head)

{

LinkList*p；

intn=0；

p=head->next；

while(p!=NULL)

{

printf(p->data);

p=p->next；

n=n+1；

}

}

【例2-4】如何將兩個(gè)有序鏈表歸并為一個(gè)有序鏈表。算法思想：假設(shè)頭指針為L(zhǎng)a和Lb的單鏈表分別為線性表LA和LB的存儲(chǔ)結(jié)構(gòu)，現(xiàn)要?dú)w并La和Lb，得到單鏈表Lc。按照有序的順序表合并的算法思想，需設(shè)立三個(gè)指針pa、pb和pc，其中pa和pb分別指向La表和Lb表中當(dāng)前待比較插入的結(jié)點(diǎn)，而pc指向Lc表中當(dāng)前最后一個(gè)結(jié)點(diǎn)。若pa->data≤pb->data，則將pa所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后，否則將pb所指結(jié)點(diǎn)鏈接到pc所指結(jié)點(diǎn)之后。顯然，指針的初始狀態(tài)為：當(dāng)La和Lb為非空表時(shí)，pa和pb分別指向La和Lb表中第一個(gè)結(jié)點(diǎn)，否則為空；pc指向空表Lc中的頭結(jié)點(diǎn)。由于鏈表的長(zhǎng)度是隱含的，因此第一個(gè)循環(huán)執(zhí)行的條件是pa和pb皆非空，當(dāng)其中一個(gè)為空時(shí)，說明有一個(gè)表的元素已歸并完，這種情況下只要將另一個(gè)表的剩余段鏈接在pc所指結(jié)點(diǎn)之后即可。由此可得歸并兩個(gè)單鏈表的算法如下：

voidMergeList(LinkList*La，linkList*Lb，LinkList*Lc)

{

pa=La->next；

pb=Lb->next；

Lc=pc=La；

while(pa&&pb)

{

if(pa->data<=pb->data)

{

pc->next=pa；

pc=pa；

pa=pa->next；

}

else

{

pc->next=pb；

pc=pb；

pb=pb->next；

}

}

pc->next=(pa!=NULL?)pa：pb；

free(La)；

free(Lb)；

}由此容易看出，單鏈表下的歸并算法和順序表下的歸并算法其時(shí)間復(fù)雜度相同，但空間復(fù)雜度不同。在歸并兩個(gè)鏈表為一個(gè)鏈表時(shí)，不需要另建新表的結(jié)點(diǎn)空間，只需將原來兩個(gè)鏈表中結(jié)點(diǎn)之間的關(guān)系解除，重新按元素值非遞減的關(guān)系將所有結(jié)點(diǎn)鏈接成一個(gè)鏈表即可。

4.線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較

線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有優(yōu)點(diǎn)和缺點(diǎn)，應(yīng)根據(jù)具體的問題選擇合適的存儲(chǔ)結(jié)構(gòu)。下面是二者在空間性能和時(shí)間性能上的比較。

(1)空間性能上的比較。順序表的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。在預(yù)先難以確定長(zhǎng)度的情況下，最好使用鏈表作為存儲(chǔ)結(jié)構(gòu)。因?yàn)殒湵碇械拿總€(gè)結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外還要存儲(chǔ)指針域，所以當(dāng)線性表的長(zhǎng)度變化不大時(shí)，采用順序存儲(chǔ)結(jié)構(gòu)比較節(jié)省存儲(chǔ)空間。

(2)時(shí)間性能上的比較。順序表是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，而鏈表中的元素只能按照頭指針順著鏈表掃描才能取得，因此，若線性表上的操作主要是查找、讀取而很少進(jìn)行插入和刪除操作，則采用順序存儲(chǔ)結(jié)構(gòu)為宜。在順序表中進(jìn)行插入和刪除操作時(shí)平均要移動(dòng)近一半的元素，而在鏈表中進(jìn)行插入和刪除操作時(shí)只需要修改指針即可，因此，在頻繁地進(jìn)行插入和刪除操作的情況下，采用鏈表比較適宜。2.1.4棧和隊(duì)列

1.棧棧(stack)是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對(duì)棧來說，表尾端有其特殊含義，稱為棧頂(top)，相應(yīng)地，表頭端稱為棧底(bottom)。不含元素的空表稱為空棧。假設(shè)棧S＝(a1，a2，…，an)，則稱an為棧底元素，a1為棧頂元素。棧中元素按a1，a2，…，an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說，棧的元素操作是按后進(jìn)先出的原則進(jìn)行的，如圖2-12所示。因此，棧又稱為后進(jìn)先出(FirstInLastOut)的線性表(簡(jiǎn)稱FILO)。圖2-12棧的示意圖棧可以進(jìn)行以下基本操作。

(1)初始化：將棧初始化為空棧。

(2)判空：若棧為空棧，則函數(shù)的返回值為“真”，否則為“假”。

(3)進(jìn)棧：在棧頂插入一個(gè)新的元素。

(4)出棧：刪除棧頂元素。

(5)取棧頂元素：得到棧頂元素的值。

1)順序?！獥５捻樞虼鎯?chǔ)表示和實(shí)現(xiàn)順序棧即采用順序存儲(chǔ)結(jié)構(gòu)的棧，它利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。通常用top＝0表示空棧。由于C語言中數(shù)組的下標(biāo)約定從0開始，因此當(dāng)以C語言作描述語言時(shí)，如此設(shè)定會(huì)帶來很大不便；另一方面，棧在使用過程中所需最大空間的大小很難估計(jì)。以下為順序棧的類型說明。

typedefstruct{DataTypedata［maxsize］；

inttop；

}SeqStack；在C語言中，采用數(shù)組來存儲(chǔ)棧中的數(shù)據(jù)元素，棧底定在一端，棧底的位置固定不變；棧頂是變的，top指示棧頂位置。鑒于C語言中數(shù)組的下標(biāo)約定從0開始，為了方便描述順序棧，可以約定向量中的0單元空閑不用，則top既為棧頂元素的下標(biāo)又指棧中元素的個(gè)數(shù)，當(dāng)top為數(shù)組最大值減1時(shí)，棧滿。按照上面的約定，當(dāng)?？盏臅r(shí)候，棧頂指針top的位置如圖2-13(a)所示；當(dāng)b入棧的時(shí)候，棧頂指針top的位置如圖2-13(b)所示；當(dāng)k元素入棧時(shí)，棧里的元素達(dá)到最大值，即棧滿，如圖2-13(c)所示；當(dāng)一元素入棧時(shí)，無法入棧，發(fā)生溢出現(xiàn)象，如圖2-13(d)所示；當(dāng)k元素出棧時(shí)，棧頂指針top指向e元素，如圖2-13(e)所示。圖2-13入棧和出棧操作時(shí)棧頂指針top的變化下面是順序棧上實(shí)現(xiàn)基本操作時(shí)對(duì)應(yīng)的算法。

(1)初始化。算法思想：此操作的作用是將棧初始化為空棧。因?yàn)闂ｍ斨羔榯op也可以表示棧中元素的個(gè)數(shù)，所以可以將top置為0來表示空棧。具體算法如下：

voidIniStack(SeqStack*s)

{s->top=0；

}

(2)判空。算法思想：若棧為空棧，即棧頂指針top為0，則函數(shù)的返回值為“真”，否則為“假”。具體算法如下：

intempty(SeqStack*s)

{

if(s->top==0)

return1；

else

return0；

}

(3)進(jìn)棧。算法思想：在棧頂插入一個(gè)新的元素，此時(shí)，棧頂指針向上移動(dòng)1個(gè)位置。具體算法如下：

intPush(SeqStack*s，DataTypex)

{

if(s->top==maxsize-1)

{

printf(″overflow″)；

return0；

}

else

{

s->top++；

(s->data)［s->top］=x；

return1；

}

}

(4)出棧。算法思想：刪除棧頂元素，通過棧頂指針減1來實(shí)現(xiàn)。具體算法如下：

Pop(SeqStack*s)

{DataTypex；

if(empty(s))printf(″underflow″)；

elses->top--；

}

(5)取棧頂元素。算法思想：得到棧頂元素的值。此算法與出棧操作的區(qū)別在于棧頂指針沒有發(fā)生變化，棧中的元素也沒有發(fā)生變化。具體算法如下：

DataTypeGetTop(SeqStack*s)

{DataTypex，XX=#；//#為特殊值，表示空元素

if(empty(s))

{

printf(″underflow″)；

x=XX；

}

else

x=(s->data)［s->top］；

returnx；

}

2)鏈棧-棧的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)若棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，則應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。人們將用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱做“鏈?！?。由于棧的插入和刪除操作只能在一端進(jìn)行，而對(duì)于單鏈表來說，在首端插入、刪除結(jié)點(diǎn)要比尾端相對(duì)容易一些，因此，將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。由于只能在鏈表的頭部進(jìn)行操作，因此沒有必要附加頭結(jié)點(diǎn)，通常用一個(gè)無頭結(jié)點(diǎn)的單鏈表來表示。下面是鏈棧的數(shù)據(jù)類型描述。

typedefstructsnode{DataTypedata；

structsnode*next；

}LinkStack；圖2-14所示為鏈棧示意圖。通過語句LinkStack*top定義了一個(gè)棧頂指針top，top能唯一地確定一個(gè)鏈棧。當(dāng)top=NULL時(shí)，該鏈棧為空棧，鏈棧沒有棧滿的問題。圖2-14鏈棧示意圖

(1)初始化。算法思想：此操作的作用是將棧初始化為空棧，只需將棧頂指針top