電子科技大學軟件技術基礎1孟中樓.ppt

《電子科技大學軟件技術基礎1孟中樓.ppt》由會員分享，可在線閱讀，更多相關《電子科技大學軟件技術基礎1孟中樓.ppt（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

軟件技術基礎 電子科技大學通信與信息工程學院軟件技術基礎課題組教師 孟中樓Email zlmeng SCIE UniversityofElectronicScienceandTechnologyofChina 2 課程簡介 教材和參考資料教材 軟件技術基礎 第3版 黃迪明等編著 電子科技大學出版社 出版日期2009年7月參考資料 1 數(shù)據(jù)結構 清華大學出版社 嚴蔚敏等2 計算機操作系統(tǒng) 西安電子科技大學出版社 湯子瀛 SCIE UniversityofElectronicScienceandTechnologyofChina 3 課程簡介 課程安排講授學時安排 48學時 第一章數(shù)據(jù)結構26學時第二章操作系統(tǒng)22學時軟件技術基礎QQ群554768353 SCIE UniversityofElectronicScienceandTechnologyofChina 4 課程簡介 考核方式平時考核占15 包括課堂出勤 平時作業(yè)中期考試占5 采用開卷考試方式期末考試占80 采用閉卷考試方式 SCIE UniversityofElectronicScienceandTechnologyofChina 5 1 數(shù)據(jù)結構的基本概念 幾個基本問題什么是數(shù)據(jù)結構數(shù)據(jù)結構研究的主要內(nèi)容學習數(shù)據(jù)結構的意義 SCIE UniversityofElectronicScienceandTechnologyofChina 6 1 數(shù)據(jù)結構的基本概念 本章主要講述內(nèi)容1 1數(shù)據(jù)結構中的基本術語1 2數(shù)據(jù)的邏輯結構1 3數(shù)據(jù)的存儲結構1 4算法 SCIE UniversityofElectronicScienceandTechnologyofChina 7 1 1數(shù)據(jù)結構中的基本術語 一 數(shù)據(jù)及數(shù)據(jù)元素的概念數(shù)據(jù)是客觀事物在計算機內(nèi)的抽象描述數(shù)據(jù)指一些事實 或一些數(shù) 或一些符號集合數(shù)據(jù)的基本單位 數(shù)據(jù)元素組成數(shù)據(jù)的 事實 數(shù)值 或 符號 稱為數(shù)據(jù)元素數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成 三者之間的關系 例 班級通訊錄 個人記錄 姓名 年齡 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 SCIE UniversityofElectronicScienceandTechnologyofChina 8 1 1數(shù)據(jù)結構中的基本術語 例1 學生花名冊 數(shù)據(jù)元素 數(shù)據(jù) 學生名字的集合 每個學生的名字 例2 學生成績表 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 學生成績的集合 每個學生的成績 名字 成績 SCIE UniversityofElectronicScienceandTechnologyofChina 9 1 1數(shù)據(jù)結構中的基本術語 二 數(shù)據(jù)結構的概念結構是指事物間的相互關系和約束 數(shù)據(jù)結構討論計算機系統(tǒng)中數(shù)據(jù)的組織形式及其相互關系數(shù)據(jù)結構是相互之間存在一種和多種特定關系的數(shù)據(jù)元素的集合 表示為 Data Structure D R 元素有限集 關系有限集 SCIE UniversityofElectronicScienceandTechnologyofChina 10 1 1數(shù)據(jù)結構中的基本術語 元素集合 元素間的關系 運算 計算機系統(tǒng) 元素在計算機系統(tǒng)里的表示字符 字串 整數(shù) 元素間的邏輯關系 邏輯結構元素在計算機系統(tǒng)中的存儲方式 物理空間關系 存儲結構操作指令的集合 算法 SCIE UniversityofElectronicScienceandTechnologyofChina 11 三 數(shù)據(jù)的邏輯結構與數(shù)據(jù)的存儲結構邏輯結構 數(shù)據(jù)元素之間關系的描述存儲結構 數(shù)據(jù)元素在計算機系統(tǒng)存儲器中的存放方式 例 班級里的同學 可能有各種各樣的邏輯關系 比如班長 班委 群眾等 形成相應的邏輯結構 上課時 大家的座次形成存儲結構 座次 存儲結構 可能與邏輯關系有關 也可能無關 1 1數(shù)據(jù)結構中的基本術語 SCIE UniversityofElectronicScienceandTechnologyofChina 12 邏輯結構 四 小結 數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構 數(shù)據(jù)在計算機系統(tǒng)中的存儲結構和數(shù)據(jù)操作的集合把數(shù)據(jù)以一定的邏輯結構組織起來 以適當?shù)姆绞酱鎯υ谟嬎銠C系統(tǒng)的存儲器里 其最終目的是為了有效處理數(shù)據(jù) 提高數(shù)據(jù)處理運算速度 教材P3 存儲結構 算法 1 1數(shù)據(jù)結構中的基本術語 要素 目標 三個要素都與我們所要實現(xiàn)的目標相關 有效處理數(shù)據(jù) 提高數(shù)據(jù)處理運算速度 SCIE UniversityofElectronicScienceandTechnologyofChina 13 數(shù)據(jù)的邏輯結構 數(shù)據(jù)元素之間關系的描述一 描述法二元組關系 一般抽象為前驅與后繼關系 即表明結構中 一個元素的前一個元素是誰 它的后一個元素又是誰 B K R K 元素集合 R 元素間關系的集合 1 2數(shù)據(jù)的邏輯結構 SCIE UniversityofElectronicScienceandTechnologyofChina 14 二 圖示法圖形要素 結點和有向線段結點 表示一個數(shù)據(jù)元素 一般以方形框代表不管多么復雜的結點 都看作是一個結點有向線段 表示元素之間的關系 箭尾指向的結點是前驅 箭頭指向的結點是后繼 Ki Kh Kj Ki的前驅 Ki的后繼 1 2數(shù)據(jù)的邏輯結構 SCIE UniversityofElectronicScienceandTechnologyofChina 15 數(shù)據(jù)的存儲結構 物理結構 是數(shù)據(jù)元素在計算機系統(tǒng)存儲器中的存放方式也可以說 是數(shù)據(jù)邏輯結構在存儲器中的存放方式 1 3數(shù)據(jù)的存儲結構 存儲器的特點 由地址連續(xù)的單元構成 SCIE UniversityofElectronicScienceandTechnologyofChina 16 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 K1 K2 K3 K4 1 3數(shù)據(jù)的存儲結構 邏輯結構 物理結構 SCIE UniversityofElectronicScienceandTechnologyofChina 17 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 K5 K6 K1 K2 K3 K4 K5 K6 1 3數(shù)據(jù)的存儲結構 邏輯結構 物理結構 SCIE UniversityofElectronicScienceandTechnologyofChina 18 1 3數(shù)據(jù)的存儲結構 思考 為什么數(shù)據(jù)邏輯結構與物理結構沒有完全統(tǒng)一 存儲器的特點 由地址連續(xù)的單元構成 線性關系 存儲單元間位置上的線性關系有時不能直接反映復雜的邏輯關系 SCIE UniversityofElectronicScienceandTechnologyofChina 19 幾種物理存儲方式一 順序存儲方法連續(xù)順序地存放數(shù)據(jù)元素若數(shù)據(jù)的邏輯結構也是順序 線性 的 則邏輯結構和物理結構完全統(tǒng)一了連續(xù)存放的數(shù)據(jù)元素可以在內(nèi)存中容易找到 1 3數(shù)據(jù)的存儲結構 SCIE UniversityofElectronicScienceandTechnologyofChina 20 二 鏈接存儲方法元素在內(nèi)存中不一定連續(xù)存放在元素中附加指針項 通過指針可以找到關系元素 元素 指針 結點 元素 指針 1 3數(shù)據(jù)的存儲結構 聯(lián)想 在一套叢書中每一本書中夾一個卡片 記錄下一本書在書架上的位置 SCIE UniversityofElectronicScienceandTechnologyofChina 21 0300 0310 0320 0330 0340 0350 0370 0380 K1 K2 K3 K4 K5 K6 K1 K2 K3 K4 K5 K6 通過指針 可以方便地找到關系結點 指向后繼結點的指針 1 3數(shù)據(jù)的存儲結構 邏輯結構 物理結構 SCIE UniversityofElectronicScienceandTechnologyofChina 22 三 索引存儲方法為放在內(nèi)存中的元素建立索引表元素可以離散存放通過查索引表找到需要的元素 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 1 2 3 4 索引表 索引號 1 3數(shù)據(jù)的存儲結構 聯(lián)想 圖書館的查書卡 SCIE UniversityofElectronicScienceandTechnologyofChina 23 四 散列存儲方法結點中設一關鍵值 利用關鍵值和相應散列函數(shù)算出結點位置 地址 例 以用戶姓名為關鍵值 DJS 算式 字母的序號相加 04 10 19 33 ZXM 26 24 13 63 1 3數(shù)據(jù)的存儲結構 DJS放在33號地址單元ZXM放在63號地址單元 聯(lián)想 通過書的名字就能確定書的位置 SCIE UniversityofElectronicScienceandTechnologyofChina 24 小結 數(shù)據(jù)的邏輯結構與物理結構1 物理結構是元素在內(nèi)存中的存儲方式 與元素間固有的邏輯關系是相對獨立的兩個問題物理結構著眼于結點在內(nèi)存中的定位2 簡單的邏輯結構可能和物理結構一致例 線性邏輯關系與順序存儲方法3 利用物理結構在內(nèi)存中找到一個結點 而為什么要找這個結點卻由元素間的邏輯關系決定任何一個算法的設計取決于選定的數(shù)據(jù)邏輯結構 而算法的實現(xiàn)依賴于采用的存儲結構4 邏輯結構與存儲結構是一個問題的兩個方面 1 3數(shù)據(jù)的存儲結構 SCIE UniversityofElectronicScienceandTechnologyofChina 25 例 一個樹形關系結構用索引方式存儲 1 2 3 4 5 6 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1 K2 K3 K4 K5 K6 1 3數(shù)據(jù)的存儲結構 SCIE UniversityofElectronicScienceandTechnologyofChina 26 1 3數(shù)據(jù)的存儲結構 SCIE UniversityofElectronicScienceandTechnologyofChina 27 一 算法的概念及特點算法是為解決某一特定類型問題規(guī)定的運算規(guī)則的有窮集合有窮性確定性有效性輸入輸出 特點 非無限執(zhí)行 必須在有限步驟內(nèi)結束 非二義 下一步必須是明確的 每一步是可執(zhí)行的 外部輸入零個或多個 至少一個 1 4算法 SCIE UniversityofElectronicScienceandTechnologyofChina 28 二 算法與程序相似 都是解決問題的方法和步驟 是指令的集合區(qū)別 算法具有有窮性描述方法聯(lián)系 程序用某種程序設計語言來實現(xiàn)算法 程序使用程序設計語言 算法可以使用框圖及其他語言 1 4算法 類似 While 1 的語句段 在程序中允許但在算法中不允許 SCIE UniversityofElectronicScienceandTechnologyofChina 29 三 算法語言算法應有嚴格的描述語言 確定性 一般使用類PASCAL語言在本課程中使用類C語言 即語言風格類似于C描述一個算法時必須滿足 對輸入和輸出的描述描述語句準確 無二義保證算法的有窮性和有效性 1 4算法 SCIE UniversityofElectronicScienceandTechnologyofChina 30 1 4算法 算法的寫作規(guī)范 intseq search elemtypes keytypek intn intlow high mid s n key k i 0 while s i key k i if i n returni elsereturn 1 SCIE UniversityofElectronicScienceandTechnologyofChina 31 四 在數(shù)據(jù)結構中常見的問題創(chuàng)建 插入 刪除 更新 檢索 排序 注意 每個問題都有一種或多種算法找到效率最高的以最容易理解的方式設計設計的算法不容易出錯或出錯情況較少 1 4算法 SCIE UniversityofElectronicScienceandTechnologyofChina 32 五 算法和數(shù)據(jù)結構的關系算法是建立在數(shù)據(jù)結構的基礎上的合理的數(shù)據(jù)結構常?？梢杂行У暮喕惴ㄖ挥忻鞔_了算法 才能較好的設計數(shù)據(jù)結構程序 算法 數(shù)據(jù)結構 1 4算法 SCIE UniversityofElectronicScienceandTechnologyofChina 33 六 算法的衡量 1 4算法 常用時間復雜度來衡量 算法評價有4個指標 運行時間 占用空間 正確性和簡單性 常用空間復雜度來衡量 SCIE UniversityofElectronicScienceandTechnologyofChina 34 五 算法的衡量 1 4算法 注 1 O 為漸近符號2 空間復雜度S n 按數(shù)量級遞增順序也與上表類似 復雜度高 復雜度低 時間復雜度T n 按數(shù)量級遞增順序為 SCIE UniversityofElectronicScienceandTechnologyofChina 35 1 4算法 3n 2 O n 因為3n 2 4nforn 26 2n n2 O 2n 因為6 2n n2 7 2nforn 4 例 漸進符號 O 的定義 當且僅當存在一個正的常數(shù)C 使得對所有的n n0 有f n Cg n 則 f n O g n SCIE UniversityofElectronicScienceandTechnologyofChina 36 1 4算法 該算法的運行時間由程序中所有語句的頻度 即該語句重復執(zhí)行的次數(shù) 之和構成 解 分析 顯然 語句 的頻度是1 設語句2的頻度是f n 則有 算法的時間復雜度是由嵌套最深層語句的頻度決定的 SCIE UniversityofElectronicScienceandTechnologyofChina 37 作業(yè) 教材P741 2 3 4 5