數據結構與算法

(C#語言版)

DataStructure&AlgorithminC#第8章查找算法電子信息學院IPLTableofContents第1章緒論第2章線性表第3章棧與隊列第4章串第5章數組和廣義表第6章樹和二叉樹第7章圖第8章查找算法第9章排序算法本章位置TableofContents8.0簡介8.1查找與查找表8.2線性表的查找8.3二叉查找樹及其查找算法8.4哈希查找8.0Introductionsearch：查找操作是在數據結構中尋找滿足某種給定條件的數據元素的過程。查找是數據處理中經常使用的一種重要運算，也是程序設計中的一項重要的基本技術。生活中經常用到查找，如在字典中查找單詞，在電話簿中查找電話號碼等。本章介紹查找的基本概念，討論多種經典查找技術，包括線性表的順序、折半和分塊查找算法，二叉排序樹的查找算法以及哈希查找算法。8.1查找與查找表8.1.1查找的基本概念8.1.2C#內建數據結構中的查找操作1.關鍵字、查找操作、查找表與查找結果關鍵字：是數據元素（或記錄）中用于識別該元素的某個域。若此關鍵字可以唯一地標識一個記錄，則稱之謂“主關鍵字”。若此關鍵字能識別若干記錄，則稱之謂“次關鍵字”。查找:根據給定的某個值，在數據集合中確定一個其關鍵字等于給定值的數據元素（或記錄）。查找表是由同一類型的數據元素(或記錄)構成的集合，待查找的數據集合。查找操作與查找結果若查找表中存在滿足條件的記錄，則稱“查找成功”，查找結果：給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結果：給出“空記錄”或“空指針”。對查找表經常進行的操作:查詢某個“特定的”數據元素是否在查找表中；檢索某個“特定的”數據元素的各種屬性；在查找表中插入一個數據元素；從查找表中刪去某個數據元素。2.靜態查找表與動態查找表靜態查找表:

僅作查詢和檢索操作的查找表。例如，字典是一個靜態查找表。動態查找表:

有時在查詢之后，還需要將“查詢”結果為“不在查找表中”的數據元素插入到查找表中；或者，從查找表中刪除其“查詢”結果為“在查找表中”的數據元素。例如，電話簿則是一個動態查找表。3.如何進行查找？查找的方法與查找表的結構。如果數據元素之間不存在明顯的組織規律，則不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關系，換句話說，用另外一種結構來表示數據集合。查找的方法與查找表的規模：數據量較小的線性表，可以采用順序查找算法。例如個人電話簿。數據量較大時，采用分塊查找算法。例如在字典中查找單詞。4.查找算法的性能評價衡量查找算法效率的最主要標準是平均查找長度（AverageSearchLength,ASL）。ASL是指查找過程所需進行的關鍵字比較次數的平均值。pi是要查找數據元素的出現概率，ci是查找相應數據元素需進行的關鍵字比較次數。考慮概率相等的情況，pi=1/n。查找成功和查找不成功的平均查找長度通常不同，分別用ASL成功和ASL不成功表示。8.1.2C#內建數據結構中的查找操作以Array、List、ArrayList、Hashtable和Dictionary為例介紹其中的查找操作方面的內容。Array、List和ArrayList類都提供了多種重載(overloaded)形式的IndexOf方法實現查找操作，Array類的IndexOf方法都是靜態方法intIndexOf<T>(T[]array,Tvalue);

intIndexOf<T>(T[]array,Tvalue,intstartindex,intcount);

二分查找BinarySearch方法對于已按關鍵字值排序的數組，可用更高效的二分查找方法：intBinarySearch<T>(T[]array,Tvalue);intBinarySearch<T>(T[]array,intstartindex,intcount,Tvalue);返回給定數據在數組指定范圍內首次出現位置。如果找到value，則返回其索引。如果找不到value，則返回值一個負數re，并且它的按位補碼i=~re正好是將value插入array并保持其排序的正確位置。{29365356707379799999}502，rv=-3Hashtable與DictionaryHashtable與Dictionary都提供了表示（鍵，值）對的集合，這些（鍵，值）對根據鍵的哈希碼進行組織。它們的元素可以直接通過鍵來索引。usingSystem;using

System.Collections.Generic;public

static

voidMain(){Dictionary<string,string>openWith=new

Dictionary<string,string>();

openWith.Add("txt","notepad.exe");

openWith.Add(“bmp”,“paint.exe”);

openWith[“doc”]=“winword.exe”;if(!openWith.ContainsKey(“doc”)){

Console.WriteLine(“Key\”doc\“isnotfound.”);}}8.2線性表查找技術8.2.1順序查找8.2.2折半查找8.2.3分塊查找8.2.1順序查找順序查找(sequentialsearch)又稱線性查找(linearsearch)，是一種最基本的查找算法。對于給定k，從線性表的指定位置開始，依次與每個數據元素的關鍵字進行比較，直到查找成功，或到達線性表的指定邊界時仍沒有找到這樣的數據元素，則查找不成功。以順序表或線性鏈表表示靜態查找表。順序查找表的定義LinearSearchList類實現順序表的順序查找算法。public

class

LinearSearchList<T>whereT:IComparable{privateT[]items;//存儲數據元素的數組private

intcount;//順序表的長度intcapacity=0;//順序表的容量

……}

順序查找算法的實現public

intIndexOf(Tk){intj=0;while(j<count&&!items[j].Equals(k))j++;if(j>=0&&j<count)

returnj;elsereturn-1;}

單向鏈表中的查找操作public

int

IndexOf(Tk){

intj=0;

SingleLinkedNode<T>q=head.Next;

while(q!=null){

if(k.Equals(q.Item))returnj;q=q.Next;j++;}

return-1;}對于一個給定值k，從鏈表的第一個數據結點沿著鏈接的方向依次與各結點數據進行比較，直至查找成功或不成功。算法分析如果線性表中位置i處的元素的關鍵字等于k，進行i+1次比較即可找到該元素。設線性表中元素的個數為n，查找第i個元素的概率為pi，在等概率情況下，pi=1/n，對于成功的查找，其關鍵字的平均查找長度為：對于不成功的查找，其關鍵字的平均查找長度為順序查找算法的時間復雜度為O(n)

8.2.2二分查找對于有序表可用二分查找

(binarysearch)。假定元素按升序排列，對于給定值k，從表的中間位置開始比較，如果k等于當前數據元素的關鍵字，則查找成功。若k小于當前數據元素的關鍵字，則在表的前半部分繼續查找；反之，則在表的后半部分繼續查找。依次重復進行，直至獲得查找成功或不成功的結果。二分查找算法實現public

int

BinarySearch(Tk,int

si,intlength){

intmid=0,left=si;

int

right=left+length-1;while(left<=right){

mid=(left+right)/2;if(k.CompareTo(items[mid])==0)

return

mid;else

if(k.CompareTo(items[mid])<0)right=mid-1;elseleft=mid+1;}if(k.CompareTo(items[mid])>0)mid++;return

~mid;}測試二分查找算法

class

LinearSearchListTest{

static

voidMain(string[]args){intn=10;

var

sl=newLinearSearchList<int>(n);Randomize(sl,n);

Console.Write("隨機排列：");sl.Show(true);

Console.Write("排序后：");sl.Sort();sl.Show(true);

intk=50;int

re=sl.BinarySearch(k,0,n);

Console.WriteLine(“{0}{1},{2}”,k,re,~re);}

static

voidRandomize(LinearSearchList<int>sl,intn){

intk;Random

random=new

Random();

for(int

i=0;i<n;i++){k=random.Next(100);

sl.Add(k);}}程序運行結果隨機排列：LinearSearchList:73567953797099992936排序后

：LinearSearchList:2936535670737979999950-3,2算法分析二分查找的過程可以用一棵二叉判定樹表示，結點中的數字表示數據元素的序號。成功與不成功的平均查找長度為二分查找算法的時間復雜度為O(log2n)

8.2.3分塊查找分塊查找(blockingsearch)將數據存儲在若干數據塊中，每一塊中的數據順序存放，是否排序則不一定，但多個數據塊之間必須按數據的關鍵字排序(“塊間有序”)。假定數據塊遞增排列，每個數據塊的起始位置記錄在另外的一張索引表中。通過索引表的幫助，迅速縮小查找的范圍。靜態查找表的分塊查找靜態查找表只需存儲，查詢，不需插入、刪除。字典字典分塊查找算法的基本思想：將所有單詞排序后存放在數組dict中，并為字典設計一個索引表index，index的每個數據元素由兩部分組成：首字母和塊起始位置下標，它們分別對應于單詞的首字母和以該字母為首字母的單詞在dict數組中的起始下標。通過索引表，將較長的單詞表dict劃分成若干個數據塊，以首字母相同的的若干單詞構成一個數據塊，因此每個數據塊的大小不等，每塊的起始下標由index中對應“首字母”列的“塊起始位置下標”列標明。字典分塊查找算法使用分塊查找算法，在字典dict中查找給定的單詞token，必須分兩步進行：根據token的首字母，查找索引表index，確定token應該在dict中的哪一塊。在相應數據塊中，使用順序或折半查找算法查找token，得到查找成功與否的信息。在某一數據塊內進行的順序查找，可以通過順序查找表中的重載方法IndexOf來完成，以限定查找范圍。塊內順序查找public

intIndexOf(Tk,int

si,int

length){intj=si;

while((j<si+length)&&!items[j].Equals(k))j++;

if(j>=si&&j<si+length)

returnj;

else

return-1;}

動態查找表的分塊查找動態查找表:需增加或刪除數據元素。電話簿如以順序存儲結構保存數據，則進行插入、刪除操作時必須移動大量的數據元素，運行效率低。如果以鏈式存儲結構保存數據，雖然插入、刪除操作較方便，但花費的空間較多，查找的效率較低。以順序存儲結構和鏈式存儲結構相結合的方式來存儲數據元素，就可能既最大限度地利用空間，又有很高的運行效率。創建動態分塊查找表并測試定義DynamicLinearBlockSearchList類表示動態分塊查找表。對于數據序列：{10,6,23,5,2,26,33,36,43,41,40,46,49,57,54,53,67,61,71,74,72,89,80,93,92}DynamicLinearBlockSearchList類public

class

DynamicLinearBlockSearchList{private

LinearSearchList<int>[]Block;

private

int

Blocksize;

public

DynamicLinearBlockSearchList(intcapacity,int

bs){

Blocksize=bs;

Block=new

LinearSearchList<int>[capacity/bs];}}插入數據Add(intk)

public

voidAdd(intk){

inti=k/Blocksize;

if(Block[i]==null){Block[i]=newLinearSearchList<int>(Blocksize);}Block[i].Add(k);}分塊查找算法Contains(intk)

public

boolContains(intk){

inti=k/Blocksize;

boolfound=false;

if(Block[i]!=null){

Console.Write("searchk="+k+“Block["+i+"]\t");found=Block[i].Contains(k);}

returnfound;}

8.3二叉排序樹及其查找算法二叉排序樹又稱二叉查找樹(BinarySearchTree,BST)，它具有下述性質：若根結點的左子樹非空，則左子樹上所有結點的關鍵字值均≤根結點的關鍵字值。若根結點的右子樹非空，則右子樹上所有結點的關鍵字值均＞根結點的關鍵字值。根結點的左、右子樹也分別為二叉排序樹。二叉排序樹的中根遍歷序列是按升序排列的。BST及其中根遍歷序列例如序列:{6,3,2,5,8,1,7,4,9}建立的二叉樹它的中根遍歷序列是{1,2,3,4,5,6,7,8,9}二叉排序樹的建立1.二叉查找樹BinarySearchTree類定義二叉查找樹BinarySearchTree類，它繼承第六章中定義的二叉樹類BinaryTree，結點為BinaryTreeNode類。在二叉查找樹BinarySearchTree類中，Contains方法在樹中查找給定值，Add方法在樹中插入結點，構造方法為給定的數據序列建立二叉查找樹。public

class

BinarySearchTree<T>:

BinaryTree<T>whereT:IComparable{public

BinarySearchTree(T[]td){

Console.Write(“建立二叉排序樹：”);for(int

i=0;i<td.Length;i++){

Console.Write(td[i]+"");Add(td[i]);}

Console.WriteLine();}}2.在二叉排序樹中查找在一棵二叉排序樹中查找給定值k的算法描述如下：設p指向根結點。將k與p結點的關鍵字進行比較，若兩者相等，則查找成功；若k值較小，則進入p的左子樹繼續查找；若k值較大，則進入p的右子樹繼續查找，直到查找成功或p為空。p為非空時表示查找成功，p為空時表示查找不成功。查找算法Contains(Tk)

public

boolContains(Tk){

BinaryTreeNode<T>p=root;

Console.Write("search("+k+")=");

while(p!=null&&!k.Equals(p.Data)){

Console.Write(p.Data+"");

if(k.CompareTo(p.Data)<0)p=p.Left;elsep=p.Right;}

if(p!=null)

return

true;

elsereturn

false;}3.在二叉查找樹中插入結點如果是空樹，則建立數據結點并作為樹的根結點。否則從根結點開始，將數據k與當前結點的關鍵字進行比較，如果k值較小，則進入左子樹；如果k值較大，則進入右子樹。循環，直至當前結點為空結點。建立數據結點，并將新結點與最后訪問的結點進行比較，插到合適的位置。插入結點Add(Tk)

public

voidAdd(Tk){

BinaryTreeNode<T>p,q=null;

if(root==null)root=new

BinaryTreeNode<T>(k);//建立根結點

else{p=root;

while(p!=null){q=p;

if(k.CompareTo(p.Data)<=0)p=p.Left;

elsep=p.Right;}p=new

BinaryTreeNode<T>(k);

if(k.CompareTo(q.Data)<=0)q.Left=p;

elseq.Right=p;}}8.4哈希查找哈希(hash)意為雜湊也稱散列。哈希技術是一種按關鍵字編址的存儲和檢索數據方法。由數據元素的關鍵字決定它的存儲位置，即哈希函數值hash(k)，就是它的存儲位置。不需要進行多次比較，從而提高了查找的效率。如果關鍵字k1!=k2，有hash(k1)=hash(k2)，則表示不同關鍵字的多個數據元素映射到同一個存儲位置，與k1和k2對應的數據元素稱為同義詞。這種現象稱為沖突(collision)。哈希查找技術的關鍵問題被處理的數據一般來源于較大的集合，計算機系統地址空間則是有限的，因此哈希函數都是從大集合到小集合的映射，沖突是不可避免的。哈希查找技術的關鍵問題在于以下兩點：避免沖突(collisionavoidance)：設計一個好的哈希函數，盡可能減少沖突。解決沖突(collisionresolution)：發生沖突時，使用一種解決沖突的有效方法。8.4.2哈希函數的設計一個好的哈希函數的標準是，能將關鍵字值均勻地分布在整個空間中，使沖突的機會盡可能地減少。除留余數法:hash(k)=k%p平方取中法:將關鍵字值k2的中間幾位作為hash(k)的值，位數取決于哈希表的長度。例如，k=4731，k2=22382361，若表長為100，取中間兩位，則hash(k)=82。折疊法:將關鍵字分成幾部分，按照某種約定把這幾部分組合在一起。Hashtable類使用的哈希函數每種關鍵字都有自己的特殊性。不存在一種哈希函數對任何關鍵字集合都是最好的。在實際應用中，應該構造不同的哈希函數，以求達到最佳效果。應該考慮以下因素：哈希表的大小；關鍵字的性質和分布情況；數據元素的查找頻率以及計算哈希函數所需的時間。hash(key)={GetHash(key)+1+[GetHash(key)>>5+1]%(hashsize–1)}%hashsize8.4.3沖突解決方法沖突不可避免，當沖突發生時必須解決沖突。沖突解決方法：探測定址法再散列法散列鏈法1.探測定址法線性試探法：欲將數據k存放在i=hash(k)位置上。沖突則繼續探測下一個空位置。如哈希表已滿，再建立一個溢出表。序列：{19,14,23,1,32,86,55,3,62,10},hash(k)=k%7查找時，首先與哈希基表中i=hash(k)

位置的數據進行比較，如果該位置是k，則查找成功，否則繼續向后依次查找。如果在哈希基表中沒有找到，還要在溢出表中順序查找。2.再散列法再散列法中定義多個哈希函數：Hi=Hashi(key)當同義詞對一個哈希函數產生沖突時，計算另一個哈希函數，直至沖突不再發生。這種方法不易產生堆積現象，但增加了計算時間。3.哈希鏈法哈希鏈法：一般將數據元素存放在哈希基表的i=hash(k)

位置上。如果產生沖突，則創建一個結點存放該數據，并將該結點插入到由沖突的數據元素構成的哈希鏈表。序列：{19,14,23,1,32,86,55,3,62,10,16,17},hash(k)=k%7查找時，首先與base[hash(k)]

比較，相等表明查找成功。不等表明沖突，在由base[hash(k)].Next指向的哈希鏈表中按順序查找，確定查找是否成功。HashSearchList類的定義public

class

HashSearchList<T>{

private

Node<T>[]baseList;

public

HashSearchList(int

hashsize){

baseList=new

Node<T>[hashsize];}

public

HashSearchList():this(7){}

public

intHash(Tk){

return

k.GetHashCode()%baseList.Length;}…Add();Search();Show();插入數據Add(Tk)public

voidAdd(Tk){

Node<T>q=new

Node<T>(k);

inti=Hash(k);

if(baseList[i]==null)baseList[i]=q;

else{q.Next=baseList[i].Next;baseList[i].Ne