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

《2020年计算机算法设计与分析课程设计常规题目的C及C代码集.docx》由会员分享，可在线阅读，更多相关《2020年计算机算法设计与分析课程设计常规题目的C及C代码集.docx（138页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算法设计与分析课程设计常规 题目的C及C代码集#includeusing namespace std;const int N=100;class list(public:int arrayN;void input(int a);void merge(int arrayc,int arrayd,int l,int m,int r);void mergepass(int arrayx,int arrayy,int s);void mergesort(int arrayl);void diaplay(int a);)；void list:input(int a)coutnPlease inpu

2、t shorted array:Hendl;for(int i=0;ia;i+)cinarrayi;)void list:merge(int arrayc,int arrayd,int l,int m,int r)(int i=l;int j=m+l;int k=l;while(i=m)&(j=r)if(arraycim)for(int q=j;q=r;q+)arraydk+=arraycq;elsefor(int q=i;q=m;q+) arraydk+=arraycq;void list:mergepass(int arrayx,int arrayy,ints)int i=0;while(

3、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,array y,i,i+s-1 ,N-1);elsefor(int j=i;jN;j+) arrayyj=arrayxj;)void list: :mergesort(int array 1)(int array2N;int s=l;while(sN)(mergepass(array 1,array 2,s);s+=s;mergepass(array2,arrayl,s);s+=s;)void list:diaplay(int a)for(in

4、t i=N-a;iN;i+) coutarrayi;)void main()(list f;int a;COUtV请输入要合并排序的数组大小:(数 组最大上限100)”vvendl;cina;f.input(a);f.mergesort (f.array);f.diaplay (a);合并排序:2#include usingnamespace std;void MERGES(int *A,int p,int q,int r) 下标P=qrint nl=q-p+l; /nl:p,q之间的数的个数int n2=r-q; /n2： q以后到r的数的个数int *L=newint nl+1,动态申请两

5、个子数组*R=newint n2+l；int ij,k;for (i=0;inl;i+)Li=Ap+i-l;)for (j=0;jn2;j+)RLj=Aq+j;)Lnl=10000; 设置哨兵Rn2=10000;i=0;j=0；for (k=p-l;kr;k+)if (Li=Rj)(Ak=Li;i=i+l;else(Ak=Rj;j=j+l；void MERGESORT(int *A,int p,int r) if (pr)(int q=(p+r)/2;MERGESORT(A,p,q);MERGESORT(A,q+l,r);MERGES(A,p,q,r);void main()int x,z,p

6、,r;coutvv”请输入数组长度” vvendl;cinx;int *A= newintx;coutv v ”请输入数组的元素“v vendl;for(int y=0；yx;y+)(cinz;Ay=z;)coutvv”请输入上下限p, rMendl;cinpr;MERGESORT(A,p,r);coutvv ”合并排序后为:vVendl;for (int m=p;m=r;m+)coutAm;delete A;合并排序3：#include #include 这个函数将 b至 bright-Ieft+l拷贝到 aleft至 arighttemplate void Copy(T a,T b,int

7、 left,int right)(int size=right-left+l;for(int i=O;isize;i+)(aleft+=bi;) 这个函数合并有序数组aleft:i,ai+l:right到b,得到新的有序数组b template void Merge(T a,T b,int left,int i,int right)int alcout=left指向第一个数组开头 alend=i指向第一个数组结尾 a2colit=i+l, 指向第二个数组开头 a2end=right, 指向第二个数组结尾bcout=0;指向b中的元素for(int j=O;jalend) bbcout+=aa2

8、cout+;continue;如果第一个数组结束,拷贝第二个数组的 元素到bif(a2couta2end)(bbcout+=aalcout+;continue;如果第二个数组结束,拷贝第一个数组的 元素到bif(aalcoutaa2cout)(bbcout+=aalcout+； continue;如果两个数组都没结束,比较元素大小, 把较小的放入belsebbcout+=aa2cout+； continue;)对数组aleft:right进行合并排序template void MergeSort(T a,int left,int right)T *b=new intright-left+l；i

9、f(leftright)(int i=(left+right)/2;取中点MergeSort(a,left,i); 左半边进行合并排序MergeSort(a,i+1,right); 右半边进行合并排序Merge(a,bjeft,i,righ;左右合并到 b 中 Copy(a,b,left,righ;从 b 拷贝回来 /fromint main()int n;coutnhow many numbers to sort:*;cinn;int *a=new intn;coutninput nn numbers:H;for(int i=0;in;i+)(cinai;)MergeSort( a, 0,

10、n-1);for(int j=O;jn;j+)(coutsetw(5)aj;)return 1;)合并排序4：#include using namespace std;void Merge(int a,int b,int IJnt m,int r)int i=l,j=m+l,k=l;while (i=m)&(j=r)if (aim)for(int q=j;q=r;q+) bk+=aq;elsefor(int q=i;q=m;q+) bk+=aq;)void Copy(int a,int b,int s,int n)for(int i=s;i=n;i+)ai=bi;)void MergeSort

11、(int a,int left,int right)int i;if(leftright)i=(left+right)/2;intb100;MergeSort(a,left,i);MergeSort(a,i+l,right);Merge(a,b,left,i,right);Copy(a,b,left,right);)int main()(int a100;int n,i;coutvv”输入元素个数n:M;cinn;coutvv”输入维数组 aHnH:M;for( i=0;in;i+)cinai;MergeSort(a,0,n-l);coutvv”输出排序为:;for (i=0;in;i+)co

12、utai* *;coutendl;return 0;矩阵相乘1：#include #include using namespace std;int main()int i,j, k;coutvv”输入二维数组a的行数和二维数组c 的行数X：；int x;cinx;coutv输入二维数组a的列数和二维数组b 的行数y：;int y;ciny;coutv输入二维数组b的列数和二维数组C 的行数Z：；int z;cinz;endl;endl;a=new int*x;for(i=0;ix;i+)(ai=new inty;coutvv”输入二维数组a:for(i=0;ix;i+)(for(j=0;jy;

13、j+)(cinaij;)b=new int*y;for(i=0;iy;i+)(bi=new int z;)coutvv”输入二维数组b:for(i=0;iy;i+)for(j=0;jz;j+)(cinbij;)c=new int*x;for(i=0;ix;i+)(ci=new int z;)coutvv”输入二维数组 c:nendl;for(i=0;ix;i+)(for(j=0;jz;j+)cij=O；)for(i=0;ix;i+)for(j=0;jz;j+)for(k=0;ky;k+)cij+=aik*bkj;)for(i=0;ix;i+)(for(j=0;jz;j+)(coutcij, *

14、;coutendl;for(i=0;ix;i+)(delete ai;)delete a;for(i=0;ix;i+)delete ci;delete c;for(i=0;iy;i+)(delete bi;delete b;return 0;矩阵相乘2：#includeusing namespace std;#define M 2#define N 3#define P 4int main()int aMN=l,2,3,4,5,6);intbNP=7,8,9,l,2,3,4,5,6,7,8,9);int cMP;int ij,k;for(i=0;iM;i+)for(j=0;jP;j+)ciU=

15、O；for(i=0;iM;i+)for(j=0;jP;j+)for(k=0;kN;k+)cij+=aik*bkj;coutvv”矩阵相乘结果是:Mendl;for(i=0;iM;i+)for(j=0;jP;j+) coutcijn H;coutendl;/sy stem( * * pause * *);return 0;矩阵相乘3：#include #include using namespace std;int main()const int m=3;const int n=3;int初始化数组 a,bfor(i=0;ivm;i+) 对数组a赋值并显示(for( j=O;jn;j+)cout

16、naniHnnnjn=H; cinaij;)for( i=0;im;i+)(for( j=O;jn;j+)coutsetw(4)aij;coutendl;)const int k=3;const int h=2;int bkh,x,y;for( x=0;xk;x+)for( y=0;yh;y+)coutnbnxnnHnyH=H; cinbxy;)for( x=O;xk;x+)(for( y=O;yh;y+)coutsetw(4)bxy;coutendl;int乘赋值给数组cfor(int r=O;rm;r+)for(int t=O;th;t+) 数组 a 与 b 相对 数组b赋值并显示(crt

17、=O;for(int s=O;sk;s+)crt+=ars*bst;coutnc,mH,nHhnnendl;for(int z=O;zm;z+)(for(int w=O;wh;w+)coutsetw(4)cz w;coutendl;return ;显示数组c矩阵相乘4：#includeusing namespace std;void chain(int*p,int n,int m7,int s7)/p 维数数组,m最优乘次数组,s记录划分方案int j;for(int i=l;i=n;i+)mii=0;for(int r=2;r=n;r+)for(i=l ;i=n-r+l ;i+)(j=i+r

18、-l;mij=mi+lj+pi-l*pi*pj;sij=i；for(int k=i+l;kj;k+)(intt=mik+mk+lj+pi-l*pk*pj;if(t=i;j-)coutmijM;coutendl;void Traceback(int ijnt j,int s7)输出相乘方if(i=j)return;Traceback(i,sij,s);Traceback(si j+lj,s);coutvvMultiply Ai,sij;coutand B(sij+l),jendl;return;)int main()int p7,m77,s77,n;while(n!=EOF)for(int i=

19、0;i=n;i+)cinpiendl;chain(p,n,m,s);Traceback(l,6,s);)return 0;Haffman 编码 !：#include#include using namespace std;typedef structint weight;int flag;int parent;int Ichild;int rchild;hnodetype;typedef structint bit10;int start;char leaf;hcodetype;void huf(char cha,int m,int n)int ij,ml,m2,xl,x2,c,p;hnode

20、type *huffnode=new hnodetype2*n-l;hcodetype *huffcode=new hcodetypen,cd;for(i=0;i2*n-l ;i+)huffnodei.weight=0;huffnodei.parent=0;huffnodei.flag=0;huffnodei.lchild=-l;huffnodei.rchild=-l;for(i=0;in;i+)huffnodei.weight=mi;huffcodei.leaf=chai;)for(i=0;in-l;i+)(ml=m2=10000000;xl=x2=0;for(j=0;jn+i;j+)(if

21、(huffnodej.weight=ml&huffnodej.flag=0)m2=ml;x2=xl;ml=huffnodej.weight;xl=j； elseif(huffnodej.weight=m2&huffnodej.flag=0)m2=huffnodej.weight; x2=j;)huffnodexl.parent=n+i;huffnodex2.parent=n+i； huffnodexl.flag=l;huffnodex2.flag=l;huffnoden+i.weight=huffnodexl.weight+huffnodex2.weight;huffnoden+i.lchil

22、d=xl;huffnoden+i.rchild=x2;for(i=0;in;i+)(cd.start=n-l;c=i;p=huffnodec.parent;while(p!=O)if(huffnodep.lchild=c)cd.bitcd.start=O;elsecd.bitcd.start=l;cd.start;c=P；p=huffnodec.parent;)couthuffcodei.leafH:H;for(j=cd.start+l ；jn;j+)(huffcodei.bitj=cd.bitj; coutcd.bitj;)coutendl;huffcodei.start=cd.start;

23、delete huffcode;delete huffnode;)void main()string str;int i=0J,n,m100,h,k=0;char cha100;coutv请输入一个字符串“ vvendl;cinstr;n=str.length();coutH字符串总共有字符nnM个Hendl;for(i=0;in;i+)(j=0;h=0;while(stri !=strj)j+；if(j=i)(chak=stri;cout v V”字符 y chakv v出现;)else continue;for(j=i;jn;j+)if(stri=strj)h+;)coutvvhvv次vv

24、endl;mk=h;k+;)coutvv”每个字符的哈夫曼编码是:endl;huf(cha,m,k);cin.get();cin.get();Haffman 编码 2：#include using namespace std;* 构 造 哈I * -2 *2* *2* 2 *2* *2* *2*2* *2* ，*!*哈夫曼树顺序表的定义/typedef struct(int weight;int parent,lchild,rchild;HTNode;typedef HTNode * HuffmanTree;/*初始化一个 哈夫曼树号void InitHuffmanTree(HuffmanTr

25、ee &HT,int m)HT=new HTNodem;for(i=0;im;i+)HTi.weight=O;HTi.parent=-l;HTi.lchild=-l;HTi.rchild=l;/ /.a 1 J *J *J *jw *Jw *jw *J* *J rjrjrjw jw rjw jw rjw *Jw *jw jw rjw *jw *jw *jw jw *j* *jw rjw Jw *jw *Jw jw *jw从n个结点中选取最小的两个结点/ /. * Y4r J *J* *J *Jw rjw rj Jw rjw Jw *jw Jw J Jw r|w rjw rjw *Jw rj *

26、j J*|w rJ rj*jw *Jwrjw rjw rJ*jwvoid SelectMin(HuffmanTree &HT,int n,int &minl9int &min2)typedef struct(int NewWeight;存储权intp; 存储该结点所在的位置TempNode,*TempTree;TempTree TT=new TempNoden;int ij;j=0；for(i=0;in;i+)(if(HTi.parent=-l & HTi.weight!=O)(TTj.NewWeight=HTi.weight;TTj.p=i;j+；)将HT中没有双亲的结点存储到TT中int

27、ml,m2;ml=m2=0;for(i=0;ij;i+)if(TTi.NewWeightTTml.NewWeight)/ 此处不让取到相等,是因为结点中有相同权值的 时候,ml取最前的那个。ml=i;for(i=0;ij;i+)(m2)m2+;当m!在第一个位置的时候,m2 向后移一位if(TTi.NewWeight=TTm2.NewWeight & i!=ml)此处取到相等,是让在结点中有相 同的权值的时候,m2取最后的那个。m2=i;)minl=TTml.p;min2=TTm2.p;创立哈夫曼树/void CreateHaffmanTree(HuffmanTree &HT,int n)(i

28、nt i;int m;int mini,mini;if(n=l)cout,1 Parameter Error!;m=2*n-l;哈夫曼树中结点的个数InitHuffmanTree(HT,m);for(i=0;in;i+)(cinHTi.weight;for(i=n;im;i+)(SelectMin(HT,i,mini,mini);HTminl.parent=i;HTmin2.parent=i;HTi.lchild=minl;HTi.rchild=min2;HTi.weight=HTminl.weight+HTmin2.we ight;coutminl min2endl;哈 夫 曼 编 码/，

29、，I1XX,J 1 *J* *jw *Jw rjw rj jw rjw Jw *jw jw J Jw rJ *jw J *jw rJ rjw *jw*Jw jw rjw rj rj *Jwrjw rjw t *jw.夫曼编码的定义/typedef struct(char ch;char bits10;CodeNode;typedef CodeNode * HuffmanCode;/哈夫曼编 码的构造/void CreateHuffmanCode(HuffmanTree&HT,HuffmanCode &HC,int n)int i;int start;int c;int p;char *cd;c

30、har q;HC=new CodeNoden;cd=new charn;cdn-l=70,;for(i=0;i=0)(-start;cdstart=(HTp.lchild=c)?,O,:*l,;c=p;)strcpy(HCi.bits,&cdstart);)delete cd;/哈夫曼编码的输出/void OutputHuffmanCode(HuffmanCode&HC,int n)(int i;for(i=0;in;i+)coutHCi.chn HCi.bitsendl;void main()(int i;coutv输入字符个数:“；cini;HuffmanTree HT;HuffmanCo

31、de HC;CreateHaffmanTree(HT,i)； CreateHuffmanCode(HT,HC,i);OutputHuffmanCode(HC,i);图形着色1：#include #include viostream回溯法using namespace std;/judge the coloration isValid or not.bool isValid(bool b55, int k, int x)for(int i=0; ik; +i)if(!bki)continue;else if(bki & xk= xi)return false;return true;/by :潘

32、乔木int main(int argc, char *argv)int n = 5;intm = 3;第i个顶点的着色号码(解向量)int x5;bool b55= 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(int i=0; i=0)xk = xk + 1;着色无效继续再当前层 搜索有效的颜色while(xk=m & !isValid(b, k, x)xk = xk

33、 + 1;if(xk=m)(if(k=n-l)break; /successelse为下个结点着色k = k+1;)else( 返回至上一层xk = 0;k = k-1;)/printcout ”Five vertexes* coloration scheme is: * endl;for(int j=0; j5; j+)cout xj * *;cout endl;system(HPAUSEH);return EXIT SUCCESS;)0-1背包回溯法1：#includeusing namespace std;templateclass Knap(TypepfriendKnapsack(Ty

34、pep*,Typew*,Typew,int);private:Typep Bound(int i);void Backtrack(int i);Typew c;int n;Typew *w;Typep *p;Typew cw;Typep cp;Typep bestp;);templateTypep Knap: :Bound(int i)(Typew cleft=c-cw;Typep b=cp;while(i=n& & wi=cleft)(cleft-=wi;b+=pi；i+；)if(i=n)b+=pi/wi*cleft;return b;)templatevoid Knap:Backtrack

35、(int i)if(in)bestp=cp;return;if(cw+wibestp)Backtrack(i+1)；)class Objectfriend int Knapsack(int *,mtpublic:int operator=a.d);)private:int ID;float d;template (Typep W=0;Typep P=0;Object*Q=new Objectn;for(int i=l;i=n;i+)(Qi-l.ID=i;Qi-l.d=1.0*pi/wi;P+=pi；W+=wi;if(W=c)return P;sort(Q,n);KnapK;K.p=new Ty

36、pepn+1;K.w=new Typewn+1； for(int i=l;i=n;i+)K.pi=pQi-l.ID;K.wi=wQi-l.ID;)K.cp=O;K.cw=O;K.c=c;K.n=n;K.bestp=O;K.Backtrack(l);deleteQ;deleteK.w;deleteK.p;return K.bestp;)；int main()int p=0,4,3,5,6,3);int w0,3,5,6,2,7;int *pl=p;int *wl=w;int c=10,n=5;int bestx6;int x=Knapsack(pl,wl,c,n);coutnbest=Hcendl; for(int i=0;i6,i+)(coutbestxi;coutH ResultH;return 0;)0-1背包动态规划法: #include #include #include using namespace std; int max(int i,int j) re