第一章 緒 論.doc

第一章 緒 論1.1 為什么要學習數(shù)據(jù)結(jié)構(gòu)1.2 數(shù)據(jù)結(jié)構(gòu)概念歷史定義1.1數(shù)據(jù)是指對象的表示，即按照適合于通信、解釋或處理（借助人或自動裝置）的方式所形成的關(guān)于事實、概念或指令的表示；數(shù)據(jù)只是表示，而無含義3。數(shù)據(jù)是計算機科學與技術(shù)中最基本的概念，它是計算機程序要處理的“原料”，是所有被計算機識別、存儲和加工處理的符號的總稱4,5。元素、結(jié)點或頂點，數(shù)據(jù)項（也稱為域或字段） 數(shù)據(jù)元素（或曰數(shù)據(jù)成分）還可被稱為元素、結(jié)點或頂點等。數(shù)據(jù)元素可大可小，大到可以是一篇文稿、一本書，小到可以是一個字符，甚至是計算機二進制數(shù)中的一位。數(shù)據(jù)元素可由若干個數(shù)據(jù)項（也稱為域或字段）組成。例1.1 如表1.1所示的通訊錄表，行表示一個結(jié)點（數(shù)據(jù)元素），每個結(jié)點由姓名、區(qū)號、辦公電話和手機四個域（數(shù)據(jù)項）組成。表1.1 通訊錄表姓名區(qū)號辦公電話手機趙一0105364458713911001234錢二0208963415913809771333孫三0214597652813916586666李四0246342754113804076111 定義1.2 數(shù)據(jù)結(jié)構(gòu)由若干數(shù)據(jù)成分按照一定方式構(gòu)成的復(fù)合數(shù)據(jù)以及作用于其上的函數(shù)或運算。數(shù)據(jù)成分及其間的數(shù)據(jù)約束關(guān)系合稱為數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)從數(shù)學上可用適當?shù)臄?shù)學結(jié)構(gòu)以及其上的函數(shù)變換統(tǒng)一地定義。但迄今為止，關(guān)于數(shù)據(jù)結(jié)構(gòu)之定義在計算機科學技術(shù)界還未取得完全認同。有些學者認為數(shù)據(jù)結(jié)構(gòu)應(yīng)由數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)及其運算三部分組成。一個邏輯結(jié)構(gòu)可形式定義為一個二元組5：L = (N, R)，其中，N是結(jié)點的有限集合，R 是定義在集合N上的二元關(guān)系r的集合。設(shè) L=(N, R) 是一個邏輯結(jié)構(gòu). r1R是與線性結(jié)構(gòu)、樹結(jié)構(gòu)和二叉樹結(jié)構(gòu)對應(yīng)的一種關(guān)系，若a，bN，且 (a，b) r1，則稱 a是b的前驅(qū)結(jié)點，b是a的后繼結(jié)點，a和b是相鄰結(jié)點；若不存在aN使得 (a，b) r1，則稱 b 為始結(jié)點；若不存在 bN 使得(a，b) r1，則稱 a 為終結(jié)點. r2R是與圖結(jié)構(gòu)對應(yīng)的一種關(guān)系，若a，bN，且關(guān)系 (a，b) r2，則稱a和b是相鄰結(jié)點;對于有向圖結(jié)構(gòu)，若存在(a，b) r2，則稱a是b的前驅(qū)結(jié)點，b是a的后繼結(jié)點。數(shù)據(jù)的存儲結(jié)構(gòu)（或曰物理結(jié)構(gòu)）1.2.3 對數(shù)據(jù)結(jié)構(gòu)的操作插入、刪除、修改、排序、查找1.3 算 法定義1.49 一個算法就是給出求解特定類型問題之運算序列的一個有窮規(guī)則集合，一個算法應(yīng)具有5個重要特征：1) 有限性：一個算法在執(zhí)行有限步驟后必然終止；2) 確定性：對一個算法的每個步驟都必須給出精確的定義；對要執(zhí)行的動作都必須給出針對每種情況的嚴格、無歧義的描述；3) 輸入：一個算法有0個或多個輸入；4) 輸出：算法有1個或多個輸出；5) 可行性：算法中的所有操作都必須是充分基本的，因而原則上人們用紙和筆都可在有限時間內(nèi)精確地完成它們。1.3.2 算法的描述ADL語言例1.3 歐幾里得算法E9-10 算法E ( m , n . n )/* 給定兩個正整數(shù)m和n，算法E求它們的最大公因子（即能同時整除m和n的最大正整數(shù)），輸出結(jié)果在n中 */E1. 求余數(shù) r m - m/n n . / 有0 r N . 與 N 是最大整數(shù)矛盾。(3) 肯定原來的結(jié)論：因此，沒有最大的整數(shù)。證畢。2. 數(shù)學歸納法證明算法正確性的一般方法是數(shù)學歸納法。設(shè)THM是一個定理， n是THM中的正參數(shù). 數(shù)學歸納法表明，如果下面兩個條件為真，則對于參數(shù)n的任何值，THM都是正確的：(1) 基礎(chǔ)歸納：n = c 時，THM成立。(2) 歸納步驟：如果n = k - 1 時THM 成立，則n = k 時THM也成立。其中，c是一個較小的常量，n c . 通常，證明初始歸納很容易，而證明歸納步驟很難。以上是一般意義下的數(shù)學歸納法，而強歸納法在歸納步驟上有所變化： (2) 歸納步驟：如果對于所有的k ( c k 1 .證明：(1) 基礎(chǔ)歸納：n =1 時，T ( 1 ) = 1 - 1 = 0，結(jié)論成立。(2) 歸納步驟：假設(shè) T ( n - 1 ) = n - 2 成立 （歸納假設(shè)）要證明T ( n ) = n - 1 成立。由遞歸定義可知：n 1 時，有T ( n ) = T ( n - 1 ) + 1 由歸納假設(shè)：T ( n ) = T ( n - 1 ) + 1 = n - 2 + 1 = n - 1所以，由數(shù)學歸納法推出T ( n ) = n - 1成立。證畢。對于一個算法，證明其正確性是必要的。如果算法比較復(fù)雜，至少應(yīng)該給出其關(guān)鍵步驟的正確性證明。目前，算法或程序的正確性證明仍然是計算機科學領(lǐng)域中具有挑戰(zhàn)性的重要研究課題。1.5 算法分析基礎(chǔ)1.5.1 算法時間復(fù)雜性的分析方法分析算法的時間復(fù)雜性需要分析算法的基本運算次數(shù)?；具\算是指算法運行過程中起主要作用且花費最多時間的運算。例1.7 A是一個含有n個不同元素的實數(shù)數(shù)組，給出求A之最大和最小元素的算法。算法SM( A , n . max , min )/ 求實數(shù)數(shù)組An的最大和最小元素( max和min ) .SM1. 初始化maxminA1. SM2. 比較FOR i = 2 to n DO（IF Ai max THEN maxAi. IF Ai min THEN minAi）對算法SM 進行分析，容易看出算法SM 對大小為的 n 的數(shù)組 A 需要 2(n -1) 次元素比較，如果規(guī)定算法SM的基本運算是元素比較，那么算法SM 的基本運算的次數(shù)，即時間復(fù)雜性為2(n-1) .一般情況下，計算一個算法的基本運算次數(shù)是相當困難的，甚至是不可能的（因為一個算法的不同輸入往往產(chǎn)生不同的運算次數(shù)，而一個算法的所有不同輸入的數(shù)目可能十分龐大）。一種可行的方法是計算算法的平均運算次數(shù)。這樣的結(jié)果在實際中可能不是特別有用，因為某些輸入較之其它的輸入可能更經(jīng)常出現(xiàn)，所以對數(shù)目足夠的不同輸入的加權(quán)平均將會給出更有意義的結(jié)果。通常在最好、最壞和平均三種情況下，討論算法的時間復(fù)雜性。定義1.5 設(shè)一個領(lǐng)域問題的輸入規(guī)模為n，Dn是該領(lǐng)域問題的所有輸入的集合，任一輸入IDn，T(I)是（解決該領(lǐng)域問題的）算法在輸入I下所執(zhí)行的基本運算次數(shù)，P(I)是I出現(xiàn)的頻率，該算法的最好情況下的復(fù)雜性為：該算法的最壞情況下的復(fù)雜性為：該算法的平均情況下的復(fù)雜性，或期望復(fù)雜性為：例1.8 實數(shù)數(shù)組R由 n 個元素組成，給定一個實數(shù)K，試確定K是否是R的元素。算法F（R , n , K . i）/*給定一具有n 個元素的實數(shù)數(shù)組R，判斷實數(shù)K是否在R中出現(xiàn)，若是，1 i n；否則，i= n+1 .*/F1. 初始化i1.F2. 比較WHILE i n DO（ IF Ri = K THEN RETURN. i i+1） 算法F的運行結(jié)果：如果1 i n，則表示 K 是 R 的元素；反之，K 不是 R 的元素。規(guī)定算法F 的基本運算為 R 中元素與 K 的比較，假定 q 表示 K 是 R 中元素的概率，又假定 K 等于 R 的每個元素有相同的概率。令 Dn = I1, I2, In, In+1，其中 Ii (1 i n) 表示 K等于 Ri 的任一輸入，In+1 表示 K 不是 R 中元素的任一輸入。由上述說明我們有：當1 i n時， P(Ii) = q/n, T(Ii) = i, P(In+1) = 1-q, T(In+1) = n . 算法F的期望復(fù)雜性為：如果已知K在R中，即q = 1，則我們有由算法F我們很容易看出，該算法的最壞情況下的時間復(fù)雜性為算法F的最好情況下的時間復(fù)雜性為Flash動畫課件115網(wǎng)盤用戶名：2010datastructu密碼：forsuccess2010例1.9 算法SM的改進算法BS .算法BS( A, i, j . fmax, fmin )/ 在數(shù)組A的第i個元素到第j個元素之間尋找最大和最小元素，已知i j .BS1. 遞歸出口IF i = j THEN ( fmaxfminAi. RETURN. )IF i = j - 1 THEN( IF Ai Aj THEN (fmaxAj. fminAi.) ELSE (fmaxAi. fminAj.) RETURN.）BS2. 取中值 mid(i+j) / 2 .BS3. 遞歸調(diào)用BS(A, i, mid . gmax, gmin) .BS(A, mid+1, j . hmax, hmin) .BS4. 合并 fmaxmaxgmax, hmax . fminmingmin, hmin . 如果規(guī)定算法BS的基本運算亦為元素的比較，則容易看出算法BS對不同的輸入Ai到A j，只要元素個數(shù)相同都有相同的基本運算次數(shù)。設(shè)T(n)表示算法BS的基本運算次數(shù)，其中，n = j - i + 1，根據(jù)算法BS的遞歸過程，我們有如下的遞歸表達式：在上式中，當n是2的冪時（即存在正整數(shù)k，使得n = 2k）我們有由上面幾個例子可以看出，分析算法時，通常用數(shù)學方法將算法的復(fù)雜性表示為輸入規(guī)模n 的函數(shù)。1.5.2 復(fù)雜性函數(shù)的漸近表示在大多情況下，特別當輸入規(guī)模n較大時，難于確定一個算法的基本運算次數(shù)T，即得到T和n間的函數(shù)關(guān)系。所以，算法分析中通常采用大O、大W和大Q表示法來漸近表示算法的基本運算次數(shù)8, 11, 12, 13, 14。(1) 大O表示法1892年，Paul Bachmann在解析數(shù)論一書中引進了“大O”記號9，主要用于估計函數(shù)的增長速率。定義1.6 設(shè) f(n)和g(n)是正整數(shù)集到正實數(shù)集上的函數(shù)，稱f(n)是O(g(n) 當且僅當存在正常數(shù)C和n0，使得對任意的n n0，有f(n) Cg(n)，記為f(n) = O(g(n) .設(shè)f(n) = O(g(n)，f和g之間的關(guān)系可以描述為“f(n)的階至多為 g(n)”或“f至多與g增長得一樣快”。一個算法的時間復(fù)雜性為O(g(n)，表明它的基本運算次數(shù)至多是g(n)的某個常數(shù)倍. O(1)表示算法的時間復(fù)雜性為一常數(shù)。O(n)、O(n2)、O(n3)、O(nm)和O(2n)分別表示算法的時間復(fù)雜性為線性階的、平方階的、立方階的、多項式階的和指數(shù)階的，其中m 1，且m為常數(shù)。例1.10 若f (n) = 3 n -2，證明：f (n) = O(n) .證明：存在C = 3，n0 = 1，使得對任意的n n0，有3 n - 2 3 n，即 f(n) C n . 由大O的定義，f (n) = O(n) . 證畢。例1.11 若 f (n) = 3log n + loglog n，證明：f (n) = O (logn) .證明： 存在C = 4，n0 = 2，使得對任意的 n n0，有3 log n + loglog n 4 logn，即f(n) C logn . 由大O的定義，f (n) = O (logn) . 證畢。定理1.1 若A(n) = am nm + + a1 n + a0是關(guān)于n的m次多項式，則A(n) = O(nm) 根據(jù)算法的時間復(fù)雜性，人們常常把算法分成兩類。凡可用多項式來對其時間復(fù)雜性限界的算法，被稱為多項式階算法，而時間復(fù)雜性需用指數(shù)限界的算法被稱為指數(shù)階算法。當n很大時，可以證明有如下關(guān)系：1 log2log2 n log2 n n nlog2n n2 n3 2n從而有：O(1) O(log2log2 n) O(log2 n) O(n) O(nlog2n) O(n2) O(n3) O(2n)易證，當n很大時，指數(shù)函數(shù)的值遠大于對數(shù)函數(shù)、冪函數(shù)及它們的組合函數(shù)的值，也就是說，指數(shù)階算法的執(zhí)行時間遠遠大于多項式階算法的執(zhí)行時間。由定義1.6和式（1.1），可以證明T(n) = O(n) . 雖然算法SM和算法BS的時間復(fù)雜性均為線性階，但因 ，故就計算時間而言，算法BS優(yōu)于算法SM . 然而算法BS是遞歸算法，因此其實現(xiàn)需要額外的輔助空間。那么算法BS和算法SM誰更優(yōu)呢？為此，我們將在下一小節(jié)給出另一個評判標準。(2) 大W表示法和大Q表示法定義1.7 設(shè)f(n)和g(n)是正整數(shù)集到正實數(shù)集上的函數(shù)，稱f(n)是W(f(n)，當且僅當存在正常數(shù)C和n0，使得對任意的n n0，有f(n) Cg(n)，記為f(n) = W (g(n) . 設(shè)f(n) =W( g(n)，f和g之間的關(guān)系可以描述為“f(n) 的階至少為 g(n)”或“f的增長速率將不會低于g”.例1.12若f(n) = 3log n + loglog n，證明：f (n) = W (logn) .證明：存在C = 3，n0 = 2，使得對任意的 n n0，有3log n + loglogn 3log n，即 f(n) C log n . 由大W的定義，f (n) = W (logn) . 證畢。定義1.8設(shè) f(n)和g(n)是正整數(shù)集到正實數(shù)集上的函數(shù)，稱f(n)是Q(g(n)，當且僅當存在正常數(shù) C1, C2和n0，使得對于所有的n n0，有C1 g(n) f(n) C2 g(n) ，記為f(n) = Q (g(n) .設(shè)f(n) =Q( g(n)，f和g之間的關(guān)系可以描述為“g(n) 和 f(n) 的階數(shù)相同”或“f和g會以相同的速率增長”。例1.13 若f(n) = 3log n + loglog n，證明：f (n) = Q (logn) .證明：由例1.11和例1.12可得：3 log n 3 log n + loglog n 4 logn，即 3 log n f(n) 4 logn .由大Q的定義，f (n) = Q (logn) . 證畢。大O和大W分別提供了一種表達上界和下界的方法，而大Q則提供了一種同時表達上界和下界的方法12。對于函數(shù)f，可能有無窮多個上界，即無窮多個g使得 f(n) = O(g(n)；也可能有無窮多個下界，即無窮多個h使得 f(n) = W (h(n) . 通常，在分析算法的時間復(fù)雜性時，總是試圖找出算法的時間復(fù)雜性 f(n) 的最小上界和最大下界?？梢钥闯?，如果f(n) = O(g(n)且f(n) = W (g(n)，則f(n) = Q (g(n) . 一個算法的時間復(fù)雜性 f(n) = Q(g(n)，意味著該算法在最好和最壞情況下的時間復(fù)雜性在一個常數(shù)因子的范圍內(nèi)是相同的。不是對所有算法時間復(fù)雜性的估計都存在Q表達式。對于有些算法，盡管可以分別估計其上界和下界，但無法找到一個共同的f(n)作為其上下界的共同漸進表示，因此，這些算法的時間復(fù)雜性不存在大