1、數據結構基礎 教材：數據結構（C+描述）（金遠平編著，清華大學出版社） 1JYP第1章 基本概念和方法 本章論述學習和研究數據結構所必須的并且將反復出現的基本概念和方法。 2JYP1.1 數據結構與軟件系統(tǒng) 設計解決實際問題的計算機軟件系統(tǒng)，首先需要建立被處理對象的數據模型。 數據和世上萬物一樣，都是具有結構的。人們很自然地用數據結構表示應用領域的被處理對象。例如，樹和圖。 數據結構由一個數據對象以及該對象中的所有數據元素之間的關系組成。數據元素本身可以是數據結構，因此，可以構造非常復雜的數據結構。 3 為了模擬實際問題的求解過程和現實對象的行為，還必須提供對數據結構的相應操作。數據結構的實現

2、是以下一層數據結構表示上一層數據結構，直至以程序設計語言提供的基本數據類型表示的過程。 評價數據結構表示能力的標準主要是它能否方便且有效地實現需要的操作，而實現操作的算法設計及其效率高低也依賴于數據結構表示。 數據結構的定義、表示及其操作的實現相互關聯，都是數據結構研究的重要內容。 4計算機軟件系統(tǒng)可看成是通過不同層次的數據結構及其操作實現的。例如： 5中間層數據結構起著核心作用，稱之為建模層。對數據結構的研究產生了一批通用性強、具有很高實用價值的中間層數據結構，如數組、字符串、集合、線性表、棧、隊列、鏈表、樹、圖、符號表等。 系統(tǒng)地學習進而掌握數據結構的知識和方法，對于提高設計與開發(fā)軟件系統(tǒng)

3、尤其是復雜軟件系統(tǒng)的能力，無疑是十分重要的。 61.2 數據抽象與封裝 抽象和封裝的概念在日常生活中是普遍存在的，例如，人們常用的手機。通過數據封裝，將一個數據對象的內部結構和實現細節(jié)對外屏蔽。通過數據抽象，將一個數據對象的規(guī)格說明與其實現分離，對外提供簡潔、清晰的接口。數據結構多層表示的過程反過來也就是從基礎數據結構到應用領域數據結構的不斷抽象與封裝的過程。7用抽象數據類型（ADT）描述數據抽象與封裝是一種自然、有效的方法。 數據類型由一個數據對象的集合和一組作用于這些數據對象的操作組成。例如，C+的基本數據類型char、int、float和double等。 抽象數據類型是一個數據類型，該數

4、據類型的組織遵循將數據對象及對這些數據對象的操作的規(guī)格說明與這些數據對象的表示、操作的實現相分離的原則。 8當強調一個數據對象的結構時，使用數據結構的概念。與數據結構的概念對比，抽象數據類型包含了一個數據結構的集合，還包含了對數據結構的操作。抽象數據類型成為描述數據結構及其操作的有效方式。 定義ADT的語言本質上不依賴具體的程序設計語言，這里采用C+描述。 9例1.1 抽象數據類型“圓”的定義為：class Circle / 對象: 幾何圓public: Circle(float r); / 構造函數，創(chuàng)建一個半徑為r的對象實例 float Circumference( ); / 返回該實例的

5、周長 float Area( ); / 返回該實例的面積; 該抽象數據類型的名稱為Circle，數據對象定義為幾何圓，操作包括構造函數、計算周長和面積等。注意：這些定義不依賴于數據對象的具體表示，也沒有給出操作實現的過程。10數據抽象和封裝機制的意義：（1）簡化軟件開發(fā)： 假設一個問題經分析將使用A、B、C三個數據類型和協(xié)調代碼求解。 （a）四位程序員，可由其中三位程序員各開發(fā)一個數據類型，另一位程序員實現協(xié)調代碼。 （b）一位程序員，數據抽象也可減少其在某一具體時間需要考慮的范圍。 11（2）易于測試和排除錯誤： 如下圖所示，數據抽象明顯提高了測試和排除錯誤的效率。 12（3）有利于重用：

6、數據抽象和封裝機制使開發(fā)人員可以將數據結構及其操作實現為可重用的軟件組件。這些組件具有清晰的界面定義，更容易從一個軟件系統(tǒng)中提取出來，應用于另一個軟件系統(tǒng)。（4）便于改變數據類型的表示： 由于數據封裝，外界不能直接訪問數據類型的內部表示。因此，只要操作接口不變，數據類型內部表示和實現的改變不會影響使用該數據類型的其他程序。 131.3 算法定義 數據結構的操作實際上是以算法的形式實現的。定義：算法是一個有限的指令集合，執(zhí)行這些指令可以完成某一特定任務。一個算法還應當滿足以下特性： 輸入 零個或多個由外界提供的輸入量。 輸出 至少產生一個輸出量。 確定性 每一指令都有確切的語義，無歧義。 有限性

7、 在執(zhí)行有限步驟后結束。 有效性 每一條指令都應能經過有限層的表示轉化為計算平臺的基本指令，即算法的指令必須是可行的。14程序和算法不同，程序可以不滿足有限性。例 如，一個軟件的總控程序在未接受新的任務之前一直處于“等待”循環(huán)中。實現數據結構操作的程序總是可結束的，因此，后面將不再嚴格區(qū)分算法和程序這兩個術語。必須保證指令的有效性，例如，指令“if （哥德巴赫猜想是真）then x = y；”是無效的。作業(yè)：P253 151.4 遞歸算法 直接遞歸：函數在執(zhí)行過程中調用本身。間接遞歸：函數在執(zhí)行過程中調用其它函數再經過這些函數調用本身。表達力：函數定義賦值if-elsewhile 函數定義賦值

8、if-else遞歸 16當問題本身是遞歸定義的，其解法適合用遞歸描述。 例1.3 階乘函數的定義是 1 當n=1n! = n(n-1)！ 當n1 用遞歸方法計算階乘函數簡明扼要，易于理解，如下所示：long Factorial ( long n ) if ( n = = 1 ) return 1; / 終止條件 else return n*Factorial ( n-1); / 遞歸步驟 17用參數n= 5調用Factorial的過程如下：Factorial (5) = (5* Factorial (4) = (5* (4* Factorial (3) = (5* (4* (3* Factor

9、ial (2) = (5* (4* (3* (2* Factorial (1) = (5* (4* (3* (2* 1) = (5* (4* (3* 2) = (5* (4* 6) = (5* 24) = 12018遞歸算法有四個特性：（1）必須有可最終達到的終止條件，否則程序將陷入無窮循環(huán)；（2）子問題在規(guī)模上比原問題小，或更接近終止條件；（3）子問題可通過再次遞歸調用求解或因滿足終止條件而直接求解；（4）子問題的解應能組合為整個問題的解。19例1.4 全排列生成器：給定一個具有n1個元素的集合，打印該集合的全排列。 分析四個元素(a，b，c，d)的情況，結果可以如下構造： （1） a后接(

10、b，c，d)的全排列 （2） b后接(a，c，d)的全排列 （3） c后接(a，b，d)的全排列 （4） d后接(a，b，c)的全排列 這表明，如果能生成n 1個元素的全排列，就能生成n個元素的全排列。20 對于只有1個元素的集合，可以直接生成其全排列。于是，全排列生成問題的遞歸步驟和終止條件可以確定。 求解函數perm：void perm (char *a, const int k，const int n) / n 是數組a的元素個數，生成ak,an-1的全排列 int i; if (k = = n-1) / 終止條件，輸出排列 for ( i=0; in; i+) cout ai “ ”;

11、 / 輸出包括前 / 綴，以構成整個問題的解 cout endl;21 else / ak,an-1 的排列大于1，遞歸生成 for ( i = k; i n; i+) char temp = ak; ak = ai; ai = temp; / 交換ak / 和 ai perm(a,k+1,n); / 生成 ak+1,an-1的全排列 temp = ak; ak = ai; ai = temp; / 再次交換 ak 和 / ai , 恢復原順序 / else結束 / perm結束 通過調用perm(a, 0, n)，可以生成n個元素的全排列。 22 用n = 3 和 a0.2 = (a, b,

12、 c)調用perm的示意如下：23當算法操作的數據結構是遞歸定義的時候也適合使用遞歸。后面將有許多此類的重要例子。作業(yè)：P255，6241.5 性能分析 除了正確性、可用性、可讀性和容錯性以外，算法的性能是評價算法優(yōu)劣的重要指標。空間復雜性：算法開始運行直至結束過程中所需要的最大存儲資源開銷的一種度量。時間復雜性：算法開始運行直至結束所需要的執(zhí)行時間的一種度量。性能評價分為事前估計和事后測量。性能分析就是指對算法的空間復雜性和時間復雜性進行事前估計。251.5.1 空間復雜性 程序P的空間需求 S(P) = c + SP(實例特性) 其中，c是常數，SP(實例特性) 是實例特性的函數。分析的重

13、點是SP(實例特性)。對于一個給定問題，首先要確定其實例特性，才可能分析求解算法的空間要求。確定實例特性與具體問題密切相關。26例如:1 float rsum (float *a, const int n) 2 if (n = 0 ) return 0;/ 當n = 1時返回a03 else return rsum( a, n1) + an1;4 rsum是一個遞歸求和算法，其實例特性是n。每次遞歸調用需在棧頂保存n的值、a的值、返回值和返回地址，共需4個存儲單元。 由于算法的遞歸深度是n+1，故所需棧空間是4(n+1)，即Srsum(n) = 4(n+1)。271.5.2 時間復雜性 算法P

14、的運行時間 T(P) = c + TP(實例特性)時間復雜性分析的目的在于揭示算法的運行時間隨著其實例特性變化的規(guī)律。將一組與實例特性無關的操作抽象為一個程序步，從而有效地簡化性能分析的過程。程序步：算法中的一個在語法和語義上有意義的指令序列，而且該序列執(zhí)行時間與算法的實例特性無關。28各類C+語句的程序步數詳見教科書。可以通過列出各個語句的程序步數確定整個程序的程序步數。例1.5 程序sum： 1 float sum (float *a, const int n) 2 float s = 0; 3 for (int i = 0; i 0時Trsum(n) = 2+ Trsum(n-1)。31

15、通過反復代入可得： Trsum(n) = 2+ Trsum(n-1) = 2+2+Trsum(n-2) = 2*2+ Trsum(n-2) = 2+2+2+ Trsum(n-3) = 2*3+ Trsum(n-3) = 2n+ Trsum(0) = 2n+2 所以rsum的程序步數為2n+2。32許多程序的實例特性并不僅僅依賴于實例規(guī)模n，還可能與實例內容密切相關。 例如，二分查找的程序步數，不僅與元素個數n，而且與集合內容有關。 有時需要按最好、最壞和平均三種情況分析算法的時間復雜性。331.5.3 O表示法 程序步本身就不是一個準確的概念，而是一個抽象的概念。 再作一次抽象，從由多種因素構

16、成的時間復雜性中抽取出其主要因素，將常數抽象為1，有利于抓住主要矛盾，簡化復雜性分析。假設函數f和g是非負函數。 定義：f(n) = O(g(n) 當且僅當存在正值常數c和n0，使得對所有n n0，f(n) c*g(n)。 34 例1.8 5n + 4 = O(n) 100n + 6 = O(n) 10 n2 + 4n + 2 = O(n2) 6*2n + n2 = O(2n) 3n + 2 O(1) O(1)表示常數， O(log n) 表示對數，O(n)表示線性，O(n2)表示平方，O(n3)表示立方， O(2n)表示指數。35f(n) = O(g(n)只表示對所有n n0，g(n)是f(

17、n)的上界。因此，n = O(n2) = O(n3) = O(2n)。為了使f(n) = O(g(n)提供盡可能多的信息，g(n)應盡可能小。有時，由于現有分析能力的限制，人們還不能得出一個算法計算時間的準確數量級。例如對實際計算時間為O(n log n)的算法，目前的分析結果只能表明其計算時間是O(n2)，這時說該算法的計算時間是O(n2)也沒錯，待到以后認識深入了，可以改說成O(n log n)。36 定理1.1 設f(n)= amnm + am-1nm-1 + + a1n + a0，則 f(n) = O(nm)。37 例1.11 n位二進制數加1的時間復雜性。設數組a模擬一個n位二進制數

18、，下列算法將a表示的二進制數加1。emun Binary 0, 1 ;void BinaryAddOne ( Binary *a, const int n ) int i = n-1; while (ai = = 1 & i = 0) /從右向左掃描，遇到第一 / 個0位停止，并將所經過的全部1置0 ai = 0; i-; if ( i = 0 ) ai = 1;38下面分別分析其最好、最壞和平均時間復雜性：（1）最好情況：當右邊第一位為0時，掃描停止，算法時間復雜性為O(1)。（2）最壞情況：當n個二進制位全為1時，需掃描n位，算法時間復雜性為O(n)。39（3）平均情況。n位二進制數共有2

19、n種取值。以n=3 為例，有下列取值： 40一般，從右到左有連續(xù)m個1需m + 1次操作，這種取值共2n-(m+1)個（m 100），只有復雜性較小（如，n，nlog2n，n2，n3）的算法是實用的。即使計算機的速度再提高1000倍，表中時間也只不過縮小1000倍。在這種情況下，當n=100時，n10個程序步的運行時間是3.17年，2n個程序步的運行時間是41010年。43 可見，如果一個算法的時間復雜性過高，當n大于一定值時，再快的計算機也無法在實際可行的時間內完成其運行。441.6 性能測量 性能測量：在一定的數據范圍內準確獲取程序運行所需要的空間和時間，屬于事后測量。測量的結果依賴于編譯

20、器及其設置，還依賴于程序運行的計算機。下面重點研究性能（程序的計算時間）測量的方法。 假設函數time ( &hsec )將當前時間返回到變量hsec中，精度為1毫秒。下面以測量順序查找算法seqsearch在最壞情況下的性能為例，說明性能測量的方法。45int seqsearch (int *a, const int n, const int x ) int i = n; a0 = x; while (ai != x) i-; return i; 順序查找算法的最壞時間復雜性是O(n)。為了反映被忽略的常數因子的影響，對于較小的n應選較多的值測量，對于較大的n值則可稀疏測量。 限于時鐘精度，

21、對于太短的事件必須重復m次，然后用測得的總時間除以m求出事件的時間。46順序查找算法的測量程序如下： void TimeSearch (const long m) int a1001, n20; for ( int j = 1; j=1000; j+ ) aj = j; / 初始化a for ( j=0; j10; j+ ) / n的取值 nj = 10*j; nj+10 = 100*( j+1 ); cout “ n 總時間 運行時間” endl; for ( j=0; j20; j+ ) long start, stop; time (&start);/ 開始計時 for ( long b

22、=1; b = m; b+ )int k = seqsearch(a, nj, 0 ); / 失敗查找47 time (&stop); / 停止計時 long totalTime = stop - start; float runTime = (float) (totalTime) / (float)m; cout nj totalTime runTimeendl; 執(zhí)行TimeSearch(300000)的輸出如下表所示。從該表可以看出，t基本上隨n線性增長。利用n = 0和60這兩點的數據，可得線性函數 t = 0.000096n + 0.0008。由此可推算，當n = 1000，t =

23、0.00968。這與實際測量的數據完全吻合。 4849規(guī)劃性能測量實驗時應注意以下問題： 時鐘精度、期望的測量結果精度以及與此相關的重復次數。 根據是測量最壞性能還是平均性能，生成合適的實驗數據。 實驗目的：是為了比較還是為了預測實際運行時間？ 當實驗目的是預測實際運行時間時，人們需要通過測量數據建立t與n之間的函數關系。50 一般需用計算機生成導致一個算法最壞性能的數據集。 但在有的情況下計算機生成也非常困難。這時可根據實例特性的值隨機生成足夠量的實驗數據，取這些數據導致的最長運行時間作為最壞性能。 生成平均性能數據更為困難，一般也采用隨機生成的方法。實驗作業(yè)：P2515511.7 C+中的

24、模板 C+的模板（template）有效地提高了函數和類的可重用性。 模板（又稱為參數化類型）是一種能被實例化為任何數據類型的變量，這些類型既包括C+基本類型又包括用戶定義的類型。模板函數:template int seqsearch (KeyType *a, const int n, KeyType x ) int i=n; a0=x; while (ai != x) i-; return i; 52 通過調用seqsearch，可以很容易地在字符數組或浮點數數組中查找元素: char carray200; float farray300; char x = r; float y = 306.523; / 設此時以上數組已完成初始化 seqsearch(carray, 200, x); seqsearch(farray, 300, y); 函數seqsearch的KeyType在調用時被實例化為相應的實參類型，例如，調用seqsearch(far