數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述課件

緒論

1.1什麼是數(shù)據(jù)結(jié)構(gòu)（定義）1.數(shù)據(jù)（Data）數(shù)據(jù)是描述客觀事物的數(shù)值、字元以及能輸入機(jī)器且能被處理的各種符號(hào)集合。換句話說(shuō)，數(shù)據(jù)是對(duì)客觀事物採(cǎi)用電腦能夠識(shí)別、存儲(chǔ)和處理的形式所進(jìn)行的描述。簡(jiǎn)而言之，數(shù)據(jù)就是電腦化的資訊。

例如對(duì)C根源程式，數(shù)據(jù)概念不僅是根源程式所處理的數(shù)據(jù)，相對(duì)於編譯程序來(lái)說(shuō)，C編譯程序相對(duì)於根源程式是一個(gè)處理程式，它加工的數(shù)據(jù)是字元流的根源程式（.c），輸出的結(jié)果是目標(biāo)程式(.obj)；對(duì)於鏈接程式來(lái)說(shuō)，它加工的數(shù)據(jù)是目標(biāo)程式(.obj)，輸出的結(jié)果是可執(zhí)行程式(.exe)，如圖1.1所示。圖1.1編譯程序示意圖根源程式目標(biāo)程度可執(zhí)行程式C編譯程序C鏈接程式2.數(shù)據(jù)元素（DataElement）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位,是數(shù)據(jù)集合的個(gè)體，在電腦中通常作為一個(gè)整體進(jìn)行考慮和處理。表1-1學(xué)籍表學(xué)號(hào)姓名性別籍貫出生年月住址101趙紅玲女河北1983.11北京………………

資料項(xiàng)目記錄3.數(shù)據(jù)對(duì)象（DataObject）

數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是集合N={0，±1，±2，…}，字母字元數(shù)據(jù)對(duì)象是集合C={′A′，′B′，…，′Z′}，表1-1所示的學(xué)籍表也可看作一個(gè)數(shù)據(jù)對(duì)象。由此可看出，不論數(shù)據(jù)元素集合是無(wú)限集（如整數(shù)集）、有限集（如字元集），還是由多個(gè)數(shù)據(jù)項(xiàng)組成的複合數(shù)據(jù)元素（如學(xué)籍表），只要性質(zhì)相同，都是同一個(gè)數(shù)據(jù)對(duì)象。綜上1~3所述，再分析數(shù)據(jù)概念：4.數(shù)據(jù)結(jié)構(gòu)（DataStructure）

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)係的數(shù)據(jù)元素集合，圖1.2學(xué)校組織層次結(jié)構(gòu)圖圖1.3交通流量圖5.數(shù)據(jù)類型(DataType)

數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合，即該類型的取值範(fàn)圍，以及該類型中可允許使用的一組運(yùn)算。例如高級(jí)語(yǔ)言中的數(shù)據(jù)類型就是已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的實(shí)例。從這個(gè)意義上講，數(shù)據(jù)類型是高級(jí)語(yǔ)言中允許的變數(shù)種類，是程式語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)（即程式中允許出現(xiàn)的數(shù)據(jù)形式）。在高級(jí)語(yǔ)言中，整型類型可能的取值範(fàn)圍是-32768~+32767，可用的運(yùn)算符集合為加、減、乘、除、乘方、取模（如C語(yǔ)言中+，-，*，/，%）。6.數(shù)據(jù)抽象與抽象數(shù)據(jù)類型

１）數(shù)據(jù)的抽象電腦中使用的是二進(jìn)位數(shù)，組合語(yǔ)言中則可給出各種數(shù)據(jù)的十進(jìn)位表示，如98.65、9.6E3等,它們是二進(jìn)位數(shù)據(jù)的抽象;使用者在編程時(shí)可以直接使用,不必考慮實(shí)現(xiàn)細(xì)節(jié)。在高級(jí)語(yǔ)言中，則給出更高一級(jí)的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型，如整型、實(shí)型、字元型等。到抽象數(shù)據(jù)類型出現(xiàn)，可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹(shù)、圖、窗口、管理器等，這種數(shù)據(jù)抽象的層次為設(shè)計(jì)者提供了更有利的手段，使得設(shè)計(jì)者可以從抽象的概念出發(fā)，從整體考慮，然後自頂向下、逐步展開(kāi)，最後得到所需結(jié)果。可以這樣看，高級(jí)語(yǔ)言中提供整型、實(shí)型、字元、記錄、檔、指針等多種數(shù)據(jù)類型，可以利用這些類型構(gòu)造出像棧、佇列、樹(shù)、圖等複雜的抽象數(shù)據(jù)類型。

２）抽象數(shù)據(jù)類型(AbstractDataType)

抽象數(shù)據(jù)類型（簡(jiǎn)稱ADT）是指基於一類邏輯關(guān)係的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決於客觀存在的一組邏輯特性，而與其在電腦內(nèi)如何表示和實(shí)現(xiàn)無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用。從某種意義上講，抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。整數(shù)類型就是一個(gè)簡(jiǎn)單的抽象數(shù)據(jù)類型實(shí)例?！俺橄蟆钡囊饬x在於教學(xué)特性的抽象。一個(gè)ADT定義了一個(gè)數(shù)據(jù)對(duì)象，數(shù)據(jù)對(duì)象中各元素間的結(jié)構(gòu)關(guān)係，以及一組處理數(shù)據(jù)的操作。ADT通常是指由用戶定義且用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，並包括一組相關(guān)服務(wù)操作。

抽象數(shù)據(jù)類型是近年來(lái)電腦科學(xué)中提出的最重要的概念之一，它集中體現(xiàn)了程式設(shè)計(jì)中一些最基本的原則：分解、抽象和資訊隱藏。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來(lái)；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過(guò)程隱藏起來(lái)。圖1.4用抽象數(shù)據(jù)類型指導(dǎo)問(wèn)題求解

數(shù)學(xué)模型→抽象數(shù)據(jù)類型→數(shù)據(jù)結(jié)構(gòu)，恰好反應(yīng)了資訊結(jié)構(gòu)轉(zhuǎn)換的三個(gè)重要階段，而在這個(gè)轉(zhuǎn)換過(guò)程中，數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，抽象數(shù)據(jù)類型是中樞。一個(gè)線性表的抽象數(shù)據(jù)類型的描述如下：

ADTLinear

-list

數(shù)據(jù)元素所有ai屬於同一數(shù)據(jù)對(duì)象，i=1，2，…，n,n≥0；邏輯結(jié)構(gòu)所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關(guān)係<ai，ai+1>，ai無(wú)前趨，an無(wú)後繼；操作 設(shè)L為L(zhǎng)inear-list:

Initial(L):初始化空線性表;

Length(L):求線性表的表長(zhǎng);

Get(L,i):取線性表的第i個(gè)元素；

Insert(L,i,b):線上性表的第i個(gè)位置插入元素b；

Delete(L,i):刪除線性表的第i個(gè)元素。３）抽象數(shù)據(jù)類型實(shí)現(xiàn)第一種情況：傳統(tǒng)的面向過(guò)程的程式設(shè)計(jì)。第二種情況：“包”、“模型”的設(shè)計(jì)方法。第三種情況：面向?qū)ο蟮某淌皆O(shè)計(jì)（ObjectOriented Programming，簡(jiǎn)稱OOP）。４）ADT的表示與實(shí)現(xiàn)

ADT的定義

ADT的定義格式不唯一,我們採(cǎi)用下述格式定義一個(gè)ADT:

ADT<ADT名>

{數(shù)據(jù)對(duì)象:<數(shù)據(jù)對(duì)象的定義>

結(jié)構(gòu)關(guān)係:<結(jié)構(gòu)關(guān)係的定義>

基本操作:<基本操作的定義>

}ADT<ADT名>其中數(shù)據(jù)對(duì)象和結(jié)構(gòu)關(guān)係的定義採(cǎi)用數(shù)學(xué)符號(hào)和自然語(yǔ)言描述,而基本操作的定義格式為:

<操作名稱>(參數(shù)表)

操作前提:<操作前提描述>

操作結(jié)果:<操作結(jié)果描述>

關(guān)於參數(shù)傳遞

參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù),又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù),又能返回操作結(jié)果，也稱變數(shù)參數(shù)。操作前提描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件,操作結(jié)果描述操作執(zhí)行之後,數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回結(jié)果。ADT可用現(xiàn)有電腦語(yǔ)言中已有的數(shù)據(jù)類型,即固有數(shù)據(jù)類型來(lái)表示和實(shí)現(xiàn)。不同語(yǔ)言的表示和實(shí)現(xiàn)方法不盡相同，如ADT中“返回結(jié)果的參數(shù)”，PASCAL語(yǔ)言用“變參”實(shí)現(xiàn),C++語(yǔ)言通過(guò)“引用型參數(shù)”實(shí)現(xiàn),而C語(yǔ)言用“指針參數(shù)”實(shí)現(xiàn)。

用標(biāo)準(zhǔn)C語(yǔ)言表示和實(shí)現(xiàn)ADT描述時(shí)，主要包括以下兩個(gè)方面:

(1)通過(guò)結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。

(2)用C語(yǔ)言函數(shù)實(shí)現(xiàn)各操作。

５）面向?qū)ο蟮母拍?/p>

Coad和Yourdon給出面向?qū)ο蟮母拍睿好嫦驅(qū)ο?對(duì)象+類+繼承+通信

對(duì)象：是指在應(yīng)用問(wèn)題中出現(xiàn)的各種實(shí)體、事件和規(guī)格說(shuō)明等，它是由一組屬性和在這組值上的一組服務(wù)構(gòu)成的，其中屬性值確定了對(duì)象的狀態(tài)。類：把具有相同屬性和服務(wù)的對(duì)象歸到同一類,而把一個(gè)類中的每一個(gè)對(duì)象稱為該類的一個(gè)實(shí)例,它們具有相同的服務(wù)。繼承：面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?/p>

面向?qū)ο蟪淌皆O(shè)計(jì)語(yǔ)言的特點(diǎn)是不僅具有封裝性（encapsulation）,還有繼承性(inheritance)和多態(tài)性(polymorphism)。從以上的討論中可以看出，與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的是定義在數(shù)據(jù)結(jié)構(gòu)上的一組操作。操作的種類和數(shù)目不同，即使邏輯結(jié)構(gòu)相同，這個(gè)數(shù)據(jù)結(jié)構(gòu)的用途也會(huì)大不相同。定義在數(shù)據(jù)結(jié)構(gòu)上的操作的種類是沒(méi)有限制的，可以根據(jù)具體需要而定義。

基本操作主要有以下幾種：

(1)插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素；

(2)刪除：刪去數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定數(shù)據(jù)元素；

(3)更新：改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)元素的值，在概念上等價(jià)於刪除和插入操作的組合；

(4)查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素（的位置和值)；

(5)排序：（線上性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)係，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。

６）結(jié)構(gòu)化的開(kāi)發(fā)方法與面向?qū)ο蟮拈_(kāi)發(fā)方法的不同點(diǎn)結(jié)構(gòu)化的開(kāi)發(fā)方法是面向過(guò)程的開(kāi)發(fā)方法，首先著眼於系統(tǒng)要實(shí)現(xiàn)的功能。從系統(tǒng)的輸入和輸出出發(fā)，分析系統(tǒng)要實(shí)現(xiàn)的功能，用自頂向下、逐步細(xì)化的方式建立系統(tǒng)的功能結(jié)構(gòu)和相應(yīng)的程式模組結(jié)構(gòu)。一旦程式功能需要修改，就會(huì)涉及多個(gè)模組，修改量大，易於出錯(cuò)，並會(huì)引起程式的退化。1.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容1.邏輯結(jié)構(gòu)圖1.5四類基本數(shù)據(jù)結(jié)構(gòu)示意(1)集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬於一個(gè)集合的關(guān)係外，無(wú)任何其他關(guān)係。

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

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

(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)係。邏輯結(jié)構(gòu)線性結(jié)構(gòu)——線性表、棧、隊(duì)、字串、數(shù)組、廣義表非線性結(jié)構(gòu)——樹(shù)、圖2.存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在電腦中的存儲(chǔ)映象，是邏輯結(jié)構(gòu)在電腦中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)係的表示。形式化描述：D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲(chǔ)空間M單元的映象S，D→M，即對(duì)於每一個(gè)d，d∈D,都有唯一的z∈M，使S（D）=Z,同時(shí)這個(gè)映象必須明顯或隱含地體現(xiàn)關(guān)係R。

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)係為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)係的映象與元素本身的映象。邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，兩者綜合起來(lái)建立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)係?！鲰樞蛴诚螅樞虼鎯?chǔ)結(jié)構(gòu)）

■非順序映象（非順序存儲(chǔ)結(jié)構(gòu)）3.運(yùn)算集合表1-2工資表

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合。按某種邏輯關(guān)係組織起來(lái)的一批數(shù)據(jù)，按一定的映象方式把它存放在電腦的記憶體中，並在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。1.3算法1.演算法（Algorithm）的定義

Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.(演算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。)2.演算法的特性

(1)有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮迴圈。

(2)確定性：演算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性。

(3)輸入：有多個(gè)或0個(gè)輸入。

(4)輸出：至少有一個(gè)或多個(gè)輸出。

(5)可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成。在演算法的五大特性中，最基本的是有限性、確定性和可行性。3.演算法設(shè)計(jì)的要求

１）演算法的正確性

(1)所設(shè)計(jì)的程式?jīng)]有語(yǔ)法錯(cuò)誤；

(2)所設(shè)計(jì)的程式對(duì)於幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；

(3)所設(shè)計(jì)的程式對(duì)於精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。

(4)程式對(duì)於一切合法的輸入數(shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。例如：要求n個(gè)數(shù)的最大值問(wèn)題，給出示意演算法如下：max:=0;

for（i=1；i<=n;i++）

{scanf(″%f″,x);

if(x>max)max=x;

}2）可讀性3）健壯性4）高效率和低存儲(chǔ)量1.4演算法描述的工具1.演算法、語(yǔ)言和程式的關(guān)係

(1)演算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)係（包括數(shù)據(jù)邏輯關(guān)係、存儲(chǔ)關(guān)係描述）。

(2)描述演算法的工具：演算法可用自然語(yǔ)言、框圖或高級(jí)程式設(shè)計(jì)語(yǔ)言進(jìn)行描述。自然語(yǔ)言簡(jiǎn)單但易於產(chǎn)生二義，框圖直觀但不擅長(zhǎng)表達(dá)數(shù)據(jù)的組織結(jié)構(gòu)，而高級(jí)程式語(yǔ)言則較為準(zhǔn)確但又比較嚴(yán)謹(jǐn)。

(3)程式是演算法在電腦中的實(shí)現(xiàn)（與所用電腦及所用語(yǔ)言有關(guān)）。2.設(shè)計(jì)實(shí)現(xiàn)演算法過(guò)程的步驟

·

找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)係（建立結(jié)構(gòu)關(guān)係）。

·

確定在某一數(shù)據(jù)對(duì)象上所施加的運(yùn)算。

·

考慮數(shù)據(jù)元素的存儲(chǔ)表示。

·

選擇描述演算法的語(yǔ)言。

·設(shè)計(jì)實(shí)現(xiàn)求解的演算法，並用程式語(yǔ)言加以描述。3.類描述演算法的語(yǔ)言選擇(1)預(yù)定義常量和類型。本書(shū)中用到以下常量符號(hào)，如True、False、MAXSIZE等，約定用如下宏定義預(yù)先定義：＃defineTRUE1

＃defineFALSE0

＃defineMAXSIZE100

＃defineOK1

＃defineERROR0(2)本書(shū)中所有的演算法都以如下的函數(shù)形式加以表示，其中的結(jié)構(gòu)類型使用前面已有的定義。［數(shù)據(jù)類型］函數(shù)名（［形式參數(shù)及說(shuō)明］）

{內(nèi)部數(shù)據(jù)說(shuō)明；執(zhí)行語(yǔ)句組；

}/*函數(shù)名*/

函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括弧“{”和“}”括起來(lái)。函數(shù)中用方括號(hào)括起來(lái)的部分如“［形式參數(shù)］”為可選項(xiàng)，函數(shù)名之後的圓括號(hào)不可省略。(3)賦值語(yǔ)句。

■簡(jiǎn)單賦值;

（1）〈變數(shù)名〉=〈運(yùn)算式〉，它表示將運(yùn)算式的值賦給左邊的變數(shù)；（2）〈變數(shù)〉++，它表示變數(shù)加1後賦值給變數(shù)；（3）〈變數(shù)〉--，它表示變數(shù)減1後賦值給變數(shù)。

■串聯(lián)賦值#;

〈變數(shù)1〉=〈變數(shù)2〉=〈變數(shù)3〉=…=〈變數(shù)k〉=〈運(yùn)算式〉；

■成組賦值#;

（〈變數(shù)1〉，〈變數(shù)2〉，〈變數(shù)3〉，…,〈變數(shù)k〉)=（〈運(yùn)算式1〉，〈運(yùn)算式2〉，〈運(yùn)算式3〉，…,〈運(yùn)算式k〉）；

〈數(shù)組名1〉［下標(biāo)1］［下標(biāo)2］=〈數(shù)組名2〉［下標(biāo)1］［下標(biāo)2］；

■條件賦值;

〈變數(shù)名〉=〈條件運(yùn)算式〉？〈運(yùn)算式1〉:〈運(yùn)算式2〉；

(4)條件選擇語(yǔ)句。

■if（〈運(yùn)算式〉）語(yǔ)句；

■if（〈運(yùn)算式〉）語(yǔ)句1；

else語(yǔ)句2；switch(<運(yùn)算式>）

{case判斷值1:

語(yǔ)句組1；

break;

case判斷值2:

語(yǔ)句組2；

break;

...

case判斷值n:

語(yǔ)句組n;

break;

［default:

語(yǔ)句組；

break;］

}(5)迴圈語(yǔ)句。

for語(yǔ)句

for(<運(yùn)算式1>；<運(yùn)算式2>；<運(yùn)算式3>）

{循環(huán)體語(yǔ)句；}

首先計(jì)算運(yùn)算式1的值，然後求運(yùn)算式2的值，若結(jié)果非零（即為真）則執(zhí)行循環(huán)體語(yǔ)句，最後對(duì)運(yùn)算式3運(yùn)算，如此迴圈，直到運(yùn)算式2的值為零（即不成立為假）時(shí)為止。while語(yǔ)句

while(<條件運(yùn)算式>）

{循環(huán)體語(yǔ)句；}

while迴圈首先計(jì)算條件運(yùn)算式的值，若條件運(yùn)算式的值非零（即條件成立），則執(zhí)行循環(huán)體語(yǔ)句，然後再次計(jì)算條件運(yùn)算式的值，重複執(zhí)行，直到條件運(yùn)算式的值為零（即為假）時(shí)退出迴圈，執(zhí)行該迴圈之後的語(yǔ)句。do-while語(yǔ)句

do{循環(huán)體語(yǔ)句

}while(<條件運(yùn)算式>）該迴圈語(yǔ)句首先執(zhí)行循環(huán)體語(yǔ)句,然後計(jì)算條件運(yùn)算式的值，若條件運(yùn)算式成立，則再次執(zhí)行循環(huán)體，再計(jì)算條件運(yùn)算式的值，直到條件運(yùn)算式的值為零，即條件不成立時(shí)結(jié)束迴圈。(6)輸入、輸出語(yǔ)句。

輸入語(yǔ)句：用函數(shù)scanf實(shí)現(xiàn)；特別當(dāng)數(shù)據(jù)為單個(gè)字元時(shí)，用getchar函數(shù)實(shí)現(xiàn)；當(dāng)數(shù)據(jù)為字串時(shí)，用gets函數(shù)實(shí)現(xiàn)。輸出語(yǔ)句：用printf函數(shù)實(shí)現(xiàn)；當(dāng)要輸出單個(gè)字元時(shí)，用putchar函數(shù)實(shí)現(xiàn)；當(dāng)數(shù)據(jù)為字串時(shí)，用puts函數(shù)實(shí)現(xiàn)。其中輸入輸出函數(shù)中的類型部分不做嚴(yán)格要求，淡化表述。(7)其他一些語(yǔ)句。

①return<運(yùn)算式>或return：用於函數(shù)結(jié)束。

②break語(yǔ)句：可用在迴圈語(yǔ)句或case語(yǔ)句中結(jié)束迴圈過(guò)程或跳出情況語(yǔ)句。

③continue語(yǔ)句：可用在迴圈語(yǔ)句中結(jié)束本次迴圈過(guò)程，進(jìn)入下一次迴圈過(guò)程。

④exit語(yǔ)句：表示出現(xiàn)異常情況時(shí)，控制退出函數(shù)。(8)注釋形式。

/*字串*/

注釋句的作用是增強(qiáng)演算法的可閱讀性，在演算法描述中要求在函數(shù)首部加上對(duì)演算法功能的必要注釋描述。加注釋說(shuō)明時(shí)如果沒(méi)有涉及到的參量一定是多餘的，而涉及到的內(nèi)容應(yīng)當(dāng)作為參量，這實(shí)際上是程式設(shè)計(jì)中的一個(gè)素質(zhì)要求，希望多加注意。(9)一些基本的函數(shù)，例如：max函數(shù)：用於求一個(gè)或幾個(gè)運(yùn)算式中的最大值；min函數(shù)：用於求一個(gè)或幾個(gè)運(yùn)算式中的最小值；abs函數(shù)：用於求運(yùn)算式的絕對(duì)值；eof函數(shù)：用於判定檔是否結(jié)束；eoln函數(shù)：用於判斷文本行是否結(jié)束。1.5對(duì)演算法作性能評(píng)價(jià)1.性能評(píng)價(jià)對(duì)問(wèn)題規(guī)模和該演算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)係的評(píng)價(jià)。問(wèn)題規(guī)模N對(duì)不同的問(wèn)題其含義不同，對(duì)矩陣是階數(shù)，對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)，對(duì)圖是頂點(diǎn)個(gè)數(shù)，對(duì)集合運(yùn)算是集合中的元素個(gè)數(shù)。2.有關(guān)數(shù)量關(guān)係的計(jì)算數(shù)量關(guān)係評(píng)價(jià)體現(xiàn)在時(shí)間——演算法編程後在機(jī)器中所耗費(fèi)的時(shí)間。數(shù)量關(guān)係評(píng)價(jià)體現(xiàn)在空間——演算法編程後在機(jī)器中所占的存儲(chǔ)量。

1）關(guān)於演算法執(zhí)行時(shí)間一個(gè)演算法的執(zhí)行時(shí)間大致上等於其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)於語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。2）語(yǔ)句頻度語(yǔ)句頻度是指該語(yǔ)句在一個(gè)演算法中重複執(zhí)行的次數(shù)。例1-1兩個(gè)n×n階矩陣相乘。3）演算法的時(shí)間複雜度原操作是指從演算法中選取一種對(duì)所研究問(wèn)題是基本運(yùn)算的操作，用隨著問(wèn)題規(guī)模增加的函數(shù)來(lái)表徵,以此作為時(shí)間量度。而對(duì)於演算法分析，我們關(guān)心的是演算法中語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)於問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況並確定T(n)的數(shù)量級(jí)（OrderofMagnitude）。在這裏，我們用“O”來(lái)表示數(shù)量級(jí)，這樣我們可以給出演算法的時(shí)間複雜度概念。所謂演算法的時(shí)間複雜度，即是演算法的時(shí)間量度，記作：T(n)=O(f(n))

它表示隨問(wèn)題規(guī)模n的增大，演算法的執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作演算法的漸進(jìn)時(shí)間複雜度，簡(jiǎn)稱時(shí)間複雜度。

一般情況下，隨n的增大，T(n)的增長(zhǎng)較慢的演算法為最優(yōu)的演算法。例如：在下列三段程式段中，給出原操作x=x+1的時(shí)間複雜度分析。（1）x=x+1；其時(shí)間複雜度為O(1)，我們稱之為常量階；（2）for(i=1;i<=n;i++)x=x+1;其時(shí)間複雜度為O(n)，我們稱之為線性階；（3）for(i=1;i<=n;i++)

for(j=1;j<=n;j++)x=x+1;其時(shí)間複雜度為O(n

2),我們稱之為平方階。此外演算法還能呈現(xiàn)的時(shí)間複雜度有對(duì)數(shù)階O(log2n),指數(shù)階O(2n)等。4）數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間複雜度頻率計(jì)數(shù)數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間複雜度頻率計(jì)數(shù)有7個(gè)：

O(1)常數(shù)型O(n)線性型O(n2)平方型O(n3)立方型

O(2n)指數(shù)型O(log2n)對(duì)數(shù)型O(nlog2n)二維型按時(shí)間複雜度由小到大遞增排列成表1-3（當(dāng)n充分大時(shí)）。不同數(shù)量級(jí)的時(shí)間複雜度的形狀如圖1.6所示，表1-3與圖1.6是同一問(wèn)題的不同表示形式。一般情況下，隨n的增大，T(n)增長(zhǎng)較慢的演算法為最優(yōu)的演算法。從中我們應(yīng)該選擇使用多項(xiàng)式階O(nk)的演算法，而避免使用指數(shù)階的演算法。表1-3常用的時(shí)間複雜度頻率表圖1.6多種數(shù)量級(jí)的時(shí)間複雜度圖示例如：下列程式段：

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

for(j=i;j<=n;j++)x++;

有一個(gè)二重迴圈，語(yǔ)句x++的執(zhí)行頻度為

n+(n-1)+(n-2)+…+3+2+1=n(n+1)/2

而該語(yǔ)句執(zhí)行次數(shù)關(guān)於n的增長(zhǎng)率為n2,即時(shí)間複雜度為O(n2)。5）最壞時(shí)間複雜度演算法中基本操作重複執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集的不同而不同。例如下麵冒泡排序演算法：voidbubble(inta［］,intlength)

{將a中整數(shù)數(shù)組重新排序，達(dá)到遞增有序}inti=0,j,temp;

intchange;

do{

change=false;

for(j=1;j<length-i;j++)

if(a［j］>a［j+1］)

{

temp=a［j］;

a［j］=a［j+1］;

a［j+1］=temp;

change=true;

}

i=i+1;

}

while(i<length||change==true)

}6）演算法的空間複雜度關(guān)於演算法的存儲(chǔ)空間需求，類似於演算法的時(shí)間複雜度，我們採(cǎi)用空間複雜度作為演算法所需存儲(chǔ)空間的量度，記作：S(n)=O(f(n))1.6關(guān)於學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)結(jié)構(gòu)課程的地位

圖1.7數(shù)據(jù)結(jié)構(gòu)與其它課程的關(guān)係2.“數(shù)據(jù)結(jié)構(gòu)”課程的學(xué)習(xí)特點(diǎn)

“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)目標(biāo)是要求學(xué)生學(xué)會(huì)分析數(shù)據(jù)對(duì)象特徵，掌握數(shù)據(jù)組織方法和電腦的表示方法，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)演算法，初步掌握演算法時(shí)間空間分析的技巧，培養(yǎng)良好的程式設(shè)計(jì)技能。人類解決問(wèn)題思維方式可分為兩大類：一類是推理方式，憑藉公理系統(tǒng)思維方法，從抽象公理體系出發(fā)，通過(guò)演繹、歸納、推理來(lái)求證結(jié)果，解決特定問(wèn)題；另一類是演算法方式，憑藉演算法構(gòu)造思維方式，從具體操作規(guī)範(fàn)入手，通過(guò)操作過(guò)程的構(gòu)造和實(shí)施，解決特定問(wèn)題。3.關(guān)於本書(shū)內(nèi)容編寫(xiě)的說(shuō)明本書(shū)基本結(jié)構(gòu)本書(shū)的基本結(jié)構(gòu)分為三個(gè)部分：第一部分：數(shù)據(jù)結(jié)構(gòu)的基本概念（第1章）。第二部分：基本的數(shù)據(jù)結(jié)構(gòu)，包括：線性結(jié)構(gòu)——線性表、棧和佇列、串、數(shù)組與廣義表（第2~5章）；非線性結(jié)構(gòu)——樹(shù)、圖（第6、7章）。第三部分：基本技術(shù)，包括：查找技術(shù)與排序技術(shù)（第8、9、10章）。

線性表圖2.1線性表的邏輯結(jié)構(gòu)2.1線性表的概念及運(yùn)算2.1.1線性表的邏輯結(jié)構(gòu)

例如：英文字母表(A,B,…,Z)就是一個(gè)簡(jiǎn)單的線性表，表中的每一個(gè)英文字母是一個(gè)數(shù)據(jù)元素，每個(gè)元素之間存在唯一的順序關(guān)係，如在英文字母表字母B的前面是字母A，而字母B的後面是字母C。在較為複雜的線性表中，數(shù)據(jù)元素(dataelements

)可由若干資料項(xiàng)目組成，如學(xué)生成績(jī)表中，每個(gè)學(xué)生及其各科成績(jī)是一個(gè)數(shù)據(jù)元素，它由學(xué)號(hào)、姓名、各科成績(jī)及平均成績(jī)等資料項(xiàng)目(item)組成，常被稱為一個(gè)記錄(record)，含有大量記錄的線性表稱為檔(file)。數(shù)據(jù)對(duì)象（dataobject）是性質(zhì)相同的數(shù)據(jù)元素集合。表2-1車輛登記表

線性表(LinearList)是由n(n≥0)個(gè)類型相同的數(shù)據(jù)元素a1,a2,…，an組成的有限序列，記作（a1,a2,…，ai-1，ai，ai+1，…，an）。這裏的數(shù)據(jù)元素ai(1≤i≤n)只是一個(gè)抽象的符號(hào)，其具體含義在不同情況下可以不同，它既可以是原子類型，也可以是結(jié)構(gòu)類型但同一線性表中的數(shù)據(jù)元素必須屬於同一數(shù)據(jù)對(duì)象。此外，線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)係，即對(duì)於非空的線性表（a1,a2,…，ai-1,ai,ai+1,…,an），表中ai-1

領(lǐng)先於ai，稱ai-1

是ai的直接前驅(qū)，而稱ai是ai-1的直接後繼。除了第一個(gè)元素a1外，每個(gè)元素ai有且僅有一個(gè)被稱為其直接前驅(qū)的結(jié)點(diǎn)ai-1，除了最後一個(gè)元素an外，每個(gè)元素ai有且僅有一個(gè)被稱為其直接後繼的結(jié)點(diǎn)ai+1。線性表中元素的個(gè)數(shù)n被定義為線性表的長(zhǎng)度，n=0時(shí)稱為空表。

線性表的特點(diǎn)可概括如下：同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)ai必須屬於同一數(shù)據(jù)對(duì)象。有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長(zhǎng)度就是表中數(shù)據(jù)元素的個(gè)數(shù)。有序性：線性表中表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)係<ai,ai+1>。由此可看出，線性表是一種最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閿?shù)據(jù)元素之間是由一前驅(qū)一後繼的直觀有序的關(guān)係確定；線性表又是一種最常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榫仃?、?shù)組、字串、堆疊、佇列等都符合線性條件。2.1.2線性表的抽象數(shù)據(jù)類型定義ADTLinearList{

數(shù)據(jù)元素：D={ai|ai∈D0,i=1,2,…，n,n≥0，D0為某一數(shù)據(jù)對(duì)象}

關(guān)係：Ｓ＝｛<ai,ai+1>|ai,ai+1∈D0，i=1,2,…,n-1｝基本操作：（1）InitList（L）操作前提：L為未初始化線性表。操作結(jié)果：將L初始化為空表。（2）DestroyList(L)

操作前提：線性表L已存在。操作結(jié)果：將L銷毀。（3）ClearList(L)

操作前提：線性表L已存在。操作結(jié)果：將表L置為空表。（4）EmptyList（L）操作前提：線性表L已存在。操作結(jié)果：如果L為空表則返回真，否則返回假。

（5）ListLength（L）操作前提：線性表L已存在。操作結(jié)果：如果L為空表則返回0，否則返回表中的元素個(gè)數(shù)。（6）Locate(L,e)

操作前提：表L已存在，e為合法元素值。操作結(jié)果：如果L中存在元素e，則將“當(dāng)前指針”指向元素e所在位置並返回真，否則返回假。（7）GetData(L,i)

操作前提：表L存在，且i值合法，即1≤i≤ListLength（L）。操作結(jié)果：返回線性表L中第i個(gè)元素的值。

（8）InsList(L,i,e)

操作前提：表L已存在，e為合法元素值且1≤i≤ListLength(L)+1。操作結(jié)果：在L中第i個(gè)位置插入新的數(shù)據(jù)元素e，L的長(zhǎng)度加1。（9）DelList(L,i,&e)

操作前提：表L已存在且非空，1≤i≤ListLength(L)。操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，並用e返回其值，L的長(zhǎng)度減1。

}ADTLinearList

2.2線性表的順序存儲(chǔ)2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素，使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過(guò)數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)係來(lái)反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)係。採(cǎi)用順序存儲(chǔ)結(jié)構(gòu)的線性表通常稱為順序表。

假設(shè)線性表中有n個(gè)元素，每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為loc(a1)，則可以通過(guò)如下公式計(jì)算出第i個(gè)元素的地址loc(a-i)：

loc(ai)=loc(a1)+(i-1)×k

其中l(wèi)oc(a-1)稱為基地址。圖2.2順序表存儲(chǔ)示意圖

順序存儲(chǔ)結(jié)構(gòu)可以借助於高級(jí)程式設(shè)計(jì)語(yǔ)言中的一堆數(shù)組來(lái)表示，一維數(shù)組的下標(biāo)與元素線上性表中的序號(hào)相對(duì)應(yīng)。線性表的順序存儲(chǔ)結(jié)構(gòu)可用C語(yǔ)言定義如下：＃defineMAXSIZE=線性表可能達(dá)到的最大長(zhǎng)度typedefstruct

{

ElemTypeelem［MAXSIZE］；/*線性表佔(zhàn)用的數(shù)組空間*/

int last；/*記錄線性表中最後一個(gè)元素在數(shù)組elem［］中 的位置（下標(biāo)值），空表置為-1*/

}SeqList；2.2.2線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算1.查找操作線性表有兩種基本的查找運(yùn)算。按序號(hào)查找GetData(L,i):要求查找線性表L中第i個(gè)數(shù)據(jù)元素，其結(jié)果是L.elem［i-1］或L->elem［i-1］。按內(nèi)容查找Locate（L,e）:要求查找線性表L中與給定值e相等的數(shù)據(jù)元素，其結(jié)果是：若在表L中找到與e相等的元素，則返回該元素在表中的序號(hào)；若找不到，則返回一個(gè)“空序號(hào)”，如-1。查找運(yùn)算可採(cǎi)用順序查找法實(shí)現(xiàn)，即從第一個(gè)元素開(kāi)始，依次將表中元素與e相比較，若相等，則查找成功，返回該元素在表中的序號(hào)；若e與表中的所有元素都不相等，則查找失敗，返回“-1”。演算法描述：intLocate(SeqListL，ElemTypee)

/*在順序表L中依次存放著線性表中的元素，在表中查找與e相等的元素，若L［i］=e，則找到該元素，並返回i值，若找不到，則返回“-1”*/{i=0;/*i為掃描計(jì)數(shù)器，初值為0，即從第一個(gè)元素開(kāi)始比較*/

while((i<=L.last)&&(L.elem［i］!=e))/*順序掃描表，直到找到值為key 的元素,

i++; 或掃描到表尾而沒(méi)找到*/

if(i<=L.last)

return(i);/*若找到值為e的元素，則返回其序號(hào)*/

else

return(-1);/*若沒(méi)找到，則返回空序號(hào)*/

}【演算法2.1線性表的查找運(yùn)算】2.插入操作線性表的插入運(yùn)算是指在表的第i(1≤i≤n+1)個(gè)位置，插入一個(gè)新元素e，使長(zhǎng)度為n的線性表(e1，…，ei-1，ei，…，en)變成長(zhǎng)度為n+1的線性表（e1，…,ei-1，e，ei，…，en）。用順序表作為線性表的存儲(chǔ)結(jié)構(gòu)時(shí)，由於結(jié)點(diǎn)的物理順序必須和結(jié)點(diǎn)的邏輯順序保持一致，因此我們必須將原表中位置n，n-1，…，i上的結(jié)點(diǎn)，依次後移到位置n+1，n，…，i+1上，空出第i個(gè)位置，然後在該位置上插入新結(jié)點(diǎn)e。當(dāng)i=n+1時(shí)，是指線上性表的末尾插入結(jié)點(diǎn)，所以無(wú)需移動(dòng)結(jié)點(diǎn)，直接將e插入表的末尾即可。

例如：已知線性表(4,9,15,28,30,30,42,51,62)，需在第4個(gè)元素之前插入一個(gè)元素“21”，則需要將第9個(gè)位置到第4個(gè)位置的元素依次後移一個(gè)位置，然後將“21”插入到第4個(gè)位置，如圖2.3所示。請(qǐng)注意區(qū)分元素的序號(hào)和數(shù)組的下標(biāo)。圖2.3順序表中插入元素演算法實(shí)現(xiàn)：＃defineOK1

＃defineERROR0

intInsList(SeqList*L,inti,ElemTypee)

/*在順序表L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)元素e。插入前表長(zhǎng)n=L->last+1，

i的合法取值範(fàn)圍是1≤i≤L->last+2*/

{

intk;

if((i<1)||(i>L->last+2))/*首先判斷插入位置是否合法*/

{

printf(″插入位置i值不合法″)；

return(ERROR);

}if(L->last>=maxsize-1)

{

printf(″表已滿無(wú)法插入″)；

return(ERROR);

}

for(k=L->last;k>=i-1;k--)/*為插入元素而移動(dòng)位置*/

L->elem［k+1］=L->elem［k］;

L->elem［i-1］=e;/*在C語(yǔ)言數(shù)組中，第i個(gè)元素的下標(biāo)為i-1*/

L->last++;

return(OK);

}【演算法2.2線性表的插入運(yùn)算】

可以看出，當(dāng)i=L->last+2時(shí)，語(yǔ)句L->elem［k+1］=L->elem［k］將不會(huì)執(zhí)行，因?yàn)檗捜Φ慕K值大於初值，此時(shí)不需要移動(dòng)元素，可直接在表尾插入e。當(dāng)i=1時(shí)，語(yǔ)句L->elem［k+1］=L->elem［k］需執(zhí)行n次，即將表中已存在的n個(gè)元素依次後移一個(gè)位置才能將e插入。因此，語(yǔ)句L->elem［k+1］=L->elem［k］的頻度與插入位置i有關(guān)。3.刪除操作線性表的刪除運(yùn)算是指將表的第i(1≤i≤n)個(gè)元素刪去，使長(zhǎng)度為n的線性表(e1，…,ei-1，ei，ei+1，…，en)變成長(zhǎng)度為n-1的線性表(e1，…,ei-1，ei+1，…，en)。例如：線性表(4,9,15,21,28,30,30,42,51,62)刪除第5個(gè)元素，則需將第6個(gè)元素到第10個(gè)元素依次向前移動(dòng)一個(gè)位置，如圖2.4所示。圖2.4順序表中刪除元素演算法描述：intDelList(SeqList*L,inti,ElemType*e)

/*在順序表L中刪除第i個(gè)數(shù)據(jù)元素，並用指針參數(shù)e返回其值。i的合法取值為1≤i≤L.last+1*/

{

intk;

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

{

printf(″刪除位置不合法！″)；

return(ERROR);

}*e=L->elem［i-1］;/*將刪除的元素存放到e所指向的變數(shù)中*/

for(k=i;i<=L->last;k++)

L->elem［k-1］=L->elem［k］;/*將後面的元素依次前移*/

L->last--;

Return(OK);

}【演算法2.3線性表的刪除運(yùn)算】

與插入運(yùn)算類似，在順序表上實(shí)現(xiàn)刪除運(yùn)算也必須移動(dòng)結(jié)點(diǎn)，這樣才能反映出結(jié)點(diǎn)間的邏輯關(guān)係的變化。若i=L->last+1，則移位語(yǔ)句L->elem［k-1］=L->elem［k］不執(zhí)行，因?yàn)檗捜ψ償?shù)的初值大於終值，此時(shí)不需要移動(dòng)元素，僅將表長(zhǎng)度減1即可。顯然，刪除演算法中移位語(yǔ)句L->elem［k-1］=L->elem［k］的執(zhí)行頻度也與刪除位置i有關(guān)。

在順序表中插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)數(shù)據(jù)元素上。對(duì)於插入演算法而言，設(shè)Pi為在第i個(gè)元素之前插入元素的概率，並假設(shè)在任何位置上插入的概率相等，即Pi=1/(n+1),i=1,2,…，n+1。設(shè)Eins為在長(zhǎng)度為n的表中插入一元素所需移動(dòng)元素的平均次數(shù)，則同理，設(shè)Qi為刪除第i個(gè)元素的概率，並假設(shè)在任何位置上刪除的概率相等，即Qi=1/n,i=1,2,…，n。刪除一個(gè)元素所需移動(dòng)元素的平均次數(shù)Edel為

例2-1有兩個(gè)順序表LA和LB，其元素均為非遞減有序排列，編寫(xiě)一個(gè)演算法，將它們合併成一個(gè)順序表LC，要求LC也是非遞減有序排列。例如LA=(2,2,3),LB=(1,3,3,4),則LC=(1,2,2,3,3,3,4)。

演算法思想：設(shè)表LC是一個(gè)空表，為使LC也是非遞減有序排列，可設(shè)兩個(gè)指針i、j分別指向表LA和LB中的元素，若LA.elem［i］>LB.elem［j］，則當(dāng)前先將LB.elem［j］插入到表LC中;若LA.elem［i］≤LB.elem［j］，則當(dāng)前先將LA.elem［i］插入到表LC中，如此進(jìn)行下去，直到其中一個(gè)表被掃描完畢，然後再將未掃描完的表中剩餘的所有元素放到表LC中。voidmerge(SeqList*LA,SeqList*LB,SeqList*LC)

{

inti,j,k,l;

i=0;j=0;k=0;

while(i<=LA->last&&j<=LB->last)

if(LA->elem［i］<=LB->elem［j］)

{

LC->elem［k］=LA->elem［i］;

i++;k++;

}

else

{

LC->elem［k］=LB->elem［j］;

j++;k++;

}

while(i<=LA->last)/*當(dāng)表LA比表LB長(zhǎng)時(shí)，則將表LA餘下的元素賦給表LC*/

{

LC->elem［k］=LA->elem［i］;

i++;k++;

}

while(j<=LB->last)/*當(dāng)表LB比表LA長(zhǎng)時(shí)，則將表LB餘下的元素賦給表LC*/

{

LC->elem［k］=LB->elem［j］;

j++;k++;

}

LC->last=LA->last+LB->last;

}【演算法2.4線性表的合併運(yùn)算】由上面的討論可知，線性表順序表示的優(yōu)點(diǎn)是：(1）無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)係而增加額外的存儲(chǔ)空間（因?yàn)檫壿嬌舷噜彽脑仄浯鎯?chǔ)的物理位置也是相鄰的）；(2）可方便地隨機(jī)存取表中的任一元素。其缺點(diǎn)是：(1）插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其他位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低；(2)由於順序表要求佔(zhàn)用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配，因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。若按可能達(dá)到的最大長(zhǎng)度預(yù)先分配表空間，則可能造成一部分空間長(zhǎng)期閒置而得不到充分利用；若事先對(duì)表長(zhǎng)估計(jì)不足，則插入操作可能使表長(zhǎng)超過(guò)預(yù)先分配的空間而造成溢出。2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.3.1單鏈表

圖2.5單鏈表的結(jié)點(diǎn)結(jié)構(gòu)

單鏈表包括兩個(gè)域：數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的值；指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接後繼的地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起。由於鏈表的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，故將這種鏈表又稱為單鏈表。由於單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)的指針域中的，而第一個(gè)結(jié)點(diǎn)無(wú)前趨，因而應(yīng)設(shè)一個(gè)頭指針H指向第一個(gè)結(jié)點(diǎn)。同時(shí)，由於表中最後一個(gè)結(jié)點(diǎn)沒(méi)有直接後繼，則指定線性表中最後一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡保∟ULL）。這樣對(duì)於整個(gè)鏈表的存取必須從頭指針開(kāi)始。

例如：圖2.6所示為線性表（A,B,C,D,E,F,G,H）的單鏈表存儲(chǔ)結(jié)構(gòu)，整個(gè)鏈表的存取需從頭指針開(kāi)始進(jìn)行，依次順著每個(gè)結(jié)點(diǎn)的指針域找到線性表的各個(gè)元素。圖2.6單鏈表的示例圖圖2.7單鏈表的邏輯狀態(tài)圖2.8帶頭結(jié)點(diǎn)單鏈表圖示單鏈表可以由頭指針唯一確定。單鏈表的存儲(chǔ)結(jié)構(gòu)描述如下：typedefstructNode/*結(jié)點(diǎn)類型定義*/

{ElemTypedata；structNode*next；}Node,*LinkList；/*LinkList為結(jié)構(gòu)指針類型*/假設(shè)L是LinkList型的變數(shù)，則L是一個(gè)結(jié)構(gòu)指針，即單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)（對(duì)於帶頭結(jié)點(diǎn)的單鏈表，則指向單鏈表的頭結(jié)點(diǎn)），若L=NULL（對(duì)於帶頭結(jié)點(diǎn)的單鏈表為L(zhǎng)->next=NULL），則表示單鏈表為一個(gè)空表，其長(zhǎng)度為0。若不是空表，則可以通過(guò)頭指針訪問(wèn)表中結(jié)點(diǎn)，找到要訪問(wèn)的所有結(jié)點(diǎn)的數(shù)據(jù)資訊。對(duì)於帶頭結(jié)點(diǎn)的單鏈表L，p=L->next指向表中的第一個(gè)結(jié)點(diǎn)a1，即p->data=a1，而p->next->data=a2。其餘依此類推。2.3.2單鏈表上的基本運(yùn)算1.建立單鏈表圖2.9頭插法建立單鏈表圖示用頭插法建立單鏈表的演算法：LinklistCreateFromHead()

{

LinkListL;

Node*s;

charc;

intflag=1;

/*設(shè)置一個(gè)標(biāo)誌變數(shù)flag，初值為1，當(dāng)輸入“$”時(shí)，將flag置為0， 建表結(jié)束*/

L=(Linklist)malloc(sizeof(Node));/*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/

L->next=NULL;

While(flag)

{

c=getchar();

if(c!=′$′)

{

s=(Node*)malloc(sizeof(Node));/*為讀入的字元分配存儲(chǔ)空間*/

s->data=c;

s->next=L->next;

L->next=s;

}

elseflag=0;

}

returnL;=}【演算法2.5用頭插法建立單鏈表】2）尾插法建表圖2.10尾插法建表圖示

該演算法的實(shí)現(xiàn)與頭插法建表的不同之處在於指針的變化，其具體實(shí)現(xiàn)如下：LinklistCreateFromTail()

{/*將新增的字元追加到鏈表的末尾*/

LinkListL;

Node*r,*s;

intflag=1;/*設(shè)置一個(gè)標(biāo)誌，初值為1，當(dāng)輸入“$”時(shí)，flag為0，建 表結(jié)束*/

L=(Node*)malloc(sizeof(Node));/*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/

L->next=NULL;

r=L;/*r指針始終動(dòng)態(tài)指向鏈表的當(dāng)前表尾，以便於做尾插入， 其初值指向頭結(jié)點(diǎn)*/

while(flag)

{c=getchar();

if(c!=′$′)

{

s=(Node*)malloc(sizeof(Node));

s->data=c;

r->next=s;

r=s；

}

else

{

flag=0;

r->next=NULL;/*將最後一個(gè)結(jié)點(diǎn)的next鏈域置為空，表示鏈表 的結(jié)束*/

}

}/*while*/

returnL;

}/*CreateFromTail*/【演算法2.6尾插法建表】2.查找

1）按序號(hào)查找在單鏈表中，由於每個(gè)結(jié)點(diǎn)的存儲(chǔ)位置都放在其前一結(jié)點(diǎn)的next域中，因而即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能像順序表那樣直接按序號(hào)i訪問(wèn)一維數(shù)組中的相應(yīng)元素，實(shí)現(xiàn)隨機(jī)存取，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。

演算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點(diǎn)（L->next）開(kāi)始順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn),初值指向頭結(jié)點(diǎn)，用j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過(guò)的結(jié)點(diǎn)數(shù)（初值為0），當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。Node*Get(LinkListL,inti)

/*在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)，若找到(1≤i≤n)，則返回該結(jié)點(diǎn)的存儲(chǔ)位置;*/

/*否則返回NULL*/

{intj；

Node*p；

p=L；j=0；/*從頭結(jié)點(diǎn)開(kāi)始掃描*/

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

{p=p->next；/*掃描下一結(jié)點(diǎn)*/

j++；/*已掃描結(jié)點(diǎn)計(jì)數(shù)器*/

}

if（i==j）returnp；/*找到了第i個(gè)結(jié)點(diǎn)*/

elsereturnNULL；/*找不到，i≤0或i>n*/

}/*Get*/【演算法2.7在單鏈表L中查找第i個(gè)結(jié)點(diǎn)】2)按值查找演算法描述：按值查找是指在單鏈表中查找是否有結(jié)點(diǎn)值等於e的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。Node*Locate(LinkListL,ElemTypekey)

/*在帶頭結(jié)點(diǎn)的單鏈表L中查找其結(jié)點(diǎn)值等於key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p；否則返回NULL*/

{Node*p;

p=L->next;/*從表中第一個(gè)結(jié)點(diǎn)比較*/

while(p![KG-*2]=NULL)

if(p->data![KG-*2]=key)

p=p->next;

elsebreak;/*找到結(jié)點(diǎn)key，退出迴圈*/

returnp;

}/*Locate*/【演算法2.8在單鏈表L中查找值等於key的結(jié)點(diǎn)】3.單鏈表插入操作演算法描述：要在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入一個(gè)數(shù)據(jù)元素e，需要首先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)並由指針pre指示，然後申請(qǐng)一個(gè)新的結(jié)點(diǎn)並由指針s指示，其數(shù)據(jù)域的值為e，並修改第i-1個(gè)結(jié)點(diǎn)的指針使其指向s，然後使s結(jié)點(diǎn)的指針域指向原第i個(gè)結(jié)點(diǎn)。插入結(jié)點(diǎn)的過(guò)程如圖2.11所示。intInsList(LinkListL,inti,ElemTypee)

{/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)*/

Node*pre,*s;

intk;

pre=L;k=0;

while(pre![KG-*2]=NULL&&k<i-1)

/*在第i個(gè)元素之前插入，則先找到第i-1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置,使指針pre指向它*/

{pre=pre->next;

k=k+1;

}if(k!=i-1)

/*即while迴圈是因?yàn)閜re=NULL或i<1而跳出的，所以一定是插入位置不合理所致*/

{printf(″插入位置不合理！″)；

returnERROR;

}

s=(Node*)malloc(sizeof(Node));/*為e申請(qǐng)一個(gè)新的結(jié)點(diǎn)並由s指向它*/s->data=e;/*將待插入結(jié)點(diǎn)的值e賦給s的數(shù)據(jù)域*/

s->next=pre->next;/*完成插入操作*/

pre->next=s;

returnOK;

}【演算法2.9單鏈表插入操作】圖2.11在單鏈表第i個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)的過(guò)程4.刪除圖2.12單鏈表的刪除過(guò)程intDelList(LinkListL,inti,ElemType*e)

/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，並將刪除的元素保存到變數(shù)*e中*/

{

Node*p,*r;

intk;

p=L;k=0;

while(p->next![KG-*2]=NULL&&k<i-1)

/*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1使p指向它*/

{p=p->next;

k=k+1;〖ZK)〗

}if(k!=i-1)/*即while迴圈是因?yàn)閜->next=NULL或i<1而跳出的*/

{

printf(″刪除結(jié)點(diǎn)的位置i不合理！″);

returnERROR;

}

r=p->next;

p->next=p->next->next;/*刪除結(jié)點(diǎn)r*/

free(r);/*釋放被刪除的結(jié)點(diǎn)所占的記憶體空間*/

returnOK;

}【演算法2.10單鏈表刪除操作】

說(shuō)明：刪除演算法中的迴圈條件（p->next!=NULL&&k<i-1）與前插演算法中的迴圈條件（p!=NULL&&k<i-1）不同，因?yàn)榍安鍟r(shí)的插入位置有m+1個(gè)（m為當(dāng)前單鏈表中數(shù)據(jù)元素的個(gè)數(shù)）。i=m+1是指在第m+1個(gè)位置前插入，即在單鏈表的末尾插入。而刪除操作中刪除的合法位置只有m個(gè)，若使用與前插操作相同的迴圈條件，則會(huì)出現(xiàn)指針指空的情況，使刪除操作失敗。

例2-2編寫(xiě)一個(gè)演算法，求單鏈表的長(zhǎng)度。演算法描述：可以採(cǎi)用“數(shù)”結(jié)點(diǎn)的方法來(lái)求出單鏈表的長(zhǎng)度，用指針p依次指向各個(gè)結(jié)點(diǎn),從第一個(gè)元素開(kāi)始“數(shù)”，一直“數(shù)”到最後一個(gè)結(jié)點(diǎn)（p->next=NULL）。intListLength(LinkListL)

/*本演算法用來(lái)求帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度*/

{Node*p;

p=L->next;

j=0;/*用來(lái)存放單鏈表的長(zhǎng)度*/

while(p![KG-*2]=NULL)

{p=p->next;

j++;

}

returnj;

}/*EndoffunctionListLength*/【演算法2.11求單鏈表的長(zhǎng)度】

例2-3如果以單鏈表表示集合，假設(shè)集合A用單鏈表LA表示，集合B用單鏈表LB表示，設(shè)計(jì)演算法求兩個(gè)集合的差，即A-B。演算法思想：由集合運(yùn)算的規(guī)則可知，集合的差A(yù)-B中包含所有屬於集合A而不屬於集合B的元素。具體做法是，對(duì)於集合A中的每個(gè)元素e，在集合B的鏈表LB中進(jìn)行查找，若存在與e相同的元素，則從LA中將其刪除。voidDifference(LinkListLA,LinkListLB)

{/*此演算法求兩個(gè)集合的差集*/

Node*pre;*p,*r;

pre=LA;p=LA->next;/*p指向LA表中的某一結(jié)點(diǎn)，而pre始終指向p 的前驅(qū)*/while(p!=NULL)

{

q=LB->next;

/*依次掃描LB中的結(jié)點(diǎn)，看是否有與LA中*p結(jié)點(diǎn)的值相同的結(jié)點(diǎn)*/while(q!=NULL&&q->data!=p->data)q=q->next;

if(q![KG-*2]=NULL)

{

r=p;

pre->next=p->next;

p=p->next;

free(r);

}

else

{

pre=p;p=p->next;

}

}/*while(p!=NULL)*/

}【演算法2.12用單鏈表求兩個(gè)集合的差集】2.3.3迴圈鏈表

迴圈鏈表(CircularLinkedList)是單鏈表的另一種形式，它是一個(gè)首尾相接的鏈表。其特點(diǎn)是將單鏈表最後一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就