演算法結構與演算法分析

Ⅰ 數據結構與演算法分析

本文出自：

www點54manong點com

請尊重原創，轉載請註明出處，謝謝！

什麼是數據結構，為什麼要學習數據結構？數據結構是否是一門純數學課程？它在專業課程體系中起什麼樣的作用？我們要怎麼才能學好數據結構？… 相信同學們在剛開始《數據結構》這門課的學習時，心裡有著類似前面幾個問題的這樣那樣的疑問。希望下面的內容能幫助大家消除疑惑，下定決心堅持學好這門課：

1 學習數據數據結構的意義

數據結構是計算機科學與技術專業、計算機信息管理與應用專業，電子商務等專業的基礎課，是十分重要的核心課程。所有的計算機系統軟體和應用軟體都要用到各種類型的數據結構。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設計語言是難以應付當前眾多復雜的課題。要想有效地使用計算機、充分發揮計算機的性能，還必須學習和掌握好數據結構的有關知識。打好「數據結構」這門課程的扎實基礎，對於學習計算機專業的其他課程，如操作系統、資料庫管理系統、軟體工程、編譯原理、人工智慧、圖視學等都是十分有益的。

2 為什麼要學習數據結構

在計算機發展的初期，人們使用計算機的目的主要是處理數值計算問題。當我們使用計算機來解決一個具體問題時，一般需要經過下列幾個步驟：首先要從該具體問題抽象出一個適當的數學模型，然後設計或選擇一個解此數學模型的演算法，最後編出程序進行調試、測試，直至得到最終的解答。例如，求解梁架結構中應力的數學模型的線性方程組，可以使用迭代演算法來求解。

由於當時所涉及的運算對象是簡單的整型、實型或布爾類型數據，所以程序設計者的主要精力是集中於程序設計的技巧上，而無須重視數據結構。隨著計算機應用領域的擴大和軟、硬體的發展，非數值計算問題越來越顯得重要。據統計，當今處理非數值計算性問題佔用了85%以上的機器時間。這類問題涉及到的數據結構更為復雜，數據元素之間的相互關系一般無法用數學方程式加以描述。因此，解決這類問題的關鍵不再是數學分析和計算方法，而是要設計出合適的數據結構，才能有效地解決問題。下面所列舉的就是屬於這一類的具體問題。

例1：圖書館信息檢索系統。當我們根據書名查找某本書有關情況的時候；或者根據作者或某個出版社查找有關書籍的時候，或根據書刊號查找作者和出版社等有關情況的時候，只要我們建立了相關的數據結構，按照某種演算法編寫了相關程序，就可以實現計算機自動檢索。由此，可以在圖書館信息檢索系統中建立一張按書刊號順序排列的圖書信息表和分別按作者、書名、出版社順序排列的索引表，如圖1.1所示。由這四張表構成的文件便是圖書信息檢索的數學模型，計算機的主要操作便是按照某個特定要求（如給定書名）對圖書館藏書信息文件進行查詢。

諸如此類的還有學生信息查詢系統、商場商品管理系統、倉庫物資管理系統等。在這類文檔管理的數學模型中，計算機處理的對象之間通常存在著的是一種簡單的線性關系，這類數學模型可稱為線性的數據結構。

例2：八皇後問題。在八皇後問題中，處理過程不是根據某種確定的計演算法則，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態。從最初的布局狀態開始，一步步地進行試探，每試探一步形成一個新的狀態，整個試探過程形成了一棵隱含的狀態樹。如圖1.2所示（為了描述方便，將八皇後問題簡化為四皇後問題）。回溯法求解過程實質上就是一個遍歷狀態樹的過程。在這個問題中所出現的樹也是一種數據結構，它可以應用在許多非數值計算的問題中。

例3：教學計劃編排問題。一個教學計劃包含許多課程，在教學計劃包含的許多課程之間，有些必須按規定的先後次序進行，有些則沒有次序要求。即有些課程之間有先修和後續的關系，有些課程可以任意安排次序。這種各個課程之間的次序關系可用一個稱作圖的數據結構來表示，如圖1.3所示。有向圖中的每個頂點表示一門課程，如果從頂點vi到vj之間存在有向邊<vi，vj>，則表示課程i必須先於課程j進行。由以上三個例子可見，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如線性表、樹、圖之類的數據結構。因此，可以說數據結構課程主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。

學習數據結構的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來並對它們進行處理。與此同時，通過演算法訓練來提高學生的思維能力，通過程序設計的技能訓練來促進學生的綜合應用能力和專業素質的提高。

3數據結構課程的內容

數據結構與數學、計算機硬體和軟體有十分密切的關系，它是介於數學、計算機硬體和計算機軟體之間的一門計算機專業的核心課程，是高級程序設計語言、操作系統、編譯原理、資料庫、人工智慧、圖視學等課程的基礎。同時，數據結構技術也廣泛應用於信息科學、系統工程、應用數學以及各種工程技術領域。

數據結構課程重在討論軟體開發過程中的方案設計階段、同時設計編碼和分析階段的若干基本問題。此外，為了構造出好的數據結構及其實現，還需考慮數據結構及其實現的評價與選擇。因此，數據結構的內容包括三個層次的五個「要素」，如圖1.3所示。

數據結構的核心技術是分解與抽象。通過分解可以劃分出數據的三個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現細節，就得到運算的定義。上述兩個方面的結合使我們將問題變換為數據結構。這是一個從具體（即具體問題）到抽象（即數據結構）的過程。然後，通過增加對實現細節的考慮進一步得到存儲結構和實現運算，從而完成設計任務。這是一個從抽象（即數據結構）到具體（即具體實現）的過程。熟練地掌握這兩個過程是數據結構課程在專業技能培養方面的基本目標。

結束語：數據結構作為一門獨立的課程在國外是從1968年才開始的，但在此之前其有關內容已散見於編譯原理及操作系統之中。20世紀60年代中期，美國的一些大學開始設立有關課程，但當時的課程名稱並不叫數據結構。1968年美國唐.歐.克努特教授開創了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本演算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。從20世紀60年代末到70年代初，出現了大型程序，軟體也相對獨立，結構程序設計成為程序設計方法學的主要內容，人們越來越重視數據結構。從70年代中期到80年代，各種版本的數據結構著作相繼出現。目前，數據結構的發展並未終結，一方面，面向各專門領域中特殊問題的數據結構得到研究和發展，如多維圖形數據結構等；另一方面，從抽象數據類型和面向對象的觀點來討論數據結構已成為一種新的趨勢，越來越被人們所重視。

Ⅱ 數據結構與演算法分析 —— C 語言描述：二叉樹

二叉樹（binary tree）是一棵樹，其中每個節點的兒子都不能多於兩個。

二叉樹的一個性質是平均二叉樹的深度要比 N 小的多，這個性質有時很重要。分析表明，這個平均深度為 ，而對於特殊類型的二叉樹，即二叉查找樹(binary search tree)。其深度的平均值是 。不幸的是，在最壞情況下，這個深度可以大到 N-1 的。

因為一棵二叉樹最多有兩個兒子，所以我們可以用指針直接指向它們。樹節點的聲明在結構上類似於雙鏈表的聲明，在聲明中，一個節點就是由 key（關鍵字）信息加上兩個指向其他節點的指針（Left 和 Right）組成的結構。

應用於鏈表上的許多法則也可以應用到樹上。特別地，當進行一次插入時，必須調用 malloc 創建一個節點。節點可以在調用 free 刪除後釋放。

我們可以用在畫鏈表時常用的矩形框畫出二叉樹，但是，樹一般畫成圓圈並用一些直線連接起來，因為二叉樹實際上就是圖（graph）。當涉及樹時，我們也不顯示地畫出 NULL 指針，因為具有 N 個節點的每一棵二叉樹都將需要 N+1 個 NULL 指針。

二叉樹有許多與搜索無關的重要應用。二叉樹的主要用處之一是在編譯器的設計領域。

上圖就是一個表達式樹（expression tree）。表達式樹的樹葉是操作樹（operand），比如常數或者變數，而其他的節點為操作符（operator）。由於這里所有的操作都是二元的，因此這棵特定的樹正好是二叉樹，雖然這是最簡單的情況，但是節點含有的兒子還是有可能多於兩個的。一個節點也有可能只有一個兒子，如果有一目減算符（unary minus operator）的情形。可以將通過遞歸計算左子樹和右子樹所得到的值應用在根處的算符操作中而算出表達式樹 T 的值。上面里的例子中，左子樹的值是「((3+1) 3)/((9-5)+2)」，右子樹的值是「(3 (7-4)+6)」，因此整棵樹的表達式就是圖上的結果。

我們可以通過遞歸產生一個帶括弧的左表達式，然後列印出在根處的運算符，最後再遞歸地產生一個帶括弧的右表達式而得到一個（對兩個括弧整體進行計算的）中綴表達式（infix expression）。這種一般的方法（左，節點，右）稱為中序遍歷（inorder traversal）；由於其產生的表達式類型，這種遍歷很容易記憶。

另一個遍歷策略是遞歸列印出左子樹、右子樹，然後列印運算符。如果我們應用這種策略於上面的樹，則輸出將是「31+3 95-2+/743- 6+-」。這種遍歷策略一般稱為後序遍歷（postorder traversal）。

第三種遍歷策略是先列印出運演算法，然後遞歸地列印出右子樹和左子樹。同樣的，應用這種策略於上面的樹，則輸出將是「-/ ++313-952+ 3-746」，這是一種不太常用前綴（prefix）記法，這種遍歷策略為先序遍歷（preorder traversal）。

這里我們只給出一種演算法，來把後綴表達式轉變成表達式樹。這里的要點是，一次一個符號地讀入表達式。如果符號是操作符，那麼我們就建立一個單節點樹並將一個指向它的指針推入棧中。如果符號是操作符，那麼我們就從棧中彈出指向兩棵樹 和 的那兩個指針( 的先彈出)並形成一棵新的樹，該樹的根就是操作符，它的左、右兒子分別指向 和 。然後將這棵新樹的指針壓入棧中。

Ⅲ 什麼是數據結構和演算法分析在編程里起到什麼作用

編程是為了解決問題，這些問題並表都是數值計算，其所處理的數據並不都是數值，但計算機所能處理的最終是0和1的二進制串，所以需要把問題中的數據用計算機能處理的方式來表示，這就需要數據結構。

簡單的說，數據結構是數據在計算機中的表示方式，有邏輯結構和物理結構之分，如邏輯上同樣的隊列，物理上可以是順序存儲，也可以是鏈式存儲。

通俗的講，演算法就是解決問題的方法，比如同樣的排序，可以用冒泡排序、插入排序等，不同的演算法可以達到相同的目標，但是效率可能有所不同。

Ⅳ 計算機考研：數據結構常用演算法解析(7)

第七章：
對於無向圖，e的范圍是：
數據結構中所討論的圖都是簡單圖，任意兩結點間不會有雙重的邊。
對於有向圖，e的范圍是：
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊，但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點，索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方，就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖，另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中，凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG)：是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式，但是利用有向無環圖可以實現對相同子式的共享，從而節省存儲空間。
頂點的度：
無向圖：某頂點V的度記為D(V)，代表與V相關聯的邊的條數
有向圖：頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中，若圖中任意兩頂點間都存在路徑，則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是：往一個連通分量中再加入頂點和邊，就構不成原圖中的一個 連通子圖，即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。

考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/

Ⅳ 數據結構與演算法分析 —— C 語言描述：開放定址法

分離鏈接散列演算法的缺點是需要指針，由於給新單元分配地址需要時間，因此這就導致演算法的速度多少有些緩慢，同時演算法實際上還要求實現另一種數據結構。除使用鏈表解決沖突外，開放定址散列法（open addressing hashing）是另外一種用鏈表解決沖突的方法。在開放定址散列演算法系統中，如果有沖突發生，那麼就要嘗試選擇另外的單元，直到找出空的單元為止。更一般地，單元 相繼試選，其中 ，且 。函數 F 是沖突解決方法，因為所有的數據都要置入表內，所以開放定址散列法所需要的表要比分離鏈接散列用的表大。一般說來，對開放定址散列演算法來說，裝填因子應該低於 。開放定址散列法有三種常用的沖突解決辦法：

在線性探測法中，函數 F 是 的線性函數，典型的情形是 。這相當於逐個探測每個單元（必要時可以繞回）以查找出一個空空單元。即插入一個第一個沖突關鍵字，它將被放入下一個空閑地址，即地址 0，該地址是開放的。之後插入的沖突關鍵字，會對表進行試選，只要表足夠大，總能夠找到一個自由單元，但是如此花費的時間是相當多的。更糟的是，即使表相對較空，這樣占據的單元也會開始形成一些區塊，其結果稱為一次聚集（primary clustering），於是，散列到區塊中的任何關鍵字都需要多次試選單元才能解決沖突，然後該關鍵字被添加到相應的區塊中。

可以證明，使用線性探測的預期探測次數對於插入和不成功的查找來說大約為 ，而對於成功的查找來說則是 。略加思考不難得出，成功查找應該比不成功查找平均花費較少的時間。

如果聚算不算是問題，那麼對應的公式就不難得到。我們假設有一個很大的表，並設每次探測都與前面的探測無關。對於隨機沖突解決辦法而言，這些假設是成立的，並且當 不是非常接近 1 時也是合理的。首先，我們導出在一次不成功查找中探測的期望次數，而這正是直到我們找到一個空單元的探測次數。由於空單元所佔的份額為 ，因此我們預計要探測的單元數是 。一次成功查找的探測次數等於該特定元素插入時所需要的探測次數。當一個元素被插入時，可以看成是一次不成功查找的結果。因此，我們可以使用一次不成功查找的開銷來計算一次成功查找的平均開銷。

需要指出， 在 0 到當前值之間的變化，因此早期的插入操作開銷較少，從而降低平均開銷。我可以通過使用積分計算插入時間平均值的方法來估計平均值，如此得到

這些公式顯然優於線性探測相應的公式，聚集不僅是理論上的問題，而且實際上也發生在具體的實現中。線性探測的預計探測次數與 呈正比，即 越小，插入操作平均次數越少。

平方探測是消除線性探測中一次聚集問題的沖突解決辦法。平方探測就是沖突函數為二次函數的探測方法。流行的選擇是 。

對於線性探測，讓元素幾乎填滿散列表並不是個好主意，因為此時表的性能會降低。對於平方探測情況甚至更糟：一旦表被填滿超過一半，當表的大小不是素數時甚至在表被填滿超過一半之前，就不能保證一次找到一個空單元了。這是因為最多有一半的表可以用作解決沖突的備選位置。

定理：如果使用平方探測，且表的大小是素數，那麼當表至少有一半是空的時候，總能夠插入一個新的元素。

哪怕表有比一半多一個的位置被填滿，那麼插入都有可能失敗（雖然這是非常難以見到的，但是把它記住很重要。）。另外，表的大小是素數也非常重要，如果表的大小不是素數，則備選單元的個數可能會銳減。

在開放定址散列表中，標準的刪除操作不能施行，因為相應的單元可能已經引起過沖突，元素繞過它存在了別處。例如，如果我們刪除一個沖突的中間元素，那麼實際上所有其他的 Find 常式都將不能正確運行。因此，開放定址散列表需要懶惰刪除，雖然在這種情況下並不存在真正意義上的懶惰。

開放定址散列表的類型聲明如下，這里，我們不用鏈表數組，而是使用散列表項單元的數組，與在分離鏈接散列中一樣，這些單元也是動態分配地址的。

初始化開放定址散列表的常式如下，由分配空間（第1～10行）及其後將每個單元的 Info 域設置為 Empty 組成。

使用平方探測散列法的 Find 常式如下。如果分裂鏈接散列法一樣， 將返回 Key 在散列表中的位置。如果 Key 不出現，那麼 Find 將返回最後的單元。該單元就是當需要時，Key 將被插入的地方。此外，因為被標記了 Empty，所以表達 Find 失敗很容易。為了方便起見，我們假設散列表的大小至少為表中元素個數的兩倍，因此平方探測方法總能夠實現。否則，我們就要在第 4 行前測試 。在下面的常式中，標記為刪除的那些元素被認為還在表內，這可能引起一些問題，因為該表可能提前過滿。

第 4～6 行為進行平方探測的快速方法。由平方解決函數的定義可知， ，因此，下一個要探測的單元可以用乘以 2（實際上就是進行一位二進制移位）並減 1 來確定。如果新的定位越過數組，那麼可以通過減去 TableSize 把它拉回到數組范圍內。這比通常的方法要快，因為它避免了看似需要的乘法和除法。注意一條重要的警告：第 3 行的測試順序很重要，切勿改變它。

下面的常式是插入。正如分離鏈接散列方法那樣，若 Key 已經存在，則我們就什麼也不做。其他工作只是簡單的修改。否則，我們就把要插入的元素放在 Find 常式指出的地方。

雖然平方探測排除了一次聚集，但是散列到同一位置上的那些元素將探測相同的備選單元。這叫做二次聚集（secondary clustering）。二次聚集是理論上的一個小缺憾，模擬結果指出，對每次查找，它一般要引起另外的少於一半的探測。

雙散列（double hashing）能夠解決平方探測中的二次聚集問題，不過也需要花費另外的一些乘法和除法形銷。對於雙散列，一種流行的選擇是 。這個公式是說，我們將第二個散列函數應用到 X 並在距離 , 等處探測。 選擇的不好將會是災難性的。

在雙散列時，保證表的帶下為素數是非常重要的。假設我們在插入一個關鍵字的時候，發現它已經引發沖突，就會選擇備選位置，如果表的大小不是素數，那麼備選單元就很有可能提前用完。然後，如果雙散列正確實現，則模擬表明，預期的探測次數幾乎和隨機沖突解決方法的情形相同。這使得雙散列理論上很有吸引力，不過，平方探測不需要使用第二個散列函數，從而在實踐中可能更簡單並且更快。