數(shù)據(jù)結構與算法課件

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

它必須是有限的：如果你設計的算法永無休止的嘗試解決問題，那么它是無用的。2它必須具備明確定義的指令：算法的每一步都必須準確定義，在任何場景下指令都應當沒有歧義。3它必須是有效的：一個算法被設計用以解決某個問題，那么它就應當能解決這個問題，并且應該是收斂的。簡而言之，我們可以說算法就是用來解決一個特定任務的一系列步驟15算法設計的要求正確性：算法的正確性是指算法至少應該具有輸入、輸出和加工處理無歧義性、能夠正確反映問題的需求、能夠得到問題的正確答案1算法程序沒有語法錯誤2算法程序對于合法的輸入數(shù)據(jù)能夠產生滿足要求的輸出結果3算法程序對于非法的輸入能夠得出滿足規(guī)格說明的結果4算法程序對于精心選擇的，甚至刁難的測試數(shù)據(jù)都能夠有滿足要求的輸出結果。算法設計的要求正確性：算法的正確性是指算法至少應該具有輸入、16可讀性：算法設計的另一目的是為了便于閱讀、理解和交流。健壯性：當輸入數(shù)據(jù)不合法時，算法也能做出相關處理，而不是產生異?；蚰涿畹慕Y果。時間效率與空間效率可讀性：算法設計的另一目的是為了便于閱讀、理解和交流。健壯性17算法效率的度量方法事后統(tǒng)計方法：主要是通過設計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低。事前分析估計方法：在計算機程序編制前，依據(jù)統(tǒng)計方法進行估算高級程序語言程序運行消耗時間取決于：1算法的策略，方法。2編譯產生的代碼質量3問題的輸入規(guī)模4機器執(zhí)行指令的速度算法效率的度量方法事后統(tǒng)計方法：主要是通過設計好的測試程序和18數(shù)據(jù)結構與算法課件19數(shù)據(jù)結構與算法課件20可以忽略加法常數(shù)可以忽略加法常數(shù)21與最高項相乘的常數(shù)并不重要與最高項相乘的常數(shù)并不重要22判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常?？梢院雎裕鼞撽P注最高階項的階數(shù)判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常?？梢院雎裕?3時間復雜度在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復雜度，也就是算法的時間度量，記作：T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的監(jiān)禁時間復雜度，簡稱為時間復雜度。其中，f(n)是問題規(guī)模n的某個函數(shù)。時間復雜度在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關于問24推導大O階：用常數(shù)1取代運行時間中的所有加法常數(shù)。在修改后的運行次數(shù)函數(shù)中，只保留最高階項。如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。得到的結果就是大O階。推導大O階：25數(shù)據(jù)結構與算法課件26數(shù)據(jù)結構與算法課件27數(shù)據(jù)結構與算法課件28數(shù)據(jù)結構與算法課件2930

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

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

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

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

序號存儲狀態(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

//

//

//32線性表(a1,a1,a2,...an)順序存儲結構的33線性表順序結構在C語言中的定義

其中：SqList----結構類型名

La----結構類型變量名

La.length---表長

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

};SqListLa;33線性表順序結構在C語言中的定義#definemaxle34線性表的順序存儲結構定義（動態(tài)）#defineList_Init_size100#defineListincrement10structSqList{ElemType*elem;intlength;intlistsize;};34線性表的順序存儲結構定義（動態(tài)）#defineList35 順序存儲結構的尋址公式

i=12in

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

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

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

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

a1a2...ai...an//////35 順序存儲結構的尋址公式a1a2...ai...an/36插入算法實現(xiàn)舉例 設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

36插入算法實現(xiàn)舉例37順序存儲結構的評價優(yōu)點：

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

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

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

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

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

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

(4)自由區(qū)中的存儲空間不能被其它數(shù)據(jù)共享37順序存儲結構的評價38線性表的鏈式存儲結構順序表：隨機存取鏈表：邏輯相鄰，物理不一定相鄰特點每個元素(表項)由結點(Node)構成。線性結構

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

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

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

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

有且僅有一個特定的稱為根的結點；⑵

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

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

ACBGFEDACBGFED有序樹、無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，65樹結構和線性結構的比較線性結構樹結構第一個數(shù)據(jù)元素根結點（只有一個）無前驅無雙親最后一個數(shù)據(jù)元素葉子結點(可以有多個)無后繼無孩子其它數(shù)據(jù)元素其它結點一個前驅,一個后繼一個雙親,多個孩子一對一一對多樹結構和線性結構的比較線性結構樹結構第一個數(shù)據(jù)元素根結點（只66二叉樹的定義

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

二叉樹的定義二叉樹是n（n≥0）個結點的有限集合，該集合或67二叉樹的特點：⑴每個結點最多有兩棵子樹；⑵二叉樹是有序的，其次序不能任意顛倒。

注意：二叉樹和樹是兩種樹結構。ABCDEFGABAB二叉樹的特點：⑴每個結點最多有兩棵子樹；注意：二叉樹和樹是68二叉樹的基本形態(tài)Ф空二叉樹只有一個根結點左子樹根結點只有左子樹右子樹根結點只有右子樹左子樹右子樹根結點同時有左右子樹二叉樹的基本形態(tài)Ф空二叉樹只有一個根結點左子樹根結點只有左子69具有3個結點的樹和具有3個結點的二叉樹的形態(tài)二叉樹和樹是兩種樹結構。具有3個結點的樹和具有3個結點的二叉樹的形態(tài)二叉樹和樹是兩種702.2二叉樹的性質

性質1二叉樹的第i層上最多有2i-1個結點（i≥1）。

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

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

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

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

n1

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

n1

＋n2

–1，同時有e=n1

＋2n2

因此得n0＋

n1

＋n2

–1=

n1

＋2n2

，于是得證。性質3對任何一棵非空二叉樹，如果葉子結點數(shù)為n0，度為73性質4具有n個結點的完全二叉樹的最小深度為log2(n+1)

。

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

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

2k-1-1…2k-12k-1———第k-1層———第k層…最少結點數(shù)最多結點數(shù)完全二叉樹是指除最后一層外，每一層上的結點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結點。性質4具有n個結點的完全二叉樹的最小深度為log2(74對不等式取對數(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ū)間對不等式取對數(shù)，有：k-1＜log2(n+1)≤kl75性質5對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結點（簡稱為結點i），有：

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

性質5表明，在完全二叉樹中，結點的層序編號反映了結點之間的邏輯關系一棵具有n個結點的完全二叉樹中從1開77二叉樹的遍歷操作

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

二叉樹的遍歷二叉樹的遍歷操作二叉樹的遍歷是指從根結點出發(fā)，按照78二叉樹的遍歷方式：VLR、LVR、LRV、VRL、RVL、RLV

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

考慮二叉樹的組成：訪問根結點記作V遍歷左子樹記作L遍歷右子樹記作R二叉樹二叉樹遍歷的遞歸算法二叉樹的遍歷方式：如果限定先左后右，則二叉樹遍歷方式有三種：79前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結點；②前序遍歷根結點的左子樹；③前序遍歷根結點的右子樹。前序遍歷序列：-+a*b-cd/ef二叉樹的遍歷操作

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

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

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

--/+*abcdef后序（根）遍歷后序遍歷序列：abcd-*+e82層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。

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

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

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

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

數(shù)據(jù)結構中討論的都是簡單圖。圖的基本術語簡單圖：在圖中，若不存在頂點到其自身的邊，且同88圖的基本術語

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

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

。

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

圖的基本術語

V1V2V3V1V2V3V4無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該93含有n個頂點的無向完全圖有多少條邊？含有n個頂點的有向完全圖有多少條??？

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

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

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

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

V1V2V3V4V1V2V5V3V4路徑：在無向圖G=(V,E)中，從頂點vp到頂點vq之間的97路徑長度：圖的基本術語

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

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

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

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

圖的鄰接矩陣存儲結構的空間復雜度？如果為稀疏圖則會出現(xiàn)什么現(xiàn)象？假設圖G有n個頂點e條邊，則存儲該圖需要O(n2)。鄰接表鄰接表存儲的基本思想：對于圖的每個頂點vi，將所有鄰接109鄰接表有兩種結點結構：頂點表結點和邊表結點。dataadjdestlink

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

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

dest：鄰接點域，邊的終點在頂點表中的下標。link：指針域，指向邊表中的下一個結點。

鄰接表有兩種結點結構：頂點表結點和邊表結點。dataadjd110template<classT,classE>structEdge{intdest;Ecost;Edge<T,E>*link;……};template<classT,classE>structVertex{

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

dataadj

destlinktemplate<classT,classE>定義鄰111圖的存儲結構的比較——鄰接矩陣和鄰接表O（n2）O（n+e）O（n2）O（n+e）空間性能時間性能適用范圍唯一性鄰接矩陣鄰接表稠密圖稀疏圖唯一不唯一圖的存儲結構的比較——鄰接矩陣和鄰接表O（n2）O（n+e）1123圖的遍歷圖的遍歷操作圖的遍歷是在從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次。

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

圖的遍歷操作要解決的關鍵問題解決方案：附設訪問標志數(shù)組visited[n]。解決方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。③因圖中可能存在回路，某些頂點可能會被重復訪問，那么如何避1161.深度優(yōu)先遍歷

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

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

1.深度優(yōu)先遍歷基本思想：⑴訪問頂點v；1172.廣度優(yōu)先遍歷

基本思想：⑴訪問頂點v；⑵依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk；⑶分別從v1，v2，…，vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問。直至圖中所有與頂點v有路徑相通的頂點都被訪問到。2.廣度優(yōu)先遍歷基本思想：⑴訪問頂點v；118一個有向圖包含頂點v={v1，v2，v3，v4，v5}，其鄰接矩陣如下：(1)畫出該圖；(2)畫出該圖的鄰接表；(3)試根據(jù)鄰接表，寫出自v1點出發(fā)的深度優(yōu)先搜索和廣度優(yōu)先搜索序列，并給出深度優(yōu)先搜索的詳細判斷過程。一個有向圖包含頂點v={v1，v2，v3，v4，v5}，其鄰119深度優(yōu)先序列：V1,V3,V2,V5,V4廣度優(yōu)先序列：V1,V3,V4,V2,V5深度優(yōu)先序列：V1,V3,V2,V5,V4120兩種遍歷算法時間性能的比較O（n2）O（n+e）O（n2）O（n+e）深度優(yōu)先搜索廣度優(yōu)先搜索鄰接矩陣鄰接表兩種遍歷算法時間性能的比較O（n2）O（n+e）O（n2）O1211.快速排序介紹：快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序n個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(nlogn)算法更快，因為它的內部循環(huán)（innerloop）可以在大部分的架構上很有效率地被實現(xiàn)出來，且在大部分真實世界的數(shù)據(jù)，可以決定設計的選擇，減少所需時間的二次方項之可能性。1.快速排序122步驟：從數(shù)列中挑出一個元素，稱為“基準”（pivot），重新排序數(shù)列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作。遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。步驟：123數(shù)據(jù)結構與算法課件1242.歸并排序介紹：歸并排序（Mergesort，臺灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（DivideandConquer）的一個非常典型的應用步驟：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列設定兩個指針，最初位置分別為兩個已經排序序列的起始位置比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置重復步驟3直到某一指針達到序列尾將另一序列剩下的所有元素直接復制到合并序列尾2.歸并排序125數(shù)據(jù)結構與算法課件1263.堆排序堆積排序（Heapsort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆性質：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。3.堆排序1274.選擇排序選擇排序(Selectionsort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。4.選擇排序1285.冒泡排序介紹：冒泡排序（BubbleSort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到沒有再需要交換，也就是說該數(shù)列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數(shù)列的頂端。5.冒泡排序129步驟：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。針對所有的元素重復以上的步驟，除了最后一個。持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數(shù)字需要比較。步驟：130數(shù)據(jù)結構與算法課件1316.插入排序介紹：插入排序（InsertionSort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。6.插入排序132步驟：從第一個元素開始，該元素可以認為已經被排序取出下一個元素，在已經排序的元素序列中從后向前掃描如果該元素（已排序）大于新元素，將該元素移到下一位置重復步驟3，直到找到已排序的元素小于或者等于新元素的位置將新元素插入到該位置中重復步驟2步驟：1337.希爾排序介紹：希爾排序，也稱遞減增量排序算法，是插入排序的一種高速而穩(wěn)定的改進版本。希爾排序是基于插入排序的以下兩點性質而提出改進方法的：1、插入排序在對幾乎已經排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率2、但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位>7.希爾排序134數(shù)據(jù)結構與算法課件135數(shù)據(jù)結構與算法DataStructureandAlgorithm數(shù)據(jù)結構與算法DataStructureandAlgo136數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。1968DonaldE.Knuth“TheArtofComputerProgramming”/~uno/計算機排版系統(tǒng)TEX程序設計=數(shù)據(jù)結構+算法數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象，以及137數(shù)據(jù)：描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別，并輸入給計算機處理的符號集合。數(shù)據(jù)元素：組成數(shù)據(jù)的、有一定意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。數(shù)據(jù)項：一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項組成。數(shù)據(jù)對象：性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)：描述客觀事物的符號，是計算機中可以操作的對象，是能138數(shù)據(jù)數(shù)據(jù)對象數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)數(shù)據(jù)對象數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)項數(shù)據(jù)元素139不同數(shù)據(jù)元素之間不是獨立的，而是存在特定的關系，將這些關系稱為結構。數(shù)據(jù)結構：相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合邏輯結構：數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系物理結構：是指數(shù)據(jù)的邏輯結構在計算機中的存儲形式。示意圖表示數(shù)據(jù)邏輯結構：將每一個數(shù)據(jù)元素看作一個結點，用圓圈表示。元素之間的邏輯關系用結點之間的連線表示，如果這個關系是有方向的，那么用帶箭頭的連線表示。不同數(shù)據(jù)元素之間不是獨立的，而是存在特定的關系，將這些關系稱140集合結構：集合結構中的數(shù)據(jù)元素，除了同屬于一個集合外，它們之間沒有其他關系。集合結構：集合結構中的數(shù)據(jù)元素，除了同屬于一個集合外，它們之141線性結構：線性結構中的數(shù)據(jù)元素之間是一對一的關系。線性結構：線性結構中的數(shù)據(jù)元素之間是一對一的關系。142樹形結構：樹形結構中的數(shù)據(jù)元素之間存在一對多的層次關系。樹形結構：樹形結構中的數(shù)據(jù)元素之間存在一對多的層次關系。143圖形結構：圖形結構的數(shù)據(jù)元素是多對多的關系圖形結構：圖形結構的數(shù)據(jù)元素是多對多的關系144物理結構順序存儲結構：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯關系和物理關系是一致的。物理結構順序存儲結構：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里145鏈式存儲結構：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。邏輯結構是面向問題的，物理結構是面向計算機的。物理結構的基本目的就是將數(shù)據(jù)及其邏輯關系存儲到計算機的內存中。鏈式存儲結構：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單146邏輯結構物理結構集合結構線性結構樹形結構圖形結構順序存儲結構鏈接存儲結構邏輯結構物理結構集合結構順序存儲結構147算法：解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作。算法的特性輸入：具有零個或多個輸入輸出：至少有一個或多個輸出有窮性：算法在執(zhí)行有限的步驟之后，自動結束而不會出現(xiàn)無線循環(huán)。確定性：算法的每一步都具有確定的含義，不會出現(xiàn)二義性?？尚行裕核惴ǖ拿恳徊蕉际强尚械?，即每一步都能通過執(zhí)行有限次數(shù)完成。算法：解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限148ThomasH.Cormen,ChalesE.Leiserson(2009)<算法導論>第三版“直白的說，算法就是任何明確定義的計算過程，它接收一些值或集合作為輸入，并產生一些值或集合作為輸出。這樣，算法就是將輸入轉換為輸出的一系列計算過程”ThomasH.Cormen,ChalesE.Le149簡而言之，我們可以說算法就是用來解決一個特定任務的一系列步驟。一個有效的算法應該含有三個重要特性：1

它必須是有限的：如果你設計的算法永無休止的嘗試解決問題，那么它是無用的。2它必須具備明確定義的指令：算法的每一步都必須準確定義，在任何場景下指令都應當沒有歧義。3它必須是有效的：一個算法被設計用以解決某個問題，那么它就應當能解決這個問題，并且應該是收斂的。簡而言之，我們可以說算法就是用來解決一個特定任務的一系列步驟150算法設計的要求正確性：算法的正確性是指算法至少應該具有輸入、輸出和加工處理無歧義性、能夠正確反映問題的需求、能夠得到問題的正確答案1算法程序沒有語法錯誤2算法程序對于合法的輸入數(shù)據(jù)能夠產生滿足要求的輸出結果3算法程序對于非法的輸入能夠得出滿足規(guī)格說明的結果4算法程序對于精心選擇的，甚至刁難的測試數(shù)據(jù)都能夠有滿足要求的輸出結果。算法設計的要求正確性：算法的正確性是指算法至少應該具有輸入、151可讀性：算法設計的另一目的是為了便于閱讀、理解和交流。健壯性：當輸入數(shù)據(jù)不合法時，算法也能做出相關處理，而不是產生異?；蚰涿畹慕Y果。時間效率與空間效率可讀性：算法設計的另一目的是為了便于閱讀、理解和交流。健壯性152算法效率的度量方法事后統(tǒng)計方法：主要是通過設計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低。事前分析估計方法：在計算機程序編制前，依據(jù)統(tǒng)計方法進行估算高級程序語言程序運行消耗時間取決于：1算法的策略，方法。2編譯產生的代碼質量3問題的輸入規(guī)模4機器執(zhí)行指令的速度算法效率的度量方法事后統(tǒng)計方法：主要是通過設計好的測試程序和153數(shù)據(jù)結構與算法課件154數(shù)據(jù)結構與算法課件155可以忽略加法常數(shù)可以忽略加法常數(shù)156與最高項相乘的常數(shù)并不重要與最高項相乘的常數(shù)并不重要157判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常?？梢院雎裕鼞撽P注最高階項的階數(shù)判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常常可以忽略，158時間復雜度在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復雜度，也就是算法的時間度量，記作：T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的監(jiān)禁時間復雜度，簡稱為時間復雜度。其中，f(n)是問題規(guī)模n的某個函數(shù)。時間復雜度在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關于問159推導大O階：用常數(shù)1取代運行時間中的所有加法常數(shù)。在修改后的運行次數(shù)函數(shù)中，只保留最高階項。如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。得到的結果就是大O階。推導大O階：160數(shù)據(jù)結構與算法課件161數(shù)據(jù)結構與算法課件162數(shù)據(jù)結構與算法課件163數(shù)據(jù)結構與算法課件164165

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

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

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

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

序號存儲狀態(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

//

//

//32線性表(a1,a1,a2,...an)順序存儲結構的168線性表順序結構在C語言中的定義

其中：SqList----結構類型名

La--