首页 > 代码库 > 贪心算法
贪心算法
学习要点：
1、概念
2、基本要素（+与动态规划算法的差异）
3、应用范例：
（1）活动安排问题
（2）最优装载问题
（3）哈夫曼编码
（4）最优服务次序问题
（5）最小生成树
（6）最大边权值最小的生成树
（7）.......
1、概念
贪心算法总是作出当前看来是最好的选择。
也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。
在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。
2、基本要素
贪心选择：通过一系列的选择得到问题的解，且所作的每一个选择都是当前状态下局部最好选择。
两个重要性质：贪心选择性质 + 最优子结构性质
（1）贪心选择性质———————————————与动态规划算法的主要区别
贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。
注：与动态规划的区别
共同点：都要求问题具有最优子结构性质
在动态规划中，每步所做的选择往往依赖于相关子问题的解，所以只有在解出相关子问题后才能作出选择。通常以自底向上的方式解各子问题。
而在贪心算法中，仅在当前状态下做出最好的选择，即局部最优选择，然后再去解作出这个选择后产生的相应的子问题。所做的贪心选择可以依赖于以往所做过的选择，但不依赖于将来所做的选择，也不依赖于子问题的解。通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。
证：确定某个具体的问题是否具有贪心选择性质，必须证明每一步所做的贪心选择最终导致问题的整体最优解。
首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明，通过每一步做贪心选择，最终可得到问题的整体最优解。
（2）最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
3、应用范例
（1）活动安排问题
/*
*问题：要求高效地安排一系列争用某一公共资源的活动
*描述：设有n 个活动的集合E={1,2，...，n}，其中每个活动都要求使用同一个资源，如演讲会场等，而在同一时间内只有一个活动可以使用这一资源。
每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。
若区间[si,fi)与区间[sj,fj)不相交，则称活动i和活动j是相容的。也就是说，当si>=fj或sj>=fi时，活动i与活动j相容。
*分析：活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
考虑到每个活动的开始、结束时间已定，要选择最佳活动安排，可以把各活动的起始时间和结束时间分别存储于数组s和f中，
且按照结束时间非递减排序，最早结束活动先被安排，依次贪心选择活动进行安排。
该贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
*B Y ：xymaqingxiang
2014-04-19
*/
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAX 20 5 #define INFINITY 32768 6 7 struct In 8 { 9 int s; 10 int f; 11 }t[MAX] ; 12 13 //按照f的值从小到大将结构体排序,关于结构体内的排序关键数据f的类型可以很多种，参考上面的例子写 14 int cmp( const void *a ,const void *b) 15 { 16 return (*(In *)a).f - (*(In *)b).f ; 17 } 18 19 void GreedySelector(int n, struct In t[], int a[]) 20 { 21 int i, j, count; 22 a[1] = 1; 23 j = 1; 24 count = 1; 25 for(i = 2; i < n+1; i++) 26 { 27 if(t[i].s >= t[j].f) 28 { 29 a[i] = 1; 30 j=i; 31 count++; 32 } 33 else 34 a[i] = 0; 35 } 36 } 37 38 //排序 39 void sort(int n, struct In t[]) 40 { 41 int i,j; 42 int t1,t2; 43 for(i=1;i<n+1;i++) 44 { 45 for(j=1;j<n+1;j++) 46 if(t[j].f>t[j+1].f) 47 { 48 t1=t[j].f; 49 t2=t[j].s; 50 51 t[j].f=t[j+1].f; 52 t[j].s=t[j+1].s; 53 54 t[j+1].f=t1; 55 t[j+1].s=t2; 56 } 57 } 58 } 59 60 int main() 61 { 62 int i = 0, j = 0; //控制程序流程 63 int n; //n：活动数目 64 int a[MAX] = {0}; //标记活动是否被安排：1--安排，0--未安排 65 66 for(i = 0; i < MAX; i++) 67 { 68 t[i].f = INFINITY; 69 t[i].s = 0; 70 } 71 72 printf("请输入活动数目（n）："); 73 scanf("%d", &n); //输入活动 74 printf("\n请输入各个活动的开始时间s和结束时间f：\n"); 75 for(i = 1; i < n+1; i++) //依次输入各个顾客服务时间 76 { 77 printf("第%d个活动的起始时间和结束时间：\n",i); 78 scanf("%d", &t[i].s); 79 scanf("%d", &t[i].f); 80 } 81 82 printf("\n"); 83 for(i = 1; i < n+1; i++) //依次打印各个活动的结束时间 84 printf("%d ",t[i].f); 85 printf("\n"); 86 for(i = 1; i < n+1; i++) //依次打印各个活动的起始时间 87 printf("%d ",t[i].s); 88 89 sort(n,t); 90 91 /* qsort(t,n,sizeof(t[0]),cmp); //排序函数--快排思想 92 */ 93 printf("\n"); 94 for(i = 1; i < n+1; i++) //依次打印各个活动的结束时间 95 printf("%d ",t[i].f); 96 printf("\n"); 97 for(i = 1; i < n+1; i++) //依次打印各个活动的起始时间 98 printf("%d ",t[i].s); 99 100 GreedySelector(n,t,a); 101 102 printf("\n"); 103 104 for(i = 1; i < n+1; i++) //打印活动标记数组 105 printf("%d",a[i]); 106 107 printf("\n被安排的活动有："); 108 for(i = 1; i < n+1; i++) 109 if(a[i]==1) 110 printf("%d ",i); 111 112 printf("\n"); 113 114 flushall(); 115 printf("按任意键继续..."); 116 getchar(); 117 return 0; 118 }
（2）最优装载问题
/*
*问题：要求在体积不受限制的情况下，将尽可能多的集装箱装上轮船
*描述：有一批集装箱要装上一搜载重量为c的轮船，其中集装箱i的重量为wi，选择尽可能多的集装箱
*分析：最优装载问题就是要在所给的这批集装箱中选择尽可能多的集装箱装上轮船，使其个数达到最大。
考虑到每个集装箱的重量已定，要把尽可能多的集装箱装上轮船，可以把各个集装箱的重量存储在数组w中，
且按照重量wi从小到大排序，最轻的先被选中，依次贪心选择集装箱进行装载。
该贪心选择的意义是使剩余的可利用空间极大化，以便装载尽可能多的集装箱。
*B Y ：xymaqingxiang
2014-04-19
*/
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAX 20 5 #define INFINITY 32768 6 7 //按照w的值从小到大排序 8 int cmp(const void *a, const void *b) 9 { 10 return (*(int *)a - *(int *)b); 11 } 12 13 14 void load(int c, int n, int w[], int a[]) 15 { 16 int i; 17 for(i = 1; i < n+1 && w[i] <= c; i++) 18 { 19 a[i] = 1; 20 c -= w[i]; 21 } 22 } 23 24 //排序 --从小到大 25 /*void sort(int n, struct In t[]) 26 { 27 int i,j; 28 int t1,t2; 29 for(i=1;i<n+1;i++) 30 { 31 for(j=1;j<n+1;j++) 32 if(t[j].f>t[j+1].f) 33 { 34 t1=t[j].f; 35 t2=t[j].s; 36 37 t[j].f=t[j+1].f; 38 t[j].s=t[j+1].s; 39 40 t[j+1].f=t1; 41 t[j+1].s=t2; 42 } 43 } 44 } 45 */ 46 47 int main() 48 { 49 int i = 0, j = 0; //控制程序流程 50 int n,c; //n：集装箱数目 51 int w[MAX] = {0}; 52 int a[MAX] = {0}; //标记集装箱是否被装载：1--被装载，0--未被装载 53 54 printf("请输入轮船载重（c）："); 55 scanf("%d", &c); //输入集装箱数目n 56 printf("请输入集装箱数目（n）："); 57 scanf("%d", &n); //输入集装箱数目n 58 printf("\n请输入各个集装箱的重量w[i]：\n"); 59 for(i = 1; i < n+1; i++) //依次输入各个集装箱重量w 60 { 61 printf("第%d个集装箱的重量w：\n",i); 62 scanf("%d", &w[i]); 63 } 64 65 printf("\n"); 66 for(i = 1; i < n+1; i++) //依次打印各个集装箱重量w 67 printf("%d ",w[i]); 68 69 // sort(n,t); 70 71 qsort(w,n,sizeof(w[0]),cmp); //排序函数--快排思想 72 73 printf("\n"); 74 for(i = 1; i < n+1; i++) //依次打印排序后各个集装箱重量w 75 printf("%d ",w[i]); 76 77 load(c,n,w,a); 78 79 printf("\n"); 80 81 for(i = 1; i < n+1; i++) //打印活动标记数组 82 printf("%d",a[i]); 83 84 printf("\n被装载的集装箱有："); 85 for(i = 1; i < n+1; i++) 86 if(a[i]==1) 87 printf("%d ",i); 88 89 printf("\n"); 90 91 flushall(); 92 printf("按任意键继续..."); 93 getchar(); 94 return 0; 95 }
（3）哈夫曼编码
/*
*问题：基础的哈夫曼树的实现
*描述：已知每个字符出现的频率，构造哈夫曼树，并设计哈弗曼编码。
*要求：从终端读入字符集大小n、n个字符和n个权值，建立哈夫曼树，打印每个字符对应的哈夫曼编码，对终端输入的字符集解码，并显示编码结果。
哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，又叫最优二叉树。
树的带权路径长度（WPL）为树中从根到所有叶子结点的各个带权路径长度之和。
带权路径长度为从树根到某一结点的路径长度（从一个结点到另一个结点所经过的分支数目）与该结点的权的乘积。
*分析：算法步骤
1、初始化：用给定的n个权值{w1,w2,....wn}对应由n棵二叉树构成的森林F={T1,T2,...,Tn}，其中每一棵二叉树Ti都只有一个权值为wi的根结点，其左右子树为空。
2、找最小树：在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左、右子树的根结点权值之和。
3、删除和加入：从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。
4、判断：重复2、3操作，知道森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。
*B Y ：xymaqingxiang
2014-04-16
*/
1 #include<stdio.h> 2 #include<malloc.h> 3 #include<stdlib.h> 4 #include<string.h> 5 6 #define MAX 20 7 #define N 20 //叶子结点的最大值 8 #define M 2*N-1 //所有结点的最大值 9 10 typedef struct 11 { 12 char data; 13 int weight; //结点的权值 14 int parent; //双亲的下标 15 int lchild; //左孩子结点的下标 16 int rchild; //右孩子结点的下标 17 }HTNode,HuffmanTree[M+1]; //HuffmanTree是结构数组类型，0号单元不用 18 19 //typedef char * HuffmanCode[N+1]; //存储哈夫曼编码串的头指针的数组 20 typedef struct 21 { 22 char data; 23 char cd[M]; 24 }CNode; 25 typedef CNode * HuffmanCode[N+1]; 26 27 28 //在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，并将其序号分别赋值给是s1，s2返回 29 void Select(HuffmanTree ht,int pos,int *s1,int *s2) 30 { 31 int m1,m2,i; 32 m1=m2=32767; //给m1、m2赋最大值 33 for(i=1;i<=pos;i++) //在ht[1]~ht[i-1]的范围内选择 34 { 35 if(ht[i].parent==0&&ht[i].weight<m1) 36 { 37 m2=m1; 38 m1=ht[i].weight; 39 *s2=*s1; 40 *s1=i; 41 } 42 else if(ht[i].parent==0&&ht[i].weight<m2) 43 { 44 m2=ht[i].weight; 45 *s2=i; 46 } 47 } 48 if(ht[*s1].weight>=ht[*s2].weight) 49 { 50 i=*s1; 51 *s1=*s2; 52 *s2=i; 53 } 54 55 /*if(*s1>*s2) 56 { 57 i=*s1; 58 *s1=*s2; 59 *s2=i; 60 }*/ 61 } 62 63 //创建哈夫曼树ht[M+1],w[]存放n个权值 64 void CrtHuffmanTree(HuffmanTree ht,int w[],char d[], int n) 65 { 66 int s1,s2; 67 int i,m; 68 for(i=1;i<=n;i++) //初始化ht[]----1~n号单元存放叶子结点 69 { 70 ht[i].data=http://www.mamicode.com/d[i]; 71 ht[i].weight=w[i]; 72 ht[i].parent=0; 73 ht[i].lchild=0; 74 ht[i].rchild=0; 75 } 76 m=2*n-1; //所有结点数目 77 for(i=n+1;i<=m;i++) //初始化ht[]----n+1~m号单元存放非叶子结点 78 { 79 ht[i].weight=0; 80 ht[i].parent=0; 81 ht[i].lchild=0; 82 ht[i].rchild=0; 83 } 84 s1=s2=1; 85 for(i=n+1;i<=m;i++) //创建非叶结点，建哈夫曼树 86 { 87 Select(ht,i-1,&s1,&s2); //在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，并将其序号分别赋值给是s1，s2返回 88 ht[i].weight=ht[s1].weight+ht[s2].weight; //标记权值、父子关系 89 ht[s1].parent=i; 90 ht[s2].parent=i; 91 ht[i].lchild=s1; 92 ht[i].rchild=s2; 93 } 94 } 95 96 //从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码 97 void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n) 98 { 99 char *cd; 100 int c,i,p,start; 101 cd=(char *)malloc((n+1)*sizeof(char)); //分配当前编码的工作空间 102 cd[n-1]=‘\0‘; //从右向左逐位存放编码，首先存放编码结束符\0 103 104 for(i=1;i<=n;i++) 105 hc[i]->data=http://www.mamicode.com/ht[i].data; 106 107 for(i=1;i<=n;i++) //求n个叶子结点对应的哈夫曼编码 108 { 109 start=n-1; //初始化编码起始指针 110 c=i; //从叶子结点开始向上倒推 111 p=ht[i].parent; 112 while(p!=0) 113 { 114 --start; 115 if(ht[p].lchild==c) 116 cd[start]=‘0‘; //左分支标0 117 else 118 cd[start]=‘1‘; //右分支标1 119 c=p; 120 p=ht[p].parent; //向上倒推 121 } 122 // hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 123 // strcpy(hc[i],&cd[start]); 124 strcpy(hc[i]->cd,&cd[start]); //把编码复制到hc[i]的cd成员变量中 125 } 126 free(cd); 127 } 128 129 //打印相应字符对应的哈夫曼编码 130 void OutPut(HuffmanCode hc,int n) 131 { 132 int i; 133 for(i=1;i<=n;i++) 134 printf("%c:%s\n",hc[i]->data,hc[i]->cd); 135 } 136 137 //解码 138 void Decode(HuffmanCode hc,char sc[],int n) 139 { 140 int len,i,j; 141 len=strlen(sc); 142 for(i=0;i<len;i++) 143 { 144 for(j=1;j<=n;j++) 145 { 146 if(hc[j]->data=http://www.mamicode.com/=sc[i]) 147 { 148 printf("%s",hc[j]->cd); 149 break; 150 } 151 } 152 153 } 154 } 155 156 void main() 157 { 158 int w[M+1]; //叶子结点的权值数组w 159 int n,i; 160 char d[M+1]; 161 char *sc; 162 HuffmanTree ht; //哈夫曼数组ht 163 HuffmanCode hc; //哈夫曼编码hc 164 printf("please input the numbers of leaves: "); 165 scanf("%d",&n); //输入叶子结点数目n 166 167 for(i=1;i<=n;i++) 168 { 169 hc[i]=(CNode *)malloc(sizeof(CNode)); 170 printf("please input the char and weight of %d:\n",i); 171 flushall(); 172 scanf("%c",&d[i]); 173 scanf("%d",&w[i]); //依次输入各叶子结点对应权值 174 } 175 176 CrtHuffmanTree(ht,w,d,n); //创建哈夫曼树 177 CrtHuffmanCode(ht,hc,n); //求哈夫曼编码 178 OutPut(hc,n); //打印哈夫曼编码结果 179 180 flushall(); 181 printf("按任意键继续..."); 182 getchar(); 183 184 sc=(char *)malloc(M*sizeof(char)); 185 printf("please input the Source code:"); 186 flushall(); 187 scanf("%s",sc); 188 Decode(hc,sc,n); 189 190 flushall(); 191 printf("按任意键继续..."); 192 getchar(); 193 }
/*
*问题：进阶哈夫曼树的文件实现
*描述：从文件中读取字符集及其权值，构造哈夫曼树，并设计哈弗曼编码，完成给定字符串的解码。
*要求：从文件读入字符集大小n、n个字符和n个权值，建立哈夫曼树，打印每个字符对应的哈夫曼编码，
将字符集的编码保存到相应的文件中，对终端输入的字符串解码，并显示解码结果。
哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，又叫最优二叉树。
树的带权路径长度（WPL）为树中从根到所有叶子结点的各个带权路径长度之和。
带权路径长度为从树根到某一结点的路径长度（从一个结点到另一个结点所经过的分支数目）与该结点的权的乘积。
*分析：算法步骤
1、初始化：用给定的n个权值{w1,w2,....wn}对应由n棵二叉树构成的森林F={T1,T2,...,Tn}，其中每一棵二叉树Ti都只有一个权值为wi的根结点，其左右子树为空。
2、找最小树：在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左、右子树的根结点权值之和。
3、删除和加入：从F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F中。
4、判断：重复2、3操作，知道森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。
*B Y ：xymaqingxiang
2014-04-16
*/
1 #include<stdio.h>
2 #include<malloc.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #include <conio.h>
6
7 #define MAX 200
8 #define N 20 //叶子结点的最大值
9 #define M 2*N-1 //所有结点的最大值
10
11 typedef struct
12 {
13 char data; //字符
14 int weight; //结点的权值
15 int parent; //双亲的下标
16 int lchild; //左孩子结点的下标
17 int rchild; //右孩子结点的下标
18 }HTNode,HuffmanTree[M+1]; //HuffmanTree是结构数组类型，0号单元不用
19
20 //typedef char * HuffmanCode[N+1]; //存储哈夫曼编码串的头指针的数组
21 typedef struct
22 {
23 char data; //字符
24 char cd[M]; //编码
25 }CNode;
26 typedef CNode * HuffmanCode[N+1];
27
28
29 //在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，并将其序号分别赋值给是s1，s2返回
30 void Select(HuffmanTree ht,int pos,int *s1,int *s2)
31 {
32 int m1,m2,i;
33 m1=m2=32767; //给m1、m2赋最大值
34 for(i=1;i<=pos;i++) //在ht[1]~ht[i-1]的范围内选择
35 {
36 if(ht[i].parent==0&&ht[i].weight<m1)
37 {
38 m2=m1;
39 m1=ht[i].weight;
40 *s2=*s1;
41 *s1=i;
42 }
43 else if(ht[i].parent==0&&ht[i].weight<m2)
44 {
45 m2=ht[i].weight;
46 *s2=i;
47 }
48 }
49 if(ht[*s1].weight>=ht[*s2].weight)
50 {
51 i=*s1;
52 *s1=*s2;
53 *s2=i;
54 }
55
56 /*if(*s1>*s2)
57 {
58 i=*s1;
59 *s1=*s2;
60 *s2=i;
61 }*/
62 }
63
64 //创建哈夫曼树ht[M+1],w[]存放n个权值
65 void CrtHuffmanTree(HuffmanTree ht,int w[],char d[], int n)
66 {
67 int s1,s2;
68 int i,m;
69 for(i=1;i<=n;i++) //初始化ht[]----1~n号单元存放叶子结点
70 {
71 ht[i].data=http://www.mamicode.com/d[i];"%c:%s\n",hc[i]->data,hc[i]->cd);
133 }
134
135 //解码
136 void Decode(HuffmanCode hc,char sc[],int n)
137 {
138 int len,i,j;
139 len=strlen(sc);
140 for(i=0;i<len;i++)
141 {
142 for(j=1;j<=n;j++)
143 {
144 if(hc[j]->data=http://www.mamicode.com/=sc[i])"%s",hc[j]->cd);
147 break;
148 }
149 }
150
151 }
152 }
153
154 //读取文件，得到字符集以及相应的权值
155 int Read(char d[],int w[])
156 {
157 FILE *fp;
158 char filename[20];
159 // char a[20] = {‘0‘};
160 // int b[20] = {0};
161 int i=1;
162 printf("\n请输入文件名:");
163 flushall();
164 scanf("%s",filename);
165 fp=fopen(filename,"rt");
166 if(fp==NULL)
167 {
168 printf("写文件出错，按任意键退出！");
169 getch();
170 exit(1);
171 }
172
173 /* while(!feof(fp))
174 {
175 fscanf(fp,"%c %d\n",&a[i],&b[i]);
176 i++;
177 }*/
178 while(!feof(fp))
179 {
180 fscanf(fp,"%c %d\n",&d[i],&w[i]);
181 i++;
182 }
183 d[i]=‘\0‘;
184 // w[i]=‘\0‘;
185 printf("\n文件读取成功！请按任意键退出！\n");
186 getch();
187 fclose(fp);
188 return (i-1);
189 }
190
191 //将字符的权值还有编码保存到相应文件中
192 void Save(char d[], int w[],int n, HuffmanCode hc)
193 {
194 FILE *fp;
195 int i;
196 char filename[20];
197 printf("\n请输入要保存规则的文件名：");
198 scanf("%s",filename);
199 fp=fopen(filename,"wt");
200 if(fp==NULL)
201 {
202 printf("写文件出错，按任意键推出！");
203 getch();
204 exit(1);
205 }
206 else
207 {
208 for(i = 1; i <= n; i++)
209 fprintf(fp, "字符%c的编码为：%s，权值为：%d\n",d[i],hc[i]->cd, w[i]);//向文件输入内容
210 }
211
212 printf("\n文件成功保存！请按任意键退出！\n");
213 getch();
214 fclose(fp);
215 }
216
217 void main()
218 {
219 int w[MAX] = {0}; //叶子结点的权值数组w
220 int n,i;
221 char d[MAX] = {‘0‘};
222 char *sc;
223 HuffmanTree ht; //哈夫曼数组ht
224 HuffmanCode hc; //哈夫曼编码hc
225
226 /* printf("please input the numbers of leaves: ");
227 scanf("%d",&n); //输入叶子结点数目n
228 for(i=1;i<=n;i++)
229 {
230 // hc[i]=(CNode *)malloc((n+1)*sizeof(CNode));
231 hc[i]=(CNode *)malloc(sizeof(CNode));
232 printf("please input the char and weight of %d:\n",i);
233 flushall();
234 scanf("%c",&d[i]);
235 scanf("%d",&w[i]); //依次输入各叶子结点对应权值
236 }
237 */
238
239 n=Read(d, w);
240
241 CrtHuffmanTree(ht,w,d,n); //创建哈夫曼树
242 CrtHuffmanCode(ht,hc,n); //求哈夫曼编码
243 OutPut(hc,n); //打印哈夫曼编码结果
244
245 Save(d, w, n, hc);
246
247 flushall();
248 printf("按任意键继续...");
249 getchar();
250
251 sc=(char *)malloc(M*sizeof(char));
252 printf("please input the Source code:");
253 flushall();
254 scanf("%s",sc);
255 Decode(hc,sc,n);
256
257 flushall();
258 printf("按任意键继续...");
259 getchar();
260 }（4）最优服务次序问题
/*
基础最优服务次序问题
1、问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1 ≤i≤n。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小 平均等待时间是n 个顾客等待服务时间的总和除以n。对于给定的n个顾客需要的服务时间，编程计算最优服务次序。
2、题目分析：
考虑到每个顾客需要的服务时间已给定，要计算最优服务次序，可以先对顾客需要的服务时间由短到长排序，再采用贪心算法求解。
3、算法设计：
a. 定义数组a[n]存储n个顾客需要的服务时间；
b. 调用库函数sort(a,a+n)对顾客需要的服务时间由短到长排序；
c. 函数time()计算最小平均等待时间，采用while循环依次对顾客等待服务时间进
行累加，用a[i]标记第i+1个顾客需要的服务时间，用b[i]计算第i+1个顾客的等待服务
时间，用t计算前i+1个顾客等待服务时间的总和（初始i=1, t=a[0],b[0]=a[0]）：
① b[i]=a[i]+b[i-1]，t=b[i]+t；
② i++；
③ i=n时循环结束；
d. t/n为所求。
4、算法分析：
函数time()的时间杂度为Ο(n)，主函数调用的库函数sort(a,a+n)的时间复杂度为，且主函数调用函数time()，故该算法的时间杂度为。
*B Y ：xymaqingxiang
2014-04-17
*/
/*
*问题：多处最优服务次序问题的实现
*描述：设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1 ≤i≤n。共有s处可以提供此项服务。
应如何安排n 个顾客的服务次序才能使平均等待时间达到最小，平均等待时间是n 个顾客等待服务时间的总和除以n。
对于给定的n个顾客需要的服务时间，编程计算最优服务次序。
*分析：考虑到每个顾客需要的服务时间已给定，要计算多处最优服务次序，可以先对顾客需要的服务时间由短到长排序，最短服务时间优先，即采用贪心算法求解。
即按照服务时间排好序，分治，每次都按从0到s依序进入需要服务的顾客，并且一定是从0到s开始服务结束时换人。
*B Y ：xymaqingxiang
2014-04-17
*/
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int cmp(const void *a, const void *b) 5 { 6 return (*(int *)a - *(int *)b); 7 } 8 9 int main() 10 { 11 int i = 0, j = 0; //控制程序流程 12 int n, s; //n：顾客数目； s：服务处数目 13 double t = 0; //统计最终的平均等待时间 14 int a[100]; //记录各个顾客的服务时间 15 int st[100] = {0}; //S个服务处服务时间记录 16 printf("请输入顾客（n）和服务处数目（s）："); 17 scanf("%d%d", &n, &s); //输入顾客数目和服务处数目 18 printf("\n请输入各个顾客的服务时间a：\n"); 19 for(i = 0; i < n; i++) //依次输入各个顾客服务时间 20 scanf("%d", &a[i]); 21 qsort(a,n,sizeof(a[0]),cmp); //排序函数--快排思想 22 i=0; 23 while(i < n) 24 { 25 st[j] +=a [i]; 26 t += st[j]; 27 i++; 28 j++; 29 if(j == s) 30 j = 0; 31 } 32 printf("\n平均等待时间："); 33 printf("%.f\n",t/n); 34 flushall(); 35 printf("按任意键继续..."); 36 getchar(); 37 return 0; 38 }
（5）最小生成树
问题：求得连通图的最小生成树，使其各边代价之和最小
描述：
一个连通图的生成树是指一个极小连通子图，它包含图中的全部顶点，但只有足以构成一棵树的n-1条边。
在一个连通网的所有生成树中，各边的代价之和最小的那棵生成树称之为该连通网的最小代价生成树，简称最小生成树（MST）。
分析：用贪心算法设计策略构造最小生成树
Prim算法 + Kruskal算法
设G=（V,E）是连通带权图，V={1,2, . . . , n }。
a、Prim算法——加点法
算法基本思想：首先置S={1}，然后，只要S是V的真子集，做如下的贪心选择：选取满足条件i属于S，j属于V-S，且c[i][j]最小的边，并将顶点j添加到S中，这个过程一直进行到S=V时为止。
b、Kruskal算法——加边法
算法基本思想：首先将G的n个顶点看成是n个孤立的连通分支，将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按照下述方法连接两个不同的连通分支：当查看到第k条边（v,w），如果端点v、w分别是当前两个不同的连通分支T1和T2中的顶点时，就用边（v,w）将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。
Kruskal算法中按权的递增顺序查看边的序列可以看做是一个优先队列，它的优先级为边权。顺序查看就是对这个优先队列执行DeleteMin运算。
在Kruskal算法中，需要对由连通分支组成的集合不断的进行修改，Union（a,b）即将两个联通分支连接起来，Find（v）返回包含顶点v的连通分支的名字。
（5）最大边权值最小的生成树
/*
问题：（有向+无向）图的连通性（遍历实现）
描述： 用邻接矩阵实现:
实现图的深度优先遍历和广度优先遍历,并输出。
用BFS、DFS判断图的连通性
*/
//拓展
/*
*问题：生成树问题
*描述：试设计一个构造图G生成树的算法，使得构造出的生成树的边的最大权值达到最小。
*分析：考虑到每条边的权值已给定，要使生成树的边中的最大权值达到最小，可以先对图中的边由大到小排序，再采用贪心算法求解。
*设计：a. 定义数组a[n]存储n条边的权值；
b. 调用库函数sort(a)对边的权值按由大到小排序；
c. 依次删除权值最大的边，并判断树是否连通，
① 若连通，则继续c；
② 若不连通，则结束；
d. 此时的a[i]即为所求。
*B Y ：xymaqingxiang
2014-04-16
**存在问题：边信息数组没有实时更新
*/
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<malloc.h> 4 5 #define MAX 20 6 //#define INFINITY 32768 7 #define False 0 8 #define True 1 9 10 int count_d; //DFS中遍历过程中点的统计计数 11 int visited[MAX]; //访问标记数组 12 13 typedef enum {DG,DN,UDG,UDN} Graphkind; //图的种类 14 typedef char VertexData; //假设顶点数据类型为字符型 15 typedef int AdjType; //权值为整型--int型 16 typedef struct ArcNode //定义邻接矩阵ArcNode 17 { 18 AdjType adj; //对于无权图，1表示相邻，0则相反 19 // OtherInfo info 20 }ArcNode; 21 22 typedef struct data //边信息数组 23 { 24 VertexData v1; //边的顶点 25 VertexData v2; //边的顶点 26 int weight; //权值 27 }Data; 28 29 typedef struct // 30 { 31 VertexData vertex[MAX]; //顶点数组 32 ArcNode arcs[MAX][MAX]; //邻接矩阵 33 int vexnum,arcnum; //图的顶点数和弧数 34 Graphkind kind; //图的种类标志 35 Data info[MAX]; 36 }AdjMatrix; 37 38 typedef struct Node //节点类型 39 { 40 int data; //数据域 41 struct Node *next; //指针域 42 }QNode; 43 typedef struct //队列类型 44 { 45 QNode *front; //队头 46 QNode *rear; //队尾 47 }LinkQueue; 48 49 int InitQueue(LinkQueue *Q) //队列初始化 50 { 51 Q->front=(QNode*)malloc(sizeof(QNode)); 52 if(Q->front==NULL) 53 { 54 printf("malloc error!\n"); 55 return False; 56 } 57 Q->front->next=NULL; 58 Q->rear=Q->front; 59 return True; 60 } 61 int EnterQueue(LinkQueue *Q,int x) //入队操作--将元素x插入到队列Q中 62 { 63 QNode *s; 64 s=(QNode*)malloc(sizeof(QNode)); 65 if(s==NULL) 66 { 67 printf("malloc error!\n"); 68 return False; 69 } 70 s->data=http://www.mamicode.com/x; 71 s->next=NULL; 72 Q->rear->next=s; 73 Q->rear=s; 74 return True; 75 } 76 int DeleteQueue(LinkQueue *Q,int *x) //出队操作--将队列Q的队头元素出队，并存放到x所指的存储空间中 77 { 78 QNode *p; 79 if(Q->front==Q->rear) 80 { 81 printf("queue is empty!\n"); 82 return False; 83 } 84 p=Q->front->next; 85 Q->front->next=p->next; 86 *x=p->data; 87 free(p); 88 if(Q->front->next==NULL) 89 Q->rear=Q->front; 90 return True; 91 } 92 int Empty(LinkQueue *Q) //将队列置空 93 { 94 if(Q->front==Q->rear) 95 return True; 96 return False; 97 } 98 99 int Locate(AdjMatrix *g,VertexData v) //求顶点位置 100 { 101 int j=False,k; 102 for(k=0;k<g->vexnum;k++) 103 if(g->vertex[k]==v) 104 { 105 j=k; 106 break; 107 } 108 return j; 109 } 110 111 void CreateDN(AdjMatrix *g) //创建有向图 112 { 113 int i,j,k; 114 VertexData v1,v2; 115 printf("please input arcnum vexnum :\n"); 116 scanf("%d %d",&g->arcnum,&g->vexnum); 117 for(i=0;i<g->vexnum;i++) 118 for(j=0;j<g->vexnum;j++) 119 g->arcs[i][j].adj=0; 120 for(i=0;i<g->vexnum;i++) 121 { 122 printf("please input vertex %d/%d:",i+1,g->vexnum); 123 flushall(); 124 scanf("%c",&g->vertex[i]); 125 printf("\n"); 126 } 127 for(k=0;k<g->arcnum;k++) 128 { 129 printf("please input arc %d/%d:",k+1,g->arcnum); 130 flushall(); 131 scanf("%c%c",&v1,&v2); 132 i=Locate(g,v1); 133 j=Locate(g,v2); 134 g->arcs[i][j].adj=1; 135 } 136 137 } 138 139 void CreateUDN(AdjMatrix *g) //创建无向图 140 { 141 int i,j,k; 142 int w; 143 // VertexData v1,v2; 144 printf("please input arcnum vexnum :\n"); //输入图的弧数、顶点数 145 scanf("%d %d",&g->arcnum,&g->vexnum); 146 for(i=0;i<g->vexnum;i++) //初始化邻接矩阵 147 for(j=0;j<g->vexnum;j++) 148 g->arcs[i][j].adj=0; 149 for(i=0;i<g->vexnum;i++) //输入图的顶点信息 150 { 151 printf("please input vertex %d/%d:",i+1,g->vexnum); 152 flushall(); //清空缓存区 153 scanf("%c",&g->vertex[i]); 154 printf("\n"); 155 } 156 157 for(k=0;k<g->arcnum;k++) //输入一条弧的两个顶点 158 { 159 printf("please input arc %d/%d:",k+1,g->arcnum); 160 flushall(); 161 // scanf("%c%c",&v1,&v2); 162 163 scanf("%c%c",&g->info[k].v1,&g->info[k].v2); 164 scanf("%d",&g->info[k].weight); 165 i=Locate(g,g->info[k].v1); //得到两个顶点的位置 166 j=Locate(g,g->info[k].v2); 167 g->arcs[i][j].adj=g->info[k].weight; //建立弧 168 g->arcs[j][i].adj=g->info[k].weight; //建立弧 169 } 170 171 } 172 173 174 //添加边 175 void Addarc(AdjMatrix *g,int k) 176 { 177 int i,j; 178 i=Locate(g,g->info[k].v1); //得到两个顶点的位置 179 j=Locate(g,g->info[k].v2); 180 g->arcs[i][j].adj=g->info[k].weight; //恢复弧 181 g->arcs[j][i].adj=g->info[k].weight; //恢复弧 182 g->arcnum+=g->arcnum; 183 } 184 185 //删除一条边 186 void Delarc(AdjMatrix *g,int k) 187 { 188 int i,j; 189 i=Locate(g,g->info[k].v1); //得到两个顶点的位置 190 j=Locate(g,g->info[k].v2); 191 g->arcs[i][j].adj=0; //删除弧 192 g->arcs[j][i].adj=0; //删除弧 193 g->arcnum-=g->arcnum; 194 } 195 196 void DFS(AdjMatrix g,int i) //深度优先遍历 197 { 198 int j; 199 printf("%c ",g.vertex[i]); 200 count_d++; 201 visited[i]=True; 202 for(j=0;j<g.vexnum;j++) 203 if(!visited[j]&&g.arcs[i][j].adj!=0) 204 DFS(g,j); 205 } 206 int TraverseD(AdjMatrix g) 207 { 208 int i; 209 count_d=0; 210 for(i=0;i<g.vexnum;i++) 211 visited[i]=False; 212 i=0; 213 // for(i=0;i<g.vexnum;i++) 214 if(!visited[i]) 215 DFS(g,i); 216 if(count_d==g.vexnum) 217 return True; 218 else 219 return False; 220 } 221 222 int BFS(AdjMatrix g,int i) //广度优先遍历 223 { 224 int j,k; 225 int count; 226 LinkQueue q; 227 printf("%c ",g.vertex[i]); 228 visited[i]=True; 229 count=1; 230 InitQueue(&q); 231 EnterQueue(&q,i); 232 while(!Empty(&q)) 233 { 234 DeleteQueue(&q,&k); 235 for(j=0;j<g.vexnum;j++) 236 { 237 if(!visited[j]&&g.arcs[k][j].adj!=0) 238 { 239 printf("%c ",g.vertex[j]); 240 visited[j]=True; 241 count++; 242 EnterQueue(&q,j); 243 } 244 } 245 } 246 if(count==g.vexnum) 247 return True; 248 else 249 return False; 250 } 251 int TraverseB(AdjMatrix g) 252 { 253 int i,f; 254 for(i=0;i<g.vexnum;i++) 255 visited[i]=False; 256 i=0; 257 // for(i=0;i<g.vexnum;i++) 258 if(!visited[i]) 259 f=BFS(g,i); 260 if(f==1) 261 return True; 262 else 263 return False; 264 } 265 266 //确定由大到小排序 267 int cmp(const void *a, const void *b) 268 { 269 return (*(int *)b - *(int *)a); 270 } 271 272 //冒泡排序实现 273 void sort(AdjMatrix *g) 274 { 275 int i,j; 276 int t; 277 VertexData v1,v2; 278 for(i=0;i<g->arcnum;i++) 279 { 280 for(j=0;j<g->arcnum;j++) 281 if(g->info[j].weight<g->info[j+1].weight) 282 { 283 t=g->info[j].weight; 284 v1=g->info[j].v1; 285 v2=g->info[j].v2; 286 287 g->info[j].weight=g->info[j+1].weight; 288 g->info[j].v1=g->info[j+1].v1; 289 g->info[j].v2=g->info[j+1].v2; 290 291 g->info[j+1].weight=t; 292 g->info[j+1].v1=v1; 293 g->info[j+1].v2=v2; 294 } 295 } 296 297 } 298 299 void main() 300 { 301 int i,j; 302 int b,d; //返回值判断标志位 303 304 AdjMatrix g; //无向图 305 CreateUDN(&g); 306 307 // AdjMatrix g; //有向图 308 // CreateDN(&g); 309 310 printf("\n"); 311 312 for(i=0;i<g.vexnum;i++) //打印邻接矩阵信息 313 { 314 for(j=0;j<g.vexnum;j++) 315 { 316 printf("%d",g.arcs[i][j].adj); 317 } 318 printf("\n"); 319 } 320 321 printf("\n"); 322 323 printf("BFS:"); //BFS:首先判断图是否连通，不连通则退出 324 b=TraverseB(g); 325 if(b==1) 326 printf("\nBFS---连通"); 327 else 328 { 329 printf("\nBFS---不连通,不存在生成树"); 330 exit(0); 331 } 332 333 printf("\n"); 334 335 printf("DFS:"); //DFS:首先判断图是否连通，不连通则退出 336 d=TraverseD(g); 337 if(d==1) 338 printf("\nDFS---连通"); 339 else 340 { 341 printf("\nDFS---不连通,不存在生成树"); 342 exit(0); 343 } 344 345 printf("\n"); 346 347 //对图的边按照权值由大到小排序 ——————有问题 348 // qsort(g.info,g.arcnum,sizeof(g.info[0]),cmp); //排序函数--快排思想 349 sort(&g); 350 351 printf("\n"); 352 353 //打印边的信息数组，检查排序效果 354 for(i=0;i<g.arcnum;i++) 355 printf("%d ",g.info[i].weight); 356 357 printf("\n\n"); 358 359 //求解生成树 360 j=g.arcnum; 361 for(i=0;i<j;i++) 362 { 363 Delarc(&g,i); //依次删除最大边并判断图的连通性 364 printf("\nBFS:"); 365 b=TraverseB(g); 366 if(b!=1) 367 Addarc(&g,i); 368 } 369 370 printf("\n"); 371 372 373 //打印最终的邻接矩阵 374 for(i=0;i<g.vexnum;i++) 375 { 376 for(j=0;j<g.vexnum;j++) 377 { 378 printf("%d",g.arcs[i][j].adj); 379 } 380 printf("\n"); 381 } 382 383 getchar(); 384 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。