數(shù)據(jù)結(jié)構(gòu)第一章概論、算法+數(shù)據(jù)結(jié)構(gòu)=程序、數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)邏輯結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲物理結(jié)構(gòu) 鏈?zhǔn)酱鎯λ饕鎯ι⒘写鎯θ⑿g(shù)語1、 數(shù)據(jù)(Data)：數(shù)字、字符、圖像、聲音。------單元格2、 數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，又稱結(jié)點(diǎn)(用一組連續(xù)的位串表示)或記錄。 行3、 數(shù)據(jù)項(DataItem)：數(shù)據(jù)元素由若干個數(shù)據(jù)項組成，是數(shù)據(jù)的不可分割的最小單位。又稱字段或域。-列4、數(shù)據(jù)對象(DataObject):是性質(zhì)相同的數(shù)據(jù)元素的集合。 表5、 數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：o—o~o錢性姑構(gòu)樹形結(jié)構(gòu)0—0%°集合皓構(gòu)o—o~o錢性姑構(gòu)樹形結(jié)構(gòu)0—0%°集合皓構(gòu)⑴集合結(jié)構(gòu)：數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，另U無其它關(guān)系；線性結(jié)構(gòu)：一對一關(guān)系；樹形結(jié)構(gòu)：一對多關(guān)系；圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：多對多關(guān)系。6、 數(shù)據(jù)類型：原子類型(只有一個數(shù)據(jù)項)、結(jié)構(gòu)類型(由多個不同類型數(shù)據(jù)項組成)。7、 抽象數(shù)據(jù)類型(AbstractDataType)：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系、基本操作四、 數(shù)據(jù)運(yùn)算查找、插入、刪除、修改、排序五、 算法和算法分析1.4.1算法1、 算法(Algorithm)：是對特定問題求解步驟的一種描述2、 五個重要特性：有窮性：執(zhí)行有窮步之后結(jié)束，每一步在有窮時間內(nèi)完成。確定性：無二義性。唯一的一條執(zhí)行路徑，相同的輸入只能得出相同的輸出。可行性：基本運(yùn)算執(zhí)行有限次次。輸入：零個或多個輸入。輸出：一個或多個輸出。3、 設(shè)計目標(biāo)：正確性、可讀性、健壯性、效率與低存儲量需求。六、算法分析1、度量一個程序的執(zhí)行時間：事后統(tǒng)計的方法事前分析估算的方法(常用)高級語言編寫的程序運(yùn)行時間取決于下列因素：依據(jù)的算法選用何種策略；問題的規(guī)模，例如求100以內(nèi)還是1000以內(nèi)的素數(shù)；書寫程序的語言，對于同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低；d編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；e.機(jī)器執(zhí)行指令的速度。一個算法是由控制結(jié)構(gòu)(順序、分支和循環(huán)三種)和原操作(指固有數(shù)據(jù)類型的操作)構(gòu)成的，則算法時間取決于兩者的綜合效果。從算法中選取一種對于所研究的問題(或算法類型)來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。2、 時間復(fù)雜度算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作：T(n)=O(f(n))。語句的頻度(FrequencyCount):該語句重復(fù)執(zhí)行的次數(shù)。時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O("2)、立方階O("3)、……k次方階O("k)、指數(shù)階O(2An)o3、 空間復(fù)雜度(SpaceComplexity)：算法所需輔助存儲空間的量度，記作：S(n)=O(g(n))。數(shù)據(jù)結(jié)構(gòu)第二章線性表一、 線性表的類型定義1、 線性表(Linear_List)：n個數(shù)據(jù)元素的有限序列，(al,...,ai-1,ai,ai+1,…,an)(2一1),ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當(dāng)i=1，2, ,n-1時，ai有且僅有一個直接后繼，當(dāng)i=2，3,...,n時，ai有且僅有一個直接前驅(qū)。2、 線性表的長度：線性表中元素的個數(shù)n(n>0),n=0時稱為空表。3、 位序：a1是第一個數(shù)據(jù)元素。an是最后一個數(shù)據(jù)元素，ai是第i個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。4、 同一線性表中的元素必定具有相同特性，即屬同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。二、 線性表的順序表示和實現(xiàn)1、 順序存儲或順序映象(順序表)：用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。2、 存儲位置計算：LOC(ai)=LOC(a1)+(i-1)*L式中LOC(a1)是a1的存儲位置，稱基地址。(假設(shè)每個元素占l個存儲單元)二1:S：3豎3214工12825302M427307712⑹977號5康43、 特點(diǎn)：以元素在計算機(jī)內(nèi)“物理位置相鄰號5康4n茫閑插人■：-Jn茫閑插人2a->-67衛(wèi)JJ212j21.544285：JS3:⑴6引)7；2777g770'}序號教捉丄點(diǎn)冊能24 >(a)4、 優(yōu)點(diǎn)：是一種隨機(jī)存取的存儲結(jié)構(gòu)。插入和刪除操作時需要移動大量的元素，平均移動5、 缺點(diǎn)：要求占用連續(xù)的存儲空間，并預(yù)先分配;插入和刪除操作時需要移動大量的元素，平均移動次數(shù)為n/2。三、線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)1、 特點(diǎn)：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)。2、 結(jié)點(diǎn)(Node)：數(shù)據(jù)域：存儲數(shù)據(jù)元素信息。指針域：存儲直接后繼存儲位置。指針域中存儲的信息稱做指針或鏈。四、單鏈表：1、每個結(jié)點(diǎn)中只包含一個指針域的鏈表，稱線性鏈表或單鏈表。例，線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的鏈表存儲結(jié)構(gòu)，整個鏈表的存取必須從頭指針開始進(jìn)行，頭指針指示鏈表中第一個結(jié)點(diǎn)(即第一個數(shù)據(jù)元素的存儲映象)的存儲位置。同時，由于最后一個數(shù)據(jù)元素沒有直接后繼，則線性鏈表中最后一個結(jié)點(diǎn)的指針為，空”(NULL)。IL1巧IL1巧7叨AN1J13SUN1L?WANG時JLL28嘰3731ZHAO737fHElSG】g胡mZHAO卜日。仙|?戶I晌l+HUT|ZHOLr|4^1wuI ―^vanc|2、 在使用鏈表時，關(guān)心的只是它所表示的線性表中數(shù)據(jù)元素之間的邏輯順序，而不是每個數(shù)據(jù)元素在存儲器中的實際位置。3、 頭指針：單鏈表可由頭指針唯一確定，它指向表中第一個結(jié)點(diǎn)。若L為，空”(L==NULL)，貝9所表示的線性表為“空”表，其長度n為“零”。有時，我們在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可存儲如線性表的長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲指向第一個結(jié)點(diǎn)的指針(即第一個元素結(jié)點(diǎn)的存儲位置)。4、 查找5、 插入：s一＞next=p—＞next；p一＞next=s；6、 刪除：s一＞next=p一＞next；p一＞next=s；P特點(diǎn)：插入或刪除結(jié)點(diǎn)時，僅需修改指針而不需要移動元素。是一種動態(tài)結(jié)構(gòu)，每個鏈表占用的空間不需預(yù)先分配劃定，可由系統(tǒng)應(yīng)需求即時生成。因此，建立線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的過程就是一個動態(tài)生成鏈表的過程。即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個插入鏈表。五、 靜態(tài)鏈表對于線性鏈表，也可用一維數(shù)組來進(jìn)行描述。這種描述方法便于在沒有指針類型的高級程序設(shè)計語言中使用鏈表結(jié)構(gòu)。這種存儲結(jié)構(gòu)，仍需要預(yù)先分配一個較大的空間，但在作為線性表的插入和刪除操作時不需移動元素，僅需修改指針，故仍具有鏈?zhǔn)酱鎯Y(jié)構(gòu)的主要優(yōu)點(diǎn)。六、 循環(huán)鏈表(CircularlinkedList)⑹空表1、特點(diǎn)：表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。由此從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。⑹空表⑹非空表2、 循環(huán)條件：不是p或者p—＞next是否為空，而是它們是否等于頭指針。3、 尾指針：設(shè)置尾指針而不設(shè)頭指針可使某些操作簡化。例如將兩個線性表合并成一個表時，僅需將一個表的表尾和另一個表的表頭相接。

S+——>i1+>..->\I"k-—-A尿+—>11+>■.->LJ卞一■R+—I+〉一<\I4、C^l—FF>七、雙向鏈表(DoubleLinkedList)1、特點(diǎn)：結(jié)點(diǎn)中有兩個指針域，其一指向直接后繼，另一指向直接前驅(qū)。priouelementnextb)結(jié)點(diǎn)結(jié)構(gòu) 仍)空的雙向循環(huán)蟻表priouelementnextb)結(jié)點(diǎn)結(jié)構(gòu) 仍)空的雙向循環(huán)蟻表5)非空的雙向循環(huán)蟻表2、 在雙向鏈表中，若p為指向表中某結(jié)點(diǎn)的指針，貝9：p->next->prior=p->prior->next=p。3、 帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表的插入和刪除：插入：s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;刪除：e=p—>data；p一>prior—>next=p—>next;p—>next—>prior=p—>prior;free(p)；八、內(nèi)容精要1、 概念和術(shù)語線性表前趨和后繼線性表的長度空表表頭元素表尾元素結(jié)點(diǎn)首元結(jié)點(diǎn)2、 線性表的特點(diǎn)存在唯一的一個稱“第一個”的數(shù)據(jù)元素；(2)存在唯一的一個稱“最后一個”的數(shù)據(jù)元素；(3)除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；(4)除最后一個之外，集合中每個數(shù)據(jù)元素均只有一個后繼。3、 線性表的順序存儲結(jié)構(gòu)(順序表)用一組地址連續(xù)的存儲單元依次存儲線性表的各個元素，可借助一維數(shù)組實現(xiàn)。在順序存儲中，每個存儲結(jié)點(diǎn)只含有所存數(shù)據(jù)元素本身的信息，元素之間的邏輯關(guān)系是通過數(shù)組下標(biāo)反映出來的。假設(shè)線性表中每個元素占用c個存儲單元，則線性表中第i個數(shù)據(jù)元素的存儲地址為LOC(ai)=LOC(a1)+(i-1)*c。4、 C語言中線性表順序存儲空間的兩種分配方法1?靜態(tài)分配在類定義中用一維數(shù)組來定義線性表的存儲空間。這種方式在程序開始運(yùn)行前，系統(tǒng)按數(shù)組大小事先分配出相應(yīng)的空間，因此向量空間的大小應(yīng)慎重選擇，使它既能標(biāo)元素數(shù)目動態(tài)增加的需求，又不至于過數(shù)據(jù)結(jié)構(gòu)多浪費(fèi)存儲空間。2.動態(tài)分配在定義線性表的存儲類型時，只定義一個指針，待程序運(yùn)行是可以通過基本函數(shù)malloc申請一個恰當(dāng)大小的用于存儲線性表的空間，并把該空間的首地址賦給這個指針。訪問動態(tài)存儲分配的線性表中的元素與訪問靜態(tài)時的情況相同，既可以采用指針方式，也可以采用數(shù)組下標(biāo)方式。5、 線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)1.優(yōu)點(diǎn)（1）結(jié)構(gòu)簡單（2）可直接定位到表中任意元素，并可隨機(jī)存取元素，連續(xù)存取速度快。2.缺點(diǎn)（1）存儲空間難于準(zhǔn)確靜態(tài)分配，分配大了浪費(fèi)空間，分配小了又可能不夠用。（2）插入、刪除操作不大方便，需要移動大量數(shù)據(jù)元素，效率較低。6、 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)在鏈?zhǔn)酱鎯Y(jié)構(gòu)下，線性表的存儲空間可以是分散不連續(xù)的。因此，存儲結(jié)點(diǎn)的物理次序和原有的邏輯次序不一定相同。為了能正確表示結(jié)點(diǎn)的邏輯關(guān)系，每個存儲結(jié)點(diǎn)不僅含有數(shù)據(jù)元素本身的信息，還含有一個或多個指針（地址）信息，指示結(jié)點(diǎn)間的邏輯關(guān)系。結(jié)點(diǎn)中data表示數(shù)據(jù)域，用來存儲數(shù)據(jù)元素本身；p稱為指針域。注意，一個存儲結(jié)點(diǎn)的存儲空間是連續(xù)的。7、 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)（1）存儲空間動態(tài)分配，可以按需要使用。（2）插入、刪除結(jié)點(diǎn)操作通常只需要修改指針，不必移動數(shù)據(jù)元素。缺點(diǎn)（1）每一個結(jié)點(diǎn)附加指針域（存儲密度小于1），空間利用率低。（2）非隨機(jī)存儲結(jié)構(gòu)，查找定位操作需從頭指針處罰順著鏈表掃描。數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組和廣義表一、定義數(shù)組中的每個數(shù)據(jù)元素都對應(yīng)于一組下標(biāo)(jl,j2,…，jn),每個下標(biāo)的取值范圍是OSUbi-1,bi稱為第i維的長度(i=1,2,...,n)。我們可以把二維數(shù)組看成是這樣一個定長線性表：它的每個數(shù)據(jù)元素也是一個定長線性表。-^00alC旬1孔...a12...電辺-alnibla10和1aLLaL2-■%培1￡-1卩^-1,1仏1詁..VLp備-1》江垃性=認(rèn)知%1 ... C.a]Q% .. ……^n-ljO^-L,!...程1,114））數(shù)組只有存取元素和修改元素值的操作。一般不作插入或刪除操作。二、順序表示和實現(xiàn)：以列序為主序(columnmajororder)和以行序為主序(rowmajororder)。假設(shè)每個數(shù)據(jù)元素占L個存儲單元，則二維數(shù)組A中任一元素的存儲位置可由下式確定：LOC(i,j)=LOC(0,0)+(b2*i+j)L其中LOC(i,j)是aij的存儲位置；LOC(0,0)是a00的存儲位置，即二維數(shù)組A的起始存儲位置，亦稱為基地址或基址。三、壓縮存儲：為多個值相同的元只分配一個存儲空間；對零元不分配空間。1、特殊矩陣：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律；反之，稱為稀疏矩陣。(1)對稱矩陣：為每一對對稱元分配一個存儲空間，則可將n2個元壓縮存儲到，n(n+1)/2個元的空間中。以行序為主序存儲其下三角(包括對角線)中的元。假設(shè)以一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)構(gòu)，則sa[k]和矩陣元aij之間存在著一一對應(yīng)的關(guān)系。當(dāng)>=j1;=TOC\o"1-5"\h\zI S 1 ?當(dāng)>=j1;=5 0 H CI 8 弓? 口0c1；J6 1三角矩陣。所謂下(上)三角矩陣是指矩陣的上(下)三角(不包括對角線)中的元均為常數(shù)c或零的n階矩陣。除了和對稱矩陣一樣，只存儲其下(上)三角中的元之外，再加一個存儲常數(shù)c的存儲空間即可。ilul ... ^1；.n1"iJ：：：： C ... CC LJ:L --- n1■dJJ JLL ... P* 4 爭* - - - --C. C ... tinL,n1_1,r H|,J...iii：L,n1_㈤上三箱如陣 (h)卜三角雉陣對角矩陣。所有的非零元都集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元之外，所有其它的元皆為零。按某個原貝I或以行為主，或以對角線的順序)將其壓縮存儲到一維數(shù)組上。H：：la-1r.l2fl'!'3k23?w.an-2n~3?丄.an-2n-2?■.311—2n—1n-21旳■】_2、稀疏矩陣假設(shè)在m*n的矩陣中，有t個元素不為零。令§=t/(m*n)，稱5為矩陣的稀疏因子。通常認(rèn)為5<0.05時稱為稀疏矩陣。稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。例如：三元組表((1,2，12),(1,3，9),(3，1，-3),(3,6，14),(4,3，24),(5,2，18),(6,1，15),(6,4,-7))加上(6,7)這一對行、列值表示的矩陣：廣°1290000000000M=-300001400024000001800000=1500-7000」酣.5稀疏矩陣M三元組順序表轉(zhuǎn)置運(yùn)算：(1)將矩陣的行列值相互交換；(2)將每個三元組中的i和j相互調(diào)換；(3)重排三元組之間的次序。行邏輯鏈接的順序表十字鏈表當(dāng)矩陣的非零元個數(shù)和位置在操作過程中變化較大時，就不宜采用順序存儲結(jié)構(gòu)來表示三元組的線性表。在鏈表中，每個非零元可用一個含五個域的結(jié)點(diǎn)表示，其中i,j和e三個域分別表示該非零元所在的行、列和非零元的值，向右域right用以鏈接同一行中下一個非零元，向下域down用以鏈接同一列中下一個非零元。同一行的非零元通過right域鏈接成一個線性鏈表，同一列的非零元通過down域鏈接成一個線性鏈表，每個非零元既是某個行鏈表中的一個結(jié)點(diǎn)，又是某個列鏈表中的一個結(jié)點(diǎn)，整個矩陣構(gòu)成了一個十字交叉的鏈表，故稱這樣的存儲結(jié)構(gòu)為十字鏈表，可用兩個分別存儲行鏈表的頭指針和列鏈表的頭指針的一維數(shù)組表示之。［例如］：矩陣M的十字鏈表^5.6棉疏趙牢vf^5.6棉疏趙牢vf時十〒訶示三元組順序表的轉(zhuǎn)置四、廣義表1、定義：LS=(al,a2,..an)其中，LS是廣義表(al,a2,..an)的名稱，n是它的長度。在線性表的定義中，ai(1<i<n)只限于是單個元素。而在廣義表的定義中，ai可以是單個元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。習(xí)慣上，用大寫字母表示廣義表的名稱，用小寫字母表示原子。當(dāng)廣義表LS非空時，稱第一個元素al為LS的表頭(Head),稱其余元素組成的表(a2,a3,…an)是LS的表尾(Tail)。

例如：A=()——A是一個空表，它的長度為零。B=(e 列表B只有一個原子e,B的長度為1。C=(a,(b，c，d)) 列表C的長度為2,兩個元素分別為原子a和子表(b,c，d)。D=(A,B，C)——列表D的長度為3,三個元素都是列表。顯然，將子表的值代入后，貝9有D=(()，(e)，(a,(b,c,d)))。E=(a,E)——這是一個遞歸的表，它的長度為2。正相當(dāng)于一個無限的列表E=(a,(a,(a,…)))。2、存儲：鏈?zhǔn)叫枰獌煞N結(jié)構(gòu)的結(jié)點(diǎn)：一種是表結(jié)點(diǎn)，用以表示列表；一種是原子結(jié)點(diǎn)，用以表示原子。一個表結(jié)點(diǎn)可由三個域組成：標(biāo)志域、指示表頭的指針域和指示表尾的指針域；而原子結(jié)點(diǎn)只需兩個域：標(biāo)志域和值域。1VQC10a1JL1VQC10a1JL1JL1110bhc□d?1?丄—?1rxe的存儲示例 on111lD■10a11111lD■10a111b——*Dc ?0d110El1數(shù)據(jù)結(jié)構(gòu)第7章圖、在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。、概述有向圖無向圖頂點(diǎn)(數(shù)據(jù)兀素)V頂點(diǎn)之間關(guān)系VR弧(弧頭v,弧尾W)邊例:(a)有向圖G1(b)無向圖G2G1=(V1,{A1}),其中：Vl={vl,v2,v3,v4}；Al={vvl,v2>,vvl,v3>,vv3,v4>,vv4,vl>}。G2=(V2,{A2}),其中：V2={vl,v2,v3,v4,v5}；A2={(vl,v2),(vl,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}三、術(shù)語用n表示圖中頂點(diǎn)數(shù)目，用e表示邊或弧的數(shù)目，不考慮頂點(diǎn)到其自身的弧或邊：1、 無向圖，e的取值范圍是0到n(n一l)/2。有n(n—1)/2條邊的無向圖稱為完全圖(Completedgraph)。2、 有向圖，e的取值范圍是0到n(n—1)。具有n(n—1)條弧的有向圖稱為有向完全圖。3、 有很少條邊或弧(如evnlogn)的圖稱為稀疏圖(Sparsegraph),反之稱為稠密圖(Densegraph)。4、 有時圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)(Weight)。表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離或耗費(fèi)。5、 帶權(quán)的圖通常稱為網(wǎng)(Network)。6、 子圖：假設(shè)兩個圖G=(V,{E})和G'=(V',{E'}),如果V'是V的子集，且E'是E的子集，則稱G'為G的子圖(Subgraph)。7、 度對于無向圖G=(V，{E})，如果邊(v,v')WE,則稱頂點(diǎn)v和v'互為鄰接點(diǎn)(Adjacent),即v和v'相鄰接。邊(v,v')依附(Incident)于頂點(diǎn)v和v',或者說(v,v')和頂點(diǎn)v和v'相關(guān)聯(lián)。頂點(diǎn)v的度(Degree)是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。［例如］,G2中頂點(diǎn)v3的度是3。對于有向圖G=(V,{A}),如果弧<v,v'>WA,則稱頂點(diǎn)v鄰接到頂點(diǎn)v',頂點(diǎn)v'鄰接自頂點(diǎn)v。弧<v,v'>和頂點(diǎn)v,v'相關(guān)聯(lián)。以頂點(diǎn)v為頭的弧的數(shù)目稱為v的入度(InDegree)，記為ID(v)；以v為尾的弧的數(shù)目稱為v的出度(Outdgree)，記為OD(v)；頂點(diǎn)v的度為TD(v)=ID(v)+OD(v)。［例如］,圖G1中頂點(diǎn)vl的入度ID(v1)=1,出度OD(v1)=2,度TD(v1)=ID(v1)+0D(v1)=3。一般地，如果頂點(diǎn)vi的度記為TD(vi),那么一個有n個頂點(diǎn)，e條邊或弧的圖，滿足關(guān)系：e=l/2￡TD(vi)8、 路徑無向圖G=(V,{E})中從頂點(diǎn)v到頂點(diǎn)v'的路徑(Path)是一個頂點(diǎn)序列(v=vi,O,vi,l,???vi,m=v'),其中(vi,j-l,vi,j)GE,lWjWm。如果G是有向圖，則路徑也是有向的，頂點(diǎn)序列應(yīng)滿^vi,j-l,vi,j〉WE,lWjWm。路徑的長度是路徑上的邊或弧的數(shù)目。第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑稱為回路或環(huán)(Cycle)。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了第一個頂點(diǎn)和最后一個頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。9、連通圖、連通分量在無向圖G中，如果從頂點(diǎn)v到頂點(diǎn)v'有路徑，則稱v和v'是連通的。如果對于圖中任意兩個頂點(diǎn)vi、vjWV，vi和vj都是連通的，則稱G是連通圖(ConnectedGraph)。圖7.1(b)中的G2就是一個連通圖,而圖7.3(a)中的G3則是非連通圖，但G3有三個連通分量，如圖7.3(b)所示。所謂連通分量(ConnectedComponent)，指的是無向圖中的極大連通子圖。A——二3)無廚圖G3A——二3)無廚圖G3;〔⑴陽的三個連通分量。圖7.3無向圖及其連通分量在有向圖G中，如果對于每一對vi,vjWV，vi!二vj,從vi到vj和從vj到vi都存在路徑，則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。［例如］圖7.1(a)中的G1,不是強(qiáng)連通圖，但它有兩個強(qiáng)連通分量，如圖7.4所示。圖T-16)圖T-16)育向圖G1 圖人4G：［的兩個強(qiáng)連通分董10、生成樹一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。圖7.5是G3中最大連通分量的一棵生成樹。圖7.5G3的最大連通分量的一棵生成樹一棵有n個頂點(diǎn)的生成樹有且僅有n-1條邊。如果一個圖有n個頂點(diǎn)和小于n-1條邊，則是非連通圖。如果它多于n-1條邊，則一定有環(huán)。但是，有n-1條邊的圖不一定是生成樹。如果一個有向圖恰有一個頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1,則是一棵有向樹。一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。

四、存儲結(jié)構(gòu)1、數(shù)組表示法圖7.6一個有向圖及其生成森林仆四、存儲結(jié)構(gòu)1、數(shù)組表示法圖7.6一個有向圖及其生成森林仆11[>-11■:)-1[*101(■0001■:'110n1101000o0-0110oJ對于無向圖，頂點(diǎn)i的度是鄰接矩陣中第i行(或第i列)的元素之和。對于有向圖，第i行的元素之和為頂點(diǎn)vi的出度OD(vi)，第j列的元素之和為頂點(diǎn)vj的入度ID(vj)。網(wǎng)的鄰接矩陣：若(T卩j)若(T卩j)或弋片，卩j S(<?)若 或€fj>史總(G)〔a)畫N;CD5GO7GOQOCOCfi4m008QDcocoCD9GOGO號GOGD6COoo005m003QOGOCD1ocr(S鄰接矩阡2、鄰接表在鄰接表中，對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對有向圖是以頂點(diǎn)vi為尾的弧)。每個結(jié)點(diǎn)由三個域組成，其中鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置，鏈域(nextare)指示下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域(info)存儲和邊或弧相關(guān)的信息，如權(quán)值等。0vl—k2-Jf11v20vl—k2-Jf11v2V5—b耳—U]二2◎G1的鄰接表123IvlV2V-v5Avl―k31v2―■02v3―n03v4—?2(■=)口的逆鄰接表在無向圖的鄰接表中，頂點(diǎn)vi的度恰為第i個鏈表中的結(jié)點(diǎn)數(shù)。而在有向圖中，第i個鏈表中的結(jié)點(diǎn)個數(shù)只是頂點(diǎn)的出度，為求入度，必須遍歷整個鄰接表。在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個數(shù)是頂點(diǎn)Vi的入度。有時，為了便于確定頂點(diǎn)的入度或以頂點(diǎn)Vi為頭的弧，可以建立一個有向圖的逆鄰接表，即對每個頂點(diǎn)Vi建立一個鏈接以vi為頭的弧的表。3、十字鏈表（有向圖）tailvexheadvexhlinktailvexheadvexhlinktlinkinfodatafirstinnrstout頂點(diǎn)結(jié)點(diǎn)在弧結(jié)點(diǎn)中有五個域：其中尾域（tailvex）和頭域（headvex）分別指示弧尾和弧頭這兩個頂點(diǎn)在圖中的位置，鏈域hlink指向弧頭相同的下一條弧，而鏈域tlink指向弧尾相同的下一條