數據結構與算法2

第一章數據結構與算法主要內容1.1算法與數據結構概念

1.2線性表1.3棧和隊列1.4樹和二叉樹

1.5查找1.6內部排序1.1.1算法的根本概念定義：解題方案的準確而完整描述。特點(四個)：(一般填空題或選擇題)有窮性：包含有限個操作步驟，每個步驟都能在有限時間內完成。確定性：每一條指令無二義性。〔相同輸入只能得到相同輸出〕可行性：指定操作都可以實現。擁有足夠的情報：有輸入有輸出?！埠w面廣〕算法：是一組嚴謹地定義運算順序的規(guī)那么，并且每個規(guī)那么都是有效的、明確的，此順序在有限的次數下終止。2.算法根本要素及描述根本要素：算法中對數據的運算和操作(算術運算、邏輯運算、關系運算、數據傳輸)算法的控制結構算法的控制結構：順序、選擇、循環(huán)。3.算法的設計方法(1)列舉法：列舉出所有可能情況，用給定條件檢驗哪些是需要的，哪些是不需要的。例：百錢百雞問題。(2)歸納法：列舉少量簡單而又特殊的情況，分析歸納出一般結論。(3)遞推法：從初始條件出發(fā)，逐步推出各種中間結果和最后結果。例：猴子摘桃子問題。(5)回溯法：嘗試。分析找出解決線索，逐步試探成功：求得解失?。褐鸩交赝?，換線索再試探。(4)遞歸法：解決復雜問題時，將問題逐層分解，歸納為一些簡單問題，解決了最后簡單問題后，再沿原來的逆過程逐步綜合。例：求3！。(6)減半遞推技術：減少：問題規(guī)模減半，而性質不變遞推：重復減半的過程例：二分查找〔游戲猜數字〕1.1.2算法復雜度評價算法標準：時間復雜度和空間復雜度。

1算法的時間復雜度：定義：算法運行從開始到結束所需要的計算工作量。計算工作量：算法執(zhí)行過程中所需要的根本運算的執(zhí)行次數。算法的時間復雜度不僅依賴于問題的規(guī)模，也取決于輸入實例的初始狀態(tài)。

平均時間復雜度：所有可能的輸入實例均以等概率出現的情況下，算法的期望運行時間。最壞時間復雜度：最壞情況下算法的時間復雜度。最優(yōu)算法：隨n的增大，T(n)增長較慢的算法。2算法的空間復雜度：定義：算法運行從開始到結束所需的存儲空間量。一個算法在執(zhí)行時所占的空間包括算法程序所占的空間、輸入數據所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。用While語句求計算：s=1+2+3+…+100，代碼如下。main(){inti=1,s=0;while(i<=100){s=s+ii=i+1}}printf(“%d〞,s);此算法的時間復雜度為：1+2*100+1=202空間復雜度為：2假設100改為n,那么時間復雜度為:o(2n+2)1.2數據結構根本概念1.2.1數據結構的定義(1)數據：信息載體，能夠被計算機識別、存儲和加工處理?？梢允菙抵禂祿?整數、實數)，也可以是非數值數據(聲音、圖像等)。(2)數據元素：數據的根本單位，在計算機程序中通常作為一個整體進行考慮和處理(又稱結點、記錄)。數據模型包括數據結構、數據操作和數據約束。數據項：一個數據元素由假設干數據項組成，數據的不可分割的最小單位。關鍵碼：其值能唯一確定一個數據元素的數據項。舉例：圖書管理系統(tǒng)數據元素數據項關鍵碼書目信息中的一本書書目信息的每一項書號VisualBasic6.0作者(或出版社或定價)978-7(3)數據結構：定義：相互之間存在著一種或多種關系的數據元素的集合。研究內容:(記住兩種結構)如:(2-1空)①數據的邏輯結構：各數據元素之間的邏輯關系；②數據的存儲結構：各數據元素在計算機中的存儲關系；③對各種數據結構進行的運算：添加，刪除，排序等。1.數據的邏輯結構四類根本邏輯結構：(1)集合結構：數據元素間的關系是“屬于同一個集合〞。(2)線性結構：數據元素之間存在一個對一個的關系。(3)樹形結構：數據元素之間存在一個對多個的關系。(4)圖形結構：數據元素之間存在多個對多個的關系。學號姓名系別住址電話…...981111李洪機械六舍5371111982111王剛電子四舍5372111983211王將計算機五舍5373211983212張強機械六舎5372221…………………………線性結構樹型結構學校教研室部、處實驗室醫(yī)學院計算機…線性結構與非線性結構概念結點：組成數據結構的數據元素稱為一個結點。前后件關系：數據元素之間的固有關系可以用前后件關系(前驅與后繼關系)描述。舉例：家庭成員輩分關系(父親、兒子、女兒)，“父親〞是“兒子〞和“女兒〞的前件，“兒子〞和“女兒〞是“父親〞后件。線性結構有且只有一個根結點每個結點最多有一個前件，也最多有一個后件非線性結構一個數據結構如果不是線性結構，那么稱之為非線性結構。數據元素的前后關系復雜，一個結點既可以有多個前件，也可以有多個后件。樹型、圖形結構屬于非線性結構。2.數據的存儲結構定義：數據的邏輯結構在計算機存儲空間中的存放形式。

數據存儲結構中不僅存放各數據元素信息，還存放前后件關系的信息。實現方式：

(1)順序存儲方式：邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中。主要用于線性結構。通常借助于數組來實現。(2)鏈式存儲方式：對邏輯上相鄰的元素不要求其物理地址相鄰，元素間邏輯關系通過附加的指針字段來表示。通常借助于指針類型實現。(3)索引存儲方法和散列存儲方法〔為了查找方便〕。1.3線性表

線性表的根本概念定義：具有相同數據類型的n(n≥0)個數據元素組成的有限序列。最簡單、最常用的數據結構。

結構特點：(1)有且只有一個根結點，無前驅

。(2)有且只有一個終端結點

，無后繼。(3)其他結點有且只有一個直接前驅和一個直接后繼。1.3.2線性表的順序存儲結構

順序表：采用順序存儲結構的線性表稱為順序表(一維數組)。

順序存儲：用一組地址連續(xù)的存儲空間依次存儲線性表的各元素。特點(順序存儲結構)：表中的所有元素所占存儲空間連續(xù)表中各元素在存儲空間中按邏輯順序存放

第i個元素地址：m：每個元素占m個存儲單元Loc(a1)第一個元素地址(基址)

1.順序表(線性表)根本概念順序表的順序存儲結構存儲地址內存狀態(tài)元素在線性表中的位序bb+m...b+(i-1)m...b+(n-1)mb+nm...b+(maxlen-1)ma1a2......12...

i...n空閑aian2.順序表根本運算根本運算：插入：在線性表指定位置插入一個新元素刪除：刪除線性表中指定的元素查找：在線性表中查找特定元素排序：線性表中元素按關鍵字升序或降序排序分解：將一個線性表分解為多個合并復制逆轉

3插入運算：定義：是指在表的第i個位置上插入一個值為b的新元素原表長為n：(a1，a2，…ai-1，ai，ai+1，…

an)

新表長為n+1：(a1，a2，…ai-1，b，ai，ai+1，…，

an)

步驟：(1)將ai

~

an順序向后移動,為新元素讓出位置(2)將b置入空出的第i個位置舉例：(在第4個和第5個元素之間插入元素91)67412621489160123456786741262148916012345678674126214891601234567891時間性能分析：插入運算，時間主要消耗在數據移動上。在長度為n的線性表中插入一個元素，那么平均移動元素次數：Pi：在第i個位置上作插入的概率。設Pi=1/(n+1)共需移動(n-i+1)個元素。4刪除運算：定義：指將表中第i個元素從線性表中去掉。原表長為n：(a1，a2，…ai-1，ai

，ai+1，…

an)

新表長為n-1：(a1，a2，…ai-1，ai+1，…，

an)

步驟：(1)刪除ai(2)將ai+1

~an

順序向前移動舉例：(刪除第五個元素21)674126214891601234567867412648916012345678平均移動元素次數：5.順序表優(yōu)點和缺點優(yōu)點：邏輯上相鄰元素存儲位置也相鄰，無需增加額外存儲空間；可方便隨機存取表中任一元素。缺點：插入和刪除運算不方便，必須移動大量結點，效率較低；不適合元素經常變動的大的線性表。鏈式存儲結構的特點:每個結點由兩局部組成：一局部存放數據，另一局部存儲指向前件或后件結點的指針域。邏輯上相鄰的結點物理上不必相連。數據運算〔插入和刪除等〕靈活。1.3.3線性表的鏈式存儲結構

結點組成：數據結構中每個數據結點對應一個存儲單元，簡稱結點。

兩局部：數據域：存放數據元素值指針域：存放指針，指向后繼結點線性鏈表中用專門的HEAD指針指向第一個元素的結點，其最后一個元素沒有后件，因此最后一個結點指針域為空〔用NULL或0表示〕。1線性鏈表定義：線性表的鏈式存儲結構稱為線性鏈表。

分類：單鏈表、循環(huán)單鏈表、雙向鏈表2單鏈表定義：由n個結點鏈接，且每個結點中只包含一個指針域的鏈表。線性單鏈表(A,B,C,D,E,F)：邏輯狀態(tài)：

ABCDEHF物理狀態(tài)：E7FNULLB25A13C31D11713192531單鏈表存取：必須從頭指針開始進行，依次順著指針向鏈尾方向掃描。找到各個元素。(1)單鏈表插入：增加新結點,修改鏈接指針步驟：PBCXSA修改s指針域,s結點的后繼是p結點的后繼修改p指針域,使其指向新結點s(2)單鏈表刪除：不需要移動元素,僅修改指針鏈接。步驟：先找到p的前驅結點q刪除p結點，修改q結點指針域

q

next＝p

nextCPBA刪除前P刪除后qCBA1.4棧和隊列

1.4.1棧

1.棧的定義〔用于子程序調用等〕只允許在線性表的一端進行插入和刪除的線性表。

相關術語：(1)棧頂：允許插入與刪除的一端稱為棧頂。指針top指向棧頂位置。(2)棧底：不允許插入與刪除的一端稱為棧底。指針base指向棧底。(3)入棧：棧的插入操作(往棧中插入一個元素)(4)出棧：棧的刪除操作(從棧中刪除一個元素)(5)棧空：top=base(6)棧滿：top=m(m為棧最大容量)棧示意圖：原那么：先進后出或后進先出2順序棧及其運算棧的兩種存儲結構：順序存儲結構：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂的數據元素。鏈式存儲結構：也稱可利用棧。用于收集計算機存儲器中所有空閑存儲空間。順序棧：順序存儲結構的棧稱為順序棧。鏈棧：鏈式存儲結構棧稱為鏈棧。根本運算：入棧、退棧與讀棧頂元素(2)出棧步驟：棧頂元素賦給一個指定的變量。棧頂指針top減1。棧頂指針為0時，棧空，不能再退棧。稱為?！跋乱绋曞e誤。(1)入棧步驟：棧頂指針top加1。新元素插入到棧頂指針指向位置。棧頂指針指向存儲空間最后一個位置時，棧已滿，不能再入棧。稱為?！吧弦绋曞e誤。(3)讀棧頂元素概念：將棧頂元素賦給一個指定變量。注意：不刪除棧頂元素，棧頂指針不會改變。讀棧頂元素和出棧區(qū)別？舉例：topbottomABCDEF10987654321S(1:10)有6個元素的棧ABCDEFXYS(1:10)topbottom插入X和Y后的棧10987654321bottomABCDEFX10987654321S(1:10)top退出一個元素后的棧1.4.2隊列

定義：指允許在一端插入，而在另一端進行刪除的線性表。

相關術語(5個)：(1)隊尾：允許插入的一端稱為隊尾。rear隊尾指針，始終指向隊尾元素的下一個位置。(2)隊頭：允許進行刪除的一端稱為隊頭。front隊頭指針，始終指向隊頭元素。(3)入隊列：隊列插入操作(進隊列)(4)出隊列：隊列的刪除操作(退隊列)(5)空隊列：隊列中無數據元素原那么：先進先出或后進后出隊頭元素總是最先進隊列的,也總是最先出隊列隊尾元素總是最后進隊列,也是最后出隊列隊列結構示意圖：隊列Q=(a1，a2,…,an

)a1aia2an……隊頭隊尾退隊入隊1順序隊列定義：隊列的順序存儲結構稱為順序隊列，利用一組地址連續(xù)的存儲單元依次存放隊列中的數據元素。約定：初始化隊列：front=rear=0隊尾插入新元素，rear加1隊頭元素出隊列，front加1舉例：順序隊列頭尾指針變化情況：543210空隊rearfront

a1

a2

a3543210frontrear

a3543210frontrear

a3

a4

a5

a6543210frontrear缺點：如上例,隊列最大存儲空間為6，隊滿時再繼續(xù)插入元素就會上溢。隊尾指針已到達數組上界，不能在增大。而當前隊列可用空間并未占滿，“假滿〞現象。2循環(huán)隊列定義：將隊列存儲空間的最后一個位置繞到第一個位置，相成邏輯上的環(huán)形空間。判定條件：隊空：rear=front隊滿：方法1：rear=front，設一個標志變量S=0隊空1隊滿約定循環(huán)數組中元素個數到達M-1隊滿頭指針在尾指針下一位置上方法2：少一個元素空間循環(huán)隊列示意圖：02134567frontrear隊空02134567一般情況a1a2frontrear02134567隊滿(少一個元素)a1a2frontreara3a4a5a6a7設循環(huán)隊列中最多可容M個元素，那么循環(huán)隊列中元素的個數為：=rear-front(當rear>front)=(rear+M-front)(當rear>front)如左圖中元素個數:4+7-5=6設棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次通過棧S，并且一個元素出棧后即進入隊列Q，假設出隊的順序為b,d,c,f,e,a，那么棧S的容量至少應該為〔〕

〔A〕3〔B〕4〔C〕5〔D〕6一個棧的初始狀態(tài)為空。現將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，那么元素出棧的順序是〔〕〔A〕12345ABCDE〔B〕EDCBA54321〔C〕ABCDE12345〔D〕54321EDCBA如果不是依次入棧，然后再依次出棧，那么ABD均有可能。類似題：(2-3)AB★樹結構中結點之間有分支關系，層次關系，樹中無環(huán)路樹的一般表示：

ABCDEFGHIJK1.5樹與二叉樹1.5.1樹的根本概念樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。根結點在第一層。1.5.2二叉樹及其根本性質二叉樹的特點：〔1〕非空二叉樹只有一個根結點；〔2〕每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。二叉樹的五種根本形態(tài)(a)(b)(c)(d)(e)1什么是二叉樹2二叉樹的根本性質性質1二叉樹第i(i≥1)層上至多有2i-1個結點。證明：根結點在二叉樹的第一層上，這層結點數最多為1個，即20；第二層上最多有2個結點，即21個；…那么第i層上結點最多有2i-1個。性質2深度為k(k≥1)的二叉樹至多有2k-1個結點。證明：由性質(1)可知各層結點最多數目之和為：20+21+22+…+2k-1；由二進制換算關系可得2k–1，因此二叉樹樹中結點的最大數目為2k-1。性質3：度為0的結點〔即葉子結點〕總是比度為2的結點多一個。證明：設n代表二叉樹結點的總數，葉子結點(即度為零的結點)個數為n0，度為1的結點個數為n1，度為2的結點個數為n2。那么n=n0+n1+n2(1)有n個結點的二叉樹總邊數為n-1條：n-1=0*n0+1*n1+2*n2(2)將(1)式代入(2)式得：n0=n2+1滿二叉樹是指除最后一層外，每一層上的所有結點有兩個子結點，那么k層上有2k-1個結點,深度為m的滿二叉樹有2m-1個結點。完全二叉樹是指除最后一層外，每一層上的結點數均到達最大值，在最后一層上只缺少右邊的假設干結點。根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。設一棵完全二叉樹共有700個結點，那么在該樹中有多少個葉子結點？設該完全二叉樹中有x個度為０的結點〔即葉子結點〕，y個度為１的結點，ｚ個度為２的結點，那么：x+y+z=700①z=x-1②將②代入①可得：x=(700+1-y)/2③又y只能取0或1，分別代入③可得：x=350.5④〔不合理舍去〕或350⑤所以葉子結點數x=350思考：將700改成739，那么結果為多少？370滿二叉樹和完全二叉樹(a)滿二叉樹；(b)完全二叉樹；(c)非完全二叉樹FGDE1376542ABC(a)FDE136542ABC(b)FG13762ABC(c)性質4具有n個結點的完全二叉樹樹深為[log2n]+1。或者：具有n個結點的二叉樹，其深度至少為[log2n]+1。其中[log2n]表示取[log2n]的整數局部。性質5設完全二叉樹共有n個結點。如果從根結點開始，按層序〔每一層從左到右〕用自然數1，2，…n給結點進行編號〔k=1,2….n〕，有以下結論：①假設k=1，那么該結點為根結點，它沒有父結點；假設k>1，那么該結點的父結點編號為INT(k/2)；②假設2k≤n，那么編號為k的結點的左子結點編號為2k；否那么該結點無左子結點〔也無右子結點〕；③假設2k+1≤n，那么編號為k的結點的右子結點編號為2k+1；否那么該結點無右子結點。1.5.3二叉樹的遍歷遍歷二叉樹是指以一定的