數(shù)據(jù)結(jié)構(gòu)課件

2003-8-14

1

緒論1.6

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1.1

什么是數(shù)據(jù)結(jié)構(gòu)(定義)

1.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容（研究范圍）1.3

算法

1.4

算法描述的工具

1.5

對(duì)算法作性能評(píng)價(jià)

2003-8-14

2

1.1什么是數(shù)據(jù)結(jié)構(gòu)（定義）

數(shù)據(jù)結(jié)構(gòu)的相關(guān)名詞：數(shù)據(jù)（Data）

數(shù)據(jù)元素（DataElement）數(shù)據(jù)對(duì)象（DataObject）數(shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)類型(DataType)數(shù)據(jù)抽象與抽象數(shù)據(jù)類型

2003-8-14

3

數(shù)據(jù)（Data）定義：

數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。C編譯程序源程序（.c）目標(biāo)程序（.obj）可執(zhí)行程序（.exe）C鏈接程序例如對(duì)C源程序2003-8-14

4

數(shù)據(jù)元素（DataElement）定義：

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：..................北京

1983.11

河北

女

趙虹玲

101住

址

出生年月

籍

貫

性

別

姓

名

學(xué)

號(hào)

數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)2003-8-14

5

數(shù)據(jù)對(duì)象（DataObject）

定義：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。整數(shù)集合：N={0，±1，±2，…}無限集

字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集

例如：2003-8-14

6

數(shù)據(jù)結(jié)構(gòu)（DataStructure）

定義：

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。

例如表結(jié)構(gòu)：

..................北京

1983.11

河北

女

趙虹玲

101住

址

出生年月

籍

貫

性

別

姓

名

學(xué)

號(hào)

2003-8-14

7

數(shù)據(jù)結(jié)構(gòu)（DataStructure）樹型結(jié)構(gòu)

圖結(jié)構(gòu)125432003-8-14

8

數(shù)據(jù)類型(DataType)

定義：

數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。

如在高級(jí)語(yǔ)言中，整型類型的取值范圍為：-32768~+32767，運(yùn)算符集合為加、減、乘、除、取模，即+、-、*、/、%。2003-8-14

9

數(shù)據(jù)類型(DataType)高級(jí)語(yǔ)言中的數(shù)據(jù)類型分為兩大類：1.原子類型，其值不可分解。如C語(yǔ)言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。

2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。指針類型屬于哪種類型？2003-8-14

10

數(shù)據(jù)抽象與抽象數(shù)據(jù)類型數(shù)據(jù)的抽象

抽象數(shù)據(jù)類型(AbstractDataType)抽象數(shù)據(jù)類型實(shí)現(xiàn)

ADT的表示與實(shí)現(xiàn)

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

結(jié)構(gòu)化的開發(fā)方法與面向?qū)ο箝_發(fā)方法不同點(diǎn)

2003-8-14

11

數(shù)據(jù)的抽象匯編語(yǔ)言中十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等,它們是二進(jìn)制數(shù)據(jù)的抽象;高級(jí)語(yǔ)言中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，還可以進(jìn)一步定義更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。2003-8-14

12

抽象數(shù)據(jù)類型(AbstractDataType)定義：

抽象數(shù)據(jù)類型（簡(jiǎn)稱ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過程隱藏起來。數(shù)學(xué)模型抽象數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)非形式算法偽語(yǔ)言程序可執(zhí)行程序用抽象數(shù)據(jù)類型的概念來指導(dǎo)問題的求解過程：2003-8-14

13

抽象數(shù)據(jù)類型(AbstractDataType)線性表的抽象數(shù)據(jù)類型的描述：ADTLinear_list

數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對(duì)象，i=1，2，……，nn≥0；

邏輯結(jié)構(gòu)所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關(guān)系

<ai，ai+1>，ai無前趨，an無后繼；

操作設(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è)元素；2003-8-14

14

抽象數(shù)據(jù)類型實(shí)現(xiàn)

傳統(tǒng)的面向過程的程序設(shè)計(jì)實(shí)現(xiàn)的三種方法：“包”、“模型”的設(shè)計(jì)方法

面向?qū)ο蟮某绦蛟O(shè)計(jì)（ObjectOrientedProgramming，簡(jiǎn)稱OOP）2003-8-14

15

ADT的表示與實(shí)現(xiàn)

ADT的定義：

ADT<ADT名>

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

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

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

}ADT<ADT名>

基本操作的定義格式為：<操作名稱>(參數(shù)表)操作前提:<操作前提描述>操作結(jié)果:<操作結(jié)果描述>2003-8-14

16

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

參數(shù)表中的參數(shù)有值參和變參兩種。用標(biāo)準(zhǔn)C語(yǔ)言表示和實(shí)現(xiàn)ADT描述時(shí)，主要有兩個(gè)方面：

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

一、通過結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。ADT的表示與實(shí)現(xiàn)

2003-8-14

17

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

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

面向?qū)ο?對(duì)象+類+繼承+通信對(duì)象：指在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等

。類：具有相同屬性和服務(wù)的對(duì)象

繼承：是面向?qū)ο蠓椒ǖ淖钣刑厣姆矫妗?/p>

2003-8-14

18

結(jié)構(gòu)化與面向?qū)ο箝_發(fā)方法的不同點(diǎn)結(jié)構(gòu)化的開發(fā)方法：是面向過程的開發(fā)方法，首先著眼于系統(tǒng)要實(shí)現(xiàn)的功能。面向?qū)ο蟮拈_發(fā)方法：首先著眼于應(yīng)用問題所涉及的對(duì)象，包括對(duì)象、對(duì)象屬性和要求的操作，從而建立對(duì)象結(jié)構(gòu)和為解決問題需要執(zhí)行的時(shí)間序列。

2003-8-14

19

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

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

運(yùn)算集合

2003-8-14

20

邏輯結(jié)構(gòu)定義：

數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系描述。形式化描述：

Data_Structure=（D,R）其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。

四類基本的結(jié)構(gòu)

集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)。

2003-8-14

21

集合結(jié)構(gòu)定義：

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

集合例如：2003-8-14

22

線性結(jié)構(gòu)定義：

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

例如：線性表2003-8-14

23

樹型結(jié)構(gòu)定義：

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

例如：

樹2003-8-14

24

圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

定義：

結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。

例如：

圖2003-8-14

25

綜上所述，數(shù)據(jù)的邏輯結(jié)構(gòu)可概括為：線性結(jié)構(gòu)——線性表、棧、隊(duì)、字符串

數(shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)——樹、圖邏輯結(jié)構(gòu)2003-8-14

26

存儲(chǔ)結(jié)構(gòu)

定義：

存儲(chǔ)結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(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。

2003-8-14

27

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系為：存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身映象，是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)；邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象。

數(shù)據(jù)元素之間關(guān)系在計(jì)算機(jī)中的表示方法：順序映象

（順序存儲(chǔ)結(jié)構(gòu)）

非順序映象（非順序存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)

2003-8-14

28

運(yùn)算集合例如工資表：編號(hào)姓名性別基本工資工齡工資應(yīng)扣工資實(shí)發(fā)工資100001張愛芬

女345．67

145．4530．00451．12

100002李林

男

445．90185．6045．00586．50100003劉

曉峰

男

345．00130．0025．00450．00100004趙

俊

女

560．90225．9065．00721．80100005孫

濤

男

450．60190．8050．00591．80…

…

…

…

…

…

…

100121張興強(qiáng)

男

1025．98

365．53100．001291.512003-8-14

29

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

綜上所述，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分，邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。

2003-8-14

30

1.3算法

算法（Algorithm）定義

算法的特性

算法設(shè)計(jì)的要求

2003-8-14

31

算法（Algorithm）定義定義：

Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.

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

2003-8-14

32

算法的特性1.有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)2.確定性：算法中的每一個(gè)步驟必須有確定含義，無二

義性得以實(shí)現(xiàn)。

3.輸

入：

有多個(gè)或0個(gè)輸入

4.輸

出：

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

5.可行性：原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)基本

運(yùn)算執(zhí)行有限次而完成。

2003-8-14

33

算法設(shè)計(jì)的要求

算法的正確性

算法特征：

可讀性

健壯性

高效率和低存儲(chǔ)量

例如要求n個(gè)數(shù)的最大值問題給出算法如下：

max:=0;for（i=1；i<=n;i++）

{scanf("%f",x);if(x>max)max=x;}2003-8-14

34

1.4算法描述的工具

概述：

算法+數(shù)據(jù)結(jié)構(gòu)=程序

算法、語(yǔ)言、程序的關(guān)系

設(shè)計(jì)實(shí)現(xiàn)算法過程步驟

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

2003-8-14

35

算法、語(yǔ)言、程序的關(guān)系1.算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）。2.描述算法的工具：算法可用自然語(yǔ)言、框圖或高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行描述。

3.程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。

2003-8-14

36

設(shè)計(jì)實(shí)現(xiàn)算法過程步驟

1.找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系2.確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算

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

4.選擇描述算法的語(yǔ)言5.設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語(yǔ)言加以描述。

2003-8-14

37

類描述算法的語(yǔ)言選擇類語(yǔ)言：

類語(yǔ)言是接近于高級(jí)語(yǔ)言而又不是嚴(yán)格的高級(jí)語(yǔ)言，具有高級(jí)語(yǔ)言的一般語(yǔ)句設(shè)施，撇掉語(yǔ)言中的細(xì)節(jié)，以便把注意力主要集中在算法處理步驟本身的描述上。2003-8-14

38

對(duì)C語(yǔ)言作以下描述：1.預(yù)定義常量和類型#defineTRUE1#defineFALSE0#defineMAXSIZE100#defineOK1#defineERROR02003-8-14

39

對(duì)C語(yǔ)言作以下描述：

[數(shù)據(jù)類型]函數(shù)名（[形式參數(shù)及說明]）{內(nèi)部數(shù)據(jù)說明；

執(zhí)行語(yǔ)句組；}/*函數(shù)名*/2.函數(shù)的表示形式：2003-8-14

40

3.賦值語(yǔ)句對(duì)C語(yǔ)言作以下描述：（1）簡(jiǎn)單賦值1）〈變量名〉=〈表達(dá)式〉

2）

〈變量〉++，

3）

〈變量〉--，（2）串聯(lián)賦值〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉

2003-8-14

41

對(duì)C語(yǔ)言作以下描述：（4）條件賦值〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉:〈表達(dá)式2〉

（3）成組賦值(<變量>,<變量2>,<變量3>,…<變量k〉=(<表達(dá)式1>,<表達(dá)式2>,<表達(dá)式3>,…<表達(dá)式k>)〈數(shù)組名1〉[下標(biāo)1][下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1][下標(biāo)2]

2003-8-14

42

4.條件選擇語(yǔ)句對(duì)C語(yǔ)言作以下描述：if(<表達(dá)式>)語(yǔ)句;if(<表達(dá)式>)語(yǔ)句1;else語(yǔ)句2;2003-8-14

43

情況語(yǔ)句switch(<表達(dá)式>）

{case判斷值1:

語(yǔ)句組

1；

break;case判斷值2:

語(yǔ)句組

2；

break;……

case判斷值n:

語(yǔ)句組n;break;[default:

語(yǔ)句組；

break;]}對(duì)C語(yǔ)言作以下描述：2003-8-14

44

對(duì)C語(yǔ)言作以下描述：5.循環(huán)語(yǔ)句for語(yǔ)句for(<表達(dá)式1>；<表達(dá)式2>；<表達(dá)式3>）{循環(huán)體語(yǔ)句；}2003-8-14

45

while語(yǔ)句while(<條件表達(dá)式>）

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

}對(duì)C語(yǔ)言作以下描述：do–while語(yǔ)句do{循環(huán)體語(yǔ)句

}while(<條件表達(dá)式>）

2003-8-14

46

對(duì)C語(yǔ)言作以下描述：6.輸入、輸出函數(shù)7.其它一些語(yǔ)句8.注釋語(yǔ)句9.一些基本的函數(shù)2003-8-14

47

1.5對(duì)算法作性能評(píng)價(jià)

評(píng)價(jià)算法的標(biāo)準(zhǔn)： 評(píng)價(jià)一個(gè)算法主要看這個(gè)算法所占用機(jī)器資源的多少，而這些資源中時(shí)間代價(jià)與空間代價(jià)是兩個(gè)主要的方面，通常是以算法執(zhí)行所需的機(jī)器時(shí)間和所占用的存儲(chǔ)空間來判斷一個(gè)算法的優(yōu)劣。

性能評(píng)價(jià)有關(guān)數(shù)量關(guān)系計(jì)算

2003-8-14

48

性能評(píng)價(jià)定義：

對(duì)問題規(guī)模與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。

問題規(guī)模N—對(duì)不同的問題其含義不同：

對(duì)矩陣是階數(shù)；

對(duì)多項(xiàng)式運(yùn)算是多項(xiàng)式項(xiàng)數(shù)；對(duì)圖是頂點(diǎn)個(gè)數(shù)；對(duì)集合運(yùn)算是集合中元素個(gè)數(shù)。2003-8-14

49

有關(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ǔ)量。關(guān)于算法執(zhí)行時(shí)間

語(yǔ)句頻度

算法的時(shí)間復(fù)雜度

數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)

最壞時(shí)間復(fù)雜度

算法的空間復(fù)雜度

2003-8-14

50

關(guān)于算法執(zhí)行時(shí)間定義：

一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。分析：

不是針對(duì)實(shí)際執(zhí)行時(shí)間的精確地算出算法執(zhí)行具體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。2003-8-14

51

語(yǔ)句頻度

定義： 語(yǔ)句頻度是指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。

例如：兩個(gè)矩陣相乘算法語(yǔ)句對(duì)應(yīng)的語(yǔ)句頻度

1 for（i=0；i<n;i++）n2 for（j=0；j<n;j++）n2

3{c[i][j]=0;n2

4for(k=0;k<n;k++)n3

c[i][j]=c[i][j]+a[i][k]*b[k][j];n3

}

總執(zhí)行次數(shù)：Tn=2n3+2n2+n2003-8-14

52

算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度，即是算法的時(shí)間量度記做：

T(n)=O(f(n))

例如給出X=X+1（1）x=x+1；時(shí)間復(fù)雜度為O(1)，稱為常量階；（2）for(i=1;i<=n;i++)x=x+1;時(shí)間復(fù)雜度為O(n)，稱為線性階；

（3）for(i=1;i<=n;i++) for(j=1;j<=n;j++)x=x+1;時(shí)間復(fù)雜度為O(n2),

稱為平方階。2003-8-14

53

常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)

數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè):

O(1)常數(shù)型

O(n)線性型

O(n2)平方型

O(n3)立方型

O(2n)指數(shù)型

O(log2n)對(duì)數(shù)型O(nlog2n)二維型

按時(shí)間復(fù)雜度由小到大排列的頻率表：

2003-8-14

54

常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)常用的時(shí)間復(fù)雜度頻率表：log2n

nnlog2nn2n3

2n

一般講：前3種可實(shí)現(xiàn)，后3種雖理論上是可實(shí)現(xiàn)的，實(shí)際上只有對(duì)N限制在很小范圍才有意義，當(dāng)N較大時(shí)，不可能實(shí)現(xiàn)。

0101121224842481664163824645122564166425650966553653216010243276821474836482003-8-14

55

最壞時(shí)間復(fù)雜度

定義：

討論算法在最壞情況下的時(shí)間復(fù)雜度，即分析最壞情況下以估計(jì)出算法執(zhí)行時(shí)間的上界。

例如冒泡排序算法

2003-8-14

56

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)}最壞時(shí)間復(fù)雜度

2003-8-14

57

算法的空間復(fù)雜度

定義：

用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記做：S(n)=O(f(n))

。2003-8-14

58

1.6關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)課程地位

數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)

關(guān)于本書內(nèi)容編寫說明

2003-8-14

59

數(shù)據(jù)結(jié)構(gòu)課程地位

數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫(kù)人工智能專業(yè)基礎(chǔ)課操作系統(tǒng)編譯原理非線性程序設(shè)計(jì)離散數(shù)學(xué)語(yǔ)言程序設(shè)計(jì)計(jì)算機(jī)原理設(shè)計(jì)2003-8-14

60

數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)教學(xué)目標(biāo)：學(xué)會(huì)分析數(shù)據(jù)對(duì)象的特征，掌握數(shù)據(jù)組織方法和計(jì)算機(jī)的表示方法，以便為應(yīng)用所涉及數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)算法，初步掌握算法時(shí)間空間分析的技巧，培養(yǎng)良好的程序設(shè)計(jì)技能。

學(xué)習(xí)方法：

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，必須經(jīng)過大量的實(shí)踐，在實(shí)踐中體會(huì)構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計(jì)的技術(shù)。

2003-8-14

61

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

2.1.2線性表的抽象數(shù)據(jù)類型定義

2003-8-14

62

線性表的定義線性表(LinearList)是由n(n≥0)個(gè)類型相同的數(shù)據(jù)元素a1,a2,…，an組成的有限序列，記做（a1,a2,…，ai-1，ai，ai+1，

…，an）。

數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，即每個(gè)數(shù)據(jù)元素最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性表的邏輯結(jié)構(gòu)圖為：

2003-8-14

63

線性表的特點(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>。

2003-8-14

64

2.1.2線性表的抽象數(shù)據(jù)類型定義抽象數(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置為空表。

………

}ADT

LinearList

2003-8-14

65

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

2.2.2線性表順序存儲(chǔ)結(jié)構(gòu)上的基本運(yùn)算

2003-8-14

66

順序存儲(chǔ)結(jié)構(gòu)的定義

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

假設(shè)線性表中每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為loc(a1)，則第k個(gè)元素的地址為：

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

67

順序存儲(chǔ)結(jié)構(gòu)示意圖

存儲(chǔ)地址

內(nèi)存空間狀態(tài)

邏輯地址

Loc(a1)a11Loc(a1)+(2-1)ka2

2…

…

…

loc(a1)+(i-1)kai

i…

…

…

loc(a1)+(n-1)kan

n...

loc(a1)+(maxlen-1)k

空閑2003-8-14

68

順序存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言定義#define maxsize=線性表可能達(dá)到的最大長(zhǎng)度；typedefstruct{ElemTypeelem[maxsize]；

/*線性表占用的數(shù)組空間*/intlast；

/*記錄線性表中最后一個(gè)元素在數(shù)組elem[]

中的位置（下標(biāo)值），空表置為-1*/}SeqList；

注意區(qū)分元素的序號(hào)和數(shù)組的下標(biāo)，如a1的序號(hào)為1，而其對(duì)應(yīng)的數(shù)組下標(biāo)為0。

2003-8-14

69

2.2.2線性表順序存儲(chǔ)結(jié)構(gòu)的基本運(yùn)算線性表的基本運(yùn)算：查找操作

插入操作

刪除操作

順序表合并算法

線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)分析

2003-8-14

70

查找操作線性表的兩種基本查找運(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)算算法描述為：

2003-8-14

71

線性表的查找運(yùn)算intLocate(SeqListL，ElemTypee){ i=0;/*i為掃描計(jì)數(shù)器，初值為0，即從第一個(gè)元素開始比較*/while((i<=L.last)&&(L.elem[i]!=e)

)i++;/*順序掃描表，直到找到值為key的元素,或掃描到表尾而沒找到*/if(i<=L.last)return(i);/*若找到值為e的元素，則返回其序號(hào)*/

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

2003-8-14

72

插入操作

線性表的插入運(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）。

線性表的插入運(yùn)算算法。2003-8-14

73

插入算法示意圖

已知：線性表

(4,9,15,28,30,30,42,51,62)，需在第4個(gè)元素之前插入一個(gè)元素“21”。則需要將第9個(gè)位置到第4個(gè)位置的元素依次后移一個(gè)位置，然后將“21”插入到第4個(gè)位置，

序號(hào)移動(dòng)元素插入元素12345678109491528303042516249152830304262514915212830304262512003-8-14

74

插入運(yùn)算intInsList(SeqList*L,inti,ElemTypee){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--)/*為插入元素而移動(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);}

算法演示（此處連接算法演示程序）。2003-8-14

75

刪除操作

線性表的刪除運(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)。

算法思路示意

算法實(shí)現(xiàn)

2003-8-14

76

刪除算法示意

將線性表(4,9,15,21,28,30,30,42,51,62)中的第5個(gè)元素刪除。

序號(hào)123456781094915212830304262514915213030425162刪除28后2003-8-14

77

刪除算法

intDelList(SeqList*L,inti,ElemType*e)/*在順序表L中刪除第i個(gè)數(shù)據(jù)元素，并用指針參數(shù)e返回其值*/{intk;if((i<1)||(i>L->last+1)){printf(“刪除位置不合法！”)；

return(ERROR)；

}*e=L->elem[i-1];

/*將刪除的元素存放到e所指向的變量中*/for(k=i;i<=L->last;k++)L->elem[k-1]=L->elem[k];/*將后面的元素依次前移*/L->last--;return(OK);}

2003-8-14

78

合并算法已知

：有兩個(gè)順序表LA和LB，其元素均為非遞減有序排列，編寫一個(gè)算法，將它們合并成一個(gè)順序表LC，要求LC也是非遞減有序排列。

算法思想：設(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中。算法實(shí)現(xiàn)

此處連接算法演示2003-8-14

79

順序表合并算法實(shí)現(xiàn)voidmerge(SeqList*LA,SeqList*LB,SeqList*LC){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長(zhǎng)則將表LA余下的元素賦給表LC*/

{

LC->elem[k]=LA->elem[i];

i++;k++;}while(j<=LB->last)/*當(dāng)表LB長(zhǎng)則將表LB余下的元素賦給表LC*/

{

LC->elem[k]=LB->elem[j];j++;k++;}

LC->last=LA->last+LB->last;}2003-8-14

80

順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：1.無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；

2.可方便地隨機(jī)存取表中的任一元素。

缺點(diǎn)：1.插入或刪除運(yùn)算不方便，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低；

2.由于順序表要求占用連續(xù)的存儲(chǔ)空間，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配。因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。

2003-8-14

81

2.3線性表的鏈?zhǔn)酱鎯?chǔ)鏈表定義：

采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表

?，F(xiàn)在我們從兩個(gè)角度來討論鏈表：1.從實(shí)現(xiàn)角度看，鏈表可分為動(dòng)態(tài)鏈表和靜態(tài)鏈表；2.從鏈接方式的角度看，鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表。

2003-8-14

82

2.3.1單鏈表

2.3.2單鏈表上的基本運(yùn)算

2.3.3循環(huán)鏈表

2.3.4雙向鏈表

*2.3.5靜態(tài)鏈表

2.3.6順序表和鏈表的比較

鏈表2003-8-14

83

2.3.1單鏈表

結(jié)點(diǎn)（Node）為了正確地表示結(jié)點(diǎn)間的邏輯關(guān)系，必須在存儲(chǔ)線性表的每個(gè)數(shù)據(jù)元素值的同時(shí)，存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這兩部分信息組成的存儲(chǔ)映象叫做結(jié)點(diǎn)（Node）。單鏈表：鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，我們將這種鏈表稱為單鏈表。

單鏈表包括兩個(gè)域：數(shù)據(jù)域用來存儲(chǔ)結(jié)點(diǎn)的值；指針域用來存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址（或位置）。頭指針

：指向鏈表頭結(jié)點(diǎn)的指針。2003-8-14

84

單鏈表的示例圖

頭指針H存儲(chǔ)地址數(shù)據(jù)域指針域1D437B1313C119HNULL25F3731A737G1943E25312003-8-14

85

帶頭結(jié)點(diǎn)的單鏈表示意圖有時(shí)為了操作的方便，還可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)。帶頭結(jié)點(diǎn)的空單鏈表

帶頭結(jié)點(diǎn)的單鏈表

∧

Ha1

a2

…

Han

∧

2003-8-14

86

單鏈表的存儲(chǔ)結(jié)構(gòu)描述

typedefstructNode/*結(jié)點(diǎn)類型定義*/{ElemTypedata；

structNode*next；}Node,*LinkList；/*LinkList為結(jié)構(gòu)指針類型*/

2003-8-14

87

2.3.2單鏈表上的基本運(yùn)算線性表的基本運(yùn)算：建立單鏈表

單鏈表查找

單鏈表插入操作

單鏈表刪除

算法應(yīng)用示例：求單鏈表的長(zhǎng)度

求兩個(gè)集合的差

2003-8-14

88

建立單鏈表

頭插法建表

算法描述：從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。c1∧

sL∧

L

ci-1∧

c2c1∧

cis…

c1∧

2003-8-14

89

頭插法建表算法

LinklistCreateFromHead(){LinkListL;Node*s;intflag=1;

/*設(shè)置一個(gè)標(biāo)志，初值為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!=’$’)/*為讀入的字符分配存儲(chǔ)空間*/{s=(Node*)malloc(sizeof(Node));s->data=c;s->next=L->next;L->next=s;}else

flag=0;}}

2003-8-14

90

尾插法建表

C1

∧

sr∧

Lc1rsc2∧Lc1∧rsL2003-8-14

91

尾插法建表算法

LinklistCreateFromTail()/*將新增的字符追加到鏈表的末尾*/{LinkListL;Node*r,*s;intflag=1;

L=(Node*)malloc(sizeof(Node));/*為頭結(jié)點(diǎn)分配存儲(chǔ)空間*/L->next=NULL;r=L;/*r指針始終動(dòng)態(tài)指向鏈表的當(dāng)前表尾*/

while(flag)/*標(biāo)志，初值為1。輸入“$”時(shí)flag為0，建表結(jié)束*/

{ c=getchar();

if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s}else{flag=0;r->next=NULL;}}}

2003-8-14

92

單鏈表查找

按序號(hào)查找

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

。算法實(shí)現(xiàn)，算法演示。

2003-8-14

93

按序號(hào)查找算法實(shí)現(xiàn)/*在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)，若找到(1≤i≤n)，則返回該結(jié)點(diǎn)的存儲(chǔ)位置;否則返回NULL*/Node*Get(LinkListL,inti){Node*p；

p=L；j=0；/*從頭結(jié)點(diǎn)開始掃描*/while((p->next!=NULL)&&(j<i){p=p->next；j++；/*掃描下一結(jié)點(diǎn)*/}/*已掃描結(jié)點(diǎn)計(jì)數(shù)器*/if（i==j）returnp；/*找到了第i個(gè)結(jié)點(diǎn)*/elsereturnNULL；/*找不到，i≤0或i>n*/}2003-8-14

94

按值查找

算法描述：按值查找是指在單鏈表中查找是否有結(jié)點(diǎn)值等于e的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為e的結(jié)點(diǎn)的存儲(chǔ)位置，否則返回NULL。查找過程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。算法實(shí)現(xiàn)，算法演示。單鏈表查找

2003-8-14

95

按值查找算法實(shí)現(xiàn)

/*在帶頭結(jié)點(diǎn)的單鏈表L中查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p，否則返回NULL*/Node*Locate(LinkListL,ElemTypekey){Node*p;p=L->next;/*從表中第一個(gè)結(jié)點(diǎn)比較*/while(p!=NULL)if(p->data!=key) p=p->next;elsebreak;/*找到結(jié)點(diǎn)key，退出循環(huán)*/returnp;}

2003-8-14

96

單鏈表插入操作

算法描述：

要在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)數(shù)據(jù)元素之前插入一個(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)。esa1

…

…

an∧

ai-1

ai

espreLa1

…

…

an∧

preai-1

ai

2003-8-14

97

單鏈表插入操作算法實(shí)現(xiàn)voidInsList(LinkListL,inti,ElemTypee){/*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)結(jié)點(diǎn)之前插入值為e的新結(jié)點(diǎn)。*/

Node*pre,*s;

pre=L;intk=0;while(pre!=NULL&&k<i-1)/*先找到第i-1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置,使指針Pre指向它*/

{pre=pre->next;

k=k+1;}if(k!=i-1){printf(“插入位置不合理！”)；return;}s=(Node*)malloc(sizeof(Node));/*為e申請(qǐng)一個(gè)新的結(jié)點(diǎn)*/s->data=e;/*將待插入結(jié)點(diǎn)的值e賦給s的數(shù)據(jù)域*/s->next=pre->next;pre->next=s;}

2003-8-14

98

單鏈表刪除

算法描述： 欲在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，則首先要通過計(jì)數(shù)方式找到第i-1個(gè)結(jié)點(diǎn)并使p指向第i-1個(gè)結(jié)點(diǎn)，而后刪除第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。

pa1

…

ai-1

ai

…

an∧

pa1

…

L…

an∧

ai-1

ai

ai+1

rL2003-8-14

99

單鏈表刪除算法實(shí)現(xiàn)voidDelList(LinkListL,inti,ElemType*e)/*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并保存其值到變量*e中*/{

Node*p,*r;p=L;intk=0;

while(p->next!=NULL&&k<i-1)/*尋找被刪除結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)*/{p=p->next;k=k+1;}if(k!=i-1)/*即while循環(huán)是因?yàn)閜->next=NULL而跳出的*/{printf(“刪除結(jié)點(diǎn)的位置i不合理！”);returnERROR;}r=p->next;p->next=p->next->next/*刪除結(jié)點(diǎn)r*/free(r);/*釋放被刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/}2003-8-14

100

求單鏈表的長(zhǎng)度

算法描述：可以采用“數(shù)”結(jié)點(diǎn)的方法來求出單鏈表的長(zhǎng)度，用指針p依次指向各個(gè)結(jié)點(diǎn),從第一個(gè)元素開始“數(shù)”，一直“數(shù)”到最后一個(gè)結(jié)點(diǎn)（p->next=NULL）。

int ListLength(LinkListL)/*L為帶頭結(jié)點(diǎn)的單鏈表*/{Node*p;p=L->next; j=0;/*用來存放單鏈表的長(zhǎng)度*/

while(p!=NULL)

{ p=p->next;j++;}

returnj;}算法演示鏈接。2003-8-14

101

求兩個(gè)集合的差

已知：以單鏈表表示集合，假設(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中將其刪除。算法實(shí)現(xiàn)

算法演示鏈接2003-8-14

102

求兩個(gè)集合的差算法實(shí)現(xiàn)

voidDifference(LinkListLA,LinkListLB)/*此算法求兩個(gè)集合的差集*/

{Node*pre;*p,*r;

pre=LA;p=LA->next;/*p向表中的某一結(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!=NULL)

{r=p;pre->next=p->next;p=p->next;free(r);}

else{pre=p;p=p->next;}}}

2003-8-14

103

2.3.3循環(huán)鏈表

循環(huán)鏈表(CircularLinkedList)

是一個(gè)首尾相接的鏈表。特點(diǎn)：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。

帶頭結(jié)點(diǎn)循環(huán)單鏈表示意圖。

2003-8-14

104

帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖

La1

…

…

ai-1

ai

anLa1

…

…

ai-1

ai

anrear*(rear->next)*rear空鏈表帶頭結(jié)點(diǎn)的一般形式

帶尾結(jié)點(diǎn)的一般形式

2003-8-14

105

循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表

已知：有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、LB，編寫一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為L(zhǎng)A。 算法思想：先找到兩個(gè)鏈表的尾，并分別由指針p、q指向它們，然后將第一個(gè)鏈表的尾與第二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來，并修改第二個(gè)表的尾Q，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。

2003-8-14

106

循環(huán)單鏈表合并算法實(shí)現(xiàn)

LinkListmerge_1(LinkListLA,LinkListLB)/*此算法將兩個(gè)鏈表的首尾連接起來*/{Node*p,*q;p=LA;q=LB;while(p->next!=LA)p=p->next; /*找到表LA的表尾*/while(q->next!=LB)q=q->next; /*找到表LB的表尾*/q->next=LA;/*修改表LB的尾指針，使之指向表LA的頭結(jié)點(diǎn)*/p->next=LB->next;/*修改表LA的尾指針，使之指向表LB中的第一個(gè)結(jié)點(diǎn)*/ free(LB);return(LA);}

2003-8-14

107

2.3.4雙向鏈表

雙向鏈表：在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前趨的指針域prior。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為雙

(向)鏈表

(DoubleLinkedList)。

雙向鏈表的結(jié)構(gòu)定義：

typedefstructDnode {ElemTypedata；

structDNode*prior，*next；

}DNode, *DoubleList；

2003-8-14

108

雙鏈表的結(jié)構(gòu)定義

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

后繼指針域priordatanext前驅(qū)指針域數(shù)據(jù)域2003-8-14

109

雙向循環(huán)鏈表示意圖

a1

a2

a3

LL空的雙向循環(huán)鏈表

非空的雙向循環(huán)鏈表

2003-8-14

110

雙向鏈表的前插操作

算法描述：欲在雙向鏈表第i個(gè)結(jié)點(diǎn)之前插入一個(gè)的新的結(jié)點(diǎn)，則指針的變化情況如圖所示。

es①

②③④…

bpa…

2003-8-14

111

雙向鏈表的前插操作算法實(shí)現(xiàn)

void

DlinkIns(DoubleListL,inti,ElemTypee)

{DNode*s,*p;

…/*首先檢查待插入的位置i是否合法*/

…/*若位置i合法，則讓指針p指向它*/

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

if(s)

{s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnTRUE;

}

else

returnFALSE;}

算法演示連接。2003-8-14

112

雙向鏈表的刪除操作

算法描述：欲刪除雙向鏈表中的第i個(gè)結(jié)點(diǎn)，則指針的變化情況如圖所示。

abcp②①…

…

2003-8-14

113

雙向鏈表的刪除操作算法實(shí)現(xiàn)

int

DlinkDel(DoubleListL,inti,ElemType*e)

{ DNode*p;

…/*首先檢查待插入的位置i是否合法*/

…/*若位置i合法，則讓指針p指向它*/

*e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

returnTRUE;

}2003-8-14

114

雙向鏈表應(yīng)用舉例已知：設(shè)一個(gè)循環(huán)雙鏈表L=（a,b,c,d）編寫一個(gè)算法將鏈表轉(zhuǎn)換為L(zhǎng)=（b,a,c,d）。算法思想：實(shí)際上是交換表中前兩個(gè)元素的次序。算法實(shí)現(xiàn)：void swap(DLinkListL){DNode*p,*q,*h;h=L->next; /*h指向表中的第一個(gè)結(jié)點(diǎn)，即a*/p=h->next; /*p指向b結(jié)點(diǎn)*/q=h->prior; /*保存a結(jié)點(diǎn)的前驅(qū)*/h->next=p->next;p->next->prior=h;/*變換指針指向*/p->prior=q;p->next=h;L->next=p; }

2003-8-14

115

*2.3.5靜態(tài)鏈表

基本概念：

游標(biāo)實(shí)現(xiàn)鏈表的方法：定義一個(gè)較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間（即存儲(chǔ)池）。當(dāng)申請(qǐng)結(jié)點(diǎn)時(shí)，每個(gè)結(jié)點(diǎn)應(yīng)含有兩個(gè)域：data域和next域。data域存放結(jié)點(diǎn)的數(shù)據(jù)信息，next域?yàn)橛螛?biāo)指示器，指示后繼結(jié)點(diǎn)在結(jié)構(gòu)數(shù)組中的相對(duì)位置（即數(shù)組下標(biāo)）。數(shù)組的第0個(gè)分量可以設(shè)計(jì)成表的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的next域指示了表中第一個(gè)結(jié)點(diǎn)的位置，為0表示靜態(tài)單鏈表的結(jié)束。我們把這種用游標(biāo)指示器實(shí)現(xiàn)的單鏈表叫做靜態(tài)單鏈表(StaticLinkedList)。靜態(tài)鏈表的結(jié)構(gòu)定義，靜態(tài)鏈表的插入和刪除操作示例。基本操作：初始化、分配結(jié)點(diǎn)與結(jié)點(diǎn)回收、前插操作、刪除。

2003-8-14

116

靜態(tài)鏈表的結(jié)構(gòu)定義

#defineMaxsize=鏈表可能達(dá)到的最大長(zhǎng)度typedefstruct{ElemTypedata;intcursor;}Component,StaticList[Maxsize];

2003-8-14

117

靜態(tài)鏈表的插入和刪除操作示例

已知：線性表

a，b，c，d，f，g，h，i），Maxsize=110123456789100123456789101a2b3c4d9f6g8h8i0e51a2b3c4d9f6g7h8i0e51a2b3c4d5f6g7h8i0012345678910(a)初始化(b)插入e后

(c)刪除h后

2003-8-14

118

靜態(tài)鏈表初始化

算法描述：初始化操作是指將這個(gè)靜態(tài)單鏈表初始化為一個(gè)備用靜態(tài)單鏈表。設(shè)space為靜態(tài)單鏈表的名字，av為備用單鏈表的頭指針，其算法如下：

voidinitial(StaticListspace,int*av){intk;space[0]->cursor=0;/*設(shè)置靜態(tài)單鏈表的頭指針指向位置0*/for(k=0;k<Maxsize-1;k++) space[k]->cursor=k+1;/*連鏈*/space[Maxsize-1]=0;/*標(biāo)記鏈尾*/*av=1;/*設(shè)置備用鏈表頭指針初值*/} 2003-8-14

119

靜態(tài)鏈表分配結(jié)點(diǎn)與結(jié)點(diǎn)回收

分配結(jié)點(diǎn)

intgetnode(int*av)/*從備用鏈表摘下一個(gè)結(jié)點(diǎn)空間，分配給待插入靜態(tài)鏈表中的元素*/{inti=*av;*av=space[*av].cur;returni;}結(jié)點(diǎn)回收

voidfreenode(int*av,intk)/*將下標(biāo)為k的空閑結(jié)點(diǎn)插入到備用鏈表*/{space[k].cursor=*av;*av=k;}2003-8-14

120

靜態(tài)鏈表前插操作

算法描述：1、先從備用單鏈表上取一個(gè)可用的結(jié)點(diǎn)；2、將其插入到已用靜態(tài)單鏈表第i個(gè)元素之前。

voidinsbefore(StaticListspace,inti,int*av){j=*av; /*j為從備用表中取到的可用結(jié)點(diǎn)空間的下標(biāo)*/av=space[av]->cursor; /*修改備用表的頭指針*/space[j]->data=x; k=space[0]->cursor;/*k為已用靜態(tài)單鏈表的第一個(gè)元素的下標(biāo)值*/for(m=1;m<i-1;m++)/*尋找第i-1個(gè)元素的位置k*/ k=space[k]->cursor;space[j]->cursor=space[k]->cursor;/*修改游標(biāo)域*/space[k]->cursor=j;}

2003-8-14

121

靜態(tài)鏈表刪除

算法描述：首先尋找第i-1個(gè)元素的位置，之后通過修改相應(yīng)的游標(biāo)域進(jìn)行刪除；在將被刪除的結(jié)點(diǎn)空間鏈到可用靜態(tài)單鏈表中，實(shí)現(xiàn)回收。voiddelete(StaticListspace;inti;int*av){k=space[0]->cursor;for(m=1,m<i-1;m++) /*尋找第i-1個(gè)元素的位置k*/k=space[k]->cursor;j=space[k]->cursor;space[k]->cursor=space[j]->cursor;/*從刪除第i個(gè)元素*/space[j]->cursor=*av;/*將第i個(gè)元素占據(jù)的空