計(jì)算機(jī)導(dǎo)論 計(jì)算機(jī)系統(tǒng)的軟件 電子工業(yè)出版社

1、第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件本章要點(diǎn)與學(xué)習(xí)要求：本章要點(diǎn)與學(xué)習(xí)要求：計(jì)算機(jī)軟件概念、分類計(jì)算機(jī)軟件概念、分類 （熟悉）（熟悉）程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言 （了解）（了解）數(shù)據(jù)結(jié)構(gòu)的定義、分類數(shù)據(jù)結(jié)構(gòu)的定義、分類 （熟悉）（熟悉）編譯原理的過程編譯原理的過程 （掌握）（掌握）操作系統(tǒng)的分類、功能操作系統(tǒng)的分類、功能 （掌握）（掌握）軟件工程的生命周期、模型軟件工程的生命周期、模型 （熟悉）（熟悉）第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)軟件概述計(jì)算機(jī)軟件概述3.1算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)3.2程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言3.3編譯原理編譯原理3.5操作系統(tǒng)操作系統(tǒng)

2、3.6軟件工程軟件工程3.7數(shù)據(jù)庫(kù)系統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)3.4第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件教學(xué)目的教學(xué)目的 本講主要介紹計(jì)算機(jī)軟件的基本概念本講主要介紹計(jì)算機(jī)軟件的基本概念,對(duì)計(jì)算機(jī)軟件有總體上了解對(duì)計(jì)算機(jī)軟件有總體上了解教學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn)與難點(diǎn) 軟件定義軟件定義 軟件分類軟件分類 計(jì)算機(jī)系統(tǒng)的組成計(jì)算機(jī)系統(tǒng)的組成第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件教學(xué)引入 在第二章，我們學(xué)習(xí)了計(jì)算機(jī)的內(nèi)部組成，在第二章，我們學(xué)習(xí)了計(jì)算機(jī)的內(nèi)部組成，那么是誰(shuí)控制這些硬件讓它為我們服務(wù)？那么是誰(shuí)控制這些硬件讓它為我們服務(wù)？ 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算

3、機(jī)系統(tǒng)的軟件程序作為商品以有形介質(zhì)程序作為商品以有形介質(zhì)(如磁盤、光盤如磁盤、光盤)為載體進(jìn)行交易為載體進(jìn)行交易,稱做軟件（稱做軟件（Software）。確切地說，）。確切地說，軟件是指為運(yùn)行、維軟件是指為運(yùn)行、維護(hù)、管理及應(yīng)用計(jì)算機(jī)所編制的所有程序及其文檔資料的護(hù)、管理及應(yīng)用計(jì)算機(jī)所編制的所有程序及其文檔資料的總和?？偤汀?上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 軟件的特性軟件的特性 軟件是功能、性能相對(duì)完備的程序系統(tǒng)軟件是功能、性能相對(duì)完備的程序系統(tǒng) 軟件是具有使用性能的軟設(shè)備軟件是具有使用性能的軟設(shè)備 軟件是信息商品軟件是信息商品 軟件是一種只有過時(shí)而無(wú)軟件是一種只有過時(shí)而無(wú)“磨損磨損”的

4、商品的商品第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件系統(tǒng)軟件：系統(tǒng)軟件：軟件制售商為釋放硬件潛能、方便使用而配備的軟軟件制售商為釋放硬件潛能、方便使用而配備的軟件。件。OSOS、語(yǔ)言編譯、語(yǔ)言編譯/ /解釋系統(tǒng)、網(wǎng)絡(luò)軟件、數(shù)據(jù)庫(kù)管理軟件、各解釋系統(tǒng)、網(wǎng)絡(luò)軟件、數(shù)據(jù)庫(kù)管理軟件、各種服務(wù)程序、界面工具箱等支持計(jì)算機(jī)正常運(yùn)作和種服務(wù)程序、界面工具箱等支持計(jì)算機(jī)正常運(yùn)作和“通用通用”的軟件。的軟件。應(yīng)用軟件：應(yīng)用軟件：指解決某一應(yīng)用領(lǐng)域問題的軟件。指解決某一應(yīng)用領(lǐng)域問題的軟件。財(cái)會(huì)軟件、通信軟件、科技計(jì)算軟件、財(cái)會(huì)軟件、通信軟件、科技計(jì)算軟件、CAD/CAM軟件等。軟件等。 上一頁(yè)上一頁(yè) 返返

5、回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件操作操作系統(tǒng)系統(tǒng)群件群件系統(tǒng)系統(tǒng)辦公辦公軟件軟件系統(tǒng)工系統(tǒng)工具軟件具軟件管理計(jì)算機(jī)系統(tǒng)的軟硬件資料，合理地組織計(jì)算機(jī)工作流程，管理計(jì)算機(jī)系統(tǒng)的軟硬件資料，合理地組織計(jì)算機(jī)工作流程，并為用戶使用計(jì)算機(jī)提供良好的工作環(huán)境。如并為用戶使用計(jì)算機(jī)提供良好的工作環(huán)境。如Windows等。等。 一類日常辦公的軟件，如一類日常辦公的軟件，如Office編程語(yǔ)言一般是以一個(gè)集成環(huán)境的形式編程語(yǔ)言一般是以一個(gè)集成環(huán)境的形式出現(xiàn)的。如：出現(xiàn)的。如：Visual

6、Stutio ?？梢詭椭僮飨到y(tǒng)更有效地完成系可以幫助操作系統(tǒng)更有效地完成系統(tǒng)的管理和維護(hù)。如反病毒軟件統(tǒng)的管理和維護(hù)。如反病毒軟件Internet工具軟件工具軟件多媒體多媒體處理處理數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)是信息管理的中心，如是信息管理的中心，如Access、SQL Server一種基于電子郵件的應(yīng)用系統(tǒng)軟件，它一種基于電子郵件的應(yīng)用系統(tǒng)軟件，它拓寬了電子郵件的內(nèi)涵，涵養(yǎng)了很多通拓寬了電子郵件的內(nèi)涵，涵養(yǎng)了很多通信協(xié)作功能。如信協(xié)作功能。如Notes、Exchange Server、Group Wise在在CPU一級(jí)提供多媒體指令，實(shí)一級(jí)提供多媒體指令，實(shí)現(xiàn)對(duì)多媒體的直接支持?，F(xiàn)對(duì)多媒體的直接支持?；?/p>

7、網(wǎng)絡(luò)環(huán)境和基于網(wǎng)絡(luò)環(huán)境和Internet 環(huán)境的應(yīng)用軟環(huán)境的應(yīng)用軟件，如件，如Web服務(wù)器、服務(wù)器、FTP 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 軟件概念；軟件概念； 軟件分類；軟件分類； 計(jì)算機(jī)系統(tǒng)的組成；計(jì)算機(jī)系統(tǒng)的組成； P194 1、2 返返 回回 上一頁(yè)上一頁(yè)第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 教學(xué)目的教學(xué)目的 本講主要介紹算法和數(shù)據(jù)結(jié)構(gòu)的基本概念

8、，以及幾種常用的本講主要介紹算法和數(shù)據(jù)結(jié)構(gòu)的基本概念，以及幾種常用的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 教學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn)與難點(diǎn) 1. 1. 算法的基本概念算法的基本概念 2. 2. 線性表線性表 3. 3. 棧棧 4. 4. 隊(duì)列隊(duì)列 5. 5. 樹樹第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件教學(xué)引入 計(jì)算機(jī)內(nèi)部有很多數(shù)據(jù)需要我們處理，那計(jì)算機(jī)內(nèi)部有很多數(shù)據(jù)需要我們處理，那么計(jì)算機(jī)是按照什么形式處理這些數(shù)據(jù)的？么計(jì)算機(jī)是按照什么形式處理這些數(shù)據(jù)的？ 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件典型問題典型問題排序問題排序問題漢諾塔問題漢諾塔問題n皇后問題皇后問題旅行商問題

9、旅行商問題問題類型問題類型排序排序查找查找串處理串處理圖問題圖問題組合問題組合問題幾何問題幾何問題數(shù)值問題數(shù)值問題 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件問題的描述問題的描述建立數(shù)學(xué)模型建立數(shù)學(xué)模型算法設(shè)計(jì)算法設(shè)計(jì)算法的正確性證明算法的正確性證明算法分析算法分析算法的程序?qū)崿F(xiàn)算法的程序?qū)崿F(xiàn) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件算法算法+ +數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)= =程序程序?qū)λ惴ǖ难芯恐饕▋煞矫鎯?nèi)容：對(duì)算法的研究主要包括兩方面內(nèi)容：一是如何設(shè)計(jì)算法，常用的算法設(shè)計(jì)方法有分治遞歸、貪心法、一是如何設(shè)

10、計(jì)算法，常用的算法設(shè)計(jì)方法有分治遞歸、貪心法、回溯法、動(dòng)態(tài)規(guī)劃、分支限界等；回溯法、動(dòng)態(tài)規(guī)劃、分支限界等；二是對(duì)給定算法，如何分析它的效率和性能。二是對(duì)給定算法，如何分析它的效率和性能。數(shù)據(jù)的結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)的結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu)反映數(shù)據(jù)成員之間的邏輯關(guān)系邏輯結(jié)構(gòu)反映數(shù)據(jù)成員之間的邏輯關(guān)系物理結(jié)構(gòu)反映數(shù)據(jù)成員在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。物理結(jié)構(gòu)反映數(shù)據(jù)成員在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件算法概念算法概念算法原意指計(jì)算步驟或規(guī)則算法原意指計(jì)算步驟或規(guī)則在計(jì)算機(jī)科學(xué)中，算法指用計(jì)算機(jī)求解某一問題

11、的方法在計(jì)算機(jī)科學(xué)中，算法指用計(jì)算機(jī)求解某一問題的方法算法特征算法特征有窮性（有窮性（Finiteness）確定性（確定性（Definiteness）有效性（有效性（Effectiveness）有有0個(gè)或多個(gè)輸入項(xiàng)個(gè)或多個(gè)輸入項(xiàng)至少有一個(gè)輸出項(xiàng)至少有一個(gè)輸出項(xiàng) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件算法描述算法描述自然語(yǔ)言描述自然語(yǔ)言描述流程圖描述流程圖描述偽代碼描述偽代碼描述算法結(jié)構(gòu)算法結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)選擇（分支）結(jié)構(gòu)選擇（分支）結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件算法

12、設(shè)計(jì)方法算法設(shè)計(jì)方法遞歸技術(shù)遞歸技術(shù)分治法分治法貪心算法貪心算法回溯法回溯法動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法算法分析算法分析 時(shí)間復(fù)雜性指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間時(shí)間復(fù)雜性指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間 空間復(fù)雜性指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的空間空間復(fù)雜性指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的空間 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)數(shù)據(jù)定義：一切可輸入計(jì)算機(jī)并能為計(jì)算機(jī)所處理的描述客觀事物定義：一切可輸入計(jì)算機(jī)并能為計(jì)算機(jī)所處理的描述客觀事物的符號(hào)，稱為數(shù)據(jù)。在計(jì)算機(jī)中，數(shù)據(jù)的定義是廣泛的，數(shù)、的符號(hào)，稱為數(shù)據(jù)。在計(jì)算機(jī)中，數(shù)據(jù)的定義是

13、廣泛的，數(shù)、字符、圖形、聲音都可是計(jì)算機(jī)處理的對(duì)象，統(tǒng)稱為數(shù)據(jù)字符、圖形、聲音都可是計(jì)算機(jī)處理的對(duì)象，統(tǒng)稱為數(shù)據(jù)分類分類數(shù)值數(shù)據(jù)：數(shù)值數(shù)據(jù)：應(yīng)用于科學(xué)計(jì)算的程序，它們的組織較為簡(jiǎn)單，如變量，數(shù)組，應(yīng)用于科學(xué)計(jì)算的程序，它們的組織較為簡(jiǎn)單，如變量，數(shù)組，簡(jiǎn)單表等。關(guān)心的是計(jì)算速度與精度。簡(jiǎn)單表等。關(guān)心的是計(jì)算速度與精度。非數(shù)值數(shù)據(jù)：非數(shù)值數(shù)據(jù)：應(yīng)用于商業(yè)或管理的程序，它們組織較為復(fù)雜，關(guān)心的是按什應(yīng)用于商業(yè)或管理的程序，它們組織較為復(fù)雜，關(guān)心的是按什么規(guī)則組織數(shù)據(jù)，使其占空間少，存取快，并有利于維護(hù)（增刪、修改）么規(guī)則組織數(shù)據(jù)，使其占空間少，存取快，并有利于維護(hù)（增刪、修改） 數(shù)據(jù)結(jié)構(gòu)就是一門研

14、究非數(shù)值性程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值性程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件書 名作者名登錄號(hào)分類號(hào)出版年月計(jì)算機(jī)病毒危機(jī)相杰超920253TP306/1092.5實(shí)用數(shù)據(jù)結(jié)構(gòu)霍義興871470TP31/7187.1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)蘇東莊841153TP303/1284.1數(shù)字邏輯王玉龍875027TP315/2087.5 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)類型：數(shù)據(jù)類型：

15、數(shù)據(jù)的定義域。常見的數(shù)據(jù)類型有字符型、整數(shù)數(shù)據(jù)的定義域。常見的數(shù)據(jù)類型有字符型、整數(shù)型、邏輯型、數(shù)組、集合、記錄等。型、邏輯型、數(shù)組、集合、記錄等。數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(date item)(date item)：是數(shù)據(jù)的是數(shù)據(jù)的最小單位最小單位。 數(shù)據(jù)元素?cái)?shù)據(jù)元素(date element)(date element)：是數(shù)據(jù)項(xiàng)的是數(shù)據(jù)項(xiàng)的集合集合（或稱（或稱記錄記錄) )數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(data object)(data object)：它是具有它是具有相同特性相同特性的的數(shù)據(jù)元素?cái)?shù)據(jù)元素的的集合。集合。 如整數(shù)數(shù)據(jù)對(duì)象的集合。如整數(shù)數(shù)據(jù)對(duì)象的集合。結(jié)構(gòu)結(jié)構(gòu)(data structure)(da

16、ta structure)：數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)元素之間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(data structure)(data structure)：它是帶有結(jié)構(gòu)的它是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集數(shù)據(jù)元素的集合合。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)組織形式，反應(yīng)數(shù)據(jù)之間的關(guān)系，但不。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)組織形式，反應(yīng)數(shù)據(jù)之間的關(guān)系，但不涉及數(shù)據(jù)的具體內(nèi)容。涉及數(shù)據(jù)的具體內(nèi)容。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件書書 名名作者作者名名登錄號(hào)登錄號(hào)分類號(hào)分類號(hào)出版年月出版年月計(jì)算機(jī)病毒危計(jì)算機(jī)病毒危機(jī)機(jī)相杰超相杰超920253TP306/1092.5實(shí)用數(shù)據(jù)結(jié)構(gòu)實(shí)用數(shù)據(jù)

17、結(jié)構(gòu)霍義興霍義興871470TP31/7187.1計(jì)算機(jī)系統(tǒng)結(jié)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)構(gòu)蘇東莊蘇東莊841153TP303/1284.1數(shù)字邏輯數(shù)字邏輯王玉龍王玉龍875027TP315/2087.5數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)數(shù)據(jù)元素?cái)?shù)據(jù)元素?cái)?shù)數(shù) 據(jù)據(jù)第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系，它：指數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式無(wú)關(guān)。與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式無(wú)關(guān)。線性結(jié)構(gòu)。數(shù)據(jù)之間存在前后順序關(guān)系，除第一個(gè)元素和線性結(jié)構(gòu)。數(shù)據(jù)之間存在前后順序關(guān)系，除第一個(gè)元素和最后一個(gè)元素外，其他結(jié)點(diǎn)都有唯一一個(gè)前驅(qū)和一個(gè)后繼最后一個(gè)元素外，其他結(jié)

18、點(diǎn)都有唯一一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)（一對(duì)一關(guān)系）。包括數(shù)組、鏈表、棧和隊(duì)列等。結(jié)點(diǎn)（一對(duì)一關(guān)系）。包括數(shù)組、鏈表、棧和隊(duì)列等。樹形結(jié)構(gòu)。數(shù)據(jù)之間存在順序關(guān)系，除了一個(gè)根結(jié)點(diǎn)外，樹形結(jié)構(gòu)。數(shù)據(jù)之間存在順序關(guān)系，除了一個(gè)根結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有唯一一個(gè)前驅(qū)結(jié)點(diǎn)，且可以有多個(gè)后繼結(jié)點(diǎn)其他結(jié)點(diǎn)都有唯一一個(gè)前驅(qū)結(jié)點(diǎn)，且可以有多個(gè)后繼結(jié)點(diǎn)（一對(duì)多關(guān)系）。（一對(duì)多關(guān)系）。網(wǎng)狀結(jié)構(gòu)。每個(gè)結(jié)點(diǎn)都可以有多個(gè)前驅(qū)和多個(gè)后繼結(jié)點(diǎn)（網(wǎng)狀結(jié)構(gòu)。每個(gè)結(jié)點(diǎn)都可以有多個(gè)前驅(qū)和多個(gè)后繼結(jié)點(diǎn)（多對(duì)多關(guān)系）多對(duì)多關(guān)系） 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：

19、指數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存指數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像。儲(chǔ)器的映像。 順序存儲(chǔ)結(jié)構(gòu)將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰順序存儲(chǔ)結(jié)構(gòu)將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里。它主要存儲(chǔ)線性結(jié)構(gòu)的數(shù)據(jù)。的存儲(chǔ)單元里。它主要存儲(chǔ)線性結(jié)構(gòu)的數(shù)據(jù)。 結(jié)點(diǎn)之間的關(guān)系由物理相鄰關(guān)系決定，結(jié)點(diǎn)中只有信息結(jié)點(diǎn)之間的關(guān)系由物理相鄰關(guān)系決定，結(jié)點(diǎn)中只有信息域，所以存儲(chǔ)密度大，空間利用率高。域，所以存儲(chǔ)密度大，空間利用率高。 數(shù)據(jù)結(jié)構(gòu)中第數(shù)據(jù)結(jié)構(gòu)中第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址可由以下公式求得個(gè)結(jié)點(diǎn)的存儲(chǔ)地址可由以下公式求得 LiL0(i-1)k 插入、刪除運(yùn)算會(huì)引起相應(yīng)結(jié)點(diǎn)的大量移動(dòng)。插入、刪除運(yùn)算會(huì)引起

20、相應(yīng)結(jié)點(diǎn)的大量移動(dòng)。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)打破了計(jì)算機(jī)存儲(chǔ)單元的連續(xù)性，可以將鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)打破了計(jì)算機(jī)存儲(chǔ)單元的連續(xù)性，可以將邏輯上相鄰的兩個(gè)數(shù)據(jù)元素存放在物理上不相鄰的存儲(chǔ)單邏輯上相鄰的兩個(gè)數(shù)據(jù)元素存放在物理上不相鄰的存儲(chǔ)單元中。元中。 結(jié)點(diǎn)中除數(shù)據(jù)外，還有表示鏈接信息的指針域，因此結(jié)點(diǎn)中除數(shù)據(jù)外，還有表示鏈接信息的指針域，因此與順序存儲(chǔ)結(jié)構(gòu)相比，占用更大的存儲(chǔ)空間。與順序存儲(chǔ)結(jié)構(gòu)相比，占用更大的存儲(chǔ)空間。 邏輯上相鄰結(jié)點(diǎn)物理上不一定相鄰，可用于線性表、邏輯上相鄰結(jié)點(diǎn)物理上不一定相鄰，可用于線性表、樹、圖等多種邏輯

21、結(jié)構(gòu)存儲(chǔ)樹、圖等多種邏輯結(jié)構(gòu)存儲(chǔ) 插入、刪除等操作靈活方便，不需要大量移動(dòng)結(jié)點(diǎn)，插入、刪除等操作靈活方便，不需要大量移動(dòng)結(jié)點(diǎn)，只需修改結(jié)點(diǎn)的指針值即可。只需修改結(jié)點(diǎn)的指針值即可。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件定義定義線性表（線性表（Linear List）是）是 n 個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素的有限序列（的有限序列（a1，a2，ai，an）。其中元素）。其中元素ai可以

22、是一個(gè)數(shù)、或是一個(gè)符號(hào)、也可可以是一個(gè)數(shù)、或是一個(gè)符號(hào)、也可以是更復(fù)雜的信息。以是更復(fù)雜的信息。性質(zhì)性質(zhì)同一線性表中的元素必定同一線性表中的元素必定屬于同一類數(shù)據(jù)屬于同一類數(shù)據(jù)對(duì)象對(duì)象； 除除a1元素外，每個(gè)元素都元素外，每個(gè)元素都僅有一個(gè)直接前趨僅有一個(gè)直接前趨； 除除an元素外，每個(gè)元素都元素外，每個(gè)元素都僅有一個(gè)直接后繼僅有一個(gè)直接后繼； 各元素的各元素的下標(biāo)表示下標(biāo)表示了該元素在線性表中的了該元素在線性表中的位置位置。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)組。它是數(shù)組。它是n n個(gè)類型相同的數(shù)據(jù)元素構(gòu)成的序列，它個(gè)類型相同的數(shù)據(jù)元素構(gòu)

23、成的序列，它們連續(xù)存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，且數(shù)組中的每個(gè)們連續(xù)存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，且數(shù)組中的每個(gè)元素占據(jù)相同的存儲(chǔ)空間。元素占據(jù)相同的存儲(chǔ)空間。對(duì)數(shù)組的描述通常包含下列對(duì)數(shù)組的描述通常包含下列5 5種屬性種屬性數(shù)組名稱。聲明數(shù)組第一個(gè)元素在內(nèi)存中的起始位址。數(shù)組名稱。聲明數(shù)組第一個(gè)元素在內(nèi)存中的起始位址。維度。每一元素所含數(shù)據(jù)項(xiàng)的個(gè)數(shù)，如一維數(shù)組、二維數(shù)組等維度。每一元素所含數(shù)據(jù)項(xiàng)的個(gè)數(shù)，如一維數(shù)組、二維數(shù)組等。數(shù)組下標(biāo)。元素在數(shù)組中的儲(chǔ)存位置。數(shù)組下標(biāo)。元素在數(shù)組中的儲(chǔ)存位置。數(shù)組元素個(gè)數(shù)。是數(shù)組下標(biāo)上限與數(shù)組下標(biāo)下限的差數(shù)組元素個(gè)數(shù)。是數(shù)組下標(biāo)上限與數(shù)組下標(biāo)下限的差+1。數(shù)組類型。聲明

24、此數(shù)組的類型，它決定數(shù)組元素在內(nèi)存所占有數(shù)組類型。聲明此數(shù)組的類型，它決定數(shù)組元素在內(nèi)存所占有的空間大小。的空間大小。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件鏈表：它是鏈表：它是0 0個(gè)或多個(gè)稱為結(jié)點(diǎn)的元素構(gòu)成的序列，個(gè)或多個(gè)稱為結(jié)點(diǎn)的元素構(gòu)成的序列，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外還包含一個(gè)或多個(gè)稱為指針每個(gè)結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外還包含一個(gè)或多個(gè)稱為指針的鏈接，指向鏈表中其他元素。的鏈接，指向鏈表中其他元素。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件棧結(jié)構(gòu)棧結(jié)構(gòu)定義：一種插入和刪除操作都只能在尾端進(jìn)行的線性表。允

25、許插入和刪除的定義：一種插入和刪除操作都只能在尾端進(jìn)行的線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底，另一端為固定的一端，稱為棧底(Bottom)。特點(diǎn)：是一種后進(jìn)先出特點(diǎn)：是一種后進(jìn)先出(LIFO)的線性表的線性表,也就是說，棧的操作是按后進(jìn)先出也就是說，棧的操作是按后進(jìn)先出(LIFO：Last In First Out) 的原則進(jìn)行的。的原則進(jìn)行的。棧的存儲(chǔ)結(jié)構(gòu)：棧的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)：占有一片連續(xù)的存儲(chǔ)空間順序存儲(chǔ)：占有一片連續(xù)的存儲(chǔ)空間鏈?zhǔn)酱鎯?chǔ)：也稱為鏈棧，它是一種限制運(yùn)算的鏈表，即規(guī)定鏈表中的插入和鏈?zhǔn)酱鎯?chǔ)：

26、也稱為鏈棧，它是一種限制運(yùn)算的鏈表，即規(guī)定鏈表中的插入和刪除運(yùn)算只能在鏈表開頭進(jìn)行。刪除運(yùn)算只能在鏈表開頭進(jìn)行。棧的基本運(yùn)算：棧的基本運(yùn)算：入棧（入棧（ 在棧的頂部插入元素在棧的頂部插入元素 ）出棧（刪除棧頂元素）外出棧（刪除棧頂元素）外取棧頂位置上的元素取棧頂位置上的元素置為一個(gè)空棧置為一個(gè)空棧判定是否為空棧。判定是否為空棧。 重點(diǎn)重點(diǎn) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件a1a2an-1an棧底棧底棧頂棧頂入棧入棧出棧出棧 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)

27、 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件隊(duì)列定義：僅允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，稱為隊(duì)隊(duì)列定義：僅允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，稱為隊(duì)列列(queue)(queue)。允許插入的一端稱為隊(duì)尾。允許插入的一端稱為隊(duì)尾(rear)(rear)，允許刪除的一端稱為隊(duì)，允許刪除的一端稱為隊(duì)頭頭隊(duì)列的特點(diǎn)：先進(jìn)先出隊(duì)列的特點(diǎn)：先進(jìn)先出(FIFO)(FIFO)。隊(duì)列的存儲(chǔ)結(jié)構(gòu)：隊(duì)列的存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)隊(duì)列的基本操作：隊(duì)列的基本操作：入隊(duì)列入隊(duì)列（在隊(duì)列（在隊(duì)列Q的隊(duì)尾插

28、入元素）；的隊(duì)尾插入元素）； 出隊(duì)列出隊(duì)列（刪除隊(duì)列（刪除隊(duì)列Q的隊(duì)頭元素）；的隊(duì)頭元素）； 取取出隊(duì)列出隊(duì)列Q的的隊(duì)頭元素隊(duì)頭元素； 置置隊(duì)列隊(duì)列Q為一個(gè)為一個(gè)空空隊(duì)列；隊(duì)列； 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件順序存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：將隊(duì)列中元素全部存入一個(gè)一維數(shù)組中將隊(duì)列中元素全部存入一個(gè)一維數(shù)組中, ,數(shù)組的低下標(biāo)一數(shù)組的低下標(biāo)一端為隊(duì)頭端為隊(duì)頭, ,高下標(biāo)一端為隊(duì)尾，將這樣的隊(duì)列看成是順序隊(duì)列高下標(biāo)一端為隊(duì)尾，將這樣的隊(duì)列看成是順序隊(duì)列 。若一維數(shù)。若一維數(shù)組中所有位置上都被元素裝滿，稱為隊(duì)滿，即尾指針組中所有位置上都被元素裝滿

29、，稱為隊(duì)滿，即尾指針rearrear指向一維數(shù)組最指向一維數(shù)組最后后, ,而頭指針指向一維數(shù)組開頭，稱為隊(duì)滿。而頭指針指向一維數(shù)組開頭，稱為隊(duì)滿。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：稱為鏈隊(duì)列，可以用帶頭結(jié)點(diǎn)的單鏈表作為隊(duì)列的鏈?zhǔn)椒Q為鏈隊(duì)列，可以用帶頭結(jié)點(diǎn)的單鏈表作為隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)。frontA B C D Erear 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件出隊(duì)列出隊(duì)列a1 a2 an入隊(duì)列入隊(duì)列隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 一個(gè)圖G=是一個(gè)數(shù)據(jù)結(jié)構(gòu)，它由兩部分組成

30、：一個(gè)有限集合V，它的元素稱為頂點(diǎn)；另一個(gè)有限集合E，它的元素由頂點(diǎn)對(duì)構(gòu)成，稱為邊。如果每對(duì)頂點(diǎn)之間都沒有順序，也就是說，頂點(diǎn)對(duì)(u，v)和頂點(diǎn)對(duì)(v，u)是相同的，我們說圖G是無(wú)向的，如圖（a）所示。否則，稱為有向的，邊的方向是從頂點(diǎn)u到達(dá)頂點(diǎn)v，如圖（b）所示。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 鄰接矩陣。鄰接矩陣。n n個(gè)頂點(diǎn)的鄰接矩陣是一個(gè)個(gè)頂點(diǎn)的鄰接矩陣是一個(gè)n nn n階的布爾矩陣，用來表階的布爾矩陣，用來表示圖的結(jié)點(diǎn)間的相鄰關(guān)系。示圖的結(jié)點(diǎn)間的相鄰關(guān)系。鄰接表。是鏈表一個(gè)集合，其中每一個(gè)頂

31、點(diǎn)用一個(gè)鄰接鏈表表示，鄰接表。是鏈表一個(gè)集合，其中每一個(gè)頂點(diǎn)用一個(gè)鄰接鏈表表示，該鏈表包含了和這個(gè)頂點(diǎn)鄰接的所有頂點(diǎn)（即所有和該頂點(diǎn)有邊相連該鏈表包含了和這個(gè)頂點(diǎn)鄰接的所有頂點(diǎn)（即所有和該頂點(diǎn)有邊相連的頂點(diǎn)）的頂點(diǎn)）賦權(quán)圖：圖的每條邊對(duì)應(yīng)一個(gè)數(shù)值，在實(shí)際應(yīng)用中這些數(shù)值往往是賦權(quán)圖：圖的每條邊對(duì)應(yīng)一個(gè)數(shù)值，在實(shí)際應(yīng)用中這些數(shù)值往往是距離、運(yùn)費(fèi)、時(shí)間等。這些值稱為邊的權(quán)或成本。距離、運(yùn)費(fèi)、時(shí)間等。這些值稱為邊的權(quán)或成本。鄰接矩陣。當(dāng)存在一條從結(jié)點(diǎn)i到結(jié)點(diǎn)j的邊時(shí)，矩陣元素aij的值就是這條邊的權(quán)重；當(dāng)不存在這樣一條邊時(shí)，則用一個(gè)特殊符號(hào)表示。鄰接表。鄰接表的結(jié)點(diǎn)中不僅包含鄰接結(jié)點(diǎn)的名字，還必須包含

32、相應(yīng)的邊的權(quán)重。第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 樹和森林：連通無(wú)回路的圖稱為樹，如圖樹和森林：連通無(wú)回路的圖稱為樹，如圖a a所示。有的所示。有的圖雖然不是樹，但它的每個(gè)子圖（連通分支）是樹，則圖雖然不是樹，但它的每個(gè)子圖（連通分支）是樹，則稱為森林，如圖稱為森林，如圖b b所示。所示。樹有兩個(gè)性質(zhì)：樹有兩個(gè)性質(zhì)：樹的邊數(shù)=樹的頂點(diǎn)數(shù)減1。樹的任意兩個(gè)頂點(diǎn)之間有且僅有一條通路。圖a 樹示例 圖b 森林示例 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 根樹：任選樹的一個(gè)頂點(diǎn)，將它作為樹的根。在對(duì)根

33、樹根樹：任選樹的一個(gè)頂點(diǎn)，將它作為樹的根。在對(duì)根樹的描述中，根通常放在最頂上（樹的第的描述中，根通常放在最頂上（樹的第0 0層），與根鄰層），與根鄰接的頂點(diǎn)放在根的下面（第接的頂點(diǎn)放在根的下面（第1 1層），再下面是和根距離層），再下面是和根距離兩條邊的頂點(diǎn)（第兩條邊的頂點(diǎn)（第2 2層），然后依此類推。層），然后依此類推。第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件內(nèi)部結(jié)點(diǎn)與葉子結(jié)點(diǎn)：內(nèi)部結(jié)點(diǎn)與葉子結(jié)點(diǎn)：除根結(jié)點(diǎn)外，有后繼的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)除根結(jié)點(diǎn)外，有后繼的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)沒有后繼的結(jié)點(diǎn)稱葉子結(jié)點(diǎn)（或樹葉）沒有后繼的結(jié)點(diǎn)稱葉子結(jié)點(diǎn)（或樹葉）父結(jié)點(diǎn)與子結(jié)點(diǎn)：父結(jié)點(diǎn)與子結(jié)點(diǎn)：某結(jié)點(diǎn)的上層結(jié)點(diǎn)

34、稱為它的父結(jié)點(diǎn)；某結(jié)點(diǎn)的上層結(jié)點(diǎn)稱為它的父結(jié)點(diǎn)；把其下層結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)把其下層結(jié)點(diǎn)稱為孩子結(jié)點(diǎn) 樹的深度：樹的深度：從根結(jié)點(diǎn)算起的樹的層次。從根結(jié)點(diǎn)算起的樹的層次。樹的高度：樹的高度：是從根到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。是從根到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 有序樹：是一棵根樹，樹中每一頂點(diǎn)的所有子女都是有有序樹：是一棵根樹，樹中每一頂點(diǎn)的所有子女都是有序的。序的。二叉樹：有序樹中所有頂點(diǎn)的子女個(gè)數(shù)都不超過兩個(gè)的二叉樹：有序樹中所有頂點(diǎn)的子女個(gè)數(shù)都不超過兩個(gè)的稱為二叉樹，并且每

35、個(gè)子女不是父母的左子女就是父母稱為二叉樹，并且每個(gè)子女不是父母的左子女就是父母的右子女。的右子女。 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 分析：分析：根據(jù)順序存儲(chǔ)和鏈接存儲(chǔ)的線性表優(yōu)、缺點(diǎn)的分析，可以發(fā)現(xiàn)選項(xiàng)C中順序存儲(chǔ)的線性表便于進(jìn)行增、刪操作是不正確的，而本題恰好讓我們選擇錯(cuò)誤的說法，則必是選項(xiàng)C無(wú)疑。例例1：下面關(guān)干線性表的敘述中，錯(cuò)誤的是（：下面關(guān)干線性表的敘述中，錯(cuò)誤的是（ ）。）。A）線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元）線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B）線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元）線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)

36、單元C）線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作）線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作D）線性表采用鏈接存儲(chǔ)，便于插入和刪除操作）線性表采用鏈接存儲(chǔ)，便于插入和刪除操作結(jié)論：答案應(yīng)選結(jié)論：答案應(yīng)選 C C） 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 例例2：求下列各圖的相鄰矩陣：求下列各圖的相鄰矩陣 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 線性表線性表 棧棧 隊(duì)列隊(duì)列 樹樹P195 7、9、10、13、15。 返返 回回 上一頁(yè)上一頁(yè)第第3 3章章 計(jì)算機(jī)

37、系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)可以直接識(shí)別和執(zhí)行，效率高指令的二進(jìn)制代碼難記住，人工編寫機(jī)器語(yǔ)言很繁瑣，易出錯(cuò)不同的計(jì)算機(jī)有不同的機(jī)器語(yǔ)言，因而通用性很差。 面向過程的第四代語(yǔ)言。如SQL、PB、Delphi。 面向?qū)ο蟮木幊陶Z(yǔ)言和網(wǎng)絡(luò)語(yǔ)言，如VB、VB、C+、HTML和Java。 各種軟件開發(fā)工具，如CASE不能為計(jì)算機(jī)硬件直接識(shí)別與執(zhí)行，必須通過匯編器的系統(tǒng)軟件“匯編”，才能被硬件執(zhí)行。匯編語(yǔ)言指令與機(jī)器語(yǔ)言指令一一對(duì)應(yīng)，為低級(jí)語(yǔ)言不同的計(jì)算機(jī)具有不同的匯編語(yǔ)言，記憶指令助記符較記憶指令二進(jìn)制代碼容易，但仍然繁瑣。用高級(jí)語(yǔ)言編寫的源程序必須通過“翻譯”生成目標(biāo)程序，才能被計(jì)算機(jī)所執(zhí)行。不

38、同計(jì)算機(jī)只要配備某種高級(jí)語(yǔ)言編譯程序，可運(yùn)行該高級(jí)語(yǔ)言源程序，通用性強(qiáng) 與一般的自然語(yǔ)言相比，具有嚴(yán)格、小巧、沒有二義性特點(diǎn)第一代第一代語(yǔ)言語(yǔ)言第二代第二代語(yǔ)言語(yǔ)言第三代第三代語(yǔ)言語(yǔ)言第四代第四代語(yǔ)言語(yǔ)言第五代第五代語(yǔ)言語(yǔ)言智能化語(yǔ)言，如PROLOG 重點(diǎn)第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 FORTRAN COBOL PASCAL C過程化編程語(yǔ)言過程化編程語(yǔ)言面向?qū)ο缶幊陶Z(yǔ)言面向?qū)ο缶幊陶Z(yǔ)言面向人工智能的語(yǔ)言面向人工智能的語(yǔ)言 專專 用用 語(yǔ)語(yǔ) 言言 C+ JavaHTMLSQLLISP語(yǔ)言 Prolog 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)

39、算機(jī)系統(tǒng)的軟件 概述概述面向過程的程序中，程序劃分成一個(gè)主模塊和若干個(gè)子模塊。 數(shù)據(jù)公用 數(shù)據(jù)與代碼相互分離面向?qū)ο蟪绦蛑校瑢?shù)據(jù)以及處理這些數(shù)據(jù)的例程全部封裝在一起形成一個(gè)類。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件對(duì)象、類、方法對(duì)象、類、方法對(duì)象是相關(guān)數(shù)據(jù)和方法的結(jié)合體。各個(gè)對(duì)象既是獨(dú)立的實(shí)體，又通過消息相互作用。類是同種對(duì)象的集合與抽象。類是一種抽象的數(shù)據(jù)類型，它是所有具有一定共性的對(duì)象的抽象。屬于類的某一個(gè)對(duì)象則被稱為是類的一個(gè)實(shí)例，是類的一次實(shí)例化的結(jié)果。方法是對(duì)數(shù)據(jù)的一種操作。對(duì)象、方法和消息對(duì)象、方法和消息“消息”是程序語(yǔ)句實(shí)現(xiàn)的一

40、個(gè)命令。 對(duì)象間的聯(lián)系通過消息來完成。 方法可以通過外界發(fā)“消息”來激活。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件將數(shù)據(jù)和操作這些數(shù)據(jù)的方法代碼組織將數(shù)據(jù)和操作這些數(shù)據(jù)的方法代碼組織到一起，即將數(shù)據(jù)和方法放在同一個(gè)對(duì)象到一起，即將數(shù)據(jù)和方法放在同一個(gè)對(duì)象中，可提高數(shù)據(jù)的安全性中，可提高數(shù)據(jù)的安全性一個(gè)接口能夠做多種用途，個(gè)接口能夠做多種用途，而其特定的用途由其特定的而其特定的用途由其特定的環(huán)境所決定環(huán)境所決定一個(gè)新類可以從現(xiàn)有的一個(gè)新類可以從現(xiàn)有的類中派生出來，新類具有類中派生出來，新類具有父類中的所有特性，直接父類中的所有特性，直接繼承了父類的

41、數(shù)據(jù)和方法繼承了父類的數(shù)據(jù)和方法 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 教學(xué)目的教學(xué)目的 對(duì)數(shù)據(jù)庫(kù)系統(tǒng)作進(jìn)一步的介紹，包括數(shù)據(jù)庫(kù)系統(tǒng)特點(diǎn)、數(shù)據(jù)庫(kù)管理系統(tǒng)的組成和分類，使大家對(duì)數(shù)據(jù)庫(kù)系統(tǒng)有進(jìn)一步的了解。 教學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn)與難點(diǎn) 數(shù)據(jù)庫(kù)創(chuàng)建 數(shù)據(jù)庫(kù)操作第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件教學(xué)引入 我們知道，計(jì)算機(jī)要處理大量的數(shù)據(jù)，那我們知道，計(jì)算機(jī)要處理大量的數(shù)據(jù)，那么計(jì)算機(jī)是如何保存這些數(shù)據(jù)？么計(jì)算機(jī)是如何保存這些數(shù)據(jù)？ 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)DBDB：相關(guān)信息或數(shù)據(jù)

42、的有規(guī)則的集合。：相關(guān)信息或數(shù)據(jù)的有規(guī)則的集合。數(shù)據(jù)庫(kù)管理系統(tǒng)數(shù)據(jù)庫(kù)管理系統(tǒng)DBMSDBMS：一種數(shù)據(jù)庫(kù)管理軟件，其職能是維護(hù)數(shù)據(jù)：一種數(shù)據(jù)庫(kù)管理軟件，其職能是維護(hù)數(shù)據(jù)庫(kù)，接受并完成用戶程序或命令提出的對(duì)數(shù)據(jù)進(jìn)行輸入、編輯、庫(kù)，接受并完成用戶程序或命令提出的對(duì)數(shù)據(jù)進(jìn)行輸入、編輯、排序、檢索、合并和輸出等操作請(qǐng)求。排序、檢索、合并和輸出等操作請(qǐng)求。 數(shù)據(jù)庫(kù)系統(tǒng)：由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)和用戶組成數(shù)據(jù)庫(kù)系統(tǒng)：由數(shù)據(jù)庫(kù)、數(shù)據(jù)庫(kù)管理系統(tǒng)和用戶組成 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)庫(kù)圖書館數(shù)據(jù)圖書外存書庫(kù)用戶讀者數(shù)據(jù)模型書卡格式數(shù)據(jù)庫(kù)管理系統(tǒng)圖書

43、館管理員數(shù)據(jù)的物理組織方法 圖書存放方法 用戶對(duì)數(shù)據(jù)庫(kù)的操作讀者對(duì)圖書館的訪問用戶對(duì)數(shù)據(jù)庫(kù)的操作讀者對(duì)圖書館的訪問 （使用數(shù)據(jù)操縱語(yǔ)言對(duì)數(shù)據(jù)借書、還書等（使用數(shù)據(jù)操縱語(yǔ)言對(duì)數(shù)據(jù)借書、還書等 檢索、插入、刪除、修改）檢索、插入、刪除、修改） 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件層次模型層次模型滿足的條件：有一個(gè)記錄類型沒有父結(jié)點(diǎn)。 其它記錄類型有且只有一個(gè)父結(jié)點(diǎn)。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件網(wǎng)狀模型網(wǎng)狀模型滿足的條件： 有一個(gè)以上記錄類型沒有父結(jié)點(diǎn)。 至少有一個(gè)記錄類型多于一個(gè)父結(jié)點(diǎn) 上

44、一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件關(guān)系模型關(guān)系模型 滿足的條件： 事物與事物之間的聯(lián)系用二維表格的形式來描述。表中每一行是一個(gè)記錄，在關(guān)系中稱為元組；表中每一列是一個(gè)字段，在關(guān)系中稱為屬性。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件基本概念：基本概念：表：存儲(chǔ)和管理數(shù)據(jù)的基本單元。它是一種格式化的二維數(shù)組。字段：二維表的每一列在關(guān)系中稱為屬性，每個(gè)屬性都有一個(gè)屬性名，屬性值則是各個(gè)元組屬性的取值。 字段類型：字段的數(shù)據(jù)類型及其長(zhǎng)度。記錄：是一組相關(guān)數(shù)據(jù)項(xiàng)的集合，用于描述一個(gè)對(duì)象在某方面的屬性。主鍵：

45、能夠唯一確定表中的一條記錄的一個(gè)或幾個(gè)字段。外鍵：關(guān)系中某個(gè)屬性或?qū)傩越M合并非主鍵，但卻是另一個(gè)關(guān)系的主鍵，稱此屬性或?qū)傩越M合為本關(guān)系的外部關(guān)鍵字。關(guān)系之間的聯(lián)系是通過外部關(guān)鍵字實(shí)現(xiàn)的。索引：提供對(duì)數(shù)據(jù)項(xiàng)的快速訪問。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件學(xué)生與所在系的關(guān)系學(xué)生與所在系的關(guān)系系與負(fù)責(zé)人的關(guān)系系與負(fù)責(zé)人的關(guān)系學(xué)生、課程與成績(jī)的關(guān)系學(xué)生、課程與成績(jī)的關(guān)系學(xué)號(hào)學(xué)號(hào)學(xué)生名學(xué)生名系名系名940101940202940301940401 李春梅李春梅劉劉 力力陳文秀陳文秀徐徐 兵兵 計(jì)算機(jī)系計(jì)算機(jī)系自動(dòng)化系自動(dòng)化系機(jī)械系機(jī)械系化工系化工系 學(xué)

46、號(hào)學(xué)號(hào)課程名課程名成績(jī)成績(jī)940101940202940301940401 ：語(yǔ)言語(yǔ)言：系名系名系主任名系主任名計(jì)算機(jī)系計(jì)算機(jī)系 自動(dòng)化系自動(dòng)化系 機(jī)械系機(jī)械系 化工系化工系 鄭鄭 敏敏李龍李龍 江江金金 劍劍 齊齊 晶晶 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)定義語(yǔ)言數(shù)據(jù)定義語(yǔ)言DDLDDL：用來定義數(shù)據(jù)庫(kù)的數(shù)據(jù)模型：用來定義數(shù)據(jù)庫(kù)的數(shù)據(jù)模型數(shù)據(jù)操作語(yǔ)言：用來表達(dá)用戶對(duì)數(shù)據(jù)庫(kù)的操作請(qǐng)求。數(shù)據(jù)操作語(yǔ)言：用來表達(dá)用戶對(duì)數(shù)據(jù)庫(kù)的操作請(qǐng)求。查詢數(shù)據(jù)庫(kù)中的信息向數(shù)據(jù)庫(kù)插入新的信息從數(shù)據(jù)庫(kù)中刪除信息修改數(shù)據(jù)庫(kù)中的信息SQLSQL語(yǔ)言是一個(gè)通用型的、功能

47、強(qiáng)大的關(guān)系數(shù)據(jù)庫(kù)語(yǔ)言語(yǔ)言是一個(gè)通用型的、功能強(qiáng)大的關(guān)系數(shù)據(jù)庫(kù)語(yǔ)言數(shù)據(jù)定義語(yǔ)句：數(shù)據(jù)庫(kù)的定義由 CREATE TABLE、ALTER TABLE和DROP TABLE3種語(yǔ)句構(gòu)成。數(shù)據(jù)庫(kù)查詢是數(shù)據(jù)庫(kù)的核心操作。SQL語(yǔ)言提供了SELECT語(yǔ)句進(jìn)行數(shù)據(jù)庫(kù)查詢數(shù)據(jù)更新語(yǔ)句的作用是在當(dāng)前表中添加、刪除和修改記錄。包括INSERT、DELETE和UPDATE三條語(yǔ)句。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件設(shè)計(jì)步驟設(shè)計(jì)步驟需求分析 概念結(jié)構(gòu)設(shè)計(jì)邏輯結(jié)構(gòu)設(shè)計(jì)物理結(jié)構(gòu)設(shè)計(jì)應(yīng)用程序設(shè)計(jì)系統(tǒng)運(yùn)行與維護(hù) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系

48、統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件常用數(shù)據(jù)庫(kù)開發(fā)平臺(tái)常用數(shù)據(jù)庫(kù)開發(fā)平臺(tái)AccessSQL ServerVisual FoxProPower BuilderOracleSybase 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)發(fā)展史發(fā)展史文件系統(tǒng)階段文件系統(tǒng)階段人工管理階段人工管理階段關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng) 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件65主要是指主要是指5050年代中期以前的這段時(shí)間，此時(shí)的計(jì)算機(jī)年代中期以前的這段時(shí)間，此時(shí)的計(jì)算機(jī)還很簡(jiǎn)陋，連完整的操作系統(tǒng)都沒有。因此，數(shù)據(jù)只還很簡(jiǎn)陋，

49、連完整的操作系統(tǒng)都沒有。因此，數(shù)據(jù)只能放在卡片上或其他介質(zhì)上，由人來手工管理。能放在卡片上或其他介質(zhì)上，由人來手工管理。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件66主要是指主要是指5050年代后期到年代后期到6060年代中期的這段時(shí)間，此時(shí)的年代中期的這段時(shí)間，此時(shí)的計(jì)算機(jī)已經(jīng)有了操作系統(tǒng)。在操作系統(tǒng)基礎(chǔ)之上建立的計(jì)算機(jī)已經(jīng)有了操作系統(tǒng)。在操作系統(tǒng)基礎(chǔ)之上建立的文件系統(tǒng)已經(jīng)成熟并廣泛應(yīng)用。因此，人們自然想到用文件系統(tǒng)已經(jīng)成熟并廣泛應(yīng)用。因此，人們自然想到用文件把大量的數(shù)據(jù)存儲(chǔ)在磁盤這種介質(zhì)上，以實(shí)現(xiàn)對(duì)數(shù)文件把大量的數(shù)據(jù)存儲(chǔ)在磁盤這種介質(zhì)上，以實(shí)現(xiàn)

50、對(duì)數(shù)據(jù)的永久保存和自動(dòng)管理以及維護(hù)；據(jù)的永久保存和自動(dòng)管理以及維護(hù)； 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件67與文件系統(tǒng)相比的優(yōu)點(diǎn)與文件系統(tǒng)相比的優(yōu)點(diǎn)：數(shù)據(jù)是結(jié)構(gòu)化的面向系統(tǒng)，減少了數(shù)據(jù)冗余可以用數(shù)據(jù)結(jié)構(gòu)化查詢語(yǔ)言對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行操作 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件XML/RDBMSXML/RDBMS混合數(shù)據(jù)處理將在未來得到快速的發(fā)展混合數(shù)據(jù)處理將在未來得到快速的發(fā)展數(shù)據(jù)集成和數(shù)據(jù)倉(cāng)庫(kù)將向內(nèi)容管理過渡數(shù)據(jù)集成和數(shù)據(jù)倉(cāng)庫(kù)將向內(nèi)容管理過渡基于基于InternetInternet的自動(dòng)化管理

51、的自動(dòng)化管理支持商業(yè)智能成重點(diǎn)支持商業(yè)智能成重點(diǎn)數(shù)據(jù)庫(kù)技術(shù)與多學(xué)科技術(shù)的有機(jī)結(jié)合數(shù)據(jù)庫(kù)技術(shù)與多學(xué)科技術(shù)的有機(jī)結(jié)合 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 分析：分析：在數(shù)據(jù)庫(kù)系統(tǒng)階段，數(shù)據(jù)的冗余度只能說明顯減小了,節(jié)約了存儲(chǔ)空間而沒有完全消除，因此說“無(wú)數(shù)據(jù)冗余”不夠準(zhǔn)確。例例3：數(shù)據(jù)管理技術(shù)隨著計(jì)算機(jī)技術(shù)的發(fā)展而發(fā)展。數(shù)據(jù)庫(kù)階段具：數(shù)據(jù)管理技術(shù)隨著計(jì)算機(jī)技術(shù)的發(fā)展而發(fā)展。數(shù)據(jù)庫(kù)階段具有很多特點(diǎn)，但下面列出的特點(diǎn)中哪一個(gè)不是數(shù)據(jù)庫(kù)階段的特點(diǎn)？有很多特點(diǎn)，但下面列出的特點(diǎn)中哪一個(gè)不是數(shù)據(jù)庫(kù)階段的特點(diǎn)？（ ）A）無(wú)數(shù)據(jù)冗余）無(wú)數(shù)據(jù)冗余 B）采用復(fù)雜的

52、數(shù)據(jù)結(jié)構(gòu)）采用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)C）數(shù)據(jù)共享）數(shù)據(jù)共享 D）數(shù)據(jù)具有較高的獨(dú)立性）數(shù)據(jù)具有較高的獨(dú)立性結(jié)論：答案應(yīng)選結(jié)論：答案應(yīng)選 A A） 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件數(shù)據(jù)庫(kù)管理系統(tǒng)的分類數(shù)據(jù)庫(kù)管理系統(tǒng)的分類 關(guān)系數(shù)據(jù)庫(kù)關(guān)系數(shù)據(jù)庫(kù) 數(shù)據(jù)庫(kù)的發(fā)展歷史數(shù)據(jù)庫(kù)的發(fā)展歷史 現(xiàn)階段常用數(shù)據(jù)庫(kù)簡(jiǎn)介現(xiàn)階段常用數(shù)據(jù)庫(kù)簡(jiǎn)介 數(shù)據(jù)庫(kù)技術(shù)的新發(fā)展數(shù)據(jù)庫(kù)技術(shù)的新發(fā)展 P195 17P195 17、1818、1919 返返 回回 上一頁(yè)上一頁(yè)第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件教學(xué)目的教學(xué)目的介紹高級(jí)語(yǔ)言源程序是如何被計(jì)算機(jī)識(shí)別，對(duì)編譯原理有大致了解教

53、學(xué)重點(diǎn)與難點(diǎn)教學(xué)重點(diǎn)與難點(diǎn) 詞法分析 語(yǔ)法分析 中間代碼生成 代碼優(yōu)化 目標(biāo)代碼生成 表格管理和出錯(cuò)處理第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件教學(xué)引入 我們向計(jì)算機(jī)編寫的代碼如何被計(jì)算機(jī)識(shí)別？我們向計(jì)算機(jī)編寫的代碼如何被計(jì)算機(jī)識(shí)別？ 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件 編譯程序編譯程序是實(shí)現(xiàn)將源程序是實(shí)現(xiàn)將源程序“翻譯翻譯”為目標(biāo)程序的系統(tǒng)為目標(biāo)程序的系統(tǒng)軟件，它由若干個(gè)程序組成，故又稱為軟件，它由若干個(gè)程序組成，故又稱為編譯系統(tǒng)編譯系統(tǒng)。 翻譯外文資料的大致過程：翻譯外文資料的大致過程：識(shí)別單詞語(yǔ)法分析初譯加工高級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序（源程序（

54、源程序.C）C語(yǔ)言語(yǔ)言編譯器編譯器連接裝連接裝配程序配程序運(yùn)行機(jī)器運(yùn)行機(jī)器語(yǔ)言程序語(yǔ)言程序目標(biāo)程序目標(biāo)程序 .obj可執(zhí)行程序可執(zhí)行程序 .exe結(jié)果結(jié)果 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 詞法分析：對(duì)源程序逐個(gè)字符地進(jìn)行掃描，以識(shí)別出各個(gè)單詞符號(hào)，并分別歸類。詞法分析：對(duì)源程序逐個(gè)字符地進(jìn)行掃描，以識(shí)別出各個(gè)單詞符號(hào)，并分別歸類。語(yǔ)法分析：根據(jù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則，將詞法分析器所提供的單詞符號(hào)串構(gòu)成語(yǔ)法分析：根據(jù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則，將詞法分析器所提供的單詞符號(hào)串構(gòu)成一個(gè)語(yǔ)法分析樹。一個(gè)語(yǔ)法分析樹。語(yǔ)義分析：檢查各句子的語(yǔ)法樹。語(yǔ)義分析：檢查各句子的語(yǔ)法樹。中間代碼的生成：向目標(biāo)代碼

55、過度的一種編碼，其形式盡可能和機(jī)器的匯編語(yǔ)言相中間代碼的生成：向目標(biāo)代碼過度的一種編碼，其形式盡可能和機(jī)器的匯編語(yǔ)言相似，以便于下一步的代碼生成。似，以便于下一步的代碼生成。代碼優(yōu)化：對(duì)中間代碼程序做局部或全局優(yōu)化，可使最后生成的目標(biāo)代碼程序運(yùn)行代碼優(yōu)化：對(duì)中間代碼程序做局部或全局優(yōu)化，可使最后生成的目標(biāo)代碼程序運(yùn)行更快，占用存儲(chǔ)空間更小。更快，占用存儲(chǔ)空間更小。目標(biāo)代碼生成：由代碼生成器生成目標(biāo)機(jī)器的目標(biāo)代碼程序，并完成數(shù)據(jù)分段、選目標(biāo)代碼生成：由代碼生成器生成目標(biāo)機(jī)器的目標(biāo)代碼程序，并完成數(shù)據(jù)分段、選定寄存器等工作，然后生成機(jī)器可執(zhí)行的代碼。定寄存器等工作，然后生成機(jī)器可執(zhí)行的代碼。重點(diǎn)

56、上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件高級(jí)語(yǔ)言的單詞屬性的類型：高級(jí)語(yǔ)言的單詞屬性的類型： 基本字（保留字） 標(biāo)識(shí)符（如變量名、數(shù)組名、過程名等） 常數(shù) 運(yùn)算符 + - * / 棧頂運(yùn)算符，則將其壓入運(yùn)算符棧； 若當(dāng)前運(yùn)算符棧頂運(yùn)算符，則彈出棧頂運(yùn)算符和操作數(shù)棧中的相應(yīng)操作數(shù)，完成其運(yùn)算，并把計(jì)算結(jié)果壓入操作數(shù)棧中； 若當(dāng)前運(yùn)算符=棧頂運(yùn)算符，則彈出運(yùn)算符棧的棧頂符號(hào)，并讀入下一單詞，什么計(jì)算也不進(jìn)行。反復(fù)執(zhí)行上述過程，直至句末符反復(fù)執(zhí)行上述過程，直至句末符“#”#”，操作數(shù)棧中只剩下一個(gè)，操作數(shù)棧中只剩下一個(gè)結(jié)果值，表明分析正確。否則出錯(cuò)。結(jié)果

57、值，表明分析正確。否則出錯(cuò)。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件中間代碼的定義中間代碼的定義中間代碼是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)，它的表現(xiàn)形式應(yīng)該既有利于后階段的代碼優(yōu)化，又要在邏輯上便于理解和最終機(jī)器（目標(biāo)）指令代碼生成 。 常用的中間代碼形式常用的中間代碼形式三元式四元式逆波蘭式 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件三元式表示：三元式表示： (OP ARG1 ARG2 ) 即: (運(yùn)算符 第一運(yùn)算項(xiàng) 第二運(yùn)算項(xiàng)) 例：對(duì)于例：對(duì)于K=(I+J)K=(I+J)* *K K可翻譯成：可翻

58、譯成： （1） + I J (2) * (1) K (3) = K (2)三元式表示實(shí)質(zhì)上是一種樹形結(jié)構(gòu)的矩陣描述，它等價(jià)于上面語(yǔ)法樹。三元式表示實(shí)質(zhì)上是一種樹形結(jié)構(gòu)的矩陣描述，它等價(jià)于上面語(yǔ)法樹。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件表示：表示： (OP ARG1 ARG2 RESULT ) (OP ARG1 ARG2 RESULT ) (運(yùn)算符 第一運(yùn)算項(xiàng) 第二運(yùn)算項(xiàng) 運(yùn)算結(jié)果) 例：對(duì)于例：對(duì)于K=(I+J)K=(I+J)* *K K可翻譯成：可翻譯成： + I J T1 * T1 K T2 = T2 K四元式與三元式的相似與區(qū)別四元式與

59、三元式的相似與區(qū)別相似：排列順序和實(shí)際計(jì)算順序相同區(qū)別：四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的，較三元式易于改變，有利于后一階段的代碼優(yōu)化操作。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件逆波蘭表示法是一種把運(yùn)算符號(hào)寫在運(yùn)算項(xiàng)之后的表示方逆波蘭表示法是一種把運(yùn)算符號(hào)寫在運(yùn)算項(xiàng)之后的表示方法，也稱法，也稱后綴表示法后綴表示法： 例： a+b 可表示為 ab+ a*b 可表示為 ab * 對(duì)于賦值語(yǔ)句 K=（I+J）*K，可翻譯成 I J+K*K= 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件代碼優(yōu)化的分類及常用方

60、法代碼優(yōu)化的分類及常用方法邏輯優(yōu)化（純代碼優(yōu)化）：在目標(biāo)代碼生成之前，對(duì)語(yǔ)法分析后的中間代碼進(jìn)行優(yōu)化，主要完成程序結(jié)構(gòu)上的等價(jià)變換。 在生成目標(biāo)代碼過程中，根據(jù)機(jī)器所提供的設(shè)備條件，為充分利用機(jī)器指令系統(tǒng)和通用寄存器等而進(jìn)行的優(yōu)化，這類優(yōu)化于具體的機(jī)器有關(guān)。 常用方法常用方法刪除多余的運(yùn)算、合并已知量、代碼外提、強(qiáng)度削弱、變換循環(huán)控制條件、復(fù)寫傳播、刪除無(wú)用賦值等。 物理優(yōu)化與具體的機(jī)器有關(guān)。 上一頁(yè)上一頁(yè) 返返 回回下一頁(yè)下一頁(yè) 第第3 3章章 計(jì)算機(jī)系統(tǒng)的軟件計(jì)算機(jī)系統(tǒng)的軟件例如，有代碼序列：例如，有代碼序列： A=B+C+D E=B+C+F W=B+C+Y刪除多余的運(yùn)算可優(yōu)化為：刪除多余