经典c编程实例

1.冒泡法：

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

Sinclude<iostream.h>

voidBubbleSort(int*pData,intCount)

(

intiTemp;

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

{

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

(

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

(

iTemp=pData[j-1];

pData[j-l]=pData[j];

pData[j]=iTemp;

)

)

}

)

voidmain0

(

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

BubbleSort(data,7);

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

cout<<data[i]«z/"\

cout<<"\n";

)

图示:before_compare|one_turn|two_turn|three_turnfour_turn|five_turn|six_turn

1010101010104

999994108

888499777

488866477

775466666

4555555通过上图可以看出，冒

泡法形象的描述来，4这个元素就像一个气泡逐渐冒到上面来了。我们排序的有7个元素,

最坏的情况全部倒序，4这个元素要冒上来需要6次。因此，n个元素，最坏的情况，需要

移动：1+2+3+...+（n-l）=l/2*n（n-l）次。倒序（最糟情况）

第一轮：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次

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

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

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

若存在一常量K和起点n0,使当n>=n0时，有f(n)<=K*g(n),则f(n)=O(g(n))»(呵

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

现在我们来看1/2*(n-l)*n,当K=l/2,n0=l,g(n)=n*n时,l/2*(nT)*n〈=l/2*n*n=K*g(n)。

所以f(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为0(n*n)。

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

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

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

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

交换法：

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

#include〈iostream.h>

voidExchangeSort(int*pData,intCount)

(

intiTemp;

for(inti=0;i<Count-l;i++)

(

for(intj=i+l;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]«w

cout«"\n";

}beforecompareIoneturntwoturn|threeturnfourturn|fiveturn|sixturn

10987654

91010101010108

89999977

78888666

677755555

664444445从上

面的算法来看，基本和冒泡法的效率一样。

倒序（最糟情况）

第一轮: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*（nT）*n,所以算法的复杂度仍然是0（n*n）。由于我们无法给出所有的情况，所以只能

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

3.选择法：

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

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

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

^include<iostream.h>

voidSelectSort（int*pData,intCount）

（

intiTemp;

intiPos;

for（inti=0;i<Count-l;i++）

（

iTemp=pData[i];

iPos=i;

for（intj=i+l;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]«，/;

cout<〈〃\n〃；

}该排序法的图示如下；i=0时：iTemp=pData[0]=10；iPos=i=0；

j=l；

pData[j]<iTemp—>pData[l]=9<10;

iTemp=pData[1]=9;

ipos=j=l;

j++=2

j=2;

pData[j]<iTemp---->pData[2]=8<9;

iTemp=pData[2]=8;

ipos=j=2;

j++=3

j=6;

pData[j]<iTemp---->pData[6]=4<5;

iTemp=pData[6]=4;

ipos=j=6;

j++=7;

pData[6]=Pdata[0];

pData[0]=4;

before_compareoneturntwoturnthreeturn

10444

9955

8886

7777

6668

5599

4101010由上面可以看到选择排序法并没有在一开始就交换数据，而

是用第一个数据去和所有的数据比较，如果第一个数据小于第二个数据，那么，先把第二个

数据放到个临时变量里面，同时记录这个较小的数据在待排序的集合中的位置。再用该集

合中的下一个数据和我们之前放在临时变量中的数据比较。也就是我们目前认为最小的数据

比较，如果比我们之前选出来的数据小，那么再替换该变量。如果比这个数据大，则继续用

下一个数据来比较。知道所有的数据都比较完为止。到这时，临时变量里面访的就是最小的

数据了。我们把这个数据和第-个数据做对换。此时，最小的元素排到了第一位。倒序(最

糟情况)

第一轮：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,10,8,9->(iTemp=8)7,10,8,9->(iTemp=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)=0(n)。所以，在数据较乱的时候，可以减少一定的交换次数。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[iPos+l]=pData[iPos];

iPos一;

}

pData[iPos+l]=iTemp;

}

voidmainO

(

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

InsertSort(data,7);

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

cout<<data[i]«/z

cout«?z\n，z;

)

i=l时：

iTemp=pData[l]=9

ipos=l-l=0;

ipos=0>=0&&iTemp=9<pData[0]=10;

pData[1]=pData[0]=10;

ipos-=0-l=-l;

pData[0]=9;9-10-8-7-6-5-4

i=2时：

iTemp=pData[2]=8

ipos=2-l=l;

ipos=l>=0&&iTemp=8<pData[1]=10;

pData[2]=pData[l]=10;

ipos―=1-1=0;9-10-10-7-6-5-4

ipos=0〉=0&&iTemp=8<pData[0]=9;

pData[1]=pData[0]=9;

ipos-=0-l=-l;

pData[0]=8;8-9-10-7-6-5-4

i=3时：

iTemp=pData[3]=7

ipos=3-l=2;

ipos=2>=0&&iTemp=7<pData[2]=10;

pData[3]=pData[2]=10;

ipos―=2-1=1;8-9-10-10-6-5-4

ipos=l>=0&&iTemp=8<pData[1]=9;

pData[2]=pData[1]=9;

ipos—=1-1=0;8-9-9-10-6-5-4

iposz:0>=0&&iTemp=7<pData[0]=8;

pData[1]=pData[0]=8;

ipos-=0-1=-l;

pData[0]=7;7-8-9-10-6-5-4i=4时:

iTemp=pData[4]=6;

ipos=4-l=3;

ipos=3>=0&&iTemp=6<pData[3]=10;

pData[4]=pData[3]=10;

ipos-=3-1=2;7-8-9-10-10-5-4

ipos=2>=0&&iTemp=7<pData[2]=9;

pData[3]=pData[2]=9;

ipos-=2-1=1;7-8-9-9-10-5-4

ipos=l>=0&&iTemp=7<pData[1]=8;

pData[2]=pData[1]=8;

ipos―=1-1=0;7-8-8-9-10-5-4

ipos=0>=0&&iTemp=7<pData[0]=7;

pData[1]=pData[0]=7;

ipos-=1-1=0;

pDate[0]=6;6-7-8-9-10-5-4

由上述可知：插入排序是先把集合中的下一个元素抽取出来

放到一个临时变量里面和第一个元素比较。并记录该元素在集合中的位置

如果第二个元素比第一个小，那么第一个元素和第二个元素对调。下一次

再用第三个元素先和变化后的第二个元素比较，如果变化后的第二个元素

小于第三个元素，用第二个元素的值覆盖第三个元素。在从临时变量里面

取出该元素放到第二个元素中去。

倒序（最糟情况）

第一轮：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,二,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）（推导类似选择法），但我们每次要进行与内层循环相同次数的

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

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

#include<iostream>

usingnamespacestd;

voidcoutstream(inta[],intn){

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

)

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

)

a[j]=temp;

)

)

intmain()

(

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

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

coutstream(a,5);//

return0;

)

二、高级排序算法：

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

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

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

换)。然后对两边分别使用这个过程(最容易的方法一递归)。

1.快速排序：

#include<iostream.h>

voidrun(int*pData,intleft,intright)

inti,j;

intmiddle,iTemp;

i=left;

J=right;

middle=pData[(left+right)/2];〃求中间值

do{

whi1e((pData[i]<midd1e)&&(i<right))〃从左扫描大于中值的数

i++；

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

j—；

if(iCj)〃找到了一对值

(

〃交换

iTemp=pData[i];

pData[i]=pDataEj];

pData[j]=iTemp;

i++；

j—；

)

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

〃当左边部分有值(left〈j),递归左半边

if(left<j)

run(pData,left,j);

〃当右边部分有值(right"),递归右半边

if(right>i)

run(pData,i,right);

)

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++)

cout<<data[i]«/z

cout«，z\n，z;

}

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

的情况

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

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

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

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

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

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

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

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

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

情况下速度要慢于快速排序(因为要重组堆)。三、其他排序

1.双向冒泡：

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

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

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

了)。

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

^include<iostream.h>

voidBubble2Sort(int*pData,intCount)

intiTemp;

intleft=1;

intright=Count-1;

intt;

do

(

〃正向的部分

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

(

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

(

iTemp=pData[i];

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

pData[i-l]=iTemp;

t=i;

)

)

left=t+1;

〃反向的部分

for(i=left;i<right+l;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()

(

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

Bubble2Sort(data,7);

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

cout<<data[i]«/z;

cout«"\n〃；

}快速排序

#include<iostream>

usingnamespacestd;

classQuicksort

(

public:

voidquick_sort(int*x,intlow,inthigh)

(

intpivotkey;

if(low<high)

(

pivotkey=partion(x,low,high);

quick_sort(x,low,pivotkey-1);

quick_sort(x,pivotkey+1,high);

)

)

intpartion(int*x,intlow,inthigh)

(

intpivotkey;

pivotkey=x[low];

while(low<high)

(

whi1e(low<high&&x[high]>=pivotkey)

—high;〃还有while循环只执行这一句

x[low]=x[high];

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

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

x[high]=x[low];

)

x[low]=pivotkey;

returnlow;

)

)；

intmain()

(

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

Quicksortqs;

qs.quicksort(x,0,9);

cout<<〃排好序的数字序列为：〃“endl;

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

(

printf('%d",x[i]);

)

return0;

)

2.SHELL排序

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

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

工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元

素的排序以次类推。

#include<iostream.h>

voidShellSort(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];

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[w+k]=pData[w];

w=w-k;

)

pData[w+k]=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次暴。同样因为非常复杂并

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

#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[j+U)

(

temp=list[j];

list[j]=list[j+l];

list[j+l]=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++)

cout«a[i]«z/

return0;

)

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

的一种。下面用个例子更好的理解一下无序数列：32,43,56,99,34,8,54,761.

首先设定gap=n/2=4于是分组32,34排序32,3443,88,4356,

5454,5699,7676,99数列变成32,8,54,76,34,43,56,

992.gap=gap/2=2于是分组32,54,34,56排序32,34,54,568,76,43,99

8,43,76,99于是数列变成32,8,34,43,54,76,56,993.gap=gap/2=l于是分组32,

8,34,43,54,76,56,99排序8,32,34,43,54,56,76,99gap=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>=O&&v[j]>v[j+gap];j-=gap){〃比较相距

gap的元素，逆序互换temp=v[j];v[j]=v[j+gap];

v[j+gap]=temp;}}〃帕斯卡恒等式为C(n,k)=C(nT,kT)+C(nT,k)

longfun(longn,longr)

(

if(r<0||n<0)

(

printf('\nError.Exit!”);

exit(1);

}

if(r>n)return0;

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

returnn;

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

return1;

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

}

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

template<classT>

voidselectsort(Tarr[],intsize)

(

Ttemp;

inti,j;

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

for(j=i+l;j<size;j++)

if(arr[i]>arr[jj)

(

temp二arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

)

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

template<classT>

voidbubblesort(T*d,intn)

(

inti,j;

Tt;

for(1=0;i<n-l;i++)

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

if(d[j]>d[j+l])

{

t=d[j];

d[j]=d[j+l];

d[j+l]=t;

)

)

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

template<classT>

voidInsertSort(TA[],intn)

(

inti,j;

Ttemp;

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

temp=A[i];

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

A[j+l]=A[j];

A[j+1]=temp;

)

}

〃二分查找法的函数模板

template<classT>

intbinary_search(Tarray[],Tvalue,intsize)

(

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

while(low<=high)

(

mid=(high+low)/2;

if(value<array[mid])

high=mid-1;

elseif(value>array[mid])

low=mid+1;

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]<=，T)

dec+=oth[i]~55;

elseif(oth[i]>=，a，&&oth[i]<=，z)

dec+=oth[i]-87;

i++；

)

returndec;

)

〃将10进制(无符号)转2〜36进制数

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

制

charch,*left=oth,*right=oth,num[]=，/0123456789ABCDEFGHIJKLMN0PQRSTUVWXYZ//;

do

{

*right=num[dec%base];

right++;

}while(dec/=base);

*right=，\0，;

right—;

while(left<right)

(

ch=*left;

*left=*right;

*right=ch;

left++;right一；

)

returnoth;

)

〃统计substr在str中的个数

intfun(char*str,char*substr)

(

intn=0;

char*q;

q=substr;

while(*str!=，\0J)

(

if(*str二二*substr)

(

str++;

substr++;

if(*substr==，\0')

{

n++;

substr=q;

)

)

else

(

str++;substr=q;

)

returnn;

}使用数组实现约瑟夫环：

ttinclude<stdio.h>

#include<stdlib.h>

main()

(

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

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

scanf(〃/d〃，&n);

intarray[n+1];

intorder[n+1];

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

scanf("%d〃，&m);

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

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

array[i]=i+l;

array[n]=l;

printf(〃%d〃,array[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("%d*”,order[o]);

)

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

per=i;

i二array[i];

k++;

)

}

order[n]=i;

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

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

printf(〃%d〃，order[i]);

system(/zpause，z);

return0;

}输入正整数N,然后是N*N个正整数，表示边权邻接矩阵。

输出求解过程。

/*

Problem:WeightedBipartiteMatching

Algorithm:HungarianAlgorithm

Reference:DouglasB.West,IntroductiontoGraphTheory,125-129

Author:PC

Date:2005.2.23

*/

#include<iostream.h>

#include<iomanip.h>

#include<fstream.h>

#include〈memory.h>

ifstrearnfin("input.txt〃)；

#definecinfin

constintmax二50;

boolT[max],R[max],visited[max];

intU[max],V[max],gt[max][max],x[max],y[max];

intN;

voidoutput()

(

inti,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)«，Rf«);

cout«endl;

)

for(i=0;i<N;i++)

if(T[i])cout«setw(2)«，V«J';

elsecout«setw(2)'；

cout<<endl;

)

intpath(intu)

intv;

for(v=0;v<N;v++)

if(gt[u][v]==0&&!visited[v])

(

visited[v]=l;

if(y[v]<0"path(y[v]))

(

x[u]=v;y[v]=u;

R[u]=l;T[v]=0;

return1;

}else{

T[v]=l;

R[y[v]]=0;

}

)

)

return0;

intmain0

(

for(;cin»N;){

inti,j,ans,sigma,step=0;

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

)

}

for(i=0;i<N;i++)

(

for(j=0;j<N;j++)

(

gt[i][j]=U[i]-gt[i][j];

}

}

//////////////////////////////////////////////////////////

for(;;)

ans=O;

sigma=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++)

(

if(x[i]<0)

(

memset(visited,0,sizeof(visited));

ans+=path(i);

)

for(j=0;j<N;j++)

(

if(sigma<l|Isigma>gt[i][j]&>[i][j]>0)

sigma=gt[i][j];

)

)

cout<<z，stepz,«++step<<，z:\n”;

output();

if(ans>=N)

break;

for(i=0;i<N;i++)

(

if(!R[i])

U[i]-=sigma;

if(T[i])

V[i]+=sigma;

for(j=0;j<N;j++)

(

if(T[j])

gt[i][j]+=sigma;

if(!R[i])

gt[i][j]-=sigma;

}

)

)

//////////////////////////////////////////////////////////

ans=0;

cout<<，，Result:，，«endl;

for(i=0;i<N;i++)

ans+=U[i]+V[i];

for(j=0;j<N;j++)

(

if(x[i]=j&&y[j]==i)cout«setw(2)<<U[i]+V[j]<<,

elsecout«setw(2)«0<<J';

)

cout«endl;

}

cout«，zMaximum:，，<<ans«endl;

)

return0;

)

input,txt:

5

41623

50376

23458

34634

46586

5

44436

11434

14535

56479

53683

5

78987

87676

96546

85764

76555

5

12345

67872

13445

36287

41354

/*

Problem:WeightedBipartiteMatching

Algorithm:HungarianAlgorithm

Reference:DouglasB.West,IntroductiontoGraphTheory,125-129

Author:PC

Date:2005.2.23

*/

#include<iostream.h>

#include<iomanip.h>

#include<fstream.h>

#include<memory.h>

ifstreamfin(〃input.txt〃);

#definecinfin

constintmax=50;

boolT[max],R[max],visited[max];

intU[max],V[max],gt[max][max],x[max],y[max];

intN;

voidoutput()

(

inti,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)'<<';

cout<<endl;

)

intpath(intu)

{

intv;

for(v=0;v<N;v++)

if(U[u]+V[v]-gt[u][v]==0&&!visited[v])

(

visited[v]=l;

if(y[v]<0||path(y[v]))

(

x[u]=v;y[v]=u;

R[u]=l;T[v]=O;

return1;

}else{

T[v]=l;

R[y[v]]=O；

)

)

)

return0;

}

intmain()

(

inti,j,ans,sigma,step=0;

for(;cin»N;){

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

)

)

//////////////////////////////////////////////////////////

for(;;)

(

ans=0;

sigma=0;

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++)

if(x[i]<0)

memset(visited,0,sizeof(visited));

ans+=path(i);

)

)

for(i=0;i<N;i++)

(

if(!R[i])

for(j=0;j<N;j++)

(

if(!T[jJ&&(sigma<l

sigma>U[i]+V[j]-gt[i][j]&&U[i]+V[j]-gt[i][j]>0))

sigma=U[i]+V[j]-gt[i][j];

)

)

cout«*step”<<++step<<":\n”;

output();

if(ans〉=N)

break;

for(i=0;i<N;i++)

(

if(!R[i])

U[i]-=sigma;

if(T[i])

V[i]+=sigma;

)

}