數(shù)據(jù)結構C語言描述課件

緒論

1.1什麼是數(shù)據(jù)結構（定義）1.數(shù)據(jù)（Data）數(shù)據(jù)是描述客觀事物的數(shù)值、字元以及能輸入機器且能被處理的各種符號集合。換句話說，數(shù)據(jù)是對客觀事物採用電腦能夠識別、存儲和處理的形式所進行的描述。簡而言之，數(shù)據(jù)就是電腦化的資訊。

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

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

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

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

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

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

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

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

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

數(shù)學模型→抽象數(shù)據(jù)類型→數(shù)據(jù)結構，恰好反應了資訊結構轉換的三個重要階段，而在這個轉換過程中，數(shù)據(jù)結構是基礎，抽象數(shù)據(jù)類型是中樞。一個線性表的抽象數(shù)據(jù)類型的描述如下：

ADTLinear

-list

數(shù)據(jù)元素所有ai屬於同一數(shù)據(jù)對象，i=1，2，…，n,n≥0；邏輯結構所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關係<ai，ai+1>，ai無前趨，an無後繼；操作 設L為Linear-list:

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

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

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

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

Delete(L,i):刪除線性表的第i個元素。３）抽象數(shù)據(jù)類型實現(xiàn)第一種情況：傳統(tǒng)的面向過程的程式設計。第二種情況：“包”、“模型”的設計方法。第三種情況：面向對象的程式設計（ObjectOriented Programming，簡稱OOP）。４）ADT的表示與實現(xiàn)

ADT的定義

ADT的定義格式不唯一,我們採用下述格式定義一個ADT:

ADT<ADT名>

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

結構關係:<結構關係的定義>

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

}ADT<ADT名>其中數(shù)據(jù)對象和結構關係的定義採用數(shù)學符號和自然語言描述,而基本操作的定義格式為:

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

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

操作結果:<操作結果描述>

關於參數(shù)傳遞

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

用標準C語言表示和實現(xiàn)ADT描述時，主要包括以下兩個方面:

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

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

５）面向對象的概念

Coad和Yourdon給出面向對象的概念：面向對象=對象+類+繼承+通信

對象：是指在應用問題中出現(xiàn)的各種實體、事件和規(guī)格說明等，它是由一組屬性和在這組值上的一組服務構成的，其中屬性值確定了對象的狀態(tài)。類：把具有相同屬性和服務的對象歸到同一類,而把一個類中的每一個對象稱為該類的一個實例,它們具有相同的服務。繼承：面向對象方法的最有特色的方面。

面向對象程式設計語言的特點是不僅具有封裝性（encapsulation）,還有繼承性(inheritance)和多態(tài)性(polymorphism)。從以上的討論中可以看出，與數(shù)據(jù)結構密切相關的是定義在數(shù)據(jù)結構上的一組操作。操作的種類和數(shù)目不同，即使邏輯結構相同，這個數(shù)據(jù)結構的用途也會大不相同。定義在數(shù)據(jù)結構上的操作的種類是沒有限制的，可以根據(jù)具體需要而定義。

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

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

(2)刪除：刪去數(shù)據(jù)結構中某個指定數(shù)據(jù)元素；

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

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

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

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

(2)線性結構：結構中的數(shù)據(jù)元素之間存在著一對一的線性關係。

(3)樹形結構：結構中的數(shù)據(jù)元素之間存在著一對多的層次關係。

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

邏輯結構與存儲結構的關係為：存儲結構是邏輯關係的映象與元素本身的映象。邏輯結構是數(shù)據(jù)結構的抽象，存儲結構是數(shù)據(jù)結構的實現(xiàn)，兩者綜合起來建立了數(shù)據(jù)元素之間的結構關係?！鲰樞蛴诚螅樞虼鎯Y構）

■非順序映象（非順序存儲結構）3.運算集合表1-2工資表

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

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

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

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

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

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

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

１）演算法的正確性

(1)所設計的程式?jīng)]有語法錯誤；

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

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

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

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

{scanf(″%f″,x);

if(x>max)max=x;

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

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

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

(3)程式是演算法在電腦中的實現(xiàn)（與所用電腦及所用語言有關）。2.設計實現(xiàn)演算法過程的步驟

·

找出與求解有關的數(shù)據(jù)元素之間的關係（建立結構關係）。

·

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

·

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

·

選擇描述演算法的語言。

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

＃defineFALSE0

＃defineMAXSIZE100

＃defineOK1

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

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

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

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

■簡單賦值;

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

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

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

■成組賦值#;

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

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

■條件賦值;

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

(4)條件選擇語句。

■if（〈運算式〉）語句；

■if（〈運算式〉）語句1；

else語句2；switch(<運算式>）

{case判斷值1:

語句組1；

break;

case判斷值2:

語句組2；

break;

...

case判斷值n:

語句組n;

break;

［default:

語句組；

break;］

}(5)迴圈語句。

for語句

for(<運算式1>；<運算式2>；<運算式3>）

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

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

while(<條件運算式>）

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

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

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

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

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

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

②break語句：可用在迴圈語句或case語句中結束迴圈過程或跳出情況語句。

③continue語句：可用在迴圈語句中結束本次迴圈過程，進入下一次迴圈過程。

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

/*字串*/

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

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

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

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

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

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

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

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

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

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

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

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

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

{將a中整數(shù)數(shù)組重新排序，達到遞增有序}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）演算法的空間複雜度關於演算法的存儲空間需求，類似於演算法的時間複雜度，我們採用空間複雜度作為演算法所需存儲空間的量度，記作：S(n)=O(f(n))1.6關於學習數(shù)據(jù)結構1.數(shù)據(jù)結構課程的地位

圖1.7數(shù)據(jù)結構與其它課程的關係2.“數(shù)據(jù)結構”課程的學習特點

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

線性表圖2.1線性表的邏輯結構2.1線性表的概念及運算2.1.1線性表的邏輯結構

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

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

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

領先於ai，稱ai-1

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

線性表的特點可概括如下：同一性：線性表由同類數(shù)據(jù)元素組成，每一個ai必須屬於同一數(shù)據(jù)對象。有窮性：線性表由有限個數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個數(shù)。有序性：線性表中表中相鄰數(shù)據(jù)元素之間存在著序偶關係<ai,ai+1>。由此可看出，線性表是一種最簡單的數(shù)據(jù)結構，因為數(shù)據(jù)元素之間是由一前驅一後繼的直觀有序的關係確定；線性表又是一種最常見的數(shù)據(jù)結構，因為矩陣、數(shù)組、字串、堆疊、佇列等都符合線性條件。2.1.2線性表的抽象數(shù)據(jù)類型定義ADTLinearList{

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

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

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

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

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

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

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

（8）InsList(L,i,e)

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

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

}ADTLinearList

2.2線性表的順序存儲2.2.1線性表的順序存儲結構

線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關係來反映數(shù)據(jù)元素之間邏輯上的相鄰關係。採用順序存儲結構的線性表通常稱為順序表。

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

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

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

順序存儲結構可以借助於高級程式設計語言中的一堆數(shù)組來表示，一維數(shù)組的下標與元素線上性表中的序號相對應。線性表的順序存儲結構可用C語言定義如下：＃defineMAXSIZE=線性表可能達到的最大長度typedefstruct

{

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

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

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

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

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

i++; 或掃描到表尾而沒找到*/

if(i<=L.last)

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

else

return(-1);/*若沒找到，則返回空序號*/

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

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

＃defineERROR0

intInsList(SeqList*L,inti,ElemTypee)

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

i的合法取值範圍是1≤i≤L->last+2*/

{

intk;

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

{

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

return(ERROR);

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

{

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

return(ERROR);

}

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

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

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

L->last++;

return(OK);

}【演算法2.2線性表的插入運算】

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

/*在順序表L中刪除第i個數(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線性表的刪除運算】

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

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

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

演算法思想：設表LC是一個空表，為使LC也是非遞減有序排列，可設兩個指針i、j分別指向表LA和LB中的元素，若LA.elem［i］>LB.elem［j］，則當前先將LB.elem［j］插入到表LC中;若LA.elem［i］≤LB.elem［j］，則當前先將LA.elem［i］插入到表LC中，如此進行下去，直到其中一個表被掃描完畢，然後再將未掃描完的表中剩餘的所有元素放到表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)/*當表LA比表LB長時，則將表LA餘下的元素賦給表LC*/

{

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

i++;k++;

}

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

{

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

j++;k++;

}

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

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

圖2.5單鏈表的結點結構

單鏈表包括兩個域：數(shù)據(jù)域用來存儲結點的值；指針域用來存儲數(shù)據(jù)元素的直接後繼的地址（或位置）。鏈表正是通過每個結點的指針域將線性表的n個結點按其邏輯順序鏈接在一起。由於鏈表的每個結點只有一個指針域，故將這種鏈表又稱為單鏈表。由於單鏈表中每個結點的存儲地址是存放在其前趨結點的指針域中的，而第一個結點無前趨，因而應設一個頭指針H指向第一個結點。同時，由於表中最後一個結點沒有直接後繼，則指定線性表中最後一個結點的指針域為“空”（NULL）。這樣對於整個鏈表的存取必須從頭指針開始。

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

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

{

LinkListL;

Node*s;

charc;

intflag=1;

/*設置一個標誌變數(shù)flag，初值為1，當輸入“$”時，將flag置為0， 建表結束*/

L=(Linklist)malloc(sizeof(Node));/*為頭結點分配存儲空間*/

L->next=NULL;

While(flag)

{

c=getchar();

if(c!=′$′)

{

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

s->data=c;

s->next=L->next;

L->next=s;

}

elseflag=0;

}

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

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

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

LinkListL;

Node*r,*s;

intflag=1;/*設置一個標誌，初值為1，當輸入“$”時，flag為0，建 表結束*/

L=(Node*)malloc(sizeof(Node));/*為頭結點分配存儲空間*/

L->next=NULL;

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

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;/*將最後一個結點的next鏈域置為空，表示鏈表 的結束*/

}

}/*while*/

returnL;

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

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

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

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

/*否則返回NULL*/

{intj；

Node*p；

p=L；j=0；/*從頭結點開始掃描*/

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

{p=p->next；/*掃描下一結點*/

j++；/*已掃描結點計數(shù)器*/

}

if（i==j）returnp；/*找到了第i個結點*/

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

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

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

{Node*p;

p=L->next;/*從表中第一個結點比較*/

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

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

p=p->next;

elsebreak;/*找到結點key，退出迴圈*/

returnp;

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

{/*在帶頭結點的單鏈表L中第i個位置插入值為e的新結點*/

Node*pre,*s;

intk;

pre=L;k=0;

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

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

{pre=pre->next;

k=k+1;

}if(k!=i-1)

/*即while迴圈是因為pre=NULL或i<1而跳出的，所以一定是插入位置不合理所致*/

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

returnERROR;

}

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

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

pre->next=s;

returnOK;

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

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

{

Node*p,*r;

intk;

p=L;k=0;

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

/*尋找被刪除結點i的前驅結點i-1使p指向它*/

{p=p->next;

k=k+1;〖ZK)〗

}if(k!=i-1)/*即while迴圈是因為p->next=NULL或i<1而跳出的*/

{

printf(″刪除結點的位置i不合理！″);

returnERROR;

}

r=p->next;

p->next=p->next->next;/*刪除結點r*/

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

returnOK;

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

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

例2-2編寫一個演算法，求單鏈表的長度。演算法描述：可以採用“數(shù)”結點的方法來求出單鏈表的長度，用指針p依次指向各個結點,從第一個元素開始“數(shù)”，一直“數(shù)”到最後一個結點（p->next=NULL）。intListLength(LinkListL)

/*本演算法用來求帶頭結點的單鏈表L的長度*/

{Node*p;

p=L->next;

j=0;/*用來存放單鏈表的長度*/

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

{p=p->next;

j++;

}

returnj;

}/*EndoffunctionListLength*/【演算法2.11求單鏈表的長度】

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

{/*此演算法求兩個集合的差集*/

Node*pre;*p,*r;

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

{

q=LB->next;

/*依次掃描LB中的結點，看是否有與LA中*p結點的值相同的結點*/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用單鏈表求兩個集合的差集】2.3.3迴圈鏈表

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