《電子科技大學(xué)軟件技術(shù)基礎(chǔ)1孟中樓.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《電子科技大學(xué)軟件技術(shù)基礎(chǔ)1孟中樓.ppt（37頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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