數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)課件

1、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 教材：數(shù)據(jù)結(jié)構(gòu)（C+描述）（金遠(yuǎn)平編著，清華大學(xué)出版社，2005）講課教師： 金遠(yuǎn)平，軟件學(xué)院 1JYP 考試： 期末考試采用開卷方式，占總評成績的70%。 平時(shí)作業(yè)和實(shí)驗(yàn)占總評成績30%。 考試注重：概念、方法、技巧、思想、創(chuàng)新、關(guān)鍵步驟、程序設(shè)計(jì)風(fēng)格2JYP 參考文獻(xiàn)：1 E. Horowitz, S. Sahni, D. Mehta, Fundamentals of Data Structure In C+, Computer Science Press,19952 W. Ford and W. Topp, Data Structures with C+,清華大學(xué)出版社（影

2、印版）, 19973 T. A. Standish, Data Structures, Algorithms & Software Principles in C, Addison-Wesley Publishing Company, 19943JYP第1章 基本概念和方法 本章論述學(xué)習(xí)和研究數(shù)據(jù)結(jié)構(gòu)所必須的并且將反復(fù)出現(xiàn)的基本概念和方法。 4JYP1.1 數(shù)據(jù)結(jié)構(gòu)與軟件系統(tǒng) 設(shè)計(jì)解決實(shí)際問題的計(jì)算機(jī)軟件系統(tǒng)，首先需要建立被處理對象的數(shù)據(jù)模型。 數(shù)據(jù)和世上萬物一樣，都是具有結(jié)構(gòu)的。人們很自然地用數(shù)據(jù)結(jié)構(gòu)表示應(yīng)用領(lǐng)域的被處理對象。例如，樹和圖。 數(shù)據(jù)結(jié)構(gòu)由一個(gè)數(shù)據(jù)對象以及該對象中的所有數(shù)據(jù)元素之

3、間的關(guān)系組成。數(shù)據(jù)元素本身可以是數(shù)據(jù)結(jié)構(gòu)，因此，可以構(gòu)造非常復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 5JYP 為了模擬實(shí)際問題的求解過程和現(xiàn)實(shí)對象的行為，還必須提供對數(shù)據(jù)結(jié)構(gòu)的相應(yīng)操作。數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)是以下一層數(shù)據(jù)結(jié)構(gòu)表示上一層數(shù)據(jù)結(jié)構(gòu)，直至以程序設(shè)計(jì)語言提供的基本數(shù)據(jù)類型表示的過程。 評價(jià)數(shù)據(jù)結(jié)構(gòu)表示能力的標(biāo)準(zhǔn)主要是它能否方便且有效地實(shí)現(xiàn)需要的操作，而實(shí)現(xiàn)操作的算法設(shè)計(jì)及其效率高低也依賴于數(shù)據(jù)結(jié)構(gòu)表示。 數(shù)據(jù)結(jié)構(gòu)的定義、表示及其操作的實(shí)現(xiàn)相互關(guān)聯(lián)，都是數(shù)據(jù)結(jié)構(gòu)研究的重要內(nèi)容。 6JYP計(jì)算機(jī)軟件系統(tǒng)可看成是通過不同層次的數(shù)據(jù)結(jié)構(gòu)及其操作實(shí)現(xiàn)的。例如： 7JYP中間層數(shù)據(jù)結(jié)構(gòu)起著核心作用，稱之為建模層。對數(shù)據(jù)結(jié)構(gòu)的

4、研究產(chǎn)生了一批通用性強(qiáng)、具有很高實(shí)用價(jià)值的中間層數(shù)據(jù)結(jié)構(gòu)，如數(shù)組、字符串、集合、線性表、棧、隊(duì)列、鏈表、樹、圖、符號(hào)表等。 系統(tǒng)地學(xué)習(xí)進(jìn)而掌握數(shù)據(jù)結(jié)構(gòu)的知識(shí)和方法，對于提高設(shè)計(jì)與開發(fā)軟件系統(tǒng)尤其是復(fù)雜軟件系統(tǒng)的能力，無疑是十分重要的。 8JYP1.2 數(shù)據(jù)抽象與封裝 抽象和封裝的概念在日常生活中是普遍存在的，例如，人們常用的手機(jī)。通過數(shù)據(jù)封裝，將一個(gè)數(shù)據(jù)對象的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)對外屏蔽。通過數(shù)據(jù)抽象，將一個(gè)數(shù)據(jù)對象的規(guī)格說明與其實(shí)現(xiàn)分離，對外提供簡潔、清晰的接口。數(shù)據(jù)結(jié)構(gòu)多層表示的過程反過來也就是從基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)到應(yīng)用領(lǐng)域數(shù)據(jù)結(jié)構(gòu)的不斷抽象與封裝的過程。9JYP用抽象數(shù)據(jù)類型（ADT）描述數(shù)據(jù)抽

5、象與封裝是一種自然、有效的方法。 數(shù)據(jù)類型由一個(gè)數(shù)據(jù)對象的集合和一組作用于這些數(shù)據(jù)對象的操作組成。例如，C+的基本數(shù)據(jù)類型char、int、float和double等。 抽象數(shù)據(jù)類型是一個(gè)數(shù)據(jù)類型，該數(shù)據(jù)類型的組織遵循將數(shù)據(jù)對象及對這些數(shù)據(jù)對象的操作的規(guī)格說明與這些數(shù)據(jù)對象的表示、操作的實(shí)現(xiàn)相分離的原則。 10JYP當(dāng)強(qiáng)調(diào)一個(gè)數(shù)據(jù)對象的結(jié)構(gòu)時(shí)，使用數(shù)據(jù)結(jié)構(gòu)的概念。與數(shù)據(jù)結(jié)構(gòu)的概念對比，抽象數(shù)據(jù)類型包含了一個(gè)數(shù)據(jù)結(jié)構(gòu)的集合，還包含了對數(shù)據(jù)結(jié)構(gòu)的操作。抽象數(shù)據(jù)類型成為描述數(shù)據(jù)結(jié)構(gòu)及其操作的有效方式。 定義ADT的語言本質(zhì)上不依賴具體的程序設(shè)計(jì)語言，這里采用C+描述。 11JYP例1.1 抽象數(shù)據(jù)類

6、型“圓”的定義為：class Circle / 對象: 幾何圓public: Circle(float r); / 構(gòu)造函數(shù)，創(chuàng)建一個(gè)半徑為r的對象實(shí)例 float Circumference( ); / 返回該實(shí)例的周長 float Area( ); / 返回該實(shí)例的面積; 該抽象數(shù)據(jù)類型的名稱為Circle，數(shù)據(jù)對象定義為幾何圓，操作包括構(gòu)造函數(shù)、計(jì)算周長和面積等。注意：這些定義不依賴于數(shù)據(jù)對象的具體表示，也沒有給出操作實(shí)現(xiàn)的過程。12JYP數(shù)據(jù)抽象和封裝機(jī)制的意義：（1）簡化軟件開發(fā)： 假設(shè)一個(gè)問題經(jīng)分析將使用A、B、C三個(gè)數(shù)據(jù)類型和協(xié)調(diào)代碼求解。 （a）四位程序員，可由其中三位程序員各

7、開發(fā)一個(gè)數(shù)據(jù)類型，另一位程序員實(shí)現(xiàn)協(xié)調(diào)代碼。 （b）一位程序員，數(shù)據(jù)抽象也可減少其在某一具體時(shí)間需要考慮的范圍。 13JYP（2）易于測試和排除錯(cuò)誤： 如下圖所示，數(shù)據(jù)抽象明顯提高了測試和排除錯(cuò)誤的效率。 14JYP（3）有利于重用： 數(shù)據(jù)抽象和封裝機(jī)制使開發(fā)人員可以將數(shù)據(jù)結(jié)構(gòu)及其操作實(shí)現(xiàn)為可重用的軟件組件。這些組件具有清晰的界面定義，更容易從一個(gè)軟件系統(tǒng)中提取出來，應(yīng)用于另一個(gè)軟件系統(tǒng)。（4）便于改變數(shù)據(jù)類型的表示： 由于數(shù)據(jù)封裝，外界不能直接訪問數(shù)據(jù)類型的內(nèi)部表示。因此，只要操作接口不變，數(shù)據(jù)類型內(nèi)部表示和實(shí)現(xiàn)的改變不會(huì)影響使用該數(shù)據(jù)類型的其他程序。 15JYP1.3 算法定義 數(shù)據(jù)結(jié)構(gòu)的

8、操作實(shí)際上是以算法的形式實(shí)現(xiàn)的。定義：算法是一個(gè)有限的指令集合，執(zhí)行這些指令可以完成某一特定任務(wù)。一個(gè)算法還應(yīng)當(dāng)滿足以下特性： 輸入 零個(gè)或多個(gè)由外界提供的輸入量。 輸出 至少產(chǎn)生一個(gè)輸出量。 確定性 每一指令都有確切的語義，無歧義。 有限性 在執(zhí)行有限步驟后結(jié)束。 有效性 每一條指令都應(yīng)能經(jīng)過有限層的表示轉(zhuǎn)化為計(jì)算平臺(tái)的基本指令，即算法的指令必須是可行的。16JYP程序和算法不同，程序可以不滿足有限性。例 如，一個(gè)軟件的總控程序在未接受新的任務(wù)之前一直處于“等待”循環(huán)中。實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)操作的程序總是可結(jié)束的，因此，后面將不再嚴(yán)格區(qū)分算法和程序這兩個(gè)術(shù)語。必須保證指令的有效性，例如，指令“if

9、（哥德巴赫猜想是真）then x = y；”是無效的。作業(yè)：P253 17JYP1.4 遞歸算法 直接遞歸：函數(shù)在執(zhí)行過程中調(diào)用本身。間接遞歸：函數(shù)在執(zhí)行過程中調(diào)用其它函數(shù)再經(jīng)過這些函數(shù)調(diào)用本身。表達(dá)力：函數(shù)定義賦值if-elsewhile 函數(shù)定義賦值if-else遞歸 18JYP當(dāng)問題本身是遞歸定義的，其解法適合用遞歸描述。 例1.3 階乘函數(shù)的定義是 1 當(dāng)n=1n! = n(n-1)！ 當(dāng)n1 用遞歸方法計(jì)算階乘函數(shù)簡明扼要，易于理解，如下所示：long Factorial ( long n ) if ( n = = 1 ) return 1; / 終止條件 else return n

10、*Factorial ( n-1); / 遞歸步驟 19JYP用參數(shù)n= 5調(diào)用Factorial的過程如下：Factorial (5) = (5* Factorial (4) = (5* (4* Factorial (3) = (5* (4* (3* Factorial (2) = (5* (4* (3* (2* Factorial (1) = (5* (4* (3* (2* 1) = (5* (4* (3* 2) = (5* (4* 6) = (5* 24) = 12020JYP遞歸算法有四個(gè)特性：（1）必須有可最終達(dá)到的終止條件，否則程序?qū)⑾萑霟o窮循環(huán)；（2）子問題在規(guī)模上比原問題小，或

11、更接近終止條件；（3）子問題可通過再次遞歸調(diào)用求解或因滿足終止條件而直接求解；（4）子問題的解應(yīng)能組合為整個(gè)問題的解。21JYP例1.4 全排列生成器：給定一個(gè)具有n1個(gè)元素的集合，打印該集合的全排列。 分析四個(gè)元素(a，b，c，d)的情況，結(jié)果可以如下構(gòu)造： （1） a后接(b，c，d)的全排列 （2） b后接(a，c，d)的全排列 （3） c后接(a，b，d)的全排列 （4） d后接(a，b，c)的全排列 這表明，如果能生成n 1個(gè)元素的全排列，就能生成n個(gè)元素的全排列。22JYP 對于只有1個(gè)元素的集合，可以直接生成其全排列。于是，全排列生成問題的遞歸步驟和終止條件可以確定。 求解函數(shù)p

12、erm：void perm (char *a, const int k，const int n) / n 是數(shù)組a的元素個(gè)數(shù)，生成ak,an-1的全排列 int i; if (k = = n-1) / 終止條件，輸出排列 for ( i=0; in; i+) cout ai “ ”; / 輸出包括前 / 綴，以構(gòu)成整個(gè)問題的解 cout endl;23JYP 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); / 生成

13、ak+1,an-1的全排列 temp = ak; ak = ai; ai = temp; / 再次交換 ak 和 / ai , 恢復(fù)原順序 / else結(jié)束 / perm結(jié)束 通過調(diào)用perm(a, 0, n)，可以生成n個(gè)元素的全排列。 24JYP 用n = 3 和 a0.2 = (a, b, c)調(diào)用perm的示意如下：25JYP當(dāng)算法操作的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的時(shí)候也適合使用遞歸。后面將有許多此類的重要例子。作業(yè)：P255，626JYP1.5 性能分析 除了正確性、可用性、可讀性和容錯(cuò)性以外，算法的性能是評價(jià)算法優(yōu)劣的重要指標(biāo)?？臻g復(fù)雜性：算法開始運(yùn)行直至結(jié)束過程中所需要的最大存儲(chǔ)資源開銷

14、的一種度量。時(shí)間復(fù)雜性：算法開始運(yùn)行直至結(jié)束所需要的執(zhí)行時(shí)間的一種度量。性能評價(jià)分為事前估計(jì)和事后測量。性能分析就是指對算法的空間復(fù)雜性和時(shí)間復(fù)雜性進(jìn)行事前估計(jì)。27JYP1.5.1 空間復(fù)雜性 程序P的空間需求 S(P) = c + SP(實(shí)例特性) 其中，c是常數(shù)，SP(實(shí)例特性) 是實(shí)例特性的函數(shù)。分析的重點(diǎn)是SP(實(shí)例特性)。對于一個(gè)給定問題，首先要確定其實(shí)例特性，才可能分析求解算法的空間要求。確定實(shí)例特性與具體問題密切相關(guān)。28JYP例如:1 float rsum (float *a, const int n) 2 if (n = 0 ) return 0;/ 當(dāng)n = 1時(shí)返回a0

15、3 else return rsum( a, n1) + an1;4 rsum是一個(gè)遞歸求和算法，其實(shí)例特性是n。每次遞歸調(diào)用需在棧頂保存n的值、a的值、返回值和返回地址，共需4個(gè)存儲(chǔ)單元。 由于算法的遞歸深度是n+1，故所需?？臻g是4(n+1)，即Srsum(n) = 4(n+1)。29JYP1.5.2 時(shí)間復(fù)雜性 算法P的運(yùn)行時(shí)間 T(P) = c + TP(實(shí)例特性)時(shí)間復(fù)雜性分析的目的在于揭示算法的運(yùn)行時(shí)間隨著其實(shí)例特性變化的規(guī)律。將一組與實(shí)例特性無關(guān)的操作抽象為一個(gè)程序步，從而有效地簡化性能分析的過程。程序步：算法中的一個(gè)在語法和語義上有意義的指令序列，而且該序列執(zhí)行時(shí)間與算法的實(shí)例

16、特性無關(guān)。30JYP各類C+語句的程序步數(shù)詳見教科書?？梢酝ㄟ^列出各個(gè)語句的程序步數(shù)確定整個(gè)程序的程序步數(shù)。例1.5 程序sum： 1 float sum (float *a, const int n) 2 float s = 0; 3 for (int i = 0; i 0時(shí)Trsum(n) = 2+ Trsum(n-1)。33JYP1 float rsum (float *a, const int n) 2 if (n = 0) /從右向左掃描，遇到第一 / 個(gè)0位停止，并將所經(jīng)過的全部1置0 ai = 0; i-; if ( i = 0 ) ai = 1;41JYP下面分別分析其最好、最

17、壞和平均時(shí)間復(fù)雜性：（1）最好情況：當(dāng)右邊第一位為0時(shí)，掃描停止，算法時(shí)間復(fù)雜性為O(1)。（2）最壞情況：當(dāng)n個(gè)二進(jìn)制位全為1時(shí)，需掃描n位，算法時(shí)間復(fù)雜性為O(n)。42JYP（3）平均情況。n位二進(jìn)制數(shù)共有2n種取值。以n=3 為例，有下列取值： 43JYP一般，從右到左有連續(xù)m個(gè)1需m + 1次操作，這種取值共2n-(m+1)個(gè)（m 100），只有復(fù)雜性較?。ㄈ纾琻，nlog2n，n2，n3）的算法是實(shí)用的。即使計(jì)算機(jī)的速度再提高1000倍，表中時(shí)間也只不過縮小1000倍。在這種情況下，當(dāng)n=100時(shí)，n10個(gè)程序步的運(yùn)行時(shí)間是3.17年，2n個(gè)程序步的運(yùn)行時(shí)間是41010年。46JY

18、P 可見，如果一個(gè)算法的時(shí)間復(fù)雜性過高，當(dāng)n大于一定值時(shí)，再快的計(jì)算機(jī)也無法在實(shí)際可行的時(shí)間內(nèi)完成其運(yùn)行。47JYP1.6 性能測量 性能測量：在一定的數(shù)據(jù)范圍內(nèi)準(zhǔn)確獲取程序運(yùn)行所需要的空間和時(shí)間，屬于事后測量。測量的結(jié)果依賴于編譯器及其設(shè)置，還依賴于程序運(yùn)行的計(jì)算機(jī)。下面重點(diǎn)研究性能（程序的計(jì)算時(shí)間）測量的方法。 假設(shè)函數(shù)time ( &hsec )將當(dāng)前時(shí)間返回到變量hsec中，精度為1毫秒。下面以測量順序查找算法seqsearch在最壞情況下的性能為例，說明性能測量的方法。48JYPint seqsearch (int *a, const int n, const int x ) int

19、 i = n; a0 = x; while (ai != x) i-; return i; 順序查找算法的最壞時(shí)間復(fù)雜性是O(n)。為了反映被忽略的常數(shù)因子的影響，對于較小的n應(yīng)選較多的值測量，對于較大的n值則可稀疏測量。 限于時(shí)鐘精度，對于太短的事件必須重復(fù)m次，然后用測得的總時(shí)間除以m求出事件的時(shí)間。49JYP順序查找算法的測量程序如下： 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

20、*j; nj+10 = 100*( j+1 ); cout “ n 總時(shí)間 運(yùn)行時(shí)間” endl; for ( j=0; j20; j+ ) long start, stop; time (&start);/ 開始計(jì)時(shí) for ( long b=1; b = m; b+ )int k = seqsearch(a, nj, 0 ); / 失敗查找50JYP time (&stop); / 停止計(jì)時(shí) long totalTime = stop - start; float runTime = (float) (totalTime) / (float)m; cout nj totalTime run

21、Timeendl; 執(zhí)行TimeSearch(300000)的輸出如下表所示。從該表可以看出，t基本上隨n線性增長。利用n = 0和60這兩點(diǎn)的數(shù)據(jù)，可得線性函數(shù) t = 0.000096n + 0.0008。由此可推算，當(dāng)n = 1000，t = 0.00968。這與實(shí)際測量的數(shù)據(jù)完全吻合。 51JYP52JYP規(guī)劃性能測量實(shí)驗(yàn)時(shí)應(yīng)注意以下問題： 時(shí)鐘精度、期望的測量結(jié)果精度以及與此相關(guān)的重復(fù)次數(shù)。 根據(jù)是測量最壞性能還是平均性能，生成合適的實(shí)驗(yàn)數(shù)據(jù)。 實(shí)驗(yàn)?zāi)康模菏菫榱吮容^還是為了預(yù)測實(shí)際運(yùn)行時(shí)間？ 當(dāng)實(shí)驗(yàn)?zāi)康氖穷A(yù)測實(shí)際運(yùn)行時(shí)間時(shí)，人們需要通過測量數(shù)據(jù)建立t與n之間的函數(shù)關(guān)系。53JYP 一

22、般需用計(jì)算機(jī)生成導(dǎo)致一個(gè)算法最壞性能的數(shù)據(jù)集。 但在有的情況下計(jì)算機(jī)生成也非常困難。這時(shí)可根據(jù)實(shí)例特性的值隨機(jī)生成足夠量的實(shí)驗(yàn)數(shù)據(jù)，取這些數(shù)據(jù)導(dǎo)致的最長運(yùn)行時(shí)間作為最壞性能。 生成平均性能數(shù)據(jù)更為困難，一般也采用隨機(jī)生成的方法。實(shí)驗(yàn)作業(yè)：P251554JYP1.7 C+中的模板 C+的模板（template）有效地提高了函數(shù)和類的可重用性。 模板（又稱為參數(shù)化類型）是一種能被實(shí)例化為任何數(shù)據(jù)類型的變量，這些類型既包括C+基本類型又包括用戶定義的類型。模板函數(shù):template int seqsearch (KeyType *a, const int n, KeyType x ) int i=n

23、; a0=x; while (ai != x) i-; return i; 55JYP 通過調(diào)用seqsearch，可以很容易地在字符數(shù)組或浮點(diǎn)數(shù)數(shù)組中查找元素: char carray200; float farray300; char x = r; float y = 306.523; / 設(shè)此時(shí)以上數(shù)組已完成初始化 seqsearch(carray, 200, x); seqsearch(farray, 300, y); 函數(shù)seqsearch的KeyType在調(diào)用時(shí)被實(shí)例化為相應(yīng)的實(shí)參類型，例如，調(diào)用seqsearch(farray, 300, y)表示在浮點(diǎn)數(shù)數(shù)組farray中查找浮

24、點(diǎn)數(shù)y。 56JYP seqsearch使用操作符“!=”比較兩個(gè)KeyType對象，使用操作符“=”將一個(gè)KeyType對象賦值給另一個(gè)KeyType對象。 對于用戶定義的數(shù)據(jù)類型，這些操作不可能由系統(tǒng)預(yù)定義。用戶必須重載這些操作以實(shí)現(xiàn)新的語義。57JYP模板類：template class Bag public: Bag ( int MaxSize = DefaultSize ); / 假設(shè)DefaultSize已定義 int Add (const Type& x ); / 將對象x加入容器中 int Delete (const int k ); / 從容器中刪除并打印k 個(gè)對象priva

25、te: int top; / 指示已用空間 Type *b; / 用數(shù)組b存放Type對象 int n; / 容量; 58JYPtemplate Bag:Bag ( int MaxSize = DefaultSize ):n(MaxSize) b = new Typen; top = -1;template int Bag:Add (const Type& x) if (top = = n-1) return 0; / 返回0表示加入失敗 else b+top = x; return 1;59JYPtemplate int Bag:Delete (const int k) if (top +

26、1 k ) return 0; / 返回0表示容器內(nèi)元素不足k/ 個(gè)，刪除失敗 else for (int i = 0; i k; i+) cout btop i “ ” ; top = top - k; return 1; Bag f; Bag c;于是，Bag對象f存放浮點(diǎn)數(shù)，c存放圓。60JYP1.8 效率與權(quán)衡 時(shí)間和空間的權(quán)衡；通用性和效率的權(quán)衡；開發(fā)效率與運(yùn)行效率的權(quán)衡；等等。 61JYP第2章 線性表 本章學(xué)習(xí)最簡單同時(shí)又最常用的數(shù)據(jù)結(jié)構(gòu)線性表。62JYP2.1 線性表與數(shù)組 線性表L定義為： ( a0, a1, , an-1)，n1 L = ( )， n = 0 線性表由n個(gè)元

27、素構(gòu)成。當(dāng)n = 0時(shí)， ( ) 表示空線性表。當(dāng)n 1時(shí)，表中第一個(gè)元素有唯一的后繼，最后一個(gè)元素有唯一的前驅(qū)，其余元素有唯一的后繼和前驅(qū)，因而呈現(xiàn)線性關(guān)系。63JYP 線性表的操作主要包括：（1）計(jì)算表的長度n。（2）從左到右（或從右到左）遍歷表的元素。（3）訪問第i個(gè)元素，0i n。（4）將新值賦予第i個(gè)元素，0i n。（5）將新元素插入第i個(gè)位置，0i n，使原來的第i，i+1，n1個(gè)元素變?yōu)榈趇+1，i+2，n個(gè)元素。（6）刪除第i個(gè)元素，0i n，使原來的第i+1，i+2，n1個(gè)元素變?yōu)榈趇，i+1，n2個(gè)元素。64JYP 假設(shè)線性表的元素類型是浮點(diǎn)數(shù)，其ADT定義為：class

28、LinearList / 對象: L = ( a0, a1, , an-1) 或 ( ), ai浮點(diǎn)數(shù), 0i npublic: LinearList ( ); / 構(gòu)造函數(shù)，創(chuàng)建一個(gè)空表 int Length( ); / 返回該實(shí)例的長度 void LeftToRight( ); / 從左到右遍歷全部元素 float Retrieve( int i ); / 返回第i個(gè)元素的值 void Store( int i, float v ); / 將v的值賦予第i個(gè)元素 void Insert( int i, float v ); / 將v作為第i個(gè)元素插入 float Delete( int i

29、 ); / 刪除第i個(gè)元素并返回其值;65JYP 如何表示線性表的結(jié)構(gòu)，從而高效實(shí)現(xiàn)這些操作？ 最通常的方法是用程序設(shè)計(jì)語言提供的數(shù)組，即用數(shù)組的第i個(gè)單元表示線性表的ai元素。 數(shù)組第i個(gè)單元與第i+1個(gè)單元在物理上是連續(xù)存放的，因此稱上述方法為順序映射（sequential mapping）。 順序映射使隨機(jī)存取表中的任何元素的時(shí)間是O(1)，但插入和刪除第i個(gè)元素將導(dǎo)致其后續(xù)元素的遷移。 作業(yè)：P62266JYP2.2 多項(xiàng)式 數(shù)學(xué)上，多項(xiàng)式P(x)定義為：其中非零項(xiàng)的最大指數(shù)稱為階。多項(xiàng)式的ADT定義如下：class Polynomial / 對象：一個(gè)有序?qū)Φ募? 其中，ai 是系

30、數(shù)，ei 是指/ 數(shù)，且指數(shù)是0的整數(shù)。public: Polynomial ( ); / 返回多項(xiàng)式 p(x) = 067JYP int operator ! ( ); / 若 *this 是零多項(xiàng)式返回1，否則返回0 float Coef (int e);/ 返回*this 中指數(shù)為e 的項(xiàng)的系數(shù) int LeadExp ( ); / 返回*this 中最大指數(shù) void AddTerm (int e, float c);/ 將 加入*this Polynomial Add (Polynomial poly); / 返回多項(xiàng)式 *this 與 / poly之和 Polynomial Mul

31、t (Polynomial poly); / 返回多項(xiàng)式 *this 與 / poly之積 float Eval ( float f); / 計(jì)算并返回x = f時(shí)*this 多項(xiàng)式的值; 68JYP2.2.1 多項(xiàng)式的表示 規(guī)定:多項(xiàng)式中的項(xiàng)按指數(shù)遞減順序排列。方法1 定義一個(gè)有MaxDegree+1個(gè)元素的數(shù)組表示系數(shù)，數(shù)組下標(biāo)表示相應(yīng)的指數(shù)：private: int degree;/ 當(dāng)前多項(xiàng)式的階 float coefMaxDegree+1; / MaxDegree是多項(xiàng)式的最高階若p是類Polynomial的一個(gè)對象，則： p.degree = n p.coefi = an-i，0i

32、n這種表示法使多項(xiàng)式的許多操作實(shí)現(xiàn)非常簡單。69JYP方法2 當(dāng)p.degree em-1 e0 0。 為此，不僅需要顯式存儲(chǔ)系數(shù)，而且需要顯式存儲(chǔ)指數(shù)。同時(shí)，為了充分利用存儲(chǔ)資源，所有Polynomial類的多項(xiàng)式都用一個(gè)元素類型為term的數(shù)組termArray表示： 71JYPterm定義如下：class Polynomial;/ 向前聲明class term friend Polynomial;private: float coef; / 系數(shù) int exp;/ 指數(shù);72JYPPolynomial的私有成員定義如下：private: static term termArrayMax

33、Terms; / 靜態(tài)成員聲明 static int free; / 靜態(tài)成員聲明 int Start, Finish;/ 多項(xiàng)式的起、始位置其中，MaxTerms是常數(shù)。由于類中的靜態(tài)成員聲明不構(gòu)成其定義，還必須在類定義之外定義靜態(tài)成員如下：term Polynomial:termArrayMaxTerms;int Polynomial:free = 0; / 指示termArray中的下一個(gè)可用單元 73JYP例如，A(x) = 2x800+3x3+1和B(x) = 7x5+x3+5x+2 一個(gè)多項(xiàng)式p(x)的項(xiàng)數(shù)為p.Finishp.Start+1。 當(dāng)多項(xiàng)式的零項(xiàng)很多時(shí)，方法3明顯好于

34、方法2。但當(dāng)絕大多數(shù)都是非零項(xiàng)時(shí)，方法3所用空間大約是方法2的兩倍。 74JYP2.2.2 多項(xiàng)式相加 用方法3表示多項(xiàng)式A和B。由于多項(xiàng)式的項(xiàng)是按指數(shù)遞減順序排列的，因而通過對A和B逐項(xiàng)掃描，比較指數(shù)，很容易實(shí)現(xiàn) C=A+B。 用函數(shù)NewTerm將新的屬于C的項(xiàng)存入free所指的termArray可用單元。1 Polynomial Polynomial:Add(Polynomial B) 2 Polynomial C;int a=Start;int b=B.Start;C.Start=free; float c; 3 while (a = Finish & b = B.Finish )4

35、switch (compare(termArraya.exp, termArrayb.exp) 5 case =: c=termArraya.coef + termArrayb.coef;6 if (c) NewTerm(c, termArraya.exp);7 a+; b+; 8 break;75JYP 9 case : NewTerm(termArraya.coef, termArraya.exp); 13 a+;14 15 for (;a=Finish;a+) NewTerm(termArraya.coef, termArraya.exp);/加入A(x)的剩余項(xiàng)16 for (;b=

36、MaxTerms) cout “空間不夠！” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; / NewTerm結(jié)束77JYP分析： 設(shè)m和n分別是A和B的非零項(xiàng)個(gè)數(shù)。 第2行O(1)。 第3行的循環(huán)內(nèi)執(zhí)行一次，a或b或a和b增加1，循環(huán)次數(shù)最多是m+n1。 第15和16行的循環(huán)的總次數(shù)不超過m+n。 整個(gè)算法的時(shí)間復(fù)雜性是O(m+n)。 free超過MaxTerms時(shí)的處理很麻煩。作業(yè)：P624，5 78JYP2.3 稀疏矩陣 矩陣是常用的數(shù)學(xué)對象，由m行、n列元素構(gòu)成，也稱為m n矩陣。當(dāng)m = n時(shí)，

37、稱該矩陣為方陣。例子： 79JYP表示：用二維數(shù)組，如Amn，表示矩陣十分自然。但對于大型稀疏矩陣，非零項(xiàng)只占所需空間的很小部分。較好的辦法是只存儲(chǔ)非零項(xiàng)，而將零元素作為缺省值。80JYP稀疏矩陣抽象數(shù)據(jù)類型 class SparseMatrix / 對象: 三元組的集合，行、列、值都是整型 public: SparseMatrix ( int Rows, int Cols ); SparseMatrix Transpose ( ); / 返回(*this)矩陣的轉(zhuǎn)置矩陣 SparseMatrix Add ( SparseMatrix b); SparseMatrix Multiply ( S

38、parseMatrix b); ; 81JYP2.3.1 稀疏矩陣的表示 用三元組唯一表示矩陣元素 用一個(gè)由此三元組構(gòu)成的數(shù)組表示整個(gè)稀疏矩陣 所有三元組按行號(hào)遞增順序排序，同一行內(nèi)的三元組按列號(hào)遞增順序排序存儲(chǔ)稀疏矩陣的行數(shù)、列數(shù)和非零項(xiàng)的個(gè)數(shù) 82JYPclass SparseMatrix;/ 向前聲明class MatrixTerm friend SparseMatrix;private: int row, col, value;/ 行、列、值;并在SparseMatrix中定義：private: int Rows, Cols, Terms;/ 行數(shù)、列數(shù)、非零項(xiàng)個(gè)數(shù) MatrixTer

39、m smArrayMaxTerms; / MaxTerms是常數(shù)83JYP前面的稀疏矩陣用三元組表示為： 84JYP2.3.2 稀疏矩陣的轉(zhuǎn)置 圖2.3(b)是圖2.3(a)中矩陣的轉(zhuǎn)置： 85JYP初始方法： 順序掃描原矩陣數(shù)組，取元素，將其轉(zhuǎn)變?yōu)榇嫒胄戮仃嚒?問題：轉(zhuǎn)置矩陣中的三元組也必須按照行、列排序，而在處理完所有元素之前，我們并不知道應(yīng)該存放在什么位置。改進(jìn)方法： 按原矩陣的列構(gòu)建新矩陣的行，對j = 0, , Cols-1 順序掃描原矩陣，找到第j列元素，將其轉(zhuǎn)變?yōu)樾戮仃嚨牡趈行元素存入三元組數(shù)組的當(dāng)前位置。86JYP 由此得算法：1 SparseMatrix SparseMatr

40、ix:Transpose ( ) / 返回矩陣a (*this)的轉(zhuǎn)置矩陣2 SparseMatrix b;3 b.Rows = Cols; / b的行數(shù) = a的列數(shù)4 b.Cols = Rows; / b的列數(shù) = a的行數(shù)5 b.Terms = Terms;6 if ( Terms 0 ) / 不是零矩陣7 int CurrentB = 0; / 當(dāng)前位置指針8 for ( int c = 0; c Cols; c+ ) / 按照列轉(zhuǎn)置9 for ( int i = 0; i 0 )結(jié)束17 return b;18 / Transpose結(jié)束 分析：第8到15行的循環(huán)共執(zhí)行Cols次，每

41、次執(zhí)行導(dǎo)致第10行的判斷執(zhí)行Terms次，第10行的總時(shí)間是ColsTerms次。第11，12，13和14行執(zhí)行Terms次。第27行只用常數(shù)時(shí)間。算法的總時(shí)間復(fù)雜性是O(ColsTerms)，需要O(1)輔助空間。88JYP進(jìn)一步改進(jìn)： 第915行的循環(huán)掃描一次僅找到少數(shù)有效三元組，導(dǎo)致算法Transpose的時(shí)間代價(jià)較大。如果先掃描一遍矩陣a，獲得其中各列的元素個(gè)數(shù)，就可知道矩陣b各行的元素個(gè)數(shù)。由此很容易推算出b中各行的開始位置。這樣，可以再次掃描a，逐項(xiàng)將a中元素置入b的正確位置。 RowSizei 矩陣b第i行的元素個(gè)數(shù) RowStarti 矩陣b第i行的當(dāng)前可置入位置 初始時(shí)， R

42、owStart0 = 0 RowStarti = RowStarti1+RowSizei189JYP 以后每次往b的第i行置入一個(gè)元素，RowStarti加1。由此得算法FastTranspose：1 SparseMatrix SparseMatrix:FastTranspose ( ) / 快速轉(zhuǎn)置2 int *rowSize = new intCols;3 int *rowStart = new intCols;4 SparseMatrix b;5 b.Rows = Cols; b.Cols = Rows; b.Terms = Terms;6 if ( Terms 0 ) / 計(jì)算b中第i

43、行的非零項(xiàng)個(gè)數(shù)7 for (int i = 0; i Cols; i+) rowSizei = 0; / 初始化8 for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+; 9 RowStart0 = 0; / RowStarti = b中第i行的開始位置10 for (i = 1;i Cols;i+) rowStarti = rowStarti-1 + rowSizei-1;90JYP11 for ( i = 0; i Terms; i+ ) / 從 a 向b復(fù)制12 int j = RowStartsmArrayi.col;13 b.smArrayj

44、.row = smArrayi.col;14 b.smArrayj.col = smArrayi.row;15 b.smArrayj.value = smArrayi.value;16 RowStartsmArrayi.col+;17 18 19 delete rowSize; delete rowStart; 20 return b;2191JYP 對圖2.3(a)的稀疏矩陣應(yīng)用算法FastTranspose，執(zhí)行完第10行后，RowSize和RowStart的值為： FastTranspose的四個(gè)循環(huán)分別迭代Cols、Terms、Cols-1和Terms次，總時(shí)間復(fù)雜性是O(Cols +

45、 Terms)。 與Transpose相比，F(xiàn)astTranspose 多使用了O(Cols)的輔助空間，但改進(jìn)了計(jì)算時(shí)間。這體現(xiàn)了時(shí)間與空間的權(quán)衡。 92JYP作業(yè)：P627，993JYP2.4 字符串 字符串是由n（n0）個(gè)字符構(gòu)成的線性序列，可表示為S = s0, , sn-1, 其中，si 取自字符集，n是字符串的長度。若n = 0，則S為空串。通過從字符串中刪除零或多個(gè)任意位置的字符可得其一個(gè)子序列。class String / 對象: n0個(gè)字符構(gòu)成的線性序列public: String (const char *init, int m);/ 初始化為長度等于m的/ 字符串init

46、 int operator = (String t ); int operator ! ( ); int Length ( ); String Concat (String t); 94JYPString Substr (int i, int j); / 返回由字符串 *this 的第i個(gè)位/ 置及其后共計(jì)j個(gè)字符構(gòu)成的子字符串int Find ( String pat ); / 若pat是空字符串，或pat不是/ *this的子字符串，返回-1；否則返回*this中/ 第一個(gè)與pat匹配的子字符串的開始位置i int Lcs ( String x );/ 返回*this和x的最長公共子序/

47、列的長度;95JYP2.4.1 字符串模式匹配的簡單算法 設(shè)有字符串s和pat，其長度分別為LengthS 和LengthP。順序考察s的第i個(gè)位置，判定其是否為一個(gè)匹配的起點(diǎn)，直至首次成功匹配，如下圖所示： 設(shè)字符串由類型為char*的私有數(shù)據(jù)成員str表示，函數(shù)Find實(shí)現(xiàn)了上述策略。96JYPint String:Find ( String pat ) char *p = pat.str, *q = str; int i = 0;/ i 是起點(diǎn) if ( *p & *q ) while ( i 0，設(shè)y=p0, , pj-1，x是y的兩頭匹配的最大真子字符串，且x=p0, , pk，則由

48、于已有匹配的結(jié)果，si-k-1, , si-1=pj-k-1, , pj-1=x，從而si-k-1, , si-1 = p0, , pk，因此 si 可與 pk+1繼續(xù)比較。如下圖所示： 102JYP注意： 由于x是y的的兩頭匹配的最大子字符串，用反證法不難證明，si 與 pk+1繼續(xù)比較不會(huì)遺漏模式。 y也是其本身兩頭匹配的最大子字符串，但y不能作為x用，否則比較將陷入無窮循環(huán)。 將以上分析形式化，可得模式p = p0, , pn-1的失敗函數(shù)f 的定義：f(j) = 最大的k 0可繼續(xù)比較si與pf(j-1)+1。由此可得以下算法FastFind。104JYP1 int String:Fa

49、stFind ( String pat )2 3 int j = 0, i = 0;4 int LengthP = pat.Length( ), LengthS = Length( );5 while ( j LengthP) & ( i LengthS)6 if ( pat.strj = stri ) / 字符匹配7 j+; i+;8 9 else10 if ( j = 0) i+;11 else j = pat.f j-1 + 1; / while結(jié)束/ f是類String的數(shù)據(jù)成員12 if ( j 0，且每次j至少減少1（注意f(j1)+1 (j1)+1=j），所以此行最多執(zhí)行Leng

50、thS次。因此，F(xiàn)astFind的總計(jì)算時(shí)間是O( LengthS)。106JYP失敗函數(shù)f的計(jì)算：f(0) = 1。假設(shè)已有f(j1)，則可通過以下觀察計(jì) 算f(j)：若a = b，則f(j) = f(j-1)+1，否則（標(biāo)記f1(j) = f(j)，fm(j) = f( fm-1(j)） 107JYP 若a = c，則f(j) = f2(j-1)+1，否則可以繼續(xù)計(jì)算下去，直至找到某個(gè)m，使第fm(j1)+1個(gè)位置的字符與a相等，或fm(j1) = 1且第0位置的字符仍不等于a。108JYP 由此，可得失敗函數(shù)的另一種定義形式：f(j) =1如果j=0fm(j1)+1m是使得pfk(j-1

51、)+1=pj 的最小的k1如果上述k不存在 由此定義可直接得出計(jì)算 f 的算法 fail。 109JYP1 void String:fail ( ) / 計(jì)算模式p ( *this)的失敗函數(shù)2 int LengthP= Length( ); f0= -1; 3 for (int j = 1; j =0) i=fi; /尋找m6 if ( *(str+j) = *(str+i+1) fj = i+1;7 else fj = -1;/ 找不到滿足條件的m8 / for 結(jié)束9 / fail 結(jié)束對fail的分析： 由于f(i) i，while循環(huán)每迭代一次i至少減少1。 110JYPi在for循

52、環(huán)中的第4行被賦值，當(dāng)j=1時(shí)i=f(0)= 1，以后最多在上次值的基礎(chǔ)上加1（當(dāng)上次執(zhí)行經(jīng)由第6行時(shí)）。由于第4行共執(zhí)行LengthP1次，i的總增加值最多為LengthP1。如果每次至少減少1，經(jīng)過LengthP1次減少，i必定小于0。while循環(huán)中的語句在整個(gè)算法中最多執(zhí)行LengthP1次。 因此，fail的計(jì)算時(shí)間為O(LengthP )。 整個(gè)模式匹配問題可用O(LengthP + LengthS)的時(shí)間完成。111JYP作業(yè)：P6315，16112JYP2.5 棧 棧是一種受限的線性表，其插入和刪除操作只能在表的一端進(jìn)行，該端稱為頂端（top）。棧S = ( a0, , an-

53、1)，a0是棧底元素，an-1是棧頂元素，ai在ai-1之上（0 i n）。由于最后插入的元素最先刪除，又稱棧為后進(jìn)先出（LIFO）表，如下所示：113JYP抽象數(shù)據(jù)類型Stack template class Stack public: Stack ( int MaxStackSize = DefaultSize); Boolean IsFull( ); void Add(const Type& item); Boolean IsEmpty( ); Type* Delete( Type& ); ; Delete操作返回棧頂元素的指針，棧為空時(shí)返回0。為確保該指針?biāo)傅臄?shù)據(jù)在Delete函數(shù)結(jié)

54、束仍然114JYP存在，采用一個(gè)引用參數(shù)，將被刪除元素復(fù)制到該引用參數(shù)，并返回該參數(shù)的指針。棧的表示 最簡單方法是用一維數(shù)組，如stackMaxSize ，再用變量top指示棧頂元素。top = 1表示?？铡?Stack的數(shù)據(jù)成員：private: int top; Type* stack; int MaxSize;115JYP Stack的構(gòu)造函數(shù)：template Stack:Stack(int MaxStackSize):MaxSize(MaxStackSize) stack = new TypeMaxSize; top = -1; IsFull( )的實(shí)現(xiàn)：template inlin

55、e Boolean Stack:IsFull( ) if (top = MaxSize-1) return TRUE; else return FALSE; 116JYP IsEmpty( )的實(shí)現(xiàn)：template inline Boolean Stack:IsFull( ) if (top = -1) return TRUE; else return FALSE; Add的實(shí)現(xiàn)： template void Stack:Add(const Type& x) if (IsFull( ) StackFull( ); else stack+top = x;117JYP Delete的實(shí)現(xiàn)： te

56、mplate Type* Stack:Delete( Type& x) if (IsEmpty( ) StackEmpty( ); return 0; x = stacktop-; return &x; StackFull( )和StackEmpty( )的實(shí)現(xiàn)依賴于具體的應(yīng)用。作業(yè)：P6319 118JYP2.6 隊(duì)列 隊(duì)列是另一種受限的線性表，其插入操作只能在表的尾端（rear）進(jìn)行，刪除操作只能在表的前端（front）進(jìn)行。隊(duì)列S = ( a0, , an-1)，a0是前端元素，an-1是尾端元素，ai在ai-1之后（0 i n）。由于最先插入的元素最先刪除，又稱棧為先進(jìn)先出（FIFO）

57、表，如下所示：119JYP抽象數(shù)據(jù)類型Queue template class Queue public: Queue ( int MaxQueueSize = DefaultSize); Boolean IsFull( ); void Add(const Type& item); Boolean IsEmpty( ); Type* Delete( Type& ); ; 120JYP隊(duì)列的表示 最簡單方法是用一個(gè)一維數(shù)組和兩個(gè)變量front與rear。為了便于判斷隊(duì)列是否為空，front指向隊(duì)列第一個(gè)元素所在位置的前一個(gè)，rear指向隊(duì)列最后一個(gè)元素所在位置。 Queue的數(shù)據(jù)成員：priva

58、te: int front, rear; Type* queue; int MaxSize;121JYP Queue的構(gòu)造函數(shù)：template Queue:Queue(int MaxQueueSize): MaxSize(MaxQueueSize) queue = new TypeMaxSize; front = rear = -1; IsFull( )的實(shí)現(xiàn)：template inline Boolean Queue:IsFull( ) if (rear=MaxSize-1) return TRUE; else return FALSE;122JYP IsEmpty( )的實(shí)現(xiàn)：templ

59、ate inline Boolean Queue:IsEmpty( ) if (front= rear) return TRUE; else return FALSE; Add的實(shí)現(xiàn)： template void Queue:Add(const Type& x) if (IsFull( ) QueueFull( ); else queue+rear = x;123JYP Delete的實(shí)現(xiàn)： template Type* Queue:Delete( Type& x) if (IsEmpty( ) QueueEmpty( ); return 0; x = queue+front; return

60、&x; 124JYP 如下所示，IsFull( ) = TRUE并不一定表示隊(duì)列中有MaxSize個(gè)元素： 125JYP 因此，將數(shù)組queueMaxSize視為環(huán)狀隊(duì)列，如下所示： 126JYP判斷隊(duì)列是否為空的條件仍然是front = rear。front = rear也可能意味著隊(duì)列滿，造成了二義性。隊(duì)列為空時(shí)的front = rear是由于刪除操作使front “追”上rear所致；而隊(duì)列滿的時(shí)候，front = rear是由于加入操作使rear “追”上front所致。為了消除二義性，只允許隊(duì)列容納最多MaxSize 1個(gè)元素，使得rear 永遠(yuǎn)“追”不上front。127JYP 通