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