c语言算法分析 计算机

1.冒泡法：

这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:

#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次）

循环次数：6次

交换次数：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次）

循环次数：6次

交换次数：3次

上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交

换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为12...

n-U写成公式就是l/2*(n-l)*n。现在注意，我们给出0方法的定义：

若存在-常量K和起点nO,使当n>=nO时，有f(n)〈=K*g(n),则f(n)=0(g(n))。(呵

呵，不要说没学好数学呀，对于编程数学是非常重要的！！！)

现在我们来看1/2*(n-l)*n,当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)»所以我们程序循环的复杂度为0(n*n)。

再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换

本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样(每

次循环判断都会交换)，复杂度为0(n*n)。当数据为正序，将不会有交换。复杂度为0(0)。

乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。

网友回复:

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

2.交换法:

交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。

#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次）

循环次数：6次

交换次数：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次）

循环次数：6次

交换次数：3次

从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是

l/2*（n-l）*n,所以算法的复杂度仍然是0（n*n）。由于我们无法给出所有的情况，所以只能

直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。

网友回复:

C/Ccode

CodehighlightingproducedbyActiproCodellighlighter(freeware)

http:〃www.CodeHighlighter.com/

3.选择法：

现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能(某些情况下)这种方

法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择

最小的与第二个交换，这样往复下去。

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

循环次数：6次

交换次数：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次)

循环次数：6次

交换次数：3次

遗憾的是算法需要的循环次数依然是l/2*(n-l)*n。所以算法复杂度为0(n*n)。

我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n

所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

网友回复：http:〃student,zjzk.cn/course_ware/data_structure/web/main.htm

网友回复：

C/Ccode

CodehighlightingproducedbyActiproCodellighlighter(freeware)

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

4.插入法：

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继

续下一张

#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次）（循环1次）

第二轮：9,10,8,7->8,9,10,7（交换1次）（循环2次）

第一轮：8,9,10,7->7,8,9,10（交换1次）（循环3次）

循环次数：6次

交换次数：3次

其他：

第一轮:8,10,7,9->8,10,7,9（交换0次）（循环1次）

第二轮：8,10,7,9->7,8,10,9（交换1次）（循环2次）

第一轮:7,8,10,9->7,8,9,10（交换1次）（循环1次）

循环次数：4次

交换次数：2次

上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其

实不是，因为其循环次数虽然并不固定，我们仍可以使用0方法。从上面的结果可以看出，

循环的次数f（n）〈=l/2*n*（n-l）〈=l/2*n*n。所以其复杂度仍为0（n*n）（这里说明一下，其实

如果不是为了展示这些简单排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观

上看，交换次数是0（n）（推导类似选择法），但我们每次要进行与内层循环相同次数的'='

操作。正常的一次交换我们需要三次'=’而这里显然多了一些，所以我们浪费了时间。

最终，我个人认为，在简单排序算法中，选择法是最好的。

网友回复：

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[i]位置的数据存起来

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;

网友回复：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter（freeware）

http://www.CodeHighlighter.com/

二、高级排序算法：

高级排序算法中我们将只介绍这•种，同时也是目前我所知道（我看过的资料中）的最快的。

它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中

间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。

然后对两边分别使用这个过程（最容易的方法——递归）。

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))〃从左扫描大于中值的数

i；

while((pData[j]>middle)&&(j>left))〃从右扫描大于中值的数

J—；

〃找到了一对值

(

〃交换

iTemp=pData[i];

pData[i]=pData[j];

pData[j]=iTemp;

i；

J—；

!

}while(i«j);〃如果两边扫描的下标交错，就停止(完成一次)

〃当左边部分有值(left。)，递归左半边

if(left<j)

run(pData,left,j);

〃当右边部分有值(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〃;

}

这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想

的情况

1.数组的大小是2的幕，这样分下去始终可以被2整除。假设为2的k次方，即k-log2(n)o

2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。

第一层递归，循环n次，第二层循环2*(n/2).....

所以共有n2(n/2)4(n/4)...n*(n/n)=nnn...n=k*n=log2(n)*n

所以算法复杂度为0(log2(n)*n)

其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那

么他将变成交换法(由于使用了递归，情况更糟)。但是你认为这种情况发生的几率有多大？？

呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。

如果你担心这个问题，你可以使用堆排序，这是一种稳定的0(log2(n)*n)算法，但是通常情

况下速度要慢于快速排序(因为要重组堆)。

网友回复:帮UP呵呵泡沫排序还没有听说过呀

网友回复：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

三、其他排序

1.双向冒泡：

通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。

代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。

写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为，也许我错了)。

反正我认为这是一段有趣的代码，值得一看。

#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

网友回复：

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循环只执行这一句

x[low]=x[high];

while(low<high&&x[low]<=pivotkey)

low;〃还有while循环只执行这•句

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«”排好序的数字序列为J〃《endl;

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

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

)

return0;

}

网友回复：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http://www.CodeHighlighter.com/

2.SHELL排序

这个排序非常复杂，看了程序就知道了。

首先需要一个递减的步长，这里我们使用的是9、5、3、1(最后的步长必须是1)。

工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔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个元素的下标

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步长造成程序异常而写的代码。这个代码我认为很值得看。这个算法的得名是因为其

发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因避免使用2的幕次

步长，它能降低算法效率。”另外算法的复杂度为n的1.2次辱。同样因为非常复杂并“超出

本书讨论范围”的原因(我也不知道过程)，我们只有结果了

网友回复：冒泡排序性能优化版

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http:〃www.CodeHighlighter.com/

#include<iostream>

usingnamespacestd;

voidmaopao(int*list,intn)

(

inti=n,j,temp;

boolexchange;〃当数据」经排好时，退出循环

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;

)

网友回复：以上是我从网上摘下来的，请大家有什么好的基本算法拿出来研究一下啊，谢谢哦,

记得要有代码哦〜

网友回复:LZ原来不是提问，是发帖，晕，那还给出那么多分

网友回复:引用14楼anglecloudy的回复：

LZ原来不是提问，是发帖，晕，那还给出那么多分

不是发帖了啊，而是来总结一下基本的算法思想〜有利于学习〜不光是排序的问题啦，其它

的

解决特殊问题的算法也可以show出来大家研究一下，学习无止境@!

网友回复：引用14楼anglecloudy的回复：

LZ原来不是提问，是发帖，晕，那还给出那么多分

谢谢你的积极发言〜

网友回复:刚才在CSDN的C语言板块看到了有人说Shell排序的问题，所以一起学习了一下，

并进行如下总结

shell排序的思想是根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序

的一种。下面用个例子更好的理解一下

无序数列：32,43,56,99,34,8,54,76

1.首先设定gap=n/2=4于是分组

32,34排序32,34

43,88,43

56,5454,56

99,7676,99

数列变成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

于是数列变成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结束...

相应的C语言代码引用K&RC程序设计一书中给出的代码

voidshellsort(intv[],intn)

(

intgap,i,j,temp;

for(gap=n/2;gap>0;gap/=2)〃设定步长

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;

)

}

网友回复:归并

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

网友回复:帮顶

网友回复：

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)〃根据组合定义，我们有C(n,l)=C(n,nT)二n

returnn;

if(r=0|r==n)〃根据组合定义,我们有C(n,0)=C(n,n)=l

return1;

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

)

〃选择法对数组排序的函数模板

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;

〃冒泡法对数组排序的函数模板

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;

}

}

〃插入法对数组排序的函数模板

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;

}

!

〃二分查找法的函数模板

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进制数与10进制数相互转换

〃将2~36进制数转换成10进制数

unsignedintOthToDec(char*oth,intbase)//base为已知数的进制

{

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进制(无符号)转2、36进制数

char*DecToOth(char*oth,unsignedintdec,intbase)〃base为要转换的数的进制

(

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

〃统计substr在str中的个数

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

网友回复：

C/Ccode

CodehighlightingproducedbyActiproCodeHighlighter(freeware)

http:〃www.CodeHighlighter.com/

使用数组实现约瑟夫环：

#include<stdio.h>

#include<stdlib.h>

main()

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

printf(“请输入总共的人数，记为n\n");

scanf("%d〃，&n);

intarray[n1];

intorder[n1];

printf(〃请输入几号出圈，记为m\n〃)；

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

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

for(;i<n;i)〃数组链表模拟

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;

)

网友回复:好贴。关注中！！！

网友回复:真该好好顶一下

网友回复：引用23楼Gengoo的回复：

真该好好顶一下

兄弟们不要光顶啊，把你们珍藏的经典算法拿出来大家收集一下吧

网友回复:看了半天都是一堆排序

网友回复：引用25楼garybo的回复：

看了半天都是一堆排序

那么兄弟啊，你有没有好的代码呢？共享・下、

网友回复:谢谢楼主的积极，学习就该这样，收藏！

网友回复:C基本算法收集？

算法还分语言吗？

网友回复:引用28楼lingzil225的回复：

C基本算法收集？

算法还分语言吗？

呵呵，不好意思，算法的实现应该是有语言之分的吧〜

网友回复:如果你给出其它语言的，我也不会排斥的，谢谢你的支持

网友回复:mark!

网友回复:up

网友回复:帮顶下

网友回复:up

网友回复:梯形插补

f=a/f;

f=f；

f-=a/f;

网友回复:mark

网友回复:若是讲搜集，给了代码但没给测试代码的没什么意义。

网友回复:怎么都是排序方面的算法啊有没有关于搜索方面的算法啊

比如爬虫、网页排序什么的

网友回复:一堆好帖强烈支持！！！

网友回复：

问：

最后一个算法放到vc中为什么编译不能通过呢？

网友回复:很好

网友回复:顶我顶，

网友回复:还好

网友回复：以前算法老师留了很多要求效率的算法作业,都是在1分钟具有处理百万数量集

能算法，楼主使我想起了上学的日子啊！！

网友回复:来冒个泡

网友回复:收藏

网友回复:标记

网友回复：51自学网一专业培训老师录制的视频教程，让学习变得很轻松

网友回复:爬虫

网友回复:做个记号，将来也许有用的到的时候.

网友回复:记号

网友回复:好顶顶

网友回复:0K

网友回复:做个模板嘛

网友回复:楼主很好

网友回复:谢谢,收臧了！

网友回复:顶顶更健康

网友回复:不错，mark'

网友回复:好帖啊

严重关注中啊

期待更多高手们的出现啊

网友回复:收藏

网友回复:该回复于2008-10-0217:14:08被版主删除

网友回复:学习了

网友回复:好东西，mark了

网友回复:引用37楼iambic的回复：

若是讲搜集，给了代码但没给测试代码的没什么意义。

谢谢你，你的讲法非常好，希望你能给出一些示例

网友回复：先MARK了

网友回复:找一本书就行了.干嘛说那么多啊.你去下载里面找了有不少的.

网友回复:集思广益也不是件坏事啊一

网友回复:亦即所谓的选择法吧！

网友回复:希望大家看清楚意思再回帖吧，我想发帖的主要意思是求一些基本的算法以及实现

的源代码〜

网友回复：谢谢LZ

向大伙好好学习。。。

网友回复:学习了……

网友回复:基数排序。

和把一堆乱扑克搞有序就是这么干的。

网友回复:好贴

网友回复:不错，谢谢LZ

网友回复:这么多算法，收藏了

网友回复:mark〜!'

网友回复:谢谢楼主分享

网友回复:LZSS算法，LZ77的加强版本，高手应该都知道的。

#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*/

网友回复：

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;

网友回复:帮顶！！留着以后用

网友回复:mark

网友回复：mark

网友回复:收你们先，改天补回

网友回复