欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++數(shù)據(jù)結(jié)構(gòu)與算法之哈夫曼樹的實現(xiàn)方法

 更新時間:2017年11月25日 11:48:50   作者:yunshouhu  
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)與算法之哈夫曼樹的實現(xiàn)方法,簡單說明了哈夫曼樹的原理,并結(jié)合具體實例形式分析了C++實現(xiàn)哈夫曼樹的相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了C++數(shù)據(jù)結(jié)構(gòu)與算法之哈夫曼樹的實現(xiàn)方法。分享給大家供大家參考,具體如下:

哈夫曼樹又稱最優(yōu)二叉樹,是一類帶權(quán)路徑長度最短的樹。

對于最優(yōu)二叉樹,權(quán)值越大的結(jié)點越接近樹的根結(jié)點,權(quán)值越小的結(jié)點越遠離樹的根結(jié)點。

前面一篇圖文詳解JAVA實現(xiàn)哈夫曼樹對哈夫曼樹的原理與java實現(xiàn)方法做了較為詳盡的描述,這里再來看看C++實現(xiàn)方法。

具體代碼如下:

#include <iostream>
using namespace std;
#if !defined(_HUFFMANTREE_H_)
#define _HUFFMANTREE_H_
/*
 * 哈夫曼樹結(jié)構(gòu)
 */
class HuffmanTree
{
public:
  unsigned int Weight;
  unsigned int Parent;
  unsigned int lChild;
  unsigned int rChild;
};
typedef char **HuffmanCode;
/*
 * 從結(jié)點集合中選出權(quán)值最小的兩個結(jié)點
 * 將值分別賦給s1和s2
 */
void Select(HuffmanTree* HT,int Count,int *s1,int *s2)
{
  unsigned int temp1=0;
  unsigned int temp2=0;
  unsigned int temp3;
  for(int i=1;i<=Count;i++)
  {
    if(HT[i].Parent==0)
    {
      if(temp1==0)
      {
        temp1=HT[i].Weight;
        (*s1)=i;
      }
      else
      {
        if(temp2==0)
        {
          temp2=HT[i].Weight;
          (*s2)=i;
          if(temp2<temp1)
          {
            temp3=temp2;
            temp2=temp1;
            temp1=temp3;
            temp3=(*s2);
            (*s2)=(*s1);
            (*s1)=temp3;
          }
        }
        else
        {
          if(HT[i].Weight<temp1)
          {
            temp2=temp1;
            temp1=HT[i].Weight;
            (*s2)=(*s1);
            (*s1)=i;
          }
          if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
          {
            temp2=HT[i].Weight;
            (*s2)=i;
          }
        }
      }
    }
  }
}
/*
 * 霍夫曼編碼函數(shù)
 */
void HuffmanCoding(HuffmanTree * HT,
          HuffmanCode * HC,
          int *Weight,
          int Count)
{
  int i;
  int s1,s2;
  int TotalLength;
  char* cd;
  unsigned int c;
  unsigned int f;
  int start;
  if(Count<=1) return;
  TotalLength=Count*2-1;
  HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];
  for(i=1;i<=Count;i++)
  {
    HT[i].Parent=0;
    HT[i].rChild=0;
    HT[i].lChild=0;
    HT[i].Weight=(*Weight);
    Weight++;
  }
  for(i=Count+1;i<=TotalLength;i++)
  {
    HT[i].Weight=0;
    HT[i].Parent=0;
    HT[i].lChild=0;
    HT[i].rChild=0;
  }
  //建造哈夫曼樹
  for(i=Count+1;i<=TotalLength;++i)
  {
    Select(HT, i-1, &s1, &s2);
    HT[s1].Parent = i;
    HT[s2].Parent = i;
    HT[i].lChild = s1;
    HT[i].rChild = s2;
    HT[i].Weight = HT[s1].Weight + HT[s2].Weight;
  }
  //輸出霍夫曼編碼
  (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
  cd = new char[Count*sizeof(char)];
  cd[Count-1]='\0';
  for(i=1;i<=Count;++i)
  {
    start=Count-1;
    for(c = i,f = HT[i].Parent; f != 0; c = f, f = HT[f].Parent)
    {
      if(HT[f].lChild == c)
        cd[--start]='0';
      else
        cd[--start]='1';
      (*HC)[i] = new char [(Count-start)*sizeof(char)];
      strcpy((*HC)[i], &cd[start]);
    }
  }
  delete [] HT;
  delete [] cd;
}
/*
 * 在字符串中查找某個字符
 * 如果找到,則返回其位置
 */
int LookFor(char *str, char letter, int count)
{
  int i;
  for(i=0;i<count;i++)
  {
    if(str[i]==letter) return i;
  }
  return -1;
}
void OutputWeight(char *Data,int Length,
         char **WhatLetter,
         int **Weight,int *Count)
{
  int i;
  char* Letter = new char[Length];
  int* LetterCount = new int[Length];
  int AllCount=0;
  int Index;
  int Sum=0;
  float Persent=0;
  for(i=0;i<Length;i++)
  {
    if(i==0)
    {
      Letter[0]=Data[i];
      LetterCount[0]=1;
      AllCount++;
    }
    else
    {
      Index=LookFor(Letter,Data[i],AllCount);
      if(Index==-1)
      {
        Letter[AllCount]=Data[i];
        LetterCount[AllCount]=1;
        AllCount++;
      }
      else
      {
        LetterCount[Index]++;
      }
    }
  }
  for(i=0;i<AllCount;i++)
  {
    Sum=Sum+LetterCount[i];
  }
  (*Weight) = new int[AllCount];
  (*WhatLetter) = new char[AllCount];
  for(i=0;i<AllCount;i++)
  {
    Persent=(float)LetterCount[i]/(float)Sum;
    (*Weight)[i]=(int)(1000*Persent);
    (*WhatLetter)[i]=Letter[i];
  }
  (*Count)=AllCount;
  delete [] Letter;
  delete [] LetterCount;
}
#endif
void main()
{
  HuffmanTree * HT = NULL;
  HuffmanCode HC;
  char Data[100];
  char *WhatLetter;
  int *Weight;
  int Count;
  cout<<"請輸入一行文本數(shù)據(jù):"<<endl;
  cin>>Data;
  cout<<endl;
  OutputWeight(Data,strlen(Data),
    &WhatLetter,
    &Weight,
    &Count);
  HuffmanCoding(HT, &HC, Weight, Count);
  cout<<"字符 出現(xiàn)頻率 編碼結(jié)果"<<endl;
  for(int i = 0; i<Count; i++)
  {
    cout<<WhatLetter[i]<<"   ";
    cout<<Weight[i]/1000.0<<"%\t";
    cout<<HC[i+1]<<endl;
  }
  cout<<endl;
}

希望本文所述對大家C++程序設計有所幫助。

相關(guān)文章

  • 聊聊C++ 運算符重載知識

    聊聊C++ 運算符重載知識

    運算符重載是一種形式的C++多態(tài),重載運算符可以使代碼看起來更加自然,下面通過例子介紹下C++ 運算符重載知識,感興趣的朋友一起看看吧
    2021-11-11
  • c++的virtual和override作用及說明

    c++的virtual和override作用及說明

    這篇文章主要介紹了c++的virtual和override作用及說明,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-11-11
  • 利用Matlab制作一款刮刮樂抽獎特效

    利用Matlab制作一款刮刮樂抽獎特效

    七夕節(jié)還不知道送啥,教你用MATLAB制作一款刮刮樂抽獎特效,讓她的手氣決定她的禮物。文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下
    2022-03-03
  • c語言經(jīng)典習題之逆序字符串詳解

    c語言經(jīng)典習題之逆序字符串詳解

    這篇文章主要為大家介紹了c語言習題之逆序字符串,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-01-01
  • C語言?超詳細講解算法的時間復雜度和空間復雜度

    C語言?超詳細講解算法的時間復雜度和空間復雜度

    算法復雜度分為時間復雜度和空間復雜度。其作用:?時間復雜度是度量算法執(zhí)行的時間長短;而空間復雜度是度量算法所需存儲空間的大小
    2022-03-03
  • C++ 實現(xiàn)求最大公約數(shù)和最小公倍數(shù)

    C++ 實現(xiàn)求最大公約數(shù)和最小公倍數(shù)

    這篇文章主要介紹了c++ 實現(xiàn)求最大公約數(shù)和最小公倍數(shù)的相關(guān)資料,需要的朋友可以參考下
    2017-05-05
  • C++ 實現(xiàn)輸入含空格的字符串

    C++ 實現(xiàn)輸入含空格的字符串

    這篇文章主要介紹了C++ 實現(xiàn)輸入含空格的字符串,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • 數(shù)據(jù)結(jié)構(gòu)串的操作實例詳解

    數(shù)據(jù)結(jié)構(gòu)串的操作實例詳解

    這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)串的操作實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-07-07
  • C/C++讀寫文本文件、二進制文件的方法

    C/C++讀寫文本文件、二進制文件的方法

    今天小編就為大家分享一篇C/C++讀寫文本文件、二進制文件的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-07-07
  • C++中的數(shù)據(jù)對齊示例詳解

    C++中的數(shù)據(jù)對齊示例詳解

    這篇文章主要介紹了C++中數(shù)據(jù)對齊的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-03-03

最新評論