數(shù)據(jù)結(jié)構(gòu)-計(jì)算機(jī)系主頁(yè)

1、第六章 集合與字典,集合及其表示并查集與等價(jià)類字典散列,1,集合及其表示,集合是成員(元素)的一個(gè)群集。集合中的成員可以是原子(單元素)，也可以是集合。集合的成員必須互不相同。在算法與數(shù)據(jù)結(jié)構(gòu)中所遇到的集合，其單元素通常是整數(shù)、字符、字符串或指針，且同一集合中所有成員具有相同的數(shù)據(jù)類型。例：colour = { red, orange, yellow, green, black, blue, purple, white },

2、2,集合基本概念,集合中的成員一般是無(wú)序的，但在表示它時(shí)，常寫在一個(gè)序列里。常設(shè)定集合中的單元素具有線性有序關(guān)系，此關(guān)系可記作“<”，表示“優(yōu)先于”。整數(shù)、字符和字符串都有一個(gè)自然線性順序。指針也可依據(jù)其在序列中安排的位置給予一個(gè)線性順序。,3,集合（Set）的抽象數(shù)據(jù)類型,template class Set {public: virtual Set() = 0; //構(gòu)造函數(shù) virt

3、ual makeEmpty() = 0; //置空集合 virtual bool addMember (const T x) = 0;,4,,,,,,,,,,,,A?B 或 A+B A?B 或 A?B A-B,A,A,A,B,B,B,,,,,virtual bool delMember (const T x) = 0; virtual Set intersectWith (Se

4、t& R) = 0;//集合的交運(yùn)算 virtual Set unionWith (Set& R) = 0; //集合的并運(yùn)算 virtual Set differenceFrom (Set& R) = 0; //集合的差運(yùn)算 virtual bool

5、 Contains (T x) = 0; virtual bool subSet (Set& R) = 0; virtual bool operator == (Set& R) = 0; //判集合是否相等};,5,用位向量實(shí)現(xiàn)集合抽象數(shù)據(jù)類型,當(dāng)集合是全集合 { 0, 1, 2, …, n } 的一個(gè)子集，且 n 是不大的整數(shù)時(shí)，可用位(0,

6、1)向量來(lái)實(shí)現(xiàn)集合。當(dāng)全集合是由有限個(gè)可枚舉的成員組成時(shí)，可建立全集合成員與整數(shù) 0, 1, 2, …的一一對(duì)應(yīng)關(guān)系，用位向量來(lái)表示該集合的子集。一個(gè)二進(jìn)位有兩個(gè)取值1或0，分別表示在集合與不在集合。如果采用16位無(wú)符號(hào)短整數(shù)數(shù)組bitVector[ ]作為集合的存儲(chǔ)，就要考慮如何求出元素 i 在bitVector數(shù)組中的相應(yīng)位置。,6,集合的位向量(bit Vector)類的定義,#include #include const

7、 int DefaultSize = 50;template class bitSet {//用位向量來(lái)存儲(chǔ)集合元素, 集合元素的范圍在0到//setSize-1之間。數(shù)組采用16位無(wú)符號(hào)短整數(shù)實(shí)現(xiàn)public: bitSet (int sz = DefaultSize);//構(gòu)造函數(shù) bitSet (const bitSet& R);//復(fù)制構(gòu)造函數(shù) ～bitSet () { del

8、ete [ ]bitVector; }//析構(gòu)函數(shù) unsigned short getMember (const T x); //讀取集合元素x,7,void putMember (const T x, unsigned short v); //將值v送入集合元素x void makeEmpty () { //置空集合 for (int i = 0; i & operat

9、or = (const bitSet& R); bitSet& operator + (const bitSet& R); bitSet& operator * (const bitSet& R); bitSet& operator - (const bitSet& R); bool Contains (const T x);

10、 //判x是否集合this的成員,8,bool subSet (bitSet& R); //判this是否R的子集 bool operator == (bitSet& R); //判集合this與R相等 friend istream& operator >> (istream& in,

11、 bitSet& R); //輸入 friend ostream& operator & R); //輸出private: int setSize;//集合大小 int vectorSize;//位數(shù)組大小 unsigned short *bitVector; //存儲(chǔ)集合元素的位數(shù)組};

12、,9,使用示例,bitSet s1, s2, s3, s4, s5; bool index, equal; for (int k = 0; k < 10; k++) { //集合賦值 s1.addMember (k); s2.addMember(k+7);}//s1: {0, 1, 2, …, 9}, s2: {7, 8, 9, …, 16} s3 = s

13、1+s2; //求s1與s2的并 {0, 1, …, 16} s4 = s1*s2; //求s1與s2的交 {7, 8, 9} s5 = s1-s2; //求s1與s2的差 {0, 1, …, 6},10,//s1: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} //s4: {7, 8, 9} index = s1.subSet (s4); //判斷s1是

14、否為s4子集 cout << index << endl; //結(jié)果，index = 0 equal = (s1 == s2); //集合s1與s2比較相等 cout << equal << endl; //為0, 兩集合不等,11,構(gòu)造函數(shù)的實(shí)現(xiàn),template bitSet::bitSet (int sz) : setSize

15、 (sz) { //構(gòu)造函數(shù) assert (setSize > 0); //檢查參數(shù)的合理性 vectorSize = (setSize+15) >> 4;//存儲(chǔ)數(shù)組大小 bitVector = new unsigned short[vectorSize];//分配空間 assert (bitVector != NULL);//檢查存儲(chǔ)分配是否成

16、功 for (int i = 0; i < vectorSize; i++) bitVector[i] = 0;//初始化};,12,template unsigned short bitSet:: getMember (const T x) { //讀取集合元素x，x從0開始 int ad = x/16; int id = x%16; unsi

17、gned short elem = bitVector[ad]; return ((elem >> (15 - id)) %2);};,13,template void bitSet:: putMember (const T x, unsigned short v) { //將值v送入集合元素x int ad = x/16; int id = x%16; unsigned

18、short elem = bitVector[ad]; unsigned short temp = elem >> (15-id); elem = elem > (id+1));};,14,templatebitSet& bitSet:: //求集合this與R的并operator + (const bitSet& R) {assert (vector

19、Size == R.vectorSize); bitSet temp (vectorSize);for (int i = 0; i < vectorSize; i++) temp.bitVector[i] = bitVector[i] | R.bitVector[i]; return temp; //按位求"或", 由第三個(gè)集合返回};,15,template

20、bitSet& bitSet:: //求集合this與R的交operator * (const bitSet& R) { assert (vectorSize == R.vectorSize); bitSet temp (setSize); for (int i = 0; i < vectorSize; i++) temp.bitV

21、ector[i] = bitVector[i] & R.bitVector[i]; return temp; //按位求“與”, 由temp返回};,16,template bitSet& bitSet:://求集合this與R的差operator - (const bitSet& R) { assert (vectorSize == R.vectorSize); bitS

22、et temp (setSize); for (int i = 0; i < vectorSize; i++) temp.bitVector[i] = bitVector[i] & (~R.bitVector[i]); return temp;//由第三個(gè)集合返回};,17,18,集合的并,集合的交,集合的差,template bool bitSet::subSet (bi

23、tSet& R) {//判this是否R的子集 assert (setSize == R.setSize); for (int i = 0; i < vectorSize; i++) //按位判斷 if (bitVector[i] & (~R.bitVector[i])) return false;return true;};,19,template boo

24、l bitSet::operator == (bitSet& R) {//判集合this與R相等 if (vectorSize != R.vectorSize) return false; for (int i = 0; i < vectorSize; i++) if (bitVector[i] != R.bitVector[i]) return false;

25、 return true;//對(duì)應(yīng)位全部相等};,20,用有序鏈表實(shí)現(xiàn)集合抽象數(shù)據(jù)類型,用有序鏈表來(lái)表示集合時(shí)，鏈表中的每個(gè)結(jié)點(diǎn)表示集合的一個(gè)成員。各結(jié)點(diǎn)所表示的成員 e0, e1, …, en 在鏈表中按升序排列，即 e0 < e1 < … < en。集合成員可以無(wú)限增加。因此，用有序鏈表可以表示無(wú)窮全集合的子集。,21,用帶表頭結(jié)點(diǎn)的有序鏈表表示集合,,last,,last,集合的有序鏈表類的

26、定義,template struct SetNode {//集合的結(jié)點(diǎn)類定義 T data;//每個(gè)成員的數(shù)據(jù) SetNode *link;//鏈接指針 SetNode() : link (NULL);//構(gòu)造函數(shù) SetNode (const T& x, SetNode *next = NULL) : data (x), link (next);

27、//構(gòu)造函數(shù)};,22,template class LinkedSet {//集合的類定義 private: SetNode *first, *last; //有序鏈表表頭指針, 表尾指針 public: LinkedSet () { first = last = new SetNode; } LinkedSet (LinkedS

28、et& R);//復(fù)制構(gòu)造函數(shù) ～LinkedSet () { makeEmpty(); delete first; } void makeEmpty();//置空集合 bool addMember (const T& x); bool delMember (const T& x); LinkedSet& ope

29、rator = (LinkedSet& R); LinkedSet& operator + (LinkedSet& R);,23,LinkedSet& operator * (LinkedSet& R); LinkedSet& operator - (LinkedSet& R); bool Contains (const T x);//判x是否

30、集合的成員 bool operator == (LinkedSet& R);//判集合this與R相等 bool Min (T& x);//返回集合最小元素的值 bool Max (T& x);//返回集合最大元素的值 bool subSet (LinkedSet& R); //判this是否R的子集};,24,表示集合的幾個(gè)重載

31、函數(shù),template LinkedSet& LinkedSet::operator + (LinkedSet& R) {//求集合this與集合R的并,25,SetNode *pb = R.first->link;//R掃描指針 SetNode *pa = first->link;//this掃描指針 LinkedSet temp;//創(chuàng)建空鏈表 SetNod

32、e *p, *pc = temp.first;//結(jié)果存放指針 while (pa != NULL && pb != NULL) { if (pa->data == pb->data) {//兩集合共有 pc->link = new SetNode(pa->data); pa = pa->link;

33、 pb = pb->link; } else if (pa->data data) {//this元素值小 pc->link = new SetNode(pa->data); pa = pa->link; },26,else {//R集合元素值小

34、pc->link = new SetNode(pb->data); pb = pb->link; }pc = pc->link; } if (pa != NULL) p = pa;//this集合未掃完 else p = pb;//或R集合未掃完 while (p != NULL) {//向結(jié)果鏈逐個(gè)復(fù)制

35、 pc->link = new SetNode(p->data); pc = pc->link; p = p->link; } pc->link = NULL; temp.last = pc; //鏈表收尾 return temp;}；,27,等價(jià)類與并查集,在求解實(shí)際應(yīng)用問(wèn)題時(shí)常會(huì)遇到等價(jià)類問(wèn)題。從數(shù)學(xué)上看，等價(jià)類是

36、對(duì)象（或成員）的集合，在此集合中所有對(duì)象應(yīng)滿足等價(jià)關(guān)系。若用符號(hào)“?”表示集合上的等價(jià)關(guān)系，則對(duì)于該集合中的任意對(duì)象x, y, z，下列性質(zhì)成立：自反性：x ? x (即等于自身)。對(duì)稱性：若 x ? y, 則 y ? x。傳遞性：若 x ? y且 y ? z, 則 x ? z。,28,等價(jià)關(guān)系與等價(jià)類(Equivalence Class),因此，等價(jià)關(guān)系是集合上的一個(gè)自反、對(duì)稱、傳遞的關(guān)系?！跋嗟取?=)就是一種等價(jià)關(guān)系，

37、它滿足上述的三個(gè)特性。一個(gè)集合 S 中的所有對(duì)象可以通過(guò)等價(jià)關(guān)系劃分為若干個(gè)互不相交的子集 S1, S2, S3, …，它們的并就是 S。這些子集即為等價(jià)類。,29,確定等價(jià)類的方法,確定等價(jià)類的方法分兩步走：讀入并存儲(chǔ)所有的等價(jià)對(duì)( i, j )；標(biāo)記和輸出所有的等價(jià)類。,30,,,,給定集合 S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 },及如下等價(jià)對(duì): 0 ? 4, 3 ?

38、 1, 6 ? 10, 8 ? 9, 7 ? 4, 6 ? 8, 3 ? 5, 2 ? 11, 11 ? 0進(jìn)行歸并的過(guò)程為：初始{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}0 ? 4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}3 ? 1 {0,4},{1,3},{2},{5},{6},{7},{8},{9},{

39、10},{11}6 ? 10 {0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}8 ? 9 {0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}7 ? 4 {0,4,7},{1,3},{2},{5},{6,10},{8,9},{11},31,{0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}6 ? 8 {0,4,7},{1,3}

40、,{2},{5},{6,8,9,10},{11}3 ? 5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11}2 ? 11 {0,4,7},{1,3,5},{2,11},{6,8,9,10}11 ? 0 {0,2,4,7,11},{1,3,5},{6,8,9,10},32,并查集 (Union-Find Sets),并查集支持以下三種操作： Union (Root1, Root2) //合并操作 F

41、ind (x) //查找操作 UFSets (s) //構(gòu)造函數(shù)對(duì)于并查集來(lái)說(shuō)，每個(gè)集合用一棵樹表示。為此，采用樹的雙親表示作為集合存儲(chǔ)表示。集合元素的編號(hào)從0到 n-1。其中 n 是最大元素個(gè)數(shù)。,33,在雙親表示中，第 i 個(gè)數(shù)組元素下標(biāo)代表包含集合元素 i 的樹結(jié)點(diǎn)。根結(jié)點(diǎn)的雙親為 -k，表示集合中的元素個(gè)數(shù)為k。同一棵樹上所有結(jié)點(diǎn)

42、所代表的集合元素在同一個(gè)子集合中。為此，需要有兩個(gè)映射：集合元素到存放該元素名的樹結(jié)點(diǎn)間的對(duì)應(yīng)；集合名到表示該集合的樹的根結(jié)點(diǎn)間的對(duì)應(yīng)。,34,設(shè) S1= {0, 6, 7, 8}, S2= {1, 4, 9}, S3= {2, 3, 5},35,為簡(jiǎn)化討論，忽略實(shí)際的集合名，僅用表示集合的樹的根來(lái)標(biāo)識(shí)集合。,36,S1,下標(biāo)parent,集合 S1, S2 和 S3 的雙親表示,-4 4 -3 2 -3

43、 2 0 0 0 4,,,,,,,,,0 1 2 3 4 5 6 7 8 9,,S2,S3,,,,,,,,,,,,,,,,,,,,,,37,初始時(shí), 用構(gòu)造函數(shù) UFSets(s) 構(gòu)造一個(gè)森林, 每棵樹只有一個(gè)結(jié)點(diǎn), 表示集合中各元素自成一個(gè)子集合。用 Find(i) 尋找集合元素 i 的根。如果有兩個(gè)集合元素

44、 i 和 j, Find(i) == Find(j), 表明這兩個(gè)元素在同一個(gè)集合中，如果兩個(gè)集合元素 i 和 j 不在同一個(gè)集合中,可用 Union(i, j) 將它們合并到一個(gè)集合中。,38,,S1 ? S2的可能的表示方法,下標(biāo)parent,集合 S1 ? S2 和 S3 的雙親表示,-7 4 -3 2 0 2 0 0 0 4,,,,,,,,,0 1

45、 2 3 4 5 6 7 8 9,,,,,,,,,,,,,,,0,4,6,7,8,4,1,9,0,1,9,6,7,8,用雙親表示實(shí)現(xiàn)并查集的類定義,const int DefaultSize = 10;class UFSets {//集合中的各個(gè)子集合互不相交public: UFSets (int sz = DefaultSize);//構(gòu)造函數(shù)

46、～UFSets() { delete []parent; }//析構(gòu)函數(shù) UFSets& operator = (UFSets& R); //集合賦值 void Union (int Root1, int Root2); //子集合并 int Find (int x);//查找x的根 void WeightedUnion (int Root1, int R

47、oot2);//改進(jìn)例程:加權(quán)的合并算法private:,39,int *parent; //集合元素?cái)?shù)組(雙親表示) int size; //集合元素的數(shù)目};UFSets::UFSets (int sz) {//構(gòu)造函數(shù)：sz 是集合元素個(gè)數(shù)，雙親數(shù)組的范圍//為parent[0]～parent[size-1]。 size = sz; //集合元素個(gè)數(shù) pare

48、nt = new int[size]; //創(chuàng)建雙親數(shù)組 for (int i = 0; i < size; i++) parent[i] = -1; //每個(gè)自成單元素集合};,40,并查集操作的算法 查找,41,-5,,1,,2,,3,,4,0,1,2,3,4,,parent (4),,parent (3) =

49、 3,,parent (2) =2,,parent (1) = 1,,parent (0) = 0,= -5 < 0 結(jié)束,int UFSets::Find (int x) {//函數(shù)搜索并返回包含元素x的樹的根。 if (parent[x] < 0) return x; //根的parent[]值小于0 else return (Find (parent[x]

50、));};,42,void UFSets::Union (int Root1, int Root2) {//求兩個(gè)不相交集合Root1與Root2的并 parent[Root1] += parent[Root2]; parent[Root2] = Root1; //將Root2連接到Root1下面};Find 和 Union 操作性能不好。假設(shè)最初 n 個(gè)元素構(gòu)成

51、n 棵樹組成的森林，parent[i] = -1。做處理Union(n-2, n-1), …, Union(1, 2), Union(0, 1)后，將產(chǎn)生退化的樹。,43,合并,44,,1,0,2,3,4,2,0,1,4,2,4,4,3,3,Union(0,1),3,4,1,2,3,,,,,,,,Union(1,2),,,Union(2,3),,Union(3,4),,,,,45,執(zhí)行一次Union操作所需時(shí)間是 O(1)，n-1次Un

52、ion操作所需時(shí)間是O(n)。若再執(zhí)行Find(0), Find(1), …, Find(n-1), 若被搜索的元素為 i，完成 Find(i) 操作需要時(shí)間為O(i+1)，完成 n 次搜索需要的總時(shí)間將達(dá)到 改進(jìn)的方法 按樹的結(jié)點(diǎn)個(gè)數(shù)合并 按樹的高度合并 壓縮元素的路徑長(zhǎng)度,,按樹結(jié)點(diǎn)個(gè)數(shù)合并結(jié)點(diǎn)個(gè)數(shù)多的樹的根結(jié)點(diǎn)作根,46,1,0,2,3,4,5,6,5,2,0,2,0,1,3,4,6,,,,,3,,4,6,,,5,

53、,,1,,,Union(2, 0),,void UFSets :: WeightedUnion (int Root1, int Root2) {//按Union的加權(quán)規(guī)則改進(jìn)的算法 int temp = parent[Root1] + parent[Root2]; if (parent[Root2] < parent[Root1]) { parent[Root1] = Root2;

54、 //Root2中結(jié)點(diǎn)數(shù)多 parent[Root2] = temp; //Root1指向Root2 } else { parent[Root2] = Root1; //Root1中結(jié)點(diǎn)數(shù)多 parent[Root1] = temp; //Root2指向Root1 }};,47,按樹高度合并 高度高的樹的根結(jié)點(diǎn)作根,48,1,

55、0,2,3,4,5,6,5,2,0,2,0,1,3,4,6,,,,,3,,4,6,,,5,,,1,,,Union(2, 0),,49,壓縮元素的路徑長(zhǎng)度,3,0,1,9,,,,,5,,,6,7,8,,,,,3,0,1,9,,,,,5,,6,7,8,,,,,3,0,1,9,,,,,5,,6,7,8,,,字典（Dictionary）,字典是一些元素的集合，每個(gè)元素有一個(gè)稱作關(guān)鍵碼（key）的域，不同元素的關(guān)鍵碼互不相同。 文件（File）

56、 表格（Table）在討論字典抽象數(shù)據(jù)類型時(shí)，把字典定義為對(duì)的集合。根據(jù)問(wèn)題的不同，可以為名字和屬性賦予不同的含義。,50,例如，在圖書館檢索目錄中，名字是書名，屬性是索書號(hào)及作者等信息；在計(jì)算機(jī)活動(dòng)文件表中，名字是文件名，屬性是文件地址、大小等信息。一般來(lái)說(shuō)，有關(guān)字典的操作有如下幾種：確定一個(gè)指定的名字是否在字典中；搜索出該名字的屬性；修改該名字的屬性；插入一個(gè)新的名字及其屬性；刪除一個(gè)名字及其屬性。,51,字典的抽

57、象數(shù)據(jù)類型,const int DefaultSize = 26;template class Dictionary {//對(duì)象: 一組對(duì), 其中, 名字是唯一的public: Dictionary (int size = DefaultSize); //構(gòu)造函數(shù) bool Member (Name name);//判name是否在字典中 Attribute *Search (Nam

58、e name); //在字典中搜索關(guān)鍵碼與name匹配的表項(xiàng),52,void Insert (Name name, Attribute attr); //若name在字典中, 則修改相應(yīng)對(duì) //的attr項(xiàng); 否則插入到字典中 void Remove (Name name); //若name在字典中, 則在字典中刪除相應(yīng)的 //對(duì)};用文件記錄（r

59、ecord）或表格的表項(xiàng)（entry）來(lái)表示單個(gè)元素時(shí)，用：（關(guān)鍵碼key，記錄或表項(xiàng)位置指針adr） 構(gòu)成搜索某一指定記錄或表項(xiàng)的索引項(xiàng)。,53,字典的線性表描述,字典可以保存在線性序列 (e1,e2,…) 中，其中ei 是字典中的元素，其關(guān)鍵碼從左到右依次增大。為了適應(yīng)這種描述方式，可以定義有序順序表和有序鏈表。用有序鏈表來(lái)表示字典時(shí)，鏈表中的每個(gè)結(jié)點(diǎn)表示字典中的一個(gè)元素，各個(gè)結(jié)點(diǎn)按照結(jié)點(diǎn)中保存的數(shù)據(jù)值非遞減鏈接，即

60、e1≤e2 ≤ …。因此，在一個(gè)有序鏈表中尋找一個(gè)指定元素時(shí)，一般不用搜索整個(gè)鏈表。,54,有序順序表的類定義,#include #include “SeqList.h”const int defaultSize = 50;template class SortedList : public SeqList {public: int Search (K k1) const; //搜索 voi

61、d Insert (const K k1, E& e1); //插入 bool Remove (const K k1, E& e1); //刪除};,55,基于有序順序表的順序搜索算法,template int SortedList::Search (K k1) const {//順序搜索關(guān)鍵碼為k1的數(shù)據(jù)對(duì)象 int n = last+1; for (int i

62、 = 1; i k1) break; return 0; //順序搜索失敗, 返回失敗信息};算法中的“==”和“>”都是重載函數(shù)，在定義K時(shí)定義它們的實(shí)現(xiàn)。,56,有序順序表順序搜索的時(shí)間代價(jià),衡量一個(gè)搜索算法的時(shí)間效率的標(biāo)準(zhǔn)是：在搜索過(guò)程中關(guān)鍵碼平均比較次數(shù)，也稱為平均搜索長(zhǎng)度ASL (Average Search Length)，通常它是字典中元素總數(shù) n 的函數(shù)。設(shè)搜索第 i 個(gè)元素的概率

63、為 pi, 搜索到第 i 個(gè)元素所需比較次數(shù)為 ci, 則搜索成功的平均搜索長(zhǎng)度:,57,在順序搜索情形，搜索第 i (1≤i≤n) 個(gè)元素需要比較 i 次，假定按等概率搜索各元素：這與一般順序表情形相同。但搜索不成功時(shí)不需一直比較到表尾，只要發(fā)現(xiàn)下一個(gè)元素的值比給定值大，就可斷定搜索不成功。設(shè)一個(gè)有 n 個(gè)表項(xiàng)的表，查找失敗的位置有n+1個(gè)，可以用判定樹加以描述。搜索成功時(shí)停在內(nèi)結(jié)點(diǎn)，搜索失敗時(shí)停在外結(jié)點(diǎn)。,58,例如，有

64、序順序表 (10, 20, 30, 40, 50, 60)的順序搜索的分析（使用判定樹）,59,判定樹是一種擴(kuò)充二叉樹。內(nèi)結(jié)點(diǎn)代表順序表中已有的元素，外結(jié)點(diǎn)代表失敗結(jié)點(diǎn)，它表示在兩個(gè)相鄰已有元素值之間的值。假定表中所有失敗位置的搜索概率相同，則搜索不成功的平均搜索長(zhǎng)度：時(shí)間代價(jià)為O(n)。為了加速搜索，在有序順序表的情形，可以采用折半搜索，它也稱二分搜索，時(shí)間代價(jià)可減小到O(log2n)。,60,基于有序順序表的折半搜索,設(shè) n

65、 個(gè)元素存放在一個(gè)有序順序表中。折半搜索時(shí), 先求位于搜索區(qū)間正中的元素的下標(biāo)mid，用其關(guān)鍵碼與給定值 x 比較: data[mid].key == x，搜索成功； data[mid].key > x，把搜索區(qū)間縮小到表的前半部分，繼續(xù)折半搜索； data[mid].key < x，把搜索區(qū)間縮小到表的后半部分，繼續(xù)折半搜索。如果搜索區(qū)間已縮小到一個(gè)對(duì)象，仍未找到想要搜索的對(duì)象，則搜索失敗。,61,62,63,6

66、4,templateint SortedList::BinarySearch (K k1, const int low, const int high ) const {//折半搜索的遞歸算法，用到E的重載操作“” int mid = 0; //元素序號(hào)從0開始 if (low k1) mid = BinarySearch (k1, low, mid -

67、1); else return mid; } return 0;};,65,template int SortedList ::BinarySearch (K k1) const { //折半搜索的迭代算法，用到K的重載操作“” int high = n-1, low = 0, mid; //元素序號(hào)從0開始 while (low

68、 k1) high = mid-1; //左縮搜索區(qū)間 else return mid; //搜索成功 } return 0; //搜索失敗},分析有序順序表 ( 10, 20, 30,

69、40, 50, 60 ) 的折半搜索算法性能的判定樹：,66,10,50,,,,,,,,=,=,=,=,=,=,,,30,,,,,,,,<,<,<,<,<,<,>,>,>,>,>,>,,,,20,40,60,ASLunsucc = (2*1+3*6)/7 = 20/7,ASLsucc = (1+2*2+ 3*3)/6 = 14/

70、6,判定樹也是擴(kuò)充二叉樹，搜索成功時(shí)檢測(cè)指針停留在樹中某個(gè)內(nèi)結(jié)點(diǎn)上。搜索不成功時(shí)檢測(cè)指針停留在某個(gè)外結(jié)點(diǎn)（失敗結(jié)點(diǎn)）上。,67,,,,,,,,,,,,,,,,,35,15,45,50,25,10,20,30,,,,,,,,,,,,,,搜索22,搜索45,,折半搜索算法的性能分析,若設(shè) n = 2h-1，則描述折半搜索的判定樹是高度為 h 的滿二叉樹 (加上失敗結(jié)點(diǎn)高度為h +1)。 2h = n+1, h =