计算机算法设计与分析专业课程设计常规题目的C及C代码集.doc

合并排序1：#include using 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 array1); void diaplay(int a); ;void list:input(int a) coutPlease input shorted array:endl; for(int i=0;iarrayi; void list:merge(int arrayc,int arrayd,int l,int m,int r) int i=l; int j=m+1; 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,int s) int i=0; while(i=N-2*s) merge(arrayx,arrayy,i,i+s-1,i+2*s-1); i=i+2*s; if(i+s)N) merge(arrayx,arrayy,i,i+s-1,N-1); else for(int j=i;jN;j+) arrayyj=arrayxj; void list:mergesort(int array1)int array2N; int s=1; while(sN)mergepass(array1,array2,s); s+=s; mergepass(array2,array1,s); s+=s; void list:diaplay(int a)for(int i=N-a;iN;i+) coutarrayi; void main() list f; int a; cout请输入要合并排序数组大小：(数组最大上限 100)a; 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 n1=q-p+1; /n1:p,q之间数个数 int n2=r-q; /n2：q以后到r数个数 int *L=newint n1+1, /动态申请两个子数组 *R=newint n2+1; int i,j,k; for (i=0;in1;i+) Li=Ap+i-1; for (j=0;jn2;j+) Rj=Aq+j; Ln1=10000; /设置哨兵 Rn2=10000; i=0; j=0; for (k=p-1;kr;k+) if (Li=Rj) Ak=Li; i=i+1; else Ak=Rj; j=j+1; void MERGESORT(int *A,int p,int r)if (pr) int q=(p+r)/2; MERGESORT(A,p,q); MERGESORT(A,q+1,r); MERGES(A,p,q,r); void main()int x,z,p,r; cout请输入数组长度x;int *A= newintx; cout请输入数组元素endl;for(int y=0;yz; Ay=z; cout请输入上下限p，rpr; MERGESORT(A,p,r); cout合并排序后为：endl; for (int m=p;m=r;m+) coutAm; delete A;合并排序3：#include #include /这个函数将b0至bright-left+1拷贝到aleft至aright template void Copy(T a,T b,int left,int right) int size=right-left+1; for(int i=0;isize;i+) aleft+=bi; /这个函数合并有序数组aleft:i,ai+1:right到b,得到新有序数组b template void Merge(T a,T b,int left,int i,int right) int a1cout=left,/指向第一个数组开头 a1end=i,/指向第一个数组结尾 a2cout=i+1,/指向第二个数组开头 a2end=right,/指向第二个数组结尾 bcout=0;/指向b中元素 for(int j=0;ja1end)bbcout+=aa2cout+;continue;/假如第一个数组结束，拷贝第二个数组元素到b if(a2couta2end)bbcout+=aa1cout+;continue;/假如第二个数组结束，拷贝第一个数组元素到b if(aa1coutaa2cout)bbcout+=aa1cout+;continue;/假如两个数组全部没结束，比较元素大小，把较小放入b else bbcout+=aa2cout+;continue; /对数组aleft:right进行合并排序 template void MergeSort(T a,int left,int right) T *b=new intright-left+1; if(leftright) int i=(left+right)/2;/取中点 MergeSort(a,left,i);/左半边进行合并排序 MergeSort(a,i+1,right);/右半边进行合并排序 Merge(a,b,left,i,right);/左右合并到b中 Copy(a,b,left,right);/从b拷贝回来 /from int main() int n; coutn; int *a=new intn; coutinput n numbers:; for(int i=0;iai; MergeSort( a, 0, n-1); for(int j=0;jn;j+) coutsetw(5)aj; return 1;合并排序4：#include using namespace std;void Merge(int a,int b,int l,int m,int r)int i=l,j=m+1,k=l;while (i=m)&(j=r)if (aim)for(int q=j;q=r;q+)bk+=aq;else for(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(int a,int left,int right)int i;if(leftright)i=(left+right)/2;int b100;MergeSort(a,left,i);MergeSort(a,i+1,right);Merge(a,b,left,i,right);Copy(a,b,left,right);int main()int a100;int n,i;coutn;cout输入一维数组an:;for( i=0;iai;MergeSort(a,0,n-1);cout输出排序为:;for ( i=0;in;i+)coutai ;coutendl;return 0; 矩阵相乘1:#include #include using namespace std;int main()int i, j, k;coutx;couty;coutz;int *a, *b, *c;a=new int*x;for(i=0;ix;i+)ai=new inty;cout输入二维数组a:endl;for(i=0;ix;i+) for(j=0;jaij;b=new int*y;for(i=0;iy;i+)bi=new int z;cout输入二维数组b:endl;for(i=0;iy;i+)for(j=0;jbij; c=new int*x;for(i=0;ix;i+)ci=new int z;cout输入二维数组c:endl;for(i=0;ix;i+) for(j=0;jz;j+)cij=0; 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 ;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=1,2,3,4,5,6;int bNP=7,8,9,1,2,3,4,5,6,7,8,9;int cMP;int i,j,k;for(i=0;iM;i+)for(j=0;jP;j+)cij=0;for(i=0;iM;i+)for(j=0;jP;j+)for(k=0;kN;k+)cij+=aik*bkj;cout矩阵相乘结果是：endl;for(i=0;iM;i+)for(j=0;jP;j+)coutcij ;coutendl;/system(pause);return 0; 矩阵相乘3：#include #include using namespace std; int main() const int m=3;const int n=3;int amn,i,j; /初始化数组 a,b for(i=0;im;i+) /对数组 a 赋值并显示 for( j=0;jn;j+) coutaijaij; for( i=0;im;i+)for( j=0;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+) coutbxybxy;for( x=0;xk;x+) for( y=0;yh;y+) coutsetw(4)bxy; coutendl; int cmh; /乘赋值给数组 cfor(int r=0;rm;r+)for(int t=0;th;t+) /数组 a 和 b 相/对数组 b 赋值并显示crt=0; for(int s=0;sk;s+)crt+=ars*bst; coutcmhendl;for(int z=0;zm;z+) for(int w=0;wh;w+)coutsetw(4)czw; coutendl;return 0; /显示数组 c 矩阵相乘4：#includeusing namespace std;void chain(int*p,int n,int m7,int s7)/p维数数组，m最优乘次数组，s统计划分方案int j;for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(i=1;i=n-r+1;i+)j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;for(i=1;i=i;j-)coutmij;coutendl;void Traceback(int i,int j,int s7)/输出相乘方案if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply Ai,sij;coutand B(sij+1),jendl;return;int main()int p7,m77,s77,n;while(n!=EOF)for(int i=0;ipiendl;chain(p,n,m,s);Traceback(1,6,s);return 0; Haffman编码1：#include #includeusing namespace std;typedef struct int weight;int flag;int parent; int lchild; int rchild; hnodetype;typedef struct int bit10; int start;char leaf; hcodetype;void huf(char cha,int m,int n)int i,j,m1,m2,x1,x2,c,p;hnodetype *huffnode=new hnodetype2*n-1;hcodetype *huffcode=new hcodetypen,cd;for(i=0;i2*n-1;i+) huffnodei.weight=0;huffnodei.parent=0;huffnodei.flag=0;huffnodei.lchild=-1;huffnodei.rchild=-1;for(i=0;in;i+)huffnodei.weight=mi;huffcodei.leaf=chai; for(i=0;in-1;i+)m1=m2=10000000;x1=x2=0;for(j=0;jn+i;j+)if (huffnodej.weight=m1&huffnodej.flag=0)m2=m1; x2=x1; m1=huffnodej.weight; x1=j; else if(huffnodej.weight=m2&huffnodej.flag=0) m2=huffnodej.weight; x2=j;huffnodex1.parent=n+i;huffnodex2.parent=n+i;huffnodex1.flag=1;huffnodex2.flag=1;huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; huffnoden+i.rchild=x2;for(i=0;in;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=0) if(huffnodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-;c=p;p=huffnodec.parent; couthuffcodei.leaf:;for(j=cd.start+1;jn;j+)huffcodei.bitj=cd.bitj;coutcd.bitj;coutendl;huffcodei.start=cd.start;delete huffcode;delete huffnode;void main()string str; int i=0,j,n,m100,h,k=0;char cha100;cout请输入一个字符串str;n=str.length();cout字符串总共有字符n个endl;for(i=0;in;i+)j=0;h=0;while(stri!=strj)j+; if(j=i) chak=stri; cout字符chak出现; else continue; for(j=i;jn;j+) if(stri=strj)h+; couth次endl; mk=h; k+;cout每个字符哈夫曼编码是：endl;huf(cha,m,k);cin.get();cin.get(); Haffman编码2：#include using namespace std;/*/结构哈夫曼树/*/*哈夫曼树次序表定义*/typedef structint weight;int parent,lchild,rchild;HTNode;typedef HTNode * HuffmanTree;/*初始化一个哈夫曼树*/void InitHuffmanTree(HuffmanTree &HT,int m)int i;HT=new HTNodem;for(i=0;im;i+)HTi.weight=0;HTi.parent=-1;HTi.lchild=-1;HTi.rchild=-1;/*/从n个结点中选择最小两个结点/*void SelectMin(HuffmanTree &HT,int n,int &min1,int &min2)typedef structint NewWeight;/存放权int p;/存放该结点所在位置 TempNode,*TempTree;TempTree TT=new TempNoden;int i,j;j=0;for(i=0;in;i+)if(HTi.parent=-1 & HTi.weight!=0)TTj.NewWeight=HTi.weight;TTj.p=i;j+;/将HT中没有双亲结点存放到TT中int m1,m2;m1=m2=0;for(i=0;ij;i+)if(TTi.NewWeightTTm1.NewWeight)/此处不让取到相等，是因为结点中有相同权值时候，m1取最前那个。m1=i;for(i=0;ij;i+)if(m1=m2)m2+;/当m1在第一个位置时候，m2向后移一位if(TTi.NewWeight=TTm2.NewWeight & i!=m1)/此处取到相等，是让在结点中有相同权值时候，/m2取最终那个。m2=i;min1=TTm1.p;min2=TTm2.p;/*创建哈夫曼树*/void CreateHaffmanTree(HuffmanTree &HT,int n)int i;int m;int min1,min2;if(n=1)coutParameter Error!;m=2*n-1;/哈夫曼树中结点个数InitHuffmanTree(HT,m);for(i=0;iHTi.weight;for(i=n;im;i+)SelectMin(HT,i,min1,min2);HTmin1.parent=i;HTmin2.parent=i;HTi.lchild=min1;HTi.rchild=min2;HTi.weight=HTmin1.weight+HTmin2.weight;coutmin1 min2endl;/*/结构哈夫曼编码/*/*哈夫曼编码定义*/typedef structchar 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;char q;HC=new CodeNoden;cd=new charn;cdn-1=/0;for(i=0;iq;HCi.ch=q;start=n-1;c=i;while(p=HTc.parent)=0)-start;cdstart=(HTp.lchild=c)?0:1;c=p;strcpy(HCi.bits,&cdstart);delete cd;/*哈夫曼编码输出*/void OutputHuffmanCode(HuffmanCode &HC,int n)int i;for(i=0;in;i+)coutHCi.ch HCi.bitsendl;void main()int i;couti;HuffmanTree HT;HuffmanCode HC;CreateHaffmanTree(HT,i);CreateHuffmanCode(HT,HC,i);OutputHuffmanCode(HC,i); 图形着色1：#include #include /回溯法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 : 潘乔木int main(int argc, char *argv)int n = 5;int m = 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 + 1; if(xk=m) if(k=n-1) 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 ; co