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

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

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

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

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

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

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

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

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

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

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

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

12、前趨典型線性結(jié)構(gòu)：線性表、堆棧、隊(duì)列、數(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為“開(kāi)始元素”無(wú)前驅(qū)； an為“結(jié)束元素” 無(wú)后繼；中間任何一個(gè)元素都存在以下關(guān)系： ( i=1,2,n-1 )。 操作集合：INITIATE（L）：初始化線性表。 LENGTH（L）；求表長(zhǎng)，返回值為int 型。 GET（L，i )：訪問(wèn)表中的第 i 個(gè)元素。 LOCATE（L，X）：定位，查找表中等于X的元 素的位置，返回值為 int

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

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

15、明A表中沒(méi)有元素x，此時(shí)應(yīng)插入。 1、求A表的長(zhǎng)度：n=length(LA)； 2、用一個(gè)循環(huán)來(lái)依次取B表中的各元素：x=get (LB,i)； 3、把x在A表中定位：k=locate(LA,x)； 4、如果k= = false就將插入在A表的最后：insert (LA,n+1,x)； 5、表長(zhǎng)加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表的表長(zhǎng) */ for(i=1;i LENGTH(LB);i

16、+) x = GET(LB,i); /* 取LB表中的第 i 個(gè)元素 */ k = LOCATE( LA,x); /* x在LA中定位 */ if(k = false) /* 若LA中的元素 ai x */ INSERT(LA,n+1,x); /* 將x插入LA的后面*/ n + + ; /* 表長(zhǎng)加1 */ 作業(yè)：假定A、B兩表都是遞增有序的線性表，設(shè)計(jì)一個(gè)程序利用以上基本操作，實(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表的表長(zhǎng) */ for(i=1;i LENGTH(LB);i+) x = GET(LB,i); /* 取LB表中的第 i 個(gè)元素 */ k = LOCATE( LA,x); /* x在LA中定位 */ if(k = false) /* 若LA中的元素 ai x */ If (x GET(LA,n) /*若x大于LA中最后一個(gè)元素，則在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è)置一個(gè)前驅(qū)指針p：p=h;算法二、單鏈表的訪問(wèn)算法。 PP P P單鏈表的訪問(wèn)就是訪問(wèn)單鏈表中的第 i 個(gè)元素。注意：?jiǎn)捂湵碇腥我鈨蓚€(gè)元素的存儲(chǔ)位置都沒(méi)有固定 的關(guān)系，每個(gè)元素的存儲(chǔ)位置僅包含在其前 驅(qū)結(jié)點(diǎn)的指針域中。 設(shè)p指針指向ai結(jié)點(diǎn)（數(shù)據(jù)域?yàn)閍i的結(jié)點(diǎn)）， 則： p data=ai； p nextdata=ai+1； 因此，在單鏈表中訪問(wèn)第i個(gè)元素必須從頭指針出發(fā)，依次尋找，直到找到第i個(gè)元素為止。PC語(yǔ)言實(shí)現(xiàn)：、未訪問(wèn)到ai結(jié)點(diǎn)返回空元素。步驟：、p指向頭結(jié)點(diǎn)，

19、結(jié)點(diǎn)計(jì)數(shù)器j置0；、若p還未指向ai結(jié)點(diǎn)且未到表尾則p后移，j+；、找到結(jié)點(diǎn)訪問(wèn)ai結(jié)點(diǎn)并返回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é)點(diǎn)，判i是否有效。申請(qǐng)一個(gè)新結(jié)點(diǎn)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語(yǔ)言實(shí)現(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é)點(diǎn)，判i是否有效； 重新建立ai-1和ai+1與x之間的鏈：Pnext=Snext； 釋放 ai 結(jié)點(diǎn)。C語(yǔ)言實(shí)現(xiàn)：注意：?jiǎn)捂湵淼牟迦牒蛣h除算法中都需要

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

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

23、鏈表稱為線性雙鏈表。 雙鏈表結(jié)點(diǎn)的結(jié)構(gòu)：指向前驅(qū)結(jié)點(diǎn)的指針域數(shù)據(jù)域指向后繼結(jié)點(diǎn)的指針域 邏輯示意圖：注意： 從雙鏈表的任一結(jié)點(diǎn)出發(fā)均可訪問(wèn)鏈表中所有 結(jié)點(diǎn)。 雙鏈表不須頭指針來(lái)標(biāo)識(shí)，用指向表中的任一 結(jié)點(diǎn)的指針均可標(biāo)識(shí)雙鏈表。 雙鏈表結(jié)點(diǎn)結(jié)構(gòu)的C 語(yǔ)言描述： typeded struct node_dl elemtype data; struct node *prior , *next ; node; 雙鏈表常見(jiàn)操作的C 語(yǔ)言實(shí)現(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中的第個(gè)元素 ai 刪除，使刪除后的鏈表dL=（a1,a2,ai-1,ai+1, , an）。P free(P) 以上給大家介紹了順序表的兩種不同的存儲(chǔ)結(jié)構(gòu)：順序表和鏈表（單鏈表、循環(huán)單鏈表、雙鏈表）以及不同存儲(chǔ)結(jié)構(gòu)下的一些常見(jiàn)操作的實(shí)現(xiàn)方法。 順序表占用的存儲(chǔ)空間最少，而雙鏈表占用的存儲(chǔ) 空間最多。 順序表是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，訪問(wèn)表中的某一個(gè)元 素方便；單鏈表元素的訪問(wèn)則必須按照一定的順序 依次去尋找待訪問(wèn)的元素。

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

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

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

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

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

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

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

32、素an ，不改變棧的內(nèi)容。 stack ；注意：這些操作都限制在表尾（棧頂）的一端進(jìn)行。判空3、棧的存儲(chǔ)結(jié)構(gòu)：棧是操作受限的線性表，順序棧和鏈棧 順序棧：利用一組地址連續(xù)的存儲(chǔ)單元依次存放從棧底 到棧頂?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語(yǔ)言描述中，Maxnum表示順序棧的最大長(zhǎng)度，top 和順序表中num的含義不一致：num為表中實(shí)際元素的個(gè)數(shù)；top為棧中棧頂元素的數(shù)組下標(biāo)值。假定定義一個(gè)數(shù)組data

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

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

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

36、 top 修改棧頂指針： top = top next 釋放原棧頂結(jié)點(diǎn)（ an結(jié)點(diǎn)）： free( P ) 鏈棧的引入解決了棧的上溢問(wèn)題，由于鏈棧的結(jié)點(diǎn)是動(dòng)態(tài)產(chǎn)生的，因此只有在整個(gè)內(nèi)存空間都被占滿，malloc過(guò)程無(wú)法實(shí)現(xiàn)時(shí)才會(huì)出現(xiàn)上溢的情況，從而實(shí)現(xiàn)了多個(gè)棧的空間共享。C語(yǔ)言實(shí)現(xiàn)： top設(shè)依次進(jìn)入一個(gè)棧的元素序列為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二、隊(duì)列(queue)1、隊(duì)列的基本概念定義：是限定在表尾進(jìn)行插入，在表頭進(jìn)行刪除的線性表。表尾的一端稱為隊(duì)尾，表頭的一端

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

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

39、ont = 0 ; 隊(duì)滿rear a3 a2 a1front rear a5 a4 a3 a2 a1front 算法一、入隊(duì)列操作（插入算法） 設(shè)棧 Q =（ a1,a2,a3,ai,an）， ENTER（Q，x）的含義為：若Q滿則入隊(duì)列操作無(wú)效，否則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實(shí)現(xiàn)： 如果隊(duì)滿（rear=Maxnum）則插入無(wú)效，返回插入出錯(cuò)的的信息。 否則，隊(duì)尾指示器加1，并將 x 插入到

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

41、的五個(gè)元素，即： rear=5; front=5 ;此時(shí)，隊(duì)列為空，還是為滿？為解決順序隊(duì)列的假溢出現(xiàn)象，可采用循環(huán)隊(duì)列。rear a7 a6 a5 a4 a3 a2 a1front 76543210循環(huán)隊(duì)列： 在循環(huán)隊(duì)列的結(jié)構(gòu)中，將data0看作是datamaxnum-1的下一個(gè)相鄰的位置。循環(huán)隊(duì)列的C語(yǔ)言描述：typedef struct elmtype datamaxnum; int front, rear ; queuetype;指示器的移動(dòng)：一般隊(duì)列和循環(huán)隊(duì)列的區(qū)別：一般隊(duì)列循環(huán)隊(duì)列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)隊(duì)列的操作和一般隊(duì)列一致，僅僅是判空和判滿的條件發(fā)生了變化。 鏈隊(duì)列：是采用一組地址不連續(xù)的存儲(chǔ)單元來(lái)存放隊(duì)列中 各元素，隊(duì)列中各元素的邏輯關(guān)系用指針來(lái)表示。 設(shè)隊(duì)列 q =（a1,a2,a3 ,ai

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

44、操作（刪除算法） 出鏈隊(duì)列的操作和鏈表的操作相似，僅僅是刪除操作被限定在隊(duì)頭進(jìn)行而已。其含義和出順序隊(duì)列的含義一致。 pfree(p)步驟： 以p指針指向鏈隊(duì)列的第一個(gè)結(jié)點(diǎn): p=front-next; 進(jìn)行頭結(jié)點(diǎn)和a2 結(jié)點(diǎn)的連接: front-next=p-next; 釋放被刪除的a1 結(jié)點(diǎn): free(p);注意：若隊(duì)列中僅有一個(gè)元素，刪除后則為空隊(duì)列。因此刪除后還要修改尾指針，使其也指向頭結(jié)點(diǎn)，表示隊(duì)列已空。1.2.2 思考題及作業(yè)1、棧和隊(duì)列各有哪些基本特征？2、設(shè)一個(gè)棧的輸入序列是1,2,3,4,寫(xiě)出該 棧的所有可能的輸出序列。3、進(jìn)一步理解循環(huán)隊(duì)列的判空和判滿的條件。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ù)組元素的下標(biāo)，求數(shù) 組元素的值。 Assign(A,x,i,j)：修改指定下標(biāo)的元素的值。 ADT Array；二、二維數(shù)組中元素的邏輯關(guān)系：已知一個(gè)二維數(shù)組Anm行下標(biāo)列下標(biāo)A= 由于，二維數(shù)組中任意一個(gè)元素aij，都有兩個(gè)直接前驅(qū)和兩個(gè)直接后繼，因此它不是一般意義上的線性表。但它的每一行和每一列都是一個(gè)線性表。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)粢孕邢蛄炕蛄邢蛄縼?lái)表示二維數(shù)組的話，則有： A= (1,2, ,i, ,p ) 其中 p = m 或

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

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

49、共（i-1）m+j個(gè)數(shù)據(jù)元素，另外由于從a1 1作為起始位算起，所以公式為L(zhǎng)oc( aij ) = Loc( a11 )+(i-1) * m+(j-1) * s相似的，對(duì)于列優(yōu)先的每個(gè)元素的存儲(chǔ)地址為L(zhǎng)oc( 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、特殊矩陣的壓縮存儲(chǔ) 特殊矩陣是指元素在矩陣中的位置分布存在一定的規(guī)律的矩陣如：對(duì)稱矩陣、三角陣等。例：若一個(gè)n 階矩陣A的元素滿足以下條件： aij= aji 1i,jn 則稱A為n階對(duì)稱矩陣。A=a11,a21,a31,an1a21,a22,a32,an2 a31,a32,a33,an3 an1,an2,an3,ann不失一般性我們以行主序方式來(lái)存

51、儲(chǔ)其下三角中的元素，這樣表長(zhǎng)為1/2(n+1)*n)，節(jié)省了近一半的存儲(chǔ)空間。表長(zhǎng)1/2(n+1)*n)可由等差數(shù)列公式計(jì)算而來(lái)。數(shù)組元素存儲(chǔ)次序?yàn)?對(duì)稱矩陣中任意一個(gè)元素在順序表中的位置（地址），可用下式來(lái)得到：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、稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣是指一個(gè)矩陣中非零元素很少且

52、其分布無(wú)規(guī)律。 這里介紹一種常用的三元組的存儲(chǔ)方法，只是存儲(chǔ)稀疏矩陣中的非零元素。所謂三元組是一個(gè)（x+1）行、3列的矩陣，而三元是指非零元素所在的行和列的值和非零元素本身的值。例、已知一個(gè)稀疏矩陣A，求其對(duì)應(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ù)和非零元素的個(gè)數(shù)。加了這一行的描述之后，便可使A、T矩陣之間一一對(duì)應(yīng)。 稀疏矩陣的三元組壓縮存儲(chǔ)是一種基礎(chǔ)的

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

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

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

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

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

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

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

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