《算法设计与分析书中程序(第07章)》由会员分享，可在线阅读，更多相关《算法设计与分析书中程序(第07章)（9页珍藏版）》请在金锄头文库上搜索。
1、 【程序7-1】 多段图的向前递推算法templateT Graph:FMultiGraph(int k, int *p)/采用程序6-8的邻接表存储图GTc,*cost=new floatn; int q, *d=new intn;costn-1=0, dn-1= -1;/设置向前递推的初值for (int j=n-2; j=0; j-)/按n-2, , 0的次序计算cost和dfloat min=INFTY;/按式（7-1）计算最小值为costjfor (ENode *r=aj; r; r=r-nextArc) int v=r-adjVex;if (r-w+costvw+costv; q=
2、v;costj=min; dj=q;/q是j在最短子路径上的后继结点p0=0; pk-1=n-1; c=cost0;/p0和pn-1是源点和汇点for(j=1; j=k-2; j+) pj=dpj-1;/pi是最短路径上第i阶段的结点delete cost; delete d; return c; 【程序7-2】 弗洛伊德算法templatevoid MGraph:Floyd(T*& d, int *& path)int i, j, k;d= new T*n; path=new int *n;for(i=0; in; i+)di=new T n; pathi=new intn;for (j=0
3、; jn; j+)/初始化dij=aij;if (i！=j & wijINFTY) pathij=i;else pathij= -1;for (k=0; kn; k+)/考察结点kfor (i=0; in; i+)for (j=0; jn; j+) if (dik+dkj dij )dij=dik+dkj;pathij=pathkj; 【程序7-3】 矩阵连乘算法class MatrixChainpublic:MatrixChain(int mSize, int *q);/创建二维数组m和s，一维数组p，并初始化int MChain();/一般动态规划法求最优解值int LookupChain
4、();/备忘录方法求最优解值（程序7-4）void Traceback();/构造最优解的公有函数private:void Traceback(int i, int j);/构造最优解的私有递归函数int LookupChain(int i, int j);/备忘录方法私有递归（程序7-4）int *p, *m, *s, n;int MatrixChain:MChain() /求A0:n-1的最优解值for (int i=0;in; i+) mii=0;for (int r=2; r=n; r+)for (int i=0; i=n-r; i+) int j=i+r-1;mij=mi+1j+pi
5、*pi+1*pj+1; /mij 的初值sij=i;for (int k=i+1; kj; k+) int t=mik+mk+1j+pi*pk+1*pj+1;if (tmij) mij=t; sij=k;return m0n-1;void MatrixChain:Traceback(int i, int j)if(i=j) coutAi; return;if (isij) cout(; Traceback(i, sij); if (isij)cout);if(sij+1j)cout(; Traceback(sij+1, j); if(sij+1j) cout);void MatrixChain
6、:Traceback()cout(; Traceback(0, n-1); cout);cout0) return mij;/子问题已经求解，直接引用if(i=j) return 0;/单一矩阵无须计算int u=LookupChain(i+1, j)+pi*pi+1*pj+1;/按式（7-9）求最小值sij=i;for (int k=i+1; kj; k+) int t=LookupChain(i, k)+LookupChain(k+1, j)+pi*pk+1*pj+1;if (tu) u=t; sij=k;mij=u; return u;/保存并返回子最优解值int MatrixChain
7、:LookupChain()return LookupChain(0, n-1); /返回A0:n-1的最优解值 【程序7-5】 求LCS的长度class LCSpublic:LCS(int nx, int ny, char *x, char*y);/创建二维数组c、s和一维数组a、b，并进行初始化void LCSLength();/求最优解值（最长公共子序列长度）void CLCS();/构造最优解（最长公共子序列）private:void CLCS(int i, int j);int *c, *s.m, n;char *a, *b;int LCS:LCSLength() for(int i
8、=1; i=m; i+) ci0=0; for(i=1; i=n; i+) c0i=0;for (i=1; i=m; i+)for (int j=1; j=cij-1)cij=ci-1j; sij=2;/由ci-1j得到cijelse cij=cij-1; sij=3;/由cij-1得到cijreturn cmn;/返回最优解值 【程序7-6】 构造最长公共子序列void LCS:CLCS(int i, int j)if (i=0|j=0) return;if (sij=1)CLCS(i-1, j-1);coutai;else if (sij=2) CLCS(i-1, j); else CLC
9、S(i, j-1); 【程序7-7】 构造最优二叉搜索树int Find(int i, int j, int *r, float*c)float min=INFTY; int k;for (int m=i+1; m=j; m+)if (cim-1+cmj)min) min=cim-1+cmj; k=m;return k;void CreateOBST(float* p, float* q, float *c, int *r, float*w, int n)for (int i=0; i=n-1; i+) /初始化wii=qi; cii=0.0; rii=0;wii+1=qi+qi+1+pi+1
10、;cii+1=qi+qi+1+pi+1;rii+1=i+1;wnn=qn; cnn=0.0; rnn=0; for (int m=2; m=n; m+)/计算n-2条对角线元素 for (i=0; i=n-m; i+) int j=i+m;wij=wij-1+pj+qj;int k = Find(i, j, r, c);cij = wij + cik-1 + ckj;rij = k; 【程序7-8】 0/1背包的递归算法templateclass Knapsack public:Knapsack(int mSize, float cap, float *wei, T *prof); T RKnap();private:T f(int j, float X); float m, *w;T *p; int n;templateT Knapsack:f(int j, float X) if (j0) return (X0) ？-INFTY: 0); if (Xb)return a; else return b; templateT Knapsack: RKnap()if(n0) return f(n-1, m);else return NoAns;
