算法设计与分析所有程序文件37213.pdf

《算法设计与分析所有程序文件37213.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析所有程序文件37213.pdf（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目 录 第二章 递归与分治.3 1、用递归思想求 N!.3 2、用递归思想求 Fibonacci 数列.3 3、用递归思想求排列问题.4 4、用递归思想求整数划分问题.5 5、用递归思想求汉诺塔问题.6 6、用递归思想实现插入排序.7 7、用分治思想实现二分查找.8 8、用分治法求两个大整数的乘法.9 9、用分治思想求一个数组的最大值与最小值.10 10、用分法思想实现合并排序.12 11、用分治思想实现快速排序.13 12、用分治法实现线性时间选择问题.15 13、用分法思想实现残缺棋盘问题.15 第三章 动态规划法.18 1、矩阵连乘问题.18 2、最长公子序列.20 3、最大子段和问题.

2、23 4、图像压缩问题.28 5、电路布线问题.31 6、最.31 7、最.31 第四章 贪心算法.32 1、哈夫曼编码.32 4、Kruskal 算法求最小生成树.35 5、集装箱问题.38 6、活动安排问题.40 第五章 回溯法.42 1、用回溯法求 01 背包问题.42 2、用回溯法求 N 皇后问题.45 3、用回溯法求旅行售货员问题.46 4、用回溯法求圆排列问题.48 5、用回溯法求符号三角形问题.50 6、用回溯法求批处理作业调度问题.52 7、用回溯法求连续邮资问题.54 8、用回溯法求图的 m 着色问题.57 9、用回溯法求最大团问题.59 第六章 回溯法.62 1、用分支限界

3、法求 01 背包问题.62 第二章 递归与分治 1、用递归思想求 N!王晓东版计算机算法设计与分析（第四版）P11 页，例 21#include void main()long n;int JieChen(int n);printf(请输入一个数n);scanf(%ld,&n);long result=JieChen(n);printf(%ld,result);int JieChen(int n)if(n=1)return 1;else return n*JieChen(n-1);2、用递归思想求 Fibonacci 数列 王晓东版计算机算法设计与分析（第四版）P12 页，例 22 int F

4、ibonacci(int n)if(n=1)return 1;else return Fibonacci(n-1)+Fibonacci(n-2);void main()long n;printf(请输入一个数n);scanf(%ld,&n);long result=Fibonacci(n);printf(%ldn,result);3、用递归思想求排列问题 王晓东版计算机算法设计与分析（第四版）P13 页，例 24 N 个元素的全排列的个数为：N!本算法非常重要，因为它是很多算法的基础，比如回溯法那章里的算法很多都是以本算法为基础的。#include /交换两个元素的值 void Swap(in

5、t&x,int&y)int t=x;x=y;y=t;/产生 listk:m的所有排列/m 是最后一个元素在数组中的下标 void Perm(int list,int k,int m)if(k=m)/如果只有一个元素 for(int i=0;i=m;i+)printf(%d,listi);printf(n);else for(int i=k;i=m;i+)Swap(listi,listk);Perm(list,k+1,m);Swap(listi,listk);/将元素还原 void main()int a5=1,2,3,4,5;/求数组前面三个元素的全排列 Perm(a,0,3);4、用递归思想

6、求整数划分问题 王晓东版计算机算法设计与分析（第四版）P14 页，例 25 整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数 n 写成如下形式：n=m1+m2+mi;（其中 mi 为正整数，并且 1=mi=n），则m1,m2,.,mi为 n 的一个划分。如果m1,m2,.,mi中的最大值不超过 m，即 max(m1,m2,.,mi)0)，只有一种划分即1;(2)当 m=1 时，不论 n 的值为多少，只有一种划分即 n 个 1，1,1,1,.,1;(3)当 n=m 时，根据划分中是否包含 n，可以分为两种情况：(a).划分中包含

7、 n 的情况，只有一个即 n；(b).划分中不包含 n 的情况，这时划分中最大的数字也一定比 n 小，即 n 的所有(n-1)划分。因此 f(n,n)=1+f(n,n-1);(4)当 n m 时，根据划分中是否包含最大值 m，可以分为两种情况：(a).划分中包含 m 的情况，即m,x1,x2,.,xi,其中x1,x2,.,xi 的和为 n-m，可能再次出现 m，因此是（n-m）的 m 划分，因此这种划分个数为 f(n-m,m);(b).划分中不包含 m 的情况，则划分中所有值都比 m 小，即 n 的(m-1)划分个数为f(n,m-1);因此 f(n,m)=f(n-m,m)+f(n,m-1);综

8、合以上情况，我们可以看出，上面的结论具有递归定义特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，将会转换为情况（5）。而情况（5）为通用情况，属于递推的方法，其本质主要是通过减小 m 以达到回归条件，从而解决问题。其递推表达式如下：f(n,m)=1;(n=1 or m=1)f(n,m)=f(n,n);(n m)因此我们可以给出求出 f(n,m)的递归函数代码如下。/求整数 n 的全部划分数，其中 max 代表最大加数 long GetPartitionCount(int n,int max)if(n=1|max=1)return 1;else if(n 0)Hanoi(n-1

9、,A,C,B);printf(%d,%c-%cn,n,A,B);/模拟移动过程 Hanoi(n-1,C,B,A);void main()Hanoi(3,a,b,c);6、用递归思想实现插入排序#include#include#include void insertSort(int*aa,int n)if(n0)n=n-1;insertSort(aa,n);int a=aan;int k=n-1;while(k=0)&aaak)aak+1=aak;k-;aak+1=a;void main()int a10;srand(unsigned int)time(NULL);for(int i=0;i10

10、;i+)ai=rand()%100;printf(%d,ai);printf(n);insertSort(a,10);for(i=0;iright)return-1;if(x=amiddle)return middle;else if(xamiddle)return BinarySearch(a,x,middle+1,right);else return BinarySearch(a,x,left,middle-1);void main()int a9=-2,2,7,9,19,21,34,65,98;int index=BinarySearch(a,100,8);printf(%dn,inde

11、x);方法二：用循环代替递归/在 a 数组里查找是否存在 x 这个元素，如果存在，则返回元素所在下标，如果不存在/则返回-1/n 为最后一个元素的下标 int BinarySearch(int a,int x,int n)int left=0;/开始需要查找元素的下标 int right=n-1;/最后需要查找元素的下标 while(leftamiddle)left=middle+1;else right=middle-1;return-1;8、用分治法求两个大整数的乘法 最简单的方法，这里没有体现分治法的思想#include int main()char a100,b100,s202;int

12、 i,j,g,t=0,k=0,temp;printf(请输入两个大整数，空格分隔n);scanf(%s%s,&a,&b);int m=strlen(a);int n=strlen(b);while(km+n-2)sk=0;temp=0;for(i=0;im;i+)for(j=0;jn;j+)if(i+j)=k)/第 k 位上所有数字之和 temp+=(am-1-i-48)*(bn-1-j-48);g=(temp+t)%10;t=(temp+t)/10;/t 用来保存进位 sk=g;k+;/求最高 1 位或者 2 位，并输出 temp=0;for(i=0;im;i+)for(j=0;j=0;i-

13、)printf(%d,si);printf(n);return 0;9、用分治思想求一个数组的最大值与最小值#include#include#include#define LEN 8 void maxmin(int a,int*max,int*min,int low,int high)int mid,max1,min1,max2,min2;if(high-low)=alow)*max=ahigh;*min=alow;else *max=alow;*min=ahigh;else mid=(high+low)/2;maxmin(a,&max1,&min1,low,mid);maxmin(a,&ma

14、x2,&min2,mid+1,high);*max=max1max2?max1:max2;*min=min1min2?min1:min2;void main()int aLEN;int max=-1,min=1000;srand(unsigned)time(NULL);printf(数组里的元素为:n);for(int i=0;iLEN;i+)ai=rand()%100;printf(%d,ai);maxmin(a,&max,&min,0,LEN-1);printf(n 最大值为:%d n 最小值为:%dn,max,min);#include#include#include#define LE

15、N 8 void main()int aLEN;srand(unsigned)time(NULL);printf(数组里的元素为:n);for(int i=0;iLEN;i+)ai=rand()%100;printf(%d,ai);*/10、用分法思想实现合并排序#include int b9;void merge(int c,int d,int l,int m,int r)int i=l,j=m+1,k=l;while(i=m)&(j=r)if(ci=cj)dk+=ci+;else dk+=cj+;/将剩余部分处理好 while(j=r)dk+=cj+;while(i=m)dk+=ci+;v

16、oid mergesort(int a,int left,int right)if(leftright)int i=(left+right)/2;mergesort(a,left,i);/将左边部分排好序 mergesort(a,i+1,right);/将右边部分排好序 merge(a,b,left,i,right);/将左右两边合并 for(int j=left;j=right;j+)aj=bj;void main()int a9=4,3,6,8,9,1,25,2,34;printf(原始数据为:n);for(int i=0;i9;i+)printf(%dt,ai);mergesort(a,

17、0,8);printf(n 合并后的数据为:n);for(i=0;i9;i+)printf(%dt,ai);printf(n);11、用分治思想实现快速排序#include void quicksort(int a,int p,int r)int partition(int a,int p,int r);if(pr)/不止一个元素时 int q=partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);/以 ap为基准，将数组 ap-ar段元素分为两部，其实一部分/比 ap小，另一部分比 ap大，/返回值为 ap最终所在位置 int part

18、ition(int a,int p,int r)void swap(int*x,int*y);int i=p,j=r+1;int x=ap;while(true)while(a+ix&ix&jp);if(i=j)break;swap(&ai,&aj);ap=aj;aj=x;return j;void swap(int*x,int*y)int t;t=*x;*x=*y;*y=t;void main()int a9=9,8,7,6,5,4,3,2,1;printf(n 排序前的结果n);for(int i=0;i9;i+)printf(%dt,ai);quicksort(a,0,8);printf

19、(n 排序后的结果n);for(i=0;i9;i+)printf(%dt,ai);printf(n);如果每次划分不以 ap为基准，而是随机从 ap-ar里取一个数为基准，则可以设计如下随机化快速排序算法。/随机选择策略的划分算法,需要调用 partition 函数 int RandomizedPartition(int a,int p,int r)srand(unsigned int)time(NULL);int i=p+rand()%(r-p+1);swap(&ai,&ap);return partition(a,p,r);12、用分治法实现线性时间选择问题 本算法要用到上面快速排序的随机

20、划分算法 int RandomizedSelect(int a,int p,int r,int k)if(p=r)/如果只剩下一个数，则这个肯定就是第 k 小的数 return ap;else int i=RandomizedPartition(a,p,r);/经过快速排序进行划分 int j=i-p+1;/计算通过划分后，从 ap到 ai有多少数 if(k=j)/第 k 小的数在 ai的前半段 return RandomizedSelect(a,p,i,k);else/第 k 小的数在 ai的后半段，并且从 ap到 ai这些数都小于第 k 小的数 return RandomizedSelec

21、t(a,i+1,r,k-j);13、用分法思想实现残缺棋盘问题 王晓东版计算机算法设计与分析（第四版）P20 页，例 2.6 注意：同一种形状的骨牌，在填充时数字不一样，关键看三个相同数字摆放位置所构成的形状。#include int tile=1;/L 型骨牌的编号(递增)int board100100;/棋盘/*tr-当前棋盘左上角的行号*tc-当前棋盘左上角的列号*dr-当前特殊方格所在的行号*dc-当前特殊方格所在的列号*size：当前棋盘的:2k*/void chessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)/棋盘方格

22、大小为 1,说明递归到最里层 return;int t=tile+;/每次递增 1 int s=size/2;/棋盘中间的行、列号(相等的)/检查特殊方块是否在左上角子棋盘中 if(drtr+s&dctc+s)/在 chessBoard(tr,tc,dr,dc,s);else /不在，将该子棋盘右下角的方块视为特殊方块 boardtr+s-1tc+s-1=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);if(dr=tc+s)/在 chessBoard(tr,tc+s,dr,dc,s);else /不在，将该子棋盘左下角的方块视为特殊方块 boardtr+s-1tc+s=

23、t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);/检查特殊方块是否在左下角子棋盘中 if(dr=tr+s&dc=tr+s&dc=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else boardtr+stc+s=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);void main()int size;printf(输入棋盘的 size,大小必须是 2 的 n 次幂:);scanf(%d,&size);int index_x,index_y;printf(输入特殊方格位置的坐标:);scanf(%d%d,&index_x,&i

24、ndex_y);chessBoard(0,0,index_x,index_y,size);for(int i=0;isize;i+)for(int j=0;jsize;j+)printf(%dt,boardij);printf(n);第三章 动态规划法 1、矩阵连乘问题#include#include /n 矩阵的个数/p 记录各矩阵的维数，n 个矩阵有 n+1 个维数，Ai 的维数为 pi-1,pi/mij 记录从第 i 个矩阵到第 j 个矩阵连乘，最小的数乘次数/sij 记录从第 i 个矩阵到第 j 个矩阵连乘，取最小的数乘次数时，最后两个矩阵相乘时的位置/如果 sij=k,则代表从第 i

25、 个矩阵到第 k 个矩阵连乘,得到一个结果矩阵，/从第 k+1 个矩阵到第 j 个矩阵连乘,得到另一个结果矩阵，然后这两个结果矩阵做最后的乘法 void MatrixChain(int*p,int n,int(*m)7,int(*s)7)for(int i=1;i=n;i+)mii=0;for(int len=2;len=n;len+)/遍历矩阵链的长度 /当矩阵链的长度的长度固定为 len 时，这时有 n-len+1 个矩阵链需要求最小数乘 /下面的循环用来从前往后求这 n-len+1 个矩阵链的最小数乘值 for(int i=1;i=n-len+1;i+)/求从第 i 个矩阵到第 i+le

26、n-1 个矩阵的最小数乘值 int j=i+len-1;mij=mii+mi+1j+pi-1*pi*pj;/假设从第 i 个矩阵处划分是最小的,mii=0 sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k;/当矩阵链相乘取最小数乘时，输出矩阵链加括号的格式 void Traceback(int i,int j,int(*s)7)if(i=j)printf(A%d,i);return;printf();Traceback(i,sij,s);Traceback(sij+1,j,s);printf();/

27、下面两条语跟书本上一致，供参考/printf(Multiply A%d,%d,i,sij);/printf(and A%d,%dn,sij+1,j);void main()int p6+1=30,35,15,5,10,20,25;int m6+16+1;/下标为 0 的行与列没有用 int s6+16+1;/初始化 m 和 s 这两个矩阵 for(int i=0;i7;i+)for(int j=0;j7;j+)mij=-1;sij=-1;MatrixChain(p,6,m,s);for(i=1;i7;i+)for(int j=1;j7;j+)printf(%dt,mij);printf(n);

28、printf(n);for(i=1;i7;i+)for(int j=1;j7;j+)printf(%dt,sij);printf(n);Traceback(1,6,s);2、最长公子序列#include#include#include /X 和 Y 保存两个字符串，m 为 X 字符串里字符的个数,n 为 Y 字符串里字符的个数/cij代表当 X 取前面连续 i 个字符，Y 取前面连续 j 个字符时，这两个子字/符串的最大公共子序列的长度，bij记录此时的最大公共子序列是如何/得来的。void LCSLength(int m,int n,char*X,char*Y,int*c,int*b)for

29、(int i=0;i=n;i+)c0i=0;b0i=0;for(i=0;i=m;i+)ci0=0;bi0=0;for(i=1;i=m;i+)/X 取前面连续 i 个字符 for(int j=1;j=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;/获取最长公共子序列符号(递归实现,书本上所用的方法)int k=0;void LCS(int i,int j,char*X,int*b,char*result)if(i=0|j=0)/将 result 里的字符反转 for(int j=0;jk/2;j+)char t=resultj;resultj=result

30、k-1-j;resultk-1-j=t;resultk=0;return;else if(bij=1)resultk+=Xi-1;LCS(i-1,j-1,X,b,result);else if(bij=2)LCS(i-1,j,X,b,result);else LCS(i,j-1,X,b,result);void main()char A100=xyxzyxyzzy;char B100=xzyzxyzxyzxy;int lenA=strlen(A);int lenB=strlen(B);printf(%d%dn,lenA,lenB);/c 与 b 为两个动态二维数组，这样不浪费空间 int*c=

31、(int*)malloc(lenA+1)*sizeof(int*);int*b=(int*)malloc(lenA+1)*sizeof(int*);for(int i=0;i=lenA;i+)ci=(int*)malloc(sizeof(int)*(lenB+1);bi=(int*)malloc(sizeof(int)*(lenB+1);LCSLength(lenA,lenB,A,B,c,b);for(i=0;i=lenA;i+)for(int j=0;j=lenB;j+)printf(%d,cij);printf(n);printf(n);for(i=0;i=lenA;i+)for(int

32、j=0;j=lenB;j+)printf(%d,bij);printf(n);char result100;LCS(lenA,lenB,A,b,result);/输出最长公共字符串 for(i=0;istrlen(result);i+)printf(%c,resulti);printf(n);获取最长公共子序列符号的非递归实现/获取最长公共子序列符号 void LCS(int m,int n,char*X,int*b,char*result)int len=(mn?m:n);int k=len+1;while(m!=0&n!=0)if(bmn=1)result-k=Xm-1;/此处与教材有区别

33、，因为教材是从下标为 1 的元素处保存有效字符 m-;n-;else if(bmn=2)m-;else n-;/将 result 数组里的数据平移 for(int i=k,j=0;i=len;i+,j+)resultj=resulti;resultj=0;/设置结束字符 3、最大子段和问题（1）分治思路实现 改进了书本上的算法，可以求出最大子段和的起始坐标和终止坐标#include#include#include#define N 8 /代表列 int bestSum=0;/最大子段和的值 int besti=0;/最大子段和所在段的起始坐标 int bestj=0;/最大子段和所在段的终止坐

34、标 /最大子段和的分治算法 void MaxSubSum(int*a,int left,int right)if(left=right)int thisSum=aleft0?aleft:0;if(thisSum bestSum)bestSum=thisSum;besti=bestj=left;/else int middle=(left+right)/2;MaxSubSum(a,left,middle);MaxSubSum(a,middle+1,right);int s1=0;int lefts=0;int bi=middle+1;/重要 for(int i=middle;i=left;i-)

35、lefts=lefts+ai;if(leftss1)s1=lefts;bi=i;if(bi middle+1)/左边的最大子段和不是小于 0 int s2=0;int rights=0;int bj=middle;for(int i=middle+1;is2)s2=rights;bj=i;if(bj middle)/右边的最大子段和不是小于 0 int sum=s1+s2;if(sum bestSum)bestSum=sum;besti=bi;/记录最大子段和的起始坐标 bestj=bj;/记录最大子段和的终止坐标 void main()int aN+1;/下标为 0 的元素没有意义 sran

36、d(unsigned int)time(NULL);/设置随机种子 for(int i=1;i=N;i+)int flag=rand()%2;/flag 为 1 代表正数，flag 为 0 代表负数 if(flag)ai=rand()%30;else ai=-rand()%30;printf(%d,ai);int bi=0,bj=0;MaxSubSum(a,1,N);printf(n 从%d 到%d 的子段和最大，最大值为：%dn,besti,bestj,bestSum);（2）动态规划思路实现 补充了书本上不完美的地方：在求最大子段和，随便可以求出最大子段和的起始坐标和终止坐标；在求最大子矩

37、阵和时，可以随便求出子矩阵的左上角和右下角坐标。#include#include#include#define N 4 /代表列#define M 4 /代表行 /求最大子段和的动态规划算法 int MaxSum(int n,int*a,int&besti,int&bestj)int sum=0,b=0;besti=0;int ti=0;int tj=0;for(int i=1;i0)b+=ai;else b=ai;ti=i;if(b sum)sum=b;besti=ti;bestj=i;return sum;/m 代表数组的行数，下标为 0 的行没有使用/n 代表数组的列数，下标为 0 的列

38、没有使用 int MaxSum2(int m,int n,int*a,int&rowStart,int&rowEnd,int&colStart,int&colEnd)int sum=0;int*b=(int*)malloc(sizeof(int)*(n+1);int tRowStart=0;int tRowEnd=0;int tColStart=0;int tColEnd=0;for(int i=1;i=m;i+)/遍历起始行 for(int k=1;k=n;k+)bk=0;for(int j=i;j=m;j+)/遍历终止行 for(int k=1;ksum)sum=max;rowStart=

39、i;rowEnd=j;colStart=tColStart;colEnd=tColEnd;return sum;/*void main()int aN+1;/下标为 0 的元素没有意义 srand(unsigned int)time(NULL);/设置随机种子 for(int i=1;i=N;i+)int flag=rand()%2;/flag 为 1 代表正数，flag 为 0 代表负数 if(flag)ai=rand()%30;else ai=-rand()%30;printf(%d,ai);int bi=0,bj=0;int max=MaxSum(N,a,bi,bj);printf(n

40、从%d 到%d 的子段和最大，最大值为：%dn,bi,bj,max);*/void main()int*a;a=(int*)malloc(M+1)*sizeof(int*);for(int i=1;i=M;i+)ai=(int*)malloc(N+1)*sizeof(int);srand(unsigned int)time(NULL);/设置随机种子 for(i=1;i=M;i+)for(int j=1;j=N;j+)int flag=rand()%2;/flag 为 1 代表正数，flag 为 0 代表负数 if(flag)aij=rand()%30;else aij=-rand()%30;

41、printf(%dt,aij);printf(n);int brs=0;int bre=0;int bcs=0;int bce=0;int max=MaxSum2(M,N,a,brs,bre,bcs,bce);printf(n 从(%d,%d)到(%d,%d)的子块和最大，最大值为：%dn,brs,bcs,bre,bce,max);4、图像压缩问题 王晓东版计算机算法设计与分析（第四版）P65 页，例 3.7 书本上 P67 页上第一行 bj=bsj行错误，本程序修正了这个错误，在求每段的最大位数时，只需要从头到位扫描一次，时间复杂度为 O(n)。小有成就感_#include int leng

42、th(int i)int k=1;i=i/2;while(i0)k+;i=i/2;return k;/n 像素总个数/pi 第 i 个像素点的灰度值/si 记录前 i 个像素的最小存储空间/li 记录前 i 个像素取最小存储空间里，最后一个分段里元素的个数/bi 存储第 i 个像素的灰度值值需要多少位 void Compress(int n,int p,int s,int l,int b)int Lmax=256;/每个分段里像素个数不超过 256 个 int header=11;/每个分段里像素的头部信息为 11 位 s0=0;for(int i=1;i=n;i+)bi=length(pi)

43、;int bmax=bi;/记录最后一段里，各像素的所需存储位数的最大值 /以最后一个像素单独作为最后一段 si=si-1+bi;li=1;for(int j=2;j=i&j=Lmax;j+)if(bmax si-j+bmax*j)si=si-j+bmax*j;li=j;si+=header;void Traceback(int n,int&i,int s,int l)if(n=0)return;Traceback(n-ln,i,s,l);/*si+=n-ln;/书本上的写法：重新为 s数组赋值，用来存储分段位置*/l+i=ln;void Output(int s,int l,int b,in

44、t n)printf(n 图像压缩后的最小空间：%dn,sn);int m=0;Traceback(n,m,s,l);/*/书本上的写法，其中 bj=bsj这一行是错误的 sm=n;/最后一段的分段位置 for(int j=1;j=m;j+)lj=lsj;bj=bsj;*/int j=1;/段计数器 int nextSplit=lj;/下一段的分届 for(int i=1;inextSplit)/到了下一段的开始元素 j+;nextSplit+=lj;bj=bi;continue;if(bibj)bj=bi;printf(n 将原灰度序列分成%d 段序列段n,m);for(j=1;j=m;j+

45、)printf(第%d 段有%d 个像素，存储每个像素止少需要%d 位n,j,lj,bj);void main()int p6+1=0,10,12,15,255,2,1;int s6+1,l6+1,b6+1;printf(各像素的灰度值为：n);for(int i=1;i=6;i+)printf(%d ,pi);printf(n);Compress(6,p,s,l,b);Output(s,l,b,6);5、电路布线问题 6、最 7、最 第四章 贪心算法 1、哈夫曼编码#include#include#include typedef struct unsigned int weight;unsi

46、gned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫树 typedef char*HuffmanCode;/动态分配数组存储赫夫曼编码表 /w 数组存放 n 个字符的权值（均0），构造赫夫曼树 HT,并求出 n 个字符的赫夫曼编码HC void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)if(n=1)return;int m=2*n-1;/整棵树结点的个数 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/构造一个动态

47、数组用作赫夫曼树，其中 0 号单元未用 HuffmanTree p=NULL;int i;for(i=1,p=HT+1;iweight=*w;p-lchild=0;p-rchild=0;p-parent=0;for(i=n+1;iweight=0;p-lchild=0;p-rchild=0;p-parent=0;for(i=n+1;i=m;i+)/*=在 HT1到 HTi-1里查找 parent 为 0，而 weight 值最小的两个结点，其序号分别为 s1,s2=*/unsigned int minValue1=999999;int s1=-1;unsigned int minValue2=

48、999999;int s2=-1;for(int k=1;ki;k+)if(HTk.parent=0)if(HTk.weightminValue1)minValue2=minValue1;s2=s1;minValue1=HTk.weight;s1=k;else if(HTk.weightminValue2)minValue2=HTk.weight;s2=k;HTi.weight=HTs1.weight+HTs2.weight;HTi.lchild=s1;HTi.rchild=s2;HTi.parent=0;HTs1.parent=i;HTs2.parent=i;printf(哈夫曼树为n);p

49、rintf(weighttparenttlchildtrchildn);for(i=1;i=m;i+)printf(%dt%dt%dt%dn,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);/=从叶子结点到根逆向求每个字符的赫夫曼编码=HC=(HuffmanCode)malloc(n+1)*sizeof(char*);char*cd=(char*)malloc(n*sizeof(char);cdn-1=0;int start;for(i=1;i=n;i+)/求每个字符编码，循环 1 次，求出 1 个 start=n-1;for(unsigned int

50、 c=i,p=HTc.parent;p!=0;c=p,p=HTp.parent)if(HTp.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);/解码过程 void Decoding(HuffmanTree&HT,char*needDecode,char*code,int n)int index=2*n-1;int k=0;char result100;int len=strlen(needDecode);for(int i=0;ilen;i+)/如果