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

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

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

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

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

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

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

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

ib+(i-1)*p

nb+(n-1)*p

自由區(qū)maxlengb+(maxleng-1)*p其中:b----表的首地址/基地址/元素a1的地址。p----1個(gè)數(shù)據(jù)元素所占存儲(chǔ)單元的數(shù)目。maxleng----最大長度,為某個(gè)常數(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線性表的順序存儲(chǔ)結(jié)構(gòu)定義（動(dòng)態(tài)）#defineList_Init_size100#defineListincrement10structSqList{ElemType*elem;intlength;intlistsize;};35 順序存儲(chǔ)結(jié)構(gòu)的尋址公式

i=12in

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

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

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插入算法實(shí)現(xiàn)舉例 設(shè)L.elem[0..maxleng-1]中有l(wèi)egth個(gè)元素，在

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

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

插入6之前：→→→→

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

2568203035////012345678

37順序存儲(chǔ)結(jié)構(gòu)的評(píng)價(jià)優(yōu)點(diǎn)：

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

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

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

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

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

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

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

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

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

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

有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；⑵

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

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

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

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

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

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

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

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

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

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

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

n1

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

n1

＋n2

–1，同時(shí)有e=n1

＋2n2

因此得n0＋

n1

＋n2

–1=

n1

＋2n2

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

。

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

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

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。對(duì)不等式取對(duì)數(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對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)i），有：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

鄰接、依附有向圖中，對(duì)于任意兩個(gè)頂點(diǎn)vi和頂點(diǎn)vj，若存在弧<vi，vj>，則稱頂點(diǎn)vi鄰接到頂點(diǎn)vj，頂點(diǎn)vj鄰接自頂點(diǎn)vi，同時(shí)稱弧<vi，vj>依附于頂點(diǎn)vi和頂點(diǎn)vj

。

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

圖的基本術(shù)語

V1V2V3V1V2V3V4含有n個(gè)頂點(diǎn)的無向完全圖有多少條邊？含有n個(gè)頂點(diǎn)的有向完全圖有多少條弧？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

dataadj

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

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

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

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

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

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

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