計(jì)算機(jī)導(dǎo)論-以計(jì)算思維為導(dǎo)向（第4版）董衛(wèi)軍 等第3章 復(fù)雜問題的存儲與管理

XXX第3復(fù)雜問題的存儲與管理3.1數(shù)據(jù)結(jié)構(gòu)概述計(jì)算機(jī)解決問題的一般步驟問題數(shù)學(xué)模型設(shè)計(jì)算法編寫程序數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的組織、存儲和運(yùn)算。數(shù)據(jù)

組織能被計(jì)算機(jī)程序處理的符號的集合。

數(shù)據(jù)元素以及元素之間的關(guān)系。存儲元素及其關(guān)系在計(jì)算機(jī)中的表示。運(yùn)算對數(shù)據(jù)元素進(jìn)行的操作處理(插入、刪除、修改、查找、排序)。數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)的核心內(nèi)容之一。介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間。不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程

序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)的地位問題的抽象：基本構(gòu)成（元素），以及它們之間的關(guān)系。邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲：存儲元素以及元素之間的關(guān)系。如何解決問題，滿足管理需求。研究

三個(gè)問題邏輯結(jié)構(gòu)存儲結(jié)構(gòu)運(yùn)算數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)的概念數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的關(guān)系。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。有時(shí)一個(gè)數(shù)據(jù)元數(shù)可由若干數(shù)據(jù)項(xiàng)(Data

Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱結(jié)點(diǎn)或記錄。數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)可描述為：

Group=（D，R）邏輯數(shù)據(jù)結(jié)構(gòu)的描述有限個(gè)數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間關(guān)系的集合。DR例：一年四季的數(shù)據(jù)結(jié)構(gòu)

B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}家庭成員的數(shù)據(jù)結(jié)構(gòu)

B=(D,R)D={父親，兒子，女兒}R={(父親，兒子),(父親，女兒)}春夏秋

冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒學(xué)號姓名成績2018161109張卓872018161107劉雨涵952018161103胡敏86（1）線性結(jié)構(gòu)結(jié)點(diǎn)間是線性關(guān)系。A

,

B

,

C

,

·······

，X

,Y

,

Z學(xué)

生

成

績

表常見的邏輯結(jié)構(gòu)（2）樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式ABCDEFGH樹形結(jié)構(gòu)——結(jié)點(diǎn)間具有分層關(guān)系BCDE

F

G

HA1423D={

1

,

2

,

3

,

4}R={(1,2)

,

(1,3)

,

(1,4)

,

(2,3),

(2,4)

,

(213D={

1

,

2

,

3

}R={

(1,2)

,

(2,3)

,

(3,2)

,

(1,3)

}（3）圖形結(jié)構(gòu)存儲結(jié)構(gòu)指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的具體實(shí)現(xiàn)。存儲所有元素；存儲元素之間的關(guān)系一種邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)。存儲結(jié)構(gòu)存儲結(jié)構(gòu)的概念順序存儲索引存儲散列存儲常見

存儲結(jié)構(gòu)鏈?zhǔn)酱鎯ΤＲ姷拇鎯Y(jié)構(gòu)一種邏輯結(jié)構(gòu)：

可以表示成一種或多種存儲結(jié)構(gòu)。3.2

順序存儲與鏈?zhǔn)酱鎯Σ捎眠B續(xù)存儲空間存儲數(shù)據(jù)元素；

元素之間的關(guān)系通過存儲位置的關(guān)系來表示。元素1元素2……..元素i……..元素nLoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址

存儲內(nèi)容順序存儲有關(guān)鍵字序列：

32

75

70

63

48

94

25

36

18a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

a[9]32

75

70

63

48

94

25

36

18321863825902i50a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]73218638255090父節(jié)點(diǎn)

i左孩子2i+1右孩子不足之處：作插入或刪除操作時(shí)，需移動大量元素。長度變化較大時(shí)，需按最大空間分配。容量難以擴(kuò)充。oLoc(a)=L

+（i-1)*m每個(gè)元素所占用的存儲單元個(gè)數(shù)優(yōu)點(diǎn)：易于定位鏈?zhǔn)酱鎯?536851400100134673∧35每個(gè)結(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放下一個(gè)結(jié)點(diǎn)的地址。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。h1345邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。插入、刪除靈活

(不必移動節(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針)。不能直接定位，必須從頭向后遍歷。鏈接存儲結(jié)構(gòu)特點(diǎn)：3.3

索引存儲與散列存儲關(guān)鍵字：能唯一標(biāo)識一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。地址：同值關(guān)鍵字結(jié)點(diǎn)的起始位置。稠密索引：每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)。稀疏索引：一組結(jié)點(diǎn)在索引表中只對應(yīng)一個(gè)索引項(xiàng)關(guān)鍵字地址索引方式存儲結(jié)點(diǎn)信息的同時(shí)，建立附加的索引表。索引表中的每一項(xiàng)稱為一個(gè)索引項(xiàng)，索引項(xiàng)的一般形式：分配連續(xù)存儲空間，元素的存儲位置由元素的關(guān)鍵字計(jì)算得到。63

48

94

25

36

18有關(guān)鍵字序列：

32

75

70存儲空間大?。?1地址計(jì)算規(guī)則：L=K

MOD

11沖突解決機(jī)制：L+1散列方式K

32

75

70

63

48

94

25

36

18L

10

9

4

8

4

6

3

3

7A

10

9

4

8

?A012345678910K70637532計(jì)算存儲位置：K327570634894253618L1094846337A109485A012345678910K7048637532K327570634894253618L1094846337A10948563?A012345678910K25704894637532K327570634894253618L1094846337A109485637A012345678910K2570489436637532K

32

75

70

63

48

94

25

36

18L

10

9

4

8

4

6

3

3

7A

10

9

4

8

5

6

3

7

?A012345678910K2570489436637532K

32

75

70

63

48

94

25

36

18L

10

9

4

8

4

6

3

3

7A

10

9

4

8

5

6

3

7

0A012345678910K182570489436637532K327570634894253618L1094846337A1094856370N111121155A012345678910K1825704894366375323.4

算法算法是程序設(shè)計(jì)的核心算法概念算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。算法是解題的過程。形成解題思路(推理實(shí)現(xiàn)的算法)，編寫程序(操作實(shí)現(xiàn)的算法)，都是在實(shí)施某種算法。算法以存儲結(jié)構(gòu)為基礎(chǔ)算法特征有窮性

保證執(zhí)行有限步之后結(jié)束每一步驟必須有確切的定義確定性有輸入

有0個(gè)或多個(gè)輸入，0輸入是指算法本身設(shè)定了初始條件有輸出

有一個(gè)或多個(gè)輸出，沒有輸出的算法毫無意義內(nèi)完成可行性

能夠在有限時(shí)間、有限空間算法設(shè)計(jì)的要求能夠正確的解決問題。正確性①不含語法錯(cuò)誤；②對于幾組輸入數(shù)據(jù)，結(jié)果正確；③對于精心選擇的幾組數(shù)據(jù)，結(jié)果正確；④對一切合法的輸入數(shù)據(jù)，結(jié)果正確。應(yīng)容易供人閱讀和交流。可讀性好的算法有助于對算法的理解和修改。可讀性應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理健壯性應(yīng)具有一般性。即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立。通用性算法的表示需要使用一些語言形式。傳統(tǒng)描述-------圖形法:“流程圖”和N-S圖。常用描述-------使用偽碼描述算法。算法描述INPUT

rS=3.14

*

r*rPTINT

S開始輸入RS=3.14

*

R*R輸出S結(jié)束問題：輸入園的半徑，計(jì)算圓的面積。算法性能分析執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。時(shí)間復(fù)雜度執(zhí)行過程中臨時(shí)占用的存儲空間來度量?？臻g復(fù)雜度基本語句執(zhí)行次數(shù)，而非時(shí)間。計(jì)算最壞情況。常數(shù)階O(1)對數(shù)階O(log2

n)線性階O(n)線性對數(shù)階O(n

log2

n)k次方階O(nK)指數(shù)階O(2n)時(shí)間復(fù)雜度隨著問題規(guī)模n的不斷增大，時(shí)間復(fù)雜度不斷增大。int

x=1,s=0;while

(x

<10){s+=x;

x++;}執(zhí)行10次，時(shí)間復(fù)雜度表示是O(1)。int

i,j,s=1;for

(i

=

0;

i

<

n;

i++){for

(j

=

0;

j

<

n;

j++){

s=s+i*j

}}時(shí)間復(fù)雜度是O（n2）空間復(fù)雜度運(yùn)行過程中臨時(shí)占用存儲空間大小的量度。計(jì)算方法：①忽略常數(shù)，用O(1)表示②遞歸算法的空間復(fù)雜度=遞歸深度N*每次遞歸所要的輔助空間int

fun(int

n){

int

k=10;if（n==k)return

n;elsereturn

fun(++n);}遞歸實(shí)現(xiàn)，調(diào)用fun函數(shù)每次都創(chuàng)建1個(gè)變量k。調(diào)用n次，空間復(fù)雜度O（n*1）=O(n)。二分查找的時(shí)間復(fù)雜度及空間復(fù)雜度以查找68為例：二分查找的時(shí)間復(fù)雜度及空間復(fù)雜度非遞歸：每次都對原查找內(nèi)容進(jìn)行二分，所以時(shí)間復(fù)雜度為O（log2

n）。變量值創(chuàng)建一次，所以空間復(fù)雜度為O（1）。遞歸：時(shí)間復(fù)雜度為O（log2

n）。每進(jìn)行一次遞歸都會創(chuàng)建變量，所以空間復(fù)雜度為O（log2

n）。算法：是一組邏輯步驟。程序：用計(jì)算機(jī)語言描述的算法。開始輸入RS=3.14

*

R*R輸出S結(jié)束main(){float

r,s;scanf(“%f”,&r);if(r<0)printf(“err,r<0”);else{s=r*r*3.14;printf(“s=%f”,s);}算法和程序的區(qū)別3.5

線性表一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)若滿足下面的幾個(gè)條件：①有且僅有一個(gè)根結(jié)點(diǎn)；②除第一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前驅(qū)結(jié)點(diǎn)；③除最后一個(gè)結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接后繼結(jié)點(diǎn)。線性表、棧和隊(duì)列都是線性結(jié)構(gòu)；樹、圖、網(wǎng)屬于非線性結(jié)構(gòu)。線性結(jié)構(gòu)由n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，ai，…，an組成的一個(gè)有限序列。20

18

32

30

76

78

90

65

70

34線性表的概念線性表的特點(diǎn)：線性表中所有元素的性質(zhì)相同。除第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)，最后一個(gè)數(shù)據(jù)元素?zé)o后繼。數(shù)據(jù)元素在表中的位置只取決于它自身的序號。線性表的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表上常用的操作有：初始化、求長度、取元素、修改、插入、刪除、檢索、排序。ai-1…..a2a1alength…ai+1ai+1axaxi分配連續(xù)存儲空間，依次存儲所有元素。?線性表的順序存儲結(jié)構(gòu)稱為順序表◆只存儲結(jié)點(diǎn)的值，不存儲結(jié)點(diǎn)間的關(guān)系；◆邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里；◆結(jié)點(diǎn)間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。線性表的順序存儲在程序設(shè)計(jì)語言中，通常利用數(shù)組來表示線性表的順序存儲結(jié)構(gòu)。數(shù)組中的元素間的地址是連續(xù)的；數(shù)組中所有元素的數(shù)據(jù)類型相同。int

a[10];系統(tǒng)將在內(nèi)存中分配連續(xù)的40個(gè)字節(jié)（VC中整數(shù)占4個(gè)字節(jié)），存放

10個(gè)整數(shù)。a[0]

a[1]

a[2]

a[3]

a[4]

a[5]

a[6]

a[7]

a[8]

a[9]01aaa2a3……ai……an存儲空間Loc(a0)0Loc(a

)+d0Loc(a

)+2*dLoc(a0)+i*dLoc(a0)+n*d存儲地址a[0]a[1]a[2]a[3]……a[i]……a[n]元素Loc（ai）=Loc（a0）+i*d直接定位，實(shí)現(xiàn)隨機(jī)存取插入運(yùn)算ai-1…..a2a1alength…ai+1aixai-1…..a2a1alength…ai+1ai+1axaxi…..a2a1alength…alengtha…i+1ai+1ai-1

aaii從后向前依次后移刪除運(yùn)算從前向后依次前移4

17

15

28

30

32

42

51

634

17

15

30

32

42

51

63

63隊(duì)尾元素插入算法性能分析假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定

在n+1個(gè)位置上插入元素的可能性均等，則平均移動元素的個(gè)數(shù)為：時(shí)間復(fù)雜度為O(n)。刪除算法的分析在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動元素的個(gè)數(shù)為：時(shí)間復(fù)雜度為O(n)?！舯碇袛?shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高；◆各數(shù)據(jù)元素在存儲空間中按邏輯順序依次存放，占有連續(xù)存儲空間，可以直接定位；◆做插入、刪除時(shí)需移動大量元素，若表長為n，則插入算法的時(shí)間復(fù)雜度都為O(n)?！艨臻g估計(jì)不清楚時(shí)，應(yīng)按最大空間分配。順序存儲總結(jié)3.6

線性表的鏈?zhǔn)酱鎯Φ臄?shù)據(jù)元素物理位置也相鄰；◆各數(shù)據(jù)元素的存儲順序任意；◆數(shù)據(jù)元素的先后關(guān)系是由結(jié)點(diǎn)的指針域指示。數(shù)據(jù)域指針域鏈?zhǔn)酱鎯?線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表◆數(shù)據(jù)存在結(jié)中，不要求邏輯上相鄰5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp帶頭節(jié)點(diǎn)的鏈表P->data：5

P->nextP->next->data：第一個(gè)元素2000NULLp

空表5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp在210的后面插入300q=p->next;從q開始向后遍歷，找210若q->data!=210，則q=q->next;q插入運(yùn)算5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp申請結(jié)點(diǎn)rr->data=300;r->next=q-next;將r和q的后繼結(jié)點(diǎn)鏈接q300CD00A1r6AB036F200AB350018C300AC210CD00A1180CF0026100UNLLpq->next=r;將q和r鏈接起來修改節(jié)點(diǎn)數(shù)為6q300CD00A1r5AB036F200AB350018C300AC210CD00A1180CF0026100UNLLp刪除180從前向后找到180的前驅(qū)結(jié)點(diǎn)

q=p;若q->next->data!=180，則q=q->next;q刪除運(yùn)算5AB036F200AB350018CF0026210CD00A1180CF0026100UNLLps=q->next;保存180所在節(jié)點(diǎn)位置

q->next=s->next;將S從鏈中刪除qs4AB036F200AB350018CF0026210CD00A1100UNLLpfree(s);釋放s所指向的節(jié)點(diǎn)修改節(jié)點(diǎn)數(shù)為4q◆表中數(shù)據(jù)元素類型一致，結(jié)點(diǎn)由數(shù)據(jù)域和指針域構(gòu)成；◆按需申請結(jié)點(diǎn)，結(jié)點(diǎn)空間不連續(xù)；◆不可直接定位，需從頭遍歷；◆便于插入、刪除。鏈?zhǔn)酱鎯偨Y(jié)單向鏈表的改進(jìn)循環(huán)鏈表：最后一個(gè)節(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)。5AB036F200AB350018C300AC210CD00A1180CF0026100A00035p從任意一個(gè)節(jié)點(diǎn)開始都可向后進(jìn)行遍歷。雙向鏈表：可以克服單鏈表的單向性的缺點(diǎn)。在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域：其一指向直接后繼，另一指向直接前趨。priordatanext從任意一節(jié)點(diǎn)開始，既可向前(q->prior)，也可向后(q->next)進(jìn)行遍歷。3.7

隊(duì)列的存儲與處理隊(duì)的概念隊(duì)列是操作位置受限的線性表只能在表的一端插入，另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出表。an-1

,

ana1

,

a2

,

a3

,

a4

,

…………隊(duì)首隊(duì)尾設(shè)置一個(gè)空隊(duì)列；插入一個(gè)新的元素（隊(duì)尾），稱為入隊(duì)；刪除隊(duì)頭素（隊(duì)首），稱為出隊(duì)；讀取隊(duì)頭元素；隊(duì)的基本操作用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素，指針

front和rear分別指示隊(duì)頭元素和隊(duì)尾元素的位置。隊(duì)的順序存儲0123456789124258267463frontrear隊(duì)空：令rear=front=-1；元素入隊(duì)：rear=rear+1;a[rear]=m;

元素出隊(duì)：front=front+1;m=a[front];故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個(gè)位置，而尾指針始終指向隊(duì)尾元素的位置01234567891242582674639042出隊(duì)

front90入隊(duì)

rear一定會出現(xiàn)假溢出現(xiàn)象012345678912425826746390625871front

rear隊(duì)中只有一個(gè)元素71，若有元素入隊(duì)則溢出。A[0] a[8]空閑解決方法：存入a[0]01234567898642582674639062587186入隊(duì)rear

front可以將為隊(duì)列分配空間看成為一個(gè)首尾相接的圓環(huán)，并稱這種隊(duì)列為循環(huán)隊(duì)列。本質(zhì)：rear和front在結(jié)尾處完成向開始的跳轉(zhuǎn)。9

0012345678986425826746390625871front86入隊(duì)

rear入隊(duì)：rear=（rear+1）mod

QSize;出隊(duì)：front=（front+1）mod

QSize;a[rear]=m;m=a[front];012345678986425826746390625871frontrear隊(duì)空：rear==front;出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空時(shí)頭尾指針相等。012345678986656789706087909683frontrear入隊(duì)時(shí)尾指針向前追趕尾指針，此時(shí)不能再入隊(duì)，否則

rear==front,滿隊(duì)、空隊(duì)無法區(qū)分。隊(duì)滿：（rear+1）mod

QSize==front;Front

所指空間永遠(yuǎn)為空。隊(duì)列具有的先進(jìn)先出的固有特性，使得隊(duì)列成為程序設(shè)計(jì)中常用的工具。隊(duì)列的應(yīng)用任務(wù)調(diào)度事件被觸發(fā)，產(chǎn)生消息，存入系統(tǒng)的消息隊(duì)列。線程從隊(duì)列中取出消息，通過操作系統(tǒng)發(fā)送到對應(yīng)的窗口過程去處理。OS從系統(tǒng)消息隊(duì)列中取出一個(gè)消息，送往處理該消息的線程消息隊(duì)列。對短作業(yè)不利改進(jìn)……先來先服務(wù)3.8

棧的存儲與處理?xiàng)５母拍钤O(shè)棧s=（a1，a2，.

.

.

,ai，.

.

.

，an），1

n其中a

是棧底元素， a

是棧頂元素。棧頂（top)：允許插入和刪除的一端；棧底（bottom):不允許插入和刪除的一端。an….a2a1入棧

出棧棧頂棧底棧是操作位置受限：只能在棧頂進(jìn)行插入和刪除。棧也稱為稱為后進(jìn)先出表第一個(gè)進(jìn)棧的元素在棧底；

最后一個(gè)進(jìn)棧的元素在棧頂；第一個(gè)出棧的元素為棧頂元素；

最后一個(gè)出棧的元素為棧底元素。不含元素的棧稱為空棧。an….a2a1入棧

出棧棧頂棧底a2a1top棧的順序存儲順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素。一般用一維數(shù)組表示，設(shè)置簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置。即：棧頂元素在top-1處。top空棧：top==0321032106543210入棧Top=0空棧int

a[7],top;top=0;a[top]=m;top=top+1;106543210Top=110入棧978563420106543210Top=620,12,34,56,78,9入棧26978563420106543210Top=726入棧滿棧再入棧，則溢出出棧26695784563342201100Top=726695784563342201100top=top-1;

m=a[top];Top=526、9出棧若有A,B,C三個(gè)元素進(jìn)S棧的順序是A,B,C，則可能的出棧序列有：CBAACBABCBACBCA入棧、出棧可能交叉進(jìn)行ABCD-----DCBADCBA棧的應(yīng)用棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中常用的工具。內(nèi)容逆置NN

div

8N

mod

81348168416821021252022504原理：N=(N

div

d)*d+N

mod

d算法分析：當(dāng)N≠0，將N%r壓入棧中；用N/r代替N；

若N>0，則重復(fù)以上步驟，若

N==0，則依次輸出棧的內(nèi)容。數(shù)制轉(zhuǎn)換棧的另一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語言中實(shí)現(xiàn)遞歸調(diào)用。

遞歸調(diào)用：一個(gè)函數(shù)(或過程)直接或間接地調(diào)用自己本身。遞歸調(diào)用遞歸是程序設(shè)計(jì)中的一個(gè)強(qiáng)有力的工具。◆遞歸函數(shù)結(jié)構(gòu)清晰，程序易讀，正確性很容易得到證明。為了使遞歸調(diào)用不至于無終止地進(jìn)行下去，實(shí)際上有效的遞歸調(diào)用函數(shù)(或過程)應(yīng)包括兩部分：遞推規(guī)則(方法)，終止條件。1當(dāng)n=0時(shí)終止條件Fact(n)=n*fact(n-1)

當(dāng)n>0時(shí)

遞推規(guī)則fact(10)=fact(9)*10;fact(9)=fact(8)*9;fact(8)=fact(7)*8;……fact(1)=fact(0)*1;fact(0)===1為保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)設(shè)立一個(gè)“遞歸工作?！?，作為整個(gè)遞歸調(diào)用過程期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸包含信息：參數(shù)、局部變量、上一層的返回地址構(gòu)成一個(gè)

“工作記錄”。每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂；每退出一層遞歸，就從棧頂彈出一個(gè)工作記錄。董衛(wèi)軍第5章層次問題的分析與處理3.9

二叉樹的概念與性質(zhì)樹的概念由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。僅有一個(gè)根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。樹(Tree)是n(n≧0)個(gè)結(jié)點(diǎn)的有限集合T，若n=0時(shí)稱為空樹，否則：有且只有一個(gè)特殊的稱為樹的根(Root)結(jié)點(diǎn)；若n>1時(shí)，其余的結(jié)點(diǎn)被分為m(m>0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集本身又是一棵樹，稱其為根的子樹(Subtree)。ACGT2DHIT3JMBELKT1F組織機(jī)構(gòu)關(guān)系書的層次結(jié)構(gòu)

家族血緣關(guān)系等樹的基本術(shù)語結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素及其若干指向其子樹的分支。結(jié)點(diǎn)的度、樹的度：結(jié)點(diǎn)所擁有的子樹的棵數(shù)稱為結(jié)點(diǎn)的度。樹中結(jié)點(diǎn)度的最大值稱為樹的度。(b)中結(jié)點(diǎn)A的度是3，結(jié)點(diǎn)B的度是2，結(jié)點(diǎn)M的度是0，樹的度是3。葉子結(jié)點(diǎn)、非葉子結(jié)點(diǎn)：樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)(或終端結(jié)點(diǎn))。相對應(yīng)地，度不為0的結(jié)點(diǎn)稱為非葉子結(jié)點(diǎn)。孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)（子結(jié)點(diǎn)）；相應(yīng)地，該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)（父結(jié)點(diǎn)）。K、L、F、M、N：葉子節(jié)點(diǎn)

A的孩子節(jié)點(diǎn)：B、C、D兄弟節(jié)點(diǎn)：H、I、J樹的深度：樹中結(jié)點(diǎn)的最大層次值，又稱為樹的高度。有序樹和無序樹：對于一棵樹，若其中每一個(gè)結(jié)點(diǎn)的子樹（若有）具有一定的次序，則該樹稱為有序樹，否則稱為無序樹。森林：是m(m≧0)棵互不相交的樹的集合。顯然，若將一棵樹的根結(jié)點(diǎn)刪除，剩余的子樹就構(gòu)成了森林。二叉樹二叉樹的概念二叉數(shù)是n(n

0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諛?n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。二叉樹是一種樹型結(jié)構(gòu)。特點(diǎn)：樹中每個(gè)結(jié)點(diǎn)最多有兩棵子樹，且子樹有左右之分?？斩鏄鋬H有根結(jié)點(diǎn)

右子樹為空

左子樹為空二叉樹的五種基本形態(tài)左右子樹均非空423678910111213

14155第三層上(i=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個(gè)節(jié)點(diǎn)。深度h=4，最多有24-1=15個(gè)節(jié)點(diǎn)。

n=8，m=7。二叉樹的第i層上至多有2i-1（i

1）個(gè)結(jié)點(diǎn)。深度為h的二叉樹中至多含有2h-1個(gè)結(jié)點(diǎn)。若在任意一棵二叉樹中，有n個(gè)葉子結(jié)點(diǎn)，有m個(gè)度為2的結(jié)點(diǎn)，則：n=m+11二叉樹的性質(zhì)4231678915510

11

12

13

14特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。滿二叉樹42316789

10

11125非完全二叉樹4231678

9

10

11

125完全二叉樹特點(diǎn)：除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。完全二叉樹849

105613

14157213452167311

12(a)滿二叉樹8

9

10

11

12(b)完全二叉樹1362455674213(c)非完全二叉樹◆樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，二叉樹結(jié)點(diǎn)最大度數(shù)為2?！魳涞慕Y(jié)點(diǎn)無左、右之分，二叉樹的結(jié)點(diǎn)子樹有明確的左、右之分。樹樹和二叉樹的區(qū)別二叉樹3.10

二叉樹的存儲與遍歷二叉樹的順序存儲用一組地址連續(xù)的存儲單元依次“自上而下、自左至右”存儲完全二叉樹的數(shù)據(jù)元素。若不是完全二叉樹，則補(bǔ)

空

使其變?yōu)橥耆鏄?，然后存儲。元素之間的父子、兄弟關(guān)系，通過存儲位置的關(guān)系來表示。abcdh

iej

klfg完全二叉樹0

1

2

3

4

5

6

7

8

9

10

11

12

13

14a

b

c

d

e

f

g

h

i

j

k

li父節(jié)點(diǎn)位置2i左孩子位置2i+1右孩子位置abcdeh???

f

g非完全二叉樹0

1

2

3

4

5

6

7

8

9

10

11

12

13

14a

b

c

d

e

?

h

?

?

f

gi父節(jié)點(diǎn)位置2i左孩子位置2i+1右孩子位置最壞的情況：深度為k，只有k個(gè)結(jié)點(diǎn)的單支樹需要長度為2k-1的一維數(shù)組。二叉鏈表節(jié)點(diǎn)三叉鏈表節(jié)點(diǎn)二叉樹的鏈?zhǔn)酱鎯Χ骀湵斫Y(jié)點(diǎn)：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域。三叉鏈表結(jié)點(diǎn)：除二叉鏈表的三個(gè)域外，再增加指向父結(jié)點(diǎn)的指針域。ABCDEFGABCDEFG^^^^^^^^ABCDEFG^^^^^^^^^二叉鏈表三叉鏈表遍歷：指按指定的規(guī)律對二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。用途：它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。遍歷的概念二叉樹是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都可能有左、右兩棵子樹。二叉樹的基本組成：根結(jié)點(diǎn)、左子樹、右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。DLRLR先左后右DLRLDRLRD先序遍歷后序遍歷若以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定先左后右，則只有三種情況。D中序遍歷二叉樹遍歷的遞歸算法是由系統(tǒng)通過使用堆棧來實(shí)現(xiàn)控制，結(jié)構(gòu)清晰。先序遞歸遍歷算法的遞歸定義：若二叉樹為空，則遍歷結(jié)束；否則⑴訪問根結(jié)點(diǎn)；⑵先序遍歷左子樹(遞歸調(diào)用本算法)；⑶先序遍歷右子樹(遞歸調(diào)用本算法)。void

PrTraverse(BTNode

*T){

if

(T!=NULL){

visit(T->data)PrTraverse(T->Lchild)

;PrTraverse(T->Rchild)

;}}—/fe-dcb*a+先序序列-+a*b-cd/ef中序遞歸遍歷算法的遞歸定義：若二叉樹為空，則遍歷結(jié)束；否則⑴中序遍歷左子樹(遞歸調(diào)用本算法)；⑵訪問根結(jié)點(diǎn)；⑶中序遍歷右子樹(遞歸調(diào)用本算法)。void

ITraverse(BTNode

*T){

if

(T!=NULL){

ITraverse(T->Lchild)

;visit(T->data)

;ITraverse(T->Rchild)

;}}中序序列a+b*c-d-e/f—/fe-dcb*a+后序遞歸遍歷算法的遞歸定義：若二叉樹為空，則遍歷結(jié)束；否則⑴后序遍歷左子樹(遞歸調(diào)用本算法)；⑵后序遍歷右子樹(遞歸調(diào)用本算法)。⑶訪問根結(jié)點(diǎn)；void

PoTraverse(BTNode

*T){

if

(T!=NULL){

PoTraverse(T->Lchild)

;PoTraverse(T->Rchild)

;visit(T->data)

;}}后序序列abcd-*+ef/-—/fe-dcb*a+3.11

二叉樹與樹樹和二叉樹的轉(zhuǎn)換以二叉鏈表作為樹的存儲結(jié)構(gòu)：孩子兄弟法。孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchilddatanextsibing樹的二叉鏈表存儲DRABECGF樹二叉鏈表存儲樹與二叉樹存儲關(guān)系理解不同：左指針指向孩子；右指針指向兄弟。理解不同：左指針指向左孩子；右指針指向右孩子。森林到二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換成二叉樹孩子兄弟表示法ACBDGMLHK(a)

森林(b)森林中每棵樹對應(yīng)的二叉樹ABCDGLKHM(c)森林對應(yīng)的二叉樹ABCDGLKHM樹的遍歷樹的遍歷有二種方法。先序遍歷：先訪問根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹。ABDCKGJIFHEABCDEFGIJHK后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結(jié)點(diǎn)。ABDCKGJIFHECDBFIJGHEKA先序遍歷：RADEBCGF先序遍歷：RADEBCGF后序遍歷：DEABGFCR中序遍歷：EDABGFCR與將樹轉(zhuǎn)換成二叉樹后對二叉樹的先序遍歷相同與將樹轉(zhuǎn)換成二叉樹后對二叉樹的中序遍歷相同樹的先序遍歷樹的后序遍歷樹采用二叉鏈表存儲：簡單、規(guī)范對樹的操作可以通過對相應(yīng)二叉樹的操作來實(shí)現(xiàn)3.12

二叉樹的應(yīng)用先序遍歷+*

*/A

B

C

D

E前綴表示+*A*/EDCB二叉樹表示算術(shù)表達(dá)式中序遍歷A/B

*

C

*

D+E中綴表示后序遍歷A

B/C

*

D

*

E+后綴表示前綴表達(dá)式、中綴表達(dá)式、后綴表達(dá)式都是四則運(yùn)算的表達(dá)方式。前綴表達(dá)式的計(jì)算：從右至左掃描表達(dá)式，遇到數(shù)字時(shí)，將數(shù)字壓入堆棧，遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)數(shù)，用運(yùn)算符對它們做相應(yīng)的計(jì)算（棧頂元素

op

次頂元素），并將結(jié)果入棧；重復(fù)上述過程直到表達(dá)式最左端，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果。EDCBA入棧，AB出棧；先序遍歷+*

*/A

B

C

D

E前綴表示計(jì)算A/B記做R1結(jié)果入棧；計(jì)算R1*C

記做R2結(jié)果入棧；計(jì)算R2*D

記做R3結(jié)果入棧；計(jì)算R3+E

記做R4結(jié)果入棧；結(jié)果R4

出棧。哈夫曼樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。結(jié)點(diǎn)路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。哈夫曼樹ABDCKGJIFHEA到F

：結(jié)點(diǎn)路徑

AEF

；A到F路徑長度：2

；

樹的路徑長度：3

1+52+2

3=19結(jié)點(diǎn)的帶權(quán)路徑長度：從結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)權(quán)(值)的乘積。權(quán)(值)：各種開銷、代價(jià)、頻度等的抽象稱呼。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記做：WPL=w1

l1+w2

l2+?+wn

ln=∑wi

li

(i=1,2,?,n)n為葉子結(jié)點(diǎn)個(gè)數(shù)；wi為第i個(gè)葉子結(jié)點(diǎn)的權(quán)值；li為第i個(gè)葉子結(jié)點(diǎn)的路徑長度。具有n個(gè)葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的權(quán)值為wi

的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹，稱這棵樹為哈夫曼樹

(或稱最優(yōu)樹)。dc24a7b5WPL=7*3+5*3+2*1+4*2=46a7b

c5

2d4WPL=7*2+5*2+2*2+4*2=36例如：有4個(gè)節(jié)點(diǎn)a,b,c,d，對應(yīng)的權(quán)值分別為7、5、2、4。以這4個(gè)節(jié)點(diǎn)作為葉子節(jié)點(diǎn)構(gòu)造二叉樹如下。abc

d7524WPL=7*1+5*2+2*3+4*3=35WPL值最小，可以證明是哈夫曼樹。在數(shù)據(jù)通訊中，常需要將傳送的文字轉(zhuǎn)換成01代碼傳輸。為提高速度要求電文編碼要盡可能地短，就要設(shè)計(jì)長短不等的編碼：高概率數(shù)據(jù)編碼短，低概率數(shù)據(jù)編碼長。還必須保證任意字符的編碼都不是另一個(gè)字符編碼的前綴。哈夫曼樹可以用來構(gòu)造編碼長度不等且譯碼不產(chǎn)生二義性的編碼哈夫曼編碼構(gòu)造哈夫曼樹以字符集C作為葉子結(jié)點(diǎn)，頻度集W作為結(jié)點(diǎn)的權(quán)值來構(gòu)造哈夫曼樹。規(guī)定分支編碼規(guī)定哈夫曼樹中左分支代表“0”，右分支代表“1”。產(chǎn)生編碼從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷路徑分支上的“0”或

“1”所組成的編碼，為該結(jié)點(diǎn)的哈夫曼編碼。ab752400110

1c

dWPL=7*1+5*2+2*3+4*3=35哈夫曼編碼a:

0

b:

10c:

110d:

1111高概率數(shù)據(jù)編碼短，低概率數(shù)據(jù)編碼長。

任意字符的編碼都不是另一個(gè)字符編碼的前綴。3.13

二叉排序樹二叉排序樹是具備以下特點(diǎn)的二叉樹：若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它根節(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于其根節(jié)點(diǎn)的值。二叉排序樹的概念序列13、8、23、5、18、9、37、2，構(gòu)造二叉樹。二叉排序樹的構(gòu)造二叉排序樹的應(yīng)用（1）數(shù)據(jù)查找最小元素：從根節(jié)點(diǎn)沿左子樹，直到找到葉子節(jié)點(diǎn)就可得到最小值；最大元素：從根節(jié)點(diǎn)沿右子樹，直到找到葉子節(jié)點(diǎn)就可得到最大值。特定元素：從根節(jié)點(diǎn)開始，若比根節(jié)點(diǎn)小，則在左子樹查找；若比根節(jié)點(diǎn)大，則在右子樹查找；以此類推，直到成功或失敗。例如：查找18。（2）數(shù)據(jù)排序構(gòu)造二叉排序樹；中序遍歷二叉排序樹即得到升序序列。序列13、8、5、23、18、9、37、2。中序遍歷：2、5、8、9、13、18、23、37。（3）數(shù)據(jù)統(tǒng)計(jì)統(tǒng)計(jì)一本書中，出現(xiàn)過多少個(gè)不同的單詞，以及每個(gè)單詞的出現(xiàn)次數(shù)。RCLC

NUM

WORDLC：指向左孩子；RC：指向右孩子；

NUM：存儲單詞出現(xiàn)的次數(shù)；WORD：存儲單詞。具體過程從書中依次讀入單詞，對每個(gè)單詞進(jìn)行如下操作：在二叉排序樹中查找該單詞是否存在：若存在，修改該單詞對應(yīng)節(jié)點(diǎn)的NUM域：NUM=NUM+1；若不存在，則將該單詞插入二叉樹，使結(jié)果仍為二叉排序樹，同時(shí)將節(jié)點(diǎn)的NUM域設(shè)置為1；重復(fù)（1）直到所有單詞均處理完；按中序遍歷輸出二叉排序樹中每個(gè)節(jié)點(diǎn)的WORD域和NUM域。3.14

數(shù)據(jù)查找概述查找的概念在給定的查找表中找出滿足某種條件的結(jié)點(diǎn)；若存在這樣的結(jié)點(diǎn)，則查找成功；否則，查找失敗。查找表：是一組待查數(shù)據(jù)元素的集合。性能衡量指標(biāo)：平均查找長度（與關(guān)鍵字進(jìn)行比較的平均次數(shù)）靜態(tài)查找查找時(shí)只對數(shù)據(jù)元素進(jìn)行查詢或檢索，表內(nèi)容不變。查找表稱為靜態(tài)查找表動態(tài)查找在查找時(shí)，在表中插入中不存在的記錄，或從刪除已存在的某個(gè)記錄，表內(nèi)容會發(fā)生變化。查找表稱為動態(tài)查找表。兩種基本形式：靜態(tài)查找和動態(tài)查找基本形式查找表是記錄的集合，元素之間是一種完全松散的關(guān)系；◆查找表結(jié)構(gòu)靈活，可用多種方式來存儲?！舸鎯Y(jié)構(gòu)的不同決定了查找方法的不同。查找表的組織四種基本存儲結(jié)構(gòu)將給定的K值與查找表中記錄的關(guān)鍵字逐個(gè)比較，找到要查找的記錄。根據(jù)給定的K值直接訪問查找表，從而找到要查找的記錄。首先根據(jù)索引確定待查找記錄所在的塊，然后再從塊中找到要查找的記錄。鏈表散列表索引查找表順序表基本查找方法順序查找從表的一端開始逐個(gè)將記錄的關(guān)鍵字和給定K值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字和給定K值相等，查找成功；若掃描完整個(gè)表，仍沒有找到相應(yīng)的記錄，則查找失敗。靜態(tài)查找順序表、鏈表折半查找折半查找又稱為二分查找，要求查找表中的所有記錄按關(guān)鍵字有序(升序或降序)。查找時(shí)，先和查找表最中間位置的元素進(jìn)行比較，確定待查找記錄在表中的范圍，然后逐步縮小范圍(每次將待查記錄所在區(qū)間縮小一半)，直到找到或找不到記錄為止。靜態(tài)查找順序表分塊查找分塊查找又稱索引順序查找，是順序比較和折半查找方法的綜合。將查找表分成若干塊。塊間有序，塊內(nèi)無序。即第i+1塊的所有記錄關(guān)鍵字均大于(或小于)第i塊記錄的關(guān)鍵字；在查找表的基礎(chǔ)上附加一個(gè)索引表，索引表按關(guān)鍵字有序。先確定待查記錄所在塊（順序或折半），再在塊內(nèi)查找(順序查找)。靜態(tài)查找

索引查找表二叉排序樹查找將給定的K值與二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：若相等：則查找成功；若給定的K值小于二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該結(jié)點(diǎn)的左子樹上進(jìn)行查找；查找失敗，插入該節(jié)點(diǎn)（仍是二叉排序樹）。若給定的K值大于二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該結(jié)點(diǎn)的右子樹上進(jìn)行查找。查找失敗，插入該節(jié)點(diǎn)（仍是二叉排序樹）。動態(tài)查找

二叉鏈表散列表查找設(shè)計(jì)一種記錄存儲地址和它關(guān)鍵字之間的確定對應(yīng)關(guān)系，根據(jù)該關(guān)系構(gòu)造查找表（散列表）；查找時(shí)，直接定位元素的存儲位置。靜態(tài)查找散列表3.15

順序比較與折半查找從前向后（或者從后向前），逐個(gè)比較。簡單，易于實(shí)現(xiàn)，效率低下。順序存儲、鏈?zhǔn)酱鎯樞虿檎宜枷胩攸c(diǎn)存儲要求順序查找0

1

2

3

4

5

6

7

8

945

6

38

72

16

23

87

65

39特點(diǎn)：n個(gè)元素，所需空間n+1;查找時(shí)，從后向前比較；int

p

;a[0]=key

;元素存于a[1]---------------a[n];/*

設(shè)置監(jiān)視哨兵,失敗返回0

*/a[0]為監(jiān)視哨，為查找失敗標(biāo)志；

for

(p=9;

a[p]!=key;

p--);return(p)

;查找38，結(jié)果為3；01234567893845638721623876539查找-10，結(jié)果為0；0123456789-104563872162387653912638722365head10

45特點(diǎn)：

鏈?zhǔn)酱鎯那跋蚝蟊容^。16

87

16

∧p=head;While(p!=NULL&&p->data!=key)p=p->next;return(p)

;1245638721623876516

∧10head查找23p1245638721623876516

∧10head查找-10

P:NULL不失一般性，設(shè)查找每個(gè)記錄成功的概率相等，即Pi=1/n；nASL=∑

Pii=1i=1nCi=

―n

∑

(n-i+1)=

21

n+1時(shí)間復(fù)雜度為O(n)；若表長為10億，ASL約為5億。將有序序列的中點(diǎn)設(shè)置為比較對象，如

果要找元素值小于比較對象，則將待查

序列縮小為左半部分，否則為右半部分。是一種高效的查找方法?？梢悦黠@減少比較次數(shù)，提高查找效率順序、有序存儲折半查找思想特點(diǎn)存儲要求折半查找首先確定整個(gè)查找區(qū)間的中間位置;

mid=

(left+right

)/2用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較:若相等，則查找成功；若大于，則確定查找范圍為后半?yún)^(qū)域

[mid+1,right]；若小于，則確定查找范圍為前半?yún)^(qū)域

[left,mid-1]

。（3）對確定的縮小區(qū)域重復(fù)（1）、（2）步驟；算法步驟01234567891245638721623876539查找關(guān)鍵字值為87的數(shù)據(jù)元素leftrightmid87>72縮小查找范圍為右半部分mid+1至right01234567891245638721623876539查找關(guān)鍵字值為87的數(shù)據(jù)元素rightmid162387653956789（2）leftrightmid2次比較成功（1）查找時(shí)每經(jīng)過一次比較，查找范圍就縮小一半。一般情況下，表長為n的折半查找的判定樹的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同。時(shí)間復(fù)雜度為O(log2n)若表長為10億，ASL約為29。3.16

索引查找與散列查找為查找表建立索引，先在索引表確定塊的位置，再在塊中查找。結(jié)合折半查找和順序比較查找，效率較高索引表順序有序存儲；塊表不做要求，后一塊中所有元素要比前一塊最大元素大。分塊查找思想特點(diǎn)存儲要求分塊查找12

23

56729

43

57

87

36

40

90

120

95

112

93

95

219

223

567

35001202

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19查找表分成若干塊；塊內(nèi)可無序也可有序，塊間有序。例中，21個(gè)元素，每塊6個(gè)，分4塊（最后一塊一般不滿）29

90

219

5670

6

12

1812

23

56729

43

57

87

36

40

90120

95

112

93

95

219223

567

350012345678910

11

12

13

14

15

16

17

18

1920為查找表建立索引表每塊一個(gè)索引項(xiàng)索引表索引項(xiàng)的構(gòu)成塊最大關(guān)鍵字塊起始地址塊最大關(guān)鍵字有序兩種組織方式有序列

12,23,5,6,7,29,43,57,87,36,40,90,120,95,112,93,95,219,223,567,35029

90

219

5670

6

12

1812235672943578736409012095112939521922356735001234567891011121314151617181920查找表采用順序存儲查找表采用鏈?zhǔn)酱鎯λ惴ú襟E先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表；查找分兩步：①對索引表進(jìn)行二分查找或順序查找，確定待查記錄在哪一塊；②在已確定的塊中用順序法進(jìn)行查找。12

23

56729

43

57

87

36

40

90

120

95

112

93

95

219

223

567350有序列

12,23,5,6,7,29,43,57,87,36,40,90,120,95,112,93,95,219,223,567,350查找112從前向后依次比較，比較15次順序比較29

90

219

5670

6

12

1812235672943578736409012095112939521922356735001234567891011121314151617181920（2）再在塊中順序比較，比較3次。合計(jì)6次。當(dāng)問題規(guī)模n較大時(shí)，效率比順序比較明顯提高。分塊查

（1）先在索引表中找塊，<219，比較3次；找112在記錄存儲地址和關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系，直接定位存放位置。依據(jù)關(guān)鍵字直接求取存放位置。順序存儲，元素存儲位置由其關(guān)鍵字決定。散列表查找思想特點(diǎn)存儲要求散列表查找哈希函數(shù)：確定記錄關(guān)鍵字與記錄存儲地址之間對應(yīng)關(guān)系的函數(shù)。哈希表：應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并記錄存入該地址，采用此方法構(gòu)造的表叫哈希表，也叫散列表。散列表的構(gòu)造哈希函數(shù)哈希函數(shù)的選擇哈希函數(shù)設(shè)定靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可。直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址。平方取中法：將關(guān)鍵字平方后取中間幾位作為哈希地址。除留余數(shù)法：取關(guān)鍵字被某個(gè)數(shù)除后所得余數(shù)作哈希地址。沖突的解決兩個(gè)關(guān)鍵字的哈希地址相等，或空間已被占用，稱為沖突。開放定址法：當(dāng)沖突發(fā)生時(shí)，形成某個(gè)探測序列；按此序列逐個(gè)探測散列表中的其他地址，直到找到一個(gè)空地址為止。線性探測法是最常用的方法之一（探測下一個(gè)相鄰地址）。再哈希法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，利用不同的哈希函數(shù)計(jì)算新的哈希地址，直到不發(fā)生沖突為止。散列表查找過程例如，有關(guān)鍵字序列：

67

81

52

73

44

91

27

36

20

39。存儲空間大?。?3地址計(jì)算規(guī)則：L=K

MOD

13；沖突解決機(jī)制：線性探測0123456789101112529167812744392073361211414111散列表查找時(shí)比較次數(shù)查找成功的ASL=17/10=1.73.17

插入排序設(shè)n

個(gè)記錄的序列為{R1

,R2

,R3

,...,Rn

}相應(yīng)的關(guān)鍵字序列為{K1

,K2

,K3

,...,Kn

}若一個(gè)排列p1

,p2

,p3

,...,pn

，使得相應(yīng)的關(guān)鍵字滿足非遞減關(guān)系。排序的概念將待排序列中元素重新調(diào)換位置，使其按關(guān)鍵字有序的過程。待排序的記錄數(shù)較少：所有的記錄都能存放在內(nèi)存中，稱為內(nèi)部排序。待排序的記錄數(shù)較多：排序過程中必須在內(nèi)、外存之間進(jìn)行數(shù)據(jù)交換，稱為外部排序。排序內(nèi)部排序外部排序排序的分類排序思想插入排序選擇排序交換排序基本

排序方法常見內(nèi)部排序方法穩(wěn)定排序：同值關(guān)鍵字排序前后相對位置絕對不變不穩(wěn)定排序：同值關(guān)鍵字排序前后相對位置可能改變待排序列3158869排序后：3688915排序后：3688915穩(wěn)定的不穩(wěn)定穩(wěn)定排序算法不穩(wěn)定排序算法將關(guān)鍵字的插入到已排序序列的適當(dāng)位置完成排序。插入排序直接插入排序?qū)⒋判虻挠涗汻i，插入到已排好序的記錄表R1,R2

,….,Ri-1中，得到一個(gè)新的、記錄數(shù)增加1的有序序列。需要N-1趟。希爾排序縮小增量排序：待排序列按增量分組，每組進(jìn)行直接插入排序；縮小增量后重復(fù)該過程，直至有序。每一趟將待排序的記錄，按其關(guān)鍵字的大小插入到已排序的適當(dāng)位置；N-1趟。方法簡單，易于實(shí)現(xiàn)順序存儲直接插入排序思想特點(diǎn)存儲要求直接插入排序初始，令第1

個(gè)元素作為初始有序表；依次插入第2

,3

,…,k

個(gè)元素，構(gòu)造新的有序表；直至最后一個(gè)元素；直接插入排序算法主要應(yīng)用比較和移動兩種操作。算法步驟例如，有待排序列：37，26，30，56，78，28，37。初始：

有序序列{37}

待排序列{26，30，56，78，28，37}第1趟：有序序列{26，37}待排序列{30，56，78，28，37}第2趟：有序序列{26，30，37}待排序列{56，78，28，37}第3趟：有序序列{26，30，37，56}待排序列{78，28，37}第3趟：有序序列{26，30，37，56}待排序列{78，28，37}第4趟：有序序列{26，30，37，56，78}待排序列{28，37}第5趟：有序序列{26，28，30，37，56，78}待排序列{37}第6趟：有序序列{26，28，30，37，37，56，78}待排序列{}每趟有序序列增1，待排序列減1；N個(gè)關(guān)鍵字，需要n-1趟；穩(wěn)定的排序算法，O(n2)3.18

交換排序和選擇排序穩(wěn)定排序算法冒泡排序：相鄰元素比較交換位置，O(n2)快速排序：一趟排序?qū)⒋庞涗浄殖蓛刹糠?，一部分的關(guān)鍵字均比另一部分關(guān)鍵字小。不穩(wěn)定排序算