06數(shù)據(jù)結(jié)構(gòu)講義

1、1.3.2 算法的比較現(xiàn)在我們需要寫一個求 1 + 2 + 3 + + 100 的結(jié)果程序，你應(yīng)該怎么寫呢？大多數(shù)人可以馬上寫出下面 go 語言代碼實現(xiàn)（或者其他語言）但是，如果這個問題讓來去做，他可能會寫如下代碼：很顯然，不論是從人類還是計算機(jī)的角度來看，上述算法效率會高出很多。因此，一個好的算讓你的程序更加高效。1.3.3算法的分類1.分治（分布治理）：有明確的目標(biāo)，明確的執(zhí)行方式。一般采用 拆分、解決小問題、合并的流程來加以實現(xiàn)。2.最短路徑：有明確的目標(biāo)，需要找尋有效的執(zhí)行方式。3.貪婪（貪心）：沒有明確的目標(biāo)，沒有有效的執(zhí)行方式。需要現(xiàn)場分析，獲取目標(biāo)，找尋執(zhí)行方式。1.3.4算法的

2、特性算法具備五個基本特性：輸入、輸出、有窮性、確定性和可行性1.輸入、輸出：算法具有零或多個輸入，至少有一或多個輸出。2.有窮性：算法在執(zhí)行有限步驟后，自動結(jié)束而無限循環(huán)。且每一步在可接受時間內(nèi)完成。3.確定性：算法的每一步驟都有明確的含義，出現(xiàn)二義性。4.可行性：算法的每一步都必須是可行的。即，每一步都能通過執(zhí)行有限次數(shù)完成。2sum := 0n := 100sum = (1+n)*n/2 fmt.Printf(%d,sum)var i int sum := 0n := 100for i = 0; i next = current-next; current-next = node;2.3.

3、2 優(yōu)點和缺點 優(yōu)點：n無需定制鏈表的容量n和刪除操作無需移動數(shù)據(jù)元素 缺點：n數(shù)據(jù)元素必須保存后繼元素的位置信息n獲取指定數(shù)據(jù)的元素操作需要順序之前的元素3.棧與隊列3.1 棧(Stack)3.1.1 棧的基本概念 概念：首先，棧是一個線性表。也就是說，棧元素具有線性關(guān)系，即前驅(qū)后繼關(guān)系。只不過它是一種特殊的線性表而已。通常描述棧，說性表的表尾進(jìn)行和刪除操作，這里表尾是指棧頂，而不是棧底。 特性13current-next = ret-next;棧的特殊之處在于限制了線性表和刪除，始終在棧頂進(jìn)行。這使得：棧底是固定的，最先進(jìn)棧的數(shù)據(jù)只能在棧底。 操作n 棧的操作，叫做進(jìn)棧或壓棧。類似入（如下

4、圖所示）n 棧的刪除操作，叫做出?；驈帡?、退棧。如同中的出夾（如下圖所示）3.1.2 棧的鏈?zhǔn)?基本概念棧的鏈?zhǔn)浇Y(jié)構(gòu)簡稱鏈棧。思考如下問題：棧只是棧頂來做和刪除操作，棧頂放在鏈表的頭部還是尾部呢？由于單鏈表有頭指針，而棧頂指針也是必須的，那干嘛不讓他倆合二為一呢，所以比較好的辦法就是把棧頂放在單鏈表的頭部。另外都已經(jīng)有了棧頂在頭部了，單鏈表中比較常用的頭結(jié)點也就失去了意義，通常對于鏈棧來說，是不需要頭結(jié)點的。 設(shè)計與實現(xiàn)鏈棧是一種特殊的線性表，鏈?？梢酝ㄟ^鏈?zhǔn)骄€性表來實現(xiàn)。3.2 隊列(Queue)3.2.1 隊列基本概念隊列（queue）是一種特殊的受限線性表。只在一端進(jìn)行14，在另一端進(jìn)行

5、刪除操作。采用先進(jìn)先出的（First In First Out）的原則，簡稱 FIFO。的一端為隊尾，刪除的一端為隊頭。隊列不在中間部位進(jìn)行操作！假設(shè)隊列是 q=（a1，a2，an），那么 a1 就是隊頭元素，而 an 是隊尾元素。這樣我們就可以刪除時，總是從 a1 開始，而時，總是在隊列最后。這也比較符合我們通常生活中的習(xí)慣，排在第一個的優(yōu)先出列，最后來的當(dāng)然排在隊伍最后。如下圖：3.2.2 隊列的鏈?zhǔn)疥犃幸彩且环N特殊的線性表；可以用線性表鏈?zhǔn)絹砟M隊列的鏈?zhǔn)健?54.二4.1 樹的基本概念樹的定義：由一個或多個(n0)結(jié)點組成的有限集合 T，有且僅有一個結(jié)點稱為根（root），當(dāng) n1 時

6、，其余的結(jié)點分為m(m0)個互不相交的有限集合 T1,T2，Tm。每個集合本身又是棵樹，被稱作這個根的子樹。樹的結(jié)構(gòu)特點n 非線性結(jié)構(gòu)，有一個直接前驅(qū)，但可能有多個直接后繼（1:n）n 樹的定義具有遞歸性，還有樹。n 樹可以為空，即節(jié)點個數(shù)為 0。若干術(shù)語n 根 即根結(jié)點(沒有前驅(qū))n 葉子 即終端結(jié)點(沒有后繼)n 森林 指m 棵不相交的樹的集合(例如刪除 A 后的子樹個數(shù))n 有序樹 結(jié)點各子樹從有序，不能互換（第一）n 無序樹 結(jié)點各子樹可互換位置。n 雙親 即上層的那個結(jié)點(直接前驅(qū)) parentn 孩子 即下層結(jié)點的子樹 (直接后繼) child16兄弟 同一雙親下的同層結(jié)點（孩子

7、之間互稱兄弟）siblingn堂兄弟 即雙親位于同一層的結(jié)點（但并非同一雙親）cousinn祖先 即從根到該結(jié)點所經(jīng)分支的所有結(jié)點n子孫 即該結(jié)點下層子的任一結(jié)點n結(jié)點 即樹的數(shù)據(jù)元素n結(jié)點的度 結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度）n結(jié)點的層次 從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）n終端結(jié)點 即度為 0 的結(jié)點，即葉子n分支結(jié)點 除樹根以外的結(jié)點（也稱為內(nèi)部結(jié)點）n樹的度 所有結(jié)點度中的最大值（Max各結(jié)點的度）n樹的深度(或高度) 指所有結(jié)點中最大的層數(shù)（Max各結(jié)點的層次）n下圖(c)中的結(jié)點數(shù) 10，樹的度 3，樹的深度 34.2 樹的表示法4.2.1 圖形表示法事物之間的邏輯關(guān)系

8、可以通過數(shù)的形式很直觀的表示出來，如下圖：174.2.2 廣義表表示法用廣義表表示法表示上圖：中國（河北（保定，石家莊），（廣州，東莞），山東（青島，濟(jì)南）根作為由子樹森林組成的表的名字寫在表的左邊。184.2.3右兄弟表示法右兄弟表示法可以將一顆多轉(zhuǎn)化為一顆二：節(jié)點的結(jié)構(gòu)：節(jié)點有兩個指針域，其中一個指針點，另一個指針指向其兄弟節(jié)點。4.3 二概念4.3.1 二基本概念 定義：二（binary tree）是 n（n0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二組成 。 基本特征:19n 每個結(jié)點最多只有兩棵子樹（不存在度大于 2 的結(jié)點）；n 左子右子樹次序不

9、能顛倒（有序樹）。 基本形態(tài):l 二性質(zhì)性質(zhì) 1:若根節(jié)點的層次為 1，則二第 i 層上至多有 2i-1 個結(jié)點（i0）n性質(zhì) 2:在高度為 k 的二中，最多有 2k-1 個結(jié)點（k0）。n 滿二一棵深度為 k 且有 2k -1 個結(jié)點的二。特點：每層都“充滿”了結(jié)點 完全二除最后一層外，每一層上的節(jié)點數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點。20理解：k-1 層與滿二完全相同，第 k 層結(jié)點盡力靠左對完全二，若從上至下、從編號，則編號為 i 的結(jié)點，其編號必為 2i，其右孩子編號必為 2i1；其雙親的編號必為 i/2（i1, 除外）使用此性質(zhì)，可以將完全二實現(xiàn)樹的順序。如果不是完全二

10、怎么辦呢? 可將其轉(zhuǎn)換成完全二后，再做。21但缺點也較明顯：浪費(fèi)空間、刪除不便。4.3.2 二的表示二主要采用鏈?zhǔn)浇Y(jié)構(gòu)，順序結(jié)構(gòu)僅適用于完全二和滿二，還有靜態(tài)鏈表。 二的順序結(jié)構(gòu) 二的鏈?zhǔn)浇Y(jié)構(gòu)二的鏈?zhǔn)浇Y(jié)構(gòu)主要有二叉鏈表和三叉鏈表兩種。二叉鏈表n二叉鏈表的節(jié)點結(jié)構(gòu)如下：22n 結(jié)點數(shù)據(jù)類型定義：4.3.3 二的遍歷遍歷定義指按某條搜索路線遍訪每個結(jié)點且不重復(fù)（又稱周游）。遍歷用途它是樹結(jié)構(gòu)、刪除、修改、查找和排序運(yùn)算的前提，是二一切運(yùn)算的基礎(chǔ)和。遍歷方法牢記一種約定，對每個結(jié)點的查看都是“先左后右” 。限定先左后右，樹的遍歷有三種實現(xiàn)方案：DLRLDRLRD先 (根)序遍歷中 (根)序遍歷后(根

11、)序遍歷n DLR先序遍歷，即先根再n LDR中序遍歷，即先左再根再右n LRD后序遍歷，即先再根23type BinaryNode struct Ch byteLChild *BinaryNode RChild *BinaryNode注：“先、中、后”的意思是指的結(jié)點 D 是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的路徑是相同的，只是結(jié)點的時機(jī)不同。從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過 3 次。n 第 1 次經(jīng)過時先序遍歷n 第 2 次經(jīng)過時中序遍歷n 第 3 次經(jīng)過時后序遍歷5.排序算法5.1 排序基本概念現(xiàn)實生活中排序很重要，例如：

12、淘寶按條件搜索的結(jié)果展示等。l 概念排序是計算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的數(shù)據(jù)元素調(diào)整為“有序”的數(shù)據(jù)元素。l 排序數(shù)學(xué)定義：假設(shè)含 n 個數(shù)據(jù)元素的序列為 R1, R2, , Rn，其相應(yīng)的關(guān)鍵字序列為 K1, K2, , Kn這些關(guān)鍵字相互之間24可以進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系 ：Kp1Kp2Kpn按此固有關(guān)系將上式序列重新排列為 Rp1, Rp2, ，Rpn的操作稱作排序排序的穩(wěn)定性l如果在序列中有兩個數(shù)據(jù)元素 ri和 r j，它們的關(guān)鍵字 ki = k j，且在排序之前，對象 ri排在 r j前面。如果在排序之后，對象 ri仍在 r j前面，則稱這個排

13、序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。排序中的關(guān)鍵操作ln 比較：任意兩個數(shù)據(jù)元素通過比較操作確定先后次序。n 交換：數(shù)據(jù)元間需要交換才能得到預(yù)期結(jié)果。內(nèi)排序和外排序ln 內(nèi)排序：在排序過，待排序的所有全部都放置在內(nèi)存中，排序分為：內(nèi)排序和外排序。n 外排序：由于排序的個數(shù)太多，不能同時放置在內(nèi)存，整個排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行。排序的審判l(wèi)n 時間性能：關(guān)鍵性能差異體現(xiàn)在比較和交換的數(shù)量n 輔助空間：為完成排序操作需要的額外的空間，必要時可以“空間換時間”n 算法的實現(xiàn)復(fù)雜性：過于復(fù)雜的排序影響代碼的可讀性和可維護(hù)性，也可能影響排序的性能總結(jié)l25n 排序是數(shù)據(jù)元素

14、從無序到有序的過程n 排序具有穩(wěn)定性，是選擇排序算法的因一n 比較和交換是排序的基本操作n 多關(guān)鍵字排序與單關(guān)鍵字排序無本質(zhì)區(qū)別n 排序的時間性能是區(qū)分排序算法好壞的主要因素5.2 大 O 表示法在編，同一個編程問題，十個程序員可能會寫出十種不同的程序，算法各不相同，卻能解決同樣的問題。程序員對算法的效率十分在乎，盡管無論算法效率高度都能解決問題，但效率高的算法除了能夠解決問題，還可以在問題規(guī)模變大變復(fù)雜的時候高效的解決問題。那么眾多解決同樣問題的算法，我們?nèi)绾稳ピu價這些算法，從什么角度去評價這些算法呢？評價算法時，應(yīng)該結(jié)合數(shù)據(jù)量來評價，當(dāng)數(shù)據(jù)量增大時，算法所消耗的時間變化趨勢。在計算機(jī)世界，

15、這種粗略的評價方式稱為“大 O 表示法”。算法的執(zhí)行時間一般是最主要的評價標(biāo)準(zhǔn)。然而存在一個問題，不同的編程語言，不同的編譯器，或不同的CPU 等因素將導(dǎo)致執(zhí)行一次操作的時間各不相同，這樣的結(jié)果會使算法的比較產(chǎn)生歧義，于是我們假定所有計算機(jī)執(zhí)行一次相同的基本操作所需要的時間是相同的，而把算法中最基本操作的最大次數(shù)作為量度。也就是說我們把算法的執(zhí)行時間簡單的用基本操作的執(zhí)行次數(shù)來代替了。基本操作是什么？它可以是基本的運(yùn)算，賦值，比較，交換。當(dāng)要處理的數(shù)據(jù)，基本操作要重復(fù)執(zhí)行的次數(shù)必定會增長，那么我們關(guān)心的是這個執(zhí)行次數(shù)是以什么樣的數(shù)量級增長。這個所謂的數(shù)量級被稱為算法的漸進(jìn)時間復(fù)雜度。如何分析這

16、個數(shù)量級呢？由于基本操作的執(zhí)行次數(shù)是問題規(guī)模 n 的一個函數(shù) T(n),所以問題就是要確定這個函數(shù) T(n)是什么？然后分析它的數(shù)量級，O 是數(shù)量級的標(biāo)記。怎么一個算法的效率？（規(guī)則如下）26一個算法的效率時，往往只需要關(guān)注操作數(shù)量的最高次項，其他次要常數(shù)項可以忽略。ll 在沒有特殊說明時，我們所分析的算法的時間復(fù)雜度都是指最壞時間復(fù)雜度l 只有常數(shù)項記做 1l 操作數(shù)量的估算，可以作為時間復(fù)雜度的估算總結(jié)：u 只關(guān)注最高次項u 時間復(fù)雜度是指最壞時間復(fù)雜度u 只有常數(shù)項記做 1常見的時間復(fù)雜度n 常見的時間復(fù)雜度之間的關(guān)系27執(zhí)行次數(shù)函數(shù)階非正式術(shù)語12O(1)常數(shù)階2n+3O(n)線性階3

17、n2+2n+1O(n2)平方階5log2n+20O(logn)對數(shù)階2n+3nlog2n+19O(nlogn)nlogn 階6n3+2n2+3n+4O(n3)立方階2nO(2n)指數(shù)階常用的時間復(fù)雜度所耗費(fèi)的時間從小到大依次是：5.2.1 簡單練習(xí)28/ 時間復(fù)雜度:/ 空間復(fù)雜度:func sum1(n int) int var i intsum := 0for i = 0; i = n; i+ sum = sum + ifmt.Printf(%d, sum) return sum/ 時間復(fù)雜度:/ 空間復(fù)雜度:func sum2(n int) int sum := 0n = 100sum

18、= (1+n)*n/2 fmt.Printf(%d,sum) return sumO(1) O(logn) O(n) O(nlogn) O(n2) O(n3) O(2n) O(n!) O(nn)5.3 常見排序算法5.3.1 冒泡排序冒泡排序（bubble sort）的基本思想：比較相鄰兩個元素的關(guān)鍵字值，如果反序，則交換。 冒泡總結(jié)：29/ 時間復(fù)雜度:/ 空間復(fù)雜度:func test1(n int) var count int = 1 for count n count = count * 2/ 時間復(fù)雜度:/ 空間復(fù)雜度:func test2(n int) var i, j intfo

19、r i = 0; i n; i+ for j = i; j n; j+ fmt.Println(i + j)n 冒泡排序是一種效率低下的排序方法，在數(shù)據(jù)規(guī)模很小時，可以采用。數(shù)據(jù)規(guī)模比較大時，最好用其它排序方法。n 冒泡排序算法的平均時間復(fù)雜度一般為 O(n2 )，算法的空 間復(fù)雜度為 O(1)。 冒泡排序算法是穩(wěn)定的。5.3.2 選擇排序直接選擇排序（straight select sort）的基本思想：第一趟從 n 個元素的數(shù)據(jù)序列中選出關(guān)鍵字最?。ɑ蜃畲螅┑脑夭⒎诺阶钋埃ɑ蜃詈螅┪恢茫乱惶嗽購?n-1 個元素中選出最?。ù螅┑脑夭⒎诺酱吻埃ê螅┪恢?，以此類推，經(jīng)過 n-1 趟完成排

20、序。1.直接選擇排序算法描述2.直接選擇排序算法分析直接選擇排序的比較次數(shù)為n(n -1)n-1n2C = (n - i) =22i=1直接選擇排序算法的時間復(fù)雜度為 O(n2 )，算法的空間復(fù)雜度為 O(1)。 直接選擇排序算法是不穩(wěn)定的。5.3.3排序排序算法是一種簡單的排序算法，也稱為直接排序算法。它是一種穩(wěn)定的排序算法，對局部有序的數(shù)據(jù)具有較高的效率。30排序算法是一個隊少量元素進(jìn)行排序的有效算法。比如，是我們使用排序方法最多的日常生活例子。我們在摸牌時，一般會重復(fù)一下步驟。期初，我們手里沒有牌，摸出第一張，隨意放在左手上，以后每一次摸排，都會按照花色從小到大排列，直到所有的牌摸完。排

21、序算法采用的類似思路，每一次從無序序列中拿出一個數(shù)據(jù)，將它放到已排序的序序列的正確位置，如此重復(fù)，直到所有的無序序列中的數(shù)據(jù)都找到了正確位置。315.3.4排序排序（shell sort）又稱縮小增量排序，它的基本思想：分組的直接排序。1、排序算法描述：322、排序算法分析排序算法實際所需的時間取決于具體的增量序列， 所以它的時間復(fù)雜度分析比較復(fù)雜， 一般為O(n(log2n)2 ) ，算法的空間復(fù)雜度為 O(1)。排序算法不穩(wěn)定。5.3.5 快速排序快速排序（quick sort）是一種分區(qū)交換排序算法，它的基本思想：在數(shù)據(jù)序列中選擇一個值作為比較的基準(zhǔn)值， 每趟從數(shù)據(jù)序列的兩端開始交替進(jìn)行，將小于基準(zhǔn)值的元素交換到序列前端，將大于基準(zhǔn)值的元素交換到序列后端， 介于兩者之間的位置則成為基準(zhǔn)值的最終位置。1.快速排序算法描述：33上述數(shù)據(jù)序列的快速排序（升序）過程如下圖所示。2.快速排序算法分析快速排序算法的平均時間復(fù)雜度為 O(nlog2n)，算法的平均空間復(fù)雜度為 O(log2n)。快速排序算法不穩(wěn)定。345.3.6 堆排序堆排序