——類C描述

數據結構 DATA STRUCTURE

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

查找表是由同一類型的數據元素(或記錄)構成的集合。

何謂查找表 ？

由于“集合”中的數據元素之間存在著松散的關系，因此查找表是

一種應用靈便的結構。

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

1)查詢某個“特定的”數據元素是否在查找表中；

對查找表經常進行的操作:

2)檢索某個“特定的”數據元素的各種屬性；

3)在查找表中插入一個數據元素；

4)從查找表中刪去某個數據元素。

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

◆ 靜態(tài)查找表

查找表可分為兩類:

◆ 動態(tài)查找表

僅作查詢和檢索操作的查找表為靜態(tài)查找表。

有時在查詢之后，還需要將“查詢”結果為“不在查找表中”

的數據元素插入到查找表中；或者，從查找表中刪除其“查詢”

結果為“在查找表中”的數據元素,此類表為動態(tài)查找表。

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

◆ 關鍵字

查找表可分為兩類:

◆ 主關鍵字

用來標識一個數據元素（或記錄）的某個數據項的值，稱為關鍵

字。

若此關鍵字可唯一地標識一個記錄，則稱此關鍵字是主關鍵字；

◆ 次關鍵字

反之，用以識別若干記錄的關鍵字是次關鍵字。

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

◆ 查找

查找表可分為兩類:

根據給定的某個值，在查找表中確定一個其關鍵字等于給定

值的數據元素或(記錄)

若查找表中存在這樣一個記錄，則稱“查找成功”。查找結果給

出整個記錄的信息，或指示該記錄在查找表中的位置；

否則稱“查找不成功”。查找結果給出“空記錄”或“空指針”。

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

假設靜態(tài)查找表的順序存儲結構為

typedef struct {

ElemType *elem;

// 數據元素存儲空間基址，建表時

// 按實際長度分配，0號單元留空

int length; // 表的長度

} SSTable;

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

數據元素類型的定義為:

typedef struct {

keyType key; // 關鍵字域

… … // 其它屬性域

} ElemType ; TElemType ;

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

一、順序查找表

以順序表或線性鏈表表示靜態(tài)查找表

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

21 37 88 19 92 05 64 56 80 75 13

0 1 2 3 4 5 6 7 8 9 10 11

ST.Length

ST.elem i

21 37 88 19 92 05 64 56 80 75 13

0 1 2 3 4 5 6 7 8 9 10 11

ST.Length

ST.elemi

60

i

key=64

key=60

i

64

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

int Search_Seq(SSTable ST,

KeyType key) {

// 在順序表ST中順序查找其關鍵字等于

// key的數據元素。若找到，則函數值為

// 該元素在表中的位置，否則為0。

ST.elem[0].key = key; // “哨兵”

for (i=ST.length; ST.elem[i].key!=key; --i);

// 從后往前找

return i; // 找不到時，i為0

} // Search_Seq

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

分析順序查找的時間性能

查找算法的平均查找長度 (Average Search Length)

為確定記錄在表中的位置，需和給定值進行比較的關鍵字次數的

期望值稱為查找算法在查找成功時的平均查找長度。

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

對于含有n個數據元素的表,查找成功時的平均查找長度為:

n

ASL=ΣPiCi

i=1

其中:Pi為查找第i個數據元素的概率,且

1

1

? =

=

n

i

Pi

Ci為查到第i個數據元素時,需要進行的比較次數.

點擊添加相關標題文字 《數據結構》

A D D R E L A T E D T I T L E W O R D S

順序查找

對順序表而言， Ci取決于所查元素所處的位置：

-查找記錄是A[n]時,僅需比較一次;

-查找記錄是A[1]時,要比較n次;

-查找記錄是A[i]時,要比較n-i+1次.

ASL = nP1 +(n-1)P2 + … +2Pn-1+Pn

2

1

1

1

1

+

= ? ? + =

=

n

(n i )

n

ASL

n

i

s s

在等概率查找的情況下，

順序表查找的平均查找長度為：

n

Pi

1

=

本節(jié)結束