【文章內(nèi)容簡介】 算棧是一種后進先出的數(shù)據(jù)結構，在實際問題中還經(jīng)常使用一種“先進先出”的數(shù)據(jù)結構：即插入在表一端進行，而刪除在表的另一端進行，將這種數(shù)據(jù)結構稱為隊或隊列，把允許插入的一端叫隊尾(rear) ；把允許刪除的一端叫隊頭(front)。 隊列的存儲實現(xiàn)及運算實現(xiàn)與線性表、棧類似，隊列也有順序存儲和鏈式存儲兩種存儲方法。1．順序隊列循環(huán)隊列的類型定義如下：define MAXQSIZE 100 //最大隊列長度typedef struct {QElemType *base。 //動態(tài)分配存儲空間int front。 //頭指針，若隊列不空，指向隊列頭元素int rear。 //尾指針，若隊列不空，指向隊列尾元素的下一個位置} SqQueue。下面是循環(huán)隊列上基本操作的實現(xiàn)。（ 3）求循環(huán)隊列元素個數(shù)：int QueueLength（ SqQueue Q） {return (+MAXQSIZE) %MAXQSIZE；}2．鏈隊列鏈式存儲的隊稱為鏈隊列。和鏈棧類似，用單鏈表來實現(xiàn)鏈隊列，根據(jù)隊的先進先出原則，為了操作上的方便，分別需要一個頭指針和尾指針。定義一個指向鏈隊列的指針： LinkQueue Q。下面是鏈隊列的基本運算的實現(xiàn)。（ 1）入隊int EnQueue (LinkQueue amp。Q, QElemType e) {QNode *p。p = （ QNode *） malloc（ sizeof（ QNode）） 。pdata = e。pnext = NULL。next = p。 = p。return OK。}（ 2）出隊int DeQueue (LinkQueue amp。Q, QElemType amp。e) {if ( == ) return ERROR。 //隊空，出隊失敗p = next。e = pdata。 //隊頭元素放 e 中next = pnext。if(==p) = 。 //只有一個元素時，此時還要修改隊尾指針free (p)。return OK。}3．除了棧和隊列之外，還有一種限定性數(shù)據(jù)結構是雙端隊列。（ 1）雙端隊列：可以在雙端進行插入和刪除操作的線性表。（ 2）輸入受限的雙端隊列：線性表的兩端都可以輸出數(shù)據(jù)元素，但是只能在一端輸入數(shù)據(jù)元素。（ 3）輸出受限的雙端隊列：線性表的兩端都可以輸入數(shù)據(jù)元素，但是只能在一端輸出數(shù)據(jù)元素。 特殊矩陣的壓縮存儲 數(shù)組數(shù)組可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結構其特點是結構中的元素本身可以是具有某種結構的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標來標識，因此，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。通常在各種高級語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。現(xiàn)在來討論數(shù)組在計算機中的存儲表示。通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲結構，這是因為內(nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過一個映象函數(shù)，則可根據(jù)數(shù)組元素的下標得到它的存儲地址。對于一維數(shù)組按下標順序分配即可。對多維數(shù)組分配時，要把它的元素映象存儲在一維存儲器中，一般有兩種存儲方式：一是以行為主序（或先行后列）的順序存放，即一行分配完了接著分配下一行。另一種是以列為主序（先列后行）的順序存放，即一列一列地分配。以行為主序的分配規(guī)律是：最右邊的下標先變化，即最右下標從小到大，循環(huán)一遍后，右邊第二個下標再變， …，從右向左，最后是左下標。以列為主序分配的規(guī)律恰好相反：最左邊的下標先變化，即最左下標從小到大，循環(huán)一遍后，左邊第二個下標再變， …，從左向右，最后是右下標。設有 mn 二維數(shù)組 Amn，下面我們看按元素的下標求其地址的計算：以“以行為主序”的分配為例：設數(shù)組的基址為 LOC(a11)，每個數(shù)組元素占據(jù) d 個地址單元，那么 aij 的物理地址可用一線性尋址函數(shù)計算：LOC(aij) = LOC(a11) + ( (i1)*n + j1 ) * d這是因為數(shù)組元素 aij 的前面有 i1 行，每一行的元素個數(shù)為 n，在第 i 行中它的前面還有j1 個數(shù)組元素。在 C 語言中，數(shù)組中每一維的下界定義為 0，則：LOC(aij) = LOC(a00) + ( i*n + j ) * d推廣到一般的二維數(shù)組： A[c1..d1] [c2..d2]，則 aij 的物理地址計算函數(shù)為：LOC(aij)=LOC(a c1 c2)+( (i c1) *( d2 c2 + 1)+ (j c2) )d 特殊矩陣對于一個矩陣結構顯然用一個二維數(shù)組來表示是非常恰當?shù)模?矩陣在這種存儲表示之下，可以對其元素進行隨機存取，各種矩陣運算也非常簡單，并且存儲的密度為 1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，比如常見的一些特殊矩陣，如三角矩陣、對稱矩陣、對角矩陣、稀疏矩陣等，從節(jié)約存儲空間的角度考慮，這種存儲是不太合適的，看起來存儲密度仍為 1，但實際上占用了許多單元去存儲重復的非零元素或零元素，這對高階矩陣會造成極大的浪費，為了節(jié)省存儲空間，我們可以對這類矩陣進行壓縮存儲：即為多個相同的非零元素只分配一個存儲空間；對零元素不分配空間。對稱矩陣的特點是：在一個 n 階方陣中，有 aij=aji ，其中 1≤i , j≤n，對稱矩陣關于主對角線對稱，因此只需存儲上三角或下三角部分即可，比如，我們只存儲下三角中的元素 aij，其特點是中 j≤i 且 1≤i≤n，對于上三角中的元素 aij ，它和對應的 aji 相等，因此當訪問的元素在上三角時，直接去訪問和它對應的下三角元素即可，這樣，原來需要 n*n 個存儲單元，現(xiàn)在只需要 n(n+1)/2 個存儲單元了，節(jié)約了 n(n1)/2 個存儲單元。對下三角部分以行為主序順序存儲到一個向量中去，在下三角中共有 n*(n+1)/2 個元素，因此，不失一般性，設存儲到向量 SA[n(n+1)/2]中，存儲順序可用圖示意，這樣，原矩陣下三角中的某一個元素 aij 則具體對應一個 sak，下面的問題是要找到 k 與 i、 j 之間的關系。對于下三角中的元素 aij，其特點是： i≥j 且 1≤i≤n，存儲到 SA 中后，根據(jù)存儲原則，它前面有 i1 行，共有 1+2+…+i1=i*(i1)/2 個元素，而 aij 又是它所在的行中的第 j 個，所以在上面的排列順序中， aij 是第 i*(i1)/2+j 個元素，因此它在 SA 中的下標 k 與 i、 j 的關系為：k=i*(i1)/2+j1 (０≤kn*(n+1)/2 )若 ij，則 aij 是上三角中的元素，因為 aij=aji ，這樣，訪問上三角中的元素 aij 時則去訪問和它對應的下三角中的 aji 即可，因此將上式中的行列下標交換就是上三角中的元素在 SA中的對應關系：k=j*(j1)/2+i1 (０≤kn*(n+1)/2 )綜上所述，對于對稱矩陣中的任意元素 aij，若令 I=max(i,j)， J=min(i,j)，則將上面兩個式子綜合起來得到：k=I*(I1)/2+J1。（ 1）下三角矩陣與對稱矩陣類似，不同之處在于存完下三角中的元素之后，緊接著存儲對角線上方的常量，因為是同一個常數(shù)，所以存一個即可，這樣一共存儲了 n*(n+1)+1 個元素，設存入向量：（ 2）上三角矩陣對于上三角矩陣，存儲思想與下三角類似，以行為主序順序存儲上三角部分， 最后存儲對角線下方的常量。對角矩陣也稱為帶狀矩陣。，在這種三對角矩陣中，所有非零元素都集中在以主對角線為中心的對角區(qū)域中，即除了主對角線和它的上下方若干條對角線的元素外，所有其他元素都為零(或同一個常數(shù) c)。三對角矩陣 A 也可以采用壓縮存儲,將三對角矩陣壓縮到向量 SA 中去，按以行為主序，順序的存儲其非零元素，如圖所示，按其壓縮規(guī)律，找到相應的映象函數(shù)。第三章 樹與二叉樹 樹的概念樹（ Tree）是 n（ n≥0）個有限數(shù)據(jù)元素的集合。當 n＝0 時，稱這棵樹為空樹。在一棵非樹 T 中： 1）有一個特殊的數(shù)據(jù)元素稱為樹的根結點，根結點沒有前驅結點； 2）若 n1， 除根結點之外的其余數(shù)據(jù)元素被分成 m （ m0）個互不相交的集合 T1， T2，…Tm，其中每一個集合 Ti（ 1≤i≤m）本身又是一棵樹。樹 T1， T2， …， Tm 稱為這個根結點的子樹。2．相關術語（ 1）結點的度：結點所擁有的子樹的個數(shù)稱為該結點的度。（ 2）葉結點：度為 0 的結點稱為葉結點，或者稱為終端結點。（ 3）分支結點：度不為 0 的結點稱為分支結點，或者稱為非終端結點。一棵樹的結點除葉結點外，其余的都是分支結點。（ 4）孩子、雙親、兄弟：樹中一個結點的子樹的根結點稱為這個結點的孩子。這個結點稱為它孩子結點的雙親。具有同一個雙親的孩子結點互稱為兄弟。（ 5）路徑、路徑長度：如果一棵樹的一串結點 n1,n2,…,nk 有如下關系：結點 ni 是 ni+1 的父結點（ 1≤ik） ,就把 n1,n2,…,nk 稱為一條由 n1 至 nk 的路徑。這條路徑的長度是 k1。（ 6）祖先、子孫：在樹中，如果有一條路徑從結點 M 到結點 N，那么 M 就稱為 N 的祖先，而 N 稱為 M 的子孫。（ 7）結點的層數(shù)：樹的根結點的層數(shù)為 1，其余結點的層數(shù)等于它的雙親結點的層數(shù)加1。（ 8）樹的深度：樹中所有結點的最大層數(shù)稱為樹的深度。（ 9）樹的度：樹中各結點度的最大值稱為該樹的度。（ 10）有序樹和無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，即若交換了某結點各子樹的相對位置，則構成不同的樹，稱這棵樹為有序樹；反之，則稱為無序樹。（ 11）森林：零棵或有限棵不相交的樹的集合稱為森林。自然界中樹和森林是不同的概念，但在數(shù)據(jù)結構中，樹和森林只有很小的差別。任何一棵樹，刪去根結點就變成了森林。 二叉樹 定義與性質二叉樹（ Binary Tree）是 n 個有限元素的集合，該集合或者為空、或者由一個稱為根(root)的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結點。二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。（ 1）滿二叉樹在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。（ 2）完全二叉樹一棵深度為 k 的有 n 個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為 i（ 1≤i≤n）的結點與滿二叉樹中編號為 i 的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點是：葉子結點只能出現(xiàn)在最下層和次下層，且最下層的葉子結點集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。性質 1 一棵非空二叉樹的第 i 層上最多有 2i1 個結點（ i≥1）。（證明略）性質 2 一棵深度為 k 的二叉樹中，最多具有 2k－1 個結點。證明：設第 i 層的結點數(shù)為 xi（ 1≤i≤k），深度為 k 的二叉樹的結點數(shù)為 M， xi 最多為 2i1，則有：M＝ xi≤ 2i1 ＝2k1性質 3 對于一棵非空的二叉樹，如果葉子結點數(shù)為 n0，度數(shù)為 2 的結點數(shù)為 n2，則有:n0＝n2＋1。證明：設 n 為二叉樹的結點總數(shù)， n1 為二叉樹中度為 1 的結點數(shù)，則有：n＝n0＋n1＋n2 （式 131）在二叉樹中，除根結點外，其余結點都有唯一的一個進入分支。設 B 為二叉樹中的分支數(shù)，那么有：B＝n－1 （式 132）這些分支是由度為 1 和度為 2 的結點發(fā)出的，一個度為 1 的結點發(fā)出一個分支，一個度為 2 的結點發(fā)出兩個分支，所以有：B＝n1＋2n2 （式 133）綜合（式 131）、（式 132）、（式 133）式可以得到：n0＝n2＋1性質 4 具有 n 個結點的完全二叉樹的深度 k 為性質 5 對于具有 n 個結點的完全二叉樹，如果按照從上至下和從左到右的順序對二叉樹中的所有結點從 1 開始順序編號，則對于任意的序號為 i 的結點，有：（ 1）如果 i1，則序號為 i 的結點的雙親結點的序號為235。i / 2 ；如果 i＝1，則序號為 i 的結點是根結點，無雙親結點。（ 2）如果 2i≤n，則序號為 i 的結點的左孩子結點的序號為 2i；如果 2in，則序號為 i 的結點無左孩子。（ 3）如果 2i＋1≤n，則序號為 i 的結點的右孩子結點的序號為 2i＋1；如果 2i＋1n，則序號為 i 的結點無右孩子。此外，若對二叉樹的根結點從 0 開始編號，則相應的 i 號結點的雙親結點的編號為 ，左孩子的編號為 2i＋1，右孩子的編號為 2i＋2。 二叉樹的存儲1．順序存儲結構所謂二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹中的結點。一般是按照二叉樹結點從上至下、從左到右的順序存儲。這樣結點在存儲位置上的前驅后繼關系并不一定就是它們在邏輯上的鄰接關系，然而只有通過一些方法確定某結點在邏輯上的前驅結點和后繼結點，這種存儲才有意義。依據(jù)二叉樹的性質，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標值確定結點在二叉樹中的位置，以及結點之間的關系。對于一般的二叉樹，如果仍按從上至下和從左到右的順序將樹中