軟件技術(shù)基礎(chǔ)：第一章 數(shù)據(jù)結(jié)構(gòu)

1、第一章數(shù)據(jù)結(jié)構(gòu)1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、直接前趨、直接后繼、邏輯關(guān)系（線性和非線性結(jié)構(gòu)）、存儲方法（順序和鏈式）、操作方法（遍歷，插入，更新，刪除，查找，排序）、抽象數(shù)據(jù)結(jié)構(gòu)1.2 線性結(jié)構(gòu)線性表（順序表和鏈表）、棧（順序棧和鏈棧）、隊列（順序隊列和鏈隊列）、數(shù)組（定義和壓縮存儲方式）1.3 非線性結(jié)構(gòu)樹（普通樹和二叉樹）、圖1.4 查找和排序基本概念、方法和算法實現(xiàn)、各方法的效率評估和比較1.1數(shù)據(jù)結(jié)構(gòu)的基本概念一、什么是數(shù)據(jù)結(jié)構(gòu) 計算機解一個有關(guān)數(shù)值計算的具體問題的步驟：建立數(shù)學模型設(shè)計解模算法編程調(diào)試輸出結(jié)果 建立數(shù)學模型的實質(zhì)是：分析實際問題，尋找包含

2、在問題中的操作對象，以及這些對象之間的關(guān)系，并用數(shù)學的語言對這些操作對象和其間的關(guān)系加以描述，這就是該問題的數(shù)學模型。數(shù)值計算問題中的數(shù)學模型通?？捎脭?shù)學方程來描述，但是更多的非數(shù)值計算的問題卻無法用數(shù)學方程來描述其數(shù)學模型。這三張查詢表就是學生成績查詢的數(shù)學模型，各元素間存在線性關(guān)系，因此這種數(shù)學模型稱為線性數(shù)據(jù)結(jié)構(gòu)。 例1 學生成績查詢 例2 人機對奕問題（五子棋） 對奕的過程是在一定的對奕規(guī)則和取勝策略下進行的，因此為使計算機能夠靈活對奕必須事先將對奕的規(guī)則、以及對奕過程中可能出現(xiàn)的情況和相應(yīng)的策略都存入計算機。在人機對奕過程中，計算機操作的對象是對奕過程中可能出現(xiàn)的棋局狀態(tài)（稱為格局）

3、。abcd 聯(lián)想一下，若將一局棋從開始到結(jié)束可能出現(xiàn)的格局都畫出來，可以得到下面一張圖： 因此，對奕問題中的數(shù)學模型就是以各種格局為元素的一種“樹”結(jié)構(gòu)?？梢钥闯鲞@種樹結(jié)構(gòu)中元素的關(guān)系不是簡單的線性關(guān)系，是另一種典型的數(shù)據(jù)結(jié)構(gòu)，稱為“樹結(jié)構(gòu)”。例3、利用交通燈進行多叉路口的交通管理問題。 本題中可以用一個圓圈表示一條通路，兩個通路之間的矛盾關(guān)系用對應(yīng)兩個圓圈的連線表示（圓圈稱為頂點、連線稱為邊），則設(shè)置交通燈的問題可以等價為對圓圈的染色問題。要求： 每個頂點染一種顏色。 相連的頂點不能染相同的顏色。 總色類最少。A BA CA DB AB CB DD AD BD CE AE BE CE D 它

4、是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科。 由此我們可以這樣來定義數(shù)據(jù)結(jié)構(gòu)： 用計算機來解決這類問題時，要處理的問題是諸如頂點和邊這樣的元素，數(shù)據(jù)結(jié)構(gòu)中稱這種為圖結(jié)構(gòu)，于是這類問題的數(shù)學模型就是圖這種數(shù)據(jù)結(jié)構(gòu)。 由此，至少要四種顏色的交通燈才能滿足保證交通秩序的要求。二、數(shù)據(jù)結(jié)構(gòu)中的有關(guān)基本概念 數(shù)據(jù)(data)：數(shù)據(jù)是指所有能輸入到計算機中并能被計算機程序處理的符號的總稱。1234567810101110ABCDEFG 數(shù)據(jù)元素(data element)：是數(shù)據(jù)結(jié)構(gòu)的基本單位。 數(shù)據(jù)項(data Item)：一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，它

5、是數(shù)據(jù)的不可分割的最小單位。 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 直接前驅(qū)、直接后繼：在數(shù)據(jù)結(jié)構(gòu)中的任意一個元素與之相鄰且在它之前的元素稱為該元素的直接前驅(qū)，與之相鄰且在它之后的元素稱為該元素的直接后繼。學生成績表對奕樹交通管理圖三、數(shù)據(jù)結(jié)構(gòu)的三個層次數(shù)據(jù)元素之間的邏輯關(guān)系線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)元素的存儲結(jié)構(gòu)線性存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的操作集合元素的遍歷，插入，更新，刪除，查找，排序1、數(shù)據(jù)元素之間的邏輯關(guān)系線性結(jié)構(gòu)：該結(jié)構(gòu)中有且僅有一個開始元素和結(jié)束元素，中間所有元素有且僅有一個直接前驅(qū)，有且僅有一個直接后繼，這樣的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。典型

6、的線性結(jié)構(gòu)有線性表，如：學生成績表。非線性結(jié)構(gòu)：該結(jié)構(gòu)中一個元素可能有多個直接前驅(qū)和多個直接后繼，這樣的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)。典型的非線性結(jié)構(gòu)為圖結(jié)構(gòu)，而樹是一種特殊的非線性結(jié)構(gòu)。線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)2、數(shù)據(jù)結(jié)構(gòu)的存儲方式順序存儲結(jié)構(gòu)：該方法是將邏輯關(guān)系相鄰的數(shù)據(jù)元素存儲在地址相鄰的存儲單元中。多用于線性結(jié)構(gòu)的存儲。各元素之間的邏輯關(guān)系是通過存儲單元(物理位置)的相鄰的關(guān)系來反映的。鏈式存儲結(jié)構(gòu)：該方法是用一組離散的存儲單元來存放數(shù)據(jù)結(jié)構(gòu)中的各元素。此方法中，每個元素所占的存儲單元分成兩部分：一部分為數(shù)據(jù)域，用于存儲數(shù)據(jù)元素本身；另一部分為指針域，指示其后繼或前驅(qū)元素的存儲地址，從而結(jié)構(gòu)中的

7、各數(shù)據(jù)元素間形成了一個鏈。存儲單元地址100130160190存儲單元地址P4300P1P23、數(shù)據(jù)結(jié)構(gòu)中常見的操作：遍歷：查看數(shù)據(jù)結(jié)構(gòu)中的所有數(shù)據(jù)元素。插入：添加新的元素到一個數(shù)據(jù)結(jié)構(gòu)中。刪除：將指定元素從數(shù)據(jù)結(jié)構(gòu)中去掉。更新：修改數(shù)據(jù)結(jié)構(gòu)中的某個數(shù)據(jù)元素。查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足條件的數(shù)據(jù)元素。排序：將數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素按指定的順序排列。元素間的邏輯關(guān)系是由指針來反映的。數(shù)據(jù)結(jié)構(gòu)的三個層次之間的關(guān)系邏輯關(guān)系與存儲結(jié)構(gòu)是否一一對應(yīng)？比如線性結(jié)構(gòu)對應(yīng)順序存儲方式，非線性結(jié)構(gòu)對應(yīng)鏈式存儲方式？不是，同一種邏輯關(guān)系可采用不同的存儲方法，比如線性結(jié)構(gòu)可以采用順序和鏈式存儲方式。同樣的同一種存儲方

8、法可以表達不同的邏輯關(guān)系，比如鏈式儲存方式可以存儲線性和非線性結(jié)構(gòu)。選擇何種存儲結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，主要是使其運算方便及根據(jù)算法的時空要求來具體確定。數(shù)據(jù)的運算不僅受到邏輯關(guān)系存儲結(jié)構(gòu)的影響，而且有其自身的特點不同的存儲結(jié)構(gòu)的運算是不同的，比如順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的插值算法就是不同。同樣的數(shù)據(jù)的運算有其本身的特點，對線性表上的插入、刪除運算限制僅在表的一端進行，則該線性表稱之為棧；而插入限制在表的一端進行，刪除限制在表的另一端進行的線性表稱為隊列。數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系、存儲結(jié)構(gòu)和操作集合要作為一個整體來理解，其中任何一個的改變會導致不同的數(shù)據(jù)結(jié)構(gòu)。四、抽象數(shù)據(jù)類型1、數(shù)據(jù)類型的定義：

9、是指一個值域和定義在這個值域上的一組操作集合的總稱。如：整型是定義在（-32768，32767）上的整數(shù)以及定義在該值域上的一組操作：+、-、*、/、%。高級語言中定義的這些數(shù)據(jù)類型，將用戶不必了解的細節(jié)都封裝在數(shù)據(jù)類型中，從而實現(xiàn)了信息的隱藏，完成了數(shù)據(jù)抽象。例：8 - 7 = 1 8的二進制代碼：00001000 7的二進制代碼：00000111 7的補碼： 11111001 8 - 7 = 8 + 7的補碼 = （00000001）二進制 =（1）十進制2、抽象數(shù)據(jù)類型（ADT）的定義：是指一個數(shù)學模型以及定義在該模型上的一組操作的集合。注意：定義中的數(shù)學模型既包含了數(shù)據(jù)類型概念中值域的

10、含義，還包含了非數(shù)值計算領(lǐng)域中的的含義。因此一方面ADT和數(shù)據(jù)類型的含義相同，另一方面ADT的范疇比數(shù)據(jù)類型的范疇更廣。3、ADT定義的格式：ADT數(shù)據(jù)類型名 數(shù)據(jù)對象：（數(shù)據(jù)對象的定義） 數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系的定義） 基本操作：（基本操作的定義） ADT抽象數(shù)據(jù)類型名 高級程序語言中不僅可以使用各種已有的數(shù)據(jù)類型，還可以根據(jù)用戶的需求自己定義新的數(shù)據(jù)類型。struct student int id ; char name20; int classes; float score4; elemtype;右邊的結(jié)構(gòu)體是否是一個完整的ADT定義？1.1 思考題1、分析一個具體的數(shù)據(jù)結(jié)構(gòu)如何入手？2、

11、常見的數(shù)據(jù)結(jié)構(gòu)有哪些？各有什么特征？3、抽象數(shù)據(jù)類型的含義？1.2 線性結(jié)構(gòu)線性結(jié)構(gòu)中數(shù)據(jù)元素的邏輯關(guān)系： 存在一個唯一的“開始元素”和一個唯一的 “結(jié)束元素”（有限性）。 其間任何一個元素都有且僅有一個直接前驅(qū)、 有且僅有一個直接后繼（有序性）。1.2.1 線性表一、定義： 線性表是由n(n0)個具有相同類型的元素 a1， a2， ， ai ， ， an , 所構(gòu)成的一個有限的線性序列。其中 n 為表長，ai 為線性表中的第i個元素， ai 可以是一個數(shù)，符號或其它更復雜的信息，但 ai 必須具有相同的數(shù)據(jù)類型。開始元素：無直接前趨，有且只有一個直接后繼結(jié)束元素：無直接后繼，有且只有一個直接

12、前趨典型線性結(jié)構(gòu)：線性表、堆棧、隊列、數(shù)組、串等(1,2,3,4,5,6,7)(SUN,MON,TUE,WED,THU,FRI,SAT)二、線性表的ADT定義ADT Linear_List 數(shù)據(jù)元素： ai具有相同的數(shù)據(jù)類型，1 i n 。 邏輯結(jié)構(gòu)： a1為“開始元素”無前驅(qū)； an為“結(jié)束元素” 無后繼；中間任何一個元素都存在以下關(guān)系： ( i=1,2,n-1 )。 操作集合：INITIATE（L）：初始化線性表。 LENGTH（L）；求表長，返回值為int 型。 GET（L，i )：訪問表中的第 i 個元素。 LOCATE（L，X）：定位，查找表中等于X的元 素的位置，返回值為 int

13、型。 INSERT（L，i, X)：在表L的第i個位置上插入X。 DELETE（L，i)：刪除表L中的第i個元素。 Linear_List ；LOCATE(L,X): 返回表中等于 X 的元素的序號i。 若表中有m(m1)個元素等于X， 則 返回序號最小的i。 若ai X，則返回（false)。INSERT(L,i,x): if(1i(LENGTH(L)+1) 則在L的第i個位置上插入X； n + + ; return ( true ); else return(flase);DELETE(L,i) : if( 1 i LENGTH(L) 刪除L中的第i個元素； n - ; return(刪除

14、的元素); else return(NIL);相關(guān)操作的具體含義 ADT定義了基本操作，更復雜的操作如將兩個線性表合成一個線性表，可由基本操作完成。例：已知存在線性表LA，LB，求LA=LA U LB。設(shè)兩 線性表中的元素的數(shù)據(jù)類型同為elemtype。 思路：以A表作為骨架構(gòu)造和鏈表，把B表中的每個元素依次取出，比較A表中有無該元素，沒有則把該元素插入到A表的最后即第i=n+1個位置上。這里比較A表中有無該元素的過程，可用定位操作來實現(xiàn)，把B表中取出的元素x在A表中做定位操作，若其返回值為1n的整數(shù)時說明元素x在A表中有，對求“并集”操作來講元素x無須插入到A表；若其返回值為false時，說

15、明A表中沒有元素x，此時應(yīng)插入。 1、求A表的長度：n=length(LA)； 2、用一個循環(huán)來依次取B表中的各元素：x=get (LB,i)； 3、把x在A表中定位：k=locate(LA,x)； 4、如果k= = false就將插入在A表的最后：insert (LA,n+1,x)； 5、表長加1：n+； #define true 1 #define false 0 void union (LA,LB) Linear_List LA,LB; int i,k,n; elemtype x ; n = LENGTH(LA); /* 取LA表的表長 */ for(i=1;i LENGTH(LB);i

16、+) x = GET(LB,i); /* 取LB表中的第 i 個元素 */ k = LOCATE( LA,x); /* x在LA中定位 */ if(k = false) /* 若LA中的元素 ai x */ INSERT(LA,n+1,x); /* 將x插入LA的后面*/ n + + ; /* 表長加1 */ 作業(yè)：假定A、B兩表都是遞增有序的線性表，設(shè)計一個程序利用以上基本操作，實現(xiàn)LA=LA U LB 得到的LA保持遞增有序。#define true 1 #define false 0 void union (LA,LB) Linear_List LA,LB; int i,k,n,j; e

17、lemtype x ; n = LENGTH(LA); /* 取LA表的表長 */ for(i=1;i LENGTH(LB);i+) x = GET(LB,i); /* 取LB表中的第 i 個元素 */ k = LOCATE( LA,x); /* x在LA中定位 */ if(k = false) /* 若LA中的元素 ai x */ If (x GET(LA,n) /*若x大于LA中最后一個元素，則在LA中n+1位置插入*/INSERT(LA,n+1,x); for (j=1;j GET(LA,j) & xnext=NULL;s =(node *)malloc(sizeof(node);s-d

18、ata = ai;p-next = s;p=s;p-next = NULL;ha1a2aianhpsa1a2spaianp設(shè)置一個前驅(qū)指針p：p=h;算法二、單鏈表的訪問算法。 PP P P單鏈表的訪問就是訪問單鏈表中的第 i 個元素。注意：單鏈表中任意兩個元素的存儲位置都沒有固定 的關(guān)系，每個元素的存儲位置僅包含在其前 驅(qū)結(jié)點的指針域中。 設(shè)p指針指向ai結(jié)點（數(shù)據(jù)域為ai的結(jié)點）， 則： p data=ai； p nextdata=ai+1； 因此，在單鏈表中訪問第i個元素必須從頭指針出發(fā)，依次尋找，直到找到第i個元素為止。PC語言實現(xiàn)：、未訪問到ai結(jié)點返回空元素。步驟：、p指向頭結(jié)點，

19、結(jié)點計數(shù)器j置0；、若p還未指向ai結(jié)點且未到表尾則p后移，j+；、找到結(jié)點訪問ai結(jié)點并返回ai ； p=h；j=0;while(jnext!=NULL) p=p-next; j+; if(j=i&p！=NULL) return(p-data);else return(NIL);尋找ai -1結(jié)點，判i是否有效。申請一個新結(jié)點t(tdata=x)。重新建立x和ai之間的鏈：tnext=pnext;重新建立 ai-1 和 x 之間的鏈：pnext=t;算法三、單鏈表的插入算法。INSERTSL（node *h,int i,elemtype x)的含義：已知線性表 sl= （a1,a2,a3,a

20、i-1,ai,an）要在ai-1 和 ai 之間插入 x 使 sl=（a1,a2,a3,ai-1,x,ai, an）。 t步驟：C語言實現(xiàn)： P能交換嗎？算法四、單鏈表的刪除算法。 單鏈表的刪除deletesl（node *h,int i)的含義：已知線性表 sl=（a1,a2,a3,ai -1,ai,ai +1,an）要去掉元素 ai ， 使：sl=（a1,a2,a3,ai-1,ai+1,an）。 P S(free(s)步驟： 尋找ai-1結(jié)點，判i是否有效； 重新建立ai-1和ai+1與x之間的鏈：Pnext=Snext； 釋放 ai 結(jié)點。C語言實現(xiàn)：注意：單鏈表的插入和刪除算法中都需要

21、判i是否有效，但判斷條件不一樣。4、循環(huán)單鏈表定義：將單鏈表中最后一個結(jié)點的指針指向頭結(jié)點， 從而使整個單鏈表形成一個環(huán)。邏輯示意圖：空循環(huán) 鏈表注意： 循環(huán)鏈表可以從任何一個結(jié) 點出發(fā)去訪問其他結(jié)點。 循環(huán)鏈表和單鏈表判定表的結(jié)束標志的方法不同： 循環(huán)單鏈表的結(jié)束標志：pnext= h；(書中為 *h) 單鏈表的結(jié)束標志：pnext = NULL ； 循環(huán)單鏈表的插入和刪除算法和單鏈表類似。例、將兩個鏈表(a1,a2,ai, an)和(b1,b2,bi, bn)合成一個新鏈表(a1,a2,ai,an,b1,b2,bi, bn)的算法。 qfree(*hb)步驟：遍歷A表，找到A表的尾結(jié)點an

22、。將B表的第一個結(jié)點b1連接到A表的尾結(jié)點an之后。遍歷B表，找到B表的尾結(jié)點bn。讓bn結(jié)點的指針指向A表的頭結(jié)點。釋放B表的頭結(jié)點。 Pq例、用尾指針表示的循環(huán)單鏈表來實現(xiàn)兩個鏈表的合并。步驟： 保留指向A表的頭結(jié)點的指針：p = ranext； 將A表的尾結(jié)點和B表的第一結(jié)點相連： ra next = rb next next； 保留指向B表的頭結(jié)點的指針：q = rbnext； 將B表的尾結(jié)點和A表的頭結(jié)點相連：rbnext = p； 釋放B表的頭結(jié)點：free(q)。 free(q) P5、雙鏈表定義：鏈表中結(jié)點的指針域中不僅包含了指向后繼結(jié)點的指針也包含了指向前驅(qū)結(jié)點的指針，這樣的

23、鏈表稱為線性雙鏈表。 雙鏈表結(jié)點的結(jié)構(gòu)：指向前驅(qū)結(jié)點的指針域數(shù)據(jù)域指向后繼結(jié)點的指針域 邏輯示意圖：注意： 從雙鏈表的任一結(jié)點出發(fā)均可訪問鏈表中所有 結(jié)點。 雙鏈表不須頭指針來標識，用指向表中的任一 結(jié)點的指針均可標識雙鏈表。 雙鏈表結(jié)點結(jié)構(gòu)的C 語言描述： typeded struct node_dl elemtype data; struct node *prior , *next ; node; 雙鏈表常見操作的C 語言實現(xiàn)算法一、插入算法已知：dL=（a1,a2,ai-1,ai, an），insertdL(dL,x,i)的含義是在dL中的 ai-1和 ai 元素之間插入x，使插入后的鏈

24、表dL= （a1,a2,ai-1,x,ai, an）。Pt算法二、刪除算法 已知：dL=（a1,a2,ai-1,ai,ai+1 ,an），deletedL(dL,i)的含義是將dL中的第個元素 ai 刪除，使刪除后的鏈表dL=（a1,a2,ai-1,ai+1, , an）。P free(P) 以上給大家介紹了順序表的兩種不同的存儲結(jié)構(gòu)：順序表和鏈表（單鏈表、循環(huán)單鏈表、雙鏈表）以及不同存儲結(jié)構(gòu)下的一些常見操作的實現(xiàn)方法。 順序表占用的存儲空間最少，而雙鏈表占用的存儲 空間最多。 順序表是一種隨機存儲結(jié)構(gòu)，訪問表中的某一個元 素方便；單鏈表元素的訪問則必須按照一定的順序 依次去尋找待訪問的元素。

25、 一個順序表一旦確定則其大小就不可以隨意改變， 因此其操作中不可避免地要進行“判滿”的工作， 而鏈表的大小卻可方便的改變，但鏈表占用的存儲 空間較多。 順序表的操作主要消耗在元素的移動上，效率較低， 單鏈表的操作消耗在指針的移動上，雙鏈表的操作 極為方便，但卻是建立在存儲空間的消耗上的。五、線性表的應(yīng)用 一元多項式相加任何一個一元多項式Pn(x)都可按升冪表示為： Pn(x) = P0 +P1x + P2x2 + + Pixi + + Pnxn 可見Pn(x)由n+1個系數(shù)（ P0，P1， ，Pi， ，Pn）唯一確定，可用一個線性表P來表示系數(shù)的集合，其中Pi(x)項的指數(shù)隱含在系數(shù)Pi中。該

26、線性表可表示為： P= （ P0， P1， ， Pi， ， Pn）表長為n+1。 同理，再設(shè)一個一元多項式Qm(x)，此多項式也可由一個線性表Q =（Q0，Q1，Qi，Qm）表長為m+1來表示。若要計算： Rn(x) = Pn(x)+ Qm(x)，這里不失一般性，假定mn。 Rn(x) 也可用線性表R=(p0+q0，p1+q1，pm+qm，pm+1，pn）來表示，這時顯然可以用順序表的形式來表示和處理這種一元多項式和一元多項式的相加。 i+= 但是，若已知多項式為 S（x）= 1+3x10000+5x30000 ，此時再用將指數(shù)項隱含在系數(shù)中的方式，用系數(shù)順序表來表示S（x），則其表長為300

27、01，而表中只有3個非零元素，浪費了大量的存儲空間。因此，一般情況下的一元n次多項式 Pn(x) = P1xe1 + P2xe2 + + Pixei+ + Pmxem ， 其中Pi為系數(shù)項，為ei指數(shù)項這時可用一個線性表R=(P1 ,e1), (P2 ,e2), ， (Pm ,em) )來表示。其中元素數(shù)據(jù)類型和順序表的C語言描述為：typedef struct poly float coef ; int exp ; elemtype ;typedef struct polynty elemtype dataMaxnum; int num; polynty;12mMaxnum 以上，用順序表的

28、形式表示了一元多項式，這種方式表示的一元多項式適用于其運算僅用于求值等不用修改多項式系數(shù)或指數(shù)項（即不進行插入、刪除等改變元素間的邏輯關(guān)系的操作）時。而一元多項式的加法運算的實現(xiàn)，須涉及到插入、刪除等改變元素邏輯關(guān)系的操作，則應(yīng)采用單鏈表來表示一元多項式。一元多項式單鏈表表示結(jié)點的C語言描述為：typedef struct node float coef; int exp ; struct node *next ; node ;數(shù)據(jù)域 指針域 一元多項式相加的實現(xiàn)方法： 指數(shù)相同的項系數(shù)相加，若其和不為零則構(gòu)成“和 多項式”中的一項。 所有指數(shù)不同的項均插入到“和多項式中”。例已知：A4(X)

29、=7+3X+9X8+5X17 B3(X)=8X+22X7- 9X8 求：C(X) = A4(X) + B3(X) P qP方法和步驟：在其中一個鏈表的基礎(chǔ)上構(gòu)造“和多項式”將p,q指針分別指向A，B鏈表的第一個結(jié)點。依次比較p,q指針所指向結(jié)點的數(shù)據(jù)域中的指數(shù)項。P q qif (p exp q exp ) q結(jié)點為和多項式的結(jié)點，將其插入到p結(jié)點之前； q指針后移； 一直比較到兩表中有一張表已到結(jié)束結(jié)點為止： if( A表到頭： pnext=NULL) 將B表中剩余的結(jié)點插入到A表之后； 釋放B 表的頭結(jié)點。C語言實現(xiàn)：1.2.1 思考題及作業(yè)1、線性數(shù)據(jù)結(jié)構(gòu)按其存儲方式的不同可分 為哪幾種

30、線性表？各有哪些區(qū)別？2、請畫出順序表插入和刪除程序的流程圖。4、鏈表由可分為單鏈表、雙鏈表、循環(huán)鏈 表等，有哪些區(qū)別？各適用于什么地方？3、請畫出單鏈表插入和刪除程序的流程圖。5、請畫出一元多項式相加程序的流程圖。 寫出源程序。1.2.2棧和隊列棧和隊列是常用的數(shù)據(jù)結(jié)構(gòu)它和線性表的關(guān)系在于：邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)與線性表相同。一、棧(stack)1、棧的基本概念定義：是限定在表尾進行插入和刪除的線性表。表尾的一端稱為棧頂，表頭的一端稱為棧底。棧底棧頂pushpop設(shè)棧 S=（ a1,a2,a3,ai, an），則a1為棧底元素， an為棧頂元素，棧的修改是按后進先出的原則進行的，因此棧又稱為后進

31、先出的線性表（LIFO）。操作集合是線性表的操作集合的子集，即是操作受限。2、棧的ADT定義ADT stack 數(shù)據(jù)元素： ai具有相同的數(shù)據(jù)類型， ai S 1 i n 。 邏輯結(jié)構(gòu)： a1為棧底元素； an棧頂元素；中間任何一個元素 都存在一種關(guān)系： ( i=1,2, ,n-1 )。 操作集合：SETNULL（S）：初始化棧，把棧設(shè)為空棧。 EMPTY（S）；判斷是否為空棧。 if (S為空）return (true); else return (false); PUSH（S，x )：進棧操作，即在棧頂插入元素x。 POP（S）：出棧操作，若棧不為空刪除棧頂元素。 TOP（S）：訪問棧頂元

32、素an ，不改變棧的內(nèi)容。 stack ；注意：這些操作都限制在表尾（棧頂）的一端進行。判空3、棧的存儲結(jié)構(gòu)：棧是操作受限的線性表，順序棧和鏈棧 順序棧：利用一組地址連續(xù)的存儲單元依次存放從棧底 到棧頂?shù)脑亍?typedef struct elmtype dataMaxnum; int top; stacktype; top=0 Atop=-1 ?？誸op=4 E D C B A top=2 C B A注意：在順序棧結(jié)構(gòu)的C語言描述中，Maxnum表示順序棧的最大長度，top 和順序表中num的含義不一致：num為表中實際元素的個數(shù)；top為棧中棧頂元素的數(shù)組下標值。假定定義一個數(shù)組data

33、5 來表示一個順序棧。43210順序棧的C語言描述：top=0 插入A元素top=4 棧滿指向指針的指針：int *ppi;ppi是一個特殊的指針變量，它存放著另外一個指針的地址int i,*pi, *ppi; pi=&i; ppi=*pi=i *ppi=pi *ppi=*pi=i 算法一、初始化棧使棧頂指針為一個無效值。C 語言中將此值定義為-1。算法二、進棧操作 設(shè)棧 S=（a1,a2,a3,ai,an）， PUSH（S，x）的含義是：通過操作使棧 S=（a1,a2,a3 ,ai,an，x），但是插入之前要檢測是否棧滿。步驟：若棧滿的話，返回“false”，程序結(jié)束。棧頂指示器的值加1。（

34、top+ +）將x放入棧頂指示器指示的存儲單元。返回“true”，程序結(jié)束。算法三、出棧操作 設(shè)棧 S=（a1,a2,a3,ai,an-1,an），POP（S）的含義是：通過操作使棧 S=（a1,a2,a3,ai,an-1），但是刪除之前要檢測是否?？铡２襟E：若?？盏脑?，返回“NIL”，程序結(jié)束。棧頂指示器的值減1。（top- -）返回刪除的棧頂元素。順序棧操作的特點：同順序表的操作相比較簡單的多，即操作受限。“上溢”的問題同樣不能圓滿解決，而當一個程序中使用多個棧時，常常會發(fā)生一個棧滿，而另外的棧非滿甚至為空的情況，使得資源的利用率很低。鏈棧：是采用一組地址不連續(xù)的存儲單元來存放棧中各元 素

35、，棧中各元素的邏輯關(guān)系用指針來表示。結(jié)構(gòu)示意圖：注意： 在單鏈表中表中第一個結(jié)點為a1結(jié)點，而在鏈棧中 第一個結(jié)點是an結(jié)點。 鏈棧中沒有頭結(jié)點。 鏈棧和單鏈表一樣也用頭指針(top)來唯一的標識。鏈棧結(jié)點結(jié)構(gòu)的C語言描述：typedef struct node elemtype data; struct node *next; node;算法一、進棧操作toptop步驟： 申請P結(jié)點： P data = x; P結(jié)點和棧頂結(jié)點(an結(jié)點)相連： Pnext= top; 重置棧頂指針： top = P;C語言實現(xiàn)：算法二、出棧操作top free(p) P步驟： 讓P指針指向棧頂結(jié)點： P =

36、 top 修改棧頂指針： top = top next 釋放原棧頂結(jié)點（ an結(jié)點）： free( P ) 鏈棧的引入解決了棧的上溢問題，由于鏈棧的結(jié)點是動態(tài)產(chǎn)生的，因此只有在整個內(nèi)存空間都被占滿，malloc過程無法實現(xiàn)時才會出現(xiàn)上溢的情況，從而實現(xiàn)了多個棧的空間共享。C語言實現(xiàn)： top設(shè)依次進入一個棧的元素序列為a,b,c,d,e,不可得到出棧的元素序列有_。( )(A) a,d,c,b,e(B) b,a,d,c,e(C) d,c,e,b,a(D) c,a,b,d,e二、隊列(queue)1、隊列的基本概念定義：是限定在表尾進行插入，在表頭進行刪除的線性表。表尾的一端稱為隊尾，表頭的一端

37、稱為隊頭。12n出隊列端入隊列端（隊尾）（隊頭） 隊列和我們?nèi)粘Ｉ钪械呐抨犚粯?，最早進入隊列的元素最先離開，因此稱隊列為先進先出(FIFO)的線性表。2、隊列的ADT定義ADT queue 數(shù)據(jù)元素： ai具有相同的數(shù)據(jù)類型，1 i n 。 邏輯結(jié)構(gòu)： a1為隊頭元素； an隊尾元素；中間任何一個元素 都存在一種關(guān)系： ( i=1,2,n-1 )。操作集合：SETNULL（Q）：初始化隊列。 EMPTY（Q）；判斷是否為空隊列。 if (Q為空）ruturn (true); else return (false); ENTER（Q，x )：入隊列，即在隊尾插入元素x。 DELETE（Q）：出

38、隊列，即刪除隊頭元素。 GETHEAD（Q）：訪問隊頭元素an 。 queue ；3、隊列的存儲結(jié)構(gòu)： 順序隊列：利用一組地址連續(xù)的存儲單元依次存放從隊 尾到隊頭的元素。通常以一個隊頭指示器 front 和一個隊尾指示器 rear 來描述隊列。順序隊列結(jié)構(gòu)的C語言描述：判空判空判滿？typedef struct elmtype dataMaxnum+1; int front, rear ; queuetype;543210front rear 假定以數(shù)組data6來定義一個隊列。如右圖所示： rear=front=0 ：隊空 rear=3; front =0 rear=5=Maxnum; fr

39、ont = 0 ; 隊滿rear a3 a2 a1front rear a5 a4 a3 a2 a1front 算法一、入隊列操作（插入算法） 設(shè)棧 Q =（ a1,a2,a3,ai,an）， ENTER（Q，x）的含義為：若Q滿則入隊列操作無效，否則Q=（a1,a2,a3,ai, an , x）。data0空int enter(queuetype *q,elemtype x) Maxnum n+1 n 2 1 0 an a2 a1 x front=0rear=nrear=n+1實現(xiàn)： 如果隊滿（rear=Maxnum）則插入無效，返回插入出錯的的信息。 否則，隊尾指示器加1，并將 x 插入到

40、新的隊尾位置。返回插入成功的信息。算法二、出隊列操作（刪除算法） 設(shè)棧 Q=（a1,a2,a3,ai,an），DELETE（Q）的含義為：若Q空則出隊列操作無效，否則Q=（a2,a3,ai,an）。 Maxnum n+1 n 2 1 0 an a2 a1front= 0front= 1rear= nelemtype delete(queuetype *q ) 實現(xiàn)： 如果隊空則刪除無效，返回空元素。 否則，隊頭指示器加1，并返回刪除的元素。Rear a5 a4 a3 a2 a1front rear front順序隊列的假溢出現(xiàn)象： rear=5=Maxnum; front=0 ;隊滿刪除隊列中

41、的五個元素，即： rear=5; front=5 ;此時，隊列為空，還是為滿？為解決順序隊列的假溢出現(xiàn)象，可采用循環(huán)隊列。rear a7 a6 a5 a4 a3 a2 a1front 76543210循環(huán)隊列： 在循環(huán)隊列的結(jié)構(gòu)中，將data0看作是datamaxnum-1的下一個相鄰的位置。循環(huán)隊列的C語言描述：typedef struct elmtype datamaxnum; int front, rear ; queuetype;指示器的移動：一般隊列和循環(huán)隊列的區(qū)別：一般隊列循環(huán)隊列front + + ( front + + ) % Maxnumrear + + ( rear + +

42、 ) % Maxnumrear a7 front rear front rear a1front rear front front rear a8rear front 不同操作中的空條件 front = rear front = rear 初始化空 front=rear= 0 front=rear=0 操作中的滿條件 rear =Maxnum front=(rear+1)% Maxnum 有關(guān)循環(huán)隊列的操作和一般隊列一致，僅僅是判空和判滿的條件發(fā)生了變化。 鏈隊列：是采用一組地址不連續(xù)的存儲單元來存放隊列中 各元素，隊列中各元素的邏輯關(guān)系用指針來表示。 設(shè)隊列 q =（a1,a2,a3 ,ai

43、,an），其結(jié)構(gòu)示意圖為：空隊列的結(jié)構(gòu)示意圖：鏈隊列結(jié)點結(jié)構(gòu)的C語言描述：typedef struct node elemtype data; struct node *next; node;typedef struct qtype node *front ; node *rear ; qtype;算法一、入鏈隊列操作（插入算法） 入鏈隊列的操作和鏈表的操作相似，僅僅是插入操作被限定在隊尾進行而已。其含義和入順序隊列一致。p rearrear步驟： 申請待插入的 x 結(jié)點，以p指針指向該結(jié)點，賦值。 進行 an 結(jié)點和 x 結(jié)點的連接。 鏈隊列的尾指針指向 x 結(jié)點。能否交換？算法二、出鏈隊列

44、操作（刪除算法） 出鏈隊列的操作和鏈表的操作相似，僅僅是刪除操作被限定在隊頭進行而已。其含義和出順序隊列的含義一致。 pfree(p)步驟： 以p指針指向鏈隊列的第一個結(jié)點: p=front-next; 進行頭結(jié)點和a2 結(jié)點的連接: front-next=p-next; 釋放被刪除的a1 結(jié)點: free(p);注意：若隊列中僅有一個元素，刪除后則為空隊列。因此刪除后還要修改尾指針，使其也指向頭結(jié)點，表示隊列已空。1.2.2 思考題及作業(yè)1、棧和隊列各有哪些基本特征？2、設(shè)一個棧的輸入序列是1,2,3,4,寫出該 棧的所有可能的輸出序列。3、進一步理解循環(huán)隊列的判空和判滿的條件。1.2.3

45、數(shù)組一、二維數(shù)組的ADT定義：ADT Array 數(shù)據(jù)元素：D=aij|aijelemtype 1in & 1jm 邏輯關(guān)系：R=|(1in-1 & 1jm)& |(1in & 1jm-1) 操作集合：Value(A,i,j)：給定數(shù)組元素的下標，求數(shù) 組元素的值。 Assign(A,x,i,j)：修改指定下標的元素的值。 ADT Array；二、二維數(shù)組中元素的邏輯關(guān)系：已知一個二維數(shù)組Anm行下標列下標A= 由于，二維數(shù)組中任意一個元素aij，都有兩個直接前驅(qū)和兩個直接后繼，因此它不是一般意義上的線性表。但它的每一行和每一列都是一個線性表。a1 1 , a1 2 , ,a1 j-1, a1

46、 j, a1 j+1, , a1 ma2 1 , a2 2 , ,a2 j-1, a2 j, a2 j+1, , a2 m ai-1 1 , ai-1 2,ai-1 j-1, ai-1 j, ai-1 j+1, ai-1 mai 1 , ai 2 ,ai j-1, ai j, ai j+1, , ai mai+1 1 , ai+1 2,ai+1 j-1, ai+1 j, ai+1 j+1, ai+1 m an 1 , an 2, , an j-1, an j, an j+1, , an m我們?nèi)粢孕邢蛄炕蛄邢蛄縼肀硎径S數(shù)組的話，則有： A= (1,2, ,i, ,p ) 其中 p = m 或

47、 n當i是一個列向量時：i=(a1i,a2i, ,an,i) 0im 當i是一個行向量時：i=(ai1,ai2, ,ai m) 0in 若以行向量或列向量來作為二維數(shù)組的元素的話，則可將二維數(shù)組視為一個線性表，前者稱為列主序的線性表，后者稱為行主序的線性表。三、二維數(shù)組的存儲結(jié)構(gòu) 數(shù)組的存儲結(jié)構(gòu)一般采用順序存儲結(jié)構(gòu)，這是由于存儲單元是一維的，因此在處理二維甚至多維數(shù)組的存放時有一個次序的問題。對二維數(shù)組而言，可以按行優(yōu)先方式存儲，也可按列優(yōu)先方式存放。在C語言中二維數(shù)組采用行優(yōu)先方式存放，即按以下次序存放：a11,a12,a1.m,a21,a22,a2.m ,an,1,an,2,an,m 由此

48、不難看出，數(shù)組中每個元素的存儲地址可以有下式方便地求出：Loc( aij ) = Loc( a11 )+(i-1) * m+(j-1) * s 其中： s 為每個元素所占用的存儲單元的 byte 數(shù) 同理，也有列優(yōu)先的存儲方式，但無論哪種存儲方式，只要給定下標，便可很方便地存取該元素，以上表達式可推廣到多維數(shù)組。四、矩陣的壓縮存儲 一般而言矩陣的存儲采用和二維數(shù)組類似的存儲結(jié)構(gòu)，但對于一些結(jié)構(gòu)特殊的矩陣如：對稱矩陣、稀疏矩陣等，套用一般數(shù)組的存儲結(jié)構(gòu)則會帶來存儲空間的浪費。壓縮存儲的含義是：值相同的元素僅分配一個存儲單元，而零元素不分配存儲單元等等一些特殊的存儲方式。A=從a1 1到ai j一

49、共（i-1）m+j個數(shù)據(jù)元素，另外由于從a1 1作為起始位算起，所以公式為Loc( aij ) = Loc( a11 )+(i-1) * m+(j-1) * s相似的，對于列優(yōu)先的每個元素的存儲地址為Loc( aij ) = Loc( a11 )+(j-1) * n+(i-1) * sa1 1 , a1 2 , ,a1 j-1, a1 j, a1 j+1, , a1 ma2 1 , a2 2 , ,a2 j-1, a2 j, a2 j+1, , a2 m ai-1 1 , ai-1 2,ai-1 j-1, ai-1 j, ai-1 j+1, ai-1 mai 1 , ai 2 ,ai j-1,

50、 ai j, ai j+1, , ai mai+1 1 , ai+1 2,ai+1 j-1, ai+1 j, ai+1 j+1, ai+1 m an 1 , an 2, , an j-1, an j, an j+1, , an m(i-1)mj1、特殊矩陣的壓縮存儲 特殊矩陣是指元素在矩陣中的位置分布存在一定的規(guī)律的矩陣如：對稱矩陣、三角陣等。例：若一個n 階矩陣A的元素滿足以下條件： aij= aji 1i,jn 則稱A為n階對稱矩陣。A=a11,a21,a31,an1a21,a22,a32,an2 a31,a32,a33,an3 an1,an2,an3,ann不失一般性我們以行主序方式來存

51、儲其下三角中的元素，這樣表長為1/2(n+1)*n)，節(jié)省了近一半的存儲空間。表長1/2(n+1)*n)可由等差數(shù)列公式計算而來。數(shù)組元素存儲次序為 對稱矩陣中任意一個元素在順序表中的位置（地址），可用下式來得到：a11,a21,a22,ai-1.i-1,ai1,ai2,aij, annLoc(aij)=Loc(a11)+(i-1) * i/2+(j-1) * s(i-1) * i/2ji j=Loc(a11)+(j-1) * j/2+(i-1) * si jaij在上三角矩陣中，而aij=aji ，即Loc(aij)=Loc(aji)2、稀疏矩陣的壓縮存儲稀疏矩陣是指一個矩陣中非零元素很少且

52、其分布無規(guī)律。 這里介紹一種常用的三元組的存儲方法，只是存儲稀疏矩陣中的非零元素。所謂三元組是一個（x+1）行、3列的矩陣，而三元是指非零元素所在的行和列的值和非零元素本身的值。例、已知一個稀疏矩陣A，求其對應(yīng)的三元組表示。A56 =1 0 0 0 7 00 0 12 0 0 03 0 0 0 0 00 0 0 0 0 0 0 -3 0 0 0 0 T63 =5 6 51 1 11 5 72 3 123 1 35 2 -3 行的值列的值非零元素的值注意：T矩陣的第一行表示原矩陣的行、列數(shù)和非零元素的個數(shù)。加了這一行的描述之后，便可使A、T矩陣之間一一對應(yīng)。 稀疏矩陣的三元組壓縮存儲是一種基礎(chǔ)的

53、數(shù)據(jù)壓縮的方法，而在此基礎(chǔ)上發(fā)展起來的更先進的壓縮方法（JPEG、MPEG）被廣泛地應(yīng)用于圖象處理和數(shù)據(jù)傳輸中。如雷達圖像的壓縮傳輸。640480壓縮傳送300KB幾KB300KB壓縮解壓縮無損壓縮1.2.3 思考題及作業(yè)1、數(shù)組和線性表的關(guān)系，三維數(shù)組又如何 用數(shù)據(jù)結(jié)構(gòu)的方法用線性表來表示呢？2、矩陣壓縮存儲的基本目的和方法是什么？3、稀疏矩陣的用三元組壓縮方法壓縮時 可以不給出原矩陣的行、列和非零元 素的個數(shù)嗎？1.3 非線性結(jié)構(gòu)1.3.1 樹結(jié)構(gòu)數(shù)據(jù)元素：具有相同的數(shù)據(jù)類型的元素所組成的有限集合。邏輯結(jié)構(gòu)：任何一個元素均可能有多個直接前驅(qū)和直接后繼。 一、基本概念： 1、定義：樹是由n個

54、（n0）具有相同類型的結(jié)點元素組成 的有限集合，且滿足以下的條件： 其中有一個結(jié)點無直接前驅(qū)，稱為根（Root）； 其余的結(jié)點元素可分為m個互不相交的子集： T1,T2 Tm，這m個子集本身又構(gòu)成樹，稱為 Root 的子樹。主要的非線性結(jié)構(gòu)：樹結(jié)構(gòu)和圖結(jié)構(gòu)和線性結(jié)構(gòu)一致ABCDEFGHIJ右圖所示為一棵樹，其中A為根，它有三棵子樹：T1=B,E,F; T2=C,G,H,I,J; T3=D 在子樹T2中，C是該子樹的根，它有三棵子樹：T21=G；T22=H；T23=I，J；T22和T21僅有一個根結(jié)點，沒有子樹。注意： 樹的定義中n0，即沒有空樹的概念； 樹的定義中采用了遞歸定義的方法，顯示了樹

55、 結(jié)構(gòu)本身的這種遞歸的性質(zhì)。在客觀世界中，樹結(jié)構(gòu)廣泛存在，如家譜、行政組織機構(gòu)和計算機磁盤文件管理等。2、有關(guān)基本概念：結(jié)點的度：該結(jié)點所擁有的子樹的數(shù)目。葉子結(jié)點：度為0的結(jié)點。分支結(jié)點：度不為0的結(jié)點。樹的度：樹中各結(jié)點的度的最大值子結(jié)點：某結(jié)點的子樹的根， 稱為他的子結(jié)點。父結(jié)點：該結(jié)點稱為其子樹根的父結(jié)點。兄弟結(jié)點：具有同一父結(jié)點的子結(jié)點稱為兄弟結(jié)點。結(jié)點的層次：根結(jié)點的層次為1，其他結(jié)點的層次等于其父 結(jié)點的層次加1。樹的深度：樹中結(jié)點的最大層次。森林： 是m(m0)棵樹的集合。 ABCDEFGHIJ二、二叉樹1、定義：二叉樹是由n個（n 0）具有相同類型的結(jié)點元素 組成的有限集合，

56、且 滿足以下的條件： 由一個根結(jié)點和它的兩棵左右子樹組成； 其左 右子樹 分別又構(gòu)成一棵二叉樹。注意： 二叉樹的定義中n0，即表示有空二叉樹的概念，而樹至少有一個根結(jié)點； 二叉樹的定義中也采用了遞歸定義的方法，顯示了二叉樹結(jié)構(gòu)本身的這種遞歸的性質(zhì)，樹的定義也采用了遞歸定義。 二叉樹的子樹有左右之分，次序不能顛倒，即使只有一個子 樹也必須分左右，樹中無此區(qū)分。 對于每一個結(jié)點至多有2個子樹。樹中對子樹的數(shù)目沒有限制，但必須是有限個。由定義知二叉樹有五種基本形態(tài)，如下圖所示：2、二叉樹的基本性質(zhì) 在二叉樹的第 i 層上至多有2 i -1個結(jié)點（ i 1 ）。 深度為K的二叉樹至多有2 k -1個結(jié)

57、點（ k 1）。由性質(zhì) 可知深度為k的二叉樹的最大結(jié)點個數(shù)為：由以上性質(zhì)可以引入以下概念：滿二叉樹：一棵深度為k且有 2 k -1 結(jié)點的二叉樹稱為滿二叉樹。特點： 滿二叉樹中所有分支 結(jié)點均存在左右子樹； 所有葉子結(jié)點均在同 一層次上。ABCFGHEDIJKLMNO約定編號順序：從上到下，從左到右。12345678 9 10 11 12 13 14 15特點： 只有最下面兩層的結(jié)點的度可以小于2。 最下層上的節(jié)點都集中在該層最左邊的若干位置。 完全二叉樹：一棵深度為k且有n個 結(jié)點的二叉樹，當且僅當其 每一個結(jié)點的編號都與深度為k的滿二叉樹中編號 為1n的結(jié)點的編號完全一致時該二叉樹稱為完全

58、 二叉樹。ABCFGHEDIJKLL12345678 9 10 11 12 13 14 151234567 8 9 10 111213 6 7 8 912M在完全二叉樹中：設(shè)樹有n個結(jié)點，對任意序號為i的結(jié)點有： 若i1，則i結(jié)點的父結(jié)點的序號為 int(i/2)。 i=1時 該結(jié)點為根結(jié)點，無父結(jié)點。若 2in 則 i 結(jié)點的左子結(jié)點的序號為 2i，否則該結(jié) 點無左子結(jié)點。 若 (2i+1) n 則 i 結(jié)點的右子結(jié)點的序號為 2i+1， 否則該結(jié)點無右子結(jié)點。 int(i/2)ii+1 2 i2i+12(i+1)2(i+1)+112345678 9 10 11 12 13 14 152、二

59、叉樹的存儲結(jié)構(gòu) 二叉樹的順序存儲結(jié)構(gòu)：對于下圖中所示的完全二叉樹，可以用內(nèi)存空間中一組地址連續(xù)的存儲單元來存放，并以一個一維數(shù)組（BT 12 ）來表示。ABCDEFGHIJKL12345678910111201234567891011數(shù)組下標序號可見，在完全二叉樹的順序存儲結(jié)構(gòu)中各結(jié)點間的的邏輯關(guān)系可以由其存儲單元的物理地址來反映。ABCFGHEDIJKL1234567 8 9 10 1112 對于一般的二叉樹，也可以按照完全二叉樹的順序結(jié)構(gòu)來存儲，僅需要添加一些空結(jié)點，使它變成為一棵完全二叉樹。ABCDEF000001234567891011012345678910ABC0D0000EF這樣

60、做可能會帶來存儲空間的浪費，最壞的情況，一個深度為K，且只有K個結(jié)點的單支樹，卻至少需要2 k -1個存儲單元。若 K= 4， 2 k -1 =8 ；K=11， 2 k -1 =1024 。123K1234567891011二叉樹的鏈式存儲結(jié)構(gòu)：由二叉樹的特性知鏈式存儲結(jié)構(gòu)中的每一個結(jié)點可如下圖所示：指向左子結(jié)點的指針域數(shù)據(jù)域指向左子結(jié)點的指針域 A B C E F DhABCDEF3、二叉樹的遍歷： 二叉樹的遍歷是指用一定的規(guī)律，按某條搜索路徑訪問樹中的每一個結(jié)點，使樹中的每個結(jié)點都被訪問且只被訪問一次。根結(jié)點 D左子樹 L右子樹 R如右圖所示，任何一棵二叉樹都由D、L、R三部分組成，若限定