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