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