電子科技大學(xué)軟件技術(shù)基礎(chǔ)1孟中樓.ppt

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

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