【正文】 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)結(jié)構(gòu)與算法分析(C++版 )課件上 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 第 1章 緒論 第 2講 線性表 第 3講 棧和隊列 第 4講 串 第 5講 數(shù)組和廣義表 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 第 1章 緒論 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)結(jié)構(gòu)討論的范疇 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 Niklaus Wirth Algorithm + Data Structures = Programs 程序設(shè)計 : 算 法 : 數(shù)據(jù)結(jié)構(gòu) : 為計算機(jī)處理問題 編制一組指令集 處理問題的策略 問題的數(shù)學(xué)模型 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 ―學(xué)生”表格 學(xué) 號 姓 名 性別 籍 貫 出生年月 1 98131 劉激揚(yáng) 男 北 京 2 98164 衣春生 男 青 島 3 98165 盧聲凱 男 天 津 4 98182 袁秋慧 女 廣 州 5 98224 洪 偉 男 太 原 6 98236 熊南燕 女 蘇 州 7 98297 宮 力 男 北 京 8 98310 蔡曉莉 女 昆 明 9 98318 陳 健 男 杭 州 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖 / (root) bin lib user etc math ds sw yin tao xie 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 綜合以例子可見，描述這類非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu) 因此簡單說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)結(jié)構(gòu)基本概念 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù) （ data） ? 數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機(jī)中，被計算機(jī)程序識別和處理的符號的集合 ? 數(shù)值性數(shù)據(jù) ? 非數(shù)值性數(shù)據(jù) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)元素 (data element) ? 數(shù)據(jù)的 基本單位 。在計算機(jī)程序中常作為一個整體進(jìn)行考慮和處理 ? 有時一個數(shù)據(jù)元素可以由若干 數(shù)據(jù)項 (Data Item)組成。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 什么是數(shù)據(jù)結(jié)構(gòu) 定義 : 由某一數(shù)據(jù)元素的集合及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成 記為： Data_Structure = {D, S} 其中， D 是某一數(shù)據(jù)元素的集合， S 是該集合中所有數(shù)據(jù)元素之間的關(guān)系組成的有限集合 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) 從邏輯關(guān)系上描述數(shù)據(jù) ， 與數(shù)據(jù)的存儲無關(guān) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是 從具體問題抽象出來的數(shù)據(jù)模型 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)的 邏輯結(jié)構(gòu) 可歸結(jié)為以下 四類 線性 結(jié)構(gòu) 樹形 結(jié)構(gòu) 圖狀 結(jié)構(gòu) 集合 結(jié)構(gòu) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)的存儲結(jié)構(gòu) ? 數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實(shí)現(xiàn) ? 數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言 ? 順序存儲表示 ? 鏈接存儲表示 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 順序存貯 所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計算機(jī)內(nèi)存仍然相鄰 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 鏈?zhǔn)酱尜A 所有元素存放在可以不連續(xù)的存貯單元中 ， 但元素之間的關(guān)系可以通過地址確定 ， 邏輯上相鄰的元素存放到計算機(jī)內(nèi)存后不一定是相鄰的 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 數(shù)據(jù)類型 ? 數(shù)據(jù)類型 定義： 一組性質(zhì)相同的值的集合 , 以及定義于這個值集合上的一組操作的總稱 ? 如 C語言中 有如下 數(shù)據(jù)類型 char int float double void 字符型 整型 浮點(diǎn)型 雙精度型 無值 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 ? 構(gòu)造數(shù)據(jù)類型由 不同成分 構(gòu)成 ? 基本數(shù)據(jù)類型可以看作是 計算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types) ?由用戶定義，用以表示應(yīng)用問題的 數(shù)據(jù)模型 ?由 基本的數(shù)據(jù)類型 組成 , 并包括含 一組相關(guān)的服務(wù) （或稱操作） 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 ADT 有兩個重要特征 數(shù)據(jù)抽象 用 ADT描述程序處理的實(shí)體時，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法） 數(shù)據(jù)封裝 將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏 其內(nèi)部實(shí)現(xiàn)細(xì)節(jié) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型 (高級編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型 )來實(shí)現(xiàn) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 算 法 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 算法是為了解決某類問題而規(guī)定的一個有限長的操作序列 算法定義 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 算法應(yīng)具有的性質(zhì) 正 確 性 具 體 性 確 定 性 有 限 性 可 讀 性 健 壯 性 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 正確性 正確性指必須完成所期望的功能，對算法是否“ 正確 ”的理解可以有如下四個層次 ： （ 1）程序中不含任何語法錯誤。 （ 2）程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。 （ 3）程序?qū)τ诰倪x擇的、典型的、苛刻的并帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。 （ 4）程序?qū)τ谝磺休斎霐?shù)據(jù)都能得出滿足要求的結(jié)果。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 具體性 一個算法必須由一系列 具體操作 組成，這時的“ 具體 ”指的所有操作都必須經(jīng)過 已實(shí)現(xiàn) 的基本操作有限次來實(shí)現(xiàn)，并且所有操作都是可讀的、可執(zhí)行的， 每一操作 必須在 有限時間 內(nèi)完成。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 確定性 算法中 的所有操作都必須有確切的含義 ，不能產(chǎn)生歧義，算法的執(zhí)行者或閱讀者都能明確其含義 及 如何執(zhí)行 。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 有限性 對于任意一組合法輸入值，在執(zhí)行 有限步驟 之后一定能結(jié)束，即：算法中的每個步驟都能在 有限時間 內(nèi)完成 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 可讀性 算法 應(yīng)具備良好的 可讀性 ，這樣的算法有利于算法的查錯及對算法的理解，一般算法的 邏輯必須清楚 、 結(jié)構(gòu)簡單 ，所有 標(biāo)識符 必須具有 實(shí)際含義 ，能 見名知義 。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 健壯性 健壯性指當(dāng) 輸入數(shù)據(jù)非法 時，算法能作 適當(dāng)?shù)奶幚?并作出反應(yīng)，而不應(yīng) 死機(jī) 或輸出異常結(jié)果 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 算法描述方法 用自然語言描述算法 用我們?nèi)粘Ｉ钪械淖匀徽Z言（可以是中文形式，也可以是英文形式）也可以描述算法 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 用流程圖描述算法 一個算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高級語言程序設(shè)計中仍然采用。也有其他的圖形輔助工具 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 用其它方式描述算法 我們還可以用數(shù)學(xué)語言或約定的符號語言來描述算法 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 用 C++描述算法 在本課中 ， 我們將采用類 C++來描述算法 ,所有算法的描述都用C＋＋中的函數(shù)形式來描述 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 為表示各種狀態(tài)信息，定義枚舉類型StatusCode供使用，具體聲明如下： // 自定義類型 enum StatusCode { SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR, NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED }。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 算法和程序的關(guān)系 算法著重體現(xiàn)思路和方法 ， 程序著重體現(xiàn)計算機(jī)的實(shí)現(xiàn) 程序不一定滿足有窮性 （ 死循環(huán) ） ，另外 ， 程序中的指令必須是機(jī)器可執(zhí)行的 ， 算法中的指令無此限制 一個算法若用計算機(jī)語言來書寫 ，它就可以是一個程序 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 算法評價標(biāo)準(zhǔn) 時間特性 (時間復(fù)雜度 T(n) ) 空間特性 (空間復(fù)雜度 S(n) ) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 一個特定 算法的 “ 運(yùn)行工作量 ” 的大小，只依賴于 問題的規(guī)模（通常用整數(shù)量 n表示），或者說，它 是問題規(guī)模的函數(shù) 。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 假如，隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率和 f(n) 的增長率相同 ，則可記作： T (n) = O(f(n)) 稱 T (n) 為算法的 (漸近 )時間復(fù)雜度。 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 例 矩陣元素之和 template class ElemType ElemType Sum( ElemType a[][MAX_SIZE], int n) // 操作結(jié)果 : 返回矩陣 a中元素之和 { ElemType s = 0。 // 暫存和 for (int i = 0。 i n。 i++) for (int j = 0。 j n。 j++) s = s + a[i][j]。 // 遍歷求和 return s。 // 返回元素之和 } 基本操作 : 加法 “ +” 時間復(fù)雜度 : O(n2) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 四、算法的存儲空間需求 算法的 空間復(fù)雜度定義為 : 表示隨著問題規(guī)模 n 的增大， 算法運(yùn)行所需存儲量的增長率 與 g(n) 的增長率相同。 S(n) = O(g(n)) 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 面向?qū)ο蟮母拍? ? 面向?qū)ο? = 對象＋類＋繼承 ? 對象 ?由一組 屬性值 和在這組值上的一 組 服務(wù) （或稱操作）構(gòu)成 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 為什么選用面向?qū)ο蠹?C++語言 講述數(shù)據(jù)結(jié)構(gòu)？ ? PASCAL與 C描述是面向過程的 ? C++描述兼有面向過程與面向?qū)ο蟮奶攸c(diǎn) ? 用面向?qū)ο蠹?C++描述與國際接軌，是市場需要 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 第 2章 線性表 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 線性表 (Linear List) 線性表的定義和特點(diǎn) 定義 n（ ? 0） 個數(shù)據(jù)元素的有限序 列，記作 （ a1, a2, … , an） ai 是表中數(shù)據(jù)元素， n 是表長度。 遍歷 逐項訪問： 從前向后 從后向前 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 線性表的特點(diǎn) ? 除第一個元素外，其他每一個元素有一個且僅有一個 直接前驅(qū) 。 ? 除最后一個元素外，其他每一個元素有一個且僅有一個 直接后繼 。 a1 a2 a3 a4 a5 a6 四川大學(xué)計算機(jī)學(xué)院，主講教師：游洪躍 線性表基本操作 1． int