【正文】 其時間復雜度為： O(n) ? 即時間復雜度為線性階。++I) ? {++x。 ? 例３、 for(I=1。s=0。++k) c[I][j]+=a[I][k]*b[k][j]。 for(k=1。j=n。 例１、 for(I=1， I=n。 ? 算法效率的度量 ? 對一個算法要作出全面的分析可分成兩用人才個階段進行，即 事先分析 和 事后測試 ? 事先分析 求出該算法的一個時間界限函數(shù) ? 事后測試 收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料。 來自 的資料庫下載 ? (4)效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。 (3)健狀性 (Robustness) 算法應(yīng)具有容錯處理。 ? (2)可讀性 (Readability) 算法應(yīng)該好讀。 ? 5） 輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。且算法只有一個入口和一個出口。 ? （ 2） 確定性 算法中每一條指令必須有確切的含義。 ? 例 整數(shù)的數(shù)據(jù)對象是 {… 3， 2， 1， 0， 1，2， 3， …} ? 英文字符類型的數(shù)據(jù)對象是 {A， B， C， D， E，F(xiàn)， …} 來自 的資料庫下載 ? 抽象數(shù)據(jù)類型的表示和實現(xiàn) ? P11 來自 的資料庫下載 ? 算法和算法分析 ? 算法 ：是對特定問題求解步驟的一種描述 ? 算法是指令的有限序列，其中每一條指令表示一個或多個操作。 來自 的資料庫下載 ? 數(shù)據(jù)類型 ：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。 ? 用三元組描述如下： ? （Ｄ，Ｓ，Ｐ） 來自 的資料庫下載 ? 數(shù)據(jù)結(jié)構(gòu)在計算機中有兩種不同的表示方法： ? 順序表示和非順序表示 ? 由此得出兩種不同的存儲結(jié)構(gòu)： 順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu) ? 順序存儲結(jié)構(gòu) :用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系 。 ? 抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。 ? 數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。 數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為數(shù)據(jù)的 物理結(jié)構(gòu) ，又稱為 存儲結(jié)構(gòu) 。 例 復數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下： Complex=(C， R) 其中： C是含兩個實數(shù)的集合 ﹛ C1， C2﹜ ，分別表示復數(shù)的實部和虛部。 ? 四、 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。 ? 二、 線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。 來自 的資料庫下載 ? 數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu) ? 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。是數(shù)據(jù)的一個子集。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。 ? 數(shù)據(jù)元素 (Data Element):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 來自 的資料庫下載 ? 基本概念和術(shù)語 ? 數(shù)據(jù) (Data):是對信息的一種符號表示。 假定名字和其電話號碼邏輯上已安排成 N元向量的形式，它的每個元素是一個數(shù)對 (ai，bi)， 1≤i≤n 數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運算的算法。 ? 上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題。 來自 的資料庫下載 ? 算法的設(shè)計，依賴于計算機如何存儲人的名字和對應(yīng)的電話號碼，或者說依賴于名字和其電話號碼的結(jié)構(gòu)。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個例子。 來自 的資料庫下載 ? ? 眾所周知，計算機的程序是對信息進行加工處理。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當復雜。數(shù) 據(jù) 結(jié) 構(gòu) 計算機系 來自 載 來自 的資料庫下載 第一章 緒 論 什么是數(shù)據(jù)結(jié)構(gòu) 基本概念和術(shù)語 抽象數(shù)據(jù)類型的表示與實現(xiàn) 算法和算法分 算法 算法設(shè)計的要求 算法效率的度量 算法的存儲空間的需求 來自 的資料庫下載 第一章 緒 論 ? 計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題： ? 信息的表示 信息的處理 而信息的表示和組又直接關(guān)系到處理信息的程序的效率。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。 ? 例 電話號碼查詢系統(tǒng) ? 設(shè)有一個電話號碼薄，它記錄了 N個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排： ? (a1， b1)(a2， b2)…(a n， bn) ? 其中 ai， bi(i=1， 2…n) 分別表示某人的名字和對應(yīng)的電話號碼要求設(shè)計一個算法，當給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。 ? 數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率?？蓪⒚趾蛯?yīng)的電話號碼設(shè)計成：二維數(shù)組、表結(jié)構(gòu)、向量。 來自 的資料庫下載 例 圖書館的書目檢索系統(tǒng)自動化問題 例 教師資料檔案管理系統(tǒng) 例 多叉路口交通燈的管理問題 P3 通過以上幾例可以直接地認為：數(shù)據(jù)結(jié)構(gòu) 就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們 之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算， 而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然 是原來的結(jié)構(gòu)類型。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。 ? 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。 ? 數(shù)據(jù)對象 (Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。 ? 數(shù)據(jù)結(jié)構(gòu) (Data Structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常分為四類基本結(jié)構(gòu)： ? 一、 集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。 ? 三、 樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。 ? 來自 的資料庫下載 數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組： DataStructure=(D， S) 其中： D是數(shù)據(jù)元素的有限集， S是 D上關(guān)系的有限集。 R={P}， P是定義在集合上的一種關(guān)系 {〈 C1， C2〉 }。 來自 的資料庫下載 ? 數(shù)據(jù)對象可以是有限的，也可以是無限的。 ? 抽象數(shù)據(jù)類型：一個數(shù)學模型以及定義在該模型上的一組操作。因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。 ? 鏈式存儲結(jié)構(gòu)： 在每一個數(shù)據(jù)元素中增加一個存放地址的指針（ ），用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 ? 例 在 FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實型、和復數(shù)型 ? 例 在 C語言中 ? 數(shù)據(jù)類型：基本類型和構(gòu)造類型 ? 基本類型：整型、浮點型、字符型 ? 構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義 ? 數(shù)據(jù)對象 ：某種數(shù)據(jù)類型元素的集合。 ? 算法具有以下五個特性： ? （ 1） 有窮性 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。不存在二義性。 ? （ 3） 可行性 一個算法是可行的。 來自 的資料庫下載 ? 4） 輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。 ? 算法設(shè)計的要求 ? 評價一個好的算法有以下幾個標準 : ? (1) 正確性 (Correctness ) 算法應(yīng)滿足具體問題的需求。以有利于閱讀者對程序的理解。當輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。一般，這兩者與問題的規(guī)模有關(guān)。 ? 定義：如果存在兩個正常數(shù) c和 n0，對于所有的n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳ ? 則記作 f(n)=O(g(n)) 來自 的資料庫下載 一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模 n的某個函數(shù)，算法的時間量度記作 T(n)=O(f(n)) 稱作算法的漸近時間復雜度。++I) for(j=1。++j) { c[I][j]=0。k=n。 } 來自 的資料庫下載 ? 由于是一個三重循環(huán)，每個循環(huán)從 1到 n，則總次數(shù)為 : n n n=n3 ? 時間復雜度為 T(n)=O(n3) ?頻度 ：是指該語句重復執(zhí)行的次數(shù) ? 例２ {++x。} ? 將 x自增看成是基本操作，則語句頻度為１，即時間復雜度為Ｏ (1) ? 如果將 s=0也看成是基本操作，則語句頻度為２，其時間復雜度仍為Ｏ (1)，即常量階。I=n。s+=x。 來自 的資料庫下載 ? 例４、 for(I=1。++I) ? for(j=1。++j) ? {++x。} ? 語句頻度為： 2n2 ? 其時間復雜度為： O(n2) ? 即時間復雜度為平方階。 例５ for(i=2。++I) for(j=2。++j) {++x。} 來自 的資料庫下載 ?語句頻度為： ? 1+2+3+…+n 2=(1+n2) (n2)/2 ? =(n1)(n2)/2 ? =n23n+2 ? ∴ 時間復雜度為 O(n2) ? 即此算法的時間復雜度為平方階 . ? 一個算法時間為 O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。而一個時間為 O(n2)的算法則由一個二次多項式來限界。其關(guān)系為： ? O(1)O(logn)O(n)O(nlogn) ? O(n2)O(n3) ?指數(shù)時間的關(guān)系為： ? O(2n)O(n!)O(nn) ? 當 n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。 來自 的資料庫下載 ? 有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。change=TURE。amp。I) ? { ? change=false。jI。 ? change=TURE} ? } ? 最好情況： 0次 ? ? 來自 的資料庫下載 ?最壞情況： 1+2+3+…+n 1 ? =n(n1)/2 ? 平均時間復雜度為 :O(n2) ? ?空間復雜度 :算法所需存儲空間的度量，記作 : ? S(n)=O(f(n)) ?其中 n為問題的規(guī)模 (或大小 ) 來自 的資料庫下載 第二章 線性表 ? 線性表的類型定義 ? 線性表的順序表示和實現(xiàn) ? 線性表的鏈式表示和實現(xiàn) ? 線性鏈表 循環(huán)鏈表 雙向鏈表 一元多項式的表示及相加