【正文】 第一篇：數(shù)據(jù)結(jié)構(gòu)與算法分析總結(jié)數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析談到計(jì)算機(jī)方面的專業(yè)課程，我覺(jué)得數(shù)據(jù)結(jié)構(gòu)算是一門(mén)必不可少的課了，它是計(jì)算機(jī)從業(yè)和研究人員了解、開(kāi)發(fā)及最大程度的利用計(jì)算機(jī)硬件的一種工具。數(shù)據(jù)結(jié)構(gòu)與算法分析是兩門(mén)緊密聯(lián)系的課程,算法要靠好的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn),二者的關(guān)系是密不可分的,談到算法不得不講數(shù)據(jù)結(jié)構(gòu),談數(shù)據(jù)結(jié)構(gòu)也不可避免的要了解算法,好的算法一定有一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，很多算法實(shí)際上是對(duì)某種數(shù)據(jù)結(jié)構(gòu)實(shí)行的一種變換,研究算法也就是研究在實(shí)行變換過(guò)程中數(shù)據(jù)的動(dòng)態(tài)性質(zhì)。這兩門(mén)課程分別是我在大二和研一的時(shí)候?qū)W的，因?yàn)樗鼈兠芮械穆?lián)系，這里將其放在一起總結(jié)如下。什么是數(shù)據(jù)結(jié)構(gòu)呢？研究數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）以及它們之間的關(guān)系，且為該結(jié)構(gòu)定義相應(yīng)的運(yùn)算設(shè)計(jì)相應(yīng)的算法。這里的數(shù)據(jù)是指可輸入到計(jì)算機(jī)能被程序處理的符號(hào)的集合。其中，數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間邏輯關(guān)系的描述，邏輯結(jié)構(gòu)的分類有線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)，它有4類基本的存儲(chǔ)映射方法：；；；。在程序設(shè)計(jì)語(yǔ)言中，數(shù)據(jù)結(jié)構(gòu)直接反映在數(shù)據(jù)類型上，比如一個(gè)整型變量就是一個(gè)節(jié)點(diǎn)，根據(jù)類型給他分配內(nèi)存單元。抽象數(shù)據(jù)類型：一組值以及在這些值上定義的操作集合，它是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具，其特點(diǎn)是把數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立于應(yīng)用程序的一種抽象代數(shù)結(jié)構(gòu)。線性表結(jié)構(gòu)：由一系列元素組成的有序的序列，除了第一個(gè)元素和最后一個(gè)元素外，每個(gè)元素都只有一個(gè)直接前趨和直接后繼，元素的個(gè)數(shù)稱為線性表的長(zhǎng)度。它的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)方式它的優(yōu)點(diǎn)是存儲(chǔ)單元是連續(xù)的，適合快速訪問(wèn)元素內(nèi)容，鏈表的特點(diǎn)是動(dòng)態(tài)申請(qǐng)內(nèi)存空間，并通過(guò)指針來(lái)鏈接結(jié)點(diǎn)，按照線性表的前驅(qū)關(guān)系把一個(gè)個(gè)結(jié)點(diǎn)鏈接起來(lái)，這樣可以動(dòng)態(tài)地根據(jù)需要分配內(nèi)存空間，經(jīng)常用于插入新結(jié)點(diǎn)或刪除節(jié)點(diǎn)的需要，鏈表還可以根據(jù)結(jié)點(diǎn)中指針個(gè)數(shù)分為單鏈表、雙鏈表、循環(huán)鏈表等。在線性表結(jié)構(gòu)中有兩類特別的線性表：棧和隊(duì)列。棧是一種限制訪問(wèn)端口的線性表，常稱為后進(jìn)先出表。正是這種特殊的性質(zhì)使得棧的用途非常廣泛，比如在計(jì)算表達(dá)式的值時(shí)處理運(yùn)算符的先后次序，另外一個(gè)大的用處就是遞歸了，hanoi 塔就是最典型的用了遞歸的思想，在算法中，也有很多運(yùn)用遞歸思想的例子。隊(duì)列也屬于限制訪問(wèn)點(diǎn)的線性表，它的特點(diǎn)就是加入和刪除元素都只能在隊(duì)列的一端進(jìn)行，即隊(duì)列首出，隊(duì)列尾進(jìn)，最大的特點(diǎn)是先來(lái)先服務(wù)，先進(jìn)先出。因?yàn)檫@個(gè)特點(diǎn)，隊(duì)列常被用作消息緩沖器。在算法設(shè)計(jì)中，順序表主要用于檢索，而利用棧中的遞歸思想在算法中則應(yīng)用非常廣泛，如遞歸排序，分治算法等。樹(shù)結(jié)構(gòu)：是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是由一個(gè)根結(jié)點(diǎn)和若干葉結(jié)點(diǎn)組成的樹(shù)狀結(jié)構(gòu)，除了根結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)只能有一個(gè)父節(jié)點(diǎn)，可以有若干子結(jié)點(diǎn)，若干個(gè)樹(shù)結(jié)構(gòu)還可以構(gòu)成森林，樹(shù)的存儲(chǔ)結(jié)構(gòu)也分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，最典型的是左孩子右兄弟法。在樹(shù)結(jié)構(gòu)中比較重要的算法就是周游（遍歷）樹(shù)，有先根次序、后根次序以及中根次序。樹(shù)結(jié)構(gòu)中有幾類非常重要的特殊樹(shù)結(jié)構(gòu)，如二叉樹(shù)，B樹(shù)，B+樹(shù)等，其中，二叉樹(shù)應(yīng)用最為廣泛。二叉樹(shù)：是指每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)的樹(shù)結(jié)構(gòu)，具體細(xì)分，根據(jù)葉子結(jié)點(diǎn)的特性可分為滿二叉樹(shù)、完全二叉樹(shù)等。二叉樹(shù)的遍歷也分為深度優(yōu)先和廣度優(yōu)先。另外，二叉樹(shù)有幾條非常重要的性質(zhì)，這也使得它的應(yīng)用非常廣泛。在算法設(shè)計(jì)中，典型的利用樹(shù)的深度優(yōu)先遍歷的算法是回溯法，而典型的廣度優(yōu)先搜索算法是分枝定界法。圖：是一種較線性表和樹(shù)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。一般來(lái)講，數(shù)據(jù)的邏輯結(jié)構(gòu)可表示為結(jié)點(diǎn)的有窮集合K和K上的一個(gè)關(guān)系r,如果對(duì)K中結(jié)點(diǎn)相對(duì)于r的前驅(qū)、后繼個(gè)數(shù)加以限制，則可以分別定義線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖結(jié)構(gòu)，即：線性結(jié)構(gòu)：惟一前驅(qū)，惟一后繼，反映一種線性關(guān)系； 樹(shù)形結(jié)構(gòu)：惟一前驅(qū)，多個(gè)后繼，反映一種層次關(guān)系；圖結(jié)構(gòu)：不限制前驅(qū)的個(gè)數(shù)，亦不限制后繼的個(gè)數(shù)，反映一種網(wǎng)狀關(guān)系。通常用G=(V,E)代表一個(gè)圖，其中V是頂點(diǎn)集，E是邊集。圖分為有向圖和無(wú)向圖，圖的存儲(chǔ)方式有鄰接表和鄰接矩陣法。和樹(shù)類似的，圖中也需要周游，同樣有深度優(yōu)先搜索和廣度優(yōu)先搜索，而比樹(shù)的周游要更復(fù)雜，也更重要。在這一塊中，有兩種比較典型的求最短路徑和最小支撐樹(shù)的算法需要注意，它們分別是Dijkstra算法和Prim算法。另外需要注意的是圖的連通性。在算法設(shè)計(jì)中，典型的用到圖論的算法有貪心算法和動(dòng)態(tài)規(guī)劃算法。對(duì)于計(jì)算機(jī)科學(xué)來(lái)說(shuō)，算法的概念至關(guān)重要。通俗的講，算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程，或者嚴(yán)格來(lái)講，是由若干條指令組成的有窮序列，且滿足以下4條性質(zhì)；（1）輸入：有零個(gè)或多個(gè)由外部提供的量作為算法的輸入。（2）輸出：算法產(chǎn)生至少一個(gè)量作為輸出。（3）確定性：組成算法的每條指令是清晰的，無(wú)歧義的。（4）有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。我們研究一個(gè)算法或者評(píng)價(jià)一個(gè)算法主要是通過(guò)估計(jì)該算法的復(fù)雜性，包括時(shí)間復(fù)雜性和空間復(fù)雜性。空間復(fù)雜性是指使用該算法的程序在運(yùn)行時(shí)需要占用多少內(nèi)存空間，具體包括指令空間、數(shù)據(jù)空間和環(huán)境?？臻g。時(shí)間復(fù)雜性是指執(zhí)行該程序所需要的時(shí)間量級(jí)，通常是估算的時(shí)間，包括編譯時(shí)間和運(yùn)行時(shí)間。同時(shí)評(píng)價(jià)一個(gè)算法的好壞還要看其時(shí)間復(fù)雜性和空間復(fù)雜性隨著輸入規(guī)模的增長(zhǎng)趨勢(shì)，一般能接受的最好是線性增長(zhǎng)。在算法設(shè)計(jì)這本書(shū)中，每介紹一個(gè)算法都會(huì)分析其算法復(fù)雜度，由此可看出它的重要性。首先，從遞歸的分治算法開(kāi)始。分治算法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。遞歸的解這些子問(wèn)題，然后將各個(gè)子問(wèn)題的解合并得到原問(wèn)題的解。該算法的主要應(yīng)用有大整數(shù)乘法，矩陣乘法、合并排序等。可以大大降低算法的時(shí)間復(fù)雜度，但使用遞歸?？赡茉黾映绦虻目臻g規(guī)模。動(dòng)態(tài)規(guī)劃算法和貪心算法：與分治算法類似，動(dòng)態(tài)規(guī)劃的基本思想也是將待求解問(wèn)題分解成若干子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治算法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解得到的子問(wèn)題往往不是相互獨(dú)立的。動(dòng)態(tài)規(guī)劃算法適用于解最優(yōu)化問(wèn)題。通?？砂匆韵?個(gè)步驟：（1）找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征。（2）遞歸的定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。動(dòng)態(tài)規(guī)劃算法的基本要素是最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問(wèn)題的最優(yōu)解所包含的子問(wèn)題的解也是最優(yōu)的，我們就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問(wèn)題提供了重要線索。子問(wèn)題重疊性質(zhì)。子問(wèn)題重疊性質(zhì)是指在用遞歸演算法自頂向下對(duì)問(wèn)題進(jìn)行求解時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在一個(gè)表格中