贪心算法实现

我就是我 2022-07-14 09:40 216阅读 0赞

一. 给出解决文件压缩问题的贪心算法

Algorithm -**HUFFMAN**

输入:  n个字符的集合C=\{c1,c2,…,cn\}和它们的频度\{f(c1),f(c2),…,f(cn)\}.

输出:  C的Huffman 树(V,T)

1.根据频度将所有字符插入最小堆H

2. VßC; T=\{\}

3. for j=1 to n-1

4. *c=DELETEMIN(H)*

5. *c’=DELETEMIN(H)*

6. *f(v)=f(c)+f(c’)*        \{ *v* 是一个新节点\}

7. *INSERT(H,v)*

8. *V=V ∪\{v\}*    \{ 添加*v* 到* V*\}

9. *T=T ∪\{(v,c),(v,c’)\}*    \{ 使c和c’成为T中v的孩子\}

10. end for

二.  程序实现上述算法（附：程序源代码）

（1）哈夫曼树的表示

设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义个哈夫曼数组（hfmt\[\]）。

迷宫定义如下：

typedef struct

int weight;

int lchild;

int rchild;

int parent;

char key;

\}htnode;

typedef htnode hfmt\[MAXLEN\];

** **

（2）对原始字符进行编码

初始化哈夫曼树（inithfmt）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

并显示出每个字符的编码。

1.void inithfmt(hfmt t)//对结构体进行初始化

2.void inputweight(hfmt t)//输入函数

3.void selectmin(hfmt t,int i,int \*p1,int \*p2)//选中两个权值最小的函数

4.void creathfmt(hfmt t)//创建哈夫曼树的函数

5.void phfmnode(hfmt t)//对字符进行初始编码

（3）对用户输入的字符进行编码

void encoding(hfmt t)//对用户输入的电文进行编码

char r\[1000\];//用来存储输入的字符串

int i,j;

printf("\\n\\n请输入需要编码的字符:");

gets(r);

printf("编码结果为:");

for(j=0;r\[j\]!='\\0';j++)

for(i=0;i<n;i++)

if(r\[j\]==t\[i\].key)

hfmtpath(t,i,j);

printf("\\n");

（4）对用户输入的字符进行编码

**void decoding(hfmt t)    ** //对用户输入的密文进行译码

**\{**

**      char r\[100\];**

**      int i,j,len;**

**     ** j=2\*n-2;     //j初始从树的根节点开始

printf("\\n\\n请输入需要译码的字符串:");

**      gets(r);**

**     ** len=strlen(r);

printf("译码的结果是:");

**      for(i=0;i<len;i++)**

**      \{**

**            if(r\[i\]=='0')**

**            \{**

**                  j=t\[j\].lchild;**

**                  if(t\[j\].lchild==-1)**

**                  \{**

**                       printf("%c",t\[j\].key);**

**                       j=2\*n-2;**

**                  \}**

**            \}**

**            else if(r\[i\]=='1')**

**            \{**

**                  j=t\[j\].rchild;**

**                  if(t\[j\].rchild==-1)**

**                  \{**

**                      printf("%c",t\[j\].key);     **

**                      j=2\*n-2;**

**                  \}**

**            \}**

**      \}**

**      printf("\\n\\n");                  **

**\}**

** **

三. 源程序清单：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXLEN 100
    
    typedef struct
    {
          int weight;
          int lchild;
          int rchild;
          int parent;
          char key;
    }htnode;
    
    typedef htnode hfmt[MAXLEN];
    
    int n;
    
    void inithfmt(hfmt t)//对结构体进行初始化 
    {
          int i;
          printf("\n");
          printf("------------------------------------------------------------------\n");
          printf("******************************输入区******************************\n");
          printf("\n请输入n=");
          scanf("%d",&n);
          getchar();
          for(i=0;i<2*n-1;i++)//对结构体进行初始化 
          {
                t[i].weight=0;
                t[i].lchild=-1;
                t[i].rchild=-1;
                t[i].parent=-1;            
          }
          printf("\n");
    } 
    
    void inputweight(hfmt t)//输入函数 
    {
          int w;//w表示权值 
          int i;
          char k;//k表示获取的字符 
          for(i=0;i<n;i++)
          { 
                printf("请输入第%d个字符:",i+1);
                scanf("%c",&k);
                getchar();
                t[i].key=k;
                printf("请输入第%d个字符的权值:",i+1);
                scanf("%d",&w);
                getchar();
                t[i].weight=w;
                printf("\n");
          }     
    }
    
    void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数 
    {
         long min1=999999;
         long min2=999999;
         int j;
         for(j=0;j<=i;j++)//选择最小权值字符的下标返回 
               if(t[j].parent==-1)
                     if(min1>t[j].weight)
                     {
                           min1=t[j].weight;
                           *p1=j;
                     }                    
         for(j=0;j<=i;j++)//选择次小权值字符的下标还回 
              if(t[j].parent==-1)
                    if(min2>t[j].weight && j!=(*p1))//注意 j!=(*p1)) 
                    {
                           min2=t[j].weight;
                           *p2=j;
                    }                   
    
    
    }
    
    void creathfmt(hfmt t)//创建哈夫曼树的函数 
    {
          int i,p1,p2;
          inithfmt(t);
          inputweight(t);
          for(i=n;i<2*n-1;i++)
          {
                selectmin(t,i-1,&p1,&p2);          
                t[p1].parent=i;
                t[p2].parent=i;
                t[i].lchild=p1;
                t[i].rchild=p2;    
                t[i].weight=t[p1].weight+t[p2].weight;    
          }
    }
    
    void printhfmt(hfmt t)//打印哈夫曼树 
    {
          int i;
          printf("------------------------------------------------------------------\n");
          printf("**********************哈夫曼编数结构:*****************************\n");
          printf("\t\t权重\t父母\t左孩子\t右孩子\t字符\t");
          for(i=0;i<2*n-1;i++)
               {
                     printf("\n");
                     printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);              
               }     
          printf("\n------------------------------------------------------------------\n");            
          printf("\n\n");     
    }
    
    void hfmtpath(hfmt t,int i,int j)//编码的重要哈夫曼树路径递归算法 
    {
          int a,b;
          a=i;
          b=j=t[i].parent; 
          if(t[j].parent!=-1)
          { 
    
                i=j;
                hfmtpath(t,i,j);
          }
    
          if(t[b].lchild==a)
               printf("0");
          else       
                printf("1");
    
    
         
    }
    
    void phfmnode(hfmt t)//对字符进行初始编码 
    {  
          int i,j,a;
          printf("\n------------------------------------------------------------------\n"); 
          printf("**************************哈夫曼编码******************************");
          for(i=0;i<n;i++)
          {
               j=0;
               printf("\n");
               printf("\t\t%c\t",t[i].key,t[i].weight);
               hfmtpath(t,i,j);
          }
          printf("\n------------------------------------------------------------------\n"); 
    }
    
    void encoding(hfmt t)//对用户输入的电文进行编码 
    { 
         char r[1000];//用来存储输入的字符串 
         int i,j;        
         printf("\n\n请输入需要编码的字符:");
         gets(r);
         printf("编码结果为:"); 
         for(j=0;r[j]!='\0';j++)
             for(i=0;i<n;i++)
                 if(r[j]==t[i].key)    
                      hfmtpath(t,i,j);  
         printf("\n");   
    }
    void decoding(hfmt t)//对用户输入的密文进行译码 
    {
          char r[100];
          int i,j,len; 
          j=2*n-2;//j初始从树的根节点开始 
          printf("\n\n请输入需要译码的字符串:");
          gets(r);
          len=strlen(r);
          printf("译码的结果是:");
          for(i=0;i<len;i++)
          {
                if(r[i]=='0')
                {
                      j=t[j].lchild;
                      if(t[j].lchild==-1)
                      {
                           printf("%c",t[j].key);
                           j=2*n-2;
                      }
                } 
                else if(r[i]=='1')
                {
                      j=t[j].rchild; 
                      if(t[j].rchild==-1)
                      {
                          printf("%c",t[j].key);     
                          j=2*n-2;
                      } 
                }
          }
          printf("\n\n");                  
    }
    
    int main()
    {
          int i,j;
          hfmt ht;
          char flag;
          creathfmt(ht);
          printhfmt(ht);
          phfmnode(ht); 
          printf("\n------------------------------------------------------------------\n"); 
          printf("***************************编码&&译码&&退出***********************");      
          printf("\n【1】编码\t【2】\t译码\t【0】退出");
          printf("\n您的选择：");
          flag=getchar();
          getchar(); 
          while(flag!='0')
          {
               if(flag=='1')     
                    encoding(ht);
               else if(flag=='2')
                    decoding(ht);
               else 
                    printf("您的输入有误，请重新输入。\n");
               printf("\n***************************编码&&译码&&退出***********************");  
               printf("\n【1】编码\t【2】\t译码\t【0】退出");
               printf("\n您的选择：");
               flag=getchar();
               getchar(); 
          } 
          system("pause");
    }