【正文】 1 第七章 搜索結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)電子教案 2 ? 靜態(tài)搜索表 ? 二叉搜索樹 ? 最優(yōu)二叉搜索樹 ? AVL樹 ? 伸展樹 ? 紅黑樹 第七章 搜索結(jié)構(gòu) 3 搜索 (Search)的概念 靜態(tài)搜索表 ? 所謂 搜索 ，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。 ? 搜索的結(jié)果通常有兩種可能： ?搜索成功 ，即找到滿足條件的數(shù)據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中 的位置 , 還可給出該對(duì)象中的具體信息。 ?搜索不成功 ，或搜索失敗。作為結(jié)果，應(yīng)報(bào)告一些信息 , 如失敗標(biāo)志、位置等。 4 ? 通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象 (或記錄 )組成。 ? 在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為 關(guān)鍵碼 。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。 但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。 ? 實(shí)施搜索時(shí)有兩種不同的環(huán)境。 ? 靜態(tài)環(huán)境 ，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。 ? 靜態(tài)搜索表 5 ? 動(dòng)態(tài)環(huán)境 ，為保持較高的搜索效率 , 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 ? 動(dòng)態(tài)搜索表 ? 在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)組元素的下標(biāo)作為數(shù)據(jù)元素的存放地址。搜索算法根據(jù)給定值 k，在數(shù)組中進(jìn)行搜索。直到找到 k 在數(shù)組中的存放位置或可確定在數(shù)組中找不到 k 為止。 靜態(tài)搜索表 6 數(shù)據(jù)表與搜索表的類定義 include include const int defaultSize = 100。 template class E, class K class dataList。 //數(shù)據(jù)表類的前視定義 template class E, class K class dataNode { //數(shù)據(jù)表中結(jié)點(diǎn)類的定義 friend class dataListE, K。 //聲明其友元類為 dataList public: 7 dataNode (const K x) : key(x) { } //構(gòu)造函數(shù) K getKey() const { return key。 } //讀取關(guān)鍵碼 void setKey (K x) { key = x。 } //修改關(guān)鍵碼 private: K key。 //關(guān)鍵碼域 E other。 //其他域（視問題而定） }。 template class E, class K class dataList { //數(shù)據(jù)表類定義 public: 8 dataList (int sz = defaultSize) : ArraySize(sz), CuurentSize(0) { Element = new dataNodeE, K[sz]。 assert (Element != NULL)。 } dataList (dataListE, Kamp。 R)。 //復(fù)制構(gòu)造函數(shù) virtual ～ dataList() { delete []Element。 } //析構(gòu)函數(shù) virtual int Length() { return CurrentSize。 } //求表的長度 virtual K getKey (int i) const { //提取第 i（ 1開始）元素值 9 assert (i 0 || i = CurrentSize)。 return Element[i1].key。 } virtual void setKey (K x, int i) { //修改第 i（ 1開始）元素值 assert (i 0 || i = CurrentSize)。 Element[i1].key = x。 } virtual int SeqSearch (const K x) const。 //搜索 virtual bool Insert (Eamp。 e1)。 //插入 virtual bool Remove (K x, Eamp。 e1)。 //刪除 friend ostreamamp。 operator (ostreamamp。 out, const dataListE, Kamp。 OutList)。 //輸出 10 friend istreamamp。 operator (istreamamp。 in, dataListE, Kamp。 InList)。 //輸入 protected: dataNodeE, K *Element。 //數(shù)據(jù)表存儲(chǔ)數(shù)組 int ArraySize, CurrentSize。 //數(shù)組最大長度和當(dāng)前長度 }。 template class E, class K bool dataListE, K::Insert (Eamp。 e1) { //在 dataList的尾部插入新元素 , 若插入失敗函數(shù)返 //回 false, 否則返回 true. 11 if (CurrentSize == ArraySize) return false。 Element[CurrentSize] = e1。 //插入在尾端 CurrentSize++。 return true。 }。 template class E, class K bool dataListE, K::Remove (K x, Eamp。 e1) { //在 dataList中刪除關(guān)鍵碼為 x的元素 , 通過 e1返回。 //用尾元素填補(bǔ)被刪除元素。 if (CurrentSize == 0) return false。 for (int i == 0。 i CurrentSize amp。amp。 Element[i] != x。 i++)。 //在表中順序?qū)ふ? 12 if (i == CurrentSize) return false。 //未找到 e1 = Element[i].other。 //找到 ,保存被刪元素的值 Element[i] = Element[CurrentSize1]。 //填補(bǔ) CurrentSize。 return true。 }。 template class E, class K ostreamamp。 operator (ostreamamp。 out, const dataListE,Kamp。 OutList) { out “存儲(chǔ)數(shù)組大小” endl。 數(shù)據(jù)表類的友元函數(shù) 13 for (int i = 1。 i = 。 i++) out [i1] ? ?。 out endl。 //輸出表的所有表項(xiàng)到 out out “數(shù)組當(dāng)前長度 : ” endl。 //輸出表的當(dāng)前長度到 out return out。 }。 template class E, class K istreamamp。 operator (istreamamp。 in, dataListE, Kamp。 InList) { 14 cout “輸入存儲(chǔ)數(shù)組當(dāng)前長度 : ”。 in 。 //從 in輸入表的當(dāng)前長度 cout “輸入數(shù)組元素的值 : \n”。 for (int i = 1。 i = 。 i++) { //從 in輸入表的全部表項(xiàng) cout “元素 ” i “ : ”。 in [i1]。 } return in。 }。 15 ? 順序搜索主要用于在線性表中搜索。 ? 設(shè)若表中有 CurrentSize 個(gè)元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值 x 進(jìn)行比較 ? 若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。 ? 若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與 x 相等的元素，則搜索失敗。給出失敗信息。 順序搜索（ Sequential Search） 16 ? 一般的順序搜索算法在第二章已經(jīng)討論過，本章介紹一種使用“監(jiān)視哨”的順序搜索方法。 ? 設(shè)在 數(shù)據(jù)表 dataList 中順序搜索關(guān)鍵碼與 給定值 x 相等的數(shù)據(jù)元素，要求數(shù)據(jù)元素在表中從下標(biāo) 0 開始存放 , 下標(biāo)為 CurrentSize 的元素作為控制搜索過程自動(dòng)結(jié)束的“監(jiān)視哨”使用。 ? 若搜索成功，則函數(shù)返回該元素在表中序號(hào) Location（比下標(biāo)大 1） , 若搜索失敗，則函數(shù)返回 CurrentSize+1。 17 使用監(jiān)視哨的順序搜索算法 template class E, class K int dataListE, K::SeqSearch (const K x) const { Element[CurrentSize].key = x。 int i = 0。 //將 x設(shè)置為監(jiān)視哨 while (Element[i].key != x) i++。 //從前向后順序搜索 return i+1。 }。 const int Size = 10。 main () { 18 dataListint L1 (Size)。 //定義 int型搜索表 L1 int Target。 int Loc。 cin L1。 cout L1。 //輸入 L1 cout “Search for a integer : ”。 cin Target。 //輸入要搜索的數(shù)據(jù) if ( (Location = (Target)) != () ) cout “找到待查元素位置在：” Loc+1 endl。 //搜索成功 else cout “ 沒有找到待查元素 \n”。 //搜索不成功 }。 19 ? 設(shè)數(shù)據(jù)表中有 n 個(gè)元素，搜索第 i 個(gè)元素的概率為 pi，搜索到第 i 個(gè)元素所需比較次數(shù)為 ci，則搜索成功的平均搜索長度 : ? 在順序搜索并設(shè)置“監(jiān)視哨”情形： ci = i +1, i = 0, 1, ? , n1，因此 ?????????1010niiniiis u c c pcpA S L ) 1 ( .)(110??? ??ipA S Lniis u c c順序搜索的平均搜索長度 20 ? 一般表中各個(gè)元素的搜索概率不同，如果按搜索概率的高低排列表中的元素，從有序順序表的情況可知，能夠得到高的平均搜索長度。 ? 在等概率情形， p