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

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

2、特性算法具備五個(gè)基本特性：輸入、輸出、有窮性、確定性和可行性1.輸入、輸出：算法具有零或多個(gè)輸入，至少有一或多個(gè)輸出。2.有窮性：算法在執(zhí)行有限步驟后，自動(dòng)結(jié)束而無限循環(huán)。且每一步在可接受時(shí)間內(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)點(diǎn)和缺點(diǎn) 優(yōu)點(diǎn)：n無需定制鏈表的容量n和刪除操作無需移動(dòng)數(shù)據(jù)元素 缺點(diǎn)：n數(shù)據(jù)元素必須保存后繼元素的位置信息n獲取指定數(shù)據(jù)的元素操作需要順序之前的元素3.棧與隊(duì)列3.1 棧(Stack)3.1.1 棧的基本概念 概念：首先，棧是一個(gè)線性表。也就是說，棧元素具有線性關(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)簡(jiǎn)稱鏈棧。思考如下問題：棧只是棧頂來做和刪除操作，棧頂放在鏈表的頭部還是尾部呢？由于單鏈表有頭指針，而棧頂指針也是必須的，那干嘛不讓他倆合二為一呢，所以比較好的辦法就是把棧頂放在單鏈表的頭部。另外都已經(jīng)有了棧頂在頭部了，單鏈表中比較常用的頭結(jié)點(diǎn)也就失去了意義，通常對(duì)于鏈棧來說，是不需要頭結(jié)點(diǎn)的。 設(shè)計(jì)與實(shí)現(xiàn)鏈棧是一種特殊的線性表，鏈?？梢酝ㄟ^鏈?zhǔn)骄€性表來實(shí)現(xiàn)。3.2 隊(duì)列(Queue)3.2.1 隊(duì)列基本概念隊(duì)列（queue）是一種特殊的受限線性表。只在一端進(jìn)行14，在另一端進(jìn)行

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

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

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

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

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

10、怎么辦呢? 可將其轉(zhuǎn)換成完全二后，再做。21但缺點(diǎn)也較明顯：浪費(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é)點(diǎn)結(jié)構(gòu)如下：22n 結(jié)點(diǎn)數(shù)據(jù)類型定義：4.3.3 二的遍歷遍歷定義指按某條搜索路線遍訪每個(gè)結(jié)點(diǎn)且不重復(fù)（又稱周游）。遍歷用途它是樹結(jié)構(gòu)、刪除、修改、查找和排序運(yùn)算的前提，是二一切運(yùn)算的基礎(chǔ)和。遍歷方法牢記一種約定，對(duì)每個(gè)結(jié)點(diǎn)的查看都是“先左后右” 。限定先左后右，樹的遍歷有三種實(shí)現(xiàn)方案：DLRLDRLRD先 (根)序遍歷中 (根)序遍歷后(根

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

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

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

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

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

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

17、n2+2n+1O(n2)平方階5log2n+20O(logn)對(duì)數(shù)階2n+3nlog2n+19O(nlogn)nlogn 階6n3+2n2+3n+4O(n3)立方階2nO(2n)指數(shù)階常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：5.2.1 簡(jiǎn)單練習(xí)28/ 時(shí)間復(fù)雜度:/ 空間復(fù)雜度:func sum1(n int) int var i intsum := 0for i = 0; i = n; i+ sum = sum + ifmt.Printf(%d, sum) return sum/ 時(shí)間復(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）的基本思想：比較相鄰兩個(gè)元素的關(guān)鍵字值，如果反序，則交換。 冒泡總結(jié)：29/ 時(shí)間復(fù)雜度:/ 空間復(fù)雜度:func test1(n int) var count int = 1 for count n count = count * 2/ 時(shí)間復(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í)，可以采用。數(shù)據(jù)規(guī)模比較大時(shí)，最好用其它排序方法。n 冒泡排序算法的平均時(shí)間復(fù)雜度一般為 O(n2 )，算法的空 間復(fù)雜度為 O(1)。 冒泡排序算法是穩(wěn)定的。5.3.2 選擇排序直接選擇排序（straight select sort）的基本思想：第一趟從 n 個(gè)元素的數(shù)據(jù)序列中選出關(guān)鍵字最?。ɑ蜃畲螅┑脑夭⒎诺阶钋埃ɑ蜃詈螅┪恢?，下一趟再從 n-1 個(gè)元素中選出最?。ù螅┑脑夭⒎诺酱吻埃ê螅┪恢茫源祟愅?，經(jīng)過 n-1 趟完成排

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

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