《《數(shù)據(jù)結構嚴蔚敏》PPT課件》由會員分享，可在線閱讀，更多相關《《數(shù)據(jù)結構嚴蔚敏》PPT課件（815頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結構目錄,第一章：緒論 第二章： 第三章： 第四章： 第五章： 第六章： 第七章： 第八章： 第九章： 第十章：排序,算法與數(shù)據(jù)結構,教材：數(shù)據(jù)結構(C語言版)。嚴蔚敏，吳偉民 編 著。清華大學出版社。 參考文獻： 1 數(shù)據(jù)結構 。張選平，雷詠梅 編， 嚴蔚敏 審。 機械工業(yè)出版社。 2 數(shù)據(jù)結構與算法分析。Clifford A. Shaffer著， 張 銘，劉曉丹 譯。電子工業(yè)出版社。 3 數(shù)據(jù)結構習題與解析(C語實言版)。李春葆。 清華大學出版社。 4 數(shù)據(jù)結構與算法。夏克儉 編著。國防工業(yè)出版社。,第1章 緒 論,目前，計算機已深入到社會生活的各個領域，其應用已不再僅僅局限于科學計算

2、，而更多的是用于控制，管理及數(shù)據(jù)處理等非數(shù)值計算領域。計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題：信息的表示，信息的處理。 信息的表示和組織又直接關系到處理信息的程序的效率。隨著應用問題的不斷復雜，導致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應用程序的規(guī)模很大，結構又相當復雜。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關系，這就是數(shù)據(jù)結構這門課所要研究的問題。,編寫解決實際問題的程序的一般過程： 如何用數(shù)據(jù)形式描述問題?即由問題抽象出一個適當?shù)臄?shù)學模型; 問題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關系; 如何在計算機中存儲數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關系? 處理問

3、題時需要對數(shù)據(jù)作何種運算? 所編寫的程序的性能是否良好? 上面所列舉的問題基本上由數(shù)據(jù)結構這門課程來回答。,計算機求解問題的一般步驟,1.1 數(shù)據(jù)結構及其概念,算法與數(shù)據(jù)結構是計算機科學中的一門綜合性專業(yè)基礎課。是介于數(shù)學、計算機硬件、計算機軟件三者之間的一門核心課程，不僅是一般程序設計的基礎，而且是設計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應用程序的重要基礎。,1.1.1 數(shù)據(jù)結構的例子,例1：電話號碼查詢系統(tǒng) 設有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中ai, bi(i=1，2n

4、) 分別表示某人的名字和電話號碼。 本問題是一種典型的表格問題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡單的一對一的線性關系。,表1-1 線性表結構,例2：磁盤目錄文件系統(tǒng) 磁盤根目錄下有很多子目錄及文件，每個子目錄里又可以包含多個子目錄及文件，但每個子目錄只有一個父目錄，依此類推： 本問題是一種典型的樹型結構問題，如圖1-1 ，數(shù)據(jù)與數(shù)據(jù)成一對多的關系，是一種典型的非線性關系結構樹形結構。,圖1-1 樹形結構,例3：交通網(wǎng)絡圖 從一個地方到另外一個地方可以有多條路徑。本問題是一種典型的網(wǎng)狀結構問題，數(shù)據(jù)與數(shù)據(jù)成多對多的關系，是一種非線性關系結構。,數(shù)據(jù)(Data) ：是客觀事物的符號表示。在計算機科學中指

5、的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。 數(shù)據(jù)元素(Data Element) ：是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。 數(shù)據(jù)對象(Data Object)：是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合C=A,B,C, 。,1.1.2 基本概念和術語,數(shù)據(jù)結構(Data Structure)：是指相互之間具有(存在)一定聯(lián)系(關系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關系)稱為邏輯結構。數(shù)據(jù)元素之間的邏輯結構有

6、四種基本類型，如圖1-3所示。 集合：結構中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其它關系。 線性結構：結構中的數(shù)據(jù)元素之間存在一對一的關系。 樹型結構：結構中的數(shù)據(jù)元素之間存在一對多的關系。 圖狀結構或網(wǎng)狀結構：結構中的數(shù)據(jù)元素之間存在多對多的關系。,數(shù)據(jù)結構的形式定義是一個二元組： Data-Structure=(D，S) 其中：D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。 例2：設數(shù)據(jù)邏輯結構B=（K，R） K=k1, k2, , k9 R= ， 畫出這邏輯結構的圖示，并確定那些是起點，那些是終點,1.1.3 數(shù)據(jù)結構的形式定義,圖1-3 四類基本結構圖,1.1.4 數(shù)據(jù)結構的存儲方式

7、,數(shù)據(jù)元素之間的關系可以是元素之間代表某種含義的自然關系，也可以是為處理問題方便而人為定義的關系，這種自然或人為定義的 “關系”稱為數(shù)據(jù)元素之間的邏輯關系，相應的結構稱為邏輯結構。,數(shù)據(jù)結構在計算機內存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關系的表示。 元素之間的關系在計算機中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。 順序存儲結構：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結構(關系)。,鏈式存儲結構：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer )，用該指針來表示數(shù)據(jù)元素之間的邏輯結構(關系)。 例

8、：設有數(shù)據(jù)集合A=3.0,2.3,5.0,-8.5,11.0 ，兩種不同的存儲結構。 順序結構：數(shù)據(jù)元素存放的地址是連續(xù)的； 鏈式結構：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求。 數(shù)據(jù)的邏輯結構和物理結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現(xiàn)依賴于所采用的存儲結構。 在C語言中，用一維數(shù)組表示順序存儲結構；用結構體類型表示鏈式存儲結構。,數(shù)據(jù)結構的三個組成部分： 邏輯結構： 數(shù)據(jù)元素之間邏輯關系的描述 D_S=（D，S） 存儲結構： 數(shù)據(jù)元素在計算機中的存儲及其邏輯關系的表現(xiàn)稱為數(shù)據(jù)的存儲結構或物理結構。 數(shù)據(jù)操作： 對數(shù)據(jù)要進行的運算。 本課程中將要討論的三種邏輯

9、結構及其采用的存儲結構如圖1-4所示。,數(shù)據(jù)類型(Data Type)：指的是一個值的集合和定義在該值集上的一組操作的總稱。 數(shù)據(jù)類型是和數(shù)據(jù)結構密切相關的一個概念。 在C語言中數(shù)據(jù)類型有：基本類型和構造類型。 數(shù)據(jù)結構不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關系。,1.1.5 數(shù)據(jù)類型,數(shù)據(jù)結構的主要運算包括： 建立(Create)一個數(shù)據(jù)結構； 消除(Destroy)一個數(shù)據(jù)結構； 從一個數(shù)據(jù)結構中刪除(Delete)一個數(shù)據(jù)元素； 把一個數(shù)據(jù)元素插入(Insert)到一個數(shù)據(jù)結構中； 對一個數(shù)據(jù)結構進行訪問(Access)； 對

10、一個數(shù)據(jù)結構(中的數(shù)據(jù)元素)進行修改(Modify)； 對一個數(shù)據(jù)結構進行排序(Sort)； 對一個數(shù)據(jù)結構進行查找(Search)。,1.1.6 數(shù)據(jù)結構的運算,抽象數(shù)據(jù)類型(Abstract Data Type ，簡稱ADT)：是指一個數(shù)學模型以及定義在該模型上的一組操作。 ADT的定義僅是一組邏輯特性描述， 與其在計算機內的表示和實現(xiàn)無關。因此，不論ADT的內部結構如何變化，只要其數(shù)學特性不變，都不影響其外部使用。 ADT的形式化定義是三元組：ADT=(D，S，P) 其中：D是數(shù)據(jù)對象，S是D上的關系集，P是對D的基本操作集。,1.2 抽象數(shù)據(jù)類型,ADT的一般定義形式是： ADT 數(shù)據(jù)

11、對象： 數(shù)據(jù)關系： 基本操作： ADT 其中數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼描述。 基本操作的定義是： () 初始條件： 操作結果： ,初始條件：描述操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件;若不滿足，則操作失敗，返回相應的出錯信息。 操作結果：描述操作正常完成之后，數(shù)據(jù)結構的變化狀況和 應返回的結果。,1.3.1 算法 算法(Algorithm)：是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。 算法具有以下五個特性 有窮性： 一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。 確定性：算法中每一條指令必須有確切的含義。不存在二義性。且

12、算法只有一個入口和一個出口。 可行性： 一個算法是能行的。即算法描述的操作都可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。,1.3 算法分析初步, 輸入： 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。 輸出： 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。 一個算法可以用多種方法描述，主要有：使用自然語言描述；使用形式語言描述；使用計算機程序設計語言描述。 算法和程序是兩個不同的概念。一個計算機程序是對一個算法使用某種程序設計語言的具體實現(xiàn)。算法必須可終止意味著不是所有的計算機程序都是算法。 在本門課程的學習、作業(yè)練習、上機實踐等環(huán)節(jié)，算法都用C語言來描述。在上

13、機實踐時，為了檢查算法是否正確，應編寫成完整的C語言程序。,評價一個好的算法有以下幾個標準 正確性(Correctness )： 算法應滿足具體問題的需求。 可讀性(Readability)： 算法應容易供人閱讀和交流?？勺x性好的算法有助于對算法的理解和修改。 健壯性(Robustness)： 算法應具有容錯處理。當輸入非法或錯誤數(shù)據(jù)時，算法應能適當?shù)刈鞒龇磻蜻M行處理，而不會產生莫名其妙的輸出結果。 通用性(Generality)： 算法應具有一般性 ，即算法的處理結果對于一般的數(shù)據(jù)集合都成立。,1.3.2 算法設計的要求,算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度

14、量。其方法通常有兩種： 事后統(tǒng)計：計算機內部進行執(zhí)行時間和實際占用空間的統(tǒng)計。 問題：必須先運行依據(jù)算法編制的程序；依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒有實際價值。 事前分析：求出該算法的一個時間界限函數(shù)。,1.3.3 算法效率的度量, 效率與存儲量需求： 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般地，這兩者與問題的規(guī)模有關。,與此相關的因素有： 依據(jù)算法選用何種策略； 問題的規(guī)模； 程序設計的語言； 編譯程序所產生的機器代碼的質量； 機器執(zhí)行指令的速度； 撇開軟硬件等有關部門因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規(guī)模（通常用n

15、表示），或者說，它是問題規(guī)模的函數(shù)。,算法分析應用舉例,算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間量度記作 T(n)=O(f(n)，稱作算法的漸近時間復雜度(Asymptotic Time complexity)，簡稱時間復雜度。 一般地，常用最深層循環(huán)內的語句中的原操作的執(zhí)行頻度(重復執(zhí)行的次數(shù))來表示。 “O”的定義： 若f(n)是正整數(shù)n的一個函數(shù)，則 O(f(n)表示 M0 ，使得當n n0時，| f(n) | M | f(n0) | 。 表示時間復雜度的階有： O(1) ：常量時間階 O (n)：線性時間階 O(n) ：對數(shù)時間階 O(nn) ：線性對數(shù)時間階,O (

16、nk)： k2 ，k次方時間階 例 兩個n階方陣的乘法 for(i=1，i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik*bkj ; 由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為： nnn=n3時間復雜度為T(n)=O(n3) 例 +x; s=0 ; 將x自增看成是基本操作，則語句頻度為，即時間復雜度為(1) 。,如果將s=0也看成是基本操作，則語句頻度為，其時間復雜度仍為(1)，即常量階。 例 for(i=1; i=n; +i) +x; s+=x ; 語句頻度為：2n，其時間復雜度為：O(n) ，即為線性階。 例

17、for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 語句頻度為：2n2 ，其時間復雜度為：O(n2) ，即為平方階。,定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一個m次多項式，則A(n)=O(n m) 例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai,j=x; 語句頻度為： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 時間復雜度為O(n2)，即此算法的時間復雜度為平方階。 一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定

18、的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為O(n2)的算法則由一個二次多項式來限界。,以下六種計算算法時間的多項式是最常用的。其關系為： O(1)O(n)O(n)O(nn)O(n2)O(n3) 指數(shù)時間的關系為： O(2n)O(n!)O(nn) 當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。 有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。,例1：素數(shù)的判斷算法。 Void prime( int n) /* n是一個正整數(shù) */ i

19、nt i=2 ; while ( (n% i)!=0 嵌套的最深層語句是i+；其頻度由條件( (n% i)!=0 for (i=n-1; change=TURE; i1 最好情況：0次 最壞情況：1+2+3+n-1=n(n-1)/2 平均時間復雜度為： O(n2),1.3.4 算法的空間分析,空間復雜度(Space complexity) ：是指算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量。記作： S(n)=O(f(n) 其中： n為問題的規(guī)模(或大小) 該存儲空間一般包括三個方面： 指令常數(shù)變量所占用的存儲空間; 輸入數(shù)據(jù)所占用的存儲空間; 輔助(存儲)空間。 一般地，算法的空間

20、復雜度指的是輔助空間。 一維數(shù)組an： 空間復雜度 O(n) 二維數(shù)組anm： 空間復雜度 O(n*m),習 題 一,1 簡要回答術語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結構，數(shù)據(jù)類型。 2 數(shù)據(jù)的邏輯結構？數(shù)據(jù)的物理結構？邏輯結構與物理結構的區(qū)別和聯(lián)系是什么？ 3 數(shù)據(jù)結構的主要運算包括哪些？ 4 算法分析的目的是什么？算法分析的主要方面是什么？ 5 分析以下程序段的時間復雜度，請說明分析的理由或原因。,第2章 線性表,線性結構是最常用、最簡單的一種數(shù)據(jù)結構。而線性表是一種典型的線性結構。其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結構中： 存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素； 存在一個唯

21、一的被稱為“最后一個”的數(shù)據(jù)元素； 除第一個元素外，每個元素均有唯一一個直接前驅； 除最后一個元素外，每個元素均有唯一一個直接后繼。,2.1 線性表的邏輯結構,線性表(Linear List) ：是由n(n0)個數(shù)據(jù)元素(結點)a1，a2， an組成的有限序列。該序列中的所有結點具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。 當n=0時，稱為空表。 當n0時，將非空的線性表記作： (a1，a2，an) a1稱為線性表的第一個(首)結點，an稱為線性表的最后一個(尾)結點。,2.1.1 線性表的定義,a1，a2，ai-1都是ai(2in)的前驅，其中ai-1是ai的直接前驅; ai+

22、1，ai+2，an都是ai(1i n-1)的后繼，其中ai+1是ai的直接后繼。,2.1.2 線性表的邏輯結構,線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應用的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號。 線性表中的結點可以是單值元素(每個元素只有一個數(shù)據(jù)項) 。 例1: 26個英文字母組成的字母表： (A，B，C、Z）,例2 ： 某校從1978年到1983年各種型號的計算機擁有量的變化情況：(6，17，28，50，92，188） 例3 ： 一副撲克的點數(shù) (2，3，4，J，Q，K，A) 線性表中的結點可以是記錄型元素，每個元素含有多個數(shù)據(jù)項 ，每個項稱為結點的一個域 。每個元

23、素有一個可以唯一標識每個結點的數(shù)據(jù)項組，稱為關鍵字。 例4 ： 某校2001級同學的基本情況：(2001414101，張里戶，男，06/24/1983)， (2001414102，張化司，男，08/12/1984) ， (2001414102，李利辣，女，08/12/1984) 若線性表中的結點是按值(或按關鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。,2.1.3 線性表的抽象數(shù)據(jù)類型定義,ADT List 數(shù)據(jù)對象：D = ai | aiElemSet, i=1,2,n, n0 數(shù)據(jù)關系：R = | ai-1, aiD, i=2,3,n 基本操作： InitList( 數(shù)據(jù)元素之

24、間的關系是以元素在計算機內“物理位置相鄰”來體現(xiàn)。 設有非空的線性表：(a1，a2，an) 。順序存儲如圖2-1所示。,2.2.1 線性表的順序存儲結構,在具體的機器環(huán)境下：設線性表的每個元素需占用l個存儲單元，以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關系： LOC(ai+1)=LOC(ai)+l 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC(ai)=LOC(a1)+(i-1)*l,在高級語言(如C語言)環(huán)境下：數(shù)組具有隨機存取的特性，因此，借助數(shù)組來描述順序表。除了用數(shù)

25、組來存儲線性表的元素之外，順序表還應該有表示線性表的長度屬性，所以用結構類型來定義順序表類型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int Status ; typedef int ElemType ; typedef struct sqlist ElemType Elem_arrayMAX_SIZE ; int length ; SqList ;,2.2.2 順序表的基本操作,順序存儲結構中，很容易實現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。 以下將對幾種主要的操作進行討論。 1 順序

26、線性表初始化 Status Init_SqList( SqList *L ) L-elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L - elem_array ) return ERROR ; else L-length= 0 ; return OK ; ,2 順序線性表的插入 在線性表 L= (a1，a i-1，ai， ai+1，an) 中的第i(1in)個位置上插入一個新結點e，使其成為線性表： L=(a1，a i-1，e，ai，ai+1，an) 實現(xiàn)步驟 (1) 將線性表L中的第i個至第n個結點后

27、移一個位置。 (2) 將結點e插入到結點ai-1之后。 (3) 線性表長度加1。,算法描述 Status Insert_SqList(Sqlist *L，int i ，ElemType e) int j ; if ( iL-length-1) return ERROR ; if (L-length=MAX_SIZE) printf(“線性表溢出!n”); return ERROR ; for ( j=L-length1; j=i-1; -j ) L-Elem_arrayj+1=L-Elem_arrayj; /* i-1位置以后的所有結點后移 */ L-Elem_arrayi-1=e; /* 在

28、i-1位置插入結點 */ L-length+ ; return OK ; ,時間復雜度分析 在線性表L中的第i個元素之前插入新結點，其時間主要耗費在表中結點的移動操作上，因此，可用結點的移動來估計算法的時間復雜度。 設在線性表L中的第i個元素之前插入結點的概率為Pi，不失一般性，設各個位置插入是等概率，則Pi=1/(n+1)，而插入時移動結點的次數(shù)為n-i+1。 總的平均移動次數(shù)： Einsert=pi*(n-i+1) (1in) Einsert=n/2 。 即在順序表上做插入運算，平均要移動表上一半結點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復雜度為O(n)。,3 順序線性表的

29、刪除 在線性表 L=(a1，a i-1，ai， ai+1，an) 中刪除結點ai(1in)，使其成為線性表： L= (a1，ai-1，ai+1，an) 實現(xiàn)步驟 (1) 將線性表L中的第i+1個至第n個結點依此向前移動一個位置。 (2) 線性表長度減1。 算法描述 ElemType Delete_SqList(Sqlist *L，int i) int k ; ElemType x ;,if (L-length=0) printf(“線性表L為空!n”); return ERROR; else if ( iL-length ) printf(“要刪除的數(shù)據(jù)元素不存在!n”) ; return E

30、RROR ; else x=L-Elem_arrayi-1 ; /*保存結點的值*/ for ( k=i ; klength ; k+) L-Elem_arrayk-1=L-Elem_arrayk; /* i位置以后的所有結點前移 */ L-length-; return (x); ,時間復雜度分析 刪除線性表L中的第i個元素，其時間主要耗費在表中結點的移動操作上，因此，可用結點的移動來估計算法的時間復雜度。 設在線性表L中刪除第i個元素的概率為Pi，不失一般性，設刪除各個位置是等概率，則Pi=1/n，而刪除時移動結點的次數(shù)為n-i。 則總的平均移動次數(shù)： Edelete=pi*(n-i) (

31、1in) Edelete=(n-1)/2 。 即在順序表上做刪除運算，平均要移動表上一半結點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復雜度為O(n)。,4 順序線性表的查找定位刪除 在線性表 L= (a1，a2，an) 中刪除值為x的第一個結點。 實現(xiàn)步驟 (1) 在線性表L查找值為x的第一個數(shù)據(jù)元素。 (2) 將從找到的位置至最后一個結點依次向前移動一個位置。 (3) 線性表長度減1。 算法描述 Status Locate_Delete_SqList(Sqlist *L，ElemType x) /* 刪除線性表L中值為x的第一個結點 */ int i=0 , k ;,while

32、 (ilength) /*查找值為x的第一個結點*/ if (L-Elem_arrayi!=x ) i+ ; else for ( k=i+1; klength; k+) L-Elem_arrayk-1=L-Elem_arrayk; L-length-; break ; if (iL-length) printf(“要刪除的數(shù)據(jù)元素不存在!n”) ; return ERROR ; return OK; ,時間復雜度分析 時間主要耗費在數(shù)據(jù)元素的比較和移動操作上。 首先，在線性表L中查找值為x的結點是否存在; 其次，若值為x的結點存在，且在線性表L中的位置為i ，則在線性表L中刪除第i個元素。

33、設在線性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設各個位置是等概率，則Pi=1/n。 比較的平均次數(shù)： Ecompare=pi*i (1in) Ecompare=(n+1)/2 。 刪除時平均移動次數(shù)：Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 平均時間復雜度：Ecompare+Edelete=n ，即為O(n),2.3 線性表的鏈式存儲,2.3.1 線性表的鏈式存儲結構,鏈式存儲 ：用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。 存儲鏈表中結點的一組任意的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內存中的任

34、意位置上的。 鏈表中結點的邏輯順序和物理順序不一定相同。,為了正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其直接后繼結點的地址(或位置)，稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結點結構，如圖2-2所示。 鏈表是通過每個結點的指針域將線性表的n個結點按其邏輯次序鏈接在一起的。 每一個結只包含一個指針域的鏈表，稱為單鏈表。 為操作方便，總是在鏈表的第一個結點之前附設一個頭結點(頭指針)head指向第一個結點。頭結點的數(shù)據(jù)域可以不存儲任何信息(或鏈表長度等信息)。,單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。 例1、線性表L=(bat，

35、cat，eat，fat，hat) 其帶頭結點的單鏈表的邏輯狀態(tài)和物理存儲方式如圖2-3所示。,1 結點的描述與實現(xiàn) C語言中用帶指針的結構體類型來描述 typedef struct Lnode ElemType data; /*數(shù)據(jù)域，保存結點的值 */ struct Lnode *next; /*指針域*/ LNode; /*結點的類型 */ 2 結點的實現(xiàn) 結點是通過動態(tài)分配和釋放來的實現(xiàn)，即需要時分配，不需要時釋放。實現(xiàn)時是分別使用C語言提供的標準函數(shù)：malloc() ，realloc()，sizeof() ，free() 。,動態(tài)分配 p=(LNode*)malloc(sizeof(

36、LNode); 函數(shù)malloc分配了一個類型為LNode的結點變量的空間，并將其首地址放入指針變量p中。 動態(tài)釋放 free(p) ; 系統(tǒng)回收由指針變量p所指向的內存區(qū)。P必須是最近一次調用malloc函數(shù)時的返回值。 3 最常用的基本操作及其示意圖, 結點的賦值 LNode *p; p=(LNode*)malloc(sizeof(LNode); p-data=20; p-next=NULL ;, 常見的指針操作,2.3.2 單線性鏈式的基本操作,1 建立單鏈表 假設線性表中結點的數(shù)據(jù)類型是整型，以32767作為結束標志。動態(tài)地建立單鏈表的常用方法有如下兩種：頭插入法，尾插入法。 頭插入法

37、建表 從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。即每次插入的結點都作為鏈表的第一個結點。,算法描述 LNode *create_LinkList(void) /* 頭插入法創(chuàng)建單鏈表,鏈表的頭結點head作為返回值 */ int data ; LNode *head, *p; head= (LNode *) malloc( sizeof(LNode); head-next=NULL; /* 創(chuàng)建鏈表的表頭結點head */ while (1) scanf(“%d”, /* 數(shù)據(jù)域賦值 */,pnext=

38、headnext ; headnext=p ; /* 鉤鏈，新創(chuàng)建的結點總是作為第一個結點 */ return (head); (2) 尾插入法建表 頭插入法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結點插入到當前鏈表的表尾，使其成為當前鏈表的尾結點。,算法描述 LNode *create_LinkList(void) /* 尾插入法創(chuàng)建單鏈表,鏈表的頭結點head作為返回值 */ int data ; LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode); p

39、-next=NULL; /* 創(chuàng)建單鏈表的表頭結點head */ while (1) scanf(“%d”,/*鉤鏈，新創(chuàng)建的結點總是作為最后一個結點*/ return (head); 無論是哪種插入方法，如果要插入建立的單線性鏈表的結點是n個，算法的時間復雜度均為O(n)。 對于單鏈表，無論是哪種操作，只要涉及到鉤鏈(或重新鉤鏈)，如果沒有明確給出直接后繼，鉤鏈(或重新鉤鏈)的次序必須是“先右后左”。,2 單鏈表的查找 (1) 按序號查找 取單鏈表中的第i個元素。 對于單鏈表，不能象順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭結點出發(fā)，沿鏈域next逐個結點往下搜索，直到搜索到第i個結

40、點為止。因此，鏈表不是隨機存取結構。 設單鏈表的長度為n，要查找表中第i個結點，僅當1in時，i的值是合法的。,算法描述 ElemType Get_Elem(LNode *L ， int i) int j ; LNode *p; p=L-next; j=1; /* 使p指向第一個結點 */ while (p!=NULL i1,n：i-1次；in：n次。 時間復雜度: O(n)。,(2) 按值查找 按值查找是在鏈表中，查找是否有結點值等于給定值key的結點? 若有，則返回首次找到的值為key的結點的存儲位置；否則返回NULL。查找時從開始結點出發(fā)，沿鏈表逐個將結點的值和給定值key作比較。,算法

41、描述 LNode *Locate_Node(LNode *L，int key) /* 在以L為頭結點的單鏈表中查找值為key的第一個結點 */ LNode *p=Lnext; while ( p!=NULL 算法的執(zhí)行與形參key有關，平均時間復雜度為O(n)。,3 單鏈表的插入 插入運算是將值為e的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結點p，然后生成一個數(shù)據(jù)域為e的新結點q，q結點作為p的直接后繼結點。 算法描述 void Insert_LNode(LNode *L，int i，ElemType e) /* 在以L為頭結點的單鏈表的

42、第i個位置插入值為e的結點 */ int j=0; LNode *p，*q; p=Lnext ; while ( p!=NULL ,if (j!=i-1) printf(“i太大或i為0!n ”); else q=(LNode *)malloc(sizeof(LNode); qdata=e; qnext=pnext; pnext=q; 設鏈表的長度為n，合法的插入位置是1in。算法的時間主要耗費移動指針p上，故時間復雜度亦為O(n)。,4 單鏈表的刪除 按序號刪除 刪除單鏈表中的第i個結點。 為了刪除第i個結點ai，必須找到結點的存儲地址。該存儲地址是在其直接前趨結點ai-1的next域中，因

43、此，必須首先找到ai-1的存儲位置p，然后令pnext指向ai的直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間，將其歸還給“存儲池”。 設單鏈表長度為n，則刪去第i個結點僅當1in時是合法的。則當i=n+1時，雖然被刪結點不存在，但其前趨結點卻存在，是終端結點。故判斷條件之一是pnext!=NULL。顯然此算法的時間復雜度也是O(n)。,算法描述 void Delete_LinkList(LNode *L， int i) /* 刪除以L為頭結點的單鏈表中的第i個結點 */ int j=1; LNode *p，*q; p=L; q=L-next; while ( p-next!=NUL

44、L , 按值刪除 刪除單鏈表中值為key的第一個結點。 與按值查找相類似，首先要查找值為key的結點是否存在? 若存在，則刪除；否則返回NULL。,算法描述 void Delete_LinkList(LNode *L，int key) /* 刪除以L為頭結點的單鏈表中值為key的第一個結點 */ LNode *p=L, *q=Lnext; while ( q!=NULL ,算法的執(zhí)行與形參key有關，平均時間復雜度為O(n)。 從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無需移動結點，僅需修改指針。解決了順序表的插入或刪除操作需要移動大量元素的問題。 變形之一： 刪除單鏈表中值為key的所

45、有結點。 與按值查找相類似，但比前面的算法更簡單。 基本思想：從單鏈表的第一個結點開始，對每個結點進行檢查，若結點的值為key，則刪除之，然后檢查下一個結點，直到所有的結點都檢查。,算法描述 void Delete_LinkList_Node(LNode *L，int key) /* 刪除以L為頭結點的單鏈表中值為key的第一個結點 */ LNode *p=L, *q=Lnext; while ( q!=NULL) if (qdata=key) p-next=q-next; free(q); q=p-next; else p=q; q=qnext; ,變形之二： 刪除單鏈表中所有值重復的結點，

46、使得所有結點的值都不相同。 與按值查找相類似，但比前面的算法更復雜。 基本思想：從單鏈表的第一個結點開始，對每個結點進行檢查：檢查鏈表中該結點的所有后繼結點，只要有值和該結點的值相同，則刪除之；然后檢查下一個結點，直到所有的結點都檢查。,算法描述 void Delete_Node_value(LNode *L) /* 刪除以L為頭結點的單鏈表中所有值相同的結點 */ LNode *p=L-next, *q, *ptr; while ( p!=NULL) /* 檢查鏈表中所有結點 */ *q=p, *ptr=pnext; /* 檢查結點p的所有后繼結點ptr */ while (ptr!=NUL

47、L) if (ptrdata=p-data) q-next=ptr-next; free(ptr); ptr=q-next; else q=ptr; ptr=ptrnext; ,p=p-next ; ,5 單鏈表的合并 設有兩個有序的單鏈表，它們的頭指針分別是La 、 Lb，將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2-4所示。,合并了值為-7，-2的結點后示意圖如圖2-5所示。,算法說明 算法中pa ，pb分別是待考察的兩個鏈表的當前結點，pc是合并過程中合并的鏈表的最后一個結點。,算法描述 LNode *Merge_LinkList(LNode *La， LNode *Lb)

48、 /* 合并以La, Lb為頭結點的兩個有序單鏈表 */ LNode *Lc, *pa , *pb , *pc, *ptr ; Lc=La ; pc=La ; pa=La-next ; pb=Lb-next ; while (pa!=NULL /* 將pa所指的結點合并，pa指向下一個結點 */,if (pa-data=pb-data) pc-next=pa ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; free(ptr) ; /* 將pa所指的結點合并，pb所指結點刪除 */ if (pa!=NULL) pc-next=pa ; else pc-n

49、ext=pb ; /*將剩余的結點鏈上*/ free(Lb) ; return(Lc) ; 算法分析 若La ，Lb兩個鏈表的長度分別是m，n，則鏈表合并的時間復雜度為O(m+n) 。,2.3.3 循環(huán)鏈表,循環(huán)鏈表(Circular Linked List)：是一種頭尾相接的鏈表。其特點是最后一個結點的指針域指向鏈表的頭結點，整個鏈表的指針域鏈接成一個環(huán)。 從循環(huán)鏈表的任意一個結點出發(fā)都可以找到鏈表中的其它結點，使得表處理更加方便靈活。 圖2-6是帶頭結點的單循環(huán)鏈表的示意圖。,空表,循環(huán)鏈表的操作 對于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算

50、法基礎上作以下簡單修改： 判斷是否是空鏈表：head-next=head ; 判斷是否是表尾結點：p-next=head ;,2.4 雙向鏈表,雙向鏈表(Double Linked List) :指的是構成鏈表的每個結點中設立兩個指針域：一個指向其直接前趨的指針域prior，一個指向其直接后繼的指針域next。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。 和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運算變得方便。 將頭結點和尾結點鏈接起來也能構成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。 雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。,1 雙向鏈表的結點及其類型定義 雙向鏈表的結點

51、的類型定義如下。其結點形式如圖2-7所示，帶頭結點的雙向鏈表的形式如圖2-8所示。 typedef struct Dulnode ElemType data ; struct Dulnode *prior , *next ; DulNode ;,雙向鏈表結構具有對稱性，設p指向雙向鏈表中的某一結點，則其對稱性可用下式描述： (p-prior)-next=p=(p-next)-prior ; 結點p的存儲位置存放在其直接前趨結點p-prior的直接后繼指針域中，同時也存放在其直接后繼結點p-next的直接前趨指針域中。 2 雙向鏈表的基本操作 (1) 雙向鏈表的插入 將值為e的結點插入雙向鏈表中

52、。插入前后鏈表的變化如圖2-9所示。, 插入時僅僅指出直接前驅結點，鉤鏈時必須注意先后次序是： “先右后左” 。部分語句組如下： S=(DulNode *)malloc(sizeof(DulNode); S-data=e; S-next=p-next; p-next-prior=S; p-next=S; S-prior=p; /* 鉤鏈次序非常重要 */ 插入時同時指出直接前驅結點p和直接后繼結點q，鉤鏈時無須注意先后次序。部分語句組如下： S=(DulNode *)malloc(sizeof(DulNode); S-data=e; p-next=S; S-next=q; S-prior=p;

53、 q-prior=S;,(2) 雙向鏈表的結點刪除 設要刪除的結點為p ，刪除時可以不引入新的輔助指針變量，可以直接先斷鏈，再釋放結點。部分語句組如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 注意： 與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時修改兩個方向上的指針域的指向。,2.5 一元多項式的表示和相加,1 一元多項式的表示 一元多項式 p(x)=p0+p1x+p2x2+ +pnxn ，由n+1個系數(shù)唯一確定。則在計算機中可用線性表(p0 ，p1 ，p2 ， ，pn )表示。既然是線性表，就可以用順序表和鏈

54、表來實現(xiàn)。兩種不同實現(xiàn)方式的元素類型定義如下：,(1) 順序存儲表示的類型 typedef struct float coef; /*系數(shù)部分*/ int expn; /*指數(shù)部分*/ ElemType ;,(2) 鏈式存儲表示的類型 typedef struct ploy float coef ; /*系數(shù)部分*/ int expn ; /*指數(shù)部分*/ struct ploy *next ; Ploy ;,2 一元多項式的相加 不失一般性，設有兩個一元多項式： P(x)=p0+p1x+p2x2+ +pnxn ， Q(x)=q0+q1x+q2x2+ +qmxm (mn) R(x)=P(x)+

55、 Q(x) R(x)由線性表R(p0+q0) ，(p1+q1) ，(p2+q2) ， ，(pm+qm) ， ， pn)唯一表示。, 順序存儲表示的相加 線性表的定義 typedef struct ElemType aMAX_SIZE ; int length ; Sqlist ; 用順序表示的相加非常簡單。訪問第5項可直接訪問：L.a4.coef ， L.a4.expn (2) 鏈式存儲表示的相加 當采用鏈式存儲表示時，根據(jù)結點類型定義，凡是系數(shù)為0的項不在鏈表中出現(xiàn)，從而可以大大減少鏈表的長度。,一元多項式相加的實質是： 指數(shù)不同： 是鏈表的合并。 指數(shù)相同： 系數(shù)相加，和為0，去掉結點，和

56、不為0，修改結點的系數(shù)域。 算法之一： 就在原來兩個多項式鏈表的基礎上進行相加，相加后原來兩個多項式鏈表就不在存在。當然再要對原來兩個多項式進行其它操作就不允許了。,算法描述 Ploy *add_ploy(ploy *La， ploy *Lb) /* 將以La ，Lb為頭指針表示的一元多項式相加 */ ploy *Lc , *pc , *pa , *pb ,*ptr ; float x ; Lc=pc=La ; pa=La-next ; pb=Lb-next ; while (pa!=NULL /* 將pb所指的結點合并，pb指向下一個結點 */,else x=pa-coef+pb-coef

57、; if (abs(x)next ; free(ptr) ; ptr=pb ; pb=pb-next ; free(ptr) ; else /* 如果系數(shù)和不為0，修改其中一個結點的系數(shù)域，刪除另一個結點 */ pc-next=pa ; pa-coef=x ; pc=pa ; pa=pa-next ; ptr=pb ; pb=pb-next ; free(pb) ; , /* end of while */ if (pa=NULL) pc-next=pb ; else pc-next=pa ; return (Lc) ; ,算法之二： 對兩個多項式鏈表進行相加，生成一個新的相加后的結果多項式鏈

58、表，原來兩個多項式鏈表依然存在，不發(fā)生任何改變，如果要再對原來兩個多項式進行其它操作也不影響。,算法描述 Ploy *add_ploy(ploy *La， ploy *Lb) /* 將以La ，Lb為頭指針表示的一元多項式相加，生成一個新的結果多項式 */ ploy *Lc , *pc , *pa , *pb , *p ; float x ; Lc=pc=(ploy *)malloc(sizeof(ploy) ; pa=La-next ; pb=Lb-next ; while (pa!=NULL,/* 生成一個新的結果結點并賦值 */ pc-next=p ; pc=p ; pa=pa-next

59、 ; /* 生成的結點插入到結果鏈表的最后，pa指向下一個結點 */ if (pa-expnpb-expn) p=(ploy *)malloc(sizeof(ploy) ; p-coef=pb-coef ; p-expn=pb-expn ; p-next=NULL ; /* 生成一個新的結果結點并賦值 */ pc-next=p ; pc=p ; pb=pb-next ; /* 生成的結點插入到結果鏈表的最后，pb指向下一個結點 */,if (pa-expn=pb-expn) x=pa-coef+pb-coef ; if (abs(x)next ; pb=pb-next ; else /* 若系

60、數(shù)和不為0，生成的結點插入到結果鏈表的最后， pa, pb分別直接后繼結點 */ p=(ploy *)malloc(sizeof(ploy) ; p-coef=x ; p-expn=pb-expn ; p-next=NULL ; /* 生成一個新的結果結點并賦值 */ pc-next=p ; pc=p ; pa=pa-next ; pb=pb-next ;, /* end of while */ if (pb!=NULL) while(pb!=NULL) p=(ploy *)malloc(sizeof(ploy) ; p-coef=pb-coef ; p-expn=pb-expn ; p-ne

61、xt=NULL ; /* 生成一個新的結果結點并賦值 */ pc-next=p ; pc=p ; pb=pb-next ; ,if (pa!=NULL) while(pa!=NULL) p=(ploy *)malloc(sizeof(ploy) ; p-coef=pb-coef ; p-expn=pa-expn ; p-next=NULL ; /* 生成一個新的結果結點并賦值 */ pc-next=p ; pc=p ; pa=pa-next ; return (Lc) ; ,習 題 二,1 簡述下列術語：線性表，順序表，鏈表。 2 何時選用順序表，何時選用鏈表作為線性表的存儲結構合適?各自的主

62、要優(yōu)缺點是什么? 3 在順序表中插入和刪除一個結點平均需要移動多少個結點?具體的移動次數(shù)取決于哪兩個因素? 4 鏈表所表示的元素是否有序?如有序，則有序性體現(xiàn)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的?有序表的有序性又如何理解? 5 設順序表L是遞增有序表，試寫一算法，將x插入到L中并使L仍是遞增有序表。,6 寫一求單鏈表的結點數(shù)目ListLength(L)的算法。 7 寫一算法將單鏈表中值重復的結點刪除，使所得的結果鏈表中所有結點的值均不相同。 8 寫一算法從一給定的向量A刪除值在x到y(tǒng)(xy)之間的所有元素(注意：x和y是給定的參數(shù)，可以和表中的元素相同，也可以不同)。 9 設A和

63、B是兩個按元素值遞增有序的單鏈表，寫一算法將A和B歸并為按按元素值遞減有序的單鏈表C，試分析算法的時間復雜度。,第3章 棧和隊列,棧和隊列是兩種應用非常廣泛的數(shù)據(jù)結構，它們都來自線性表數(shù)據(jù)結構，都是“操作受限”的線性表。 棧在計算機的實現(xiàn)有多種方式： 硬堆棧：利用CPU中的某些寄存器組或類似的硬件或使用內存的特殊區(qū)域來實現(xiàn)。這類堆棧容量有限，但速度很快； 軟堆棧：這類堆棧主要在內存中實現(xiàn)。堆棧容量可以達到很大。在實現(xiàn)方式上，又有動態(tài)方式和靜態(tài)方式兩種。 本章將討論棧和隊列的基本概念、存儲結構、基本操作以及這些操作的具體實現(xiàn)。,3.1 棧,3.1.1 棧的基本概念,1 棧的概念 棧(Stack)

64、：是限制在表的一端進行插入和刪除操作的線性表。又稱為后進先出LIFO (Last In First Out)或先進后出FILO (First In Last Out)線性表。 棧頂(Top)：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。 棧底(Bottom)：是固定端，又稱為表頭。 空棧：當表中沒有元素時稱為空棧。,設棧S=(a1，a2，an)，則a1稱為棧底元素，an為棧頂元素，如圖3-1所示。 棧中元素按a1，a2，an的次序進棧，退棧的第一個元素應為棧頂元素。即棧的修改是按后進先出的原則進行的。,2 棧的抽象數(shù)據(jù)類型定義 ADT Stack 數(shù)據(jù)對象：D

65、 = ai|aiElemSet, i=1,2,n，n0 數(shù)據(jù)關系：R =|ai-1，aiD, i=2,3,n 基本操作：初始化、進棧、出棧、取棧頂元素等 ADT Stack,棧的順序存儲結構簡稱為順序棧，和線性表相類似，用一維數(shù)組來存儲棧。根據(jù)數(shù)組是否可以根據(jù)需要增大，又可分為靜態(tài)順序棧和動態(tài)順序棧。 靜態(tài)順序棧實現(xiàn)簡單，但不能根據(jù)需要增大棧的存儲空間； 動態(tài)順序?？梢愿鶕?jù)需要增大棧的存儲空間，但實現(xiàn)稍為復雜。,3.1.2 棧的順序存儲表示,采用動態(tài)一維數(shù)組來存儲棧。所謂動態(tài)，指的是棧的大小可以根據(jù)需要增加。 用bottom表示棧底指針，棧底固定不變的；棧頂則隨著進棧和退棧操作而變化。用top(稱為棧頂指針)指示當前棧頂位置