演算法WPL

❶ 哈夫曼樹演算法

題目的闡述：以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åâæBA­WPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33對應編碼為：A：221B：220C：21D：20E：1F：0

❷ 請描述哈夫曼演算法，並用圖描述構造哈夫曼樹的過程。

這個講的相當清楚。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）
然而怎樣構造一棵哈夫曼樹呢？最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述：
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對於編碼串：1010就可翻譯為bb或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點：一、對於過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網路，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

❸ 最優二叉樹演算法的基本概念

最優二叉樹，也稱哈夫曼（Haffman）樹，是指對於一組帶有確定權值的葉結點，構造的具有最小帶權路徑長度的二叉樹。
那麼什麼是二叉樹的帶權路徑長度呢？
在前面我們介紹過路徑和結點的路徑長度的概念，而二叉樹的路徑長度則是指由根結點到所有葉結點的路徑長度之和。如果二叉樹中的葉結點都具有一定的權值，則可將這一概念加以推廣。設二叉樹具有n個帶權值的葉結點，那麼從根結點到各個葉結點的路徑長度與相應結點權值的乘積之和叫做二叉樹的帶權路徑長度，記為：
WPL= Wk·Lk
其中Wk為第k個葉結點的權值，Lk 為第k個葉結點的路徑長度。如圖7.2所示的二叉樹，它的帶權路徑長度值WPL=2×2+4×2+5×2+3×2=28。
在給定一組具有確定權值的葉結點，可以構造出不同的帶權二叉樹。例如，給出4個葉結點，設其權值分別為1，3，5，7，我們可以構造出形狀不同的多個二叉樹。這些形狀不同的二叉樹的帶權路徑長度將各不相同。圖7.3給出了其中5個不同形狀的二叉樹。
這五棵樹的帶權路徑長度分別為：
（a）WPL=1×2+3×2+5×2+7×2=32
（b）WPL=1×3+3×3+5×2+7×1=29
（c）WPL=1×2+3×3+5×3+7×1=33
（d）WPL=7×3+5×3+3×2+1×1=43
（e）WPL=7×1+5×2+3×3+1×3=29
最優二叉樹演算法 最優二叉樹演算法
由此可見，由相同權值的一組葉子結點所構成的二叉樹有不同的形態和不同的帶權路徑長度，那麼如何找到帶權路徑長度最小的二叉樹（即哈夫曼樹）呢？根據哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉結點越靠近根結點，而權值越小的葉結點越遠離根結點。
哈夫曼（Haffman）依據這一特點於1952年提出了一種方法，這種方法的基本思想是：
（1）由給定的n個權值{W1，W2，…，Wn}構造n棵只有一個葉結點的二叉樹，從而得到一個二叉樹的集合F={T1，T2，…，Tn}；
（2）在F中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和；
（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，並將新建立的二叉樹加入到集合F中；
（4）重復（2）（3）兩步，當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

❹ 給定權3,4,5,6,7,8,9,試用演算法構造一棵最優二叉樹,畫出這棵樹並計算出...

建樹步驟：
3
4
5
6
7
8
9
7
5
6
7
8
9
7
11
7
8
9
11
14
8
9
11
14
17
25
17
42
建立後的最優二叉樹是這樣滴：(線和箭頭自己連一下吧汗~）
42
25
17
11
14
8
9
5
6
7
7
3
4
權(WPL):3*4+4*4+5*3+6*3+7*3+8*2+9*2=116

❺ 計算哈夫曼編碼

六個權值(頻率)是0.040.060.130.250.280.33

(1)從小到大排序0.040.060.130.250.280.33(這是有序序列)
(2)每次提取最小的兩個結點,取結點0.04和結點0.06,組成新結點N0.10,其權值=0.04+0.06=0.10,
取數值較小的結點作為左分支,結點0.04為左分支,結點0.06為右分支.
(3)將新結點N0.10放入有序序列,保持從小到大排序:
N0.100.130.250.280.33
(4)重復步驟(2),提取最小的兩個結點,N0.10與結點0.13組成新結點N0.23,其權值=0.10+0.13=0.23,
N0.10的數值較小,作為左分支,結點0.13就作為右分支.
(5)將新結點N0.23放入有序序列,保持從小到大排序:
N0.230.250.280.33
(6)重復步驟(2),提取最小的兩個結點,N0.23與結點0.25組成新結點N0.48,其權值=0.23+0.25=0.48,
N0.23的數值較小,作為左分支,結點0.25就作為右分支.
(7)將新結點N0.48放入有序序列,保持從小到大排序:
0.280.33N0.48
(8)重復步驟(2),提取最小的兩個結點,結點0.28與結點0.33組成新結點N0.61,其權值=0.28+0.33=0.61,
結點0.28的數值較小,作為左分支,結點0.33就作為右分支.
(9)將新結點N0.61放入有序序列,保持從小到大排序:
N0.48N0.61
(10)重復步驟(2),提取剩下的兩個結點,N0.48與N0.61組成新結點N1.09,其權值=0.48+0.61=1.09,
數值較小的N0.48作為左分支,N0.61就作為右分支.
有序序列已經沒有結點,得到"哈夫曼樹":

N1.09
/
N0.48N0.61
//
N0.230.250.280.33
/
N0.100.13
/
0.040.06

帶權路徑長度(WPL):
根結點N1.09到結點0.33的路徑長度是2,結點0.33的帶權路徑長度是0.33*2
根結點N1.09到結點0.28的路徑長度是2,結點0.28的帶權路徑長度是0.28*2
根結點N1.09到結點0.25的路徑長度是2,結點0.25的帶權路徑長度是0.25*2
根結點N1.09到結點0.13的路徑長度是3,結點0.13的帶權路徑長度是0.13*3
根結點N1.09到結點0.06的路徑長度是4,結點0.06的帶權路徑長度是0.06*4
根結點N1.09到結點0.04的路徑長度是4,結點0.04的帶權路徑長度是0.04*4
所以,哈夫曼樹的帶權路徑長度(WPL)等於
0.33*2+0.28*2+0.25*2+0.13*3+0.06*4+0.04*4=2.51

哈夫曼編碼:
規定哈夫曼樹的左分支代表0,右分支代表1.
從根結點N1.09到結點0.33,先後經歷兩次右分支,結點0.33的編碼就是11
從根結點N1.09到結點0.28,先經歷右分支,後經歷左分支,結點0.28的編碼就是10
從根結點N1.09到結點0.25,先經歷左分支,後經歷右分支,結點0.25的編碼就是01
從根結點N1.09到結點0.13,先經歷兩次左分支,後經歷右分支,結點0.13的編碼就是001
從根結點N1.09到結點0.06,先經歷三次左分支,後經歷右分支,結點0.06的編碼就是0001
從根結點N1.09到結點0.04,先後經歷四次左分支,結點0.04的編碼就是0000
得出所有結點的"哈夫曼編碼":
字元f(頻率0.33):11
字元e(頻率0.28):10
字元d(頻率0.25):01
字元c(頻率0.13):001
字元b(頻率0.06):0001
字元a(頻率0.04):0000


//C語言測試程序(來自其他網友)
//
//輸入構造哈夫曼樹中帶權葉子結點數(n)：6
//輸入6個整數作為權值：4613252833(將頻率的小數形式改為整數形式)
//可以得出哈夫曼樹的廣義表形式,帶權路徑長度,以及哈夫曼編碼.

#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};

//1、輸出二叉樹，可在前序遍歷的基礎上修改。
//採用廣義表格式，元素類型為int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//輸出根結點的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//輸出左子樹
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//輸出右子樹
printf(")");
}
}
}

//2、根據數組a中n個權值建立一棵哈夫曼樹，返回樹根指針
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指針數組，使每個指針元素指向a數組中對應的元素結點
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//進行n-1次循環建立哈夫曼樹
{
//k1表示森林中具有最小權值的樹根結點的下標，k2為次最小的下標
intk1=-1,k2;
//讓k1初始指向森林中第一棵樹，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//從當前森林中求出最小權值樹和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小權值樹和次最小權值樹建立一棵新樹，q指向樹根結點
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];

b[k1]=q;//將指向新樹的指針賦給b指針數組中k1位置
b[k2]=NULL;//k2位置為空
}
free(b);//刪除動態建立的數組b
returnq;//返回整個哈夫曼樹的樹根指針
}

//3、求哈夫曼樹的帶權路徑長度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始為0
{
if(FBT==NULL)//空樹返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//訪問到葉子結點
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//訪問到非葉子結點，進行遞歸調用，
{//返回左右子樹的帶權路徑長度之和，len遞增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}

//4、哈夫曼編碼（可以根據哈夫曼樹帶權路徑長度的演算法基礎上進行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值為0
{
//定義靜態數組a，保存每個葉子的編碼，數組長度至少是樹深度減一
staticinta[10];
inti;
//訪問到葉子結點時輸出其保存在數組a中的0和1序列編碼
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("權值為%d的編碼：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf("
");
}
else//訪問到非葉子結點時分別向左右子樹遞歸調用，
{//並把分支上的0、1編碼保存到數組a的對應元素中，
//向下深入一層時len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}

intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("輸入構造哈夫曼樹中帶權葉子結點數(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重輸n值：");
}
a=malloc(n*sizeof(ElemType));
printf("輸入%d個整數作為權值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("廣義表形式的哈夫曼樹：");
PrintBTree_int(fbt);
printf("
");
printf("哈夫曼樹的帶權路徑長度：
");
printf("=");
printf("
=%d
",WeightPathLength(fbt,0));
printf("樹中每個葉子結點的哈夫曼編碼：
");
HuffManCoding(fbt,0);

return0;
}

❻ 數據結構中什麼是排序演算法的穩定性

第一章 數據結構基本概念
1、基本概念：理解什麼是數據、數據對象、數據元素、數據結構、數據的邏輯結構與物理結構、邏輯結構與物理結構間的關系。
2、面向對象概念：理解什麼是數據類型、抽象數據類型、數據抽象和信息隱蔽原則。了解什麼是面向對象。由於目前關於這個問題有許多說法，我們採用了一種最流行的說法，即Coad與Yourdon 給出的定義：面向對象 = 對象 + 類 + 繼承 + 通信。
要點：
·抽象數據類型的封裝性
·面向對象系統結構的穩定性
·面向對象方法著眼點在於應用問題所涉及的對象
3、數據結構的抽象層次：理解用對象類表示的各種數據結構
4、演算法與演算法分析：理解演算法的定義、演算法的特性、演算法的時間代價、演算法的空間代價。
要點：·演算法與程序的不同之處需要從演算法的特性來解釋
·演算法的正確性是最主要的要求
·演算法的可讀性是必須考慮的
·程序的程序步數的計算與演算法的事前估計
·程序的時間代價是指演算法的漸進時間復雜性度量

第二章 數組
1、作為抽象數據類型的數組：數組的定義、數組的按行順序存儲與按列順序存儲
要點：
·數組元素的存放地址計算
2、順序表：順序表的定義、搜索、插入與刪除
要點：
·順序表搜索演算法、平均比較次數的計算
·插入與刪除演算法、平均移動次數的計算
3、多項式：多項式的定義
4、字元串：字元串的定義及其操作的實現
要點：
·串重載操作的定義與實現

第三章 鏈接表
1、單鏈表：單鏈表定義、相應操作的實現、單鏈表的游標類。
要點：
·單鏈表的兩種定義方式（復合方式與嵌套方式）
·單鏈表的搜索演算法與插入、刪除演算法
·單鏈表的遞歸與迭代演算法
2、循環鏈表：單鏈表與循環鏈表的異同
3、雙向鏈表：雙向鏈表的搜索、插入與刪除演算法、鏈表帶表頭結點的優點
4、多項式的鏈接表示

第四章 棧與隊列
1、棧：棧的特性、棧的基本運算
要點：
·棧的數組實現、棧的鏈表實現
·棧滿及棧空條件、抽象數據類型中的先決條件與後置條件
2、棧的應用：用後綴表示計算表達式，中綴表示改後綴表示
3、隊列：隊列的特性、隊列的基本運算
要點：
·隊列的數組實現：循環隊列中隊頭與隊尾指針的表示，隊滿及隊空條件
·隊列的鏈表實現：鏈式隊列中的隊頭與隊尾指針的表示、
4、雙向隊列：雙向隊列的插入與刪除演算法
5、優先順序隊列：優先順序隊列的插入與刪除演算法

第五章 遞歸與廣義表
1、遞歸：遞歸的定義、遞歸的數據結構、遞歸問題用遞歸過程求解
要點：·鏈表是遞歸的數據結構，可用遞歸過程求解有關鏈表的問題
2、遞歸實現時棧的應用
要點：·遞歸的分層（樹形）表示：遞歸樹
·遞歸深度（遞歸樹的深度）與遞歸工作棧的關系
·單向遞歸與尾遞歸的迭代實現
3、廣義表：廣義表定義、廣義表長度、廣義表深度、廣義表表頭、廣義表表尾
要點：
·用圖形表示廣義表的存儲結構
·廣義表的遞歸演算法

第六章 樹與森林
1、樹：樹的定義、樹的基本運算
要點：
·樹的分層定義是遞歸的
·樹中結點個數與高度的關系
2、二叉樹：二叉樹定義、二叉樹的基本運算
要點：
·二叉樹性質、二叉樹中結點個數與高度的關系、不同種類的二叉樹棵數
·完全二叉樹的順序存儲、完全二叉樹的雙親、子女和兄弟的位置
·二叉樹的前序·中序·後序·層次遍歷
·前序
·中序
·後序的線索化二叉樹、前驅與後繼的查找方法
3、霍夫曼樹：霍夫曼樹的構造方法、霍夫曼編碼、帶權路徑長度的計算
4、樹的存儲：樹的廣義表表示、樹的雙親表示、樹與二叉樹的對應關系、樹的先根·中根·後根·層次遍歷。
5、堆：堆的定義、堆的插入與刪除演算法
要點：
·形成堆時用到的向下調整演算法及形成堆時比較次數的上界估計
·堆插入時用到的向上調整演算法

第七章 集合與搜索
1、集合的概念：集合的基本運算、集合的存儲表示
要點：
·用位數組表示集合時集合基本運算的實現
·用有序鏈表表示集合時集合基本運算的實現
2、並查集：並查集定義、並查集的三種基本運算的實現
3、基本搜索方法
要點：
·對一般表的順序搜索演算法（包括有監視哨和沒有監視哨）
·對有序順序表的順序搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
·對有序順序表的折半搜索演算法、用判定樹（即擴充二叉搜索樹）描述搜索，以及平均搜索長度（成功與不成功）的計算。
4、二叉搜索樹：
要點：
·動態搜索樹與靜態搜索樹的特性
·二叉搜索樹的定義、二叉搜索樹上的搜索演算法、二叉搜索樹搜索時的平均搜索長度（成功與不成功）的計算。
·AVL樹結點上的平衡因子、AVL樹的平衡旋轉方法
·高度為h的AVL樹上的最少結點個數與最多結點個數
· AVL樹的搜索方法、插入與刪除方法

第八章 圖
1、圖：圖的定義與圖的存儲表示
要點：
·鄰接矩陣表示（通常是稀疏矩陣）
·鄰接表與逆鄰接表表示
·鄰接多重表(十字鏈表)表示
2、深度優先遍歷與廣度優先遍歷
要點：
·生成樹與生成樹林的定義
·深度優先搜索是個遞歸的過程，而廣度優先搜索是個非遞歸的過程
·為防止重復訪問已經訪問過的頂點，需要設置一個訪問標志數組visited
3、圖的連通性
要點：
·深度優先搜索可以遍歷一個連通分量上的所有頂點
·對非連通圖進行遍歷，可以建立一個生成森林
·對強連通圖進行遍歷，可能建立一個生成森林
·關節點的計算和以最少的邊構成重連通圖
4、最小生成樹
要點：
·對於連通網路、可用不會構成環路的權值最小的n-1條邊構成最小生成樹
·會畫出用Kruskal演算法及Prim演算法構造最小生成樹的過程
5、單源最短路徑
要點：
·採用逐步求解的方式求某一頂點到其他頂點的最短路徑
·要求每條邊的權值必須大於零
6、活動網路
要點：
·拓撲排序、關鍵路徑、關鍵活動、AOE網
·拓撲排序將一個偏序圖轉化為一個全序圖。
·為實現拓撲排序，要建立一個棧，將所有入度為零的頂點進棧
·關鍵路徑的計算

第九章 排序
1、基本概念：關鍵碼、初始關鍵碼排列、關鍵碼比較次數、數據移動次數、穩定性、附加存儲、內部排序、外部排序
2、插入排序：
要點：
·當待排序的關鍵碼序列已經基本有序時，用直接插入排序最快
3、選擇排序：
要點：
·用直接選擇排序在一個待排序區間中選出最小的數據時，與區間第一個數據對調，而不是順次後移。這導致方法不穩定。
·當在n個數據（n很大）中選出最小的5 ~ 8個數據時，錦標賽排序最快
·錦標賽排序的演算法中將待排序的數據個數n補足到2的k次冪2k-1<n≤2k
·在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。
4、交換排序：
要點：
·快速排序是一個遞歸的排序方法
·當待排序關鍵碼序列已經基本有序時，快速排序顯著變慢。
5、二路歸並排序：
要點：
·歸並排序可以遞歸執行
·歸並排序需要較多的附加存儲。可以採用一種"推拉法"（參見教科書上習題）實現歸並排序，演算法的時間復雜度為O (n)、空間復雜度為O(1)
·歸並排序對待排序關鍵碼的初始排列不敏感，排序速度較穩定
6、外排序
要點：
·多路平衡歸並排序的過程、I/O緩沖區個數的配置
·外排序的時間分析、利用敗者樹進行多路平衡歸並
·利用置換選擇方法生成不等長的初始歸並段
·最佳歸並樹的構造及WPL的計算

第十章 索引與散列
1、線性索引：
要點：
·密集索引、稀疏索引、索引表計算
·基於屬性查找建立倒排索引、單元式倒排表
2、動態搜索樹
要點：
·平衡的m路搜索樹的定義、搜索演算法
·B樹的定義、B樹與平衡的m路搜索樹的關系
·B樹的插入（包括結點分裂）、刪除（包括結點調整與合並）方法
·B樹中結點個數與高度的關系
·B+樹的定義、搜索、插入與刪除的方法
3、散列表
要點：
·散列函數的比較
·裝填因子 a 與平均搜索長度的關系，平均搜索長度與表長m及表中已有數據對象個數n的關系
·解決地址沖突的（閉散列）線性探查法的運用，平均探查次數的計算
·線性探查法的刪除問題、散列表類的設計中必須為各地址設置三個狀態
·線性探查法中的聚集問題
·解決地址沖突的（閉散列）雙散列法的運用，平均探查次數的計算
·雙散列法中再散列函數的設計要求與表長m互質，為此m設計為質數較宜
·解決地址沖突的（閉散列）二次散列法的運用，平均探查次數的計算
·注意：二次散列法中裝填因子 a 與表長m的設置
·解決地址沖突的（開散列）鏈地址法的運用，平均探查次數的計算

❼ 哈夫曼樹是什莫

哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權值Wi（i=1,2,...n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,...n）。
例子：
17
/ \
8 9
/ \
3 6
/ \
1 2
另外，補充一下，構造哈夫曼樹的主要目的是為了進行哈夫曼編碼，是一種用於無損數據壓縮的熵編碼（權編碼）演算法。也稱「霍夫曼編碼」，「赫夫曼編碼」。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，並發表於《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Rendancy Codes）一文。

❽ 兩道題，求詳細過程，講解的。

首先聲明，我沒學過數據結構，以下專業術語不正確的或者做錯了那麼。。。請自己翻書查相關的准確術語
nk=(k-1)n0+1
如果nk成為父節點有nk個，n0成為子節點有n0個。對於k叉樹而言，每當一個子節點拓展為一個父節點時，則子節點變為父節點即ak+=1同時a0-=1，同時子節點又多了k個即an+=k，兩式子聯立得每拓展一次時
ak+=1 a0+=k-1
又因為樹的根節點是沒有父親的，所以n0要再加1
就得到上面的關系了。

自己畫畫圖就出來了

第二題
樹的形狀如下圖
○
○ 8
○ 7
○ 4
○ 3
1 2
中間的線不知道怎麼畫，就是A的子女分別是B和8，B的子女分別是C和7，下同，最後的E的子女是1和2
WPL演算法 1*5+2*5+3*4+4*3+7*2+8*1 答案自己算（如果所有的路徑的權都是1的話。。）

哈弗曼數演算法如下
霍夫曼演算法
（1）由給定的n個權值構造具有n棵擴充二叉樹的森林F，其中每一棵擴充二叉樹只有一個帶有權值的根結點；
（2）在F中選取兩棵根結點的權值最小的擴充二叉樹作為左、右子樹構造一棵新的二叉樹，置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值的之和。在F中刪去這兩棵二叉樹，把新的二叉樹加入F；
（3）重復步驟（2）直到F中僅剩下一棵樹為止。

反正簡單的理解就是說越是小的數越是放下面，然後每個根節點下面就放一個帶有權的數，另一個當然就是根節點了，然後小的放下面，大的放上面，所謂WPL就是根節點到葉節點有幾條路徑，簡單來說就是幾條線，再乘以那個葉節點上的權值，然後都加起來就可以了。哈弗曼演算法是這樣的，怎麼證明的忘記了。。。

❾ 用huffman演算法求帶權為2，3，5，7，8的最優2元樹，要求畫出中間過程

7/8應該一起作為同一父的葉這樣才是最優，權為55

把最小的兩個數2、3放在最下面作為左右葉子節點，得出他們的父節點權值5，然後它和剩餘里最小的數5做成左右兄弟節點，得出父節點10，以此類推啊，10和7得出17，17和8，得到跟節點25完成。

例如：

先將所有的權值選出最小的兩個值，為1，4，這兩個的和為5，那麼再從5，9，25，36，49中選出兩個最小的，為5和9，然後再從14，25，36，49中選出兩個最小的，為14，25，依次進行下去。那麼就可以得到最優二叉樹為：（） / () 49 / () 36 / () 25 / () 9 / 1 4

(9)演算法WPL擴展閱讀：

所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。

樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權值Wi（i=1,2,...n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,...n）。可以證明哈夫曼樹的WPL是最小的。