數(shù)據(jù)結構DS01-概論

1、第 1 章 概 論 什么是數(shù)據(jù)結構 為什么要學習數(shù)據(jù)結構 算法和算法分析1.1 什么是數(shù)據(jù)結構1.1.1 數(shù)據(jù)和數(shù)據(jù)元素 數(shù)據(jù)（data）是信息的載體，是對客觀事物的符號表示，它能夠被計算機識別、存儲和加工處理?？梢哉f，數(shù)據(jù)是計算機程序加工的“原料”。目前，象圖像、聲音、視頻等都可以通過編碼而由計算機處理，因此它們也屬于數(shù)據(jù)的范疇。 數(shù)據(jù)元素（data element）是數(shù)據(jù)的基本單位，通常在計算機程序中作為一個整體進行考慮和處理。數(shù)據(jù)元素也稱為元素、結點或記錄。有時，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（也稱字段、域），數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。1.1.2 數(shù)據(jù)對象和數(shù)據(jù)類型 數(shù)據(jù)對象（da

2、ta object）是性質(zhì)相同的數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是集合N=0，1，2，3，；大寫字母字符數(shù)據(jù)對象是集合C=A，B，Z。要注意的是，計算機中的整數(shù)數(shù)據(jù)對象集合N1應該是上述集合N的一個子集，N1=0，1，2，maxint，其中maxint是依賴于所使用的計算機和語言的最大整數(shù)。 數(shù)據(jù)類型（data type）是計算機程序中的數(shù)據(jù)對象以及定義在這個數(shù)據(jù)對象集合上的一組操作的總稱。例如，C語言中的整數(shù)類型是區(qū)間-maxint，maxint上的整數(shù)，在這個集合上可以進行加、減、乘、整除、求余等操作。1.1.3 數(shù)據(jù)結構 數(shù)據(jù)結構（data structure）是指

3、數(shù)據(jù)對象以及該數(shù)據(jù)對象集合中的數(shù)據(jù)元素之間的相互關系（即數(shù)據(jù)元素的組織形式）。 數(shù)據(jù)元素的組織形式一般包含下列內(nèi)容： 數(shù)據(jù)元素之間的邏輯關系，也稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)的邏輯結構通常有下列4類（見圖1.1）： 集合：其中的數(shù)據(jù)元素之間除了“屬于同一個集合”的關系以外，別無其他關系。 線性結構：其中的數(shù)據(jù)元素之間存在一對一的關系。 樹型結構：其中的數(shù)據(jù)元素之間存在一對多的關系。 圖狀結構（或稱網(wǎng)狀結構）：其中的數(shù)據(jù)元素之間存在多對多的關系。 數(shù)據(jù)元素以及它們之間的相互關系在計算機存儲器內(nèi)的表示（又稱映象），稱為數(shù)據(jù)的存儲結構，也稱數(shù)據(jù)的物理結構。 數(shù)據(jù)元素之間的運算，亦即對數(shù)據(jù)元素施加的操作，有

4、時也直接稱為數(shù)據(jù)的運算或操作。例1.1 學生成績表（表1.1）是一個數(shù)據(jù)結構。表1.1 學生成績表學號姓名計算機導論高等數(shù)學普通物理平均成績04081101陳小潔8090858504081102馬麗麗7568787404081103林春英8278667504081104王澄娟9085938904081150張吉祥70887578 數(shù)據(jù)結構可以理解為：按某種邏輯關系組織起來的一批數(shù)據(jù)，應用計算機語言，按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合。 數(shù)據(jù)結構的內(nèi)容可歸納為三個部分：邏輯結構、存儲結構和運算集合。按某種邏輯關系組織起來的一批數(shù)據(jù)，按一定的映象方

5、式把它存放在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合， 這就是一個數(shù)據(jù)結構。 數(shù)據(jù)的存儲結構可采用以下4種基本的存儲方法得到： 順序存儲方法 鏈接存儲方法 索引存儲方法 散列存儲方法 上述4種基本的存儲方法，既可以單獨使用，也可以組合起來對數(shù)據(jù)結構進行存儲映象。同一種邏輯結構，若采用不同的存儲方法，則可以得到不同的存儲結構。 1.2 為什么要學習數(shù)據(jù)結構?1.2.1 學習數(shù)據(jù)結構的重要性 算法+數(shù)據(jù)結構=程序 1.2.2 數(shù)據(jù)結構的應用舉例 例1.2 電話號碼的查詢問題。 要求編寫一個電話號碼的查詢程序。對于任意給出的一個姓名，如果該人留有電話號碼，那么就找出他的電話號碼；否則就指

6、出該人沒有電話號碼。例1.3 n個城市之間鋪設光纜的問題。 假設需要在n個城市之間鋪設光纜，并且任意兩個城市之間都可以鋪設。大家知道，在n個城市之間只要鋪設n-1條光纜，即能將這n個城市連成網(wǎng)絡，只是由于地理位置的不同，所需經(jīng)費也不同，問題是采用什么樣的設計方案能使總投資最省。 這個問題的數(shù)學模型是如圖1.3（a）所示的“圖”，圖中“頂點”表示城市，頂點之間的連線及其上面的數(shù)值表示可以鋪設的光纜及所需經(jīng)費。 1.3 算法和算法分析1.3.1 什么是算法? 由于數(shù)據(jù)的運算是通過算法來描述的，因此，討論算法是數(shù)據(jù)結構課程的重要內(nèi)容之一。 算法（Algorithm）是對特定問題求解步驟的一種描述，它

7、是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列5個特性： 1、有窮性 2、確定性 3、可行性 4、輸入 5、輸出程序與算法的異同 在一個算法中，有些指令可能重復執(zhí)行，因而指令的執(zhí)行次數(shù)可能遠遠大于算法中的指令條數(shù)。由有窮性和可行性得知，對于任何輸入，一個算法在執(zhí)行了有限條指令后一定要終止，而且必須在有限時間內(nèi)完成。因此，一個程序如果對任何輸入都不會產(chǎn)生無限循環(huán)，則它就是一個算法。 盡管算法的含義與程序非常相似，但兩者還是有區(qū)別的。首先，一個程序不一定滿足有窮性，因此它不一定是算法。例如，系統(tǒng)程序中的操作系統(tǒng)，只要整個系統(tǒng)不遭受破壞，它就永遠不會停止，即使沒有作業(yè)要

8、處理，它仍處于等待循環(huán)中，以待一個新作業(yè)的進入。因此操作系統(tǒng)就不是一個算法。其次，程序中的指令必須是計算機可以執(zhí)行的，而算法中的指令卻無此限止。如果一個算法采用機器可執(zhí)行的語言來書寫，那么它就是一個程序。1.3.2 算法的描述和設計 一個算法可以采用自然語言、數(shù)學語言或者約定的符號語言（如偽碼、框圖等）來描述。為了方便讀者的閱讀和實踐，本書中的算法和數(shù)據(jù)結構均使用C語言來描述。 本書中采用的C語言遵照ANSI C標準，各章的程序都在Turbo C或Visual C+ 6.0中調(diào)試通過。對書中采用的一些預定義常量，簡要說明如下： /*函數(shù)結果的狀態(tài)代碼*/ #define TRUE 1 #def

9、ine FALSE 0 #define OK 1 #define ERROR 0 其他有關C語言的知識，請參考專門介紹C語言的書籍。如何評價算法的優(yōu)劣？一般來說，設計一個“好”的算法應該考慮以下幾點：1、正確性算法應當滿足具體問題的需求。2、健壯性當輸入數(shù)據(jù)非法時，算法也能適當?shù)刈鞣磻蜻M行處理，而不會產(chǎn)生莫明其妙的輸出結果或出錯信息，并中止程序的執(zhí)行。3、可讀性算法主要是為了方便人們的閱讀和交流，其次才是機器執(zhí)行。4、執(zhí)行算法所耗費的時間。5、執(zhí)行算法所耗費的存儲空間，其中主要考慮輔助存儲空間。1.3.3 算法分析 評價一個程序優(yōu)劣的重要依據(jù)是看這個程序的執(zhí)行需要占用多少機器資源。在各種機器

10、資源中，最重要的是時間資源和空間資源。因此，在進行程序分析時，大家最關心的就是程序所用算法在運行時所要花費的時間代價和程序中使用的數(shù)據(jù)結構所占有的空間代價。通常就稱之為時間復雜度（時間代價）和空間復雜度（空間代價）。1、算法的時間復雜度分析 一般，一個算法所耗費的時間將隨輸入數(shù)據(jù)量n的增大而增大。所以算法的時間復雜性是輸入數(shù)據(jù)量n的函數(shù)，這時就稱該算法的時間代價為T（n）。 評價算法的時間復雜性，就是設法找出T（n）和n的關系，即求出T（n）。 通常，一個算法是由控制結構（順序、選擇和循環(huán)）和“原操作”（指固有數(shù)據(jù)類型的操作，一條基本語句）構成的，而算法時間取決于兩者的綜合效果。假定算法每執(zhí)行

11、一條基本語句（對于所研究的問題來說是基本操作的“原操作”），以該原操作重復執(zhí)行的次數(shù)作為算法的時間度量。大部分情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。所謂語句的頻度，指的是該語句重復執(zhí)行的次數(shù)。 一個算法所耗費的時間是算法中所有語句執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句的執(zhí)行次數(shù)（頻度）與該語句執(zhí)行一次所需時間（略，因機器不同而不同）的乘積。 通常，只求出T（n）隨輸入數(shù)據(jù)量n而增長的趨勢(極限),稱T（n）的漸近時間復雜性。如果存在正的常數(shù)M和n0，當問題的規(guī)模nn0后，算法的時間量度T（n）Mf(n)，那么就稱該算法的時間復雜度為O(f(n)。人們

12、通常采用大O表示法來描述算法分析的結果。 f(n)是某個值非負的函數(shù)，這種說法意味著：當n充分大時，該算法的復雜度不大于f(n)的一個常數(shù)倍。 一般來說，在求時間復雜度時，主要考慮與程序規(guī)模有關的頻度最大的語句（即“問題的原操作”），例如循環(huán)語句的循環(huán)體、多重循環(huán)的最內(nèi)層循環(huán)等等。例1.4 有下列三個程序段： x=x+1; s=0; for(i=1; i=n; i+) x=x+1; s=s+x; for(j=1; j=n; j+) for(k=1; k=n; k+) x=x+1; s=s+x; 它們含基本操作“x加1”的語句的頻度分別為1、n和n2，因此，對于程序段來說，其時間復雜度為O(1)

13、，程序段的時間復雜度為O(n)，程序段的時間復雜度為O(n2)。例1.5 對n個記錄進行升序排序的問題，采用最簡單的選擇排序方法。 每次處理時，先從n個未排序的記錄中選出一個最小記錄，則第一次要經(jīng)過n-1次比較，才能選出最小記錄；第二次再從剩下的n-1個記錄中經(jīng)過n-2次比較，選出次小記錄；如此反復，直到只剩兩個記錄時，經(jīng)過1次比較就可以確定它們的大小。整個排序過程的基本操作（即“原操作”）是“比較兩個記錄的大小”，含“比較”的語句的頻度是： （n-1）+（n-2）+ +1= n （n-1）/2因此，其時間復雜度為O(n2)。 在同一個算法處理兩個規(guī)模相同的問題，所花費的時間和空間代價也不一定

14、相同。要全面分析一個算法，應該考慮它在最壞情況下的代價（即對同樣規(guī)模的問題所花費的最大代價）、最好情況下的代價和平均情況下的代價等。然而，要全面準確地分析每個算法是相當困難的，因此，本書中在分析算法時將主要考慮它們在最壞情況下的代價，個別地方也涉及到其他情況。 通常有如下的函數(shù)關系排序： c log2 n n n log2 n n2 n3 2n 其中，c是與n無關的任意常數(shù)。上述函數(shù)排序與數(shù)學中對無窮大的分級完全一致，因為考慮的也是n值變化過程中的趨勢。 按數(shù)量級將常見的時間復雜度遞增排序，依次為：常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(

15、n2)、立方階O(n3)、指數(shù)階(2n)等。參見圖1.4。 例1.6 要交換變量x和y中的內(nèi)容，其程序段為 temp=x; x=y; y=temp; 由于以上三條語句的頻度均為1，說明該程序段的執(zhí)行時間是一個與問題規(guī)模n無關的常數(shù)，因此，算法的時間復雜度為O(1)。 例1.7 有程序段如下： x=1; for(i=1; i=n; i+) for(j=1; j=n; j+) for(k=1; k=n; k+) x+; 在此程序段中，因為含基本操作“x加1”的語句“x+;”的頻度是n3，所以該程序段的時間復雜度為O(n3)。2、算法的空間復雜度分析 與算法的時間復雜度類似，可以定義算法的空間復雜度如下：如果存在正的常數(shù)M和n0，當問題的規(guī)模nn0后，算法的空間量度S（n）Mf(n)，那么就稱該算法的空間復雜度為O（f(n)）。 一個上機執(zhí)行的程序，除了需要存儲空間來寄存本身所用的指令、常數(shù)、變量和輸入數(shù)據(jù)以外，也需要一些對數(shù)據(jù)進行處理的工作單元和存儲一些為實現(xiàn)計算機所需信息的輔助空間。如果輸入數(shù)據(jù)所占空間只取決于問題本身，而與算法無關，那么只需要分析除了輸入和程序之外的額外空間，否則應該同時考慮輸入本身所需要的空