《考研-資料結構-哈弗曼樹-已知某段通信封包内容，對該封包進行哈弗曼編碼，并計算平均碼長》

題目描述

已知某段通信封包内容，對該封包進行哈弗曼編碼，并計算平均碼長。

(1)統計封包中各字元出現的頻度。(字元集範圍為52個英文字母，空格，英文句号。封包長度<=200)

(2)構造一棵哈弗曼樹，依次給出各字元編碼結果。

(3)給字元串進行編碼。

(4)給編碼串進行譯碼。

(5)計算平均碼長。

規定：

(1)結點統計：以ASCII碼的順序依次排列，例如：空格，英文句号，大寫字母，小寫字母。

(2)建構哈弗曼樹時：左子樹根結點權值小于等于右子樹根結點權值。

(3)選擇的根節點權值相同時，前者建構為雙親的左孩子，後者為右孩子。

(4)生成編碼時：左分支标0，右分支标1。

輸入

第一部分：封包内容，以’#'結束。

第二部分：待譯碼的編碼串。

輸出

依次輸出封包編碼串、譯碼串、平均碼長，三者之間均以換行符間隔。

平均碼長，保留小數點2位。

樣例輸入 Copy

Data structure is the way of computer storage and organization data. A data structure is a collection of data elements that exist between one or more specific relationships.#

000111111110101111110100101010000110111100010011011000001110011110011100101011010011100001101111011001011010101011001101110010101011101011110110101000110001101001010101010001111000101001110111111101000001101010100000010111111110101110110011111101001111010111011100000011110101111000100110000111011000000111101011111101001010100001101111000100110110000011100111100111011111101110010100000100001001111000100111101011101110101010110011000000111101011111100010000100110111000111101010100111001010110111110101100010110001011110010101100110000001010000110001001111011101010111010011101010100011010111010101000001110100110111100111100011110110001111110011010000010000111110100111101011101100110110101111011111001000100

樣例輸出 Copy

Data structure is the way of computer storage and organization data. A data structure is a collection of data elements that exist between one or more specific relationships.

4.11

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct hafutree
{
   char ch;
   int  parent;
   int  weight;
   int  lchild;
   int  rchild;
}hafutree;
float wt[200];
char ch_ch[200];
///初始化哈夫曼樹
hafutree **inithafutree(int wet[],char diff_zf[],int n)
{ 
  //printf("初始化哈夫曼樹\n");
  //getchar();
  hafutree **head;
  head=(hafutree **)malloc(sizeof(hafutree *)*n*2);
  for(int i=1;i<=n;i++)
  {
    head[i]=(hafutree *)malloc(sizeof(hafutree));
    head[i]->ch=diff_zf[i-1];
    head[i]->weight=wet[i-1];
    head[i]->parent=0;
    head[i]->lchild=0;
    head[i]->rchild=0;
  }
  for(int i=n+1;i<2*n;i++)
  {
    head[i]=(hafutree *)malloc(sizeof(hafutree));
    head[i]->ch='#';
    head[i]->weight=0;
    head[i]->parent=0;
    head[i]->lchild=0;
    head[i]->rchild=0;
  }
  return head;
}
///建立好哈夫曼樹
void create_hafutree(hafutree **head,int x)
{  
  //printf("建立哈弗樹\n");
  //getchar();
	int m,n;//m第一個最小，n第二個最小
	int k=x;//記錄下一次存放位置
	while(k<2*x-1)
   {
      for(int j=1;j<=k;j++)
        {
       if(head[j]->parent==0)
       	{
       	m=j;
       	break;
       	}
       }
    for(int i=1;i<=k;i++)
    { 
      if(head[m]->weight>head[i]->weight&&head[i]->parent==0)
      {
        m=i;
      }
    }
    for(int j=1;j<=k;j++)
      {
      	if(head[j]->parent==0&&m!=j)
      	{
      		n=j;
      		break;
      	}
      }			
    for(int i=1;i<=k;i++)
    { 
      if(i==m)
      {
      	continue;
      }
      if(head[n]->weight>head[i]->weight&&head[i]->parent==0)
      {
        n=i;
      }
    }
    head[++k]->weight=head[m]->weight+head[n]->weight;
    head[k]->lchild=m;
    head[k]->rchild=n;
    head[m]->parent=k;
    head[n]->parent=k;
  }
  /*getchar();
  printf("完成哈夫曼樹\n");
  for(int i=1;i<2*x;i++)
   {
     //printf("%d",head[i]->weight);
      printf("%d-節點值%c-",i,head[i]->ch);
       printf("父親%d-",head[i]->parent);
        printf("左孩子%d-",head[i]->lchild);
         printf("右孩子%d\n",head[i]->rchild);
   }
  getchar();*/
}
//對預處理的權值和資訊進行排序
void paixu(int getwt[],char getch[])
{ 
   int a;
   char b;
   for(int i=0;i<strlen(getch)-1;i++)
    {
      for(int j=0;j<strlen(getch)-1-i;j++)
      {
        if(getch[j]>getch[j+1])
      {
           b=getch[j+1];
           getch[j+1]=getch[j];
           getch[j]=b;
           a=getwt[j+1];
           getwt[j+1]=getwt[j];
           getwt[j]=a;
      }
      }
    }
    for(int i=0;i<strlen(getch);i++)
    {
      wt[i]=getwt[i];
    }
}
//計算碼長
/*void vacaluct(char **ch,int getwt[],char getch[],int n,int m)
{  
   printf("%d,%d",n,m);
   getchar();
   int sum=0;
    for(int i=1;i<=n;i++)
    { 
      printf("%d",getwt[i-1]);
      sum=sum+(getwt[i-1]/m)*strlen(ch[i]);
    }
   printf("%d",sum);

}*/
//得到不同字元資訊（名稱和權值）
hafutree **getdifferentchar(char *text,int *number)
{   
  hafutree **head;//傳回初始化後的哈弗樹
  int m=0;//表示text的總數
  int n=0;//記錄不同字元
  //int k=0;
  int flog=0;//用來做判斷不同字元條件
  char *getch;//儲存不同字元
  int *getwt;//儲存不同字元的權值
  for(int i=0;text[i]!='#';i++)
  {
    m++;
  }
  text[m]='\0';
  getch=(char *)malloc(sizeof(char)*m);
  getwt=(int *)malloc(sizeof(int)*m);
    for(int i=0;i<=m;i++)//初始化權值數組
  {
    getwt[i]=0;
  }
    getch[n]=text[n];
    getch[++n]='\0';
    for(int i=0;text[i]!='\0';i++)
    {    
      flog=0;
        for(int j=0;getch[j]!='\0';j++)
        {
          if(text[i]==getch[j])
          {
              getwt[j]++;
              flog=1;
              break;                                                                                                                                        
          }
          else
      {
      continue;
        }
        }
        if(flog==0)
        {
          getch[n]=text[i];
          getwt[n]++;
          getch[++n]='\0';
        }
    }
    //調用初始化函數
    *number=strlen(getch);
    paixu(getwt,getch);
    //strcpy(getch,".ADabcdefghilmnoprstuwxyz");
    //puts(getch);
    head=inithafutree(getwt,getch,strlen(getch));
    return head;
}
進行哈夫曼編碼
char **makecode(hafutree **head,int n)
{
   char a[n];
   int start;
   int p;
   int k;
   char **ch;
   ch=(char **)malloc(sizeof(char *)*n);
   ch[0]=(char *)malloc(sizeof(char)*5);
   for(int i=1;i<=n;i++)
   {
      start=n-1;
      a[start]='\0';
      p=head[i]->parent;
      k=i;
      while(p)
      {
        if(head[p]->lchild==k)
        {
          a[--start]='0';
        }
        else if(head[p]->rchild==k)
        {
        a[--start]='1';
        }
        k=p;
        p=head[p]->parent;
     }

     ch[i]=(char *)malloc(sizeof(char)*(n-start));
     strcpy(ch[i],&a[start]);
   }
   return ch;
}
///進行哈夫曼譯碼
char *translatecode(hafutree **head,char hafu_number[],int y)
{
  int k=0;//記錄邊緣後位置 
  int m,x,n;
  char *tr;
  tr=(char *)malloc(sizeof(char)*500);
  x=0;
  for(int i=k;hafu_number[i]!='\0';)
   { 
     m=2*y-1;
     n=i;
     while(head[m]->lchild&&head[m]->rchild)
    {
     if(hafu_number[n]=='0')
     {
        m=head[m]->lchild;
     }
     else if(hafu_number[n]=='1')
     {
        m=head[m]->rchild;
     }
     n++;
     i++; 
   }
   tr[x++]=head[m]->ch;
   tr[x]='\0';
  }
  return tr;
}
int main()
{
  char hafuch[500];//待編譯碼
  char hafu_number[1000];//待解譯碼
  char hafuch_num[1000]="";
	hafutree **head;
  char *tr;//儲存譯碼後的資訊;
  char **ch;
  int n;//記錄不同字元個數
  int j;
  gets(hafuch);
  gets(hafu_number);
  //初始化哈弗樹
  head=getdifferentchar(hafuch,&n);
  //建立好哈弗樹.
  create_hafutree(head,n);
  //哈弗編碼ch[]儲存資訊
  ch=makecode(head,n); 
  //哈弗譯碼
  //puts(hafuch);
  for(int i=0;hafuch[i]!='\0';i++)
  { 
    j=1;
    while(j<=n)
    { 
      if(head[j]->ch==hafuch[i])
      { 
        strcat(hafuch_num,ch[j]);
        break;
      }
      j++;
    }
  }
  puts(hafuch_num);
 // getchar();
  tr=translatecode(head,hafu_number,n);
  puts(tr);
 // getchar();
  float sum=0;
    for(int i=0;i<n;i++)
    { 
      //printf("%f,%d,%d,%f\n",wt[i],strlen(hafuch),strlen(ch[i+1]),wt[i]*strlen(ch[i+1])/strlen(hafuch));
     // getchar();
      sum=sum+wt[i]*strlen(ch[i+1])/strlen(hafuch);
     // getchar();
    }
   printf("%0.2f",sum);
  // printf("%f",sum);
}

《考研-資料結構-哈弗曼樹-已知某段通信封包内容，對該封包進行哈弗曼編碼，并計算平均碼長》

題目描述

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器