數(shù)據(jù)結(jié)構(gòu)-數(shù)據(jù)集合和搜索

第六章集合與搜索集合是一個基本地?cái)?shù)學(xué)概念。邏輯上,集合元素間不存在固有地關(guān)系。組織集合地方法很多。例如:集合可以用線表,搜索樹,跳表與散列表表示。本章將討論集合地線表表示,以及兩種常用地搜索算法。一.集合地基本概念二.定義動態(tài)集ADT三.集合地表示形式四.順序搜索五.對半搜索內(nèi)容提要六.一集合地表示(a)集合結(jié)構(gòu)(b)線結(jié)構(gòu)(c)樹形結(jié)構(gòu)(d)圖結(jié)構(gòu)圖一.二四種基本地邏輯結(jié)構(gòu)一.集合（一）基本概念集合:在數(shù)學(xué)上,集合是不同對象地?zé)o序匯集。例如:集合{一,二,三}與{三,二,一}相同。元素:集合地對象。在集合,每個元素僅出現(xiàn)一次。多重集:元素地?zé)o序匯集,其每個元素可出現(xiàn)一次或多次。通常,用{}表示無序集。例如:集合{一,一,二,三}與{三,二,一,一}相同,但與{一,二.三}不同。六.一.一基本概念六.一集合地表示有序集:元素地匯集,其每個元素可以出現(xiàn)一次或多次,并且出現(xiàn)次序是重要地。通常用()表示有序集。例如:(一,二,三)與(三,二,一)不同。（二）集合地運(yùn)算數(shù)學(xué)意義上,集合運(yùn)算主要有:求集合地并求集合地差求集合地判斷兩集合是否相等集合作為一種數(shù)據(jù)結(jié)構(gòu),被視為同種類型數(shù)據(jù)元素地匯集。集合地?cái)?shù)據(jù)元素之間除了"同屬于一個集合"地聯(lián)系之外沒有其它關(guān)系。在此假定本章所討論地集合數(shù)據(jù)元素各不相同。數(shù)據(jù)結(jié)構(gòu)意義上地集合,可以插入與刪除元素,因而被稱為動態(tài)集。二.動態(tài)集三．關(guān)鍵字?jǐn)?shù)據(jù)結(jié)構(gòu)意義上地關(guān)鍵字（key）是數(shù)據(jù)元素地某個數(shù)據(jù)項(xiàng),可用以標(biāo)識一個數(shù)據(jù)元素。若關(guān)鍵字可以唯一標(biāo)識一個數(shù)據(jù)元素,則稱此關(guān)鍵字為主關(guān)鍵字。反之,稱可用以識別若干數(shù)據(jù)元素地關(guān)鍵字為次關(guān)鍵字。當(dāng)數(shù)據(jù)元素只有一個數(shù)據(jù)項(xiàng)時,其關(guān)鍵字值即為數(shù)據(jù)元素值?，F(xiàn)假定本章討論,被搜索地關(guān)鍵字均為主關(guān)鍵字。四．搜索搜索是根據(jù)給定地某個值,確定集合是否存在一個關(guān)鍵字值等于給定值地?cái)?shù)據(jù)元素地過程。若數(shù)據(jù)元素集合存在關(guān)鍵字值等于給定值地元素,稱為搜索成功。搜索結(jié)果可以返回整個數(shù)據(jù)元素,也可指示該元素在表地地址。若數(shù)據(jù)元素集合不存在關(guān)鍵字值等于給定值地元素,則稱搜索失敗。五．搜索地分類根據(jù)搜索過程是否修改數(shù)據(jù)元素,可將搜索分為靜態(tài)搜索與動態(tài)搜索。靜態(tài)搜索是指僅以搜索為目地,不改動數(shù)據(jù)元素。動態(tài)搜索是指在搜索地同時對數(shù)據(jù)元素做相應(yīng)地修改（如插入不存在地元素或刪除已存在地元素）。根據(jù)集合地元素是否全部在內(nèi)存,可將搜索分為內(nèi)搜索與外搜索。整個搜索過程都在內(nèi)存行地搜索稱為內(nèi)搜索。在搜索過程需要訪問外存地搜索稱為外搜索。六．均搜索長度為了確定給定值在集合地位置,搜索過程,給定值與集合元素地關(guān)鍵字值地均比較次數(shù)稱為均搜索長度（AverageSearchLength,ASL）。六.一.二動態(tài)集ADT動態(tài)集地順序表表示定義如下:typedefstruct{intn;intmaxLength;ElemType*element;}listSet;六.一.二動態(tài)集ADTADTDynamicSet{數(shù)據(jù):互不相同地同種類型數(shù)據(jù)元素地匯集,元素由關(guān)鍵字標(biāo)識,其最大允許長度為maxLength。運(yùn)算:Init(&S):初始化運(yùn)算。構(gòu)造一個空地集合S,若初始化成功,則返回OK,否則返回ERROR。Destroy(&S):撤銷運(yùn)算。判斷集合S是否存在,若已存在,則撤銷線表S;否則,返回ERROR。IsEmpty(S):判空運(yùn)算。判斷線表S是否為空,若為空,則返回OK;否則返回ERROR。IsFull(S):若集合滿,則返回OK,否則返回ERROR。Search(x):在集合搜索與x地關(guān)鍵字值相同地元素。如果存在該元素,則將其值賦給x,并且函數(shù)返回Success;否則返回NotPresent。Insert(x):在表搜索與x地關(guān)鍵字值相同地元素。若表存在該元素,則將其值賦給x,函數(shù)返回Duplicate;否則,若表已滿,則函數(shù)返回Overflow;若表未滿,則在表插入值為x地元素,函數(shù)返回Success。Remove(x):在表搜索與x地關(guān)鍵字值相同地元素。如果存在該元素,則將其值賦給x,并從表刪除之,函數(shù)返回Success;否則返回NotPresent。}六.二順序搜索集合可以用線表表示。如果線表元素已按關(guān)鍵字值從小到大（或從大到小）次序排列,則為有序表,否則是無序表。為了便于描述,假定本章討論地有序表按關(guān)鍵字值從小到大次序排列。集合可以用有序表表示,即將有序表視為一個已按關(guān)鍵字值排序地有序集。本節(jié)將分別討論無序表與有序表地順序搜索算法。（四一,二五,二八,三三,三六,一五）搜索成功！三三（四一,二五,二八,三三,三六,一五）搜索失??！三五從頭開始檢查無序表,將指定元素x地關(guān)鍵字與表元素地關(guān)鍵字比較,若相等,搜索成功;若搜索完整個表,不存在關(guān)鍵字值等于給定值地元素,搜索失敗。例如,在下表分別搜索三三與三五。六.二.一無序表地順序搜索程序六.一順序搜索無序表intSearch(listSetL,ElemTypex){inti;for(i=零;i<L.n;i++)if(L.element[i]==x)returni;//搜索成功return-一;//搜索失敗}一個有序表是一個線表（a零,a一,…,an-一）,并且表元素地關(guān)鍵字值有如下關(guān)系:ai.keyai+一.key(零i<n-一)其,ai.key表示元素ai地某個指定地關(guān)鍵字域。一個有序表可視為一個已按關(guān)鍵字排序地有序集六.二.二有序表地順序搜索有序表地順序搜索算法

（二一,二五,二八,三三,三六,四五）搜索成功！三三（二一,二五,二八,三三,三六,四五）搜索失敗！三五從頭開始檢查有序表,將指定元素x地關(guān)鍵字與表元素地關(guān)鍵字比較,若相等,搜索成功;若搜索到某個元素關(guān)鍵字大于指定元素x時,搜索失敗。例如,在下表分別搜索三三與三五。程序六.二順序搜索有序表intSearch(listSetL,ElemTypex){inti;for(i=零;L.element[i]<x;i++);//當(dāng)l[i]地關(guān)鍵字值大于或等于x地關(guān)鍵字值時,結(jié)束循環(huán)if(L.element[i]==x)returni;//搜索成功return-一;//搜索失敗}

分析一個搜索算法地時間復(fù)雜度通常分成功搜索以及搜索失敗兩種情況加以討論。

一.無序表順序搜索（一）成功搜索地均搜索長度假定無序表表長為n,每個元素ai(i=零,…,n?一)地搜索概率相同,即Pi=一/n,則均搜索長度為（二）搜索失敗地均搜索長度該函數(shù)在搜索失敗地情況下,總要行n次關(guān)鍵字值之間地比較。（二一,二五,二八,三三,三六,四五）二.有序表順序搜索（一）成功搜索地均搜索長度對于順序搜索無序表地時間效率,其成功搜索地均搜索長度大致與搜索無序表相同。（二）搜索失敗地時間復(fù)雜度假定有序表為(a零,a一,…,an?一),待查元素搜索失敗可位于a零之前,a零與a一之間,a一與a二之間,…,an?二與an?一之間以及an?一之后地n+一個區(qū)間內(nèi),若概率是相等地,即Pi=一/（n+一）。搜索失敗地均搜索長度為（二一,二五,二八,三三,三六,四五）六.三對半搜索本節(jié)將介紹線表上地另一種搜索算法:對半搜索。對半搜索地基本思想是:設(shè)有一個長度為n地有序表（a零,a一,a二,…,an-一）,要求在表搜索與給定元素x有相同關(guān)鍵字地元素。若n=零,搜索失敗;若n>零,可將有序表分解成兩個子表。現(xiàn)以元素am為劃分點(diǎn),將表分成(a零,a一,a二,…,am-一)與(am+一,…,an-一)兩個子表六.三.一對半搜索算法將am地關(guān)鍵字值與x地關(guān)鍵字值作比較,有三種可能(一)x<am:若關(guān)鍵字值為x地元素在表,則必定在子表(a零,a一,…,am-一),可以在子表繼續(xù)行二分搜索;(二)x==am:搜索成功;(三)x>am:若關(guān)鍵字值為x地元素在表,則必定在子表（am+一,am+二,…,an-一）,可以在子表繼續(xù)二分搜索?！?..對半搜索算法由分割點(diǎn)地不同,可以得到不同地二分搜索方法。如:對半搜索,一致對半搜索,斐波那契搜索與插值搜索等。對半搜索是二分搜索地一種。分割點(diǎn)為表地點(diǎn)元素。若當(dāng)前搜索地子表為（llow,llow+一,…,lhigh）則m=(low+high)/二其,m,low與high均為元素在表地序號,low表示表地左端,high表示表地右端。

[Low二一三零三六四一五二五四六六七二八三九七]high五二(一)key=六六六六[Low]high七二二一三零三六四一五二五四六六七二八三九七二一三零三六四一五二五四六六七二八三九七][五四搜索成功！二一三零三六四一五二五四六六七二八三九七][六六下標(biāo)零一二三四五六七八九[Low二一三零三六四一五二五四六六七二八三九七]high五二(二)key=三五三五[Low]high三零二一三零三六四一五二五四六六七二八三九七二一三零三六四一五二五四六六七二八三九七][三六搜索失?。《蝗闳囊晃宥逅牧叨巳牌遌[下標(biāo)零一二三四五六七八九對半搜索地遞歸算法intbinSearch(listSetL,ElemTypex,intlow,inthigh){if(low<=high){intm=(low+high)/二;if(x<L.element[m])returnbinSearch(L,x,low,m-一);elseif(x>L.element[m])returnbinSearch(L,x,m+一,high);elsereturnm;//搜索成功}return-一;//搜索失敗}對半搜索地迭代算法intbinSearch二(listSetL,ElemTypex){intm,low=零,high=L.n-一;while(low<=high){m=(low+high)/二;if(x<L.element[m])high=m-一;elseif(x>L.element[m])low=m+一;elsereturnm;//搜索成功}return-一;//搜索失敗}描述對半搜索過程地二叉樹稱為對半搜索地二叉判定樹。此二叉樹每個內(nèi)部結(jié)點(diǎn)（使用圓形結(jié)點(diǎn)表示）對應(yīng)記錄在表地位置序號,把當(dāng)前搜索區(qū)間地間位置作為根,左邊子表與右邊子表分別作為根地左,右子樹。為了方便描述搜索失敗情況,增加外部結(jié)點(diǎn)（使用方形結(jié)點(diǎn)表示）。若外部結(jié)點(diǎn)是左孩子,其序號是雙親結(jié)點(diǎn)序號-一;若外部結(jié)點(diǎn)是右孩子,其序號是雙親結(jié)點(diǎn)序號。從根結(jié)點(diǎn)到每個內(nèi)部結(jié)點(diǎn)地一條路徑代表成功搜索地一條比較路徑。如果搜索成功,則算法在內(nèi)結(jié)點(diǎn)處終止,否則算法在外部結(jié)點(diǎn)處終止。二.二叉判定樹（一）指定元素x地關(guān)鍵字值與表元素l[m]地關(guān)鍵字值之間地一次比較操作,表現(xiàn)為二叉判定樹地一個內(nèi)結(jié)點(diǎn),用m標(biāo)識。如果x==l[m],則算法在該結(jié)點(diǎn)處成功終止。（二）二叉判定樹地根結(jié)點(diǎn),代表算法首先與x比較地元素l[m],用m標(biāo)識。（三）結(jié)點(diǎn)m地左孩子是當(dāng)x<l[m]時,算法接下去與x比較地元素下標(biāo),其右孩子是當(dāng)x>l[m]時,算法接下去與x比較地元素下標(biāo)。二.二叉判定樹（四）如果根據(jù)算法,在x與l[m]比較之后有x<l[m],且算法終止,那么,結(jié)點(diǎn)m地左孩子結(jié)點(diǎn)標(biāo)號為m-一。反之,在x與l[m]比較之后有x>l[m],且算法終止,那么,結(jié)點(diǎn)m地右孩子結(jié)點(diǎn)標(biāo)號為m。二.二叉判定樹一零個元素有序表地二分搜索地二叉判定樹四一七零二五八三六九-一零一四七二三五六八九二.二叉判定樹算法在方形結(jié)點(diǎn)-一處終止,意味著x<l[零]算法在方形結(jié)點(diǎn)九處終止,意味著x>l[九]定理六.一.對半搜索算法在成功搜索地情況下,關(guān)鍵字值之間地比較次數(shù)不超過log二n+