c語言算法分析 計(jì)算機(jī)

1.冒泡法：

這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭?

#include<iostream.h>

voidBubbleSort(int*pData,intCount)

I

intiTemp;

for(inti=l;i<Count;i)

(

for(intj=Count-l;j>=i;j一)

!

if(pData[j]<pData[j-1])

(

iTemp=pData[j-1];

pData[j-1]=pDatatj];

pData[j]=iTemp;

I

}

}

voidmain（）

{

intdata[]={10,9,8,7,6,5,4）;

BubbleSort（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次

其他：

第一輪：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-U寫成公式就是l/2*(n-l)*n。現(xiàn)在注意，我們給出0方法的定義：

若存在-常量K和起點(diǎn)nO,使當(dāng)n>=nO時，有f(n)〈=K*g(n),則f(n)=0(g(n))。(呵

呵，不要說沒學(xué)好數(shù)學(xué)呀，對于編程數(shù)學(xué)是非常重要的?。?！)

現(xiàn)在我們來看1/2*(n-l)*n,當(dāng)K=l/2,nO=l,g(n)=n*n時，1/2*(n-1)*n<-l/2*n*n=K*g(n)?

所以f(n)=0(g(n))=0(n*n)?所以我們程序循環(huán)的復(fù)雜度為0(n*n)。

再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實(shí)交換

本身同數(shù)據(jù)源的有序程度有極大的關(guān)系，當(dāng)數(shù)據(jù)處于倒序的情況時，交換次數(shù)同循環(huán)一樣(每

次循環(huán)判斷都會交換)，復(fù)雜度為0(n*n)。當(dāng)數(shù)據(jù)為正序，將不會有交換。復(fù)雜度為0(0)。

亂序時處于中間狀態(tài)。正是由于這樣的原因，我們通常都是通過循環(huán)次數(shù)來對比算法。

網(wǎng)友回復(fù):

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

2.交換法:

交換法的程序最清晰簡單，每次用當(dāng)前的元素一一的同其后的元素比較并交換。

#include<iostream.h>

voidExchangeSort(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;

)

!

voidmain()

intdata[]={10,9,8,7,6,5,4};

ExchangeSort(data,7);

for(inti=0;i<7;i)

cout?data[i]?/z"\

cout?z/\n//;

}

倒序（最糟情況）

第一輪: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次

交換次數(shù)：3次

從運(yùn)行的表格來看，交換幾乎和冒泡一樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡一樣也是

l/2*（n-l）*n,所以算法的復(fù)雜度仍然是0（n*n）。由于我們無法給出所有的情況，所以只能

直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。

網(wǎng)友回復(fù):

C/Ccode

CodehighlightingproducedbyActiproCodellighlighter(freeware)

http:〃www.CodeHighlighter.com/

3.選擇法：

現(xiàn)在我們終于可以看到一點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能(某些情況下)這種方

法類似我們?nèi)藶榈呐判蛄?xí)慣：從數(shù)據(jù)中選擇最小的同第一個值交換，在從省下的部分中選擇

最小的與第二個交換，這樣往復(fù)下去。

#include<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)

if(pData[j]<iTemp)

iTemp=pData[j];

iPos=j;

)

pData[iPos]=pData[i];

pData[i]=iTemp;

)

)

voidmain()

intdata[]={10,9,8,7,6,5,4};

SelectSort(data,7);

for(inti=0;i<7;i)

cout?data[i]?/z"\

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,10(交換0次)

循環(huán)次數(shù)：6次

交換次數(shù)：2次

其他：

第一輪：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交換1

次)

第二輪:7,二,8,9->(仃60^=8)7,10,8,9-〉(仃611^=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)。

我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換(只有一個最小值)。所以f(n)<=n

所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時候，可以減少一定的交換次數(shù)。

網(wǎng)友回復(fù)：http:〃student,zjzk.cn/course_ware/data_structure/web/main.htm

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodellighlighter(freeware)

http://w\nv.CodeHighlighter.com/

4.插入法：

插入法較為復(fù)雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應(yīng)的位置插入，然后繼

續(xù)下一張

#include<iostream.h>

voidInsertSort(int*pData,intCount)

intiTemp;

intiPos;

for(inti=l;i<Count;i)

(

iTemp=pData[i];

iPos=i-1;

while((iPos>=0)&&(iTemp<pData[iPos]))

(

pData[iPos1]=pData[iPos];

iPos一；

)

pData[iPos1]=iTemp;

}

}

voidmain()

I

intdata[]={10,9,8,7,6,5,4};

InsertSort(data,7);

for(inti=0;i<7;i)

cout?data[i]?/z"\

cout?z/\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次）

循環(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)為這種算法是簡單算法中最好的，其

實(shí)不是，因?yàn)槠溲h(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂?方法。從上面的結(jié)果可以看出，

循環(huán)的次數(shù)f（n）〈=l/2*n*（n-l）〈=l/2*n*n。所以其復(fù)雜度仍為0（n*n）（這里說明一下，其實(shí)

如果不是為了展示這些簡單排序的不同，交換次數(shù)仍然可以這樣推導(dǎo)）?，F(xiàn)在看交換，從外觀

上看，交換次數(shù)是0（n）（推導(dǎo)類似選擇法），但我們每次要進(jìn)行與內(nèi)層循環(huán)相同次數(shù)的'='

操作。正常的一次交換我們需要三次'=’而這里顯然多了一些，所以我們浪費(fèi)了時間。

最終，我個人認(rèn)為，在簡單排序算法中，選擇法是最好的。

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

插入排序

#include<iostream>

usingnamespacestd;

voidcoutstream(inta[],intn){

for(inti=0;i!=n;i)

cout<<a[i]?z，，z;

；

voidinsertsort(inta[],intn){

inttemp;

for(inti=l;i<n;i)

intj=i;

temp=a[i];〃先把a(bǔ)[i]位置的數(shù)據(jù)存起來

while(j>O&&temp<a[j-l])

(

a[j]=a[j-l];

j—；

I

a[j]=temp;

intmainO

I

inta[5]={l,6,4,8,4);

insertsort(a,5);〃插入排序

coutstream(a,5);//

return0;

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter（freeware）

http://www.CodeHighlighter.com/

二、高級排序算法：

高級排序算法中我們將只介紹這?種，同時也是目前我所知道（我看過的資料中）的最快的。

它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數(shù)組中

間值，然后把比它小的放在左邊，大的放在右邊（具體的實(shí)現(xiàn)是從兩邊找，找到一對后交換）。

然后對兩邊分別使用這個過程（最容易的方法——遞歸）。

1.快速排序：

#include<iostream.h>

voidrun（int*pData,intleft,intright）

（

inti,j;

intmiddle,iTemp;

i=left;

j=right;

middle=pData[(leftright)/2];〃求中間值

do{

whi1e((pData[i]<midd1e)&&(i<right))〃從左掃描大于中值的數(shù)

i；

while((pData[j]>middle)&&(j>left))〃從右掃描大于中值的數(shù)

J—；

〃找到了一對值

(

〃交換

iTemp=pData[i];

pData[i]=pData[j];

pData[j]=iTemp;

i；

J—；

!

}while(i?j);〃如果兩邊掃描的下標(biāo)交錯，就停止(完成一次)

〃當(dāng)左邊部分有值(left。)，遞歸左半邊

if(left<j)

run(pData,left,j);

〃當(dāng)右邊部分有值(right>i),遞歸右半邊

if(right>i)

run(pData,i,right);

)

voidQuicksort(int*pData,intCount)

I

run(pData,0,Count-1);

I

voidmain()

(

intdata[]={10,9,8,7,6,5,4);

Quicksort(data,7);

for(inti=0;i<7;i)

cout<<data[i]?/z〃；

cout<X〃\n〃;

}

這里我沒有給出行為的分析，因?yàn)檫@個很簡單，我們直接來分析算法：首先我們考慮最理想

的情況

1.數(shù)組的大小是2的幕，這樣分下去始終可以被2整除。假設(shè)為2的k次方，即k-log2(n)o

2.每次我們選擇的值剛好是中間值，這樣，數(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)

其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那

么他將變成交換法(由于使用了遞歸，情況更糟)。但是你認(rèn)為這種情況發(fā)生的幾率有多大？？

呵呵，你完全不必?fù)?dān)心這個問題。實(shí)踐證明，大多數(shù)的情況，快速排序總是最好的。

如果你擔(dān)心這個問題，你可以使用堆排序，這是一種穩(wěn)定的0(log2(n)*n)算法，但是通常情

況下速度要慢于快速排序(因?yàn)橐亟M堆)。

網(wǎng)友回復(fù):幫UP呵呵泡沫排序還沒有聽說過呀

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

三、其他排序

1.雙向冒泡：

通常的冒泡是單向的，而這里是雙向的，也就是說還要進(jìn)行反向的工作。

代碼看起來復(fù)雜，仔細(xì)理一下就明白了，是一個來回震蕩的方式。

寫這段代碼的作者認(rèn)為這樣可以在冒泡的基礎(chǔ)上減少一些交換(我不這么認(rèn)為，也許我錯了)。

反正我認(rèn)為這是一段有趣的代碼，值得一看。

#include<iostream.h>

voidBubble2Sort(int*pData,intCount)

intiTemp;

intleft=1;

intright=Count-1;

intt;

do

(

〃正向的部分

for(inti=right;i>=left;i--)

I

if(pData[i]<pData[i-1])

(

iTemp=pData[i];

pData[i]=pData[i-l];

pData[i-1]=iTemp;

t=i;

)

I

left=t1;

〃反向的部分

for(i=left;Krightl;i)

if(pData[i]<pData[i-1])

iTemp=pData[i];

pData[i]=pData[i-l];

pData[i-l]=iTemp;

t=i;

}

)

right=t-1;

}while(left<=right);

；

voidmain()

I

intdata[]={10,9,8,7,6,5,4);

Bubble2Sort(data,7);

for(inti=0;i<7;i)

cout<<data[i]?，z，z;

cout〈〈〃\n〃；

I

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http:〃www.CodeHighlighter.com/

快速排序

#include<iostream>

usingnamespacestd;

classQuicksort

I

public:

voidquick_sort(int*x,intlow,inthigh)

(

intpivotkey;

if(low<high)

I

pivotkey=partion(x,low,high);

quick_sort(x,low,pivotkey-1);

quick_sort(x,pivotkey1,high);

I

)

intpartion(int*x,intlow,inthigh)

intpivotkey;

pivotkey=x[low];

while(low<high)

I

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]；

I

x[low]=pivotkey;

returnlow;

)

}；

intmainO

I

intx[10]={52,49,80,36,14,58,61,97,23,65);

Quicksortqs;

qs.quick_sort(x,0,9);

cout?”排好序的數(shù)字序列為J〃《endl;

for(inti=0;i<10;i)

printf(z，%d”,x[i]);

)

return0;

}

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

2.SHELL排序

這個排序非常復(fù)雜，看了程序就知道了。

首先需要一個遞減的步長，這里我們使用的是9、5、3、1(最后的步長必須是1)。

工作原理是首先對相隔9-1個元素的所有內(nèi)容排序，然后再使用同樣的方法對相隔5T個元

素的排序以次類推。

#include<iostream.h>

voidShellSort(int*pData,intCount)

intstep[4];

step[O]=9;

step[l]=5;

step[2]=3;

step[3]=1;

intiTemp;

intk,s,w;

for(inti=0;i<4;i)

{

k=step[i];

s=-k;

for(intj=k;j<Count;j)

{

iTemp=pData[j];

w=j-k;〃求上step個元素的下標(biāo)

if(s==0)

(

s=-k;

s;

pData[s]=iTemp;

)

while((iTemp<pData[w])&&(w>=0)&&(w<=Count))

pData[wk]=pData[w];

w=w-k;

)

pData[wk]=iTemp;

)

)

)

voidmain()

(

intdata口={10,9,8,7,6,5,4,3,2,1,-10,-1);

ShellSort(data,12);

for(inti=0;i<12;i)

cout?data[i]?z/"\

cout?，，\n，/;

)

呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使

用0步長造成程序異常而寫的代碼。這個代碼我認(rèn)為很值得看。這個算法的得名是因?yàn)槠?/p>

發(fā)明者的名字D.L.SHELL。依照參考資料上的說法：“由于復(fù)雜的數(shù)學(xué)原因避免使用2的幕次

步長，它能降低算法效率?！绷硗馑惴ǖ膹?fù)雜度為n的1.2次辱。同樣因?yàn)榉浅?fù)雜并“超出

本書討論范圍”的原因(我也不知道過程)，我們只有結(jié)果了

網(wǎng)友回復(fù)：冒泡排序性能優(yōu)化版

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http:〃www.CodeHighlighter.com/

#include<iostream>

usingnamespacestd;

voidmaopao(int*list,intn)

(

inti=n,j,temp;

boolexchange;〃當(dāng)數(shù)據(jù)」經(jīng)排好時，退出循環(huán)

for(i=0;i<n;i)

exchange=false;

for(j=0;j<n-i-l;j)

if(list[j]>list[j1])

temp=list[j];

list[j]=list[j1];

list[j1]=temp;

exchange=true;

)

}

if(!exchange)

(

return;

}

}

!

intmain()

{

inta[7]={32,43,22,52,2,10,30);

maopao(a,7);

for(inti=0;i<7;i)

return0;

)

網(wǎng)友回復(fù)：以上是我從網(wǎng)上摘下來的，請大家有什么好的基本算法拿出來研究一下啊，謝謝哦,

記得要有代碼哦?

網(wǎng)友回復(fù):LZ原來不是提問，是發(fā)帖，暈，那還給出那么多分

網(wǎng)友回復(fù):引用14樓anglecloudy的回復(fù)：

LZ原來不是提問，是發(fā)帖，暈，那還給出那么多分

不是發(fā)帖了啊，而是來總結(jié)一下基本的算法思想?有利于學(xué)習(xí)?不光是排序的問題啦，其它

的

解決特殊問題的算法也可以show出來大家研究一下，學(xué)習(xí)無止境@!

網(wǎng)友回復(fù)：引用14樓anglecloudy的回復(fù)：

LZ原來不是提問，是發(fā)帖，暈，那還給出那么多分

謝謝你的積極發(fā)言?

網(wǎng)友回復(fù):剛才在CSDN的C語言板塊看到了有人說Shell排序的問題，所以一起學(xué)習(xí)了一下，

并進(jìn)行如下總結(jié)

shell排序的思想是根據(jù)步長由長到短分組，進(jìn)行排序，直到步長為1為止，屬于插入排序

的一種。下面用個例子更好的理解一下

無序數(shù)列：32,43,56,99,34,8,54,76

1.首先設(shè)定gap=n/2=4于是分組

32,34排序32,34

43,88,43

56,5454,56

99,7676,99

數(shù)列變成32,8,54,76,34,43,56,99

2.gap=gap/2=2于是分組

32,54,34,56排序32,34,54,56

8,76,43,998,43,76,99

于是數(shù)列變成32,8,34,43,54,76,56,99

3.gap=gap/2=l于是分組

32,8,34,43,54,76,56,99排序

8,32,34,43,54,56,76,99

gap=l結(jié)束...

相應(yīng)的C語言代碼引用K&RC程序設(shè)計(jì)一書中給出的代碼

voidshellsort(intv[],intn)

(

intgap,i,j,temp;

for(gap=n/2;gap>0;gap/=2)〃設(shè)定步長

for(i=gap;i<n;i)〃在元素間移動為止

for(j=i-gap;j>=0&&v[j]>v[jgap];j-=gap){〃比較相距gap的元素，逆序互換

temp=v[j];

v[j]=v[jgap];

v[jgap]=temp;

)

}

網(wǎng)友回復(fù):歸并

http://blog.csdn.net/mifeixq/archive/2008/09/18/2946405.aspx

網(wǎng)友回復(fù):幫頂

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

//帕斯卡恒等式為C(n,k)=C(nT,k-l)C(n-l,k)

longfun(longn,longr)

if(r<0|n<0)

printf(z?\nError.Exit!");

exit(1);

I

if(r>n)return0;

if(r=l||r二二nT)〃根據(jù)組合定義，我們有C(n,l)=C(n,nT)二n

returnn;

if(r=0|r==n)〃根據(jù)組合定義,我們有C(n,0)=C(n,n)=l

return1;

returnfun(n-l,r)fun(nT,rT);〃帕斯卡組合公式

)

〃選擇法對數(shù)組排序的函數(shù)模板

template<classT>

voidselectsort(Tarr[],intsize)

(

Ttemp;

inti,j;

for(i=0;i<size-l;i)

for(j=i1;j<size;j)

if(arr[i]>arr[j])

temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

〃冒泡法對數(shù)組排序的函數(shù)模板

template<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])

(

t=d[j];

d[j]=d[j1L

d[jl]=t;

}

}

〃插入法對數(shù)組排序的函數(shù)模板

template<classT>

voidInsertSort(TA口，intn)

I

inti,j;

Ttemp;

for(i=1;i<n;i)

(

temp=A[i];

for(j=i-l;j>=0&&temp<A[j];j—)

A[jl]=A[j];

A[j1]=temp;

}

!

〃二分查找法的函數(shù)模板

template<classT>

intbinarysearch(Tarray[],Tvalue,intsize)

I

inthigh=size-1,low=0,mid;

while(low〈二high)

mid=(highlow)/2;

if(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)換成10進(jìn)制數(shù)

unsignedintOthToDec(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；

)

returndec;

I

〃將10進(jìn)制(無符號)轉(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口二〃0123456789ABCDEFGHIJKLMN0PQRSTUVWXYZ〃；

do

(

*right=num[dec篡e];

right;

}while(dec/=base);

"right=''0';

right一一；

while(left<right)

ch=*left;

*left=*right;

*right=ch;

left;right―;

)

returnoth;

I

〃統(tǒng)計(jì)substr在str中的個數(shù)

intfun(char*str,char*substr)

{

intn=0;

char*q;

q二substr;

while(*str!=\0J)

{

if(*str=二*substr)

|

str;

substr;

if(*substr==，\0')

substr二q;

else

(

str;substr=q;

)

)

returnn;

1

網(wǎng)友回復(fù)：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http:〃www.CodeHighlighter.com/

使用數(shù)組實(shí)現(xiàn)約瑟夫環(huán)：

#include<stdio.h>

#include<stdlib.h>

main()

intm,n,i=l,j,k=l,per,o;

printf(“請輸入總共的人數(shù)，記為n\n");

scanf("%d〃，&n);

intarray[n1];

intorder[n1];

printf(〃請輸入幾號出圈，記為m\n〃)；

scant*("%d",&m);

printf(〃\n**************************************\n〃);

for(;i<n;i)〃數(shù)組鏈表模擬

array[i]=i1;

array[n]=l;

printf(，z%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*z，,order[o]);

)

else{printf(z，%d〃，array[i]);

per=i;

i=array[i];

order[n]=i;

printf('\n**************************************\n〃);

for(i=l;i<=n;i)

printf(，z%dorder[i]);

system("pause");

return0;

)

網(wǎng)友回復(fù):好貼。關(guān)注中?。?！

網(wǎng)友回復(fù):真該好好頂一下

網(wǎng)友回復(fù)：引用23樓Gengoo的回復(fù)：

真該好好頂一下

兄弟們不要光頂啊，把你們珍藏的經(jīng)典算法拿出來大家收集一下吧

網(wǎng)友回復(fù):看了半天都是一堆排序

網(wǎng)友回復(fù)：引用25樓garybo的回復(fù)：

看了半天都是一堆排序

那么兄弟啊，你有沒有好的代碼呢？共享?下、

網(wǎng)友回復(fù):謝謝樓主的積極，學(xué)習(xí)就該這樣，收藏！

網(wǎng)友回復(fù):C基本算法收集？

算法還分語言嗎？

網(wǎng)友回復(fù):引用28樓lingzil225的回復(fù)：

C基本算法收集？

算法還分語言嗎？

呵呵，不好意思，算法的實(shí)現(xiàn)應(yīng)該是有語言之分的吧?

網(wǎng)友回復(fù):如果你給出其它語言的，我也不會排斥的，謝謝你的支持

網(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ù):若是講搜集，給了代碼但沒給測試代碼的沒什么意義。

網(wǎng)友回復(fù):怎么都是排序方面的算法啊有沒有關(guān)于搜索方面的算法啊

比如爬蟲、網(wǎng)頁排序什么的

網(wǎng)友回復(fù):一堆好帖強(qiáng)烈支持?。?！

網(wǎng)友回復(fù)：

問：

最后一個算法放到vc中為什么編譯不能通過呢？

網(wǎng)友回復(fù):很好

網(wǎng)友回復(fù):頂我頂，

網(wǎng)友回復(fù):還好

網(wǎng)友回復(fù)：以前算法老師留了很多要求效率的算法作業(yè),都是在1分鐘具有處理百萬數(shù)量集

能算法，樓主使我想起了上學(xué)的日子啊?。?/p>

網(wǎng)友回復(fù):來冒個泡

網(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ù):做個記號，將來也許有用的到的時候.

網(wǎng)友回復(fù):記號

網(wǎng)友回復(fù):好頂頂

網(wǎng)友回復(fù):0K

網(wǎng)友回復(fù):做個模板嘛

網(wǎng)友回復(fù):樓主很好

網(wǎng)友回復(fù):謝謝,收臧了！

網(wǎng)友回復(fù):頂頂更健康

網(wǎng)友回復(fù):不錯，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了

網(wǎng)友回復(fù):引用37樓iambic的回復(fù)：

若是講搜集，給了代碼但沒給測試代碼的沒什么意義。

謝謝你，你的講法非常好，希望你能給出一些示例

網(wǎng)友回復(fù)：先MARK了

網(wǎng)友回復(fù):找一本書就行了.干嘛說那么多啊.你去下載里面找了有不少的.

網(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ù):不錯，謝謝LZ

網(wǎng)友回復(fù):這么多算法，收藏了

網(wǎng)友回復(fù):mark?!'

網(wǎng)友回復(fù):謝謝樓主分享

網(wǎng)友回復(fù):LZSS算法，LZ77的加強(qiáng)版本，高手應(yīng)該都知道的。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<ctype.h>

#defineN4096/*sizeofringbuffer*/

#defineF18/*upperlimitformatch_length*/

#defineTHRESHOLD2/*encodestringintopositionandlength

ifmatch_lengthisgreaterthanthis*/

#defineNILN/*indexforrootofbinarysearchtrees*/

unsignedlongint

textsize=0,/*textsizecounter*/

codesize=0,/*codesizecounter*/

printcount=0;/*counterforreportingprogresseveryIKbytes*/

unsignedchar

text_buf[NF-1];/*ringbufferofsizeN,

withextraFTbytestofacilitatestringcomparison*/

intmatch_position,match_length,/*oflongestmatch.Theseare

setbytheInsertNodeOprocedure.*/

Ison[N1],rson[N257],dad[N1];/*left&rightchildren&

parents一一Theseconstitutebinarysearchtrees.*/

FILE*infile,*outfile;/*input&outputfiles*/

網(wǎng)友回復(fù)：

voidInitTree(void)/*initializetrees*/

(

inti;

/*Fori=0toN-1,rson[i]andlson[i]willbetherightand

leftchildrenofnodei.Thesenodesneednotbeinitialized.

Also,dad[i]istheparentofnodei.Theseareinitializedto

NIL(=N),whichstandsfor'notused.'

Fori=0to255,rson[Ni1]istherootofthetree

forstringsthatbeginwithcharacteri.Theseareinitialized

toNIL.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

trees(text_buf[rj,thtree)andreturnsthelongest-matchposition

andlengthviatheglobalvariablesmatchjpositionandmatch_length.

Ifmatch_length=F,thenremovestheoldnodeinfavorofthenew

one,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){

if(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]-textbuf[pi])!=0)break;

if(i>matchlength){

matchposition=p;

if((matchlength=i)>=F)break;

}

)

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;

elseIson[dad[p]]=r;

dad[p]=NIL;/*removep*1

I

voidDeleteNode(intp)/*deletesnodepfromtree*/

I

intq;

if(dad[p]==NIL)return;/*notintree*/

if(rson[p]==NIL)q=lson[p];

elseif(Ison[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[lson[q]]=dad[q];

lson[q]=lson[p];dad[lson[p1]=q;

I

rson[q]=rson[p];dad[rson[p]]=q;

dad[q]=dad[p];

if(rson[dad[p]]==p)rson[dad[p]]=q;else1son[dad[p]]=q;

dad[p]=NIL;

}

voidEncode(void)

I

inti,c,len,r,s,last_match_length,code_buf_ptr;

unsignedcharcode_buf[17],mask;

InitTreeO;/*initializetrees*/

codebuf[0]=0;/*codebuf[1..16]saveseightunitsofcode,and

codebuf[0]worksaseightflags,〃1〃representingthattheunit

isanunencodedletter(1byte),〃0〃aposition-and-lengthpair

(2bytes).Thus,eightunitsrequireatmost16bytesofcode.*/

codebuf_ptr=mask=1;

s=0;r=N-F;

for(i=s;i<r;i)textbuf[i]='；/*Clearthebufferwith

anycharacterthatwillappearoften.*/

for(len=0;len<F&&(c=getc(infile))!=EOF;len)

textbuf[rlen]=c;/*ReadFbytesintothelastFbytesof

thebuffer*/

if((textsize=len)==0)return;/*textofsizezero*/

for(i=1;i<=F;i)InsertNode(r-i);/*InserttheFstrings,

eachofwhichbeginswithoneormore'space'characters.Note

theorderinwhichthesestringsareinserted.Thisway,

degeneratetreeswillbelesslikelytooccur.*/

InsertNode(r);/*Finally,insertthewholestringjustread.The

globalvariablesmatch_lengthandmatch_positionareset.*/

do(

if(match_length>len)match_length=len;/*match_length

maybespuriouslylongneartheendoftext.*/

if(matchlength<=THRESHOLD){

matchlength=1;/*Notlongenoughmatch.Sendonebyte.*/

codebuf[0]|=mask;/*，sendonebyte'flag*/

codebuf[codebuf_ptr]=text__buf[r];/*Senduncoded.*/

}else{

codebuf[codebuf_ptr]=(unsignedchar)matchposition;

codebuf[codebuf_ptr]=(unsignedchar)

(((match_position?4)&OxfO)

(matchlength-(THRESHOLD1)));/*Sendpositionand

lengthpair.Notematchlength>THRESHOLD.*/

}

if((mask<<=1)==0){/*Shiftmaskleftonebit.*/

for(i=0;i<code_buf_ptr;i)/*Sendatmost8unitsof*/

putc(code_buf[i],outfile);/*codetogether*/

codesize=code_buf_ptr;

code_buf[0]=0;code_buf_ptr=mask=1;

I

last_match_length=match_length;

for(i=0;i<last_match_length&&

(c二getc(infile))!=EOF;i){

DeleteNode(s);/*Deleteoldstringsand*/

textbuf[s]=c;/*readnewbytes*/

if(s<F-1)textbuf[sN]=c;/*Ifthepositionis

neartheendofbuffer,extendthebuffertomake

stringcomparisoneasier.*/

s=(s1)&(N-1);r=(r1)&(N-1);

/*Sincethisisaringbuffer,incrementtheposition

moduloN.*/

InsertNode(r);/*Registerthestringintextbuf[r..rF-l]*/

}

if((textsize=i)>printcount){

printfCld\r，z,textsize);printcount=1024;

/*Reportsprogresseachtimethetextsizeexceeds

multiplesof1024.*/

}

while(i<last_match_length){/*Aftertheendoftext,*/

DeleteNode(s);/*noneedtoread,but*/

s=(s1)&(N-1);r=(r1)&(N-1);

if(—len)InsertNode(r);/*buffermaynotbeempty.*/

I

}while(len>0);/*untillengthofstringtobeprocessediszero*/

if(code_buf_ptr>1){/*Sendremainingcode.*/

for(i=0;i<code_buf_ptr;i)putc(code_buf[i],outfile);

codesize=codebuf_ptr;

}

printf(^In:%ldbytes\n〃，textsize);/*Encodingisdone.*/

printf(，z0ut:%ldbytes\n，，?codesize);

printf(z，0ut/In:%.3f\n，\(double)codesize/textsize);

}

voidDecode(void)/*JustthereverseofEncode0.*/

I

inti,j,k,r,c;

unsignedintflags;

for(i=0;i<N-F;i)text_buf[i]=''；

r=N-F;flags=0;

for(;;){

if(((flags>>=1)&256)=0){

if((c=getc(infile))=EOF)break;

flags=cIOxffOO;/*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=text_buf[(ik)&(N-1)];

putc(c,outfile);text_buf[r]=c;r&=(N-1);

I

I

I

；

intmain(intargc,char*argv口)

char*s;

if(argc!=4){

printf(/z，Izssefilelfile2'encodesfilelintofile2.\n〃

〃'Izssdfile2fileTdecodesfile2intofilel.\n〃)；

returnEXIT_FAILURE;

if((s=argv[l],s[l]IIstrpbrk(s,〃DEde")==NULL)

Ii(s=argv[2],(infile=fopen(s,〃rb〃))==NULL)

II(s=argv[3],(outfile=fopen(s,〃wb〃))==NULL)){

printfC???%s\n〃，s);returnEXITFAILURE;

1

if(toupper(*argv[1])=='E')Encode();elseDecode();

fclose(infile);fclose(outfile);

returnEXITSUCCESS;

網(wǎng)友回復(fù):幫頂??！留著以后用

網(wǎng)友回復(fù):mark

網(wǎng)友回復(fù)：mark

網(wǎng)友回復(fù):收你們先，改天補(bǔ)回

網(wǎng)友回復(fù)