數(shù)據(jù)結(jié)構(gòu)與算法課件

數(shù)據(jù)結(jié)構(gòu)與算法DataStructureandAlgorithm數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象，以及它們之間的關(guān)系和操作等相關(guān)問題的學(xué)科。1968DonaldE.Knuth“TheArtofComputerProgramming”/~uno/計算機排版系統(tǒng)TEX程序設(shè)計=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)：描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別，并輸入給計算機處理的符號集合。數(shù)據(jù)元素：組成數(shù)據(jù)的、有一定意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。數(shù)據(jù)項：一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項組成。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)數(shù)據(jù)對象數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)元素不同數(shù)據(jù)元素之間不是獨立的，而是存在特定的關(guān)系，將這些關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合邏輯結(jié)構(gòu)：數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式。示意圖表示數(shù)據(jù)邏輯結(jié)構(gòu)：將每一個數(shù)據(jù)元素看作一個結(jié)點，用圓圈表示。元素之間的邏輯關(guān)系用結(jié)點之間的連線表示，如果這個關(guān)系是有方向的，那么用帶箭頭的連線表示。集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素，除了同屬于一個集合外，它們之間沒有其他關(guān)系。線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系。樹形結(jié)構(gòu)：樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的層次關(guān)系。圖形結(jié)構(gòu)：圖形結(jié)構(gòu)的數(shù)據(jù)元素是多對多的關(guān)系物理結(jié)構(gòu)順序存儲結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。鏈?zhǔn)酱鎯Y(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。邏輯結(jié)構(gòu)是面向問題的，物理結(jié)構(gòu)是面向計算機的。物理結(jié)構(gòu)的基本目的就是將數(shù)據(jù)及其邏輯關(guān)系存儲到計算機的內(nèi)存中。邏輯結(jié)構(gòu)物理結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)算法：解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作。算法的特性輸入：具有零個或多個輸入輸出：至少有一個或多個輸出有窮性：算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無線循環(huán)。確定性：算法的每一步都具有確定的含義，不會出現(xiàn)二義性?？尚行裕核惴ǖ拿恳徊蕉际强尚械?，即每一步都能通過執(zhí)行有限次數(shù)完成。ThomasH.Cormen,ChalesE.Leiserson(2009)<算法導(dǎo)論>第三版“直白的說，算法就是任何明確定義的計算過程，它接收一些值或集合作為輸入，并產(chǎn)生一些值或集合作為輸出。這樣，算法就是將輸入轉(zhuǎn)換為輸出的一系列計算過程”簡而言之，我們可以說算法就是用來解決一個特定任務(wù)的一系列步驟。一個有效的算法應(yīng)該含有三個重要特性：1

它必須是有限的：如果你設(shè)計的算法永無休止的嘗試解決問題，那么它是無用的。2它必須具備明確定義的指令：算法的每一步都必須準(zhǔn)確定義，在任何場景下指令都應(yīng)當(dāng)沒有歧義。3它必須是有效的：一個算法被設(shè)計用以解決某個問題，那么它就應(yīng)當(dāng)能解決這個問題，并且應(yīng)該是收斂的。算法設(shè)計的要求正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性、能夠正確反映問題的需求、能夠得到問題的正確答案1算法程序沒有語法錯誤2算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果3算法程序?qū)τ诜欠ǖ妮斎肽軌虻贸鰸M足規(guī)格說明的結(jié)果4算法程序?qū)τ诰倪x擇的，甚至刁難的測試數(shù)據(jù)都能夠有滿足要求的輸出結(jié)果。可讀性：算法設(shè)計的另一目的是為了便于閱讀、理解和交流。健壯性：當(dāng)輸入數(shù)據(jù)不合法時，算法也能做出相關(guān)處理，而不是產(chǎn)生異常或莫名其妙的結(jié)果。時間效率與空間效率算法效率的度量方法事后統(tǒng)計方法：主要是通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低。事前分析估計方法：在計算機程序編制前，依據(jù)統(tǒng)計方法進行估算高級程序語言程序運行消耗時間取決于：1算法的策略，方法。2編譯產(chǎn)生的代碼質(zhì)量3問題的輸入規(guī)模4機器執(zhí)行指令的速度可以忽略加法常數(shù)與最高項相乘的常數(shù)并不重要判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常?？梢院雎?，而更應(yīng)該關(guān)注最高階項的階數(shù)時間復(fù)雜度在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復(fù)雜度，也就是算法的時間度量，記作：T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的監(jiān)禁時間復(fù)雜度，簡稱為時間復(fù)雜度。其中，f(n)是問題規(guī)模n的某個函數(shù)。推導(dǎo)大O階：用常數(shù)1取代運行時間中的所有加法常數(shù)。在修改后的運行次數(shù)函數(shù)中，只保留最高階項。如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。得到的結(jié)果就是大O階。30

線性表的類型定義（a1,a2,…ai-1，ai,ai＋1

，…,an）1.線性表的定義：是n個數(shù)據(jù)元素的有限序列n=0時稱為數(shù)據(jù)元素線性起點ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長空表線性終點31

線性表的順序表示和實現(xiàn)線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像邏輯上相鄰，物理上也相鄰用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過數(shù)組來實現(xiàn)若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）32

線性表(a1,a1,a2,...an)順序存儲結(jié)構(gòu)的一般形式

序號存儲狀態(tài)存儲地址1b2b+p

ib+(i-1)*p

nb+(n-1)*p

自由區(qū)maxlengb+(maxleng-1)*p其中:b----表的首地址/基地址/元素a1的地址。p----1個數(shù)據(jù)元素所占存儲單元的數(shù)目。maxleng----最大長度,為某個常數(shù)。

a1

a2

...

ai

...

an

//

//

//33線性表順序結(jié)構(gòu)在C語言中的定義

其中：SqList----結(jié)構(gòu)類型名

La----結(jié)構(gòu)類型變量名

La.length---表長

La.elem[0]----a1La.elem[La.length-1]---an#definemaxleng100structSqList{ElemTypeelem[maxleng];//下標(biāo):0,1,...,maxleng-1intlength;//表長

};SqListLa;34線性表的順序存儲結(jié)構(gòu)定義（動態(tài)）#defineList_Init_size100#defineListincrement10structSqList{ElemType*elem;intlength;intlistsize;};35 順序存儲結(jié)構(gòu)的尋址公式

i=12in

地址=bb+1b+(i-1)pb+(n-1)p

假設(shè):線性表的首地址為b,每個數(shù)據(jù)元素占p個存儲單元,則表中任意元素ai(1≤i≤n)的存儲地址是:

LOC(i)=LOC(1)+(i-1)*p=b+(i-1)*p(1≤i≤n)

例:假設(shè)b=1024,p=4,i=35LOC(i)=b+(i-1)*p=1024+(35-1)*4=1024+34*4=1160

a1a2...ai...an//////36插入算法實現(xiàn)舉例 設(shè)L.elem[0..maxleng-1]中有l(wèi)egth個元素，在

L.elem[i-1]之插入新元素e，1<=i<=length

例.i=3,e=6,length=6

插入6之前：→→→→

258203035//////01234567835,30,20,8依次后移一個位置插入6之后：

2568203035////012345678

37順序存儲結(jié)構(gòu)的評價優(yōu)點：

(1)是一種隨機存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快；

(2)結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也是相鄰的；

(3)不使用指針，節(jié)省存儲空間。缺點：

(1)插入和刪除元素要移動大量元素，消耗大量時間；

(2)需要一個連續(xù)的存儲空間；

(3)插入元素可能發(fā)生“溢出”；

(4)自由區(qū)中的存儲空間不能被其它數(shù)據(jù)共享38線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)順序表：隨機存取鏈表：邏輯相鄰，物理不一定相鄰特點每個元素(表項)由結(jié)點(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點可以不連續(xù)存儲表可擴充適用于存儲空間需求不定、插入或刪除頻繁的情形datanexta1a2a3a4a5first39free(a)可利用存儲空間a0a2a1a3freefirst(b)經(jīng)過一段運行后的單鏈表結(jié)構(gòu)單鏈表的存儲映像40線性鏈表用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，可以是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點的邏輯次序和物理次序不一定相同。利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)結(jié)點 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置4131ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針42結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；鏈表：n個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚?，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。43頭指針、頭結(jié)點和首元結(jié)點頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。 單鏈表可由一個頭指針唯一確定。頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息;首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點44一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。7ZHAOH31∴頭指針的值是3145單鏈表的C定義 或typedefstructnode*LPointer;structnode{intdata;LPointernext;};typedefstructnode{intdata;node*next;}*LinkList;46單鏈表的插入在第一個結(jié)點前插入newnode->next=first;first=newnode;（插入前）（插入后）newnodenewnodefirst

firstdatanextqdatanextdatanextdatanull……firstdatanextdatanextdatanull……firstdatanextq48在鏈表中間插入newnode->next=current->next; current->next=newnode；(插入前)(插入后)newnodecurrentnewnodecurrent49datanextdatanextdatanull……datanextq…pdatanextdatanextdatanull……datanextq…50在鏈表末尾插入newnode->next=current->next; current->next=newnode；(插入前)(插入后)newnodenewnodecurrentcurrent51在鏈表中設(shè)置頭結(jié)點在鏈表的首元結(jié)點之前附設(shè)的一個頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理，編程更方便無頭結(jié)點時，當(dāng)頭指針的值為空時表示空表；有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空時表示空表52

循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個結(jié)點的next

指針不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點。循環(huán)鏈表的特點是：只要知道表中某一結(jié)點的地址，就可搜尋到所有其他結(jié)點的地址53循環(huán)鏈表的示例帶表頭結(jié)點的循環(huán)鏈表a1a2a3anfirstanfirsta2a1first(空表)(非空表)54循環(huán)鏈表的運算與單鏈表類似，只是在涉及到鏈頭與鏈尾的處理時稍有不同表尾插入樹的基本概念二叉樹二叉樹的存儲表示二叉樹的遍歷1.1樹的定義和術(shù)語樹：n（n≥0）個結(jié)點的有限集合。當(dāng)n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴

有且僅有一個特定的稱為根的結(jié)點；⑵

當(dāng)n＞1時，除根結(jié)點之外的其余結(jié)點被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。1樹的基本概念樹的定義是采用遞歸方法(a)一棵樹結(jié)構(gòu)(b)一個非樹結(jié)構(gòu)(c)一個非樹結(jié)構(gòu)ACBGFEDHIACBGFDACBGFDE以下哪一棵是樹？哪一棵不是？理由？結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。樹的度：樹中各結(jié)點度的最大值。CGBDEFKLHMIJA葉子結(jié)點：度為0的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。CGBDEFKLHMIJA孩子、雙親：樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點；兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。

CGBDEFKLHMIJA路徑：如果樹的結(jié)點序列n1,n2,…,nk有如下關(guān)系：結(jié)點ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。CGBDEFKLHMIJA祖先、子孫：在樹中，如果有一條路徑從結(jié)點x到結(jié)點y，那么x就稱為y的祖先，而y稱為x的子孫。CGBDEFKLHMIJA結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何結(jié)點，若某結(jié)點在第k層，則其孩子結(jié)點在第k+1層。樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJCCBDEFKLHJA71234568910層序編號：將樹中結(jié)點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。有序樹、無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹

ACBGFEDACBGFED樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹結(jié)構(gòu)第一個數(shù)據(jù)元素根結(jié)點（只有一個）無前驅(qū)無雙親最后一個數(shù)據(jù)元素葉子結(jié)點(可以有多個)無后繼無孩子其它數(shù)據(jù)元素其它結(jié)點一個前驅(qū),一個后繼一個雙親,多個孩子一對一一對多二叉樹的定義

二叉樹是n（n≥0）個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。2二叉樹問題轉(zhuǎn)化：將樹轉(zhuǎn)換為二叉樹，從而利用二叉樹解決樹的有關(guān)問題。研究二叉樹的意義？2.1二叉樹的定義

二叉樹的特點：⑴每個結(jié)點最多有兩棵子樹；⑵二叉樹是有序的，其次序不能任意顛倒。

注意：二叉樹和樹是兩種樹結(jié)構(gòu)。ABCDEFGABAB二叉樹的基本形態(tài)Ф空二叉樹只有一個根結(jié)點左子樹根結(jié)點只有左子樹右子樹根結(jié)點只有右子樹左子樹右子樹根結(jié)點同時有左右子樹具有3個結(jié)點的樹和具有3個結(jié)點的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。2.2二叉樹的性質(zhì)

性質(zhì)1二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）。

證明：當(dāng)i=1時，第1層只有一個根結(jié)點，而2i-1=20=1，結(jié)論顯然成立。假定i=k（1≤k＜i）時結(jié)論成立，即第k層上至多有2k-1個結(jié)點，則

i=k+1時，因為第k+1層上的結(jié)點是第k層上結(jié)點的孩子，而二叉樹中每個結(jié)點最多有2個孩子，故在第k+1層上最大結(jié)點個數(shù)為第k層上的最大結(jié)點個數(shù)的二倍，即2×2k-1＝2k。結(jié)論成立。[證明用數(shù)學(xué)歸納法]性質(zhì)2深度為k（k≥0）的二叉樹，最多有2k-1個結(jié)點，最少有k個結(jié)點。

證明：由性質(zhì)1可知，深度為k的二叉樹中結(jié)點個數(shù)最多==2k-1；每一層至少要有一個結(jié)點，因此深度為k的二叉樹，至少有k個結(jié)點。深度為k且具有2k-1個結(jié)點的二叉樹一定是滿二叉樹，！性質(zhì)3對任何一棵非空二叉樹，如果葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有:n0＝n2＋1。

證明：設(shè)度為1的結(jié)點數(shù)為n1，二叉樹總的結(jié)點數(shù)為n，則有:n=n0＋

n1

＋n2。再設(shè)分支條數(shù)為e，有e=n-1=n0＋

n1

＋n2

–1，同時有e=n1

＋2n2

因此得n0＋

n1

＋n2

–1=

n1

＋2n2

，于是得證。性質(zhì)4具有n個結(jié)點的完全二叉樹的最小深度為log2(n+1)

。

證明：假設(shè)具有n個結(jié)點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1–1<n≤2k-1

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點數(shù)最多結(jié)點數(shù)完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點。對不等式取對數(shù)，有：k-1＜log2(n+1)

≤

k即：

log2(n+1)≤k＜

log2(n+1)+1由于k是整數(shù)，故必有k＝log2(n+1)

。log2(n+1)+1log2n+1log2(n+1)log2(n+1)k所在區(qū)間性質(zhì)5對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結(jié)點（簡稱為結(jié)點i），有：

(1)如果i＞1，則結(jié)點i的雙親結(jié)點的序號為i/2；如果i＝1，則結(jié)點i是根結(jié)點，無雙親結(jié)點。(2)如果2i≤n，則結(jié)點i的左孩子的序號為2i；(3)如果2i＋1≤n，則結(jié)點i的右孩子的序號為2i＋1；(4)若結(jié)點編號i為奇數(shù)，且i≠1，它處于右兄弟位置，則它的左兄弟為結(jié)點i-1。(5)若結(jié)點編號i為偶數(shù)，且i≠n，它處于左兄弟位置，則它的右兄弟為結(jié)點i+1。(6)結(jié)點i所在層次為log2i+1一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則結(jié)點i的雙親結(jié)點為i/2；結(jié)點i的左孩子為2i；結(jié)點i的右孩子為2i＋1。

性質(zhì)5表明，在完全二叉樹中，結(jié)點的層序編號反映了結(jié)點之間的邏輯關(guān)系。二叉樹的遍歷操作

二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？將非線性結(jié)構(gòu)線性化抽象操作，可以是對結(jié)點進行的各種處理，這里簡化為輸出結(jié)點的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

二叉樹的遍歷二叉樹的遍歷方式：VLR、LVR、LRV、VRL、RVL、RLV

如果限定先左后右，則二叉樹遍歷方式有三種：前序：VLR中序：LVR后序：LRV層序遍歷：按二叉樹的層序編號的次序訪問各結(jié)點。

考慮二叉樹的組成：訪問根結(jié)點記作V遍歷左子樹記作L遍歷右子樹記作R二叉樹二叉樹遍歷的遞歸算法前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結(jié)點；②前序遍歷根結(jié)點的左子樹；③前序遍歷根結(jié)點的右子樹。前序遍歷序列：-+a*b-cd/ef二叉樹的遍歷操作

--/+*abcdef中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結(jié)點的左子樹；②訪問根結(jié)點；③中序遍歷根結(jié)點的右子樹。

中序遍歷序列：a+b*c-d-e/f二叉樹的遍歷操作

--/+*abcdef后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結(jié)點的左子樹；②后序遍歷根結(jié)點的右子樹。③訪問根結(jié)點；后序遍歷序列：abcd-*+ef/-二叉樹的遍歷操作

--/+*abcdef層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。

層序遍歷序列：-+/a*efb–cd二叉樹的遍歷操作

--/+*abcdef二叉樹遍歷操作練習(xí)前序遍歷結(jié)果：ABDGCEF中序遍歷結(jié)果：DGBAECF后序遍歷結(jié)果：GDBEFCA層序遍歷結(jié)果：ABCDEFGABCDEFG已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECDFGHIJ,中序遍歷的結(jié)果序列是EBCDAFHIGJ,試畫出這棵二叉樹，并求出后序遍歷序列和層序遍歷序列。1圖的基本概念圖的定義圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G=(V，E)其中：G表示一個圖，V是圖G中頂點的集合，E是圖G中頂點之間邊的集合。在線性表中，元素個數(shù)可以為零，稱為空表；在樹中，結(jié)點個數(shù)可以為零，稱為空樹；在圖中，頂點個數(shù)不能為零，但可以沒有邊。如果圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖。若頂點vi和vj之間的邊沒有方向，則稱這條邊為無向邊，表示為(vi,vj)。若從頂點vi到vj的邊有方向，則稱這條邊為有向邊，表示為<vi,vj>。

如果圖的任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖。V1V2V3V4V5V1V2V3V4圖的基本術(shù)語

簡單圖：在圖中，若不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)。V3V4V5V1V2V3V4V5V1V2非簡單圖非簡單圖簡單圖V1V2V3V4V5

數(shù)據(jù)結(jié)構(gòu)中討論的都是簡單圖。圖的基本術(shù)語

鄰接、依附無向圖中，對于任意兩個頂點vi和頂點vj，若存在邊(vi，vj)，則稱頂點vi和頂點vj互為鄰接點，同時稱邊(vi，vj)依附于頂點vi和頂點vj。V1V2V3V4V5V1的鄰接點：V2、V4V2的鄰接點：V1、V3、V5圖的基本術(shù)語

鄰接、依附有向圖中，對于任意兩個頂點vi和頂點vj，若存在弧<vi，vj>，則稱頂點vi鄰接到頂點vj，頂點vj鄰接自頂點vi，同時稱弧<vi，vj>依附于頂點vi和頂點vj

。

V1V2V3V4V1的鄰接點：V2、V3V3的鄰接點：V4在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間僅具有線性關(guān)系；在樹結(jié)構(gòu)中，結(jié)點之間具有層次關(guān)系；在圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比在線性結(jié)構(gòu)中，元素之間的關(guān)系為前驅(qū)和后繼；在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系為雙親和孩子；在圖結(jié)構(gòu)中，頂點之間的關(guān)系為鄰接。FECBAD線性結(jié)構(gòu)ABCDEF樹結(jié)構(gòu)V1V2V3V4V5圖結(jié)構(gòu)不同結(jié)構(gòu)中邏輯關(guān)系的對比無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。

圖的基本術(shù)語

V1V2V3V1V2V3V4含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條?。?/p>

含有n個頂點的無向完全圖有n×(n-1)/2條邊。含有n個頂點的有向完全圖有n×(n-1)條邊。V1V2V3V1V2V3V4稀疏圖：稱邊數(shù)很少的圖為稀疏圖；稠密圖：稱邊數(shù)很多的圖為稠密圖。頂點的度：在無向圖中，頂點v的度是指依附于該頂點的邊數(shù)，通常記為TD(v)。圖的基本術(shù)語

頂點的入度：在有向圖中，頂點v的入度是指以該頂點為弧頭的弧的數(shù)目，記為ID(v)；頂點的出度：在有向圖中，頂點v的出度是指以該頂點為弧尾的弧的數(shù)目，記為OD(v)。權(quán)：是指對邊賦予的有意義的數(shù)值量。網(wǎng)：邊上帶權(quán)的圖，也稱網(wǎng)圖。圖的基本術(shù)語

V1V2V3V42785路徑：在無向圖G=(V,E)中，從頂點vp到頂點vq之間的路徑是一個頂點序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向圖，則路徑也是有方向的，頂點序列滿足<vij-1,vij>∈E。圖的基本術(shù)語

V1V2V3V4V5一般情況下，圖中的路徑不惟一。V1到V4的路徑：V1V4

V1V2V3V4V1V2V5V3V4路徑長度：圖的基本術(shù)語

非帶權(quán)圖——路徑上邊的個數(shù)帶權(quán)圖——路徑上各邊的權(quán)之和V1V2V3V4V5V1V4：長度為1V1V2V3V4：長度為3V1V2V5V3V4：長度為4回路（環(huán)）：第一個頂點和最后一個頂點相同的路徑。簡單路徑：序列中頂點不重復(fù)出現(xiàn)的路徑。簡單回路（簡單環(huán)）：除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路。圖的基本術(shù)語

V1V2V3V4V5V1V2V3V4鄰接矩陣（數(shù)組表示法）基本思想：用一個一維數(shù)組存儲圖中頂點的信息，用一個二維數(shù)組（稱為鄰接矩陣）存儲圖中各頂點之間的鄰接關(guān)系。假設(shè)圖G＝(V，E)有n個頂點，則鄰接矩陣是一個n×n的方陣，定義為：G.Edge[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它無向圖的鄰接矩陣的特點？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=0101101101001100G.Edge=V1V2V3V4V1V2V3V4主對角線為0且一定是對稱矩陣。如何求頂點i的度？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=鄰接矩陣的第i行（或第i列）非零元素的個數(shù)。0101101101001100G.Edge=V1V2V3V4V1V2V3V4如何判斷頂點i和j之間是否存在邊？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=測試鄰接矩陣中相應(yīng)位置的元素G.Edge[i][j]是否為1。0101101101001100G.Edge=V1V2V3V4V1V2V3V4如何求頂點i的所有鄰接點？無向圖的鄰接矩陣V1V3V4V2V1V2V3V4vertex=將數(shù)組中第i

行元素掃描一遍，若G.Edge[i][j]為1，則頂點j

為頂點i的鄰接點。0101101101001100G.Edge=V1V2V3V4V1V2V3V4有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=0110000000011000G.Edge=V1V2V3V4V1V2V3V4有向圖的鄰接矩陣一定不對稱嗎？不一定，例如有向完全圖。有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=V1V2V3V4V1V2V3V4如何求頂點i的出度？鄰接矩陣的第i行元素之和。0110000000011000G.Edge=有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=V1V2V3V4V1V2V3V4如何求頂點i的入度？鄰接矩陣的第i列元素之和。0110000000011000G.Edge=有向圖的鄰接矩陣V1V2V3V4V1V2V3V4vertex=V1V2V3V4V1V2V3V4如何判斷從頂點i到頂點j是否存在邊？測試鄰接矩陣中相應(yīng)位置的元素G.Edge[i][j]是否為1。0110000000011000G.Edge=鄰接表鄰接表存儲的基本思想：對于圖的每個頂點vi，將所有鄰接于vi的頂點鏈成一個單鏈表，稱為頂點vi的邊表（對于有向圖則稱為出邊表），所有邊表的頭指針和存儲頂點信息的一維數(shù)組構(gòu)成了頂點表。

圖的鄰接矩陣存儲結(jié)構(gòu)的空間復(fù)雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？假設(shè)圖G有n個頂點e條邊，則存儲該圖需要O(n2)。鄰接表有兩種結(jié)點結(jié)構(gòu)：頂點表結(jié)點和邊表結(jié)點。dataadjdestlink

頂點表邊表data：數(shù)據(jù)域，存放頂點信息。

adj：指針域，指向邊表中第一個結(jié)點。

dest：鄰接點域，邊的終點在頂點表中的下標(biāo)。link：指針域，指向邊表中的下一個結(jié)點。

template<classT,classE>structEdge{intdest;Ecost;Edge<T,E>*link;……};template<classT,classE>structVertex{

Tdata;Edge<T,E>*adj;};定義鄰接表的結(jié)點

dataadj

destlink圖的存儲結(jié)構(gòu)的比較——鄰接矩陣和鄰接表O（n2）O（n+e）O（n2）O（n+e）空間性能時間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一3圖的遍歷圖的遍歷操作圖的遍歷是在從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次。

抽象操作，可以是對結(jié)點進行的各種處理，這里簡化為輸出結(jié)點的數(shù)據(jù)。圖的遍歷操作要解決的關(guān)鍵問題①在圖中，如何選取遍歷的起始頂點？在線性表中，數(shù)據(jù)元素在表中的編號就是元素在序列中的位置，因而其編號是唯一的；在樹中，將結(jié)點按層序編號，由于樹具有層次性，因而其層序編號也是唯一的；在圖中，任何兩個頂點之間都可能存在邊，頂點是沒有確定的先后次序的，所以，頂點的編號不唯一。為了定義操作的方便，將圖中的頂點按任意順序排列起來，比如，按頂點的存儲順序。解決方案：從編號小的頂點開始。②從某個起點始可能到達不了所有其它頂點，怎么辦？圖的遍歷操作要解決的關(guān)鍵問題解決方案：多次調(diào)用從某頂點出發(fā)遍歷圖的算法。下面僅討論從某頂點出發(fā)遍歷圖的算法。③因圖中可能存在回路，某些頂點可能會被重復(fù)訪問，那么如何避免遍歷不會因回路而陷入死循環(huán)。④在圖中，一個頂點可以和其它多個頂點相連，當(dāng)這樣的頂點訪問過后，如何選取下一個要訪問的頂點？

圖的遍歷操作要解決的關(guān)鍵問題解決方案：附設(shè)訪問標(biāo)志數(shù)組visited[n]。解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。1.深度優(yōu)先遍歷

基本思想：⑴訪問頂點v；⑵從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；⑶

重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。

2.廣度優(yōu)先遍歷

基本思想：⑴訪問頂點v；⑵依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk；⑶分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。一個有向圖包含頂點v=