數(shù)據(jù)結構嚴蔚敏完整版ppt課件.ppt

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