1、算法與數(shù)據(jù)結構，教材：數(shù)據(jù)結構(C語言版本)。嚴為民，吳偉民編輯。清華大學出版社。參考文獻：1數(shù)據(jù)結構。張選平，雷主編，審核。機械工業(yè)出版社。2數(shù)據(jù)結構和算法分析。作者：克利福德謝弗，由張明和劉小丹翻譯。電子工業(yè)出版社。3數(shù)據(jù)結構練習和分析(C語言真實版)。李春寶。清華大學出版社。4數(shù)據(jù)結構和算法。夏克儉主編。國防工業(yè)出版社。目前，計算機已經(jīng)滲透到社會生活的各個領域，其應用不再局限于科學計算，而是更多地應用于控制、管理和數(shù)據(jù)處理等非數(shù)值計算領域。計算機是一門研究計算機對信息的表示和處理的科學。涉及到兩個問題：信息的表示和信息的處理。信息的表示和組織直接關系到信息處理程序的效率。隨著應用問題日益

2、復雜，信息量急劇增加，信息范圍不斷擴大，使得許多系統(tǒng)程序和應用程序規(guī)模龐大，結構復雜。因此，有必要分析待解決問題中對象的特征以及對象之間的關系，這是數(shù)據(jù)結構過程中需要研究的問題。編寫程序解決實際問題的一般過程：如何用數(shù)據(jù)形式描述問題？也就是說，從問題中抽象出一個合適的數(shù)學模型；問題涉及的數(shù)據(jù)量和數(shù)據(jù)之間的關系；如何在計算機中存儲數(shù)據(jù)并反映數(shù)據(jù)之間的關系。處理問題時，您需要對數(shù)據(jù)執(zhí)行哪些操作？書面程序的性能好嗎？上面列出的問題基本上都是通過數(shù)據(jù)結構課程來回答的。1.1數(shù)據(jù)結構及其概念、算法和數(shù)據(jù)結構是計算機科學中一門綜合性的專業(yè)基礎課。它是數(shù)學、計算機硬件和計算機軟件中的一門核心課程。它不僅是通

3、用程序設計的基礎，也是設計和實現(xiàn)編譯器、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)等系統(tǒng)程序和大規(guī)模應用的重要基礎。1.1.1數(shù)據(jù)結構示例，示例1:電話號碼查詢系統(tǒng)具有電話號碼簿，該電話號碼簿記錄了n個人的姓名及其相應的電話號碼。假設按如下方式排列：(a1，b1)，(a2，b2)，(an，bn)，其中ai，bi(i=1，2n)分別代表某人的姓名和電話號碼這個問題是典型的表格問題。如表1-1所示，數(shù)據(jù)和數(shù)據(jù)之間存在簡單的一對一線性關系。表1-1線性表結構，例2:磁盤目錄文件系統(tǒng)磁盤根目錄下有很多子目錄和文件，每個子目錄可以包含多個子目錄和文件，但是每個子目錄只有一個父目錄，等等：這個問題是一個典型的樹形結構問題，如圖

4、1-1所示，數(shù)據(jù)有一對多的關系，這是一個典型的具有非線性關系結構的樹形結構。圖1-1樹形結構，示例3:交通網(wǎng)絡圖可以有從一個地方到另一個地方的多條路徑。這是一個典型的網(wǎng)絡結構問題，數(shù)據(jù)和數(shù)據(jù)之間的關系是多對多的，是一種非線性關系結構。數(shù)據(jù)：它是客觀事物的象征性表現(xiàn)。在計算機科學中，它指的是可以輸入計算機并由計算機程序處理的所有符號。數(shù)據(jù)元素：它是數(shù)據(jù)的基本單位，通常在程序中作為一個整體來考慮和處理。一個數(shù)據(jù)元素可以由幾個數(shù)據(jù)項組成。數(shù)據(jù)項是不可分割的最小數(shù)據(jù)單元。數(shù)據(jù)項是對客觀事物特征的數(shù)據(jù)描述。數(shù)據(jù)對象：它是具有相同屬性的數(shù)據(jù)元素的集合和數(shù)據(jù)的子集。例如字符集C=A，B，C，1.1.2基本概

5、念和術語，數(shù)據(jù)結構：它是指相互之間有一定聯(lián)系(關系)的數(shù)據(jù)元素的集合。元素之間的關系稱為邏輯結構。數(shù)據(jù)元素之間有四種基本類型的邏輯結構，如圖1-3所示。集合：結構中的數(shù)據(jù)元素除了“屬于同一個集合”之外，沒有其他關系。線性結構：結構中的數(shù)據(jù)元素之間存在一對一的關系。樹形結構：結構中的數(shù)據(jù)元素之間有一對多的關系。圖結構或網(wǎng)絡結構：結構中的數(shù)據(jù)元素之間存在多對多的關系。數(shù)據(jù)結構的形式定義是一個二進制組：數(shù)據(jù)結構=(D，s)，其中：D是數(shù)據(jù)元素的有限集合，s是D上關系的有限集合.例2:讓數(shù)據(jù)邏輯結構B=(K，r) k=k1，k2，k9r=，畫出這個邏輯結構的圖，并確定哪些是起點，哪些是終點，1.1.3

6、數(shù)據(jù)結構的形式定義，圖1-3四個基本結構圖，1.1.1它也可以是一個人為定義的關系，以便于處理問題。這種自然或人為定義的“關系”稱為數(shù)據(jù)元素之間的邏輯關系，相應的結構稱為邏輯結構。計算機內(nèi)存中數(shù)據(jù)結構的存儲包括數(shù)據(jù)元素的存儲和元素之間關系的表示。在計算機中有兩種不同的方法來表達元素之間的關系：順序表示法和非順序表示法。因此，獲得了兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。順序存儲結構：數(shù)據(jù)元素之間的邏輯結構(關系)由數(shù)據(jù)元素在內(nèi)存中的相對位置來表示。鏈式存儲結構：在每個數(shù)據(jù)元素中添加一個指針來存儲另一個元素的地址，并使用這個指針來表示數(shù)據(jù)元素之間的邏輯結構(關系)。示例：有兩種不同的存儲

7、結構，數(shù)據(jù)集a=3.0、2.3、5.0、-8.5和11.0。序列結構：存儲數(shù)據(jù)元素的地址是連續(xù)的；鏈式結構：對于存儲數(shù)據(jù)元素的地址是否連續(xù)沒有要求。數(shù)據(jù)的邏輯結構和物理結構是不可分割的兩個方面。算法的設計取決于所選擇的邏輯結構，而算法的實現(xiàn)取決于所采用的存儲結構。在c語言中，順序存儲結構用一維數(shù)組表示；用結構類型表示鏈式存儲結構。數(shù)據(jù)結構有三個組成部分：邏輯結構：數(shù)據(jù)元素之間邏輯關系的描述存儲結構：數(shù)據(jù)元素在計算機中的存儲和邏輯關系的表達稱為數(shù)據(jù)的存儲結構或物理結構。數(shù)據(jù)操作：對數(shù)據(jù)執(zhí)行的操作。本課程將討論的三種邏輯結構及其存儲結構如圖1-4所示。數(shù)據(jù)類型：指一組值和在該組值上定義的一組操作。

8、數(shù)據(jù)類型是一個與數(shù)據(jù)結構密切相關的概念。在C語言中，數(shù)據(jù)類型有：基本類型和構造類型。數(shù)據(jù)結構不同于數(shù)據(jù)類型和數(shù)據(jù)對象。它不僅描述了數(shù)據(jù)類型的數(shù)據(jù)對象，還描述了數(shù)據(jù)對象元素之間的關系。1.1.5數(shù)據(jù)類型，數(shù)據(jù)結構的主要操作包括：創(chuàng)建數(shù)據(jù)結構；破壞數(shù)據(jù)結構；從數(shù)據(jù)結構中刪除數(shù)據(jù)元素；將數(shù)據(jù)元素插入到數(shù)據(jù)結構中；訪問數(shù)據(jù)結構；修改數(shù)據(jù)結構(其中的數(shù)據(jù)元素)；對數(shù)據(jù)結構進行排序；數(shù)據(jù)結構是搜索。1.1.6數(shù)據(jù)結構操作，抽象數(shù)據(jù)類型(ADT):指數(shù)學模型和在模型上定義的一組操作。ADT的定義只是一組邏輯特征的描述，與它在計算機中的表示和實現(xiàn)無關。因此，無論ADT的內(nèi)部結構如何變化，只要它的數(shù)學特性保持不

9、變，它就不會影響它的外部使用。ADT的形式定義是三重的：ADT=(D，s，p)，其中D是數(shù)據(jù)對象，s是D上的關系集，p是d. 1.2上的基本操作集。抽象數(shù)據(jù)類型，ADT的一般定義形式是：ADT數(shù)據(jù)對象：數(shù)據(jù)關系：基本操作：ADT，其中數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽代碼描述?；具\算的定義是：(1)初始條件：運算結果：初始條件：描述數(shù)據(jù)結構和參數(shù)在執(zhí)行運算前應該滿足的條件；如果不是，操作將失敗，并返回相應的錯誤消息。操作結果：描述數(shù)據(jù)結構的變化以及操作正常完成后返回的結果。1.3.1算法：它是對解決特定問題的方法(步驟)的描述，它是一個有限的指令序列，其中每個指令代表一個或多個操作。該算法具有以下

10、五個特點：有限性：算法必須總是在執(zhí)行完有限性步驟后完成，并且每一步都是在有限時間內(nèi)完成的。確定性：算法中的每條指令都必須有確切的含義。沒有含糊之處。該算法只有一個入口和一個出口。可行性：一個算法是可行的。也就是說，算法描述的操作可以通過執(zhí)行已經(jīng)實現(xiàn)了有限次數(shù)的基本操作來實現(xiàn)。1.3算法分析初步，輸入：一個算法有零個或多個輸入，這些輸入取自特定的對象集。輸出：一個算法有一個或多個輸出，這些輸出是與輸入有特定關系的量。一個算法可以用很多方式來描述，包括：用自然語言來描述它；用正式語言來描述；用計算機編程語言來描述。算法和程序是兩個不同的概念。計算機程序是使用某種編程語言的算法的具體實現(xiàn)。算法必須是

11、可終止的，這意味著不是所有的計算機程序都是算法。在本課程的學習、作業(yè)練習和計算機實踐中，算法是用C語言描述的。在實踐中，為了檢查算法是否正確，應該編寫一個完整的C語言程序。要評價一個好的算法，有以下標準：算法應該滿足特定問題的需要。可讀性：該算法應該便于人們閱讀和交流?？勺x算法有助于理解和修改算法。健壯性：算法應該有容錯處理。當輸入非法或錯誤的數(shù)據(jù)時，算法應該能夠做出適當?shù)姆磻蛱幚?，而不會產(chǎn)生無法解釋的輸出結果。通用性：算法應該是通用的，即算法的處理結果對通用數(shù)據(jù)集有效。1.3.2算法設計要求，算法執(zhí)行時間應由根據(jù)運行在計算機上的算法編譯的程序所消耗的時間來衡量。通常有兩種方法：事后統(tǒng)計：統(tǒng)

12、計計算機的執(zhí)行時間和實際占用空間。問題：你必須首先運行根據(jù)算法編譯的程序；根據(jù)軟硬件環(huán)境，很容易掩蓋算法本身的優(yōu)缺點；沒有真正的價值。預分析：找到算法的時間限制函數(shù)。1.3.3算法效率、效率和存儲要求的度量：效率是指算法的執(zhí)行時間；存儲需求是指算法執(zhí)行過程中所需的最大存儲空間。一般來說，兩者都與問題的規(guī)模有關。相關因素有：根據(jù)算法選擇哪種策略；問題的規(guī)模；編程語言；編譯器生成的機器代碼的質(zhì)量；機器執(zhí)行指令的速度；除了軟件和硬件等相關部門的因素外，可以認為特定算法的“運行工作量”的大小僅取決于問題的規(guī)模(通常用N表示)，或者是問題規(guī)模的函數(shù)。以算法分析和應用為例，算法中基本運算的重復執(zhí)行次數(shù)是問

13、題規(guī)模n的函數(shù)，其時間度量記錄為T(n)=O(f(n)，稱為算法的漸近時間復雜度。通常，它通常由最深循環(huán)語句中原始操作的執(zhí)行頻率(重復執(zhí)行次數(shù))來表示?！癘”的定義：如果f(n)是正整數(shù)n的函數(shù)，那么O(f(n)代表M0，因此當n為n0時，| f(n) | M | f(n0) |。時間復雜度的順序如下：O(1):常數(shù)時間順序O (n):線性時間順序O(n):對數(shù)時間順序O(nn):線性對數(shù)時間順序O (nk): k2，k次冪時間順序，例如，兩個N階方陣的乘法(I=1，I=N；I)對于(j=1；j=n；j)cij=0；對于(k=1；k=n；k)cij=aik * bkj；因為它是一個三重循環(huán)，每個循環(huán)是從1到n，總次數(shù)是nnn=n3，時間復雜度是T(n)=O(n3)x；s=0；如果把x自增看作一個基本運算，則語句的頻率為，即時間復雜度為(1)。如果s=0也被認為是一個基本運算，則語句頻率為，其時間復雜度仍為(1)，即常數(shù)階。例如(I=1；I=n；I)x；s=x；語句頻率為2n，時間復雜度為O(n)，為線性順序。例如(I=1；I=n；I)對于(j=1；j=n；j)x；s=x；語句的頻率為2n2，時間復雜度為O(n2)，為平方階。定理：如果A(n)=a m n m a m-1 n m-1 a1n a0是m次多項式，那么A(n)=O