數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏完整版ppt課件.ppt

算法與數(shù)據(jù)結(jié)構(gòu) 教材 數(shù)據(jù)結(jié)構(gòu) C語言版 嚴(yán)蔚敏 吳偉民編著 清華大學(xué)出版社 參考文獻(xiàn) 1 數(shù)據(jù)結(jié)構(gòu) 張選平 雷詠梅編 嚴(yán)蔚敏審 機械工業(yè)出版社 2 數(shù)據(jù)結(jié)構(gòu)與算法分析 CliffordA Shaffer著 張銘 劉曉丹譯 電子工業(yè)出版社 3 數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析 C語實言版 李春葆 清華大學(xué)出版社 4 數(shù)據(jù)結(jié)構(gòu)與算法 夏克儉編著 國防工業(yè)出版社 第1章緒論 目前 計算機已深入到社會生活的各個領(lǐng)域 其應(yīng)用已不再僅僅局限于科學(xué)計算 而更多的是用于控制 管理及數(shù)據(jù)處理等非數(shù)值計算領(lǐng)域 計算機是一門研究用計算機進(jìn)行信息表示和處理的科學(xué) 這里面涉及到兩個問題 信息的表示 信息的處理 信息的表示和組織又直接關(guān)系到處理信息的程序的效率 隨著應(yīng)用問題的不斷復(fù)雜 導(dǎo)致信息量劇增與信息范圍的拓寬 使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大 結(jié)構(gòu)又相當(dāng)復(fù)雜 因此 必須分析待處理問題中的對象的特征及各對象之間存在的關(guān)系 這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題 編寫解決實際問題的程序的一般過程 如何用數(shù)據(jù)形式描述問題 即由問題抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型 問題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系 如何在計算機中存儲數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系 處理問題時需要對數(shù)據(jù)作何種運算 所編寫的程序的性能是否良好 上面所列舉的問題基本上由數(shù)據(jù)結(jié)構(gòu)這門課程來回答 計算機求解問題的一般步驟 1 1數(shù)據(jù)結(jié)構(gòu)及其概念 算法與數(shù)據(jù)結(jié)構(gòu) 是計算機科學(xué)中的一門綜合性專業(yè)基礎(chǔ)課 是介于數(shù)學(xué) 計算機硬件 計算機軟件三者之間的一門核心課程 不僅是一般程序設(shè)計的基礎(chǔ) 而且是設(shè)計和實現(xiàn)編譯程序 操作系統(tǒng) 數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ) 1 1 1數(shù)據(jù)結(jié)構(gòu)的例子 例1 電話號碼查詢系統(tǒng)設(shè)有一個電話號碼薄 它記錄了N個人的名字和其相應(yīng)的電話號碼 假定按如下形式安排 a1 b1 a2 b2 an bn 其中ai bi i 1 2 n 分別表示某人的名字和電話號碼 本問題是一種典型的表格問題 如表1 1 數(shù)據(jù)與數(shù)據(jù)成簡單的一對一的線性關(guān)系 表1 1線性表結(jié)構(gòu) 例2 磁盤目錄文件系統(tǒng)磁盤根目錄下有很多子目錄及文件 每個子目錄里又可以包含多個子目錄及文件 但每個子目錄只有一個父目錄 依此類推 本問題是一種典型的樹型結(jié)構(gòu)問題 如圖1 1 數(shù)據(jù)與數(shù)據(jù)成一對多的關(guān)系 是一種典型的非線性關(guān)系結(jié)構(gòu) 樹形結(jié)構(gòu) 圖1 1樹形結(jié)構(gòu) 例3 交通網(wǎng)絡(luò)圖從一個地方到另外一個地方可以有多條路徑 本問題是一種典型的網(wǎng)狀結(jié)構(gòu)問題 數(shù)據(jù)與數(shù)據(jù)成多對多的關(guān)系 是一種非線性關(guān)系結(jié)構(gòu) 數(shù)據(jù) Data 是客觀事物的符號表示 在計算機科學(xué)中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱 數(shù)據(jù)元素 DataElement 是數(shù)據(jù)的基本單位 在程序中通常作為一個整體來進(jìn)行考慮和處理 一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項 DataItem 組成 數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位 數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述 數(shù)據(jù)對象 DataObject 是性質(zhì)相同的數(shù)據(jù)元素的集合 是數(shù)據(jù)的一個子集 如字符集合C A B C 1 1 2基本概念和術(shù)語 數(shù)據(jù)結(jié)構(gòu) DataStructure 是指相互之間具有 存在 一定聯(lián)系 關(guān)系 的數(shù)據(jù)元素的集合 元素之間的相互聯(lián)系 關(guān)系 稱為邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型 如圖1 3所示 集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了 同屬于一個集合 外 沒有其它關(guān)系 線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系 樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系 數(shù)據(jù)結(jié)構(gòu)的形式定義是一個二元組 Data Structure D S 其中 D是數(shù)據(jù)元素的有限集 S是D上關(guān)系的有限集 例2 設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)B K R K k1 k2 k9 R 畫出這邏輯結(jié)構(gòu)的圖示 并確定那些是起點 那些是終點 1 1 3數(shù)據(jù)結(jié)構(gòu)的形式定義 圖1 3四類基本結(jié)構(gòu)圖 1 1 4數(shù)據(jù)結(jié)構(gòu)的存儲方式 數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系 也可以是為處理問題方便而人為定義的關(guān)系 這種自然或人為定義的 關(guān)系 稱為數(shù)據(jù)元素之間的邏輯關(guān)系 相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關(guān)系的表示 元素之間的關(guān)系在計算機中有兩種不同的表示方法 順序表示和非順序表示 由此得出兩種不同的存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 順序存儲結(jié)構(gòu) 用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu) 關(guān)系 鏈?zhǔn)酱鎯Y(jié)構(gòu) 在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針 pointer 用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu) 關(guān)系 例 設(shè)有數(shù)據(jù)集合A 3 0 2 3 5 0 8 5 11 0 兩種不同的存儲結(jié)構(gòu) 順序結(jié)構(gòu) 數(shù)據(jù)元素存放的地址是連續(xù)的 鏈?zhǔn)浇Y(jié)構(gòu) 數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方面 一個算法的設(shè)計取決于所選定的邏輯結(jié)構(gòu) 而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu) 在C語言中 用一維數(shù)組表示順序存儲結(jié)構(gòu) 用結(jié)構(gòu)體類型表示鏈?zhǔn)酱鎯Y(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的三個組成部分 邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間邏輯關(guān)系的描述D S D S 存儲結(jié)構(gòu) 數(shù)據(jù)元素在計算機中的存儲及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu) 數(shù)據(jù)操作 對數(shù)據(jù)要進(jìn)行的運算 本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲結(jié)構(gòu)如圖1 4所示 數(shù)據(jù)類型 DataType 指的是一個值的集合和定義在該值集上的一組操作的總稱 數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念 在C語言中數(shù)據(jù)類型有 基本類型和構(gòu)造類型 數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型 也不同于數(shù)據(jù)對象 它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象 而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系 1 1 5數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu)的主要運算包括 建立 Create 一個數(shù)據(jù)結(jié)構(gòu) 消除 Destroy 一個數(shù)據(jù)結(jié)構(gòu) 從一個數(shù)據(jù)結(jié)構(gòu)中刪除 Delete 一個數(shù)據(jù)元素 把一個數(shù)據(jù)元素插入 Insert 到一個數(shù)據(jù)結(jié)構(gòu)中 對一個數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問 Access 對一個數(shù)據(jù)結(jié)構(gòu) 中的數(shù)據(jù)元素 進(jìn)行修改 Modify 對一個數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序 Sort 對一個數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找 Search 1 1 6數(shù)據(jù)結(jié)構(gòu)的運算 抽象數(shù)據(jù)類型 AbstractDataType 簡稱ADT 是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作 ADT的定義僅是一組邏輯特性描述 與其在計算機內(nèi)的表示和實現(xiàn)無關(guān) 因此 不論ADT的內(nèi)部結(jié)構(gòu)如何變化 只要其數(shù)學(xué)特性不變 都不影響其外部使用 ADT的形式化定義是三元組 ADT D S P 其中 D是數(shù)據(jù)對象 S是D上的關(guān)系集 P是對D的基本操作集 1 2抽象數(shù)據(jù)類型 ADT的一般定義形式是 ADT 數(shù)據(jù)對象 數(shù)據(jù)關(guān)系 基本操作 ADT其中數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述 基本操作的定義是 初始條件 操作結(jié)果 初始條件 描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件 若不滿足 則操作失敗 返回相應(yīng)的出錯信息 操作結(jié)果 描述操作正常完成之后 數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果 1 3 1算法算法 Algorithm 是對特定問題求解方法 步驟 的一種描述 是指令的有限序列 其中每一條指令表示一個或多個操作 算法具有以下五個特性 有窮性 一個算法必須總是在執(zhí)行有窮步之后結(jié)束 且每一步都在有窮時間內(nèi)完成 確定性 算法中每一條指令必須有確切的含義 不存在二義性 且算法只有一個入口和一個出口 可行性 一個算法是能行的 即算法描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn) 1 3算法分析初步 輸入 一個算法有零個或多個輸入 這些輸入取自于某個特定的對象集合 輸出 一個算法有一個或多個輸出 這些輸出是同輸入有著某些特定關(guān)系的量 一個算法可以用多種方法描述 主要有 使用自然語言描述 使用形式語言描述 使用計算機程序設(shè)計語言描述 算法和程序是兩個不同的概念 一個計算機程序是對一個算法使用某種程序設(shè)計語言的具體實現(xiàn) 算法必須可終止意味著不是所有的計算機程序都是算法 在本門課程的學(xué)習(xí) 作業(yè)練習(xí) 上機實踐等環(huán)節(jié) 算法都用C語言來描述 在上機實踐時 為了檢查算法是否正確 應(yīng)編寫成完整的C語言程序 評價一個好的算法有以下幾個標(biāo)準(zhǔn) 正確性 Correctness 算法應(yīng)滿足具體問題的需求 可讀性 Readability 算法應(yīng)容易供人閱讀和交流 可讀性好的算法有助于對算法的理解和修改 健壯性 Robustness 算法應(yīng)具有容錯處理 當(dāng)輸入非法或錯誤數(shù)據(jù)時 算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理 而不會產(chǎn)生莫名其妙的輸出結(jié)果 通用性 Generality 算法應(yīng)具有一般性 即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立 1 3 2算法設(shè)計的要求 算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量 其方法通常有兩種 事后統(tǒng)計 計算機內(nèi)部進(jìn)行執(zhí)行時間和實際占用空間的統(tǒng)計 問題 必須先運行依據(jù)算法編制的程序 依賴軟硬件環(huán)境 容易掩蓋算法本身的優(yōu)劣 沒有實際價值 事前分析 求出該算法的一個時間界限函數(shù) 1 3 3算法效率的度量 效率與存儲量需求 效率指的是算法執(zhí)行的時間 存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間 一般地 這兩者與問題的規(guī)模有關(guān) 與此相關(guān)的因素有 依據(jù)算法選用何種策略 問題的規(guī)模 程序設(shè)計的語言 編譯程序所產(chǎn)生的機器代碼的質(zhì)量 機器執(zhí)行指令的速度 撇開軟硬件等有關(guān)部門因素 可以認(rèn)為一個特定算法 運行工作量 的大小 只依賴于問題的規(guī)模 通常用n表示 或者說 它是問題規(guī)模的函數(shù) 算法分析應(yīng)用舉例 算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù) 其時間量度記作T n O f n 稱作算法的漸近時間復(fù)雜度 AsymptoticTimecomplexity 簡稱時間復(fù)雜度 一般地 常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度 重復(fù)執(zhí)行的次數(shù) 來表示 O 的定義 若f n 是正整數(shù)n的一個函數(shù) 則O f n 表示 M 0 使得當(dāng)n n0時 f n M f n0 表示時間復(fù)雜度的階有 O 1 常量時間階O n 線性時間階O n 對數(shù)時間階O n n 線性對數(shù)時間階 O nk k 2 k次方時間階例 兩個n階方陣的乘法for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j 由于是一個三重循環(huán) 每個循環(huán)從1到n 則總次數(shù)為 n n n n3時間復(fù)雜度為T n O n3 例 x s 0 將x自增看成是基本操作 則語句頻度為 即時間復(fù)雜度為 1 如果將s 0也看成是基本操作 則語句頻度為 其時間復(fù)雜度仍為 1 即常量階 例 for i 1 i n i x s x 語句頻度為 2n 其時間復(fù)雜度為 O n 即為線性階 例 for i 1 i n i for j 1 j n j x s x 語句頻度為 2n2 其時間復(fù)雜度為 O n2 即為平方階 定理 若A n amnm am 1nm 1 a1n a0是一個m次多項式 則A n O nm 例 for i 2 i n i for j 2 j i 1 j x a i j x 語句頻度為 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 時間復(fù)雜度為O n2 即此算法的時間復(fù)雜度為平方階 一個算法時間為O 1 的算法 它的基本運算執(zhí)行的次數(shù)是固定的 因此 總的時間由一個常數(shù) 即零次多項式 來限界 而一個時間為O n2 的算法則由一個二次多項式來限界 以下六種計算算法時間的多項式是最常用的 其關(guān)系為 O 1 O n O n O n n O n2 O n3 指數(shù)時間的關(guān)系為 O 2n O n O nn 當(dāng)n取得很大時 指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊 因此 只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法 那就取得了一個偉大的成就 有的情況下 算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同 例1 素數(shù)的判斷算法 Voidprime intn n是一個正整數(shù) inti 2 while n i 0 嵌套的最深層語句是i 其頻度由條件 n i 0 i 1 0 sqrt n 決定 顯然i 1 0 sqrt n 時間復(fù)雜度O n1 2 例2 冒泡排序法 Voidbubble sort inta intn change false for i n 1 change TURE i 1 最好情況 0次最壞情況 1 2 3 n 1 n n 1 2平均時間復(fù)雜度為 O n2 1 3 4算法的空間分析 空間復(fù)雜度 Spacecomplexity 是指算法編寫成程序后 在計算機中運行時所需存儲空間大小的度量 記作 S n O f n 其中 n為問題的規(guī)模 或大小 該存儲空間一般包括三個方面 指令常數(shù)變量所占用的存儲空間 輸入數(shù)據(jù)所占用的存儲空間 輔助 存儲 空間 一般地 算法的空間復(fù)雜度指的是輔助空間 一維數(shù)組a n 空間復(fù)雜度O n 二維數(shù)組a n m 空間復(fù)雜度O n m 習(xí)題一 1簡要回答術(shù)語 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)類型 2數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu) 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么 3數(shù)據(jù)結(jié)構(gòu)的主要運算包括哪些 4算法分析的目的是什么 算法分析的主要方面是什么 5分析以下程序段的時間復(fù)雜度 請說明分析的理由或原因 第2章線性表 線性結(jié)構(gòu)是最常用 最簡單的一種數(shù)據(jù)結(jié)構(gòu) 而線性表是一種典型的線性結(jié)構(gòu) 其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的 在這種結(jié)構(gòu)中 存在一個唯一的被稱為 第一個 的數(shù)據(jù)元素 存在一個唯一的被稱為 最后一個 的數(shù)據(jù)元素 除第一個元素外 每個元素均有唯一一個直接前驅(qū) 除最后一個元素外 每個元素均有唯一一個直接后繼 2 1線性表的邏輯結(jié)構(gòu) 線性表 LinearList 是由n n 0 個數(shù)據(jù)元素 結(jié)點 a1 a2 an組成的有限序列 該序列中的所有結(jié)點具有相同的數(shù)據(jù)類型 其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度 當(dāng)n 0時 稱為空表 當(dāng)n 0時 將非空的線性表記作 a1 a2 an a1稱為線性表的第一個 首 結(jié)點 an稱為線性表的最后一個 尾 結(jié)點 2 1 1線性表的定義 a1 a2 ai 1都是ai 2 i n 的前驅(qū) 其中ai 1是ai的直接前驅(qū) ai 1 ai 2 an都是ai 1 i n 1 的后繼 其中ai 1是ai的直接后繼 2 1 2線性表的邏輯結(jié)構(gòu) 線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同 在線性表的定義中 只不過是一個抽象的表示符號 線性表中的結(jié)點可以是單值元素 每個元素只有一個數(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 線性表中的結(jié)點可以是記錄型元素 每個元素含有多個數(shù)據(jù)項 每個項稱為結(jié)點的一個域 每個元素有一個可以唯一標(biāo)識每個結(jié)點的數(shù)據(jù)項組 稱為關(guān)鍵字 例4 某校2001級同學(xué)的基本情況 2001414101 張里戶 男 06 24 1983 2001414102 張化司 男 08 12 1984 2001414102 李利辣 女 08 12 1984 若線性表中的結(jié)點是按值 或按關(guān)鍵字值 由小到大 或由大到小 排列的 稱線性表是有序的 2 1 3線性表的抽象數(shù)據(jù)類型定義 ADTList 數(shù)據(jù)對象 D ai ai ElemSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R ai 1 ai D i 2 3 n 基本操作 InitList L 操作結(jié)果 構(gòu)造一個空的線性表L 線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu) 其長度可根據(jù)需要增長或縮短 對線性表的數(shù)據(jù)元素可以訪問 插入和刪除 ListLength L 初始條件 線性表L已存在 操作結(jié)果 若L為空表 則返回TRUE 否則返回FALSE GetElem L i e 初始條件 線性表L已存在 1 i ListLength L 操作結(jié)果 用e返回L中第i個數(shù)據(jù)元素的值 ListInsert L i e 初始條件 線性表L已存在 1 i ListLength L 操作結(jié)果 在線性表L中的第i個位置插入元素e ADTList 2 2線性表的順序存儲 順序存儲 把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里 用這種方法存儲的線性表簡稱順序表 順序存儲的線性表的特點 線性表的邏輯順序與物理順序一致 數(shù)據(jù)元素之間的關(guān)系是以元素在計算機內(nèi) 物理位置相鄰 來體現(xiàn) 設(shè)有非空的線性表 a1 a2 an 順序存儲如圖2 1所示 2 2 1線性表的順序存儲結(jié)構(gòu) 在具體的機器環(huán)境下 設(shè)線性表的每個元素需占用l個存儲單元 以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置 則線性表中第i 1個數(shù)據(jù)元素的存儲位置LOC ai 1 和第i個數(shù)據(jù)元素的存儲位置LOC ai 之間滿足下列關(guān)系 LOC ai 1 LOC ai l線性表的第i個數(shù)據(jù)元素ai的存儲位置為 LOC ai LOC a1 i 1 l 在高級語言 如C語言 環(huán)境下 數(shù)組具有隨機存取的特性 因此 借助數(shù)組來描述順序表 除了用數(shù)組來存儲線性表的元素之外 順序表還應(yīng)該有表示線性表的長度屬性 所以用結(jié)構(gòu)類型來定義順序表類型 defineOK1 defineERROR 1 defineMAX SIZE100typedefintStatus typedefintElemType typedefstructsqlist ElemTypeElem array MAX SIZE intlength SqList 2 2 2順序表的基本操作 順序存儲結(jié)構(gòu)中 很容易實現(xiàn)線性表的一些操作 初始化 賦值 查找 修改 插入 刪除 求長度等 以下將對幾種主要的操作進(jìn)行討論 1順序線性表初始化StatusInit SqList SqList L L elem array ElemType malloc MAX SIZE sizeof ElemType if L elem array returnERROR else L length 0 returnOK 2順序線性表的插入在線性表L a1 ai 1 ai ai 1 an 中的第i 1 i n 個位置上插入一個新結(jié)點e 使其成為線性表 L a1 ai 1 e ai ai 1 an 實現(xiàn)步驟 1 將線性表L中的第i個至第n個結(jié)點后移一個位置 2 將結(jié)點e插入到結(jié)點ai 1之后 3 線性表長度加1 算法描述StatusInsert SqList Sqlist L inti ElemTypee intj if iL length 1 returnERROR if L length MAX SIZE printf 線性表溢出 n returnERROR for j L length 1 j i 1 j L Elem array j 1 L Elem array j i 1位置以后的所有結(jié)點后移 L Elem array i 1 e 在i 1位置插入結(jié)點 L length returnOK 時間復(fù)雜度分析在線性表L中的第i個元素之前插入新結(jié)點 其時間主要耗費在表中結(jié)點的移動操作上 因此 可用結(jié)點的移動來估計算法的時間復(fù)雜度 設(shè)在線性表L中的第i個元素之前插入結(jié)點的概率為Pi 不失一般性 設(shè)各個位置插入是等概率 則Pi 1 n 1 而插入時移動結(jié)點的次數(shù)為n i 1 總的平均移動次數(shù) Einsert pi n i 1 1 i n Einsert n 2 即在順序表上做插入運算 平均要移動表上一半結(jié)點 當(dāng)表長n較大時 算法的效率相當(dāng)?shù)?因此算法的平均時間復(fù)雜度為O n 3順序線性表的刪除在線性表L a1 ai 1 ai ai 1 an 中刪除結(jié)點ai 1 i n 使其成為線性表 L a1 ai 1 ai 1 an 實現(xiàn)步驟 1 將線性表L中的第i 1個至第n個結(jié)點依此向前移動一個位置 2 線性表長度減1 算法描述ElemTypeDelete SqList Sqlist L inti intk ElemTypex if L length 0 printf 線性表L為空 n returnERROR elseif iL length printf 要刪除的數(shù)據(jù)元素不存在 n returnERROR else x L Elem array i 1 保存結(jié)點的值 for k i klength k L Elem array k 1 L Elem array k i位置以后的所有結(jié)點前移 L length return x 時間復(fù)雜度分析刪除線性表L中的第i個元素 其時間主要耗費在表中結(jié)點的移動操作上 因此 可用結(jié)點的移動來估計算法的時間復(fù)雜度 設(shè)在線性表L中刪除第i個元素的概率為Pi 不失一般性 設(shè)刪除各個位置是等概率 則Pi 1 n 而刪除時移動結(jié)點的次數(shù)為n i 則總的平均移動次數(shù) Edelete pi n i 1 i n Edelete n 1 2 即在順序表上做刪除運算 平均要移動表上一半結(jié)點 當(dāng)表長n較大時 算法的效率相當(dāng)?shù)?因此算法的平均時間復(fù)雜度為O n 4順序線性表的查找定位刪除在線性表L a1 a2 an 中刪除值為x的第一個結(jié)點 實現(xiàn)步驟 1 在線性表L查找值為x的第一個數(shù)據(jù)元素 2 將從找到的位置至最后一個結(jié)點依次向前移動一個位置 3 線性表長度減1 算法描述StatusLocate Delete SqList Sqlist L ElemTypex 刪除線性表L中值為x的第一個結(jié)點 inti 0 k while ilength 查找值為x的第一個結(jié)點 if L Elem array i x i else for k i 1 klength k L Elem array k 1 L Elem array k L length break if i L length printf 要刪除的數(shù)據(jù)元素不存在 n returnERROR returnOK 時間復(fù)雜度分析時間主要耗費在數(shù)據(jù)元素的比較和移動操作上 首先 在線性表L中查找值為x的結(jié)點是否存在 其次 若值為x的結(jié)點存在 且在線性表L中的位置為i 則在線性表L中刪除第i個元素 設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi 不失一般性 設(shè)各個位置是等概率 則Pi 1 n 比較的平均次數(shù) Ecompare pi i 1 i n Ecompare n 1 2 刪除時平均移動次數(shù) Edelete pi n i 1 i n Edelete n 1 2 平均時間復(fù)雜度 Ecompare Edelete n 即為O n 2 3線性表的鏈?zhǔn)酱鎯?2 3 1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 鏈?zhǔn)酱鎯?用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素 用這種方法存儲的線性表簡稱線性鏈表 存儲鏈表中結(jié)點的一組任意的存儲單元可以是連續(xù)的 也可以是不連續(xù)的 甚至是零散分布在內(nèi)存中的任意位置上的 鏈表中結(jié)點的邏輯順序和物理順序不一定相同 為了正確表示結(jié)點間的邏輯關(guān)系 在存儲每個結(jié)點值的同時 還必須存儲指示其直接后繼結(jié)點的地址 或位置 稱為指針 pointer 或鏈 link 這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu) 如圖2 2所示 鏈表是通過每個結(jié)點的指針域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的 每一個結(jié)只包含一個指針域的鏈表 稱為單鏈表 為操作方便 總是在鏈表的第一個結(jié)點之前附設(shè)一個頭結(jié)點 頭指針 head指向第一個結(jié)點 頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息 或鏈表長度等信息 單鏈表是由表頭唯一確定 因此單鏈表可以用頭指針的名字來命名 例1 線性表L bat cat eat fat hat 其帶頭結(jié)點的單鏈表的邏輯狀態(tài)和物理存儲方式如圖2 3所示 1結(jié)點的描述與實現(xiàn)C語言中用帶指針的結(jié)構(gòu)體類型來描述typedefstructLnode ElemTypedata 數(shù)據(jù)域 保存結(jié)點的值 structLnode next 指針域 LNode 結(jié)點的類型 2結(jié)點的實現(xiàn)結(jié)點是通過動態(tài)分配和釋放來的實現(xiàn) 即需要時分配 不需要時釋放 實現(xiàn)時是分別使用C語言提供的標(biāo)準(zhǔn)函數(shù) malloc realloc sizeof free 動態(tài)分配p LNode malloc sizeof LNode 函數(shù)malloc分配了一個類型為LNode的結(jié)點變量的空間 并將其首地址放入指針變量p中 動態(tài)釋放free p 系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū) P必須是最近一次調(diào)用malloc函數(shù)時的返回值 3最常用的基本操作及其示意圖 結(jié)點的賦值LNode p p LNode malloc sizeof LNode p data 20 p next NULL 常見的指針操作 2 3 2單線性鏈?zhǔn)降幕静僮?1建立單鏈表假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是整型 以32767作為結(jié)束標(biāo)志 動態(tài)地建立單鏈表的常用方法有如下兩種 頭插入法 尾插入法 頭插入法建表從一個空表開始 重復(fù)讀入數(shù)據(jù) 生成新結(jié)點 將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中 然后將新結(jié)點插入到當(dāng)前鏈表的表頭上 直到讀入結(jié)束標(biāo)志為止 即每次插入的結(jié)點都作為鏈表的第一個結(jié)點 算法描述LNode create LinkList void 頭插入法創(chuàng)建單鏈表 鏈表的頭結(jié)點head作為返回值 intdata LNode head p head LNode malloc sizeof LNode head next NULL 創(chuàng)建鏈表的表頭結(jié)點head while 1 scanf d 數(shù)據(jù)域賦值 p next head next head next p 鉤鏈 新創(chuàng)建的結(jié)點總是作為第一個結(jié)點 return head 2 尾插入法建表頭插入法建立鏈表雖然算法簡單 但生成的鏈表中結(jié)點的次序和輸入的順序相反 若希望二者次序一致 可采用尾插法建表 該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾 使其成為當(dāng)前鏈表的尾結(jié)點 算法描述LNode create LinkList void 尾插入法創(chuàng)建單鏈表 鏈表的頭結(jié)點head作為返回值 intdata LNode head p q head p LNode malloc sizeof LNode p next NULL 創(chuàng)建單鏈表的表頭結(jié)點head while 1 scanf d 鉤鏈 新創(chuàng)建的結(jié)點總是作為最后一個結(jié)點 return head 無論是哪種插入方法 如果要插入建立的單線性鏈表的結(jié)點是n個 算法的時間復(fù)雜度均為O n 對于單鏈表 無論是哪種操作 只要涉及到鉤鏈 或重新鉤鏈 如果沒有明確給出直接后繼 鉤鏈 或重新鉤鏈 的次序必須是 先右后左 2單鏈表的查找 1 按序號查找取單鏈表中的第i個元素 對于單鏈表 不能象順序表中那樣直接按序號i訪問結(jié)點 而只能從鏈表的頭結(jié)點出發(fā) 沿鏈域next逐個結(jié)點往下搜索 直到搜索到第i個結(jié)點為止 因此 鏈表不是隨機存取結(jié)構(gòu) 設(shè)單鏈表的長度為n 要查找表中第i個結(jié)點 僅當(dāng)1 i n時 i的值是合法的 算法描述ElemTypeGet Elem LNode L inti intj LNode p p L next j 1 使p指向第一個結(jié)點 while p NULLi 1 n i 1次 i n n次 時間復(fù)雜度 O n 2 按值查找按值查找是在鏈表中 查找是否有結(jié)點值等于給定值key的結(jié)點 若有 則返回首次找到的值為key的結(jié)點的存儲位置 否則返回NULL 查找時從開始結(jié)點出發(fā) 沿鏈表逐個將結(jié)點的值和給定值key作比較 算法描述LNode Locate Node LNode L intkey 在以L為頭結(jié)點的單鏈表中查找值為key的第一個結(jié)點 LNode p L next while p NULL 算法的執(zhí)行與形參key有關(guān) 平均時間復(fù)雜度為O n 3單鏈表的插入插入運算是將值為e的新結(jié)點插入到表的第i個結(jié)點的位置上 即插入到ai 1與ai之間 因此 必須首先找到ai 1所在的結(jié)點p 然后生成一個數(shù)據(jù)域為e的新結(jié)點q q結(jié)點作為p的直接后繼結(jié)點 算法描述voidInsert LNode LNode L inti ElemTypee 在以L為頭結(jié)點的單鏈表的第i個位置插入值為e的結(jié)點 intj 0 LNode p q p L next while p NULL if j i 1 printf i太大或i為0 n else q LNode malloc sizeof LNode q data e q next p next p next q 設(shè)鏈表的長度為n 合法的插入位置是1 i n 算法的時間主要耗費移動指針p上 故時間復(fù)雜度亦為O n 4單鏈表的刪除 按序號刪除刪除單鏈表中的第i個結(jié)點 為了刪除第i個結(jié)點ai 必須找到結(jié)點的存儲地址 該存儲地址是在其直接前趨結(jié)點ai 1的next域中 因此 必須首先找到ai 1的存儲位置p 然后令p next指向ai的直接后繼結(jié)點 即把ai從鏈上摘下 最后釋放結(jié)點ai的空間 將其歸還給 存儲池 設(shè)單鏈表長度為n 則刪去第i個結(jié)點僅當(dāng)1 i n時是合法的 則當(dāng)i n 1時 雖然被刪結(jié)點不存在 但其前趨結(jié)點卻存在 是終端結(jié)點 故判斷條件之一是p next NULL 顯然此算法的時間復(fù)雜度也是O n 算法描述voidDelete LinkList LNode L inti 刪除以L為頭結(jié)點的單鏈表中的第i個結(jié)點 intj 1 LNode p q p L q L next while p next NULL 按值刪除刪除單鏈表中值為key的第一個結(jié)點 與按值查找相類似 首先要查找值為key的結(jié)點是否存在 若存在 則刪除 否則返回NULL 算法描述voidDelete LinkList LNode L intkey 刪除以L為頭結(jié)點的單鏈表中值為key的第一個結(jié)點 LNode p L q L next while q NULL 算法的執(zhí)行與形參key有關(guān) 平均時間復(fù)雜度為O n 從上面的討論可以看出 鏈表上實現(xiàn)插入和刪除運算 無需移動結(jié)點 僅需修改指針 解決了順序表的插入或刪除操作需要移動大量元素的問題 變形之一 刪除單鏈表中值為key的所有結(jié)點 與按值查找相類似 但比前面的算法更簡單 基本思想 從單鏈表的第一個結(jié)點開始 對每個結(jié)點進(jìn)行檢查 若結(jié)點的值為key 則刪除之 然后檢查下一個結(jié)點 直到所有的結(jié)點都檢查 算法描述voidDelete LinkList Node LNode L intkey 刪除以L為頭結(jié)點的單鏈表中值為key的第一個結(jié)點 LNode p L q L next while q NULL if q data key p next q next free q q p next else p q q q next 變形之二 刪除單鏈表中所有值重復(fù)的結(jié)點 使得所有結(jié)點的值都不相同 與按值查找相類似 但比前面的算法更復(fù)雜 基本思想 從單鏈表的第一個結(jié)點開始 對每個結(jié)點進(jìn)行檢查 檢查鏈表中該結(jié)點的所有后繼結(jié)點 只要有值和該結(jié)點的值相同 則刪除之 然后檢查下一個結(jié)點 直到所有的結(jié)點都檢查 算法描述voidDelete Node value LNode L 刪除以L為頭結(jié)點的單鏈表中所有值相同的結(jié)點 LNode p L next q ptr while p NULL 檢查鏈表中所有結(jié)點 q p ptr p next 檢查結(jié)點p的所有后繼結(jié)點ptr while ptr NULL if ptr data p data q next ptr next free ptr ptr q next else q ptr ptr ptr next p p next 5單鏈表的合并設(shè)有兩個有序的單鏈表 它們的頭指針分別是La Lb 將它們合并為以Lc為頭指針的有序鏈表 合并前的示意圖如圖2 4所示 合并了值為 7 2的結(jié)點后示意圖如圖2 5所示 算法說明算法中pa pb分別是待考察的兩個鏈表的當(dāng)前結(jié)點 pc是合并過程中合并的鏈表的最后一個結(jié)點 算法描述LNode Merge LinkList LNode La LNode Lb 合并以La Lb為頭結(jié)點的兩個有序單鏈表 LNode Lc pa pb pc ptr Lc La pc La pa La next pb Lb next while pa NULL 將pa所指的結(jié)點合并 pa指向下一個結(jié)點 if pa data pb data pc next pa pc pa pa pa next ptr pb pb pb next free ptr 將pa所指的結(jié)點合并 pb所指結(jié)點刪除 if pa NULL pc next pa elsepc next pb 將剩余的結(jié)點鏈上 free Lb return Lc 算法分析若La Lb兩個鏈表的長度分別是m n 則鏈表合并的時間復(fù)雜度為O m n 2 3 3循環(huán)鏈表 循環(huán)鏈表 CircularLinkedList 是一種頭尾相接的鏈表 其特點是最后一個結(jié)點的指針域指向鏈表的頭結(jié)點 整個鏈表的指針域鏈接成一個環(huán) 從循環(huán)鏈表的任意一個結(jié)點出發(fā)都可以找到鏈表中的其它結(jié)點 使得表處理更加方便靈活 圖2 6是帶頭結(jié)點的單循環(huán)鏈表的示意圖 空表 循環(huán)鏈表的操作對于單循環(huán)鏈表 除鏈表的合并外 其它的操作和單線性鏈表基本上一致 僅僅需要在單線性鏈表操作算法基礎(chǔ)上作以下簡單修改 判斷是否是空鏈表 head next head 判斷是否是表尾結(jié)點 p next head 2 4雙向鏈表 雙向鏈表 DoubleLinkedList 指的是構(gòu)成鏈表的每個結(jié)點中設(shè)立兩個指針域 一個指向其直接前趨的指針域prior 一個指向其直接后繼的指針域next 這樣形成的鏈表中有兩個方向不同的鏈 故稱為雙向鏈表 和單鏈表類似 雙向鏈表一般增加頭指針也能使雙鏈表上的某些運算變得方便 將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表 并稱之為雙向循環(huán)鏈表 雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的 1雙向鏈表的結(jié)點及其類型定義雙向鏈表的結(jié)點的類型定義如下 其結(jié)點形式如圖2 7所示 帶頭結(jié)點的雙向鏈表的形式如圖2 8所示 typedefstructDulnode ElemTypedata structDulnode prior next DulNode 雙向鏈表結(jié)構(gòu)具有對稱性 設(shè)p指向雙向鏈表中的某一結(jié)點 則其對稱性可用下式描述 p prior next p p next prior 結(jié)點p的存儲位置存放在其直接前趨結(jié)點p prior的直接后繼指針域中 同時也存放在其直接后繼結(jié)點p next的直接前趨指針域中 2雙向鏈表的基本操作 1 雙向鏈表的插入將值為e的結(jié)點插入雙向鏈表中 插入前后鏈表的變化如圖2 9所示 插入時僅僅指出直接前驅(qū)結(jié)點 鉤鏈時必須注意先后次序是 先右后左 部分語句組如下 S DulNode malloc sizeof DulNode S data e S next p next p next prior S p next S S prior p 鉤鏈次序非常重要 插入時同時指出直接前驅(qū)結(jié)點p和直接后繼結(jié)點q 鉤鏈時無須注意先后次序 部分語句組如下 S DulNode malloc sizeof DulNode S data e p next S S next q S prior p q prior S 2 雙向鏈表的結(jié)點刪除設(shè)要刪除的結(jié)點為p 刪除時可以不引入新的輔助指針變量 可以直接先斷鏈 再釋放結(jié)點 部分語句組如下 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 表示 既然是線性表 就可以用順序表和鏈表來實現(xiàn) 兩種不同實現(xiàn)方式的元素類型定義如下 1 順序存儲表示的類型typedefstruct floatcoef 系數(shù)部分 intexpn 指數(shù)部分 ElemType 2 鏈?zhǔn)酱鎯Ρ硎镜念愋蛅ypedefstructploy floatcoef 系數(shù)部分 intexpn 指數(shù)部分 structploy next Ploy 2一元多項式的相加不失一般性 設(shè)有兩個一元多項式 P x p0 p1x p2x2 pnxn Q x q0 q1x q2x2 qmxm m n R x P x Q x R x 由線性表R p0 q0 p1 q1 p2 q2 pm qm pn 唯一表示 順序存儲表示的相加線性表的定義typedefstruct ElemTypea MAX SIZE intlength Sqlist 用順序表示的相加非常簡單 訪問第5項可直接訪問 L a 4 coef L a 4 expn 2 鏈?zhǔn)酱鎯Ρ硎镜南嗉赢?dāng)采用鏈?zhǔn)酱鎯Ρ硎緯r 根據(jù)結(jié)點類型定義 凡是系數(shù)為0的項不在鏈表中出現(xiàn) 從而可以大大減少鏈表的長度 一元多項式相加的實質(zhì)是 指數(shù)不同 是鏈表的合并 指數(shù)相同 系數(shù)相加 和為0 去掉結(jié)點 和不為0 修改結(jié)點的系數(shù)域 算法之一 就在原來兩個多項式鏈表的基礎(chǔ)上進(jìn)行相加 相加后原來兩個多項式鏈表就不在存在 當(dāng)然再要對原來兩個多項式進(jìn)行其它操作就不允許了 算法描述Ploy add ploy ploy La ploy Lb 將以La Lb為頭指針表示的一元多項式相加 ploy Lc pc pa pb ptr floatx Lc pc La pa La next pb Lb next while pa NULL 將pb所指的結(jié)點合并 pb指向下一個結(jié)點 else x pa coef pb coef if abs x next free ptr ptr pb pb pb next free ptr else 如果系數(shù)和不為0 修改其中一個結(jié)點的系數(shù)域 刪除另一個結(jié)點 pc next pa pa coef x pc pa pa pa next ptr pb pb pb next free pb endofwhile if pa NULL pc next pb elsepc next pa return Lc 算法之二 對兩個多項式鏈表進(jìn)行相加 生成一個新的相加后的結(jié)果多項式鏈表 原來兩個多項式鏈表依然存在 不發(fā)生任何改變 如果要再對原來兩個多項式進(jìn)行其它操作也不影響 算法描述Ploy add ploy ploy La ploy Lb 將以La Lb為頭指針表示的一元多項式相加 生成一個新的結(jié)果多項式 ploy Lc pc pa pb p floatx Lc pc ploy malloc sizeof ploy pa La next pb Lb next while pa NULL 生成一個新的結(jié)果結(jié)點并賦值 pc next p pc p pa pa next 生成的結(jié)點插入到結(jié)果鏈表的最后 pa指向下一個結(jié)點 if pa expn pb expn p ploy malloc sizeof ploy p coef pb coef p expn pb expn p next NULL 生成一個新的結(jié)果結(jié)點并賦值 pc next p pc p pb pb next 生成的結(jié)點插入到結(jié)果鏈表的最后 pb指向下一個結(jié)點 if pa expn pb expn x pa coef pb coef if abs x next pb pb next else 若系數(shù)和不為0 生成的結(jié)點插入到結(jié)果鏈表的最后 pa pb分別直接后繼結(jié)點 p ploy malloc sizeof ploy p coef x p expn pb expn p next NULL 生成一個新的結(jié)果結(jié)點并賦值 pc next p pc p pa pa next pb pb next endofwhile if pb NULL while pb NULL p ploy malloc sizeof ploy p coef pb coef p expn pb expn p next NULL 生成一個新的結(jié)果結(jié)點并賦值 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 生成一個新的結(jié)果結(jié)點并賦值 pc next p pc p pa pa next return Lc 習(xí)題二 1簡述下列術(shù)語 線性表 順序表 鏈表 2何時選用順序表 何時選用鏈表作為線性表的存儲結(jié)構(gòu)合適 各自的主要優(yōu)缺點是什么 3在順序表中插入和刪除一個結(jié)點平均需要移動多少個結(jié)點 具體的移動次數(shù)取決于哪兩個因素 4鏈表所表示的元素是否有序 如有序 則有序性體現(xiàn)于何處 鏈表所表示的元素是否一定要在物理上是相鄰的 有序表的有序性又如何理解 5設(shè)順序表L是遞增有序表 試寫一算法 將x插入到L中并使L仍是遞增有序表 6寫一求單鏈表的結(jié)點數(shù)目ListLength L 的算法 7寫一算法將單鏈表中值重復(fù)的結(jié)點刪除 使所得的結(jié)果鏈表中所有結(jié)點的值均不相同 8寫一算法從一給定的向量A刪除值在x到y(tǒng) x y 之間的所有元素 注意 x和y是給定的參數(shù) 可以和表中的元素相同 也可以不同 9設(shè)A和B是兩個按元素值遞增有序的單鏈表 寫一算法將A和B歸并為按按元素值遞減有序的單鏈表C 試分析算法的時間復(fù)雜度 第3章棧和隊列 棧和隊列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu) 它們都來自線性表數(shù)據(jù)結(jié)構(gòu) 都是 操作受限 的線性表 棧在計算機的實現(xiàn)有多種方式 硬堆棧 利用CPU中的某些寄存器組或類似的硬件或使用內(nèi)存的特殊區(qū)域來實現(xiàn) 這類堆棧容量有限 但速度很快 軟堆棧 這類堆棧主要在內(nèi)存中實現(xiàn) 堆棧容量可以達(dá)到很大 在實現(xiàn)方式上 又有動態(tài)方式和靜態(tài)方式兩種 本章將討論棧和隊列的基本概念 存儲結(jié)構(gòu) 基本操作以及這些操作的具體實現(xiàn) 3 1棧 3 1 1棧的基本概念 1棧的概念棧 Stack 是限制在表的一端進(jìn)行插入和刪除操作的線性表 又稱為后進(jìn)先出LIFO LastInFirstOut 或先進(jìn)后出FILO FirstInLastOut 線性表 棧頂 Top 允許進(jìn)行插入 刪除操作的一端 又稱為表尾 用棧頂指針 top 來指示棧頂元素 棧底 Bottom 是固定端 又稱為表頭 空棧 當(dāng)表中沒有元素時稱為空棧 設(shè)棧S a1 a2 an 則a1稱為棧底元素 an為棧頂元素 如圖3 1所示 棧中元素按a1 a2 an的次序進(jìn)棧 退棧的第一個元素應(yīng)為棧頂元素 即棧的修改是按后進(jìn)先出的原則進(jìn)行的 2棧的抽象數(shù)據(jù)類型定義ADTStack 數(shù)據(jù)對象 D ai ai ElemSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R ai 1 ai D i 2 3 n 基本操作 初始化 進(jìn)棧 出棧 取棧頂元素等 ADTStack 棧的順序存儲結(jié)構(gòu)簡稱為順序棧 和線性表相類似 用一維數(shù)組來存儲棧 根據(jù)數(shù)組是否可以根據(jù)需要增大 又可分為靜態(tài)順序棧和動態(tài)順序棧 靜態(tài)順序棧實現(xiàn)簡單 但不能根據(jù)需要增大棧的存儲空間 動態(tài)順序棧可以根據(jù)需要增大棧的存儲空間 但實現(xiàn)稍為復(fù)雜 3 1 2棧的順序存儲表示 采用動態(tài)一維數(shù)組來存儲棧 所謂動態(tài) 指的是棧的大小可以根據(jù)需要增加 用bottom表示棧底指針 棧底固定不變的 棧頂則隨著進(jìn)棧和退棧操作而變化