2.3.1線性表的鏈式存儲—鏈表鏈式存儲不要求邏輯上相鄰的數據元素在物理位置上也相鄰，僅通過指針來映射數據元素之間的邏輯關系。存儲結點包含數據域：所有存元素本身的信息；指針域：元素之間邏輯關系的信息；包含有后繼結點的地址信息。循環隊列：將存儲隊列的數組頭尾相接。如何解決假溢出？01234入隊出隊a3a4fronta5rearreara6隊列的順序存儲結構及實現（順序隊列）不存在物理的循環結構，但可用軟件方法實現。求模：（4＋1）mod5＝0如何實現循環隊列？01234入隊出隊a3a4frontreara6隊列的順序存儲結構及實現（順序隊列）a5append

job1append

job2append

job3Popjob1append

job4append

job5Popjob2append

job6append

job7append

job8【0】【1】【2】【3】【4】【5】rearfront空隊：front=rearjob11rear2job23job3rear45job4front6job5rear7front8job69job710job8rear隊滿：front=rear3.2.2隊列的順序存儲結構及其實現---幾個問題1、當rear指向數組的最大下標的時候，如何向下標為0的位置改變？2、隊空和隊滿的條件都是front=rear,如何區分？3、如何表示出隊和入隊操作？【0】【1】【2】【3】【4】【5】CDEfrontrearBMaxSize=6chardata[MaxSize];rear=5rear=?data[rear]=‘F’;rear=(rear+1)%MaxSize3.2.2隊列的順序存儲結構及其實現---問題一

循環隊列首尾相連,這可以利用除法取余的運算(％)來實現:

隊首指針進1:front=(front+1)％MaxSize

隊尾指針進1:rear=(rear+1)％MaxSize

循環隊列的隊頭指針和隊尾指針初始化時都置0:front=rear=0。在入隊元素和出隊元素時,指針都按順時針方向進1。隊空和隊滿的條件都是front=rear,如何區分？

rear

0

1

2

3

4

front

(a)空隊

rear

0

1

2

3

4

front

(e)出隊多

次,

隊空

front==rear

rear

0

1

2

3

4

front

(e),隊滿

ABCDEfront==rear3.2.2隊列的順序存儲結構及其實現---問題二循環隊的入隊和出隊操作示意圖

rear

0

43

2

1

front

(a)空隊

(b)a,b,c入隊

0

4

3

2

1

front

c

b

ar0

4

3

2

1d

c

b

afront

(c)d入隊,隊滿

reara隊滿：(rear+1)%MaxSize==front

怎樣區分隊空與隊滿之間的差別呢?在入隊時少用一個數據元素空間,以隊尾指針加1等于隊首指針判斷隊滿,即隊滿條件為:

(q->rear+1)%MaxSize==q->front隊空條件仍為:

q->rear==q->front假設以數組sq[0..7]存放循環隊列元素，變量f指向隊頭元素的前一個位置，變量r指向隊尾元素，如果用A和D分別表示入隊和出隊操作，請回答如下問題：執行操作訓練A4D2A6時的狀態.（A3表示三次入隊操作，D1表示一次出隊操作）A4r=4,f=0D2f=2,r=4A6溢出1.1通俗定義樹形表示法樹的括號表達式a(b(e,f,g),c(h),d(i,j))會根據括號表達式畫出樹形圖7.1.3樹的基本術語

1.樹的結點：包含一個數據元素和指向其子樹的所有分支。

2.結點的度：一個結點擁有的子樹的個數。

A

C

G

J

B

E

D

F

I

H

M

K

L

樹形表示法

AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支結點與葉結點：度不為零的結點稱為非終端結點,又叫分支結點。度為零的結點稱為終端結點或葉結點。4.樹的度：樹中所有結點的度的最大值max(D(I))。含義：樹中最大分支數為樹的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3

A

C

G

B

D

I

JEFH

MKL

樹形表示法

樹的度：3結點所在層數：根結點的層數為1；對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層。樹的深度：樹中所有結點的最大層數，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJC樹的基本術語 5.7.2.1二叉樹概念二叉樹也稱為二次樹或二分樹，它是結點數為0或當節點數不為0時每個結點最多只有左右兩棵子樹的樹。特點是：（1）每個結點最多只有兩棵樹，既不存在度大于2的結點。（2）子樹有左右之分，不能顛倒。思考：二叉樹和度為2的樹一樣嗎有什么區別？度為2的樹中至少有一個節點的度為2，而二叉樹沒有此要求。結點孩子的有序性：度為2的樹不區分左右樹，二叉樹嚴格區分。二叉樹的特點：⑴每個結點最多有兩棵子樹；⑵二叉樹是有序的，其次序不能任意顛倒。

7.2.1二叉樹的邏輯結構注意：二叉樹和樹是兩種樹結構。ABCDEFGABAB二叉樹的基本形態Ф空二叉樹只有一個根結點左子樹根結點只有左子樹右子樹根結點只有右子樹左子樹右子樹根結點同時有左右子樹二叉樹的邏輯結構二叉樹的邏輯結構具有3個結點的樹和具有3個結點的二叉樹的形態二叉樹和樹是兩種樹結構。特殊的二叉樹斜樹1.所有結點都只有左子樹的二叉樹稱為左斜樹；2.所有結點都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統稱為斜樹。1.在斜樹中，每一層只有一個結點；2.斜樹的結點個數與其深度相同。

二叉樹的邏輯結構---斜樹的特點：ABCABC滿二叉樹在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點：葉子只能出現在最下一層；只有度為0和度為2的結點。CDEFGHIJKLMNO1112131415特殊的二叉樹二叉樹的邏輯結構---滿二叉樹?不是滿二叉樹，雖然所有分支結點都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結點個數最多滿二叉樹在同樣深度的二叉樹中葉子結點個數最多A1523467BCDEFGLM89特殊的二叉樹二叉樹的邏輯結構---完全二叉樹對一棵具有n個結點的二叉樹按層序編號，如果編號為i（1≤i≤n）的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉樹二叉樹的邏輯結構---在滿二叉樹中，從最后一個結點開始，連續去掉任意個結點，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結點10與滿二叉樹中的結點10不是同一個結點特殊的二叉樹二叉樹的邏輯結構---1.葉子結點只能出現在最下兩層，且最下層的葉子結點都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結點，只可能有一個，且該結點只有左孩子。

3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點CDEFGHIJ特殊的二叉樹二叉樹的邏輯結構---7.2.2二叉樹性質（5個）

性質1非空二叉樹上第i層上至多有2i-1個結點,這里應有i≥1。

性質2高度為h的二叉樹至多有2h-1個結點(h≥1)。證明：深度為h的二叉樹的最大結點數是二叉樹中每層結點的最大數之和，即=20+21+22+……+2h-1=2h-1(等比級數求和)

性質3非空二叉樹上葉結點數等于度為2的結點數加1。有如下關系：n0=n2+1

證明：設二叉樹上葉結點數為n0,單分支結點數為n1,雙分支結點數為n2,則總結點數n=n0+n1+n2。在一棵二叉樹中,度為i(i=0,1,2)的結點，有i個孩子。孩子數=n1+2n2。由于二叉樹中除根結點以外,每個結點都是另一個結點的孩子,因此二叉樹中有：孩子數=總結點數-1=n-1。由上述三個等式可得：n1+2n2=n-1=n0+n1+n2-1即：n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉樹

在一棵二叉樹中,如果所有分支結點都有左孩子結點和右孩子結點,并且葉結點都集中在二叉樹的最下一層,這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹。可以對滿二叉樹的結點進行連續編號,約定編號從樹根為1開始,按照層數從小到大、同一層從左到右的次序進行。圖中每個結點外邊的數字為對該結點的編號。每一層上結點樹都達到最大度為1的結點n1=0完全二叉樹:若二叉樹中度小于2的結點只能出現在最大層或次大層,并且最下面一層的葉結點都依次排列在該層最左邊的位置上,則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對完全二叉樹中每個結點進行連續編號,編號的方法同滿二叉樹相同。

性質4具有n個(n＞0)結點的完全二叉樹的高（深）度為log2n+1。證明：設深度為H余下的性質是針對完全二叉樹的：證明：假設具有n個結點的完全二叉樹的深度為k，根據完全二叉樹的定義和性質2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結點數最多結點數

log2n+1[log2n]log2n[log2n]+1k所在區間證明：假設具有n個結點的完全二叉樹的深度為k，根據完全二叉樹的定義和性質2，有下式成立

2k-1≤n＜2k性質4

具有n個結點的完全二叉樹的深度為log2n+1。

對不等式取對數，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數，故必有k＝log2n+1一棵具有n個結點的完全二叉樹中從1開始按層序編號，則結點i的雙親結點為

i/2；結點i的左孩子為2i；結點i的右孩子為2i＋1。

在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系。完全二叉樹的基本性質

思考題：二叉樹和樹的區別有哪些？7.8哈夫曼樹與哈夫曼編碼

哈夫曼(Huffman)樹，又稱最優二叉樹，是一類帶權路徑長度最短的樹。概念：兩結點間的路徑：從一結點到另一結點所經過的結點序列。路徑長度：從樹中一個結點到另一個結點之間路徑上的分支數。樹的路徑長度：樹根到每一個結點的路徑長度之和稱為。4123567結點1到5之間的路徑：（1）（2）（5）結點1到5之間的路徑長度：2樹的路徑長度：1+1+2+2+2+2=10定理：對于具有n個葉子節點的哈夫曼樹，共有2n-1個節點。樹的帶權路徑長度WPL：設樹中有M個葉結點，每個葉結點帶一個權值WK，樹根到每一個葉結點K的路徑長度為LK則WPL=。哈夫曼樹：WPL最小的樹稱為最優二叉樹，又稱哈夫曼樹7A5B4C2DWPL=7*2+5*2+4*2+2*2=36相關概念葉子結點的權值：對葉子結點賦予的一個有意義的數值量。

二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和。記為：WPL=7.8哈夫曼樹及哈夫曼編碼?=nkkklw1第k個葉子的權值；從根結點到第k個葉子的路徑長度哈夫曼樹：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹。例：給定4個葉子結點，其權值分別為{2，3，4，7}，可以構造出形狀不同的多個二叉樹。

7.8哈夫曼樹及哈夫曼編碼WPL=32WPL=41WPL=30234723477423哈夫曼樹的特點：1.權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。2.只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.

7.8哈夫曼樹及哈夫曼編碼2347WPL=32WPL=41WPL=3023477423哈夫曼樹的構造過程

abcd2347(a)c4d7ab5(b)d7cab9(c)dcab16(d)哈夫曼算法基本思想：⑴初始化：由給定的n個權值{w1，w2，…，wn}構造n棵只有一個根結點的二叉樹，從而得到一個二叉樹集合F＝{T1，T2，…，Tn}；⑵選取與合并：在F中選取根結點的權值最小的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；⑶刪除與加入：在F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到F中；

⑷

重復⑵、⑶兩步，當集合F中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。

7.8哈夫曼樹及哈夫曼編碼W＝{2，3，4，5}

哈夫曼樹的構造過程7.8哈夫曼樹及哈夫曼編碼重復第2步54325549重復第3步554932哈夫曼樹的構造過程

例1：W={5,29,7,8,14,23,3,11}7.8哈夫曼樹及哈夫曼編碼前綴編碼：一組編碼中任一編碼都不是其它任何一個編碼的前綴。前綴編碼保證了在解碼時不會有多種可能。P196例7.15：一組字符{A,B,C,D,E,F,G,H}出現的頻率分別是{7,19,2,6,32,3,21}，設計最經濟的編碼方案。答案參考教材哈夫曼樹應用——哈夫曼編碼8.1圖的基本概念8.1.1圖的定義（多對多）

圖(Graph)G由兩個集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點的有限集合V(G),E是連接V中兩個不同頂點的邊的有限集合,記為E(G)。

1

3

0

2

4

(a)

8.1.2圖的基本概念和術語基本術語頂點：圖中數據元素弧（邊）：有向圖：由頂點和弧構成的圖（圖a）無向圖：由頂點和邊構成的圖（圖b）無向完全圖：無向圖有n(n-1)/2條邊(圖8.2a)有向完全圖:有向圖有n(n-1)個弧(圖8.2b)權：與圖的邊或弧相關的數值叫做權網：帶權的圖稱為網12453573841628.1.2圖的基本術語1.頂點的度、入度和出度在無向圖中,頂點所具有的邊的數目稱為該頂點的度。在有向圖中,以頂點vi為終點的弧的數目,稱為該頂點的入度。以頂點vi為始點的弧的數目,稱為該頂點的出度。一個頂點的入度與出度的和為該頂點的度。

圖的存儲方法很多，但是目標是相同的。即不僅要存儲圖中各個頂點的數據信息，還要存儲頂點與頂點之間的關系（邊或弧）。兩種存儲方法：鄰接矩陣（數組存儲）鄰接表8.2圖的存儲結構

8.2圖的存儲結構

8.2.1鄰接矩陣存儲方法（教材P207) 鄰接矩陣是一個（n×n）階方陣，n為圖的頂點數，它的每一行分別對應圖的各個頂點，它的每一列也分別對應圖的各個頂點。我們規定矩陣的元素為：

無向圖的鄰接矩陣

DCBAAúúúú?ùêêêê?é=0111101111011110A

B

C

D

有向圖的鄰接矩陣8.2.2鄰接表存儲方法

圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。在鄰接表中,對圖中每個頂點建立一個單鏈表,對于無向圖鏈表中每個結點表示與該頂點相鄰接的一個頂點；對于有向圖則表示以該頂點為起點的一條邊的終點。

無向圖的鄰接表VA

B

C

D∧

A

B

D

∧

A

C

D

∧

A

B

C

∧

VBVCVD有向圖的鄰接表

AVBVCV

C

∧

B

C∧

B∧

8.3圖的遍歷8.3.1圖的遍歷的概念從圖中某一頂點出發訪遍圖中其余結點，且使每一個頂點僅被訪問一次，這一過程稱為圖的遍歷圖的遍歷有兩種：深度優先搜索廣度優先搜索。深度優先搜索過程：從圖中某個初始頂點v出發，首先訪問初始頂點v，然后選擇一個與頂點v相鄰且沒有被訪問過的頂點w為初始頂點，再從w出發進行深度優先遍歷，直到圖中與當前頂點v鄰接的所有頂點都被訪問過為止。遞歸調用

圖的深度優先遍歷例子深度優先遍歷序列：12485367深度優先遍歷序列：12485367訪問結點1訪問結點2訪問結點4訪問結點8訪問結點5訪問結點3訪問結點6訪問結點7

例如,以上圖的鄰接表為例調用DFS()函數,假設初始頂點編號v=2,寫出深度優先遍歷序列。

圖的廣度優先遍歷例子廣度優先遍歷序列：12345678訪問結點1訪問結點2訪問結點3訪問結點4訪問結點5訪問結點6訪問結點7訪問結點8廣度優先遍歷過程：首先訪問初始頂點v，接著訪問頂點v的所有未被訪問過的鄰接點v1，v2，v3..vt，然后在按照v1，v2，v3..vt的次序訪問每一個頂點的所有未被訪問過的鄰接點，以此類推，直到途中所有和初始頂點v有路徑相通的頂點都被訪問過為止。

一個有向圖的鄰接表深度優先序列：13452廣度優先序列：132458.3.3廣度優先搜索遍歷

廣度優先搜索遍歷的過程是：首先訪問初始點vi,接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,訪問每一個頂點的所有未被訪問過的鄰接點,依次類推,直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。

1、已知一個有無向圖的鄰接矩陣P208圖8.5A1.根據無向圖的鄰接矩陣，寫出無向圖的鄰接表存儲結構。圖8.6(a).

根據無向圖的深度優先遍歷算法，寫出從頂點v0出發所得到的頂點序列。(3)根據無向圖的廣度優先遍歷算法，寫出從頂點v0出發所得到的頂點序列。2、給定某圖求其深度優先搜索遍歷和廣度優先搜索遍歷。8.4圖的應用----生成樹和最小生成樹最小生成樹的概念可以應用到許多實際問題中。例：在n個城市之間建造通信網絡，至少要架設n-1條通信線路，而每兩個城市之間架設通信線路的造價是不一樣的，那么如何設計才能使得總造價最小？

應用實例——計算機網絡傳輸的問題：怎樣找到一種最經濟的方式，從一臺計算機向網上所有其它計算機發送一條消息。8.4圖的應用----生成樹和最小生成樹8.4.1生成樹的概念在一個無向連通圖G中，含有N個頂點（1）N個頂點（2）N-1條邊（3）無環路最小生成樹生成樹中，每個邊都有權值，權值總和最小的樹。8.4.2普里姆算法普里姆算法求解最小生成樹的過程

5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

0

2

(b)

1

0

2

5

(c)

1

4

0

2

3

5

(d)

1

4

2

0

2

1

3

5

(e)

1

5

4

2

0

2

1

3

4

5

(f)

1

3

4

2

5

普里姆(prim)算法描述假設G=(V,E)是一個具有n個頂點的連通網絡，T=(U,TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空。算法開始時，首先從V中任取一個頂點（假定為V1），將此頂點并入U中，此時最小生成樹頂點集U={V1}；然后從那些其一個端點已在U中，另一個端點仍在U外的所有邊中，找一條最短（即權值最小）的邊，假定該邊為(Vi,Vj),其中Vi∈U，Vj∈V-U,并把該邊(Vi,Vj)和頂點Vj分別并入T的邊集TE和頂點集U；普里姆(prim)算法描述續如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到n-1次后，把所有n個頂點都并入生成樹T的頂點集U中，此時U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。普里姆算法中每次選取的邊兩端，總是一個已連通頂點（在U集合內）和一個未連通頂點（在U集合外），故這個邊選取后一定能將未連通頂點連通而又保證不會形成環路。克魯斯卡爾算法求解最小生成樹的過程4

1

0

2

1

3

4

5

(a)

1

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

0

2

1

3

4

5

(d)

1

4

2

(e)

0

2

1

3

4

5

1

3

4

2

5

2

2

3

3

0

0

3

5

4

1

0

03

3

1

1

0

0

3

3

1

1

0

0

0

0

1

1

1

1

1

1

5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

8.4.3克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法是一種按權值的遞增次序選擇合適的邊來構造最小生成樹的方法。假設G=(V,E)是一個具有n個頂點的帶權連通無向圖,T=(U,TE)是G的最小生成樹,則構造最小生成樹的步驟如下：

(1)置U的初值等于V(即包含有G中的全部頂點),TE的初值為空集(即圖T中每一個頂點都構成一個分量)。

(2)將圖G中的邊按權值從小到大的順序依次選取：若選取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止。已知某帶權無向圖，用普里姆算法求其最小生成樹，寫出算法過程。粘圖？？

AOE網絡AOE網絡有向圖邊表示活動(ActivityOnEdge)的網絡，簡稱為AOE網絡頂點表示事件，弧表示事件完成的過程也就是活動，弧上的權值表示完成該項活動需要的時間。源點：入度為0，表示工程的開始匯點：出度為0，表示工程的結束事件V:表示以它為弧頭的所有活動已經結束，也表示以它為弧尾的活動可以開始了。求關鍵路徑首先分別求出活動的最早發生時間與最遲發生時間，然后利用兩者之差是否為0來確定關鍵活動，因為活動的最早發生時間與最晚發生時間為0就意味著該活動的時間余量，時間余量為0的活動為關鍵活動。

例如,下圖表示某工程的AOE網。共有9個事件和11項活動。其中A表示開始事件,I表示結束事件。根據三元組畫出AOE網（1，2，3）a1（1，3，2）a2（2，4，2）a3（3，4，4）a5粘圖9.2順序查找structRecord{intkey;……};Recordr[n];

無監視哨的順序查找:

intSeqSearch(Recordr[],intn,intk)

{

inti=0;

while(i<n&&r[i].key!=k)i++;

if(i<n)returni;

elsereturn-1;

}

順序查找的平均查找長度為：順序查找的特點：算法簡單，但查找效率低。9.3二分查找

二分查找又稱為折半查找。

二分查找要求順序表是有序的。二分查找的基本思想是：首先將待查的K值與有序表R[0]到R[n-1]的中間位置mid上的結點的關鍵字進行比較，若相等，則查找完成；否則，若

R[mid].key>K，則說明待查找的結點只可能在左子表R[0]到R[mid-1]中，只需在左子表中繼續查找；否則在右子表R[mid+1]到R[n-1]中繼續查找。這樣，經過一次關鍵字的比較就縮小了一半的查找區間。如此進行下去，直到找到為止（當然也存在最后找不到的可能）。例:[0513192137566475808892][0513192137]566475808892051319[2137]566475808892查找K=21的過程（查找成功）[0513192137566475808892]051319213756[6475808892]051319213756647580[8892]查找K=85的過程（查找失敗）051319213756647580[8892]9.4Hash查找1.基本概念

Hash,哈希,也稱為散列.

Hash是一種重要的存儲方法，也是一種常見的查找方法。它的基本思想是：以數據元素的關鍵字K為自變量，通過一個確定的函數關系，計算出對應的函數值f(K)，把這個值作為數據元素的存儲地址。查找時也是根據這個函數計算其存儲位置。【例】假設一組記錄的關鍵字分別為{18，27，1，20，22，6，10，13，41，15，25}。選取關鍵字與記錄位置間的函數為f(key)=key%11。Hash函數----關鍵字與記錄位置間的函數.Hash地址----據Hash函數計算出的存儲位置.Hash表----存儲記錄的查找表,該表中根據Hash函數計算出的存儲位置.基于Hash表的查找稱為Hash查找。在建立Hash表時，若Hash函數是一個一對一的函數，則在查找時，只需根據散列函數對給定值進行某種運算，即可得到待查數據的存儲位置。在一般情況下，Hash表的空間必須比數據的集合大，此時雖然浪費了一定的空間，但換取的是查找效率。設散列表的空間大小為m，填入表中的數據個數為n，則稱α=n/m為散列表的裝填因子。Hash函數的選取原則是：運算盡可能簡單；函數的值域必須在表長的范圍內；盡可能使得關鍵字不同時，其散列函數值亦不相同。若某個Hash函數對于不相等的關鍵字計算出了相同的

Hash地址，則稱該現象為hash沖突，發生沖突的兩個關鍵字該Hash函數的同義詞。在實際應用中，不產生沖突的Hash函數極少存在。例9.9假設哈希表長度m=13，采用除留余數法加線性探查法建立如下關鍵字集合的哈希表(16,74,60,43,54,90,46,31,29,88,77)并計算查找成功和查找不成功時候的平均查找長度。提示：n=11(記錄個數)m=13（表長）h(key)=key%pp應該為小于等于m素數二叉排序樹特點、判斷什么樣的樹是二叉排序樹，P257二叉排序樹上的重要性質。10.7堆排序堆排序是選擇排序的改進（1964提出）。在排序過程中，將r[1]到r[n]看成是一個完全二叉樹順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小元素。堆的定義：n個數據序列K1,k2,...,Kn稱為堆，當且僅當該序列滿足特性：

此種情況稱為小頂堆。或者，均大于也可以。此種情況情況稱為大頂堆。從堆的定義可以看出，堆實質上是滿足如下性質的二叉樹：樹中任一非葉子結點的值均小于等于它的孩子結點的值。