首页 > 代码库 > 贪心算法

贪心算法

学习要点:

1、概念

2、基本要素(+与动态规划算法的差异)

3、应用范例:

1)活动安排问题

2)最优装载问题

3)哈夫曼编码

4)最优服务次序问题

5)最小生成树

6)最大边权值最小的生成树

7.......

 

1、概念

贪心算法总是作出当前看来是最好的选择。

也就是说贪心算法并不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择

在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。

2、基本要素

贪心选择:通过一系列的选择得到问题的解,且所作的每一个选择都是当前状态下局部最好选择。

两个重要性质:贪心选择性质 + 最优子结构性质

(1)贪心选择性质———————————————与动态规划算法的主要区别

贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。

注:与动态规划的区别

共同点:都要求问题具有最优子结构性质

在动态规划中,每步所做的选择往往依赖于相关子问题的解,所以只有在解出相关子问题后才能作出选择。通常以自底向上的方式解各子问题。

而在贪心算法中,仅在当前状态下做出最好的选择,即局部最优选择,然后再去解作出这个选择后产生的相应的子问题。所做的贪心选择可以依赖于以往所做过的选择,但不依赖于将来所做的选择,也不依赖于子问题的解。通常以自顶向下的方式进行,以迭代的方式做出相继的贪心选择,每做一次贪心选择就将所求问题简化为规模更小的子问题。

证:确定某个具体的问题是否具有贪心选择性质,必须证明每一步所做的贪心选择最终导致问题的整体最优解。

首先考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始,做了贪心选择后,原问题简化为规模更小的类似子问题。然后用数学归纳法证明,通过每一步做贪心选择,最终可得到问题的整体最优解。

(2)最优子结构性质

当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。

问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

3、应用范例

(1)活动安排问题

/*

*问题:要求高效地安排一系列争用某一公共资源的活动

*描述:设有个活动的集合E={1,2...n},其中每个活动都要求使用同一个资源,如演讲会场等,而在同一时间内只有一个活动可以使用这一资源。

   每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开时间区间[si,fi)内占用资源。

   若区间[si,fi)与区间[sj,fj)不相交,则称活动i和活动j是相容的。也就是说,当si>=fjsj>=fi时,活动i与活动j相容。

*分析:活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

   考虑到每个活动的开始、结束时间已定,要选择最佳活动安排,可以把各活动的起始时间和结束时间分别存储于数组sf中,

   且按照结束时间非递减排序,最早结束活动先被安排,依次贪心选择活动进行安排。

   该贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。

*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)哈夫曼编码

/*

*问题:基础的哈夫曼树的实现

*描述:已知每个字符出现的频率,构造哈夫曼树,并设计哈弗曼编码。

*要求:从终端读入字符集大小nn个字符和n个权值,建立哈夫曼树,打印每个字符对应的哈夫曼编码,对终端输入的字符集解码,并显示编码结果。

   哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树,又叫最优二叉树。

   树的带权路径长度(WPL)为树中从根到所有叶子结点的各个带权路径长度之和。

   带权路径长度为从树根到某一结点的路径长度(从一个结点到另一个结点所经过的分支数目)与该结点的权的乘积。

*分析:算法步骤

   1、初始化:用给定的n个权值{w1,w2,....wn}对应由n棵二叉树构成的森林F={T1,T2,...,Tn},其中每一棵二叉树Ti都只有一个权值为wi的根结点,其左右子树为空。

   2、找最小树:在森林F中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左、右子树,标记新二叉树的根结点权值为其左、右子树的根结点权值之和。

   3、删除和加入:从F中删除被选中的那两棵二叉树,同时把新构成的二叉树加入到森林F中。

   4、判断:重复23操作,知道森林中只含有一棵二叉树为止,此时得到的这棵二叉树就是哈夫曼树。

*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 }
代码实现

/*

*问题:进阶哈夫曼树的文件实现

*描述:从文件中读取字符集及其权值,构造哈夫曼树,并设计哈弗曼编码,完成给定字符串的解码。

*要求:从文件读入字符集大小nn个字符和n个权值,建立哈夫曼树,打印每个字符对应的哈夫曼编码,

   将字符集的编码保存到相应的文件中,对终端输入的字符串解码,并显示解码结果。

   哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树,又叫最优二叉树。

   树的带权路径长度(WPL)为树中从根到所有叶子结点的各个带权路径长度之和。

   带权路径长度为从树根到某一结点的路径长度(从一个结点到另一个结点所经过的分支数目)与该结点的权的乘积。

*分析:算法步骤

   1、初始化:用给定的n个权值{w1,w2,....wn}对应由n棵二叉树构成的森林F={T1,T2,...,Tn},其中每一棵二叉树Ti都只有一个权值为wi的根结点,其左右子树为空。

   2、找最小树:在森林F中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左、右子树,标记新二叉树的根结点权值为其左、右子树的根结点权值之和。

   3、删除和加入:从F中删除被选中的那两棵二叉树,同时把新构成的二叉树加入到森林F中。

   4、判断:重复23操作,知道森林中只含有一棵二叉树为止,此时得到的这棵二叉树就是哈夫曼树。

*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、问题描述:
设有个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1 in。应如何安排个顾客的服务次序才能使平均等待时间达到最小 平均等待时间是个顾客等待服务时间的总和除以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

*/

 

/*

*问题:多处最优服务次序问题的实现

*描述:设有个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1 in。共有s处可以提供此项服务。

   应如何安排个顾客的服务次序才能使平均等待时间达到最小,平均等待时间是个顾客等待服务时间的总和除以n

   对于给定的n个顾客需要的服务时间,编程计算最优服务次序。

*分析:考虑到每个顾客需要的服务时间已给定,要计算多处最优服务次序,可以先对顾客需要的服务时间由短到长排序,最短服务时间优先,即采用贪心算法求解。

   即按照服务时间排好序,分治,每次都按从0s依序进入需要服务的顾客,并且一定是从0s开始服务结束时换人。

*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},然后,只要SV的真子集,做如下的贪心选择:选取满足条件i属于Sj属于V-S,且c[i][j]最小的边,并将顶点j添加到S中,这个过程一直进行到S=V时为止。

bKruskal算法——加边法

算法基本思想:首先将Gn个顶点看成是n个孤立的连通分支,将所有的边按权从小到大排序。然后从第一条边开始,依边权递增的顺序查看每一条边,并按照下述方法连接两个不同的连通分支:当查看到第k条边(v,w),如果端点vw分别是当前两个不同的连通分支T1T2中的顶点时,就用边(v,w)将T1T2连接成一个连通分支,然后继续查看第k+1条边;如果端点vw在当前的同一个连通分支中,就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

Kruskal算法中按权的递增顺序查看边的序列可以看做是一个优先队列,它的优先级为边权。顺序查看就是对这个优先队列执行DeleteMin运算。

Kruskal算法中,需要对由连通分支组成的集合不断的进行修改,Uniona,b即将两个联通分支连接起来,Findv返回包含顶点v的连通分支的名字。

(5)最大边权值最小的生成树

 /*

 问题:(有向+无向)图的连通性(遍历实现) 

 描述: 用邻接矩阵实现

实现图的深度优先遍历和广度优先遍历,并输出。

BFSDFS判断图的连通性

 */

//拓展

 /*

*问题:生成树问题

*描述:试设计一个构造图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 }
代码实现