哈氏演算法
Ⅰ 什麼是哈夫曼演算法
有一種樹形結構叫哈夫曼樹，用哈夫曼樹的方法解編程題的演算法就叫哈夫曼演算法，其實也沒有哈夫曼演算法這個專有名詞了拉，你這么問我就這么跟你講把。它產生的代碼是
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char ElemType;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // save the information of the symbolizes;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;
printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;
}
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1)
return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;++i)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(i=n+1;i<=m;++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].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-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]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
} // end of else if
} // end of if
} // end of for
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
return;
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
Ⅱ 哈夫曼演算法的概述
1.初始化： 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。
2. 找最小樹：在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 刪除與加入：在F中刪除這兩棵樹，並將新的二叉樹加入F中。
4. 判斷：重復前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹
Ⅲ 哈夫曼演算法的定義
定義：它是由n個帶權葉子結點構成的所有二叉樹中帶權路徑長度最短的二叉樹。
因為這種樹最早由哈夫曼（Huffman）研究，所以稱為哈夫曼樹，又叫最優二叉樹。
Ⅳ 本人沒有學過高等數學，是否可以通俗的解釋一下哈系演算法（hash）SHA-256的原理，最好能夠具體點！謝謝！
【哈希演算法】在【數據結構】課程裡面有提及，它是散列表查找中的一種思想，當然與編程緊密相連。
能力有限，無法解釋通透~~
Ⅳ 哈夫曼演算法
計算過程如圖所示：
Ⅵ 演算法有哪些分類
演算法分類編輯演算法可大致分為：
基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法，厄米變形模型，隨機森林演算法。
Ⅶ 請描述哈夫曼演算法，並用圖描述構造哈夫曼樹的過程。
1. 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。
2. 在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 在F中刪除這兩棵樹，並將新的二叉樹加入F中。
4. 重復前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹
幫你貼過來了，網路
這東西實際用法是可以減少樹的訪問次數，因為他把頻率高的點放在比較靠近根節點的地方，頻率低的在下面，這樣訪問速度快。舉個例子，比如四個點，他們的使用頻率分別是1,2,3,4，然後構成的樹就是
4
0 3
0 2
0 1
補：打不出樹形結構...
Ⅷ 哈夫曼樹演算法
題目的闡述：以N進制編碼方式對一個英文字串中的字元進行編碼，每個不同的字元其編碼不同．使得由新的編碼替代原串後總碼長最小，且輸入0，1，2，．．．，N－1構成的數字串後，依照該編碼方式可以正確的對譯出唯一的英文原串．如：N＝3英文原串為ABBCBADDACE其對應的一種編碼方式為A：00B：01C：020D：021E：022原串對譯後的編碼為000101020010002102100020022其碼長為27若輸入編碼串0102002200則對應的英文原串為BCEA 分析： 假設英文原串中的字元存放於字元集S中，‖S‖＝X，每個字元在字串中出現的概率為W［i］，L［i］為字元i的編碼長．依題意得，對S集合中的不同字元進行N進制編碼後要求1）新字串的碼長最短WPL＝∑W［i］＊L［i］
（i∈1．．X）使得在WPL是所有編碼方式中的最小值2）編碼無二義性任意一字元編碼都不為其它字元編碼的前綴 此題以哈夫曼樹來解答是非常適宜的．N為此哈夫曼樹的分叉數，S字元集里的元素即為此N叉哈夫曼樹的葉子，概率W［i］即為葉子結點的權重，從根結點到各葉子結點的路徑長即為該葉子結點的編碼長L［i］．由哈夫曼樹的思想可以知道哈夫曼樹的建立是一步到位的貪心法，即權重越大的結點越靠近該樹的根，這樣，出現頻率越大的字元其編碼就越短．但具體應該怎樣建立起此N叉哈夫曼樹呢？我們首先以N＝2為例：S＝｛A，B，C，D｝W＝［3，1，2，1］首先從W中選出兩個最小權，1，1，將其刪去，並以2（即1＋1）替代W＝［3，2，2］；再從新的W中取出兩個最小權，2，2，將其刪去，並以4（即2＋2）替代W＝［3，4］；依此類推，直到W中只一個值時合並結束，此時W＝［7］以上兩兩合並的過程即為二叉哈夫曼樹的建立過程，每一次的合並即是將兩棵子樹歸於一個根結點下，於是可以建立二叉樹如下： m0åæ1mmA0åæ1mmC0åæ1mmBD MIN－WPL＝3＊1＋1＊3＋2＊2＋1＊3＝13 從某一根結點出發走向其左子樹標記為0，走向其右子樹標記為1，則可以得到以下編碼A，B，C，D對應的編碼為A：0B：110C：10D：111
N＝3時又是怎樣一種情況呢？設S＝｛A，B，C，D，E｝W＝［7，4，2，5，3｝則按權重排序可得S＝｛D，B，E，C，A｝W＝［7，5，4，3，2］那麼此哈夫曼樹的樹形應為怎樣呢？是以下的左圖，還是右圖，或是兩者均不是mmåâæåæmmllmåæåæCAåælllllmADBEDåæ
lmBåællEC 顯然，要帶權路徑長WPL最短，那麼，此樹的高度就應盡可能的小，由此可知將此樹建成豐滿N叉樹是最合理的，於是我們盡量使樹每一層都為N個分枝．對於這道題的情況，我們具體來分析．按照哈夫曼樹的思想，首先從W中取出權最小的三個值，即2，3，4，並以9（2＋3＋4）來代替，得到新的W＝［9，7，5］；再將這三個值合並成9＋7＋5＝21這個結點．於是得到三叉哈夫曼樹如下：måâællmDBåâælllECAWPL＝1＊7＋1＊5＋2＊2＋2＊3＋2＊4＝30以0．．N－1依次標記每個根結點的N個分枝，則可以得到每個字元相對應的編碼：A：22B：1C：21D：0E：20我們發現對於這種情況恰巧每層均為N個分枝，但事實上並非所有的N叉哈夫曼樹都可得到每層N個分枝．例於當N＝3，‖S‖＝6時就不可能構成一棵每層都為三個分枝的三叉樹．如何來處理這種情況呢？最簡單的處理方式就是添加若干出現概率為0的空字元填補在N叉樹的最下一層，這些權為0的虛結點並無實際意義但卻非常方全便於這棵N叉樹的建立．空字元的添加個數add的計算如下：Y＝‖S‖mod（n－1）add＝0（Y＝1）add＝1（Y＝0）add＝N－Y（Y＞1） 虛結點的加入使得權重最小的N－add個字元構成了距根結點最遠的分枝，使其它字元構成的N叉樹保持了豐滿的N叉結構．例：N＝3S＝｛A，B，C，D，E，F｝W＝［1，2，3，4，5，6｝則y：＝6mod（3－1）＝0add＝1於是構成N叉樹如下：為虛結點¡åâællmFEåâællmDCåâæBAWPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33對應編碼為：A：221B：220C：21D：20E：1F：0
Ⅸ 本人沒有學過高等數學，不知可有高手用最通俗的方法闡述什麼是哈系演算法（hash）
比如字典里按筆畫數來查字，或是KTV里按歌名分三字歌，四字歌等，這樣的一個把字轉成筆畫數或歌名分類的演算法可以比喻成非常簡單的哈希演算法。
哈希演算法不可逆：就好比「大」字變成筆畫數後是3一樣，你不能通過3來確定它就是大字。
哈希演算法用於校驗：好比「大」字是3畫，你要是改變了這個字，變成了「太」字，於是結果是4畫，從而你知道這個字被改動了。
哈希演算法的碰撞：比如「大」「小」變成筆畫後都是3，這就是產生了碰撞。
當然這上面的比喻是非常淺顯的，也不是非常切合，只是助於理解一下概念。