《數(shù)據(jù)結(jié)構(gòu)與算法》PPT課堂課件-第8章-集合

1、1第9章 集合 學(xué)習(xí)要點(diǎn):9.1 以集合為基礎(chǔ)的抽象數(shù)據(jù)類型 理解集合的概念。 理解以集合為基礎(chǔ)的抽象數(shù)據(jù)類型。 掌握用位向量實(shí)現(xiàn)集合的方法。 掌握用鏈表實(shí)現(xiàn)集合的方法。29.2 符號表 理解抽象數(shù)據(jù)類型符號表的概念。 掌握數(shù)組實(shí)現(xiàn)符號表的方法。 理解開散列和閉散列的概念。 掌握用開散列表實(shí)現(xiàn)符號表的方法。 掌握除余法、數(shù)乘法、平方取中法、基數(shù)轉(zhuǎn)換法和隨機(jī)數(shù)法等散列函數(shù)構(gòu)造方法。 掌握采用線性重新散列技術(shù)的閉散列表實(shí)現(xiàn)符號表的方法。39.3 字典 理解以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型字典。 理解用數(shù)組實(shí)現(xiàn)字典的方法。 理解二叉搜索樹的概念和實(shí)現(xiàn)方法。 掌握用二叉搜索樹實(shí)現(xiàn)字典的方法。 理解AVL樹

2、的定義和性質(zhì)。 掌握二叉搜索樹的結(jié)點(diǎn)旋轉(zhuǎn)變換及實(shí)現(xiàn)方法。 掌握AVL樹的插入重新平衡運(yùn)算及實(shí)現(xiàn)方法。 掌握AVL樹的刪除重新平衡運(yùn)算及實(shí)現(xiàn)方法。49.4 優(yōu)先隊(duì)列 理解以集合為基礎(chǔ)的抽象數(shù)據(jù)類型優(yōu)先隊(duì)列。 理解用有序字典實(shí)現(xiàn)優(yōu)先隊(duì)列的方法。 理解優(yōu)先級樹和堆的概念。 掌握用數(shù)組實(shí)現(xiàn)堆的方法。 理解以集合為基礎(chǔ)的抽象數(shù)據(jù)類型可并優(yōu)先隊(duì)列。 理解左偏樹的定義和概念。 掌握用左偏樹實(shí)現(xiàn)可并優(yōu)先隊(duì)列的方法。 掌握堆排序算法。59. 5 并查集 理解以不相交的集合為基礎(chǔ)的抽象數(shù)據(jù)類型并查集。 掌握用數(shù)組實(shí)現(xiàn)并查集的方法。 掌握用樹結(jié)構(gòu)實(shí)現(xiàn)并查集的方法。 理解將小樹合并到大樹的合并策略及其實(shí)現(xiàn)。 掌握路徑

3、壓縮技術(shù)及其實(shí)現(xiàn)方法。69.0 引言9.0.1 集合的概念的原形 銀行中所有儲戶帳號的集合；圖書館中 所有藏書的集合；一個(gè)程序中所有標(biāo)識 符的集合；2003級34班全體同學(xué)的集合等 79.0 引言9.0.2 集合的概念與術(shù)語 集合：集合是由元素(成員)組成的一個(gè)類。 原子：不可再分的元素。 多重集合：允許同一元素在集合中多次出 現(xiàn)的集合稱為多重集合。有序集：當(dāng)由原子組成的集合具有線性序關(guān) 系“”時(shí)，稱該集合為有序集?！啊笔羌系?一個(gè)線性序，它滿足： (1)若a、b是集合中任意2個(gè)原子,則ab,a=b和 ba三者必居其一；(2)a，b和c是集合中的原 子，且ab，bc則asetsize=siz

4、e; S-arraysize=(size+15)4; S-v=malloc(size*sizeof(unsigned short); for (i=0; ivi=0; return S; 15void SetAssign(Set A, Set B) int i; if (A-setsize !=B-setsize) Error(“Sets are not the same size”); for(i=0; iarraysize; i+) A-vi=B-vi; 16int SetMemeber(int x, Set S) if (x=S-setsize) Error(“Invalid membe

5、r reference”); return S-vArrayIndex() & BitMask(x); 17int ArrayIndex(int x) return x4; unsigned short BitMask(int x) return 1setsize !=B-setsize) Error(“.”); for(i=0; iarraysize; i+) if(A-vi !=B-vi) retval=0; break; return retval; 19Set SetUnion(Set A, Set B) int i; Set tmp=SetInit(A-setsize); for(i

6、=0; iarraysize; i+) tmp-vi=A-vi | B-vi; return tmp; 20Set SetIntersection(Set A, Set B) int i; Set tmp=SetInit(A-setsize); for(i=0; iarraysize; i+) tmp-vi=A-vi & B-vi; return tmp; 21Set SetDifference(Set A, Set B) int i; Set tmp=SetInit(A-setsize); for(i=0; iarraysize; i+) tmp-vi=A-vi (B-vi & A-vi);

7、 return tmp; 22void SetInsert(int x, Set S) if (x=S-setsize) Error(“.”); S-vArrayIndex(x) |=BitMask(x); 23void SetDelete(int x, Set S) if (x=S-setsize) Error(“.”); S-vArrayIndex(x) &=BitMask(x); 249.1 以集合為基礎(chǔ)的抽象數(shù)據(jù)類型9.1.3 ADT集合的簡單實(shí)現(xiàn)用有序鏈表實(shí)現(xiàn)9.1.3.0 LinkedSet的有序鏈表結(jié)點(diǎn)類型Node的定義Typedef struct node *linkstruc

8、t node ListItem element; link next; Node;259.1 以集合為基礎(chǔ)的抽象數(shù)據(jù)類型9.1.3 ADT集合的簡單實(shí)現(xiàn)用有序鏈表實(shí)現(xiàn) 9.1.3.1有序鏈表實(shí)現(xiàn)的集合Set的定義Typedef struct list *SetTypedef struct list link first;26Set SetInit( ) Set S=malloc(sizeof *S); S-first=0; return S; 27int SetEmpty(Set S) return S-first=0; 28int SetSize(Set S) int len; link c

9、urrent; current=S-first; len=0; while (current) len+; current=current-next; return len; 29void SetAssign(Set A, Set B) link a,b,c; b=B-first; A-first=0; if (b) A-first=NewNode( ); a=A-first; a-element=b-element; a-next=0; b=b-next; while(b) c=NewNode( ); c-element=b-element; c-next=0; b=b-next; a-ne

10、xt=c; a=c; 30Set SetIntersection(Set A, Set B) link a,b,p,q,r; Set tmp=SetInit( ); a=A-first; b=B-first; p=NewNode( ); q=p; while(a & & b) if(a-element =b-element) r=NewNode( ); r-element=a-element; r-next=0; p-next=r; p=r; a=a-next; b=b-next; else if(a-element element) a=a-next; else b=b-next; if(p

11、!=q) tmp-first=q-next; free(q); return tmp; 31void SetIntsert(ListItem x, Set S) link p,q,r; p = S-first; q = p; while ( p & p-element next; if (p & p-element = x) return; r = NewNode(); r -element =x; r-next = p; if (p = q) S-first = r; else q-next =r; 329.2 符號表9.2.0 引言 ADT符號表的概念 以集合為基礎(chǔ)，并支持Member、I

12、nsert和Delete三種運(yùn)算的抽象數(shù)據(jù)類型叫做符號表。 ADT符號表的應(yīng)用 公司的客戶字典 一個(gè)地區(qū)的固定/移動電話號碼字典 軟件開發(fā)中的數(shù)據(jù)字典 網(wǎng)上的在線字典 互聯(lián)網(wǎng)/企業(yè)網(wǎng)/局域網(wǎng)網(wǎng)管中的IP地址字典等等 339.2符號表9.2.1 實(shí)現(xiàn)符號表的簡單方法用固定數(shù)組typedef struct atab *Table;typedef struct atab int arraysize; int last; SetItem*data;Atab;34Table TableInit(int size) Table T=malloc(sizeof *T); T-arraysize=size;

13、T-last=0; T-data=malloc(size*sizeof(SetItem); return T;35int TableMember(SetItem x,Table T) int I; for(i=0;ilast;i+) if(T-datai=x) return 1;return 0;36void TableInsert(SetItem x,Table T) if(! TableMember(x,T) & T-lastarraysize) T-dataT-last+=x;37void TableDelete(SetItem x,Table T) int i=0; if (T-las

14、t0) while(Y-datai!=x & ilast) i+; if(ilast & T-datai=x) T-datai=T-data-T-last;389.2符號表9.2.1 實(shí)現(xiàn)符號表的簡單方法用固定數(shù)組9.2.1.3 優(yōu)缺點(diǎn)優(yōu)點(diǎn)：結(jié)構(gòu)簡單，實(shí)現(xiàn)操作的邏輯簡單。缺點(diǎn)： 所表示的集合的大小受到數(shù)組大小的限制。 三個(gè)基本操作在最壞情況下都需要O(n)。 通常集合元素并不占滿整個(gè)數(shù)組，因此， 空間沒有得到充分利用。399.2符號表9.2.2 實(shí)現(xiàn)符號表的簡單方法開散列9.2.2.1 基本設(shè)想 把符號表中的所有元素散列(hashing)即映射到一 個(gè)桶數(shù)組(散列表)的桶中。當(dāng)有多個(gè)不同元素被

15、 散列到同一個(gè)桶時(shí)，這些元素用鏈在一個(gè)表里。 期望散列能均勻，使得當(dāng)桶數(shù)組的規(guī)模與字典 的規(guī)模同階時(shí)，桶數(shù)組的每一個(gè)桶中大致有常 數(shù)個(gè)元素，從而對字典的三個(gè)基本操作都只需 要常數(shù)時(shí)間。 這里的問題是如何散列即如何構(gòu)造散列(映射)函 數(shù)去達(dá)到設(shè)想的期望？409.2符號表9.2.2 實(shí)現(xiàn)符號表的簡單方法開散列9.2.2.2 開散列的數(shù)據(jù)要素 按照設(shè)想，開散列首先需要擁有一個(gè)桶數(shù)組， 桶數(shù)組的規(guī)模與符號表的規(guī)模同階，桶數(shù)組中的 每一個(gè)桶有一個(gè)指針各指向一個(gè)鏈表。 其次需要擁有一個(gè)散列(映射)函數(shù)，它把字典 中的元素分別散列(映射，分散)到各桶所對應(yīng) 的鏈表中。419.2符號表9.2.2 實(shí)現(xiàn)符號表的

16、簡單方法開散列9.2.2.3 散列函數(shù)的例子 假設(shè)符號表的元素是字符串x，桶數(shù)組的規(guī)模為 101，那么，下面是散列函數(shù)的一個(gè)具體例子int hash1(char* x) int len=strlen(x), hashval = 0; for(int i=0;isize=nbuckets; H-hf=hashf; H-ht=malloc(H-size*sizeof(List); for(i=0;isize;i+) H-hti=ListInit() return H;45int HTMember(SetItem x,OpenHashTable H) int i=(*h-HF)(x) % H-siz

17、e; return (ListLocate(x,H-hti)0);46void HTInsert(SetItem x,OpenHashTable H) int i; if (HTMember(x,H) Error(“Bad Input”); i=(*h-hf)(x) % H-size; ListInsert(0,x,H-hti);47void HTDelete(SetItem x,OpenHashTable H) int i; i=(*h-hf)(x) % H-size; if (k=ListLocate(x,H-hti) ListDelete(k,H-hti);489.2符號表9.2.3 實(shí)

18、現(xiàn)符號表的簡單方法閉散列9.2.3.1 與開散列的相同點(diǎn)和區(qū)別相同點(diǎn)：把字典中的所有元素散列(hashing)即 映射到一個(gè)桶數(shù)組(散列表)的桶中。區(qū)別：桶數(shù)組(散列表)的桶直接用來存放字典 元素，而且一個(gè)桶只存放一個(gè)元素。出現(xiàn)多個(gè) 元素散列到同一個(gè)桶時(shí)(這叫沖突)，需要按照 確定的規(guī)則在桶數(shù)組中進(jìn)行探測，找還沒有存 放元素的桶(這叫空桶)，然后將發(fā)生沖突的后 到元素放入空桶，解決沖突，實(shí)現(xiàn)散列。 499.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.2 閉散列引發(fā)的問題(1)需要一個(gè)探測函數(shù)c(i),i=0,1,2,size-1： c(0)=0,而且對于任意的0jsize-1 (

19、j+c(0)mod size, (j+c(1)mod size, ,(j+c(size-1)mod size是 0,1,2,size-1 的重排,保證不會漏測。(2)需要對ht 的每一個(gè)桶的狀態(tài)加以標(biāo)記： statek=0表示htk桶存放著元素。 statek=1表示htk桶一直是空桶。 statek=2表示htk桶現(xiàn)在是空桶但曾經(jīng)存放過元素509.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.3 閉散列的數(shù)據(jù)要素(1)桶數(shù)組的規(guī)模size；(2)桶數(shù)組ht ；(3)散列函數(shù)指針 int (*hf) (T x)；(4)探測函數(shù)c(i),i=0,1,2,size-1；(5)桶狀態(tài)標(biāo)記

20、數(shù)組state ；519.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.4 閉散列表實(shí)現(xiàn)的的定義typedef struct hashtable *HashTable;typedef struct hashtableint size;int (*hf)(SetItem x);SetItem *ht;int *state;Hashtable;52HashTable HTInit(int divisor, int (*hashf)(SetItem x)int i;HashTable H=malloc(sizeof *H);H-size=divisor;H-hf = hashf;H-ht

21、=malloc(H-size*sizeof(int);for (i=0;isize;i+)H-statei=1;return H;53int FindMatch(SetItem x,HashTable H)int I,j,k;j=(*H-hf)(x);for (i=0;isize;i+)k=(j+HashProb(i)%H-size;if (H-statek=1) break;if(!H-statek & H-htk=x) return k;return H-size;int HashProb(int i)return i;54int Unoccupied(SetItem x,HashTabl

22、e H)int I,j,k;j=(*H-hf)(x);for (i=0;isize;i+)k=(j+HashProb(i)%H-size;if (H-statek) return k;return H-size;55int HTMember(SetItem x,HashTable H)int i=FindMatch(x,H);if (isize & H-hti=x) return 1;return 0;56int HTInsert(SetItem x,HashTable H)int I;if(HTMember(x,H) Error(“Bad Input”);i=Unoccupied(x,H);

23、if(isize) H-statei=0; H-hti=x; else Error(“table full”);57int HTDelete(SetItem x,HashTable H)int i=FindMatch(x,H);if (isize & H-hti=x) H-statei=2;589.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.5 HashTable的定義中未實(shí)現(xiàn)的函數(shù)(續(xù))函數(shù)HTDelete的缺點(diǎn)： 在執(zhí)行了大量元素刪除運(yùn)算后，大量的桶的狀態(tài) 標(biāo)記為 2 即大量的桶的狀態(tài)標(biāo)記既非 1 也非 0 使 得運(yùn)算FindMatch 中的循環(huán)次數(shù)大大增加，從而 使得運(yùn)算F

24、indMatch的速度大大減慢。 因此人們提出HTDelete的一種改進(jìn)版本HTDelete1599.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.5 HashTable的定義中未實(shí)現(xiàn)的函數(shù)(續(xù))改進(jìn)HTDelete的基本思想： 動機(jī)是希望騰出的空桶(記為hti)不僅僅可供新元素插入 ，而且能為提高還在桶數(shù)組中的元素(比如y= htj)的查 找速度作出貢獻(xiàn)：減少查找y的探測次數(shù)。 容易理解，如果不作任何改進(jìn)，查找y的探測次數(shù)會等于 插入y時(shí)的探測次數(shù)。如果插入y時(shí)x已在桶hti中且與x發(fā) 生沖突而增加了插入的探測次數(shù)，那么，現(xiàn)在x不存在了， 只要將x騰出的桶hti讓y頂替，就可以使

25、得將來查找y時(shí) 減少探測次數(shù)。因此改進(jìn)HTDelete的途徑是在當(dāng)前的桶數(shù) 組中找能頂替x的y。如果找不到，就按HTDelete的原版處 理；如果找得到，在用y頂替x之后還可以引起連鎖反應(yīng)。 609.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.5 HashTable的定義中未實(shí)現(xiàn)的函數(shù)(續(xù))改進(jìn)HTDelete的細(xì)節(jié)找能頂替x的y 假設(shè)被刪除元素x位于桶單元hti。現(xiàn)考察一個(gè)非空單元htj 中的元素y，其散列函數(shù)值設(shè)為h=hf(y)，則按從h出發(fā)的線性 探測，只要i比j離h近即可使得在頂替后找y的探測次數(shù)減少。 當(dāng)ij時(shí)，若ihj，則不可用元素htj頂替hti；若hij或ijh，

26、則可用元素htj頂替hti。如下圖(a)。 當(dāng)ji時(shí)，若jhI，則可用元素htj頂替hti，如下圖 (b)；否則不可。 這里以線性探測為前題，以頂替后減少探測次數(shù)為目標(biāo)。619.2符號表9.2.3 實(shí)現(xiàn)符號表的簡單方法閉散列9.2.3.5 HashTable的定義中未實(shí)現(xiàn)的函數(shù)(續(xù))(8) 改進(jìn)HTDelete的函數(shù)HTDelete1Void HTDelete1SetItem x,HashTable H) int i=FindMatch(x); if (isize) / &H-hti=x可以去掉 for (;) /找hti的頂替元素 H-statei=2; /先按無頂替元素處理 int j;

27、/從(i+1)%size開始線性搜索可頂替元素 for (j=(i+1)%H-size; !statej; j=(j+1)%H-size) 629.2符號表 int h=(*H-hf) (H-htj);if (h=i&ij)|(ij&jh)|(jh&hstatej) break; /跳出外for循環(huán) H- hti=htj; H-statei=statej; /做頂替工作i=j; /為構(gòu)成循環(huán)找htj的頂替元素 639.2符號表9.2.4 開散列的效率若能選擇一個(gè)好的散列函數(shù)，將集合中的N個(gè)元素均勻地散列到B個(gè)桶中，那么，每個(gè)桶中平均有N/B個(gè)元素，使得在開散列表中，Insert，Delete和

28、Member運(yùn)算都只要O(N/B)的平均時(shí)間。進(jìn)而當(dāng)N/B為一常數(shù)時(shí)，字典的每一個(gè)運(yùn)算都可在常數(shù)時(shí)間內(nèi)完成。因此：對于開散列表，關(guān)鍵在于選擇一個(gè)好的散列函數(shù)649.2符號表9.2.5 散列函數(shù)舉例(1)除余法：h(k)=k %m。(2)數(shù)乘法：h(k)= 。(3)平方取中法：h(k)= %B。(4)基數(shù)轉(zhuǎn)換法 ：(5)隨機(jī)數(shù)法 ：h(k)=random(k)。659.2符號表9.2.6 閉散列的重新散列技術(shù) (1)二次重新散列技術(shù) 它選取的探查桶序列為：h(x),h1(x) ,h2(x) ,h2i(x) ,h2i+1(x) , 其中， ， 。 (2)隨機(jī)重新散列技術(shù) 它選取的探查桶序列為： ,

29、i=1，2，B-1。 其中， 是1，2，B-1的一個(gè)隨機(jī)排列。 (3)雙重散列技術(shù) 這種方法使用2個(gè)散列函數(shù)h和h來產(chǎn)生探索序列： 其中 i=1，2，B-1。要求h(x)的值和B互素 。669.3.1 字典的定義 字典是以有序集為基礎(chǔ)的抽象數(shù)據(jù)類型。 它支持以下運(yùn)算： (1)Member(x)，成員運(yùn)算。 (2)Insert(x)，插入運(yùn)算：將元素x插入集合。 (3)Delete(x)，刪除運(yùn)算：將元素x從當(dāng)前集合中刪去。 (4)Predecessor(x)，前驅(qū)運(yùn)算：返回集合中小于x的最大元素。 (5)Successor(x)，后繼運(yùn)算：返回集合中大于x的最小元素。 (6)Range(x，y

30、)，區(qū)間查詢運(yùn)算：返回集合中界于x和y之間，即xzy的所有元素z組成的集合。 (7)Min( )，最小元運(yùn)算：返回當(dāng)前集合中依線性序最小的元素。 9.3 字典 679.3 字典 9.3.2 用數(shù)組實(shí)現(xiàn)字典 用數(shù)組實(shí)現(xiàn)字典與用數(shù)組實(shí)現(xiàn)符號表的不同之處： 可以利用線性序?qū)⒆值渲械脑貜男〉酱笠佬虼鎯υ跀?shù)組中，通過數(shù)組下標(biāo)來反映有序字典元素之間的序關(guān)系。優(yōu)點(diǎn)：可用二分法高效地實(shí)現(xiàn)與線性序有關(guān)的一些運(yùn)算。如：Member(x) ，Predecessor(x)和 Successor(x)可在時(shí)間O(logn)內(nèi)實(shí)現(xiàn)。缺點(diǎn)：插入和刪除運(yùn)算的效率較低。每執(zhí)行一次Insert或Delete運(yùn)算，需要移動部分?jǐn)?shù)

31、組元素，從而導(dǎo)致它們在最壞情況下的計(jì)算時(shí)間為O(n)?？紤]：能否用鏈表來實(shí)現(xiàn)字典？Member運(yùn)算需要O(n)時(shí)間，一旦找到元素在鏈表中插入或刪除的位置后，只要用O(1)時(shí)間就可完成插入或刪除操作。 兩種實(shí)現(xiàn)方式均不可?。?89.3 字典 9.3.3 用二叉搜索樹實(shí)現(xiàn)字典9.3.3.1 基本思想： 用二叉樹來存儲有序集，每一個(gè)結(jié)點(diǎn)存儲一個(gè)元素。 滿足：存儲于每個(gè)結(jié)點(diǎn)中的元素x大于其左子樹中任一結(jié)點(diǎn)中所存儲的元素，小于其右子樹中任一結(jié)點(diǎn)中所存儲的元素。699.3 字典 9.3.3 用二叉搜索樹實(shí)現(xiàn)字典9.3.3.2 二叉搜索樹結(jié)點(diǎn)的定義及程序?qū)崿F(xiàn)709.3 字典 9.3.3 用二叉搜索樹實(shí)現(xiàn)字典

32、9.3.3.3 二叉搜索樹的定義及運(yùn)算的實(shí)現(xiàn):71例 10， 18， 3， 8， 12， 2， 7， 41010181018310183810183812210183812710183812247101838122二叉搜索樹的建立過程：72刪除508060120110150557053刪除6080551201101505370805012060110150557053刪除43例80501206011015055705343運(yùn)算Delete(const T& x)的實(shí)現(xiàn)73運(yùn)算Delete(const T& x)的實(shí)現(xiàn)（續(xù)）設(shè)要刪除二叉搜索樹中的結(jié)點(diǎn)p ，分三種情況：p為葉結(jié)點(diǎn) 直接刪除節(jié)點(diǎn)pp

33、只有左子樹或右子樹p只有左子樹 用p的左兒子代替p p只有右子樹 用p的右兒子代替p p左、右子樹均非空找p的左子樹的最大元素結(jié)點(diǎn)（即p的前驅(qū)結(jié)點(diǎn)），用該結(jié)點(diǎn)代替結(jié)點(diǎn)p，然后刪除該結(jié)點(diǎn)。74用二叉搜索樹實(shí)現(xiàn)字典時(shí)間復(fù)雜性分析 最壞情況分析member,insert,delete都需要O(n) 平均情況分析引入記號:記：p(n)為含有n個(gè)結(jié)點(diǎn)的二叉搜索樹的平均查找長度。顯然p(0)=0,p(1)=1; 若設(shè)某二叉搜索樹的左子樹有i個(gè)結(jié)點(diǎn)，則：p(i)+1為查找左子樹中每個(gè)結(jié)點(diǎn)的平均查找長度;p(n-i-1)+1為查找右子樹中每個(gè)結(jié)點(diǎn)的平均查找長度；由此構(gòu)造而得的二叉搜索樹在n個(gè)結(jié)點(diǎn)的查找概率相等

34、的情況下，其平均查找長度為：75對n用數(shù)學(xué)歸納法可以證明:又假設(shè)當(dāng)前的二叉搜索樹有n個(gè)結(jié)點(diǎn)，而它是從空樹開始反復(fù)調(diào)用n次的Insert運(yùn)算得到的，且被插入的n個(gè)元素的所有可能的順序是等概率的。則：當(dāng)n=1時(shí)顯然成立。若設(shè)in時(shí)有 ，則76平均情況下的時(shí)間復(fù)雜度為：略去 -1/n 項(xiàng)77運(yùn)算Predecessor(x)和Successor(x)的實(shí)現(xiàn)：類似于Search(x)算法運(yùn)算Range(y, z)的實(shí)現(xiàn)：可借助于Search(y)和Successor(y)運(yùn)算首先，用Search(y)檢測y是否在二叉搜索樹中，是則輸出y，否則不輸出y；然后，從y開始，不斷地用Successor找當(dāng)前元素

35、在二叉搜索樹中的后繼元素。當(dāng)找出的后繼元素x滿足x z時(shí)，就輸出x，并將x作為當(dāng)前元素。重復(fù)這個(gè)過程，直到找出的當(dāng)前元素的后繼元素大于z，或二叉搜索樹中已沒有后繼元素為止。時(shí)間復(fù)雜度：若二叉樹搜索樹中有r個(gè)元素x滿足y x z，則在最壞情況下用 時(shí)間，在平均情況下用 時(shí)間可實(shí)現(xiàn)Range運(yùn)算。 78運(yùn)算Range(y,z)的改進(jìn)：考慮半無限查詢區(qū)域 , 即找出二叉搜索樹中滿足y x的所有元素x。 當(dāng)y不在二叉搜索樹中時(shí)，產(chǎn)生一條從根到葉的路徑。如下圖(a) 當(dāng)y在二叉搜索樹中時(shí)，產(chǎn)生一條從根到存儲元素y的結(jié)點(diǎn)的路徑。如下圖(b) 79在找到的搜索路徑上的所有結(jié)點(diǎn)可分為以下3種情況，如下圖 ：8

36、0運(yùn)算Range(y,z)的實(shí)現(xiàn)：可用類似于Range(y,)算法 從二叉搜索樹的根結(jié)點(diǎn)開始，同時(shí)與y和z比較,此時(shí),結(jié)點(diǎn)分類的情況可能有（見下圖） ：81運(yùn)算Range(y,z)的搜索路徑如下圖： 829.4 優(yōu)先隊(duì)列 9.4.0 優(yōu)先隊(duì)列的原型排隊(duì)上車，老弱病殘者優(yōu)先上車排隊(duì)候診，危急病人優(yōu)先就診洗相館為顧客洗照片，加錢加急者優(yōu)先洗分時(shí)操作系統(tǒng)運(yùn)行程序，小程序優(yōu)先貪心算法對解分量的選擇，按元素的某種特征值，大(或小)的優(yōu)先在一個(gè)集合中搜索，按元素的某種特征值，大(或小)的優(yōu)先處理或服務(wù)時(shí)只關(guān)心對象中誰的優(yōu)先級最高通常的隊(duì)列是一種優(yōu)先隊(duì)列最先到者優(yōu)先級最高839.4 優(yōu)先隊(duì)列9.4.1 優(yōu)先

37、隊(duì)列的定義優(yōu)先隊(duì)列也是一個(gè)以集合為基礎(chǔ)的抽象數(shù)據(jù)類型。優(yōu)先隊(duì)列中的每一個(gè)元素都有一個(gè)優(yōu)先級值。優(yōu)先隊(duì)列中元素x的優(yōu)先級值記為p(x)，它可以是一個(gè)實(shí)數(shù)，也可以是一個(gè)一般的全序集中的元素。優(yōu)先級值用來表示該元素出列的優(yōu)先級。通常約定優(yōu)先級值小的優(yōu)先級高。也可以約定優(yōu)先級值大的優(yōu)先級高。優(yōu)先隊(duì)列支持的基本運(yùn)算有：(1)Size( )：返回優(yōu)先隊(duì)列中元素個(gè)數(shù)。(2)Min( )：返回優(yōu)先隊(duì)列中具有最小優(yōu)先級值的元素。(3)Insert(x)：將元素x插入優(yōu)先隊(duì)列。(4)DeleteMin(x)：刪除優(yōu)先隊(duì)列中具有最小優(yōu)先級值的元素，并保存到x中。 849.4 優(yōu)先隊(duì)列9.4.2 用實(shí)現(xiàn)有序字典的方式

38、實(shí)現(xiàn)優(yōu)先隊(duì)列(1)優(yōu)先隊(duì)列與字典的相似性與區(qū)別：優(yōu)先隊(duì)列中元素的優(yōu)先級值可以看作是有序字典中元素的線性序值。在有序字典中，不同的元素具有不同的線性序值，其插入運(yùn)算僅當(dāng)要插入元素x的線性序值與當(dāng)前字典中所有元素的線性序值都不同時(shí)才執(zhí)行。對于優(yōu)先隊(duì)列來說，不同的元素可以有相同的優(yōu)先級值。因此，優(yōu)先隊(duì)列的插入運(yùn)算即使在當(dāng)前優(yōu)先隊(duì)列中存在與要插入元素x有相同的優(yōu)先級值的元素時(shí)，也要執(zhí)行元素x的插入。 859.4 優(yōu)先隊(duì)列9.4.2 用實(shí)現(xiàn)有序字典的方式實(shí)現(xiàn)優(yōu)先隊(duì)列(2)由于優(yōu)先隊(duì)列與字典的相似性,除了散列表之外,所有實(shí)現(xiàn)字典和有序字典的方法都可用于實(shí)現(xiàn)優(yōu)先隊(duì)列。 用有序鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列;(Insert

39、低效) 用二叉搜索樹實(shí)現(xiàn)優(yōu)先隊(duì)列;(Insert,DeleteMin, Min 均低效) 用AVL樹實(shí)現(xiàn)優(yōu)先隊(duì)列;(邏輯復(fù)雜) 用無序鏈表實(shí)現(xiàn)優(yōu)先隊(duì)列;(DeleteMin, Min均低效) 都有缺點(diǎn)。原因在于沒有考慮到優(yōu)先隊(duì)列的特性。869.4 優(yōu)先隊(duì)列9.4.3 用優(yōu)先級樹實(shí)現(xiàn)優(yōu)先隊(duì)列 1.優(yōu)先隊(duì)列的特征:DeleteMin和Min只關(guān)心優(yōu)先級最高的元素Insert的元素不要求全局的序關(guān)系 因此實(shí)現(xiàn)優(yōu)先隊(duì)列的結(jié)構(gòu)只要求方便DeleteMin 和Min,而對Insert也只要求不給結(jié)構(gòu)的維護(hù)帶來 太大的麻煩。 根據(jù)這兩個(gè)特征,人們發(fā)明了優(yōu)先級樹。879.4 優(yōu)先隊(duì)列9.4.3 用優(yōu)先級樹實(shí)現(xiàn)

40、優(yōu)先隊(duì)列(續(xù))2.優(yōu)先級樹的概念 優(yōu)先級樹是滿足下面的優(yōu)先級性質(zhì)的二叉樹： (1)樹中每一結(jié)點(diǎn)存儲一個(gè)元素。 (2)任一結(jié)點(diǎn)中存儲的元素的優(yōu)先級值不大(小)于 其兒子結(jié)點(diǎn)中存儲的元素的優(yōu)先級值即父結(jié)點(diǎn)的 優(yōu)先級不低于其兒子結(jié)點(diǎn)的優(yōu)先級。 換句話說，越接近根的結(jié)點(diǎn)中的元素的優(yōu)先級越高，越方便被訪問，因?yàn)楦罘奖惚辉L問。 相應(yīng)的優(yōu)先級樹稱為極小(大)化優(yōu)先級樹。889.4 優(yōu)先隊(duì)列9.4.4用堆實(shí)現(xiàn)優(yōu)先隊(duì)列用優(yōu)先級樹實(shí)現(xiàn)優(yōu)先隊(duì)列仍有不足： Insert(x)和DeleteMin(x)后對結(jié)構(gòu)的維護(hù)，在最壞情況下，仍需O(h)=O(n)。如果讓優(yōu)先級樹近似滿,從而h=log n,達(dá)到最小,那么，結(jié)果

41、將令人滿意：在最壞情況下， Min( )將只需O(1), Insert(x)和DeleteMin(x)后對結(jié)構(gòu)的維護(hù)只需O(log n)。因而引入堆的概念并用堆來實(shí)現(xiàn)優(yōu)先隊(duì)列。(1)堆的概念：如果一棵優(yōu)先級樹是一棵近似滿二叉樹，那么，這棵具有優(yōu)先級性質(zhì)的近似滿二叉樹(外形像堆)就叫做堆。(2)用堆實(shí)現(xiàn)優(yōu)先隊(duì)列： Min( )、Insert(x)和DeleteMin(x)運(yùn)算的實(shí)現(xiàn)899.4 優(yōu)先隊(duì)列9.4.5 用數(shù)組表示堆從而實(shí)現(xiàn)優(yōu)先隊(duì)列(1) 用數(shù)組表示堆： 從1開始對堆的結(jié)點(diǎn)從根開始自上而下逐層、 每層從左到右進(jìn)行編號，然后讓結(jié)點(diǎn)中的元 素按編號在數(shù)組A中與下標(biāo)對號入座。(2) 用數(shù)組表示

42、堆的優(yōu)點(diǎn)： 存儲緊湊，空間利用率高 父子關(guān)系簡單清晰:存放在Ai的是結(jié)點(diǎn)i的元 素, A2i和A2i+1分別是結(jié)點(diǎn)i的左和右兒子 結(jié)點(diǎn)2i和2i+1的元素， Ai/2是結(jié)點(diǎn)i的父結(jié) 點(diǎn)的元素。909.4 優(yōu)先隊(duì)列9.4.5 用數(shù)組表示堆從而實(shí)現(xiàn)優(yōu)先隊(duì)列（續(xù)）(3)數(shù)組實(shí)現(xiàn)優(yōu)先隊(duì)列極小化堆MinHeap919.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.1 問題的提出 已知一個(gè)文本文件，要求把它轉(zhuǎn)換成一個(gè)電子文檔，以便存儲在磁介質(zhì)中或在網(wǎng)絡(luò)上傳輸。從存儲的角度看， 我們自然希望該電子文檔越短越好即存儲占用的空間越 少越好；從傳輸?shù)慕嵌瓤?，我們自然也希望該電子文檔 越短越好

43、即傳輸占用的時(shí)間越少越好。因此，我們要求 轉(zhuǎn)換成的電子文檔盡量地短，盡量地壓縮。 有許多名家說過，把一個(gè)問題表述清楚了，就已經(jīng)解決 了問題的一半。這說明問題的表述很重要，表述得越清 楚、越精確，對問題的解決越好。 上述問題還需要更精確的表述。929.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.2 表述Huffman編碼問題的準(zhǔn)備 對涉及的有關(guān)對象、概念、術(shù)語、和記號的準(zhǔn)備 一個(gè)文本文件就是一個(gè)字符串，記為F。 文本文件中所用到的不同的字符組成的集合，記為C。 C中的字符c在文件中出現(xiàn)的頻率/次數(shù)，記為f(c)或fc。 字符的編碼0/1串。如字符a的ASCII碼是0110

44、0001。 字符編碼的碼長0/1串的串長。記cC的碼長為l(c)。 文件F編碼的碼長原文本文件編碼后的0/1串的累計(jì)長。記為L(F)=cC f(c)* l(c) 。 字符的定長編碼。 ASCII碼是一種定長編碼。不可能壓縮。 字符的變長編碼字符的碼長隨字符而變。 939.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.2 表述Huffman編碼問題的的準(zhǔn)備(續(xù)) 編碼與解碼既要編碼又要解碼，以便復(fù)原文件。 二義性:不能造成一串編碼有兩種理解。 前綴碼：為了解碼時(shí)不會出現(xiàn)二義性， 要求任意一個(gè)字符的編碼不能是另一個(gè) 字符的前綴。 字符集C的前綴碼的表示以C中的 字符為葉結(jié)點(diǎn)的

45、二叉樹，如a0，b101，c100，d111，e1101，f1100 可表示成右圖的二叉樹。 這棵樹叫字符集C的前綴編碼樹,記為T。acbfed0101010101949.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.3 Huffman編碼問題的表述問題數(shù)學(xué)化。 經(jīng)上述準(zhǔn)備，我們看到，字符cC的碼長l (c) 正是c在字符集C的前綴編碼樹T中的深度，記 為dT(c)。這樣，我們的問題可更具體、更精 確地表述為：已知字符串F和出現(xiàn)在F中的字 符集C及C中每一字符c出現(xiàn)的頻率/次數(shù)f(c) ， 要求C的一棵最優(yōu)的前綴編碼樹T, 使得F的編 碼長cC f(c)* dT(c) B

46、(T)達(dá)到最小。這棵 最優(yōu)的前綴編碼樹叫Huffman編碼樹。相應(yīng)的 前綴編碼叫Huffman編碼。959.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.4 求解問題的設(shè)想與分析 (1) 問題的目標(biāo)是求C的最優(yōu)前綴編碼樹T，因此，我們應(yīng) 該先分析一下C的最優(yōu)的前綴編碼樹T的性質(zhì):它是一棵以C中 的字符為葉結(jié)點(diǎn)的健全二叉樹(這容易用反證法加以證明)。 因而一定有兩個(gè)最深的葉結(jié)點(diǎn)是兄弟結(jié)點(diǎn)。 (2) 按照大數(shù)學(xué)家、大教育家波利亞的觀點(diǎn)，“除數(shù)學(xué)和論 證邏輯外,我們所有的知識都是由一些猜想所構(gòu)成的。” 為了 得到有用的結(jié)論、方法，總是從猜想開始。而猜想的依據(jù)是 合情推理。 就擺

47、在面前的問題而言，可直觀地設(shè)想：最深的葉結(jié)點(diǎn)中 有兩個(gè)兄弟是C中頻 度最低的字符x和y ，因?yàn)榫幋a最長的字 符應(yīng)該是頻度最低的字符(這需要證明)。969.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.4 求解問題的設(shè)想與分析(續(xù)) (3) 用字符z代替字符x和y ,讓f(x)+f(y)作為字符z 的頻度 f(z)，相應(yīng)地，在T中刪去兄弟葉結(jié)點(diǎn)x和y ，而且用z 取代已經(jīng)成為葉結(jié)點(diǎn)的x和y的父結(jié)點(diǎn)，得到一棵新的健全二叉編碼樹T，那么，T應(yīng)該是C-x,yz的最優(yōu)前綴編碼樹(這需要證明) 。 若上述設(shè)想與分析正確，那么，問題就有了解法：把C中的字符以其頻度為優(yōu)先級值，且以小者優(yōu)

48、先組織成優(yōu)先隊(duì)列Q。然后反復(fù)地執(zhí)行下面兩個(gè)語句： 刪除Q中優(yōu)先級最高的兩個(gè)字符，設(shè)為x和y； 虛擬字符z(分別以x和y為左和右兒子)，并賦予優(yōu)先 級值f(z)=f(x)+f(y),插入Q；直到Q為空，其結(jié)果就是C的最優(yōu)前綴編碼樹。979.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.5 Huffman編碼問題的解決 從理論上看待Huffman編碼問題，在9.4.6.4 求 解問題的設(shè)想與分析中的(2)和(3)所猜想的分 別是問題的解的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性 質(zhì)。這兩個(gè)性質(zhì)保證了問題可以用基于優(yōu)先隊(duì) 列的前述算法正確地加以求解。所以問題的真 正解決有待對貪心選擇性質(zhì)和最

49、優(yōu)子結(jié)構(gòu)性質(zhì) 作理論上的證明。此外，還得給出Huffman編 碼和解碼的簡潔實(shí)現(xiàn)。989.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.5 Huffman編碼問題的解決(續(xù)) (1) 問題解的貪心選擇性質(zhì)：設(shè)x和y是C 中具有最小頻度的兩個(gè)字符，則存在C的 一個(gè)最優(yōu)前綴碼使x和y具有最長的相同碼 長且僅最后一位編碼不同，即x和y是編碼 樹中最深的一對葉結(jié)點(diǎn)兄弟。 證明：999.4 優(yōu)先隊(duì)列9.4.6 優(yōu)先隊(duì)列的應(yīng)用Huffman編碼9.4.6.5 Huffman編碼問題的解決（續(xù)） (2) 問題解的最優(yōu)子結(jié)構(gòu)性質(zhì)：設(shè)x和y是C的最優(yōu)編碼樹T中的兩個(gè)葉子且為兄弟，z是它們的父親。若將z看作是具有頻率f(z)=f