第一章 緒 論.doc

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