《數(shù)據(jù)結(jié)構(gòu)》完整加精版課件

1、1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 2第1章 基本概念和方法 本章論述學(xué)習(xí)和研究數(shù)據(jù)結(jié)構(gòu)所必須的并且將反復(fù)出現(xiàn)的基本概念和方法。 31.1 數(shù)據(jù)結(jié)構(gòu)與軟件系統(tǒng) P.1 設(shè)計(jì)解決實(shí)際問(wèn)題的計(jì)算機(jī)軟件系統(tǒng)，首先需要建立被處理對(duì)象的數(shù)據(jù)模型。 數(shù)據(jù)和世上萬(wàn)物一樣，都是具有結(jié)構(gòu)的。人們很自然地用數(shù)據(jù)結(jié)構(gòu)表示應(yīng)用領(lǐng)域的被處理對(duì)象。例如，樹和圖。 數(shù)據(jù)結(jié)構(gòu)由一個(gè)數(shù)據(jù)對(duì)象以及該對(duì)象中的所有數(shù)據(jù)元素之間的關(guān)系組成。數(shù)據(jù)元素本身可以是數(shù)據(jù)結(jié)構(gòu)，因此，可以構(gòu)造非常復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 4 數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)是以下一層數(shù)據(jù)結(jié)構(gòu)表示上一層數(shù)據(jù)結(jié)構(gòu)，直至以程序設(shè)計(jì)語(yǔ)言提供的基本數(shù)據(jù)類型表示的過(guò)程。為了模擬實(shí)際問(wèn)題的求解過(guò)程和現(xiàn)實(shí)對(duì)象的行為，還必須

2、提供對(duì)數(shù)據(jù)結(jié)構(gòu)的相應(yīng)操作。評(píng)價(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)容。 5計(jì)算機(jī)軟件系統(tǒng)可看成是通過(guò)不同層次的數(shù)據(jù)結(jié)構(gòu)及其操作實(shí)現(xiàn)的。例如： 6中間層數(shù)據(jù)結(jié)構(gòu)起著核心作用，稱之為建模層。對(duì)數(shù)據(jù)結(jié)構(gòu)的研究產(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í)和方法，對(duì)于提高設(shè)計(jì)與開發(fā)軟件系統(tǒng)尤其是復(fù)雜軟件系統(tǒng)的能力，無(wú)疑是十分重要的。 71.2 數(shù)據(jù)抽

3、象與封裝 P.2 抽象和封裝的概念在日常生活中是普遍存在的，例如，人們常用的手機(jī)。通過(guò)數(shù)據(jù)封裝，將一個(gè)數(shù)據(jù)對(duì)象的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)對(duì)外屏蔽。通過(guò)數(shù)據(jù)抽象，將一個(gè)數(shù)據(jù)對(duì)象的規(guī)格說(shuō)明與其實(shí)現(xiàn)分離，對(duì)外提供簡(jiǎn)潔、清晰的接口。Eg. int數(shù)據(jù)結(jié)構(gòu)多層表示的過(guò)程反過(guò)來(lái)也就是從基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)到應(yīng)用領(lǐng)域數(shù)據(jù)結(jié)構(gòu)的不斷抽象與封裝的過(guò)程。8數(shù)據(jù)類型由一個(gè)數(shù)據(jù)對(duì)象的集合和一組作用于這些數(shù)據(jù)對(duì)象的操作組成。例如，C和C+的基本數(shù)據(jù)類型char、int、float和double等。用抽象數(shù)據(jù)類型（ADT）描述數(shù)據(jù)抽象與封裝是一種自然、有效的方法。 抽象數(shù)據(jù)類型是一個(gè)數(shù)據(jù)類型，該數(shù)據(jù)類型的組織遵循將數(shù)據(jù)對(duì)象及對(duì)這些數(shù)據(jù)

4、對(duì)象的操作的規(guī)格說(shuō)明與這些數(shù)據(jù)對(duì)象的表示、操作的實(shí)現(xiàn)相分離的原則。 9當(dāng)強(qiáng)調(diào)一個(gè)數(shù)據(jù)對(duì)象的結(jié)構(gòu)時(shí)，使用數(shù)據(jù)結(jié)構(gòu)的概念。與數(shù)據(jù)結(jié)構(gòu)的概念對(duì)比，抽象數(shù)據(jù)類型包含了一個(gè)數(shù)據(jù)結(jié)構(gòu)的集合，還包含了對(duì)數(shù)據(jù)結(jié)構(gòu)的操作。(C與C+的差別）。抽象數(shù)據(jù)類型成為描述數(shù)據(jù)結(jié)構(gòu)及其操作的有效方式。 定義ADT的語(yǔ)言本質(zhì)上不依賴具體的程序設(shè)計(jì)語(yǔ)言，這里采用C+描述。Eg. (C+并非100%的ADT，如friend，inline等) 10例1.1 抽象數(shù)據(jù)類型“圓”的定義為： P.3class Circle / 對(duì)象: 幾何圓public: Circle(float r); / 構(gòu)造函數(shù)，創(chuàng)建一個(gè)半徑為r的對(duì)象實(shí)例 fl

5、oat Circumference( ); / 返回該實(shí)例的周長(zhǎng) float Area( ); / 返回該實(shí)例的面積; 該抽象數(shù)據(jù)類型的名稱為Circle，數(shù)據(jù)對(duì)象定義為幾何圓，操作包括構(gòu)造函數(shù)、計(jì)算周長(zhǎng)和面積等以及計(jì)算結(jié)果如何獲得。注意：這些定義不依賴于數(shù)據(jù)對(duì)象的具體表示，也沒(méi)有給出操作實(shí)現(xiàn)的過(guò)程。11數(shù)據(jù)抽象和封裝機(jī)制的意義：（0）便于對(duì)軟件的理解和使用（對(duì)用戶）（1）簡(jiǎn)化軟件開發(fā)： 假設(shè)一個(gè)問(wèn)題經(jīng)分析將使用A、B、C三個(gè)數(shù)據(jù)類型和協(xié)調(diào)代碼求解。 （a）四位程序員，可由其中三位程序員各開發(fā)一個(gè)數(shù)據(jù)類型，另一位程序員實(shí)現(xiàn)協(xié)調(diào)代碼。 （b）一位程序員，數(shù)據(jù)抽象也可減少其在某一具體時(shí)間需要考慮的

6、范圍。 12（2）易于測(cè)試和排除錯(cuò)誤： 如下圖所示，數(shù)據(jù)抽象明顯提高了測(cè)試和排除錯(cuò)誤的效率。 13（3）有利于重用： 數(shù)據(jù)抽象和封裝機(jī)制使開發(fā)人員可以將數(shù)據(jù)結(jié)構(gòu)及其操作實(shí)現(xiàn)為可重用的軟件組件。這些組件具有清晰的界面定義，更容易從一個(gè)軟件系統(tǒng)中提取出來(lái)，應(yīng)用于另一個(gè)軟件系統(tǒng)。（4）便于改變數(shù)據(jù)類型的表示： 由于數(shù)據(jù)封裝，外界不能直接訪問(wèn)數(shù)據(jù)類型的內(nèi)部表示。因此，只要操作接口不變，數(shù)據(jù)類型內(nèi)部表示和實(shí)現(xiàn)的改變不會(huì)影響使用該數(shù)據(jù)類型的其他程序。 141.3 算法定義 (Algorithm) P.5 數(shù)據(jù)結(jié)構(gòu)的操作實(shí)際上是以算法的形式實(shí)現(xiàn)的。定義：算法是一個(gè)有限的指令集合，執(zhí)行這些指令可以完成某一特定

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

8、直接遞歸：函數(shù)在執(zhí)行過(guò)程中調(diào)用本身。間接遞歸：函數(shù)在執(zhí)行過(guò)程中調(diào)用其它函數(shù)再經(jīng)過(guò)這些函數(shù)調(diào)用本身。表達(dá)力：函數(shù)定義賦值if-elsewhile 函數(shù)定義賦值if-else遞歸 17當(dāng)問(wèn)題本身是遞歸定義的，其解法適合用遞歸描述。 例1.3 階乘函數(shù)的定義是 1 當(dāng)n=1n! = n(n-1)！ 當(dāng)n1 用遞歸方法計(jì)算階乘函數(shù)簡(jiǎn)明扼要，易于理解，如下所示：long Factorial ( long n ) if ( n = = 1 ) return 1; / 終止條件 else return n*Factorial ( n-1); / 遞歸步驟 18用參數(shù)n= 5調(diào)用Factorial的過(guò)程如下：

9、 P.7Factorial (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) = 12019遞歸算法有四個(gè)特性： P.7（1）必須有可最終達(dá)到的終止條件，否則程序?qū)⑾萑霟o(wú)窮循環(huán)；（2）子問(wèn)題在規(guī)模上比原問(wèn)題小，或更接近終止條件；（3）子問(wèn)題可通過(guò)再次遞歸調(diào)用求解或因滿足終止條件而直接求解；（4）子問(wèn)題的解應(yīng)能組

10、合為整個(gè)問(wèn)題的解。20例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è)元素的全排列。/此處a為（b，c，d）全排列的前綴，其余類推 對(duì)于只有1個(gè)元素的集合，可以連同此時(shí)的前綴直接生成其全排列。于是，全排列生成問(wèn)題的遞歸步驟和終止條件可以確定。21 用n = 3 和 a0.2 = (a, b, c)調(diào)用perm

11、的示意如下：22求解函數(shù)perm：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è)問(wèn)題的解 cout endl; i。 k n-1前綴 當(dāng)前部分元素的全排列23 else / ak,an-1 的排列大于1，遞歸生成 for ( i = k; i n; i+) char temp = ak; ak = ai; ai = temp

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

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

14、 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)。281.5.2 時(shí)間復(fù)雜性 P.10算法P的運(yùn)行時(shí)間 T(P) = c + TP(實(shí)例特性)時(shí)間復(fù)雜性分析的目的在于揭示算法的運(yùn)行時(shí)間隨著其實(shí)例特性變化的規(guī)律。將一組與實(shí)例特性無(wú)關(guān)的操作抽象為一個(gè)程序步，從而有效地簡(jiǎn)化性能分析的過(guò)程。程序步：算法中的一個(gè)在語(yǔ)法和語(yǔ)義上有意義的指令序列，而且該序列執(zhí)行時(shí)間與算法的實(shí)例

15、特性無(wú)關(guān)。29各類C+語(yǔ)句的程序步數(shù)詳見(jiàn)教科書（P11-12）?？梢酝ㄟ^(guò)列出各個(gè)語(yǔ)句的程序步數(shù)確定整個(gè)程序的程序步數(shù)。例1.5 程序sum:計(jì)算a0+a1+an-1 P9 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)。321 float rsum (float *a, const int n) 2 if (n = 0 ) return 0;/ 當(dāng)n = 1時(shí)返回a03 else return rsum( a, n1) + an1;4 33通過(guò)反復(fù)

16、代入可得： 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的程序步數(shù)為2n+2。34許多程序的實(shí)例特性并不僅僅依賴于實(shí)例規(guī)模n，還可能與實(shí)例內(nèi)容密切相關(guān)。 例如，順序查找的程序步數(shù)，不僅與元素個(gè)數(shù)n，而且與集合內(nèi)容有關(guān)。 有時(shí)需要按最好、最壞和平均三種情況分析算法的時(shí)間復(fù)雜性。351.5.3 O表示法 P.14 程序步本身就不是一個(gè)準(zhǔn)確的概念，而是一個(gè)抽象的概念。 再作一次抽象，從由多種因素

17、構(gòu)成的時(shí)間復(fù)雜性中抽取出其主要因素，將常數(shù)抽象為1，有利于抓住主要矛盾，簡(jiǎn)化復(fù)雜性分析。假設(shè)函數(shù)f和g是非負(fù)函數(shù)。 定義：f(n) = O(g(n) 當(dāng)且僅當(dāng)存在正值常數(shù)c和n0，使得對(duì)所有n n0，f(n) c*g(n)。 g(n)是參照物，通常是一些常用的標(biāo)準(zhǔn)函數(shù)。36常用的7種度量：O(1)、 O(log n) 、 O(n)、 O(n log n)、O(n2)、O(n3)、 O(2n) 且 n 充分大時(shí)：O(1) O(log n) O(n) O(n log n) O(n2) O(n3) = 0) /從右向左掃描，遇到第一 / 個(gè)0位停止，并將所經(jīng)過(guò)的全部1置0 ai = 0; i-; i

18、f ( i = 0 ) ai = 1;40下面分別分析其最好、最壞和平均時(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)。41（3）平均情況。n位二進(jìn)制數(shù)共有2n種取值。以n=3 為例，有下列取值： 42一般，從右到左有連續(xù)m個(gè)1需m + 1次操作，這種取值共2n-(m+1)個(gè)（m 100），只有復(fù)雜性較?。ㄈ?，n，nlog2n，n2，n3）的算法是實(shí)用的。即使計(jì)算機(jī)的速度再提高1000倍，表中時(shí)間也只不過(guò)縮小1000倍。在這種情況下，當(dāng)n=100時(shí)，n10個(gè)程序步的運(yùn)行時(shí)間是3.1

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

20、t n, const int x ) int i = n; a0 = x; while (ai != x) i-; return i; 順序查找算法的最壞時(shí)間復(fù)雜性是O(n)。為了反映被忽略的常數(shù)因子的影響，對(duì)于較小的n應(yīng)選較多的值測(cè)量，對(duì)于較大的n值則可稀疏測(cè)量。 限于時(shí)鐘精度，對(duì)于太短的事件必須重復(fù)m次，然后用測(cè)得的總時(shí)間除以m求出事件的時(shí)間。48順序查找算法的測(cè)量程序如下： void TimeSearch (const long m) int a1001, n20; for ( int j = 1; j=1000; j+ ) aj = j; / 初始化a for ( j=0; j10;

21、j+ ) / n的取值 nj = 10*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 ); / 失敗查找49 time (&stop); / 停止計(jì)時(shí) long totalTime = stop - start; float runTime = (float) (totalTime) / (float)m; cout

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

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

24、) /在a1,a2,an中查找x int i=n; a0=x; /找不到時(shí)結(jié)束條件，返回值為 0 while (ai != x) i-; return i; 54 通過(guò)調(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)用seqse

25、arch(farray, 300, y)表示在浮點(diǎn)數(shù)數(shù)組farray中查找浮點(diǎn)數(shù)y。 55 seqsearch使用操作符“!=”比較兩個(gè)KeyType對(duì)象，使用操作符“=”將一個(gè)KeyType對(duì)象賦值給另一個(gè)KeyType對(duì)象。 對(duì)于用戶定義的數(shù)據(jù)類型，這些操作不可能由系統(tǒng)預(yù)定義。用戶必須重載這些操作以實(shí)現(xiàn)新的語(yǔ)義。56模板類： P.23template class Bag public: Bag ( int MaxSize = DefaultSize ); / 假設(shè)DefaultSize已定義 int Add (const Type& x ); / 將對(duì)象x加入容器中 int Delete

26、(const int k ); / 從容器中刪除并打印k 個(gè)對(duì)象private: int top; / 指示已用空間 Type *b; / 用數(shù)組b存放Type對(duì)象 int n; / 容量; 57template 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;58template int Bag:

27、Delete (const int k) if (top + 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對(duì)象f存放浮點(diǎn)數(shù)，c存放圓。591.8 效率與權(quán)衡 時(shí)間和空間的權(quán)衡；通用性和效率的權(quán)衡；開發(fā)效率與運(yùn)行效率的權(quán)衡；等等。 60第2章 線性表 本章學(xué)習(xí)最簡(jiǎn)單同時(shí)又最常用的數(shù)據(jù)結(jié)構(gòu)線性表。612.1 線性表與數(shù)組 P.26 線性表L定義為： ( a0, a1, , an-1

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

29、類型是浮點(diǎn)數(shù)，其ADT定義為：class LinearList / 對(duì)象: L = ( a0, a1, , an-1) 或 ( ), ai浮點(diǎn)數(shù), 0i npublic: LinearList ( ); / 構(gòu)造函數(shù)，創(chuàng)建一個(gè)空表 int Length( ); / 返回該實(shí)例的長(zhǎng)度 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è)元素插

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

31、：一個(gè)有序?qū)Φ募? 其中，ai 是系數(shù)，ei 是指/ 數(shù)，且指數(shù)是0的整數(shù)。public: Polynomial ( ); / 返回多項(xiàng)式 p(x) = 066 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之和

32、。 P1+P2+P3可表述為： / P1.Add(P2).Add(P3) Polynomial Mult (Polynomial poly); / 返回多項(xiàng)式 *this 與/ poly之積。 float Eval ( float f); / 計(jì)算并返回x = f時(shí)*this 多項(xiàng)式的值; 672.2.1 多項(xiàng)式的表示 P.28規(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)式的最高階若

33、p是類Polynomial的一個(gè)對(duì)象，則： p.degree = n p.coefi = an-i，0in /冪次信息隱藏在數(shù)組位置中這種表示法使多項(xiàng)式的許多操作實(shí)現(xiàn)非常簡(jiǎn)單。68方法2 當(dāng)p.degree em-1 e0 0。 為此，不僅需要顯式存儲(chǔ)系數(shù)，而且需要顯式存儲(chǔ)指數(shù)。同時(shí)，為了充分利用存儲(chǔ)資源，所有Polynomial類的多項(xiàng)式都用一個(gè)元素類型為term的數(shù)組termArray表示： 70term定義如下：class Polynomial;/ 向前聲明class term friend Polynomial;private: float coef; / 系數(shù) int exp;/ 指

34、數(shù);71Polynomial的數(shù)據(jù)成員定義如下：private: static term termArrayMaxTerms; / 靜態(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è)可用單元 StarttermArray free Finish 72例如，A(x) =

35、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明顯好于方法2。但當(dāng)絕大多數(shù)都是非零項(xiàng)時(shí)，方法3所用空間大約是方法2的兩倍。 732.2.2 多項(xiàng)式相加 P.30 用方法3表示多項(xiàng)式A和B。由于多項(xiàng)式的項(xiàng)是按指數(shù)遞減順序排列的，因而通過(guò)對(duì)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

36、a=Start;int b=B.Start;C.Start=free; float c; 3 while (a = Finish & b = B.Finish )4 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;74 9 case : NewTerm(termArraya.coef, termArraya.exp); 13 a+;14 15 for

37、 (;a=Finish;a+) NewTerm(termArraya.coef, termArraya.exp);/加入A(x)的剩余項(xiàng)16 for (;b= MaxTerms) cout “空間不夠！” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; / NewTerm結(jié)束76分析： 設(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ù)不超過(guò)m+n。 整個(gè)算法的時(shí)間復(fù)雜性是O(m+n)。 free超過(guò)Ma

38、xTerms時(shí)的處理很麻煩。作業(yè)：P624，5 772.3 稀疏矩陣 P.31 矩陣是常用的數(shù)學(xué)對(duì)象，由m行、n列元素構(gòu)成，也稱為m n矩陣。當(dāng)m = n時(shí)，稱該矩陣為方陣。例子： 78表示：用二維數(shù)組，如Amn，表示矩陣十分自然。但對(duì)于大型稀疏矩陣，非零項(xiàng)只占所需空間的很小部分。較好的辦法是只存儲(chǔ)非零項(xiàng)，而將零元素作為缺省值。79稀疏矩陣抽象數(shù)據(jù)類型 class SparseMatrix / 對(duì)象: 三元組的集合，行、列、值都是整型 public: SparseMatrix ( int Rows, int Cols ); SparseMatrix Transpose ( ); / 返回(*t

39、his)矩陣的轉(zhuǎn)置矩陣 SparseMatrix Add ( SparseMatrix b); / 返回矩陣 *this 與b之和。 /矩陣b1+b2+b3可表述為：b1.Add(b2).Add(b3) SparseMatrix Multiply ( SparseMatrix b); ; /以上的SparseMatrix的ADT定義，并未規(guī)定矩陣的具體表示方法，故上述ADT對(duì)一般矩陣也適用。802.3.1 稀疏矩陣的表示 P.32 用三元組唯一表示矩陣元素 用一個(gè)由此三元組構(gòu)成的數(shù)組表示整個(gè)稀疏矩陣 所有三元組按行號(hào)遞增順序排序，同一行內(nèi)的三元組按列號(hào)遞增順序排序存儲(chǔ)稀疏矩陣的行數(shù)、列數(shù)和非零

40、項(xiàng)的個(gè)數(shù) 81class SparseMatrix;/ 向前聲明class MatrixTerm friend SparseMatrix;private: int row, col, value;/ 非零項(xiàng)的行、列、值;并在SparseMatrix（S.81)中定義：private: /針對(duì)稀疏矩陣 int Rows, Cols, Terms;/ 行數(shù)、列數(shù)、非零項(xiàng)個(gè)數(shù) MatrixTerm smArrayMaxTerms; / MaxTerms是常數(shù)兩件套rowvaluecol82前面的稀疏矩陣（S.79）用三元組表示為： 832.3.2 稀疏矩陣的轉(zhuǎn)置 P.32 圖2.3(b)是圖2.3(

41、a)中矩陣的轉(zhuǎn)置： 84初始方法： 順序掃描原矩陣數(shù)組，取元素，將其轉(zhuǎn)變?yōu)榇嫒胄戮仃嚒?問(wèn)題：轉(zhuǎn)置矩陣中的三元組也必須按照行、列排序，而在處理完所有元素之前，我們并不知道應(yīng)該存放在什么位置。解決辦法： 按原矩陣的列構(gòu)建新矩陣的行，設(shè)立計(jì)數(shù)器j，對(duì)j = 0, , Cols-1 順序掃描原矩陣，找到第j列元素，將其轉(zhuǎn)變?yōu)樾戮仃嚨牡趈行元素存入三元組數(shù)組的當(dāng)前位置。85 由此得算法：1 SparseMatrix SparseMatrix:Transpose ( ) / 返回矩陣a (*this)的轉(zhuǎn)置矩陣2 SparseMatrix b;3 b.Rows = Cols; / b的行數(shù) = a的列數(shù)

42、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次，每次執(zhí)行導(dǎo)致第10行的判斷執(zhí)行Terms次，第10行的總時(shí)間是ColsTerms次（注意到2重for語(yǔ)句無(wú)其他出口）。第11，12，13和14行執(zhí)行Terms次。第27行

43、只用常數(shù)時(shí)間。算法的總時(shí)間復(fù)雜性是O(ColsTerms)，需要O(1)輔助空間。87改進(jìn)方法： 第915行的循環(huán)掃描一次僅找到少數(shù)有效三元組，導(dǎo)致算法Transpose的時(shí)間代價(jià)較大。如果先掃描一遍矩陣a，獲得其中各列的元素個(gè)數(shù)，就可知道矩陣b各行的元素個(gè)數(shù)。由此很容易推算出b中各行的開始位置。這樣，可以再次掃描a，逐項(xiàng)將a中元素置入b的正確位置。設(shè)立2個(gè)計(jì)數(shù)器數(shù)組： RowSizei 矩陣b第i行的元素個(gè)數(shù) RowStarti 矩陣b第i行的當(dāng)前可置入位置 初始時(shí)， RowStart0 = 0 RowStarti = RowStarti1+RowSizei1RowStart0RowStar

44、t188 以后每次往b的第i行置入一個(gè)元素，RowStarti加1。由此得算法FastTranspose： P.341 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行的非零項(xiàng)個(gè)數(shù)7 for (int i = 0; i Cols; i+) rowS

45、izei = 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;8911 for ( i = 0; i Terms; i+ ) / 從 a 向b復(fù)制12 int j = RowStartsmArrayi.col;13 b.smArrayj.row = smArrayi.col;14 b.smArrayj.col = smAr

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

47、的輔助空間，但改進(jìn)了計(jì)算時(shí)間。這體現(xiàn)了時(shí)間與空間的權(quán)衡。 91算法改進(jìn)：（習(xí)題2 P629）P.34函數(shù)FastTranspose第8行：for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+; 改為8 for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+1+; 0 1 2 3 4 5 6 7 2 1 1 2 0 1 1 0 2 3 4 6 6 7作業(yè)：P627，9RowSizeRowStart922.4 字符串 P.35 字符串是由n（n0）個(gè)字符構(gòu)成的線性序列，可表示為S = s0, , sn-1, 其中，s

48、i 取自字符集，n是字符串的長(zhǎng)度。若n = 0，則S為空串。通過(guò)從字符串中刪除零或多個(gè)任意位置的字符可得其一個(gè)子序列。C+規(guī)定，字符串常數(shù)結(jié)束符為“0”。93class String / 對(duì)象: n0個(gè)字符構(gòu)成的線性序列 public: String (const char *init, int m);/ 初始化為長(zhǎng)度等于m的 / 字符串init int operator = (String t ); / 操作符重載。注釋見(jiàn)P.35 int operator ! ( );/ 空串？ int Length ( ); String Concat (String t); String Substr

49、(int i, int j); / 返回由字符串 *this 的第i個(gè)位/ 置及其后共計(jì)j個(gè)字符構(gòu)成的子字符串int Find ( String pat ); / 若pat是空字符串，或pat不是/ *this的子字符串，返回-1；否則返回*this中/ 第一個(gè)與pat匹配的子字符串的開始位置Iint Lcs ( String x );/ 返回*this和x的最長(zhǎng)公共子序/ 列的長(zhǎng)度;942.4.1 字符串模式匹配的簡(jiǎn)單算法 P.36 設(shè)有字符串s和pat，其長(zhǎng)度分別為L(zhǎng)engthS 和LengthP。順序考察s的第i個(gè)位置，判定其是否為一個(gè)匹配的起點(diǎn)，直至首次成功匹配（p移至pat尾），如下

50、圖所示： 設(shè)字符串由類型為char*的私有數(shù)據(jù)成員str表示，函數(shù)Find實(shí)現(xiàn)了上述策略。95int String:Find ( String pat ) char *p = pat.str, *q = str; /分別指向2個(gè)串的頭部 int i = 0;/ i 是此次匹配的起點(diǎn) if ( *p & *q )/ 非空串 while ( i 0，設(shè)y=p0, , pj-1，x是y的兩頭匹配的最大真子字符串，且x=p0, , pk，則由于已有匹配的結(jié)果，si-k-1, , si-1=pj-k-1, , pj-1=x，從而si-k-1, , si-1 = p0, , pk，因此 si 可與 pk+

51、1繼續(xù)比較。如下圖所示： i 只增不減(不回溯)101注意： 由于x是y的的兩頭匹配的最大子字符串，用反證法不難證明，si 與 pk+1繼續(xù)比較不會(huì)遺漏模式。 y也是其本身兩頭匹配的最大子字符串，但y不能作為x用，否則比較將陷入無(wú)窮循環(huán)。 將以上分析形式化，可得模式p = p0, , pn-1的失敗函數(shù)f 的定義：f(j) = 最大的k 0可繼續(xù)比較si與pf(j-1)+1。由此可得以下算法FastFind。Class String的數(shù)據(jù)成員： Private: char strMaxStr; / where the string is int fMaxStr; / failure funct

52、ion1031 int String:FastFind ( String pat ) P.382 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

53、)+1 (j1)+1=j），所以此行最多執(zhí)行LengthS次。因此，F(xiàn)astFind的總計(jì)算時(shí)間是O( LengthS)。105失敗函數(shù)f的計(jì)算： P.38f(0) = 1。假設(shè)已有f(j1)，則可通過(guò)以下觀察計(jì) 算f(j)：若a = b，則f(j) = f(j-1)+1。一階失敗函數(shù)f1(j) = f(j)否則：106若a = c，則f(j) = f(f(j-1)+1= f2(j-1)+1，否則可以繼續(xù)計(jì)算下去， fm(j) = f( fm-1(j) m=1,2,直至找到某個(gè)m，使第fm(j1)+1個(gè)位置的字符與a相等，或fm(j1) = 1（且第0位置的字符仍不等于a,見(jiàn)63習(xí)題17）。1

54、07 由此，可得失敗函數(shù)的另一種定義形式：f(j) =1如果j=0fm(j1)+1m是使得pfk(j-1)+1=pj 的最小的k1如果上述k不存在 由此定義可直接得出計(jì)算 f 的算法 fail。 1081 void String:fail ( ) / 計(jì)算模式p ( *this)的失敗函數(shù)2 int LengthP= Length( ); f0= -1; 3 for (int j = 1; j =0) i=fi; /尋找m /*(str+j)為Pj, *(str+i+1)為Pf k(j-1)+16 if ( *(str+j) = *(str+i+1) fj = i+1;7 else fj =

55、-1;/ 找不到滿足條件的m8 / for 結(jié)束9 / fail 結(jié)束對(duì)fail的分析： for循環(huán)LengthP-1次。下面關(guān)注while循環(huán)。LengthP次109i在for循環(huán)中的第4行被賦值，當(dāng)j=1時(shí)i=f(0)= 1，以后最多在上次值的基礎(chǔ)上加1（相當(dāng)于i+，當(dāng)上次執(zhí)行經(jīng)由第6行時(shí)）。由于第4行共執(zhí)行LengthP1次，i的總增加值最多為L(zhǎng)engthP1。由于f(i) i，while循環(huán)每迭代一次i至少減少1。如果每次至少減少1，經(jīng)過(guò)LengthP1次減少，i必定小于0。while循環(huán)中的語(yǔ)句在整個(gè)算法中最多執(zhí)行LengthP1次。 因此，fail的計(jì)算時(shí)間為O(LengthP )

56、。 整個(gè)模式匹配問(wèn)題可用O(LengthP + LengthS)的時(shí)間完成。110作業(yè)：P6315，161112.5 棧 P.41棧是一種受限的線性表，其插入和刪除操作只能在表的一端進(jìn)行，該端稱為頂端（top）。棧S = ( a0, , an-1)，a0是棧底元素，an-1是棧頂元素，ai在ai-1之上（0 i n）。由于最后插入的元素最先刪除，又稱棧為后進(jìn)先出（LIFO）表，如下所示：衣櫥 vs 衣箱112抽象數(shù)據(jù)類型Stack template class Stack public: Stack ( int MaxStackSize = DefaultSize); Boolean IsFu

57、ll( ); void Add(const Type& item); Boolean IsEmpty( ); Type* Delete( Type& ); ; Delete操作返回棧頂元素的指針，棧為空時(shí)返回0。為確保該指針?biāo)傅臄?shù)據(jù)在Delete函數(shù)結(jié)束仍然113存在，采用一個(gè)引用參數(shù)，將被刪除元素復(fù)制到該引用參數(shù)，并返回該參數(shù)的指針。棧的表示 最簡(jiǎn)單方法是用一維數(shù)組，如stackMaxSize ，再用變量top指示棧頂元素。top = 1表示?？?。 Stack的數(shù)據(jù)成員：private: int top; Type* stack; int MaxSize;114 Stack的構(gòu)造函數(shù)：te

58、mplate Stack:Stack(int MaxStackSize):MaxSize(MaxStackSize) stack = new TypeMaxSize; top = -1; IsFull( )的實(shí)現(xiàn)：template inline Boolean Stack:IsFull( ) if (top = MaxSize-1) return TRUE; else return FALSE; 115 IsEmpty( )的實(shí)現(xiàn)：template inline Boolean Stack:IsFull( ) if (top = -1) return TRUE; else return FAL

59、SE; Add的實(shí)現(xiàn)： template void Stack:Add(const Type& x) if (IsFull( ) StackFull( ); else stack+top = x;重載：拷貝構(gòu)造函數(shù)116 Delete的實(shí)現(xiàn)： template Type* Stack:Delete( Type& x) if (IsEmpty( ) StackEmpty( ); return 0; x = stacktop-; return &x; StackFull( )和StackEmpty( )的實(shí)現(xiàn)依賴于具體的應(yīng)用。Q1 to Add：Why “Type&” instead of “Ty

60、pe ”Q2 to Delete：Why “return &x”作業(yè)：P6319 1172.6 隊(duì)列 P.44隊(duì)列是另一種受限的線性表，其插入操作只能在表的尾端（rear）進(jìn)行，刪除操作只能在表的前端（front）進(jìn)行。隊(duì)列S = ( a0, , an-1)，a0是前端元素，an-1是尾端元素，ai在ai-1之后（0 i n）。由于最先插入的元素最先刪除，又稱棧為先進(jìn)先出（FIFO）表，如下所示： A A B A B C A B C D B C D C Df/r f r f r f r f r f r f r118抽象數(shù)據(jù)類型Queue template class Queue public: