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