娓呭崕澶у2001騫寸澹爺絀剁敓鑰冭瘯鏁版嵁緇撴瀯璇曢_璺ㄨ€冪綉

澶嶄範(fàn)绱у紶錛岀劍澶寸儌棰濓紵閫嗛杞昏錛屾潵璺ㄨ€冪瀛ｉ泦璁惀錛屽府浣犲鏂規(guī)硶錛屽畾鏂規(guī)錛?/span> 浜嗚В涓€涓?>

銆€銆€涓€銆佽瘯緇欏嚭涓嬪垪鏈夊叧騫舵煡闆?mfsets)鐨勬搷浣滃簭鍒楃殑榪愮畻緇撴灉錛?/p>

銆€銆€union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)銆?union鏄悎騫惰繍綆楋紝鍦ㄤ互鍓嶇殑涔︿腑鍛藉悕涓簃erge)

銆€銆€瑕佹眰

銆€銆€(1) 瀵逛簬union(i,j)錛屼互i浣滀負(fù)j鐨勫弻浜詫紱 (5鍒?

銆€銆€(2) 鎸塱鍜宩涓烘牴鐨勬爲(wèi)鐨勯珮搴﹀疄鐜皍nion(i,j)錛岄珮搴﹀ぇ鑰呬負(fù)楂樺害灝忚€呯殑鍙屼翰錛?(5鍒?

銆€銆€(3) 鎸塱鍜宩涓烘牴鐨勬爲(wèi)鐨勭粨鐐逛釜鏁板疄鐜皍nion(i,j)錛岀粨鐐逛釜鏁板ぇ鑰呬負(fù)緇撶偣涓暟灝忚€呯殑鍙屼翰錛?(5鍒?

銆€銆€浜屻€佽鍦?鍦?A,B,C,D)涔嬮棿鏋惰鏈?搴фˉ,濡傚浘鎵€紺?

銆€銆€瑕佹眰浠庢煇涓€鍦板嚭鍙?緇忚繃姣忓駭妗ユ伆宸т竴嬈?鏈€鍚庝粛鍥炲埌鍘熷湴

銆€銆€(1) 璇曞氨浠ヤ笂鍥懼艦璇存槑:姝ら棶棰樻湁瑙ｇ殑鏉′歡鏄粈涔? (5鍒?

銆€銆€(2) 璁懼浘涓殑欏剁偣鏁頒負(fù)n,璇曠敤C鎴朠ascal鎻忚堪涓庢眰瑙ｆ闂鏈夊叧鐨勬暟鎹粨鏋勫茍緙栧啓涓€涓畻娉?鎵懼嚭婊¤凍瑕佹眰鐨勪竴鏉″洖璺? (10鍒?

銆€銆€涓夈€侀拡瀵逛互涓嬫儏鍐電‘瀹氶潪閫掑綊鐨勫綊騫舵帓搴忕殑榪愯鏃墮棿(鏁版嵁姣旇緝嬈℃暟涓庣Щ鍔ㄦ鏁?:

銆€銆€(1) 杈撳叆鐨刵涓暟鎹叏閮ㄦ湁搴? (5鍒?

銆€銆€(2) 杈撳叆鐨刵涓暟鎹叏閮ㄩ€嗗悜鏈夊簭; (5鍒?

銆€銆€(3) 闅忔満鍦拌緭鍏涓暟鎹? (5鍒?

銆€銆€鍥涖€佺畝鍗曞洖絳旀湁鍏矨VL鏍?wèi)鐨勯棶棰?

銆€銆€(1) 鍦ㄦ湁N涓粨鐐圭殑AVL鏍?wèi)涓?涓虹粨鐐瑰鍔犱竴涓瓨鏀劇粨鐐歸珮搴︾殑鏁版嵁鎴愬憳,閭ｄ箞姣忎竴涓粨鐐歸渶瑕佸鍔犲灝戜釜瀛椾綅(bit)? (5鍒?

銆€銆€(2) 鑻ユ瘡涓€涓粨鐐逛腑鐨勯珮搴﹁鏁板櫒鏈?bit,閭ｄ箞榪欐牱鐨凙VL鏍?wèi)鍙互鏈夊灏戝?鏈€灝戞湁澶氬皯涓叧閿爜? (5鍒?

銆€銆€浜斻€佽涓€涓暎鍒楄〃鍖呭惈hashSize=13涓〃欏?.鍏朵笅鏍囦粠0鍒?2,閲囩敤綰挎€ф帰鏌ユ硶瑙ｅ喅鍐茬獊. 璇鋒寜浠ヤ笅瑕佹眰,灝嗕笅鍒楀叧閿爜鏁ｅ垪鍒拌〃涓?

銆€銆€10 100 32 45 58 126 3 29 200 400 0

銆€銆€(1) 鏁ｅ垪鍑芥暟閲囩敤闄ょ暀浣欐暟娉?鐢?hashSize(鍙栦綑榪愮畻)灝嗗悇鍏抽敭鐮佹槧鍍忓埌琛ㄤ腑. 璇鋒寚鍑烘瘡涓€涓駭鐢熷啿紿佺殑鍏抽敭鐮佸彲鑳戒駭鐢熷灝戞鍐茬獊. (7鍒?

銆€銆€(2) 鏁ｅ垪鍑芥暟閲囩敤鍏堝皢鍏抽敭鐮佸悇浣嶆暟瀛楁姌鍙犵浉鍔? 鍐嶇敤%hashSize灝嗙浉鍔犵殑緇撴灉鏄犲儚鍒拌〃涓殑鍔炴硶. 璇鋒寚鍑烘瘡涓€涓駭鐢熷啿紿佺殑鍏抽敭鐮佸彲鑳戒駭鐢熷灝戞鍐茬獊. (8鍒?

銆€銆€鍏€佽涓€媯典簩鍙夋爲(wèi)鐨勭粨鐐瑰畾涔変負(fù)

銆€銆€struct BinTreeNode{

銆€銆€ElemType data;

銆€銆€BinTreeNode *leftChild, *rightChild;

銆€銆€}

銆€銆€鐜伴噰鐢ㄨ緭鍏ュ箍涔夎〃琛ㄧず寤虹珛浜屽弶鏍? 鍏蜂綋瑙勫畾濡備笅:

銆€銆€(1) 鏍?wèi)鐨勬牴缁撶偣浣滀负鐢卞瓙鏍?wèi)鏋勬垚鐨勮〃鐨勮〃鍚嶆斁鍦ㄨ〃鐨勬渶鍓嶉潰;

銆€銆€(2) 姣忎釜緇撶偣鐨勫乏瀛愭爲(wèi)鍜屽彸瀛愭爲(wèi)鐢ㄩ€楀彿闅斿紑. 鑻ヤ粎鏈夊彸瀛愭爲(wèi)娌℃湁宸﹀瓙鏍? 閫楀彿涓嶈兘鐪佺暐.

銆€銆€(3) 鍦ㄦ暣涓箍涔夎〃琛ㄧず杈撳叆鐨勭粨灝懼姞涓婁竴涓壒孌婄殑絎﹀彿(渚嬪鈥?鈥?琛ㄧず杈撳叆緇撴灉.

銆€銆€渚嬪,瀵逛簬濡傚彸鍥炬墍紺虹殑浜屽弶鏍? 鍏跺箍涔夎〃琛ㄧず涓篈(B(D,E(G,)),C(,F))

銆€銆€A

銆€銆€/ \

銆€銆€B C

銆€銆€/ \ \

銆€銆€D E F

銆€銆€/

銆€銆€G

銆€銆€姝ょ畻娉曠殑鍩烘湰鎬濊礬鏄?渚濇浠庝繚瀛樺箍涔夎〃鐨勫瓧絎︿覆ls涓緭鍏ユ瘡涓瓧絎? 鑻ラ亣鍒扮殑鏄瓧姣?鍋囧畾浠ュ瓧姣嶄綔涓虹粨鐐圭殑鍊?, 鍒欒〃紺烘槸緇撶偣鐨勫€? 搴斾負(fù)瀹冨緩绔嬩竴涓柊鐨勭粨鐐? 騫舵妸璇ョ粨鐐逛綔涓哄乏瀛愬コ(褰搆=1)鎴栨湁瀛愬コ(褰搆=2)閾炬帴鍒板叾鍙屼翰緇撶偣涓? 鑻ラ亣鍒扮殑鏄乏鎷彿鈥?鈥? 鍒欒〃鏄庡瓙琛ㄧ殑寮€濮?灝唊緗負(fù)1;鑻ラ亣鍒扮殑鏄彸鎷彿鈥?鈥? 鍒欒〃鏄庡瓙琛ㄧ粨鏋? 鑻ラ亣鍒扮殑鏄€楀彿鈥?鈥? 鍒欒〃紺轟互宸﹀瓙濂充負(fù)鏍圭殑瀛愭爲(wèi)澶勭悊瀹屾瘯,搴旀帴鐫€澶勭悊浠ュ彸瀛愬コ涓烘牴鐨勫瓙鏍? 灝唊緗負(fù)2.

銆€銆€鍦ㄧ畻娉曚腑浣跨敤浜嗕竴涓爤s, 鍦ㄨ繘鍏ュ瓙琛ㄤ箣鍓?灝嗘牴緇撶偣鎸囬拡榪涙爤, 浠ヤ究鎷彿鍐呯殑瀛愬コ閾炬帴涔嬬敤. 鍦ㄥ瓙琛ㄥ鐞嗙粨鏉熸椂閫€鏍? 鐩稿叧鐨勬爤鎿嶄綔濡備笅:

銆€銆€MakeEmpty(s) 緗┖鏍?/p>

銆€銆€Push(s,p) 鍏冪礌p榪涙爤

銆€銆€Pop(s) 榪涙爤

銆€銆€Top(s) 瀛樺彇鏍堥《鍏冪礌鐨勫嚱鏁?/p>

銆€銆€涓嬮潰緇欏嚭浜嗗緩绔嬩簩鍙夋爲(wèi)鐨勭畻娉? 鍏朵腑鏈?涓鍙ョ己澶? 璇烽槄璇繪綆楁硶騫舵妸緙哄け鐨勮鍙ヨˉ涓? (姣忕┖3鍒?

銆€銆€Void CreateBinTree(BinTreeNode *&BT, char ls){

銆€銆€Stacks; MakeEmpty(s);

銆€銆€BT=NULL; //緗簩鍙夋爲(wèi)

銆€銆€BinTreeNode *p;

銆€銆€int k;

銆€銆€istream ins(ls); //鎶婁覆ls瀹氫箟涓鴻緭鍏ュ瓧絎︿覆嫻佸璞ns

銆€銆€Char ch;

銆€銆€ins>>ch; //浠巌ns欏哄簭璇誨叆涓€涓瓧絎?/p>

銆€銆€While(ch!=鈥?鈥?{ //閫愪釜瀛楃澶勭悊,鐩村埌閬囧埌''#''涓烘

銆€銆€Switch(ch){

銆€銆€case鈥?鈥? _______(1)_______

銆€銆€k=1;

銆€銆€break;

銆€銆€case鈥?鈥? pop(s);

銆€銆€break;

銆€銆€case鈥?鈥? _______(2)_______

銆€銆€break;

銆€銆€default: p=new BinTreeNode;

銆€銆€_______(3)_______

銆€銆€p->leftChild=NULL;

銆€銆€p->rightChild=NULL;

銆€銆€if(BT==NULL)

銆€銆€_______(4)_______

銆€銆€else if (k==1) top(s)->leftChild=p;

銆€銆€else top(s)->rightChild=p;

銆€銆€}

銆€銆€_______(5)_______

銆€銆€}

銆€銆€}

銆€銆€涓冦€佷笅闈㈡槸涓€涓敤C緙栧啓鐨勫揩閫熸帓搴忕畻娉? 涓轟簡閬垮厤鏈€鍧忔儏鍐?鍙栧熀鍑嗚褰昿ivot閲囩敤浠巐eft,right鍜宮id=[(left+right)/2]涓彇涓棿鍊? 騫朵氦鎹㈠埌right浣嶇疆鐨勫姙娉? 鏁扮粍a瀛樻斁寰呮帓搴忕殑涓€緇勮褰? 鏁版嵁綾誨瀷涓篢ype, left鍜宺ight鏄憜鎺掑簭瀛愬尯闂寸殑鏈€宸︾鐐瑰拰鏈€鍙崇鐐?

銆€銆€Void quicksort(Type a,int left,int right){

銆€銆€Type temp;

銆€銆€If(leftType pivot=median3(a,left,right);

銆€銆€Int I=left, j=right-1;

銆€銆€For( ; ; ){

銆€銆€While(iWhile(iif(itemp=a[i]; a[j]=a[i]; a[i]=temp;

銆€銆€I++; j--;

銆€銆€}

銆€銆€else break;

銆€銆€}

銆€銆€if(a[i]>pivot)

銆€銆€{temp=a[i]: a[i]=a[right]; a[right]=temp;}

銆€銆€quicksort(a,left,i-1); //閫掑綊鎺掑簭宸﹀瓙鍖洪棿

銆€銆€quicksort(a,i+1,right); //閫掑綊鎺掑簭鍙沖瓙鍖洪棿

銆€銆€}

銆€銆€}

銆€銆€(1) 鐢–鎴朠ascal瀹炵幇涓夎€呭彇涓瓙紼嬪簭 median3(a,left,right); (5鍒?

銆€銆€(2) 鏀瑰啓 quicksort 綆楁硶, 涓嶇敤鏍堟秷鍘葷浜屼釜閫掑綊璋冪敤 quicksort(a,i+1,right); (5鍒?

銆€銆€(3) 緇х畫鏀瑰啓 quicksort 綆楁硶, 鐢ㄦ爤娑堝幓鍓╀笅鐨勯€掑綊璋冪敤. (5鍒?