排序問題和離散集合的操作

第三章排序問題和離散集合的操作3.3基數(shù)排序基于比較的排序算法，算法的運(yùn)行時間下界為I”nlogn）?；鶖?shù)排序方法可以按線性時間運(yùn)行。331基數(shù)排序算法的思想方法n個元素的鏈表L={a「a2,……’a.}，每個元素關(guān)鍵字的值有如下形式：dkdkAd10_dj_9,1_i_k1、m=12、按關(guān)鍵字的數(shù)字dm，把元素分布到10個鏈表L。，Li,……±9，使得關(guān)鍵字的dm=i的元素，都分布在鏈表Lj中；3、把10個鏈表，按照鏈表的下標(biāo)由0到9的順序重新鏈接成一個新的鏈表L。4、m=m，1，若m_k，轉(zhuǎn)2,否則結(jié)束例3.4假設(shè)鏈表L中有如下10個元素，其關(guān)鍵字值分別為：3097、3673、2985、1358、6138、9135、4782、1367、3684、0139。第一步，按關(guān)鍵字中的數(shù)字d!，把L中的元素分布到鏈表L°~L9的情況如下：L0L1Pl3l4l5l6l7l8l94782367336842985309713580139913513676138把L。~L9的元素順序鏈接到L后，在L中的元素順序如下：L:4782367336842985913530971367135861380139第二步，按數(shù)字d2,把L中的元素分布到L0~L9的情況如下:L。L1l2L3l4L591351-6L7135813671-8L93673478230976138368401392985把L0~L9的元素順序鏈接到L后，在L中的元素順序如下L:9135613801391358136736734782368429853097

第三步，按數(shù)字d3，把L中的元素分布到Lo~L9的情況如下:L0L1l2L3l4L5L6L7l8l93097913513583673478229856138136736840139把Lo~L9的元素順序鏈接到L后，在L中的元素順序如下：L:3097913561380139135813673673368447822985第四步，按數(shù)字d4，把L中的元素分布到Lo~L9的情況如下:l0l1l2l3l4l5l6l7l8l90139135829853097478261389135136736733684L把Lo~L9的元素順序鏈接到后，在L中的元素順序如下：L:0139135813672985309736733684478261389135在第四步之后，鏈表中的所有關(guān)鍵字都已經(jīng)排序了。next指向下一個元素。3.3.2基數(shù)排序算法的實(shí)現(xiàn)next指向下一個元素。用雙循環(huán)鏈表，用成員變量prior指向前一個元素，用成員變量算法3.10基數(shù)排序輸入：存放元素的鏈表L,元素個數(shù)n,及關(guān)鍵字的數(shù)字位數(shù)k輸出：按遞增順序排序的鏈表Ltemplate<classType>voidradix_sort(Type*L,intk){Type*Lhead[10],*p;inti,j;for(i=0;i<10;i++)Lhead[i]=newType;for(i=0;i<k;i++){for(j=0;j<10;j++)10.Lhead[j]->prior=Lhead[j]->next=Lhead[j];while(L->next!=L){p=del_entry(L);j=get_digital(p,i);/*分配10個鏈表的頭結(jié)點(diǎn)*//*把10個鏈表置為空表*//*取L的第一個元素于p并把它從L刪去*//*從p所指向的元素關(guān)鍵字取第i個數(shù)字*/

add_entry(Lhead[j],p);/*}for(j=0;j<10;j++)append(L,Lhead[j]);}for(i=0;i<10;i++)delete(Lhead[i]);}把p加入鏈表Lhead[j]的表尾*//*把10個鏈表的元素鏈接到L*//*釋放10個鏈表的頭結(jié)點(diǎn)*/算法3.11取下并刪去雙循環(huán)鏈表的第一個元素輸入：鏈表的頭結(jié)點(diǎn)指針L輸出：被取下第一個元素的鏈表L,指向被取下元素的指針，template<classType>Type*del_entry(Type*L){Type*p;p=L->next;if(p!=L){p->prior->next=p->next;p->next->prior=p->prior;}elsep=NULL;retuenp;}算法3.12把一個元素插入雙循環(huán)鏈表的表尾輸入：鏈表頭結(jié)點(diǎn)的指針L,被插入元素的指針p輸出：插入了一個元素的鏈表Ltemplate<classType>voidadd_entry(Type*L,Type*p)TOC\o"1-5"\h\z{p->prior=L->prior;p->next=L;L->prior->next=p;L->prior=p;}算法3.13取p所指向元素關(guān)鍵字的第i位數(shù)字(最低位為第0位)輸入：指向某元素的指針p,該元素關(guān)鍵字的的第i位數(shù)字輸出：該元素關(guān)鍵字的的第i位數(shù)字templatevclassType〉intget_digital(Type*p,inti){intkey;key=p_>key;if(i!=0)key=key/power(10,i);returnkey%10;}算法3.14把鏈表L1附加到鏈表L的末端輸入：指向鏈表L及L1的頭結(jié)點(diǎn)指針輸出：附加了新內(nèi)容的鏈表Ltemplate<classType>voidappend(Type*L,Type*L1){if(L1->next!=L1){L->prior->next=L1->next;L1->next->prior=L->prior;L1->prior->next=L;L->prior=L1->prior;TOC\o"1-5"\h\z}}算法3.11、3.12、3.14的執(zhí)行時間是常數(shù)時間。輸出：按遞增順序排序的鏈表Ltemplate<classType>voidradix_sort(Type*L,intk){Type*Lhead[10],*p;inti,j;for(i=0;i<10;i++)Lhead[i]=newType;for(i=0;i<k;i++){for(j=0;j<10;j++)10.Lhead[j]->prior=Lhead[j]->next=Lhead[j];while(L->next!=L){p=del_entry(L);j=get_digital(p,i);/*分配10個鏈表的頭結(jié)點(diǎn)*//*把10個鏈表置為空表*//*取L的第一個元素于p并把它從L刪去*//*從p所指向的元素關(guān)鍵字取第i個數(shù)字*/add_entry(Lhead[j],p);/*}for(j=0;j<10;j++)append(L,Lhead[j]);}for(i=0;i<10;i++)delete(Lhead[i]);}算法3.13的執(zhí)行時間取決于函數(shù)power(x,y)的執(zhí)行時間，power函數(shù)計算以x為底的y次幕。假定，x是有限長度的整數(shù)，后面將說明，該函數(shù)的執(zhí)行時間將是0(log北如果y是一個大于0的常整數(shù)，則該函數(shù)的執(zhí)行時間也是常數(shù)。所以，它們都是0(1)。3.3.3基數(shù)排序算法的分析―、復(fù)雜性分析算法的執(zhí)行時間是0(kn)。當(dāng)k是常數(shù)時，它的執(zhí)行時間是4(n)。工作單元為0(1)。二、正確性證明用歸納法證明，算法經(jīng)過k步(假定元素的關(guān)鍵字有k位數(shù)字)的重新分布和重新鏈接之后，序列中的元素是按順序排列的：i1:L中的元素按其關(guān)鍵字的最低位數(shù)字分布到10個鏈表，然后，再把這些鏈表按順序鏈接成一個鏈表L,則L中的元素將按其關(guān)鍵字的最低數(shù)字排序；i=2:L中的元素再按其關(guān)鍵字的十位數(shù)字分布到10個鏈表令x和y是L序列中任意兩個元素，

x的關(guān)鍵字的最低兩位數(shù)字分別為y的關(guān)鍵字的最低兩位數(shù)字分別為a、b,

c、do若ac,則a、b,

c、do重新鏈接到L去時，y先于x被鏈接到L,它們是按最低兩位數(shù)字的順序排序的。若ca同理可證。a=c，則它們分布在同一個鏈表。這時，若b>d,則y先于x被分布到這個鏈表。重新鏈接到L去時，仍維持這個順序，它們也按最低兩位數(shù)字的順序排列。x和y是任意的，所以，鏈表中的元素都按最低兩位數(shù)字的順序排列。歸納步的證明類似，留作練習(xí)。3.4離散集合的操作在很多應(yīng)用中，經(jīng)常把n個元素劃分成若干個集合，然后把某兩個集合合并成一個集合，或者尋找包含某個特定元素的集合。例：對集合S={1,2,…，8}定義如下的等價關(guān)系：R={:::x,y|x：=Sy:=S(x_y)%3=0}求S關(guān)于R的等價類，初始化：{1}{2}{3}{4}{5}{6}{7}{8};1R4,有：{1,4}{2}{3}{5}{6}{7}{8};4R7,有:{1,4,7}{2}{3}{5}{6}{8};2R5,有:{1,4,7}{2,5}{3}{6}{8};5R8,有:{1,4,7}{2,5,8}{3}{6};3R6,有：{1,4,7}{2,5,8}{3,6};find操作：把元素x和y所在的集合找出來，union操作：把兩個集合合并成一個集合。3.4.1離散集合的數(shù)據(jù)結(jié)構(gòu)―、第一種數(shù)據(jù)結(jié)構(gòu)

structTree_node{strueeTree_node*p;/*指向父親結(jié)點(diǎn)的指針*/Typex;/*structTree_node{strueeTree_node*p;/*指向父親結(jié)點(diǎn)的指針*/Typex;集合可以由集合中的元素來命名，這個元素就稱為該集合的代表元。集合中的所有元素，都有資格作為集合的代表元。要把元素x所代表的集合，與元素y所代表的集合合并起來，只要分別找出元素素x和元y所在集合的根結(jié)點(diǎn)，使元素y的根結(jié)點(diǎn)的父指針指向元素x的根結(jié)點(diǎn)即可。圖3.7(a)表示由集合{1,3,5,8},{2,7,10},{4,6},{9}所組成的森林;108S26■:3.7離散集合的表示形式由此，可以把離散集合中find操作和union操作的含義定義如下:find(x):尋找元素x所在集合的根結(jié)點(diǎn)；union(x,y):把元素x和元素y108S26■:3.7離散集合的表示形式由此，可以把離散集合中find操作和union操作的含義定義如下:find(x):尋找元素x所在集合的根結(jié)點(diǎn)；union(x,y):把元素x和元素y所在集合合并成一個集合。缺點(diǎn)：樹的高度可能很大，變成退化樹，成為線性表。如圖3.8(a)。find操作可能需要■?,)時間。n12圖3.8n個集合合并的兩種情況、改進(jìn)的數(shù)據(jù)結(jié)構(gòu)structTree_node{strueeTree_nodestrueeTree_node*p;/*指向父親結(jié)點(diǎn)的指針*/intrank;/*結(jié)點(diǎn)的秩intrank;Typex;/*存放在結(jié)點(diǎn)中的元素*/｝；typedefstructTree_nodeNODE;結(jié)點(diǎn)的秩等于以該結(jié)點(diǎn)作為子樹的根時，該子樹的高度。union(x,y)操作：令x和y是當(dāng)前森林中兩棵不同樹的根結(jié)點(diǎn)，如果rank(x):::rank(y)，把y作為x的父親，rank(x)和rank(y)不變;如果rank(x)二rank(y)，就把y作為x的父親，并使rank(y)加1；如果rank(x)rank(y)，把x作為y的父親，rank(x)和rank(y)不變；例：圖3.8(b)表示采用這個方法對n個集合進(jìn)行合并時的情況。三、用數(shù)組存放元素structTree_node{intindex;/*指向父親結(jié)點(diǎn)的下標(biāo)*/intrank;/*結(jié)點(diǎn)的秩*/Typex;/*存放在結(jié)點(diǎn)中的元素*/};structTree_nodenode[n];這時，父結(jié)點(diǎn)的指針，用該結(jié)點(diǎn)在數(shù)組中的下標(biāo)表示。3.4.2union、find操作及路徑壓縮一、路徑壓縮find操作時，找到根結(jié)點(diǎn)y之后，再沿著這條路徑，改變路徑上所有結(jié)點(diǎn)的父指針，使其直接指向y。如圖3.9所示。圖3一9路徑壓縮、算法描述算法3.15離散集合的find操作輸入：指向結(jié)點(diǎn)x的指針xp輸出：指向結(jié)點(diǎn)X所在集合的根結(jié)點(diǎn)的指針ypNODE*find(NODE*xp)2.3.4./*尋找xp所在集合的根結(jié)點(diǎn)yp*/NODE*wp,*yp=xp,*zp=xp;3.4./*尋找xp所在集合的根結(jié)點(diǎn)yp*/5.6.yp=yp->p;while(zp->p!=NULL){/*路徑壓縮*/wp=zp_>pzp->p=yp;zp=wp;}returnyp;}算法3.16離散集合的union操作輸入：指向結(jié)點(diǎn)x和結(jié)點(diǎn)y的指針xp和yp輸出：結(jié)點(diǎn)x和結(jié)點(diǎn)y所在集合的并集，指向該并集根結(jié)點(diǎn)的指針1.NODE*union(NODE*xp,NODE*yp){NODE*up,*vp;up=find(xp);vp=find(yp);if(up_>rank<=vp_>rank){up->p=vp;if(up->rank==vp->rank)vp->rank++;up=vp;}elsevp->p=up;returnup;}例3.5集合{1,2,3,4},{5,6,7,8},如圖3.10(a)所示，在執(zhí)行了union(1,5)之后，結(jié)果如圖3.10(b)所示。在union操作中，對結(jié)點(diǎn)1和5執(zhí)行了find操作，結(jié)點(diǎn)1和5的路徑都被壓縮了。(a)圖3.10集合union操作的例子(a)三、算法分析X是樹中的任意結(jié)點(diǎn)，x.p指向x的父親結(jié)點(diǎn)。得到下面兩個結(jié)論。1、結(jié)論3.1x.p->rankx.ran*1。2、結(jié)論3.2xrank的初始值為0,在一系列的union操作中遞增，直到x不再是樹的根結(jié)點(diǎn)為止。一旦x變?yōu)榱硪粋€結(jié)點(diǎn)的兒子，它的秩就不再改變。3、弓I理3.1若結(jié)點(diǎn)x的秩為xrank，則以x為根的樹，其結(jié)點(diǎn)數(shù)至少為2x-ranko(含義：結(jié)點(diǎn)數(shù)至少為n=2x』ank的樹，其高度至多為logn=x.rank)證明用歸納法證明。開始時，x本身是一棵數(shù)，其秩x.rank=0，其結(jié)點(diǎn)數(shù)等于2°=1，引理成立。假定x和y分別是兩棵樹的根結(jié)點(diǎn)，其秩分別是x.rank，和y.ranko在union(x,y)操作之前，x和y為根的樹，其結(jié)點(diǎn)數(shù)分別至少為2x-rank和2y-ranko在union(x,y)操作