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

查找表為線性表，其存儲(chǔ)結(jié)構(gòu)為一維結(jié)構(gòu)數(shù)組，也即是順序表，數(shù)組的每一個(gè)元素對(duì)應(yīng)查找表的一個(gè)記錄。為簡(jiǎn)單起見(jiàn)，設(shè)記錄中只有一個(gè)整數(shù)關(guān)鍵字，存放記錄的結(jié)構(gòu)體類(lèi)型描述如下：

typedef struct{int key； /*存放關(guān)鍵字的成員項(xiàng)*/…… /*其它成員項(xiàng)*/} NODE；

順序查找

順序查找的算法

在該算法中，while循環(huán)語(yǔ)句中包含兩個(gè)判斷條件，勢(shì)必會(huì)影響查找的速度，因此要盡可能地減少判斷條件以提高效率。這里介紹一個(gè)編程小技巧來(lái)達(dá)到這一目的。具體做法是：在順序表的末尾設(shè)置一個(gè)監(jiān)視哨a[n].key，開(kāi)始查找之前，先將給定關(guān)鍵字的值k賦給a[n].key，這樣循環(huán)中就不用判斷整個(gè)表是否查找完畢。具體算法如下：

改進(jìn)的順序查找算法

int search(NODE a[],int n, int k)/*在a[0]～a[n-1]中順序查找關(guān)鍵字等于k的記錄。查找成功時(shí)返回該記錄的下標(biāo)，失敗時(shí)返回-1*/{int i=0;a[n].key=k;while(a[i].key!=k)i++;if(i>=n)return -1; /*查找成功*/elsereturn i; /*查找失敗*/}

順序查找的基本操作是關(guān)鍵字的比較。查找成功的最好情況是第一個(gè)記錄就符合查找要求，只需進(jìn)行一次比較；最壞情況是第n個(gè)記錄符合查找要求，要進(jìn)行n次比較。若每個(gè)記錄的查找概率相等，即pi=1/n，且每次都是成功查找，則順序查找的平均查找長(zhǎng)度為：

對(duì)于算法8-2，查找不成功時(shí)關(guān)鍵字的比較次數(shù)為n＋1，順序查找的算法時(shí)間復(fù)雜度為O（n）。