2020年计算机算法设计与分析课程设计常规题目的C及C代码集

计算机算法设计与分析课程设计常规

题目的C及C代码集

文档仅供参考，不当之处，请联系改正。

合并排序1:

#include<iostream>

usingnamespacestd;

constintN=100;

classlist

(

public:

intarray[N];

voidinput(inta);

voidmerge(intarrayc[],intarrayd[],int

l,intm,intr);

voidmergepass(intarrayx[],int

arrayy[],ints);

voidmergesort(intarrayl[]);

voiddiaplay(inta);

)；

voidlist::input(inta)

(

cout«MPleaseinputshortedarray:n«endl;

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

cin»array[i];

)

文档仅供参考，不当之处，请联系改正。

voidlist::merge(intarrayc[],intarrayd[],intl,int

m,intr)

(

inti=l;

intj=m+l;

intk=l;

while((i<=m)&&(j<=r))

if(arrayc[i]<=arrayc[j])

arrayd[k++]=arrayc[i++];

elsearrayd[k++]=arrayc[j++];

if(i>m)

for(intq=j;q<=r;q++)

arrayd[k++]=arrayc[q];

else

for(intq=i;q<=m;q++)

arrayd[k++]=arrayc[q];

)

voidlist::mergepass(intarrayx[],intarrayy[],int

s)

inti=0;

while(i<=N-2*s)

文档仅供参考，不当之处，请联系改正。

merge(arrayx,arrayy,i,i+s-l,i+2*s-l);

i=i+2*s;

)

if((i+s)<N)

merge(arrayx,arrayy,i,i+s-l,N-l);

else

for(intj=i;j<N;j++)

arrayy[j]=arrayx[j];

)

voidlist::mergesort(intarray1[])

(

intarray2[N];

ints=l;

while(s<N)

(

mergepass(arrayl,array2,s);

s+=s;

mergepass(array2,array1,s);

s+=s;

)

)

文档仅供参考，不当之处，请联系改正。

voidlist::diaplay(inta)

(

for(inti=N-a;i<N;i++)

cout«array[i];

)

voidmain()

(

listf;

inta;

coutvv”请输入要合并排序的数组大小：(数

组最大上限100)”vveii祖；

cin»a;

f.input(a);

f.mergesort(f.array);

f.diaplay(a);

)

合并排序：2

#include<iostream>

usingnamespacestd;

voidMERGES(int*A,intp,intq,intr)〃下标

文档仅供参考，不当之处，请联系改正。

P<=q<r

intnl=q-p+l;//nl:p,q之间的数的个数

intn2=r-q;//n2：q以后到r的数的个数

int*L=newint[nl+1],〃动态申请两个子

数组

*R=newint[n2+l];

inti,j,k;

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

(

L[i]=A[p+i-l];

)

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

(

R[j]=A[q+j]；

)

L[nl]=10000;〃设置哨兵

R[n2]=10000;

i=0;

j=0；

for(k=p-l;k<r;k++)

文档仅供参考，不当之处，请联系改正。

if(L[i]<=R[j])

(

A[k]=L[i];

i=i+l;

)

else

(

A[k]=RU];

j=j+l；

)

)

)

voidMERGESORT(int*A,intp,intr)

(

if(P<r)

(

intq=(p+r)/2;

MERGESORT(A,p,q);

MERGESORT(A,q+l,r);

MERGES(A,p,q,r);

)

文档仅供参考，不当之处，请联系改正。

voidmain()

intx,z,p,r;

cout«”请输入数组长度"vVendl;

cin»x;

int*A=newint[x];

cout«"请输入数组的元素"vvendl;

for(inty=0;y<x;y++)

(

cin»z;

A[y]=z;

)

coutvv”请输入上下限p,rn«endl;

cin»p»r;

MERGESORT(A,p,r);

cout«"合并排序后为："vVendl;

for(intm=p;m<=r;m++)

(

cout«A[m];

)

delete[]A;

)

文档仅供参考，不当之处，请联系改正。

合并排序3：

#include<iomanip.h>

#include<iostream.h>〃这个函数将b[0]至

b[right」eft+l]拷贝到至a[right]

template<classT>

voidCopy(Ta[],Tb[],intleft,intright)

(

intsize=right-left+l;

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

(

a[left++]=b[i];

)

)〃这个函数合并有序数组

到b,得到新的有序数组b

template<classT>

voidMerge(Ta[],Tb[],intleft,inti,intright)

(

intalcout=leftj/指向第一个数组开头

alend=i〃指向第一个数组结尾

a2cout=i+l,〃指向第二个数组开头

a2end=right,〃指向第二个数组结尾

文档仅供参考，不当之处，请联系改正。

bcout=0;〃指向b中的元素

for(intj=0;j<right-left+1；j++)//执行

right-left+1次循环

(

if(alcout>alend)

(

b[bcout++]=a[a2cout++];

continue;

}〃如果第一个数组结束，拷贝第二个数组的

元素到b

if(a2cout>a2end)

(

b[bcout++]=a[alcout++];

continue;

}〃如果第二个数组结束，拷贝第一个数组的

元素到b

if(a[alcout]<a[a2cout])

(

b[bcout++]=a[alcout++];

continue;

}〃如果两个数组都没结束，比较元素大小，

把较小的放入b

文档仅供参考，不当之处，请联系改正。

else

b[bcout++]=a[a2cout++];

continue;

)

)

}〃对数组right]进行合并排序

template<classT>

voidMergeSort(Ta[],intleft,intright)

(

T*b=newint[right-left+l];

if(left<right)

(

inti=(left+right)/2;〃取中点

MergeSort(a,left,i);〃左半边进行合并排序

MergeSort(a,i+l,right);〃右半边进行合并排

序

Merge(a,b,Ieft,i,right);〃左右合并到b中

Copy(a,b,left,right);//Ab拷贝回来

)

}//from

intmain()

文档仅供参考，不当之处，请联系改正。

intn;

cout«nhowmanynumberstosort:'';

cin»n;

int*a=newint[n];

cout«ninputn«n«nnumbers:n;

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

(

cin»a[i];

)

MergeSort(a,0,n-1);

for(intj=O;j<n;j++)

(

cout«setw(5)«a[j];

)

return1;

)

合并排序4：

#include<iostream>

usingnamespacestd;

voidMerge(inta[],intb[],intl,intm,intr)

文档仅供参考，不当之处，请联系改正。

inti=I,j=m+l,k=l;

while((i<=m)&&(j<=r))

if(a[i]<=a[j])b[k++]=a[i++];

elseb[k++]=a[j++];

if(i>m)

for(intq=j;q<=r;q++)

b[k++]=a[q];

else

for(intq=i;q<=m;q++)

b[k++]=a[q];

)

voidCopy(inta[],intb[],ints,intn)

(

for(inti=s;i<=n;i++)

a[i]=b[i];

)

voidMergeSort(inta[],intleft,intright)

(

inti;

if(left<right)

文档仅供参考，不当之处，请联系改正。

i=(left+right)/2;

intb[100];

MergeSort(a,left,i)；

MergeSort(a,i+l,right);

Merge(a,b,left,i,right);

Copy(a,b,left,right);

)

)

intmain()

(

inta[100];

intn,i；

coutvv”输入元素个数n:u;

cin»n;

coutvv”输入一维数组a[n«n«n]:n;

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

cin»a[i];

MergeSort(a,0,n-l);

coutvv”输出排序为:“；

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

cout«a[i]«,

cout«endl;

文档仅供参考，不当之处，请联系改正。

return0;

)

矩阵相乘1：

#include<iostream>

#include<stdio.h>

usingnamespacestd;

intmain()

(

inti,j,k;

coutvv”输入二维数组a的行数和二维数组c

的行数x:n;

intx;

cin»x;

coutvv”输入二维数组a的列数和二维数组b

的行数y：n;

inty;

cin»y;

coutvv”输入二维数组b的列数和二维数组c

的行数Z：”；

intz;

cin»z;

文档仅供参考，不当之处，请联系改正。

int**a,**b,**c;

a=newint*[x];

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

(

a[i]=newint[y];

)

coutvv”输入二维数组a:H«endl;

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

(

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

(

cin»a[i][j];

)

)

b=newint*[y];

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

(

b[i]=newint[z];

)

coutvv”输入二维数组b:n«endl;

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

文档仅供参考，不当之处，请联系改正。

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

(

cin»b[i][j];

)

)

c=newint*[x];

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

(

c[i]=newint[z];

)

coutvv”输入二维数组c:n«endl;

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

(

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

(

c[i]U]=0;

)

)

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

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

文档仅供参考，不当之处，请联系改正。

for(k=0;k<y;k++)

(

c[i][j]+=a[i][k]*b[k][j];

)

)

)

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

(

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

(

coutvvc[i][j]vv，'；

)

cout«endl;

)

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

(

delete[]a[i];

)

delete[]a;

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

delete[]c[i];

文档仅供参考，不当之处，请联系改正。

)

delete[]c;

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

(

delete[]b[i];

)

delete[]b;

return0;

)

矩阵相乘2：

#include<iostream>

usingnamespacestd;

#defineM2

#defineN3

#defineP4

intmain()

(

inta[M][N]={{l,2,3},{4,5,6});

intb[N][P]={{7,8,9」},{2,3,4,5},{6,7,8,9}};

intc[M][P];

inti,j,k;

文档仅供参考，不当之处，请联系改正。

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

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

c[i][j]=O;

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

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

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

c[i][j]+=a[i][k]*b[k][j];

cout«n矩阵相乘结果是："vVendl;

for(i=0;i<M;i++){for(j=0;j<P;j++)

cout«c[i][j]«nn;

cout«endl;

}//system(npause");

return0;

)

矩阵相乘3：

#include<iostream>

#include<iomanip>

usingnamespacestd;

intmain()

constintm=3;

文档仅供参考，不当之处，请联系改正。

constintn=3;

inta[m][n],i,j;〃初始化数组a,b

for(i=0;ivm;i++)〃对数组a赋值并显示

(

for(j=O;j<n;j++)

(

cout«na[n«i«n]n«n[n«j«n]=n;

cin»a[i][j];

)

)

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

(

for(j=O;j<n;j++)

cout«setw(4)«a[i][j];

cout«endl;

)

constintk=3;

constinth=2;

intb[k][h],x,y;

for(x=0;x<k;x++)

for(y=0;y<h;y++)

文档仅供参考，不当之处，请联系改正。

cout«nb[n«x«n]n«n[n«y«n]=n;

cin»b[x][y];

)

)

for(x=O;x<k;x++)

(

for(y=O;y<h;y++)

cout«setw(4)«b[x][y];

cout«endl;

)

intc[m][h];//乘赋值给数组c

for(intr=O;r<m;r++)

(

for(intt=O;t<h;t++)〃数组a与b相〃对

数组b赋值并显示

(

c[r][t]=O;

for(ints=O;s<k;s++)

(

c[r][t]+=a[r][s]*b[s][t];

)

文档仅供参考，不当之处，请联系改正。

)

)

cout«nc[n«m«n]n«n[n«h«n]H«endI;

for(intz=O;z<m;z++)

(

for(intw=O;w<h;w++)

cout«setw(4)«c[z][w];

cout«endl;

)

return0;〃显示数组c

)

矩阵相乘4：

#include<iostream>

usingnamespacestd;

voidchain(int*p,intn,intm[][7],mts[][7])//p维

数数组，m最优乘次数组，s记录划分方案

(

intj;

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

m[i][i]=0;

for(intr=2;r<=n;r++)

文档仅供参考，不当之处，请联系改正。

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

(

j=i+r-l；

m[i][j]=m[i+l][j]+p[i-l]*p[i]*p[j];

s[i][j]=i；

for(intk=i+l;k<j;k++)

(

int

t=m[i][k]+m[k+l][j]+p[i-l]*p[k]*p[j];

if(t<m[i][j])

(

m[i][j]=t;

s[i][j]=k;

)

)

for(i=l;iv=n;i++)〃我把它翻过来输出。。。

for(j=ii;j>=i;j-)

文档仅供参考，不当之处，请联系改正。

cout«m[i][j]«M;

)

cout«endl;

)

)

voidTraceback(inti,intj,ints口[7])〃输出相乘方

案

(

if(i==j)

return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+l,j,s);

cout«HMultiplyAn«i«n,n«s[i][j];

cout«"andB''«(s[i][j]+l)«n,H«j«endl;

return;

)

intmain()

(

intp[7],m[7][7],s[7][7],n;

while(n!=EOF)

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

文档仅供参考，不当之处，请联系改正。

cin»p[i]»endl;

)

chain(p,n,m,s);

Traceback(l,6,s);

)

return0;

)

Haffman编码1：

#include<iostream>

#include<string>

usingnamespacestd;

typedefstruct

(

intweight;

intflag;

intparent;

intlehild;

intrchild;

)

hnodetype;

文档仅供参考，不当之处，请联系改正。

typedefstruct

(

intbit[10];

intstart;

charleaf;

)

hcodetype;

voidhuf(charcha[],intm[],mtn)

(

inti,j,ml,m2,xl,x2,c,p;

hnodetype*huffnode=newhnodetype[2*n-l];

hcodetype*huffcode=newhcodetype[n],cd;

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

(

huffnode[i].weight=0;

huffnode[i].parent=0;

huffnode[i].flag=0;

huffnode[i].lchild=-l;

huffnode[i].rchild=-l;

)

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

文档仅供参考，不当之处，请联系改正。

huffnode[i].weight=m[i];

huffcode[i].leaf=cha[i];

)

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

(

ml=m2=10000000;

xl=x2=0;

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

(

if

(huffnode[j].weight<=ml&&huffnode[j].flag==0

)

(

m2=ml;

x2=xl;

ml=huffnode[j].weight;

xl=j；

)

else

if(huffnode[j].weight<=m2&&huffnode[j].flag=

=0)

文档仅供参考，不当之处，请联系改正。

m2=huffnode[j].weight;

x2=j;

)

)

huffnode[xl].parent=n+i;

huffnode[x2].parent=n+i;

huffnode[xl].flag=l;

huffnode[x2].flag=l;

huffnode[n+i].weight=huffnode[xl].weight+h

uffnode[x2].weight;

huffnode[n+i].lchild=xl;

huffnode[n+i].rchild=x2;

)

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

(

cd.start=n-l;

c=i;

p=huffnode[c].parent;

while(p!=O)

if(huffnode[p].lchild==c)

文档仅供参考，不当之处，请联系改正。

cd.bit[cd.start]=O;

else

cd.bit[cd.start]=l;

cd.start—;

c=p；

p=huffnode[c].parent;

)

cout«huffcode[i].leaf«

for(j=cd.start+l;j<n;j++)

(

huffcode[i].bit[j]=cd.bit[j];

cout«cd.bit[j];

)

cout«endl;

huffcode[i].start=cd.start;

)

delete[]huffcode;

delete[]huffnode;

)

voidmain()

stringstr;

文档仅供参考，不当之处，请联系改正。

inti=0,j,n,m[100],h,k=0;

charcha[100];

coutvv”请输入一个字符串n«endl;

cin»str;

n=str.length();

cout«n字符串总共有字符n«n«n个

n«endl;

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

(

j=0；

h=0;

while(str[i]!=str[j])

j++；

(

cha[k]=str[i];

cout«"字符"«cha[k]«"出现"；

)

elsecontinue;

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

if(str[i]==str[j])h++;

文档仅供参考，不当之处，请联系改正。

)

cout«h«"次"vvendl;

m[k]=h;

k++;

)

coutvv”每个字符的哈夫曼编码是：n«endl;

huf(cha,m,k);

cin.get();

cin.get();

)

Haffman编码2：

#include<iostream>

usingnamespacestd;

〃********************************〃构造哈

yvAis：尤//不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不/不

哈夫曼树顺序表的定义*/

typedefstruct

intweight;

intparent,lchild,rchild;

)

文档仅供参考，不当之处，请联系改正。

HTNode;

typedefHTNode*HuffmanTree;/*初始化一个

哈夫曼树*/

voidInitHuffmanTree(HuffmaiiTree&HT,int

m)

(

inti;

HT=newHTNode[m];

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

HT[i].weight=O;

HT[i].parent=-l;

HT[i].lchild=-l;

HT[i].rchild=-l;

)

)

//al*a£<»KJA<£•<{>

1t

〃从n个结点中选取最小的两个结点

//«]»»£••£>«]»

1arj»q、rj、rJwrj»rj»rjwrjwrjwrj»rjwrJwrj»rj»rj»rf»rjwrj»乙、*Jwrjwrj—rj»rjwrj*rj»rj»rjfrj»rj>rjw

voidSelectMin(HuffmanTree&HT,intn,int

&minl,int&min2)

文档仅供参考，不当之处，请联系改正。

typedefstruct

(

intNewWeight;〃存储权

intp;〃存储该结点所在的位置

)

TempNode,*TempTree;

TempTreeTT=newTempNode[n];

inti,j;

j=0；

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

(

if(HT[i].parent==-l&&HT[i].weight!=O)

(

TT[j].NewWeight=HT[i].weight;

TT[j].p=i;

j++；

)

}〃将HT中没有双亲的结点存储到TT中

intml,m2;

ml=m2=0;

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

文档仅供参考，不当之处，请联系改正。

if(TT[i].NewWeight<TT[ml].NewWeight)//

此处不让取到相等，是因为结点中有相同权值的

时候，ml取最前的那个。

ml=i;

)

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

(

if(ml==m2)

m2++;〃当ml在第一个位置的时候，m2

向后移一位

if(TT[i].NewWeight<=TT[m2].NewWeight

&&i!=ml)〃此处取到相等，是让在结点中有相

同的权值的时候，〃m2取最后的那个。

m2=i;

)

minl=TT[ml].p;min2=TT[m2].p;

}/*创立哈夫曼树*/

voidCreateHaffmanTree(HuffmanTree&HT,int

n)

(

inti;

intm;

文档仅供参考，不当之处，请联系改正。

intminl9min2;

if(n<=l)

cout«**ParameterError!n;

m=2*n-l;〃哈夫曼树中结点的个数

InitHuffmanTree(HT,m);

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

(

cin»HT[i].weight;

)

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

(

SelectMin(HT,i,minl,min2);

HT[minl].parent=i;

HT[min2].parent=i;

HT[i].lchild=minl;

HT[i].rchild=min2;

HT[i].weight=HT[minl].weight+HT[min2].we

ight;

cout«minl«nn«min2«endl;

)

)

文档仅供参考，不当之处，请联系改正。

哈夫曼编码

〃//芋¥¥7**，*1*¥¥¥*7，**1**¥¥¥<£•*KJ***KY>¥¥<£*¥**KJ>¥<£•¥<£•¥**KY>**!•¥<£¥*K!¥•<?*>**KJ/*/*KJ*哈

夫曼编码的定义*/

typedefstruct

(

charch;

charbits[10];

)

CodeNode;

typedefCodeNode*HuffmanCode;/*哈夫曼编

码的构造*/

voidCreateHuffmanCode(HuffmanTree

&HT,HuffmanCode&HC,intn)

(

inti;

intstart;

intc;

intp;

char*cd;

charq;

HC=newCodeNode[n];

文档仅供参考，不当之处，请联系改正。

cd=newchar[n];

cd[n-l]=70,;

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

(

cin»q;

HC[i].ch=q;

start=n-l;

c=i;

while((p=HT[c].parent)>=0)

(

—start;

cd[start]=(HT[p].lchild==c)?,O*:T;c=p;

)

strcpy(HC[i].bits,&cd[start]);

)

deletecd;

}/*哈夫曼编码的输出*/

voidOutputHuffmanCode(HuffmanCode

&HC,intn)

(

inti;

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

文档仅供参考，不当之处，请联系改正。

cout«HC[i].ch«nn«HC[i].bits«endl;

)

)

voidmain()

(

inti;

coutvv”输入字符个数：”；

cin»i;

HuffmanTreeHT;

HuffmanCodeHC;

CreateHaffmanTree(HT,i);

CreateHuffmanCode(HT,HC,i)；

OutputHuffmanCode(HC,i)；

)

图形着色1：

#include<cstdlib>

#includeviostream>〃回溯法

usingnamespacestd;//judgethecoloration

isValidornot.

boolisValid(boolb[5][5],intk,intx[])

文档仅供参考，不当之处，请联系改正。

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

if(!b[k][i])

continue;

elseif(b[k][i]&&x[k]==x[i])

returnfalse;

returntrue;

}//by:潘乔木

intmain(intargc,char*argv[])

(

intn=5;

血111=3;〃第》个顶点的着色号码(解向量)

intx[5];

boolb[5][5]={true,true,true,false,false,true,

true,true,true,true,true,

true,true,false,true,false,true,false,true,true,false

,true,true,true,true};

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

x[i]=0;

intk=0;//whiles

while(k>=0)

文档仅供参考，不当之处，请联系改正。

x[k]=x[k]+1;〃着色无效继续再当前层

搜索有效的颜色

while(x[k]<=m&&!isValid(b,k,x))

x[k]=x[k]+1;

if(x[k]<=m)

(

if(k==n-l)

break;//successelse

〃为下一个结点着色

k=k+1;

)

else

{〃返回至上一层

x[k]=0;

k=k-1;

)

}//print

cout«"Fivevertexes*colorationschemeis:''

«endl;

for(intj=0;j<5;j++)

cout«x[j]«nn;

cout«endl;

文档仅供参考，不当之处，请联系改正。

system(nPAUSEn);

returnEXITSUCCESS;

)

0」背包回溯法1：

#include<iostream.h>

usingnamespacestd;

template<classTypew,classTypep>

classKnap

(

friendTypep

Knapsack(Typep*,Typew*,Typew,int);

private:

TypepBound(inti);

voidBacktrack(inti);

Typewc;

intn;

Typew*w;

Typep*p;

Typewcw;

Typepcp;

Typepbestp;

文档仅供参考，不当之处，请联系改正。

);

template<classTypew,classTypep>

TypepKnap<Typew,Typep>::Bound(inti)

(

Typewcleft=c-cw;

Typepb=cp;

while(i<=n&&w[i]<=cleft)

(

cleft-=w[i];

b+=p[i]；

i++;

)

if(i<=n)b+=p[i]/w[i]*cleft;

returnb;

)

template<classTypew,classTypep>

voidKnap<Typew,Typep>::Backtrack(inti)

(

if(i>n)

(

bestp=cp;

return;

文档仅供参考，不当之处，请联系改正。

)

if(cw+w[i]<=c)

(

cw+=w[i];

cp+=p[i];

Backtrack(i+1);

cw-=w[i];

cp-=p[i];

)

if(Bound(i+l)>bestp)

Backtrack(i+1);

)

classObject

(

friendintKnapsack(int*,mt

public:

intoperator<=(Objecta)const

|

return(d>=a.d);

)

private:

intID;

文档仅供参考，不当之处，请联系改正。

floatd;

template<classTypew,classTypep>

(

TypepW=0;

TypepP=0;

Object*Q=newObject[n];

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

|

Q[i-l].ID=i;

Q[i-l].d=1.0*p[i]/w[i];

P+=p[i]；

W+=w[i];

)

if(W<=c)returnP;

sort(Q,n);

Knap<Typew,Typep>K;

K.p=newTypep[n+1];

K.w=newTypew[n+1];

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

K.p[i]=p[Q[i-l].ID];

文档仅供参考，不当之处，请联系改正。

K.w[i]=w[Q[i-l].ID];

)

K.cp=O;

K.cw=O;

K.c=c;

K.n=n;

K.bestp=O;

K.Backtrack(l);

delete[]Q;

delete[]K.w;

delete[]K.p;

returnK.bestp;

)；

intmainO

(

intp[]={0,4,3,5,6,3);

intw[]={0,3,5,6,2,7);

int*pl=p;

int*wl=w;

intc=10,n=5;

intbestx[6];

intx=Knapsack(p1,wl,c,n);

文档仅供参考，不当之处，请联系改正。

cout«nbest=''«c«endl;

for(inti=0;i<6,i++)

(

cout«bestx[i];

)

cout«nResultn;

return0;

)

0-1背包动态规划法：

#include<iostream>

#include<fstream>

#include<memory.h>

usingnamespacestd;

intmax(inti,intj)

(

returni>j?i:j;

)

intmin(inti,intj)

(

returni<j?i:j;

)

文档仅供参考，不当之处，请联系改正。

template<classType>

voidKnapsack(Type*v,int*w,intc,intn,Type

**m)

(

//0-1背包算法

intjMax=min(w[ii]-l,c);

for(intj=O;j<=jMax;j++)

(

m[n][j]=0;

)

for(intt=w[n];t<=c;j++)

(

m[n][t]=v[n];

)

for(inti=n-l;i>l;i-)

(

jMax=min(w[i]-l,c);

for(intj=O;j<=jMax;j++)

for(intk=w[i];j<=c;j++)

m[i][k]=max(m[i+l][k],m[i+l][k-w[i]]+v[i]);

文档仅供参考，不当之处，请联系改正。

)

m[l][c]=m[2][c];

if(c>=w[l])

m[l][c]=max(m[l][c],m[2][c-w[l]]+v[l]);

)

template<classType>

voidTraceBack(Type**m,int*w,intc,intn,int*

x)

{

〃计算04背包路径

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

(

if(m[i][c]==m[i+l][c])

x[i]=0;

else

(

x[i]=l；

c-=w[i];

)

)

x[n]=(m[n][c])?l:0;

)

文档仅供参考，不当之处，请联系改正。

voidmain()

(

//物品量n,承载重量c,各物体重量：w,各

物体价值：v〃m用来存储动态规划的子结构值

intn,c,i；

int*w,*v,*x;

int**m;

ifstreaminput('*Input.txtH,ios::in);

ofstreamoutput(nOutput.txtn,ios::out);

if(!input||!output)

(

cerr«nFi!eopenorcreateerror!n«endl;

exit(O);

)

else

(

input»n»c;

w=newint[n+l];

v=newint[n+l];

x=newint[n+l];

m=newint*[n+l];

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

文档仅供参考，不当之处，请联系改正。

m[i]=newint[c+l];

memset(m[i],0,(c+l)*sizeof(int));

}

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

input»w[i];

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

input»v[i];

input.closeQ;

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

for(intj=O;j<c+l;j++)

m[i][j]=0;

Knapsack(v,w,c,n,m);

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

(

for(intk=0;k<=c;k++)

output«m[i][k]«nH;

output«endl;

)

output«endl;

TraceBack(m,w,c,n,x);

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

文档仅供参考，不当之处，请联系改正。

output«x[i]«n

output,close。;〃回收内存

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

delete[]m[i];

delete[]w;

delete[]v;

delete[]x;

delete[]m;

)

)

0」背包回溯法2：

#include<iostream>

usingnamespacestd;

voidinput(int"number,int.weight,int*price)

(

inti,n;

coutvv”包的容量:H;

cin»weight[0];

coutvv”物品数：H;

cin»*number;

coutvv”各物品的重量：n;

文档仅供参考，不当之处，请联系改正。

for(i=l;i<=*number;i++)

(

cin»weight[i];

)

coutvv”各物品的价值:n;

for(i=l;i<=*number;i++)

(

cin»price[i];

)

)

voidbacktrack(intt,intn,int.weight,int

*price,int*maxPrice,int*flag,int

*nowWeight,int*nowPrice,int*x)

(

inti;

if(t>n)

(

if(*nowWeight<=weight[0]&&*nowPrice>*m

axPrice)

//cout«nmaxPriceis

文档仅供参考，不当之处，请联系改正。

**«*maxPrice«11nowPriceis

n«*nowPrice«endl«endl;

*maxPrice=*nowPrice;

flag[0]=0;

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

(

if(x[i])

|

//coutvv”深度是：”Wtvv"i是

n«i«endl«endl;

flag[++flag[O]]=i;

)

)

)

return;

)

else

(

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

(

x[t]=i;

*nowWeight+=weight[t]*i;

文档仅供参考，不当之处，请联系改正。

*nowPrice+=price[t]*i;

//cout«11nowPriceisn«*nowPrice«n

深度是:n«t«nx[n«t«n]是:n«i«endl;

backtrack(t+l,n,weight,price,maxPrice,flag,n

owWeight,nowPrice,x);

*nowWeight-=weight[t]*i;

*nowPrice-=price[t]*i;

)

)

)

voidoutput(int*maxPrice,int*flag)

(

inti;

cout«endl;

cout«''最大价值:H;

cout«*maxPrice«endl;

cout«”所选物品为:''；

for(i=l;i<=flag[0];i++)

(

cout«flag[i]«nn;

)

文档仅供参考，不当之处，请联系改正。

cout«endl;

)

intmain()

(

inttempl=0,temp2=-l,temp3=0,temp4=0;〃这

一行很重要!!!!!!!！

int*number=&templ,weight[100],price[100];

int

*maxPrice=&temp2,flag[100],*nowWeight=&te

mp3,*nowPrice=&temp4,x[100];

input(number,weight,price);

backtrack(l,*number,weight,price,maxPrice,f

lag,nowWeight,nowPrice,x);

output(maxPrice,flag);

return0;

)

最小生成树prim法1：

#include<string>

#include<iostream>

usingnamespacestd;

structMGraph

文档仅供参考，不当之处，请联系改正。

voidcreateGraph(intn,intm);

intPrim(intu);

intmat[100][100];//弧的信息

intvexnum;//顶点数

intMinVertex(intdist[],boolvisited[]);

)；

intMGraph::Prim(intu)

{〃从顶点u出发构造网的从顶点最小生成

树

intadjvex[100];

intdist[100];

boolvisited[100];

inti;//辅助数组初始化

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

(

adjvex[i]=u;

dist[i]=mat[u][i];

)

fill(visited,visited+vexnum,false);

visited[u]=true;//初始，U={u}初始，=

for(intv=l;v<=vexnum-l;v++)

文档仅供参考，不当之处，请联系改正。

//选择vexnum-1个顶点边)个顶点(边

intk=MinVertex(dist,visited);//加入生成

树的下一个顶点(k)

visited[k]=true;〃新节点加入集合

U

//调整集合V-U中剩余顶点到集合U的

最短距离

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

(

if(visited[i]==false&&mat[k][i]<dist[i])

(

adjvex[i]=k;

dist[i]=mat[k][i];

)

)

)

intcost=0;

dist[u]=0;

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

文档仅供参考，不当之处，请联系改正。

cost+=dist[i];

)

returncost;

}//寻找V-U中未被访问，且dist最小的顶点

中未被访问，

intMGraph::MinVertex(intdist[],boolvisited[])

(

intk=-1;

intmin=INTMAX;

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

(

if(dist[i]<min&&visited[i]==false)

(

min=dist[i];

k=i;

)

)

returnk;

)

voidMGraph::createGraph(intn,intm)

vexnum=n;

文档仅供参考，不当之处，请联系改正。

for(intv=0;v<vexnum;v++)

(

for(intw=0;w<vexnum;w++)

(

mat[v][w]=INT_MAX;

)

)

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

(

inta,b,c;

cin»a»b»c;

mat[a][b]=c;

mat[b][a]=c;

)

)

intmain。//个顶点(边〃选择vexnum」个顶

点边)

(

MGraphG;

intn,m;

cin»n»m;

G.createGraph(n,m);

文档仅供参考，不当之处，请联系改正。

cout«G.Prim(0)«endl;

return0;

)

最小生成树kruskal法1：

//#includenstdafx.hn

#include<iostream>

#defineMAX100

typedefintWeiType;

usingnamespacestd;//

structEdge

(

intno;〃边的序号

intx;〃端点1序号

inty;//端点2序号

WeiTypeweight;〃权值

boolselected;〃是否被选择

｝；〃边集和

Edgeedge[MAX];〃已找到的最小生成树其中一

部分的秩

intrank[MAX];〃已找到的最小生成树其中一部

分的头结点〃用来判断一条边的2个端点是否在

文档仅供参考，不当之处，请联系改正。

一个集合中，即加上这条边是否会形成回路

intparent[MAX];〃找出每一集合的头结点

intfind_set(intx)

(

if(x!=parent[x])

parent[x]=find_set(parent[x]);

returnparent[x];

}〃合并集合

voidunion_set(intx,inty,WeiTypew,WeiType

&sum)

(

if(x==y)

return;

if(rank[x]>rank[y])

parent[y]=x;

else

(

if(rank[x]==rank[y])

rank[y]++;

parent[x]=y;

)

sum+=w;

文档仅供参考，不当之处，请联系改正。

}〃依据边的权值升序快速排序

voidfast_sort(Edge*edge,intbegin,intend)

(

if(begin<end)

(

inti=begin-lj=begin;

edge[0]=edge[end];

while(j<end)

(

if(edge[j].weight<edge[O].weight)

(

i++；

Edgetempi=edge[i];

edge[i]=edge[j];

edge[j]=tempi;

)

j++；

)

Edgetempi=edge[end];

edge[end]=edge[i+l];

edge[i+l]=temp2;

fast_sort(edge,begin,i)；

文档仅供参考，不当之处，请联系改正。

fast_sort(edge,i+2,end);

)

)

intmain(intargc,char*argv[])

(

intcases;

coutvv”请输入案例的个数：”；

cin»cases;

while(cases—)

(

intn;〃最小生成树的权值总和

WeiTypesum=0;

cout«”请输入边的个数：”；

cin»n;

inti;〃初始化

charchx,chy;

WeiTypeweight;

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

(

edge[i].no=i;

coutvv”请输入第”VViVV”条边的二个端

点的名称(小写字符)：”；

文档仅供参考，不当之处，请联系改正。

cin»chx»chy;

edge[i].x=chx-'a，+l;

edge[i].y=chy-'a'+l;

coutvv”这条边的权值为：”;

cin»weight;

edge[i].weight=weight;

edge[i].selected=false;

parent[edge[i].x]=edge[i].x;

parent[edge[i].y]=edge[i].y;

rank[edge[i].x]=0;

rank[edge[i].y]=0;

)〃快排

fast_sort(edge,l?n);

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

(

intx,y;

x=find_set(edge[i].x);

y=find_set(edge[i].y);〃判断即加上

这条边是否会形成回路

if(x!=y)

〃选择这条边

文档仅供参考，不当之处，请联系改正。

edge[i].selected=true;

〃合并不会形成回路的二个集合

union_set(x,y9edge[i].weight,sum);

)

)

coutvv”最小生成树的边集为："vvendl;

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

(

if(edge[i].selected)

(

coutvv”序号：n«edge[i].no«n''

vv"端点1："vv(char)(edge[i].x+'aLl)vv”,端点

2：n«(char)(edge[i].y+*a,-l)«endl;

)

)

cout«n最小生成树的权值为：

H«sum«endl;

)

system(npausen);

return0;

)

文档仅供参考，不当之处，请联系改正。

最小生成树prim法2：

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#defineMAX_N