數(shù)據(jù)結(jié)構(gòu)、算法及其應(yīng)用

1、數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+描述史玉良堆(Heaps)左高樹(LeftistTrees)Chapter9PriorityQueuesFocus堆的實現(xiàn)1堆排序2左高樹3霍夫曼編碼4與FIFO結(jié)構(gòu)的隊隊列不同同，優(yōu)先先隊列中中元素出出隊列的的順序由由元素的的優(yōu)先級級決定。從優(yōu)先先隊列中中刪除元元素是根根據(jù)優(yōu)先先權(quán)高或或低的次次序，而而不是元元素進(jìn)入入隊列的的次序。例-CPU調(diào)度優(yōu)先隊列列優(yōu)先隊列列是0個個或多個個元素的的集合，每個元元素都有有一個優(yōu)優(yōu)先權(quán)或或值。對優(yōu)先隊隊列執(zhí)行行的操作作有：查找插入一個個新元素素刪除優(yōu)先隊列列描述最大大優(yōu)先隊隊列最簡簡單的方方法是采采用無序序線性表表。假設(shè)有一一個具

2、有有n個元元素的優(yōu)優(yōu)先隊列列，插入入操作可可以十分分容易地地在表的的右端末末尾執(zhí)行行，插入入所需時時間為(1)。刪除操操作時必必須查找找優(yōu)先權(quán)權(quán)最大的的元素，即在未未排序的的n個元元素中查查找具有有最大優(yōu)優(yōu)先權(quán)的的元素，所以刪刪除操作作所需時時間為(n)。優(yōu)先隊列列的線性性表描述述如果利用用鏈表，插入操操作在鏈鏈頭執(zhí)行行，時間間為(1)，而每個個刪除操操作所需需時間為為(n)。優(yōu)先隊列列的線性性表描述述另一種描描述方法法是采用用有序線線性表，當(dāng)使用用公式化化描述時時元素按按遞增次次序排列列，使用用鏈表時時則按遞遞減次序序排列，這兩種種描述方方法的刪刪除時間間均為(1)，插入操操作所需需時間為為

3、(n)。優(yōu)先隊列列的線性性表描述述定義：每個節(jié)點點的值都都大于或或等于其其子節(jié)點點（如果果有的話話）值的的樹。最大樹最大樹定義：每個節(jié)點點的值都都小于或或等于其其子節(jié)點點（如果果有的話話）值的的樹。最小樹最小樹定義：最大（最最小）的的完全二二叉樹。最大堆(最小堆堆)最大堆的的插入插入時間間復(fù)雜性性插入策略略從葉到到根只有有單一路路徑，每每一層的的工作需需耗時(1)，因此實實現(xiàn)此策策略的時時間復(fù)雜雜性為O(height)=O(log2n)。最大堆的的刪除最大堆的的刪除刪除時間間復(fù)雜性性刪除策略略產(chǎn)生了了一條從從堆的根根節(jié)點到到葉節(jié)點點的單一一路徑，每層工工作需耗耗時(1)，因此實實現(xiàn)此策策略的時

4、時間復(fù)雜雜性為O(height)=O(log2n)。開始時堆堆中已經(jīng)經(jīng)含有n(n0)個元素?？梢酝ㄍㄟ^在初初始為空空的堆中中執(zhí)行n次插入操操作來構(gòu)構(gòu)建非空空的堆，插入操操作所需需總時間間為O(nlogn)。最大堆的的初始化化更快的堆堆的初始始化策略略？思考從第一個個具有孩孩子的節(jié)節(jié)點開始始，這個個元素在在數(shù)組中中的位置置為i=n/2，如果以以這個元元素為根根的子樹樹已是最最大堆，則此時時不需調(diào)調(diào)整，否否則必須須調(diào)整子子樹使之之成為堆堆。隨后，繼繼續(xù)檢查查以i-1,i-2等節(jié)點為為根的子子樹，直直到檢查查到整個個二叉樹樹的根節(jié)節(jié)點（其其位置為為1）。思想最大堆的的初始化化最大堆的的初始化化類Ma

5、xHeaptemplateclassMaxHeap public:MaxHeap(intMaxHeapSize= 10);MaxHeap() deleteheap;intSize() const returnCurrentSize;T Max() if(CurrentSize=0)throwOutOfBounds();returnheap1;MaxHeap&Insert(constT&x);MaxHeap&DeleteMax(T&x);voidInitialize(Ta, intsize,intArraySize);private :intCurrentSize, MaxSize;T*heap

6、; /元素數(shù)組組 ;最大堆的的插入templateMaxHeap&MaxHeap:Insert(constT&x)/把x插入到最最大堆中中if(CurrentSize=MaxSize)throwNoMem();/為x尋找相應(yīng)應(yīng)插入位位置/i從新的葉葉節(jié)點開開始，并并沿著樹樹上升inti=+CurrentSize；while(i!=1&xheapi/2)/不能把x放入heapiheapi=heapi/2;i/=2;heapi=x;return*this; 最大堆的的刪除templateMaxHeap&MaxHeap:DeleteMax(T&x)/將最大元元素放入入x，并從堆堆中刪除除最大元元素/

7、檢查堆是是否為空空if(CurrentSize=0)throwOutOfBounds();/隊列空x=heap1;/最大元素素/重構(gòu)堆T y=heapCurrentSize-;/最后一個個元素/從根開始始，為y尋找合適適的位置置inti=1,/堆的當(dāng)前前節(jié)點ci=2;/i的孩子最大堆的的刪除while(ci=CurrentSize)/heapci應(yīng)該是i較大的孩孩子if(ciCurrentSize&heapci=heapci) break; /能/不能heapi=heapci;i=ci;ci*=2;heapi=y;return*this; 一棵二叉叉樹，它它有一類類特殊的的節(jié)點叫叫做外部節(jié)點點

8、(externalnode)，用來代代替樹中中的空子子樹，其其余節(jié)點點叫做內(nèi)內(nèi)部節(jié)點點(internalnode)。增加了外外部節(jié)點點的二叉叉樹被稱稱為擴(kuò)充充二叉樹樹(extendedbinary tree)。擴(kuò)充二叉叉樹堆結(jié)構(gòu)是是一種隱隱式數(shù)據(jù)據(jù)結(jié)構(gòu)，用完全全二叉樹樹表示的的堆在數(shù)數(shù)組中是是隱式存存貯的。由于沒沒有存貯貯結(jié)構(gòu)信信息，這這種描述述方法空間利用用率很高高。盡管堆結(jié)結(jié)構(gòu)的時時間和空空間效率率都很高高，但它它不適合合于所有有優(yōu)先隊隊列的應(yīng)應(yīng)用，尤尤其是當(dāng)當(dāng)需要合并兩個個優(yōu)先隊隊列或多多個長度度不同的的隊列時時。因此需需要借助助于其他他數(shù)據(jù)結(jié)結(jié)構(gòu)來實實現(xiàn)這類類應(yīng)用，左高樹樹就能滿滿足這

9、種種要求。Leftist Trees(左高高樹)擴(kuò)充二叉叉樹令s(x)為從節(jié)點x到它的子子樹的外外部節(jié)點點的所有有路徑中中最短的的一條，根據(jù)s(x)的定義可可知，若若x是外部節(jié)節(jié)點，則則s的值為0，若x為內(nèi)部節(jié)節(jié)點，則則它的s值是：mins(L),s(R)+ 1其中L與R分別為x的左右孩孩子。s擴(kuò)充二叉叉樹的s和w定義：當(dāng)當(dāng)且僅當(dāng)當(dāng)一棵二二叉樹的的任何一一個內(nèi)部部節(jié)點，其左孩子子的s值大于等等于右孩孩子的s值時，該二叉叉樹為高度優(yōu)先先左高樹樹（height-biased leftisttree,HBLT）。高度優(yōu)先先左高樹樹定理9-1令x為一個HBLT的內(nèi)部節(jié)節(jié)點，則則以x為根的子子樹的節(jié)節(jié)點

10、數(shù)目目至少為為2s(x)-1。若子樹x有m個節(jié)點，s(x)最多為log2(m+1)。通過最右路徑徑（即，此此路徑是是從x開始沿右右孩子移移動）從從x到達(dá)外部部節(jié)點的的路徑長長度為s(x)。高度優(yōu)先先左高樹樹-性質(zhì)質(zhì)最大HBLT即同時又又是最大大樹的HBLT；最小HBLT即同時又又是最小小樹的HBLT。最大HBLT/最小HBLT插入刪除合并初始化最大HBLT的的操作最大HBLT的插入操操作可借借助于最最大HBLT的合并操操作來完完成。假設(shè)將元元素x插入到名名為H的最大HBLT中，如果果建造一一棵僅有有一個元元素x的最大HBLT然后將它它與H進(jìn)行合并并，結(jié)果果得到的的最大HBLT將包括H中的全部部

11、元素及及元素x。因此插插入操作作只需先先建立一一棵僅包包含欲插插入元素素的HBLT，然后將將它與原原來的HBLT合并即可可。最大HBLT的的插入根是最大大元素，如果根根被刪除除，將留留下分別別以其左左右孩子子為根的的兩棵HBLT的子樹。將這兩兩棵最大大HBLT合并到一一起，便便得到包包含除刪刪除元素素外所有有元素的的最大HBLT。所以刪除除操作可可以通過過刪除根根元素并并對兩個個子樹進(jìn)進(jìn)行合并并來實現(xiàn)現(xiàn)。最大HBLT的的刪除具有n個元素的的最大HBLT，其最右右路徑的的長度為為O(logn)。合并操操作僅需需遍歷欲欲合并的的HBLT的最右路路徑。由由于在兩兩條最右右路徑的的每個節(jié)節(jié)點上只只需耗

12、時時O(1)，因此將將兩棵HBLT進(jìn)行合并并具有對對數(shù)復(fù)雜雜性。通過以上上觀察，在合并并算法中中，僅需需移動右右孩子。合并兩棵棵最大HBLT合并策略略最好用用遞歸來實現(xiàn)。令A(yù)、B為需要合合并的兩兩棵最大大HBLT，如果其其中一個個為空，則將另另一個作作為合并并的結(jié)果果，因此此可以假假設(shè)兩者者均不為為空。為實現(xiàn)合合并，先先比較兩兩個根元元素，較大者作為合合并后的的HBLT的根。假假定A具有較大大的根，且其左左子樹為為L，C是由A的右子樹樹與B合并而成成的HBLT。A與B合并所得得結(jié)果即即是以A的根為根根，L與C為左右子子樹的最最大HBLT。如果L的s值小于C的s值，則C為左子樹樹，否則則L為左子

13、樹樹。合并兩棵棵最大HBLT最大HBLT的的合并最大HBLT的的合并通過將n個元素插插入到最最初為空空的最大大HBLT中來對其其進(jìn)行初初始化，所需時時間為O(nlogn)。更快的方方法？初始化最最大HBLT為得到具具有線性性時間的的初始化化算法，首先創(chuàng)創(chuàng)建n個最大HBLT，每個樹樹中僅包包含n個元素中中的某一一個，這這n棵樹排成成一個FIFO隊列，然然后從隊隊列中依依次刪除除兩個HBLT，將其合合并，然然后再加加入隊列列末尾，直到最最后只有有一棵HBLT。初始化最最大HBLT構(gòu)造五個個元素：7,1,9,11,2的一棵最最大HBLT。首先構(gòu)造造五個單單元素的的最大HBLT，并形成成一個FIFO隊

14、列。例templatevoid MaxHBLT:Meld(HBLTNode* &x,HBLTNode*y)/合并兩棵棵根分別別為*x和*y的左高樹樹，返回回指向新新根x的指針if(!y)return;if(!x)x=y;return;if(x-data data)Swap(x,y);Meld(x-RightChild,y);if(!x-LeftChild) x-LeftChild=x-RightChild;x-RightChild=0;x-s=1;elseif(x-LeftChild-s RightChild-s)Swap(x-LeftChild, x-RightChild);x-s=x-Ri

15、ghtChild-s+1;合并兩棵棵左高樹樹templateMaxHBLT&MaxHBLT:DeleteMax(T&x)/刪除最大大元素，并將其其放入xif(!root)throwOutOfBounds();x=root-data;/最大元素素HBLTNode*L=root-LeftChild;HBLTNode*R=root-RightChild;deleteroot;root=L;Meld(root,R);return*this;從最大HBLT中刪除除最大元元素templatevoid MaxHBLT:Initialize(Ta, intn)/初始化有有n個元素的的HBLT樹QueueHBL

16、TNode*Q(n);Free(root);/刪除老節(jié)節(jié)點/對樹的隊隊列進(jìn)行行初始化化for(inti=1;i=n;i+)HBLTNode*q=newHBLTNode(ai,1);Q.Add(q);HBLTNode*b,*c;for(i=1;i=n-1;i+)Q.Delete(b).Delete(c); Meld(b,c);Q.Add(b);if(n)Q.Delete(root);最大HBLT的的初始化化堆排序(Heap Sort)機(jī)器調(diào)度度(MachineScheduling)霍夫曼編編碼(HuffmanCodes)應(yīng)用先將要排排序的n個元素初初始化為為一個最最大堆，然后每每次從堆堆中提取取

17、（即刪刪除）元元素。各各元素將將按遞減減次序排排列。初始化所所需要的的時間為為(n)，每次刪刪除所需需要的時時間為O(logn)，因此總總時間為為O(nlogn)。堆排序templatevoid HeapSort(Ta,intn)/利用堆排排序算法法對a1:n進(jìn)行排序序/創(chuàng)建一個個最大堆堆MaxHeap H(1);H.Initialize(a,n,n);/從最大堆堆中逐個個抽取元元素T x;for(inti =n-1;i = 1; i-)H.DeleteMax(x);ai+1=x;/在堆的析析構(gòu)函數(shù)數(shù)中保存存數(shù)組aH.Deactivate(x);堆排序算算法實現(xiàn)現(xiàn)堆排序假設(shè)文本本是由a,u,x

18、,z組成的字字符串，若這個個字符串串的長度度為1000，每個字字符用一一個字節(jié)節(jié)來存貯貯，共需需1000個字節(jié)（即8000位）的空空間。如如果每個個字符用用2位二進(jìn)制制來編碼碼（00=a,01=x,10=u,11=z），則用用2000位二進(jìn)制制即可表表示1000個字符。字符串a(chǎn)axuaxz的壓縮編編碼為二二進(jìn)制串串0000011000011。例-壓縮縮此外，還還需要一一定的空空間來存存放編碼碼表，可可采用如如下格式式來存儲儲：符號個數(shù)數(shù),代碼1,符號1,代碼2,符號2,符號個數(shù)數(shù)及每個個符號分分別用8位二進(jìn)制制來表示示，每個個代碼需需占用log2(符號個數(shù)數(shù))位二進(jìn)制制。因此此，代碼碼表需占占

19、用5*8+4*2=48位，壓縮縮比為8000/2048=3.9。例字符串a(chǎn)axuaxz的壓縮編編碼為二二進(jìn)制串串00000110000111，每個字字符的編編碼具有有相同的的位數(shù)（兩位）。從左到右右依次從從位串中中取出2位，通過過查編碼碼表便可可獲得原原字符串串。例-解壓壓一個字符符出現(xiàn)的的次數(shù)稱稱為頻率率（frequency）在字符串串a(chǎn)axuaxz中，a出現(xiàn)了三三次。a,x,u,z，在這個個字符串串中出現(xiàn)現(xiàn)的頻率率分別為為3，2，1，1。頻率采用可變長編編碼。使用編碼碼(0=a,10=x,110=u,111=z)。如果四四個字符符的出現(xiàn)現(xiàn)頻率分分別為(996,2,1,1)，則每個個字符用用

20、2位編碼所所得到編編碼的長長度為2000位，而用用可變長長編碼則則僅為1006位。方案可變長編編碼:沒有任何何一個代代碼是另另一代碼碼的前綴綴。因此，當(dāng)當(dāng)從左到到右檢查查代碼時時，可以以很確定定地得到到與實際際代碼相相匹配的的字符。解碼依據(jù)據(jù)可以利用用擴(kuò)充二二叉樹來來派生一一個實現(xiàn)現(xiàn)可變長長編碼的的特殊類類，該類類滿足上上述前綴綴性質(zhì)，被稱為為霍夫曼曼編碼?；舴蚵幘幋a在擴(kuò)充二二叉樹中中，可對對從根到到外部節(jié)節(jié)點的路路徑進(jìn)行行編碼，方法是是向左孩子子移動時時取0，向右孩孩子移動動時取1。霍夫曼編編碼到節(jié)點(a,b,c,d,e,f)的路徑編編碼分別別為(00，010，011，100，101，11)霍夫曼編編碼對于一棵棵具有外外部節(jié)點點1，n的擴(kuò)充二二叉樹，對應(yīng)的的壓縮編編碼串的的長度為為：其中L(i)為從根到到達(dá)外部部節(jié)點i的路徑長長度（即即路徑的的邊數(shù)）；F(i)為外部節(jié)節(jié)點i的權(quán)值(壓縮中字字符的頻頻率)；WEP