數(shù)據(jù)結(jié)構(gòu)：思想與方法-第七章課件

1、1第7章 集合與靜態(tài)查找表 集合的基本概念查找的基本概念無序表的查找有序表的查找STL中的靜態(tài)表1第7章 集合與靜態(tài)查找表 集合的基本概念2集合的基本概念集合中的數(shù)據(jù)元素除了屬于同一集合之外，沒有任何邏輯關(guān)系。在集合中，每個數(shù)據(jù)元素有一個區(qū)別于其他元素的唯一標(biāo)識，通常稱為鍵值或關(guān)鍵字值集合的主要運算：查找某一元素是否存在將集合中的元素按照它的唯一標(biāo)識排序2集合的基本概念集合中的數(shù)據(jù)元素除了屬于同一集合之外，沒有任3集合的存儲任何容器都能存儲集合常用的表示形式是借鑒于線性表或樹唯一一個僅適合于存儲和處理集合的數(shù)據(jù)結(jié)構(gòu)是散列表 3集合的存儲任何容器都能存儲集合4第7章 集合與靜態(tài)查找表 集合的基本

2、概念查找的基本概念無序表的查找有序表的查找STL中的靜態(tài)表4第7章 集合與靜態(tài)查找表 集合的基本概念5查找的基本概念用于查找的集合稱之為查找表 查找表的分類：靜態(tài)查找表 動態(tài)查找表。 內(nèi)部查找外部查找5查找的基本概念用于查找的集合稱之為查找表 6靜態(tài)查找表的存儲靜態(tài)查找表可以用順序表存儲。 如C+的標(biāo)準(zhǔn)模板庫中的類模板vector，或第二章中定義的seqList查找函數(shù)應(yīng)該是一個函數(shù)模板。模板參數(shù)是數(shù)據(jù)元素的類型。6靜態(tài)查找表的存儲靜態(tài)查找表可以用順序表存儲。 如C+的標(biāo)7第7章 集合與靜態(tài)查找表 集合的基本概念查找的基本概念無序表的查找有序表的查找STL中的靜態(tài)表7第7章 集合與靜態(tài)查找表

3、集合的基本概念8無序表的查找無序表：數(shù)組中的元素是無序的無序表的查找：毫無選擇只能做線性的順序查找 template int seqSearch(vector &data, const Type &x) data0 = x; for (int i = data.size() + 1; x != datai; -i); return i; 8無序表的查找無序表：數(shù)組中的元素是無序的template 9第7章 集合與靜態(tài)查找表 集合的基本概念查找的基本概念無序表的查找有序表的查找STL中的靜態(tài)表9第7章 集合與靜態(tài)查找表 集合的基本概念10有序表的查找順序查找二分查找插值查找分塊查找10有序表的查

4、找順序查找11順序查找與無序表的順序查找類似，只是當(dāng)被查元素在表中不存在時，不需要查到表尾template int seqSearch(vector &data, const Type &x) data0 = x; for (int i = data.size() + 1; x datai; -i); if ( i = 0 | x != datai) return 0; else return i; 11順序查找與無序表的順序查找類似，只是當(dāng)被查元素在表中不存12有序表的查找順序查找二分查找插值查找分塊查找12有序表的查找順序查找13二分查找每次檢查待查數(shù)據(jù)中排在最中間的那個元素如中間元素等于

5、要查找的元素，則查找完成否則，確定要找的數(shù)據(jù)是在前一半還是在后一半，然后縮小范圍，在前一半或后一半內(nèi)繼續(xù)查找。 13二分查找每次檢查待查數(shù)據(jù)中排在最中間的那個元素14查找 x=8012mid=4 但 key=9 10, 向左key 4 8 9 10 11 13 1934567high=7low=1012mid=2 找到key 4 8 9 10 11 13 1934567high=7low=114查找 x=8012mid=4 但 key=9 10,15template int binarySearch(const vector &data, const Type &x) int low = 1,

6、 high = data.size() + 1, mid; while (low = high ) /查找區(qū)間存在 mid = (low + high) / 2; /計算中間位置 if ( x = datamid ) return mid; if ( x datamid) high = mid - 1; else low = mid + 1; return 0; 15template 16有序表的查找順序查找二分查找插值查找分塊查找16有序表的查找順序查找17插值查找適用于知道數(shù)據(jù)的大致分布情況查找位置的估計 缺點：計算量大17插值查找適用于知道數(shù)據(jù)的大致分布情況18插值查找適用情況訪問一個數(shù)

7、據(jù)元素必須比一個典型的指令費時得多。例如，數(shù)組可能在磁盤里而不是在內(nèi)存里，而且每次比較都需要訪問一次磁盤。這些數(shù)據(jù)必須不僅有序，而且分布相當(dāng)均勻，這可以使每次估計都相當(dāng)準(zhǔn)確，可以將大量的數(shù)據(jù)排除出查找范圍。這樣，花費這些計算代價是值得的 18插值查找適用情況訪問一個數(shù)據(jù)元素必須比一個典型的指令費時19有序表的查找順序查找二分查找插值查找分塊查找19有序表的查找順序查找20分塊查找分塊查找也稱為索引順序塊的查找。它把整個有序表分成若干塊，塊內(nèi)的數(shù)據(jù)元素可以是有序存儲，也可以是無序的，但塊之間必須是有序的。 20分塊查找分塊查找也稱為索引順序塊的查找。21塊內(nèi)最大關(guān)鍵字174460塊起始地址061

8、4369101417192334373940424446485158600123456789101112131415161718查找由兩個階段組成：查找索引和查找塊 21塊內(nèi)最大關(guān)鍵字174460塊起始地址0614369122第7章 集合與靜態(tài)查找表 集合的基本概念查找的基本概念無序表的查找有序表的查找STL中的靜態(tài)表22第7章 集合與靜態(tài)查找表 集合的基本概念23STL中的靜態(tài)表對應(yīng)于順序查找和二分查找，C+的標(biāo)準(zhǔn)模板庫中提供兩個模板函數(shù)：find和binary_search。這兩個函數(shù)模板都位于標(biāo)準(zhǔn)庫algorithm中 find函數(shù)順序查找一個序列find有兩個模板參數(shù)。第一個模板參數(shù)是

9、對應(yīng)于存儲集合數(shù)據(jù)的容器的迭代器。第二個模板參數(shù)是集合元素的類型。函數(shù)有三個形式參數(shù)。第一、二個形式參數(shù)是兩個迭代器對象，指出查找的范圍。第三個參數(shù)是需要查找的對象值。find函數(shù)的返回值是一個迭代器對象，指出了被查找的元素在容器中的位置。23STL中的靜態(tài)表對應(yīng)于順序查找和二分查找，C+的標(biāo)準(zhǔn)模24binary_searchbinary_search函數(shù)用二分查找的方式查找一個有序序列。它也有兩個模板參數(shù)。第一個模板參數(shù)是對應(yīng)于存儲集合數(shù)據(jù)的容器的迭代器。第二個模板參數(shù)是集合元素的類型。函數(shù)也有三個形式參數(shù)。第一、二個形式參數(shù)是兩個迭代器對象，指出查找的范圍。第三個參數(shù)是需要查找的對象值。函

10、數(shù)的返回值是bool類型的，指出了被查找的元素在容器中是否存在。如果存在，返回true，否則，返回false。24binary_searchbinary_search函數(shù)25應(yīng)用實例#include #include #include using namespace std;int main() int a = 2,4,7,8,10,12,13,15,16,19,20; vector v; vector:iterator itr; for (int i=0; i11; +i) v.push_back(ai); if (binary_search(v.begin(), v.end(),13) cout 13 存在n; else cout 13 不存在n; itr = find(v.begin(), v.end(),13); cout *itr endl; return 0; 25應(yīng)用實例#include 26總結(jié)本章介紹了集合關(guān)