c語(yǔ)言常用經(jīng)典算法分析

C語(yǔ)言常用經(jīng)典算法分析中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnc語(yǔ)言常用經(jīng)典算法分析.冒泡法:這是最原始,也是眾所周知的最慢的算法了。他的名字的由來(lái)因?yàn)樗墓ぷ骺磥?lái)象是冒泡:ttinclude<iostream.h>voidBubbleSort(int*pData,intCount)IintiTemp;for(inti=l;i<Count;i)(for(intj二Count-1;j>=i;j--)(中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnif(pData[j]<pData[j-1])iiTemp=pData[j-1];pData[j-l]=pData[j];pDatafj]=iTemp;voidmainOintdata[]={10,9,8,7,6,5,4};中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnBubbleSort（data,7）;for（inti=0;i<7;i）cout?data[i]?**;coutくく“、n";）倒序（最糟情況）第一輪:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8（交換3次）第二輪:7,10,9,8->7,10,8,9->7,8,10,9（交換2次）第一輪:7,8,10,9->7,8,9,10（交換1次）循環(huán)次數(shù):6次交換次數(shù):6次中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn其他：第一輪：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9（交換2次）第二輪:7,8,10,9->7,8,10,9->7,8,10,9（交換0次）第一輪：7,8,10,9->7,8,9,10（交換1次）循環(huán)次數(shù)：6次交換次數(shù)：3次上面我們給出了程序段,現(xiàn)在我們分析它:這里,影響我們算法性能的主要部分是循環(huán)和交換,顯然，次數(shù)越多,性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為12...n-l?寫成公式就是l/2*(n-l)*n?，F(xiàn)在注意，我們給出〇方法的定義:若存在ー常量K和起點(diǎn)nO,使當(dāng)n>=nO時(shí)，有f(n)く=K*g(n),則f(n)=O(g(n))?(呵呵，不要說(shuō)沒學(xué)好數(shù)學(xué)呀,對(duì)于編程數(shù)學(xué)是非常重要的!??！)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn現(xiàn)在我們來(lái)看l/2*(nT)*n,當(dāng)K=l/2,nO=l,g(n)=n*n時(shí)，1/2*(n-l)*n<=l/2*n*n=K*g(n)〇所以f(n)=0(g(n))=O(n*n)〇所以我們程序循環(huán)的復(fù)雜度為〇(n*n)。再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同,交換不同。其實(shí)交換本身同數(shù)據(jù)源的有序程度有極大的關(guān)系,當(dāng)數(shù)據(jù)處于倒序的情況時(shí),交換次數(shù)同循環(huán)ー樣(每次循環(huán)判斷都會(huì)交換),復(fù)雜度為0(n*n)。當(dāng)數(shù)據(jù)為正序,將不會(huì)有交換。復(fù)雜度為0(0)?亂序時(shí)處于中間狀態(tài)。正是由于這樣的原因，我們通常都是通過(guò)循環(huán)次數(shù)來(lái)對(duì)比算法。網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/.交換法：交換法的程序最淸晰簡(jiǎn)單,每次用當(dāng)前的元素ーー的同其后的元素比較并交換。#include<iostream.h>中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnvoidExchangeSort(int*pData,intCount)intiTemp;for(inti=0;i<Count-l;i)for(intj=i1;j<Count;j)if(pData[j]<pData[i])iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn)voidmain()(intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,7);for(inti=0;i<7;i)coutくくdata[i]くく“”；cout?*\n";)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn倒序(最糟情況)第一輪:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交換3次)第二輪:7,10,9,8->7,9,10,8->7,8,10,9(交換2次)第一輪:7,8,10,9->7,8,9,10(交換1次)循環(huán)次數(shù):6次交換次數(shù):6次其他：第一輪：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9（交換1次）第二輪:7,10,8,9->7,8,10,9->7,8,10,9（交換1次）第一輪：7,8,10,9->7,8,9,10（交換1次）循環(huán)次數(shù)：6次中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn交換次數(shù)：3次從運(yùn)行的表格來(lái)看,交換幾乎和冒泡ー樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡ー樣也是l/2*（n-l）*n,所以算法的復(fù)雜度仍然是0（n*n）。由于我們無(wú)法給出所有的情況,所以只能直接告訴大家他們?cè)诮粨Q上面也是ー樣的糟糕（在某些情況下稍好，在某些情況下稍差）。網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter（freeware）CodeHighlighter/.選擇法：現(xiàn)在我們終于可以看到ー點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能（某些情況下）這種方法類似我們?nèi)藶榈呐判蛄?xí)慣:從數(shù)據(jù)中選擇最小的同第一個(gè)值交換，在從省下的部分中選擇最小的與第二個(gè)交換,這樣往復(fù)下去。中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnttinclude<iostream.h>voidSelectSort（int*pData,intCount）intiTemp;intiPos;for(inti=0;i<Count-l;i){iTemp=pData[i];iPos=i;for(intj=i1;j<Count;j)iif(pData[j]<iTemp)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn{iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidmainO(intdata[]={10,9,8,7,6,5,4};中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnSelectSort(data,7);cout?data[i]?*coutくく"、n";)倒序(最糟情況)第一輪:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交換1次)第二輪:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交換1次)第一輪:7,8,9,10->(iTemp=9)7,8,9,第(交換0次)循環(huán)次數(shù):6次交換次數(shù):2次中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn其他：第一輪:8,10,7,9-XiTemp=8)8,10,7,9-XiTemp=7)8,10,7,9-XiTemp=7)7,10,8,9(交換1次)第二輪：7,10,8,9^(訂6(^=8)7,10,8,9^(述01^=8)7,8,10,9(交換1次)第一輪：7,8,10,9->(iTemp=9)7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：3次遺憾的是算法需要的循環(huán)次數(shù)依然是l/2*(n-l)*n。所以算法復(fù)雜度為0(n*n)。我們來(lái)看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換(只有一個(gè)最小值)。所以f(n)<=n所以我們有f(n)=0(n)。所以,在數(shù)據(jù)較亂的時(shí)候,可以減少ー定的交換次數(shù)。網(wǎng)友回復(fù):student,zjzk/course_ware/data_structure/web/main,htm網(wǎng)友回復(fù):C/Ccode中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/.插入法:插入法較為復(fù)雜,它的基本工作原理是抽出牌,在前面的牌中尋找相應(yīng)的位置插入,然后繼續(xù)下ー張^include<iostream.h>voidInsertSort(int*pData,intCount){intiTemp;intiPos;for(inti=l;i<Count;i)(中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdniTemp=pData[i];iPos=i-l;while((iPos>=0)&&(iTemp<pData[iPos]))(pData[iPos1]=pData[iPos];iPosーー;pData[iPos1]=iTemp;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnvoidmainO{intdata[]={10,9,8,7,6,5,4};InsertSort（data,7）;for（inti=0;i<7;i）cout?data[i]?**;cout?*\n*：）倒序（最糟情況）第一輪:10,9,8,7->9,10,8,7（交換1次）（循環(huán)1次）第二輪:9,10,8,7->8,9,10,7（交換1次）（循環(huán)2次）第一輪:8,9,10,7->7,8,9,10（交換1次）（循環(huán)3次）中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn循環(huán)次數(shù):6次交換次數(shù):3次其他：第一輪:8,10,7,9->8,10,7,9（交換0次）（循環(huán)1次）第二輪:8,10,7,9->7,8,10,9（交換1次）（循環(huán)2次）第一輪：7,8,10,9->7,8,9,10（交換1次）（循環(huán)1次）循環(huán)次數(shù)：4次交換次數(shù)：2次上面結(jié)尾的行為分析事實(shí)上造成了一種假象,讓我們認(rèn)為這種算法是簡(jiǎn)單算法中最好的,其實(shí)不是,因?yàn)槠溲h(huán)次數(shù)雖然并不固定,我們?nèi)钥梢允褂茅柗椒?。從上面的結(jié)果可以看出,循環(huán)的次數(shù)f(n)く=l/2*n*(nT)く=l/2*n*ru所以其復(fù)雜度仍為O(n*n)(這里說(shuō)明一下,其實(shí)如果不是為了展示這些簡(jiǎn)單排序的不同,交換次數(shù)仍然可以這樣推導(dǎo))?，F(xiàn)在看交換,從外觀上看,交換次數(shù)是。(n)(推導(dǎo)類似選擇法),但我們每次要進(jìn)行與內(nèi)層循環(huán)相同次數(shù)的‘二’操作。正常的一次交換我們需要三次‘二’而這里顯然多了一些,所以我們浪費(fèi)了時(shí)間。中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn最終,我個(gè)人認(rèn)為,在簡(jiǎn)單排序算法中,選擇法是最好的。網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/插入排序^include<iostream>中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdnusingnamespacestd;voidcoutstream(inta[],intn){for(inti=0;i!=n;i)coutくくa[i]くく”}voidinsertsort(inta[],intn){inttemp;for(inti=l;i<n;i)intj=i;temp=a[i];〃先把a(bǔ)[i]位置的數(shù)據(jù)存起來(lái)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnwhile(j>O&&temp<a[j-l])(a[j]=a[j-l];j一；}a[j]=temp;}}intmain()(中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdninta[5]={l,6,4,8,4);insertsort(a,5);〃插入排序coutstream(a,5);//return0;)網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodellighlighter(freeware)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnCodeHighlighter/二、高級(jí)排序算法:髙級(jí)排序算法中我們將只介紹這ーー種,同時(shí)也是目前我所知道(我看過(guò)的資料中)的最快的。它的工作看起來(lái)仍然象一個(gè)ニ叉樹。首先我們選擇ー個(gè)中間值middle程序中我們使用數(shù)組中間值,然后把比它小的放在左邊,大的放在右邊(具體的實(shí)現(xiàn)是從兩邊找,找到ー對(duì)后交換)。然后對(duì)兩邊分別使用這個(gè)過(guò)程(最容易的方法——遞歸)。1.快速排序:ftincludeくiostream.h>voidrun(int*pData,intleft,intright)(inti,j;intmiddle,iTemp;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdni=left;j=right;middle=pData[(leftright)/2];〃求中間值do{while((pData[i]<middle)&&(iくright))〃從左掃描大于中值的數(shù)i；while((pData[j]>middle)&&(j>left))〃從右掃描大于中值的數(shù)j-；if(i〈=j)〃找到了一對(duì)值{〃交換iTemp=pData[i];中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdnpData[i]=pData[j];pData[j]=iTemp;}while(i〈=j);〃如果兩邊掃描的下標(biāo)交錯(cuò),就停止(完成一次)〃當(dāng)左邊部分有值(leftくj),遞歸左半邊if(left<j)run(pData,left,j);〃當(dāng)右邊部分有值(right*),遞歸右半邊if(right>i)run(pData,i,right);中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn}voidQuicksort(int*pData,intCount)(run(pData,0,Count-1);}voidmain()(intdata口={10,9,8,7,6,5,4};Quicksort(data,7);for(inti=0;i<7;i)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdncout?data[i]?*cout?*\n*;)這里我沒有給出行為的分析,因?yàn)檫@個(gè)很簡(jiǎn)單,我們直接來(lái)分析算法:首先我們考慮最理想的情況.數(shù)組的大小是2的事,這樣分下去始終可以被2整除。假設(shè)為2的k次方,即k=log2(n)〇.每次我們選擇的值剛好是中間值,這樣，數(shù)組オ可以被等分。第一層遞歸，循環(huán)n次,第二層循環(huán)2*(n/2) 所以共有n2(n/2)4(n/4)...n*(n/n)=nnn...n=k*n=log2(n)*n所以算法復(fù)雜度為0(log2(n)*n)其他的情況只會(huì)比這種情況差,最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變成交換法(由于使用了遞歸，情況更糟)。但是你認(rèn)為這種情況發(fā)生的幾率有多大??呵呵，你完全不必?fù)?dān)心這個(gè)問(wèn)題。實(shí)踐證明,大多數(shù)的情況,快速排序總是最好的。如果你擔(dān)心這個(gè)問(wèn)題，你可以使用堆排序，這是ー種穩(wěn)定的。(log2(n)*n)算法,但是通常情況下速度要慢于快速排序(因?yàn)橐亟M堆)。中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdn網(wǎng)友回復(fù):幫UP呵呵泡沫排序還沒有聽說(shuō)過(guò)呀網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/三、其他排序.雙向冒泡:通常的冒泡是單向的,而這里是雙向的,也就是說(shuō)還要進(jìn)行反向的工作。代碼看起來(lái)復(fù)雜,仔細(xì)理一下就明白了,是ー個(gè)來(lái)回震蕩的方式。寫這段代碼的作者認(rèn)為這樣可以在冒泡的基礎(chǔ)上減少ー些交換(我不這么認(rèn)為,也許我錯(cuò)了)。中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn反正我認(rèn)為這是一段有趣的代碼,值得一看。ttinclude<iostream.h>voidBubble2Sort(int*pData,intCount){intiTemp;intleft=1;intright=Count-1;intt;do[〃正向的部分for(inti=right;i>=left;i—)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn{if(pData[i]<pData[i-1])(iTemp=pData[i];pData[i]=pData[i-l];pData[i-l]=iTemp;left=t1;〃反向的部分for(i=left;i<right1;i)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn!if(pData[i]<pData[i~l])(iTemp=pData[i];pData[i]=pData[i-l];pData[i-l]=iTemp;t=i;}}right=t-1;}while(left<=right);)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnvoidmain()intdata口={10,9,8,7,6,5,4};Bubble2Sort(data,7);for(inti=0;i<7;i)cout?data[i]?*coutくく"、n";)網(wǎng)友回復(fù):C/Ccode中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/快速排序ttinclude<iostream>usingnamespacestd;classQuicksort(public:voidquick_sort(int*x,intlow,inthigh)(中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnintpivotkey;if(low<high)pivotkey=partion(x,low,high);quick_sort(x,low,pivotkey-1);quick_sort(x,pivotkey1,high);}}intpartion(int*x,intlow,inthigh)iintpivotkey;pivotkey=x[low];while(low<high)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn(while(low<high&&x[high]>=pivotkey)一high;〃還有while循環(huán)只執(zhí)行這一句x[low]=x[high];while(low<high&&x[low]<=pivotkey)low;〃還有while循環(huán)只執(zhí)行這一句x[high]=x[low];}x[low]=pivotkey;returnlow;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdnintmainOintx[10]={52,49,80,36,14,58,61,97,23,65};Quicksortqs;qs.quick_sort(x,0,9);coutくく“排好序的數(shù)字序列為:"くくendl;for(inti=0;i<10;i)(printf("%d",x[i]);}return0;}中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/.SHELL排序這個(gè)排序非常復(fù)雜,看了程序就知道了。首先需要一個(gè)遞減的步長(zhǎng),這里我們使用的是9、5、3、1(最后的步長(zhǎng)必須是1)。工作原理是首先對(duì)相隔9T個(gè)元素的所有內(nèi)容排序,然后再使用同樣的方法對(duì)相隔5T個(gè)元素的排序以次類推。#include<iostream.h>中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnvoidShellSort(int*pData,intCount){intstep[4];step[0]=9;step[l]=5;step[2]=3;step[3]=1;intiTemp;intk,s,w;for(inti=0;i<4;i)(k=step[i];中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdns=-k;for(intj=k;j<Count;j)(iTemp=pData[j];w=j-k;〃求上step個(gè)元素的下標(biāo)if(s=0)(s=-k;pData[s]=iTemp;while((iTemp<pData[w])&&(w>=0)&&(wく二Count))中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn{pData[wk]=pData[w];w-k;pData[wk]=iTemp;voidmainOintdata[]={10,9,8,7,6,5,4,3,2,1,-10,-1};ShellSort(data,12);中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnfor(inti=0;i<12;i)coutくくdata[i]くく“"；coutくく、n;呵呵,程序看起來(lái)有些頭疼。不過(guò)也不是很難,把s==0的塊去掉就輕松多了,這里是避免使用〇步長(zhǎng)造成程序異常而寫的代碼。這個(gè)代碼我認(rèn)為很值得一看。這個(gè)算法的得名是因?yàn)槠浒l(fā)明者的名字D.L.SHELL。依照參考資料上的說(shuō)法:“由于復(fù)雜的數(shù)學(xué)原因避免使用2的冢次步長(zhǎng),它能降低算法效率?！绷硗馑惴ǖ膹?fù)雜度為n的1.2次暴。同樣因?yàn)榉浅?fù)雜并“超出木書討論范圍”的原因（我也不知道過(guò)程）,我們只有結(jié)果了網(wǎng)友回復(fù):冒泡排序性能優(yōu)化版C/Ccode中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/ttinclude<iostream>usingnamespacestd;voidmaopao(int*list,intn)!inti=n,j,temp;boolexchange;〃當(dāng)數(shù)據(jù)已經(jīng)排好時(shí),退出循環(huán)for(i=0;i<n;i)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn(exchange=false;for(j=0;j<n-i-l;j)(if(list[j]>list[j1])(temp=list[j];list[j]=list[j1];list[jl]=temp;exchange=true;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn)if(!exchange)(return;intmain()(inta[7]={32,43,22,52,2,10,30);maopao(a,7);for(inti=0;iく7;i)cout?a[i]?*中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnreturn0;)網(wǎng)友回復(fù):以上是我從網(wǎng)上摘下來(lái)的,請(qǐng)大家有什么好的基本算法拿出來(lái)研究一下啊,謝謝哦,記得要有代碼哦、網(wǎng)友回復(fù):LZ原來(lái)不是提問(wèn),是發(fā)帖,暈,那還給岀那么多分網(wǎng)友回復(fù):引用14樓anglecloudy的回復(fù):LZ原來(lái)不是提問(wèn),是發(fā)帖,暈,那還給出那么多分不是發(fā)帖了啊,而是來(lái)總結(jié)一下基本的算法思想~有利于學(xué)習(xí)~不光是排序的問(wèn)題啦,其它的解決特殊問(wèn)題的算法也可以show出來(lái)大家研究一下,學(xué)習(xí)無(wú)止境@!網(wǎng)友回復(fù):引用14樓anglecloudy的回復(fù):LZ原來(lái)不是提問(wèn),是發(fā)帖,暈,那還給出那么多分謝謝你的積極發(fā)言~中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn網(wǎng)友回復(fù):剛オ在CSDN的C語(yǔ)言板塊看到了有人說(shuō)Shell排序的問(wèn)題,所以ー起學(xué)習(xí)了一下，并進(jìn)行如下總結(jié)shell排序的思想是根據(jù)步長(zhǎng)由長(zhǎng)到短分組,進(jìn)行排序，直到步長(zhǎng)為1為止,屬于插入排序的ー種。下面用個(gè)例子更好的理解一下無(wú)序數(shù)列:32,43,56,99,34,8,54,76首先設(shè)定gap=n/2=4于是分組32,34排序32,3443,88,4356,5454,5699,7676,99數(shù)列變成32,8,54,76,34,43,56,99gap=gap/2=2于是分組32,54,34,56排序32,34,54,568,76,43,998,43,76,99于是數(shù)列變成32,8,34,43,54,76,56,99gap=gap/2=l于是分組32,8,34,43,54,76,56,99排序8,32,34,43,54,56,76,99gap=l結(jié)束 相應(yīng)的C語(yǔ)言代碼引用K&RC程序設(shè)計(jì)ー書中給出的代碼中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnvoidshellsort(intvロ,intn)Iintgap,i,j,temp;for(gap=n/2;gap>0;gap/=2)〃設(shè)定步長(zhǎng)for(i=gap;i<n;i)〃在元素間移動(dòng)為止for(j=i-gap;j>=O&&v[j]>v[jgap];j-=gap){〃比較相距gap的元素,逆序互換temp=v[j];v[j]=v[jgap];v[jgap]=temp;)}網(wǎng)友回復(fù):歸并blog,csdn/mifeixq/archive/2008/09/18/2946405.aspx網(wǎng)友回復(fù):幫頂網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnCodeHighlighter/〃帕斯卡恒等式為C(n,k)=C(n-l,k-1)C(n-1,k)longfun(longn,longr)if(r<0||n<0)(printf(*\nError.Exitド)；exit(1);}中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdnif(r>n)return0;if(r=l||rニニn-1)〃根據(jù)組合定義,我們有C(n,l)=C(n,n-l)=nreturnn;if(rニニ01Irニニn)〃根據(jù)組合定義,我們有C(n,0)=C(n,n)=lreturn1;returnfun(n-l,r)fun(nT,rT);〃帕斯卡組合公式}〃選擇法對(duì)數(shù)組排序的函數(shù)模板template<classT>voidselectsort(Tarr[],intsize)(Ttemp;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdninti,j;for(i=0;iくsizeT;i)for(j=i1;j<size;j)if(arr[i]>arr[j])[temp=arr[i];arr[i]=arr[j];arr[j]=temp;))〃冒泡法對(duì)數(shù)組排序的函數(shù)模板中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdntemplate<classT>voidbubblesort(T*d,intn)[inti,j;Tt;for(i=0;i<n-l;i)for(j=0;j<n-i-l;j)if(d[j]>d[j1])It=d[j];d[j]=d[j1];d[jl]=t;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn〃插入法對(duì)數(shù)組排序的函數(shù)模板template<classT>voidInsertSort(TA[],intn)(inti,j;Ttemp;for(i=1;i<n;i)itemp=A[i];for(j=i-l;j>=0&&temp<A[j];j—)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnA[jl]=A[j];A[j1]=temp;}}〃二分查找法的函數(shù)模板template<classT>intbinary_search(Tarray[],Tvalue,intsize)(inthigh=size-1,low=0,mid;while(lowく二high)mid=(highlow)/2;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnif(value<array[mid])high=mid-1;elseif(value>array[mid])low=mid1;elsereturnmid;}return-1;}將2~36進(jìn)制數(shù)與10進(jìn)制數(shù)相互轉(zhuǎn)換〃將2~36進(jìn)制數(shù)轉(zhuǎn)換成I0進(jìn)制數(shù)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnunsignedintOthToDec(char*oth,intbase)〃base為已知數(shù)的進(jìn)制(unsignedinti=0,dec=0;while(oth[i])(dec?二base;if(oth[i]>='0'&&oth[i]くエ’9')dec=oth[i]&15;//dec=oth[i]-48;elseif(oth[i]>=，A'&&oth[i]<='Z')dec=oth[i]-55;elseif(oth[i]>=,a*&&oth[i]<=,z)dec=oth[i]-87;i；中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn)returndec;}〃將10進(jìn)制(無(wú)符號(hào))轉(zhuǎn)2、36進(jìn)制數(shù)char*DecToOth(char*oth,unsignedintdec,intbase)//base為要轉(zhuǎn)換的數(shù)的進(jìn)制(charch,*left=oth,*right=oth,numロ=”0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ”;do{*right=num[dec塞e];right;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn}while(dec/=base);*right=，;right―;while(left<right)ch=*left;*left=*right;*right=ch;left;right—;}returnoth;)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn〃統(tǒng)計(jì)substr在str中的個(gè)數(shù)intfun(char*str,char*substr)iintn=0;char*q;q二substr;while(*str!=,\0*){if(*strニニ*substr)(str;substr;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnif(*substrニニ‘、〇')substr=q;else(str;substr二q;}}returnn;}中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/使用數(shù)組實(shí)現(xiàn)約瑟夫環(huán):#include<stdio.h>ttinclude<stdlib.h>main()(中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnintm,n,i=l,j,k=l,per,o;printf（"請(qǐng)輸入總共的人數(shù),記為n\ぺ）;scanf("%d",&n);intarray[n1];intorder[n1];printf(〃請(qǐng)輸入幾號(hào)出圈,記為m\n");scanf&m);printf("\n**************************************\n");for(;iくn;i)〃數(shù)組鏈表模擬array[i]=i1;array[n]=l;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnprintf(*%darray[n]);i=l;j=l;per=n;while(array[i]!=i){if(k==m){order[j]=i;j；array[per]=array[i];k=0;for(o=l;o<=j;o)printf(，z%d*”,order[〇]);}else{printf("%d”,array[i]);中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnper=i;i=array[i];k;))order[n]=i;printf("\n**************************************\n");for(i=l;i<=n;i)printf(*%d”,order[i]);system("pause");中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnreturn0;)網(wǎng)友回復(fù):好貼。關(guān)注中!！！網(wǎng)友回復(fù):真該好好頂一下網(wǎng)友回復(fù):引用23樓Gengoo的回復(fù):真該好好頂一下兄弟們不要光頂啊,把你們珍藏的經(jīng)典算法拿出來(lái)大家收集一下吧網(wǎng)友回復(fù):看了半天都是一堆排序網(wǎng)友回復(fù):引用25樓garybo的回復(fù):看了半天都是一堆排序那么兄弟啊,你有沒有好的代碼呢?共享一下~網(wǎng)友回復(fù):謝謝樓主的積極,學(xué)習(xí)就該這樣,收藏!網(wǎng)友回復(fù):C基本算法收集?算法還分語(yǔ)言嗎?網(wǎng)友回復(fù):引用28樓!ingzil225的回復(fù):C基本算法收集?算法還分語(yǔ)言嗎?中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn呵呵,不好意思,算法的實(shí)現(xiàn)應(yīng)該是有語(yǔ)言之分的吧~網(wǎng)友回復(fù):如果你給出其它語(yǔ)言的,我也不會(huì)排斥的,謝謝你的支持網(wǎng)友回復(fù):mark!網(wǎng)友回復(fù):up網(wǎng)友回復(fù):幫頂下網(wǎng)友回復(fù):up網(wǎng)友回復(fù):梯形插補(bǔ)f=a/f;f=f；f-=a/f;網(wǎng)友回復(fù):mark網(wǎng)友回復(fù):若是講搜集，給了代碼但沒給測(cè)試代碼的沒什么意義。網(wǎng)友回復(fù):怎么都是排序方面的算法啊有沒有關(guān)于搜索方面的算法啊比如爬蟲、網(wǎng)頁(yè)排序什么的網(wǎng)友回復(fù):ー堆好帖強(qiáng)烈支持!??！網(wǎng)友回復(fù):問(wèn):最后ー個(gè)算法放到vc中為什么編譯不能通過(guò)呢?網(wǎng)友回復(fù):很好中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn網(wǎng)友回復(fù):頂我頂,網(wǎng)友回復(fù):還好網(wǎng)友回復(fù):以前算法老師留了很多要求效率的算法作業(yè),都是在1分鐘具有處理百萬(wàn)數(shù)量集能算法,樓主使我想起了上學(xué)的日子啊!！網(wǎng)友回復(fù):來(lái)冒個(gè)泡網(wǎng)友回復(fù):收藏網(wǎng)友回復(fù):標(biāo)記網(wǎng)友回復(fù):51自學(xué)網(wǎng)ー專業(yè)培訓(xùn)老師錄制的視頻教程,讓學(xué)習(xí)變得很輕松網(wǎng)友回復(fù):爬蟲網(wǎng)友回復(fù):做個(gè)記號(hào),將來(lái)也許有用的到的時(shí)候.網(wǎng)友回復(fù):記號(hào)網(wǎng)友回復(fù):好頂頂網(wǎng)友回復(fù):0K網(wǎng)友回復(fù):做個(gè)模板嘛網(wǎng)友回復(fù):樓主很好網(wǎng)友回復(fù):謝謝,收藏了!網(wǎng)友回復(fù):頂頂更健康網(wǎng)友回復(fù):不錯(cuò),mark"網(wǎng)友回復(fù):好帖啊嚴(yán)重關(guān)注中啊期待更多高手們的出現(xiàn)啊網(wǎng)友回復(fù):收藏網(wǎng)友回復(fù):該回復(fù)于2008-10-0217:14:08被版主刪除網(wǎng)友回復(fù):學(xué)習(xí)了網(wǎng)友回復(fù):好東西,mark/中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn網(wǎng)友回復(fù):引用37樓iambic的回復(fù):若是講搜集,給了代碼但沒給測(cè)試代碼的沒什么意義。謝謝你,你的講法非常好，希望你能給出ー些示例網(wǎng)友回復(fù):先MARK了網(wǎng)友回復(fù):找ー本書就行了.干嘛說(shuō)那么多啊.你去下載里面找了有不少的.網(wǎng)友回復(fù):集思廣益也不是件壞事啊?網(wǎng)友回復(fù):亦即所謂的選擇法吧!網(wǎng)友回復(fù):希望大家看清楚意思再回帖吧，我想發(fā)帖的主要意思是求一些基本的算法以及實(shí)現(xiàn)的源代碼?網(wǎng)友回復(fù):謝謝LZ向大伙好好學(xué)習(xí)。。。網(wǎng)友回復(fù):學(xué)習(xí)了……網(wǎng)友回復(fù):基數(shù)排序。和把一堆亂撲克搞有序就是這么干的。網(wǎng)友回復(fù):好貼網(wǎng)友回復(fù):不錯(cuò),謝謝LZ網(wǎng)友回復(fù):這么多算法,收藏了網(wǎng)友回復(fù):mark、!'網(wǎng)友回復(fù):謝謝樓主分享網(wǎng)友回復(fù):LZSS算法,LZ77的加強(qiáng)版本,高手應(yīng)該都知道的。

中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdn#include<stdio.h>ttinclude<stdlib.h>ttinclude<string.h>ttinclude<ctype.h>ttdefineN4096/*sizeofringbuffer*/ttdefineF18/*upperlimitformatch_length*/ttdefineTHRESHOLD2/*encodestringintopositionandlengththanthis*/ifmatch_lengthisgreaterthanthis*/ttdefineNILN/*indexforrootofbinarysearchtrees*/ttdefineNILN/*indexforrootofbinarysearchtrees*/unsignedlongintcounter*/counter*/textsize=0,/*textsizecounter*/counter*/codesize=0,/*codesizeprintcount=0;/*counterforreportingprogresseveryIKbytes*/printcount=0;/*counterunsignedchar中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdntext_buf[NF-1];/*ringbufferofsizeN,withextraF_1bytestofacilitatestringcomparison*/intmatch_position,match_length,/*oflongestmatch.ThesearesetbytheInsertNodeOprocedure.*/Ison[N1],rson[N257],dad[N1];/*left&rightchildren&parents-Theseconstitutebinarysearchtrees.*/FILE*infile,*outfile;/*input&outputfiles*/網(wǎng)友回復(fù):voidInitTree(void)/*initializetrees*/{inti;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn/*Fori=0toN-1,rson[i]andlson[i]willbetherightandleftchildrenofnodei.Thesenodesneednotbeinitialized.Also,dad[i]istheparentofnodei.TheseareinitializedtoNIL(=N),whichstandsfor'notused.,Fori=0to255,rson[Ni1]istherootofthetreeforstringsthatbeginwithcharacteri.TheseareinitializedtoNIL.Notethereare256trees.*/for(i=N1;i<=N256;i)rson[i]=NIL;for(i=0;i<N;i)dad[i]=NIL;}voidInsertNode(intr)/*InsertsstringoflengthF,text_buf[r..rF-l],intooneofthe中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdntrees(text_buf[r]'thtree)andreturnsthelongest-matchpositionandlengthviatheglobalvariablesmatch_positionandmatch_length.Ifmatch_length=F,thenremovestheoldnodeinfavorofthenewone,becausetheoldonewillbedeletedsooner.Noterplaysdoublerole,astreenodeandpositioninbuffer.*/inti,p,cmp;unsignedchar*key;cmp=1;key=&text_buf[r];p=N1key[0];rson[r]=lson[r]=NIL;match_length=0;for(;;){if(cmp>=0){中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnif(rson[p]!=NIL)p=rson[p];else{rson[p]=r;dad[r]=p;return;}}else{if(lson[p]!=NIL)p=lson[p];else{lson[p]=r;dad[r]=p;return;}}for(i=1;i<F;i)if((cmp=key[i]-text_buf[pi])!=0)break;if(i>matchlength){match_position=p;if((match_length=i)>=F)break;)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn)dad[r]=dad[p];lson[r]=lson[p];rson[r]=rson[p];dad[Ison[p]]=r;dad[rson[p]]=r;if(rson[dad[p]]==p)rson[dad[p]]=r;else1son[dad[p]]=r;dad[p]=NIL;/*removep*/}voidDeleteNode(intp)/*deletesnodepfromtree*/(intq;if(dad[p]==NIL)return;/*notintree*/中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnif(rsonLp」==NIL)q=lson[p];elseif(lson[p]==NIL)q=rson[p];else{q=lson[p];if(rson[q]!=NIL){do{q=rson[q];}while(rson[q]!=NIL);rson[dad[q]]=lson[q];dad[Ison[q]]=dad[q];lson[q]=lson[p];dad[lson[p]]=q;)rson[q]=rson[p];dad[rson[p]]=q;}dad[q]=dad[p];if(rson[dad[p]]==p)rson[dad[p]]=q;elseIson[dad[p]]=q;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdndad[p]=NIL;voidEncode(void)(inti,c,len,r,s,last_match_length,code_buf_ptr;unsignedcharcode_buf[17],mask;InitTree();/*initializetrees*/code_buf[0]=0;/*code_buf[1..16]saveseightunitsofcode,andcode_buf[0]worksaseightflags,Trepresentingthattheunitisanunencodedletter(1byte),“〇"aposition-and-1engthpair(2bytes).Thus,eightunitsrequireatmost16bytesofcode.*/中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdncode_buf_ptr=mask=1;s=0;r=N-F;for(i=s;i<r;i)textbuf[i]='';/*Clearthebufferwithanycharacterthatwillappearoften.*/for(len=0;len<F&&(c=getc(infile))!=EOF;len)text_buf[rlen]=c;/*ReadFbytesintothelastFbytesofthebuffer*/if((textsize=len)==0)return;/*textofsizezero*/for(i=1;i<=F;i)InsertNode(r-i);/*InserttheFstrings,eachofwhichbeginswithoneormore'space'characters.Notetheorderinwhichthesestringsareinserted.Thisway,degeneratetreeswillbelesslikelytooccur.*/中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnInsertNode(r);/*Finally,insertthewholestringjustread.Theglobalvariablesmatch_lengthandmatch_positionareset.*/do{if(match_length>len)match_length=len;/*match_lengthmaybespuriouslylongneartheendoftext.*/if(match.length<=THRESHOLD){match_length=1;/*Notlongenoughmatch.Sendonebyte.*/code_buf[0]|=mask;/*'sendonebyte'flag*/codebuf[code_buf_ptr]=text_buf[r];/*Senduncoded.*/}else{code_buf[code_buf_ptr]=(unsignedchar)match_position;code_buf[code_buf_ptr]=(unsignedchar)(((matchposition?4)&OxfO)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnI(match_length-(THRESHOLD1)));/*Sendpositionandlengthpair.Notematch_length>THRESHOLD.*/}if((mask<<=1)=0){/*Shiftmaskleftonebit.*/for(i=0;i<codebufptr;i)/*Sendatmost8unitsof*/putc(code_buf[i],outfile);/*codetogether*/codesize=code_buf_ptr;code_buf[0]=0;code_buf_ptr=mask=1;lastmatchlength=matchlength;for(i=0;i<last_match_length&&(c=getc(infile))!=EOF;i){中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnDeleteNode(s);/*Deleteoldstringsand*/text_buf[s]=c;/*readnewbytes*/if(s<F-1)text_buf[sN]=c;/*Ifthepositionisneartheendofbuffer,extendthebuffertomakestringcomparisoneasier.*/s=(s1)&(N-1);r=(r1)&(N-1);/*Sincethisisaringbuffer,incrementthepositionmoduloN.*/InsertNode(r);/*Registerthestringintextbuf[r..rF-l]*/}if((textsize=i)>printcount){printflld\r,textsize);printcount=1024;/*Reportsprogresseachtimethetextsizeexceeds中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnmultiplesof1024.*/while(i<last_match_length){/*Aftertheendoftext,*/DeleteNode(s);/*noneedtoread,but*/s=(s1)&(N-1);r=(r1)&(N-1);if(—len)InsertNode(r);/*buffermaynotbeempty.*/}}while(len>0);/*untillengthofstringtobeprocessediszero*/if(code_buf_ptr>1){/*Sendremainingcode.*/for(i=0;i<code_buf_ptr;i)putc(code_buf[i],outfile);codesize=code_buf_ptr;}中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnprintflIn:%ldbytes\n〃,textsize);/*Encodingisdone.*/printf(z，0ut:%ldbytes'n”,codesize);printf("Out/In:%.3f\n〃,(double)codesize/textsize);}voidDecode(void)/*JustthereverseofEncode().*/(inti,j,k,r,c;unsignedintflags;for(i=0;i<N-F;i)text_buf[i]二''；r=N-F;flags=0;for(;;){中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdnif(((flags?=1)&256)==0){if((c=getc(infile))==EOF)break;flags=cOxffOO;/*useshigherbytecleverly*/}/*tocounteight*/if(flags&1){if((c=getc(infile))==EOF)break;putc(c,outfile);text_buf[r]=c;r&二(N-1);}else{if((i=getc(infile))==EOF)break;if((j=getc(infile))=EOF)break;i|=((j&OxfO)<<4);j=(j&OxOf)THRESHOLD;for(k=0;k<=j;k){c=textbuf[(ik)&(N-1)];中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnputc(c,outfile);text_buf[r]=c;r&=(N-1);intmain(intargc,char*argv[])(char*s;if(argc!=4){printflIzssefilelfile2'encodesfilelintofile2.ゝn”Izssdfile2filel'decodesfile2intofilel.\n/z);中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnreturnEXIT_FAILURE;)if((s=argv[l],s[l]I'strpbrk(s,"DEde")==NULL)II(s=argv[2],(infile=fopen(s,"rb"))==NULL)II(s=argv[3],(outfile=fopen(s,"wb"))==NULL)){printf("???%s\n”,s);returnEXIT_FAILURE;)if(toupper(*argv[1])=='E')Encode();elseDecode();fclose(infile);fclose(outfile);returnEXIT_SUCCESS;網(wǎng)友回復(fù):幫頂!!留著以后用網(wǎng)友回復(fù):mark網(wǎng)友回復(fù):mark網(wǎng)友回復(fù):收你們先,改天補(bǔ)回網(wǎng)友回復(fù):其實(shí)我更喜歡C#的,C不怎以懂,所以也沒有認(rèn)真看,希望以后會(huì)對(duì)我有所幫助!謝謝[size=14px][/size]中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn網(wǎng)友回復(fù):繼續(xù)收集,請(qǐng)大家積極參與網(wǎng)友回復(fù):mark需要收藏我是低手學(xué)習(xí)。。只學(xué)過(guò)基礎(chǔ)算法高等的算法就沒學(xué)過(guò)了網(wǎng)友回復(fù):謝謝樓主的分享網(wǎng)友回復(fù)：topic,csdn/t/20030902/12/2214508.html網(wǎng)友回復(fù):mark~網(wǎng)友回復(fù):topic,csdn/t/20050223/21/3801741.html網(wǎng)友回復(fù):C/CcodeCodehighlightingproducedbyActiproCodeHighlighter(freeware)CodeHighlighter/輸入正整數(shù)N,然后是N*N個(gè)正整數(shù),表示邊權(quán)鄰接矩陣。輸出求解過(guò)程。中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn/*Problem:WeightedBipartiteMatchingAlgorithm:HungarianAlgorithmReference:DouglasB.West,IntroductiontoAuthor:PCDate:2005.2.23*/^include<iostream.h>#include<iomanip.h>ttinclude<fstream.h>中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟GraphTheory,125-129lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdn#include<memory.h>ifstreamfin("input.txt");#definecinfinconstintmax=50;boolT[max],R[max],visited[max];intU[max],V[max],gt[max][max],x[max],y[max];intN;voidoutput()(中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟!isdninti,j;for(i=0;i<N;i)for(j=0;j<N;j)(cout?setw(2)?gt[i][j]?，';}if(R[i])coutくくsetw(2)くぐR‘くぐ'；cout?endl;}for(i=0;i<N;i)if(T[i])cout?setw(2)?,T'?'';elsecout?setw(2)?''?'中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟,;lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdncout?endl;intpath(intu)intv;for(v=0;v<N;v)(if(gt[u][v]==0&&!visited[v])(visited[v]=l;if(y[v]<0Ipath(y[v]))中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn{x[u]=v;y[v]=u;R[u]=l;T[v]=0;return1;}else{T[v]=l;R[y[v]]=0；return0;)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnfor(;cin?N;){inti,j,ans,sigma,step=O;for(i=0;i<N;i)(U[i]=V[i]=0;for(j=0;j<N;j)(cin?gt[i][j];if(U[i]<gt[i][j])U[i]=gt[i][j];)中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn)for(i=0;i<N;i){for(j=0;j<N;j)[gt[i][j]=U[i]-gt[i][j]:))//////////////////////////////////////////////////////////for(;;)(ans=0;中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnsigma=O;memset(x,-1,sizeof(x));memset(y,-1,sizeof(y));memset(R,0,sizeof(R));memset(T,0,sizeof(T));for(i=0;i<N;i)iif(x[i]<0)!memset(visited,0,sizeof(visited));ans=path(i);}中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdn中國(guó)Unix/Linux軟件開發(fā)聯(lián)盟lisdnfor(j=