第三部分 計(jì)算機(jī)軟件系統(tǒng)

1、計(jì)算機(jī)軟件系統(tǒng)計(jì)算機(jī)系統(tǒng)操作系統(tǒng)程序=算法+數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)系統(tǒng)的概念1硬件系統(tǒng)說硬件系統(tǒng)說 計(jì)算機(jī)系統(tǒng)是由運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備和輸出設(shè)備這5個(gè)部件組成的。這種說法其實(shí)僅針對(duì)計(jì)算機(jī)的硬件而言，比較片面。計(jì)算機(jī)系統(tǒng)的概念2硬件與軟件結(jié)合說硬件與軟件結(jié)合說 計(jì)算機(jī)系統(tǒng)是由硬件系統(tǒng)和軟件系統(tǒng)兩大部分組成的。硬件構(gòu)成計(jì)算機(jī)系統(tǒng)的物理存在，軟件則是計(jì)算機(jī)系統(tǒng)的靈魂。 計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)軟件計(jì)算機(jī)軟件計(jì)算機(jī)硬件計(jì)算機(jī)硬件輸出設(shè)備輸出設(shè)備輸入設(shè)備輸入設(shè)備存儲(chǔ)器存儲(chǔ)器控制器控制器運(yùn)算器運(yùn)算器程序程序數(shù)據(jù)數(shù)據(jù)文檔文檔計(jì)算機(jī)系統(tǒng)是由硬件和軟件組成的，兩者缺一不可！計(jì)算機(jī)系統(tǒng)是由硬件和軟件組成的，

2、兩者缺一不可！計(jì)算機(jī)系統(tǒng)的概念l 軟件：是計(jì)算機(jī)可以運(yùn)行的各種程序、數(shù)據(jù)及其相關(guān)文檔的總和。l 程序：是軟件的主體，是各種計(jì)算機(jī)任務(wù)的處理對(duì)象和處理規(guī)則的描述，是指令序列的符號(hào)表示，一般保存在存儲(chǔ)介質(zhì)（如硬盤和光盤）中。l 數(shù)據(jù)：程序運(yùn)行過程中需要處理的對(duì)象和必須使用的一些參數(shù)（如三角函數(shù)表、英漢詞典等）。l 文檔：與程序開發(fā)、維護(hù)及操作有關(guān)的一些技術(shù)資料（如設(shè)計(jì)報(bào)告、使用指南和維護(hù)手冊(cè)等），是為了便于了解程序所需的闡明性資料，文檔對(duì)于使用和維護(hù)軟件尤其重要。 計(jì)算機(jī)系統(tǒng)的概念3廣義系統(tǒng)說廣義系統(tǒng)說 計(jì)算機(jī)系統(tǒng)是由 人員（people）、 數(shù)據(jù)（data）、 設(shè)備（equipment）、 程序

3、（program）和 規(guī)程（procedure）5個(gè)部分組成的，只有把它們有機(jī)地結(jié)合在一起，才能完成各種任務(wù)。 程序程序設(shè)備設(shè)備規(guī)程規(guī)程數(shù)據(jù)數(shù)據(jù)人員人員計(jì)算機(jī)軟件的分類按照不同的標(biāo)準(zhǔn)，可以將軟件劃分為不同的種類。按產(chǎn)權(quán)按產(chǎn)權(quán)性質(zhì)性質(zhì)商品軟件商品軟件 共享軟件共享軟件 自由軟件自由軟件按軟件按軟件用途用途系統(tǒng)軟件系統(tǒng)軟件應(yīng)用軟件應(yīng)用軟件計(jì)算機(jī)軟件的分類系統(tǒng)軟件軟件系統(tǒng)應(yīng)用軟件 操作系統(tǒng)語言處理程序數(shù)據(jù)庫管理系統(tǒng)服務(wù)性程序Office組件工具軟件用戶程序 從應(yīng)用的角度出發(fā)（軟件用途），計(jì)算機(jī)軟件可以分為系統(tǒng)軟件和應(yīng)用軟件。 計(jì)算機(jī)軟件的分類u 系統(tǒng)軟件系統(tǒng)軟件 系統(tǒng)軟件是管理、監(jiān)控和維護(hù)計(jì)算機(jī)資源

4、（包括硬件和軟件）的軟件，使得它們可以協(xié)調(diào)工作。u 應(yīng)用軟件應(yīng)用軟件 應(yīng)用軟件是為了某種特定的通途而開發(fā)的軟件。由于計(jì)算機(jī)應(yīng)用已經(jīng)滲透到社會(huì)生活的各個(gè)方面，因而計(jì)算機(jī)的應(yīng)用軟件也是多種多樣的，一般包括通用應(yīng)用軟件和定制應(yīng)用軟件。 通用應(yīng)用軟件的類別和功能類別類別功能功能舉例舉例文字處理文本編輯、文字處理、桌面排版等WPS、Word、FrontPage等電子表格表格定義、計(jì)算和處理等Excel等圖形、圖像圖像處理、幾何圖形繪制、動(dòng)畫制作等AutoCAD、Photoshop、3D Max、CoreDraw等演示、簡報(bào)幻燈片、演講報(bào)告制作等Powerpoint等媒體播放播放各種數(shù)字音頻和視頻文件Wi

5、ndows Media Player、Real Player、暴風(fēng)影音、千千靜聽等網(wǎng)絡(luò)通信電子郵件、聊天、IP電話、網(wǎng)絡(luò)文件管理、瀏覽等Outlook Express、MSN、QQ、Mail等圖像瀏覽工具查看圖像等ACDSee等網(wǎng)絡(luò)電視播放網(wǎng)絡(luò)視頻等PPS、PPTV、PPlive、UUSee等各類軟件的層次應(yīng)用程序（用戶）語言處理程序數(shù)據(jù)庫管理系統(tǒng)服務(wù)性程序操作系統(tǒng)裸機(jī)n 所謂層次關(guān)系指的是內(nèi)層軟件向外層軟件提供服務(wù)，外層軟件在內(nèi)層軟件的支持下才能運(yùn)行。 n 系統(tǒng)軟件支持應(yīng)用軟件的開發(fā)和運(yùn)行；應(yīng)用軟件處在軟件系統(tǒng)的最外層，直接面向用戶，為用戶服務(wù)。計(jì)算機(jī)軟件的分類 如果按照軟件權(quán)益的處置方式（

6、產(chǎn)權(quán)性質(zhì)）來進(jìn)行分類，可以分為：商品軟件、共享軟件和自由軟件。 u商品軟件商品軟件 作為商品進(jìn)行交易的軟件，版權(quán)嚴(yán)格，用戶需要付費(fèi)才可以在授權(quán)范圍內(nèi)使用。 u共享軟件共享軟件（也稱為試用軟件）（也稱為試用軟件） 具有版權(quán)，可免費(fèi)試用一段時(shí)間，允許拷貝和散發(fā)（但不可修改），試用期滿后需交費(fèi)才能繼續(xù)使用。u自由軟件自由軟件 （開放源代碼軟件）開放源代碼軟件） 用戶可共享，并允許隨意拷貝、修改其源代碼，允許銷售和自由傳播。但是，對(duì)軟件源代碼的任何修改都必須向所有用戶公開，還必須允許此后的用戶享有進(jìn)一步拷貝和修改的自由。操作系統(tǒng)的概念n 操作系統(tǒng)是管理計(jì)算機(jī)的資源，組織計(jì)算機(jī)的工作流程以及方便用戶使用

7、的程序集合。也就是說，操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)資源的管理者和指揮者。n 操作系統(tǒng)是計(jì)算機(jī)中最重要的，也是核心的系統(tǒng)軟件，它是其它系統(tǒng)軟件及應(yīng)用軟件運(yùn)行的基礎(chǔ)。操作系統(tǒng)的基本特征（1）并發(fā)性 并發(fā)是指在計(jì)算機(jī)系統(tǒng)中可以同時(shí)運(yùn)行多個(gè)程序。 （2）共享性 共享是指多個(gè)用戶的程序可以共同使用計(jì)算機(jī)系統(tǒng)的資源。 （3）虛擬性 虛擬性指操作系統(tǒng)可以把一臺(tái)物理設(shè)備變成若干個(gè)邏輯上 的對(duì)應(yīng)設(shè)備。 （4）異步性 異步性又稱不確定性，不確定性是與確定性相互依存的。 操作系統(tǒng)的主要作用（1）是用戶和計(jì)算機(jī)硬件之間的接口 （2）是計(jì)算機(jī)系統(tǒng)資源的管理者 （3）為用戶提供友善的人機(jī)界面 操作系統(tǒng)虛擬機(jī)操作系統(tǒng)虛擬機(jī) 硬件硬

8、件 操作系統(tǒng)操作系統(tǒng)其他系統(tǒng)軟件其他系統(tǒng)軟件應(yīng)用軟件應(yīng)用軟件各類用戶各類用戶操作系統(tǒng)的啟動(dòng)過程ROMBIOS硬硬 盤盤RAM 執(zhí)行自舉裝入程序執(zhí)行自舉裝入程序執(zhí)執(zhí)行行引引導(dǎo)導(dǎo)程程序序序序讀讀出出引引導(dǎo)導(dǎo)程程CPU 執(zhí)行執(zhí)行加電自檢程序加電自檢程序 裝入引導(dǎo)程序裝入引導(dǎo)程序 裝入操作系統(tǒng)裝入操作系統(tǒng)CMOS？從從何何處處啟啟動(dòng)動(dòng)運(yùn)運(yùn)行行操操作作系系統(tǒng)統(tǒng)顯示初始界面顯示初始界面CMOS的設(shè)置 CMOS基本參數(shù)包括硬盤、日期/時(shí)間、啟動(dòng)順序、密碼以及保存等。 操作系統(tǒng)的主要功能u處理器管理（任務(wù)管理）處理器管理（任務(wù)管理） 處理器管理就是指CPU管理，讓它有條不紊地工作。n“任務(wù)”指的是要計(jì)算機(jī)做的

9、一件事，計(jì)算機(jī)執(zhí)行一個(gè)任 務(wù)通常就對(duì)應(yīng)著運(yùn)行一個(gè)應(yīng)用程序n“單任務(wù)處理”與“多任務(wù)處理”n單任務(wù)處理：在任何時(shí)刻只允許有一個(gè)任務(wù)執(zhí)行，直到該任務(wù)完成后才能啟動(dòng)下一個(gè)程序，任務(wù)是順序執(zhí)行的。n多任務(wù)處理：允許計(jì)算機(jī)同時(shí)執(zhí)行多個(gè)任務(wù)，任務(wù)是并發(fā)執(zhí)行的。n多任務(wù)處理的優(yōu)點(diǎn)：n大大提高了用戶的工作效率n大大提高了計(jì)算機(jī)的使用效率前臺(tái)任務(wù)與后臺(tái)任務(wù)l 前臺(tái)任務(wù)：當(dāng)多個(gè)任務(wù)都在運(yùn)行時(shí)，其中只有一個(gè)任務(wù)正在被用戶直接操作，這個(gè)任務(wù)稱為前臺(tái)任務(wù)，該任務(wù)對(duì)應(yīng)的屏幕窗口稱為活動(dòng)窗口。l 后臺(tái)任務(wù)：除前臺(tái)任務(wù)外，所有其它任務(wù)均為后臺(tái)任務(wù)，與之相應(yīng)的屏幕窗口是非活動(dòng)窗口。 l 前臺(tái)任務(wù)與后臺(tái)任務(wù)的區(qū)別：l前臺(tái)任務(wù)對(duì)應(yīng)

10、的窗口(活動(dòng)窗口)位于其它窗口的前面l活動(dòng)窗口的標(biāo)題欄與非活動(dòng)窗口顏色不同Windows任務(wù)管理器 利用Windows任務(wù)管理器查看系統(tǒng)中任務(wù)的運(yùn)行狀態(tài)、CPU的使用率、內(nèi)存的使用狀況等。l“應(yīng)用程序”選項(xiàng)卡：顯示當(dāng)前正在運(yùn)行的任務(wù)。l“進(jìn)程”選項(xiàng)卡：顯示當(dāng)前正在運(yùn)行的所有進(jìn)程，包括正在運(yùn)行的系統(tǒng)進(jìn)程。 l“性能”選項(xiàng)卡：以圖形的方式顯示CPU和內(nèi)存的使用情況。 CPU時(shí)間片輪轉(zhuǎn)方法 時(shí)間CPU任務(wù)1任務(wù)2任務(wù)3任務(wù)4任務(wù)5目的：讓目的：讓CPUCPU輪流為所有任務(wù)服務(wù)輪流為所有任務(wù)服務(wù)操作系統(tǒng)的主要功能u存儲(chǔ)管理存儲(chǔ)管理 所謂存儲(chǔ)管理主要是指對(duì)內(nèi)存的管理，將有限的內(nèi)存空間合理地分配，以滿足多

11、任務(wù)運(yùn)行的需求。內(nèi)內(nèi) 存存 儲(chǔ)儲(chǔ) 器器其它計(jì)算機(jī)硬件其它計(jì)算機(jī)硬件應(yīng)用程序接口應(yīng)用程序接口(API)處理器處理器管理管理文件文件管理管理存儲(chǔ)存儲(chǔ)管理管理文件系統(tǒng)，網(wǎng)絡(luò)通信程序文件系統(tǒng)，網(wǎng)絡(luò)通信程序設(shè)備驅(qū)動(dòng)程序設(shè)備驅(qū)動(dòng)程序設(shè)備設(shè)備管理管理窗口窗口管理管理應(yīng)用應(yīng)用 程序程序1應(yīng)用應(yīng)用 程序程序2應(yīng)用應(yīng)用 程序程序3用戶用戶 接口外殼接口外殼應(yīng)用應(yīng)用 程序程序k用用 戶戶操操 作作 系系 統(tǒng)統(tǒng)正在運(yùn)行正在運(yùn)行的應(yīng)用程的應(yīng)用程序序內(nèi)存的擴(kuò)充n 虛擬存儲(chǔ)技術(shù)（即虛擬內(nèi)存技術(shù)，簡稱虛存）。n 虛擬存儲(chǔ)技術(shù)的核心思想就是把內(nèi)存與外存有機(jī)的結(jié)合起來使用，利用外存空間來彌補(bǔ)實(shí)際內(nèi)存空間，從而得到一個(gè)容量很大的“

12、內(nèi)存”。n 虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn)的基本思想是：當(dāng)一個(gè)任務(wù)啟動(dòng)并向內(nèi)存裝入程序和數(shù)據(jù)時(shí)，只將當(dāng)前要執(zhí)行的一部分程序和數(shù)據(jù)裝入內(nèi)存，其余部分放在外存的虛擬空間中，然后開始執(zhí)行程序。當(dāng)需要的指令和數(shù)據(jù)不在內(nèi)存中時(shí)，則由存儲(chǔ)管理程序?qū)⑺辈糠謴耐獯娴奶摂M空間中調(diào)入實(shí)際內(nèi)存，同時(shí)將暫時(shí)不用的部分調(diào)出到虛擬空間中，實(shí)現(xiàn)內(nèi)存和外存虛擬空間的動(dòng)態(tài)交換。虛擬存儲(chǔ)器 用戶可以使用“任務(wù)管理器”查看內(nèi)存的狀態(tài)。l總的物理內(nèi)存大小l可用物理內(nèi)存大小l總的虛擬內(nèi)存大小l可用虛擬內(nèi)存大小等操作系統(tǒng)的主要功能u文件管理文件管理 文件管理又稱文件系統(tǒng)，計(jì)算機(jī)中的各種程序和數(shù)據(jù)均為計(jì)算機(jī)的軟件資源，它們都以文件的形式存儲(chǔ)在外存中。

13、文件管理主要是指對(duì)軟件的管理，方便用戶對(duì)文件進(jìn)行存取和檢索等。文件的概念l文件：存儲(chǔ)在外存中的一組相關(guān)信息的集合，例如一個(gè)程序、一篇文章、一張數(shù)碼相片、一個(gè)MP3歌曲、一封電子郵件等都可以是文件的內(nèi)容。l文件名：為了便于區(qū)別，每個(gè)文件都有自己的名字，是文件的標(biāo)識(shí)，用戶可以通過文件名來使用該文件。文件名由兩部分組成： .擴(kuò)展名，其中文件名是文件的主要標(biāo)識(shí)，不可省略，文件名最多可包含255個(gè)中文或西文字符；文件擴(kuò)展名（類型名）由“.”加34個(gè)英文字母組成，可以省略。l記錄：文件由若干個(gè)相關(guān)記錄組成，每個(gè)記錄都是一些相關(guān)信息的集合。例如：每一行程序、每一行數(shù)據(jù)等。 文件的組成 每一個(gè)文件都由2部分組

14、成：文件名等文件名等說明信息說明信息文文 件件 內(nèi)內(nèi) 容容 文件名和文件擴(kuò)展名 文件大小(長度) 在磁盤上存放的起始位置 文件時(shí)間(創(chuàng)建時(shí)間、最近修改時(shí)間、最近訪問時(shí)間等) 文件創(chuàng)建者 文件屬性系統(tǒng)文件系統(tǒng)文件隱藏文件隱藏文件存檔文件存檔文件只讀文件只讀文件 壓縮壓縮 加密加密編制索引編制索引 文件的存儲(chǔ)n Windows、UNIX等操作系統(tǒng)都采用樹形目錄結(jié)構(gòu)，該樹從根結(jié)點(diǎn)向下，每個(gè)結(jié)點(diǎn)是一個(gè)目錄（或稱文件夾），多次分叉的樹枝是各級(jí)子目錄，末端的葉結(jié)點(diǎn)是文件。 n 文件目錄在Windows中稱為文件夾。n 每個(gè)邏輯盤(物理盤或硬盤上的分區(qū))是一個(gè)根文件夾。n 文件夾中既可包含文件，也可包含文件

15、夾 (子文件夾)，子文件夾又可存放文件和子文件夾, 形成樹狀多級(jí)文件夾結(jié)構(gòu)。根節(jié)點(diǎn)和中間節(jié)根節(jié)點(diǎn)和中間節(jié)點(diǎn)都是文件夾點(diǎn)都是文件夾葉節(jié)點(diǎn)都是文件葉節(jié)點(diǎn)都是文件根文件夾數(shù)據(jù)應(yīng)用程序P1.jpgQQ.exe01.docT1.txtPS.exe系統(tǒng)軟件教案課件資料02.ppt03.pdf操作系統(tǒng)的主要功能u設(shè)備管理設(shè)備管理 設(shè)備管理是指對(duì)各種各樣外部設(shè)備的管理，方便用戶使用輸入/輸出設(shè)備（I/O）。主要包括對(duì)I/O設(shè)備的分配、啟動(dòng)、完成和回收。 常用操作系統(tǒng)簡介 u Windows操作系統(tǒng)操作系統(tǒng) Windows操作系統(tǒng)是一種在個(gè)人計(jì)算機(jī)上運(yùn)行的系統(tǒng)軟件，由美國微軟（Microsoft）公司開發(fā)，Wi

16、ndows的原意是“窗戶”、“視窗”，可以看作是一款視窗操作系統(tǒng)。 Microsoft Windows系列操作系統(tǒng)，最初是在微軟給IBM機(jī)器設(shè)計(jì)的MS-DOS的基礎(chǔ)上設(shè)計(jì)的圖形操作系統(tǒng)。Windows提供了多任務(wù)圖形界面以及統(tǒng)一的應(yīng)用程序接口，使得在Windows環(huán)境下運(yùn)行應(yīng)用程序的操作大為簡化。常用操作系統(tǒng)簡介 u UNIX操作系統(tǒng)操作系統(tǒng) UNIX操作系統(tǒng)是當(dāng)今世界上應(yīng)用較廣泛的主流操作系統(tǒng)，它適用于小型和微型計(jì)算機(jī)領(lǐng)域，是一個(gè)通用的、交互式的分時(shí)操作系統(tǒng)。在1969年由美國Bell實(shí)驗(yàn)室開發(fā)研制，1972年用C語言改寫，提高了它的兼容性和可讀性。 UNIX系統(tǒng)的特點(diǎn)是：結(jié)構(gòu)緊湊、功能強(qiáng)大

17、、使用方便、易于擴(kuò)充、修改、維護(hù)、可移植性好、互操作性強(qiáng)、網(wǎng)絡(luò)通信功能豐富、安全可靠等。常用操作系統(tǒng)簡介 u Linux操作系統(tǒng)操作系統(tǒng) Linux是一種“類UNIX”的操作系統(tǒng)。它是一種外觀和性能與UNIX相同或更好的操作系統(tǒng)，Linux產(chǎn)品成功的模仿了UNIX系統(tǒng)和功能，但是源代碼和UNIX一點(diǎn)關(guān)系都沒有。Linux是自由軟件，免費(fèi)并向世人公開源代碼，吸引了對(duì)該操作系統(tǒng)感興趣的人們共同工作。 Linux操作系統(tǒng)的優(yōu)勢(shì)反映在網(wǎng)絡(luò)服務(wù)器方面，其內(nèi)核中包含許多網(wǎng)絡(luò)協(xié)議，已成為網(wǎng)絡(luò)上最普遍的服務(wù)器架構(gòu)模式。Linux操作系統(tǒng)作為一個(gè)多用戶、多任務(wù)的操作系統(tǒng)，支持多工作平臺(tái)和多處理器。程序=算法+數(shù)

18、據(jù)結(jié)構(gòu) 著名的計(jì)算機(jī)科學(xué)家沃思（N.Wirth）教授曾提出：程序=算法+數(shù)據(jù)結(jié)構(gòu)。程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。算法u 算法的概念算法的概念n 在日常生活中，人們做事情都會(huì)按照一定的規(guī)則和步驟。n 所謂算法，就是為了解決特定問題而采取的步驟和方法，即對(duì)特定問題求解步驟的一種描述。 n 人們常說：“軟件的主體是程序，程序的核心是算法”。 算法u 算法的特性算法的特性（1）確定性：算法的每個(gè)步驟都必須有確切的定義，不能含糊不清或存在歧義。（2）有窮性：算法必須保證執(zhí)行有限步后能夠結(jié)束。（3）可行性：算法原則

19、上應(yīng)該能夠被計(jì)算機(jī)執(zhí)行，并得到確定的運(yùn)算結(jié)果。（4）輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，取自特定的數(shù)據(jù)對(duì)象集合。（5）輸出：一個(gè)算法有1個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果，沒有輸出的算法是毫無意義的。算法u 算法的表示算法的表示算法描述種類算法描述種類算法描述說明算法描述說明優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)自然語言日常生活中使用的語言表示通俗易懂文字冗長，不精確流程圖特定的表示算法的圖形符號(hào)形象、直觀、邏輯結(jié)構(gòu)明了在算法復(fù)雜時(shí)，難以表示清楚，容易出錯(cuò)偽代碼介于自然語言與程序設(shè)計(jì)語言的文字與符號(hào)代碼簡單，結(jié)構(gòu)清晰，可讀性強(qiáng)隨意性較強(qiáng)算法u 算法的分析算法的分析 算法分析就是衡量算法性能的過程，通過算法分析得

20、知不同算法的優(yōu)劣。對(duì)算法的分析主要是對(duì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度的衡量。 l時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：n算法的時(shí)間復(fù)雜度即時(shí)間代價(jià)很容易理解，它是依據(jù)該算法運(yùn)行時(shí)所 消耗的時(shí)間多少來決定的。 n 一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)有關(guān)。一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是關(guān)于問題規(guī)模n的某個(gè)函數(shù)f（n），時(shí)間復(fù)雜度不是一個(gè)精確的執(zhí)行次數(shù)，而是估算的數(shù)量級(jí)。用數(shù)量級(jí)估算的方法，使用O標(biāo)記算法時(shí)間復(fù)雜度的結(jié)果，記做：T（n）=O（f（n）。l空間復(fù)雜性：空間復(fù)雜性：除原始數(shù)據(jù)之外，額外占用的存儲(chǔ)空間的大小。數(shù)據(jù)結(jié)構(gòu) n 數(shù)據(jù)結(jié)構(gòu)研究如何在計(jì)算機(jī)中表示被處理的對(duì)象及對(duì)象之 間的關(guān)系，即如

21、何組織數(shù)據(jù)。n 算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù) 據(jù)的存儲(chǔ)結(jié)構(gòu)。精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)可使算法獲得更高 的時(shí)間效率或空間效率。n 數(shù)據(jù)結(jié)構(gòu)包括幾個(gè)方面：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)運(yùn)算。數(shù)據(jù)結(jié)構(gòu) u邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。 線性結(jié)構(gòu)線性結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)樹形結(jié)構(gòu)樹形結(jié)構(gòu)集合結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) u存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱物理結(jié)構(gòu)，是指邏輯結(jié)構(gòu)如何在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。 常見的有：l 順序存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)元素按某種順序依次存放在存儲(chǔ)器的存儲(chǔ)單元中，它的特點(diǎn)是邏輯上相鄰的數(shù)據(jù)在物理位置上也相鄰。 l 鏈接存儲(chǔ)結(jié)構(gòu) 利用地址指針來表示元素之

22、間的邏輯關(guān)系，也就是說數(shù)據(jù)所占的存儲(chǔ)單元分為兩個(gè)部分：數(shù)據(jù)本身的信息和數(shù)據(jù)后繼元素所對(duì)應(yīng)的存儲(chǔ)單元的地址。 數(shù)據(jù)結(jié)構(gòu) u存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) （1）順序存儲(chǔ)結(jié)構(gòu) a2是a1的直接后繼元素陳辰王平劉明李麗10011002100310041005低地址高地址a1a2a2是a1的后繼元素a1a2低地址高地址陳辰李麗劉明王平10011002100310041005100410051003（2）鏈接存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) u數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算 定義在數(shù)據(jù)結(jié)構(gòu)上的一組運(yùn)算（操作）及其實(shí)現(xiàn)方法。常用的運(yùn)算有：插入、刪除、更新、檢索和排序等。程序設(shè)計(jì) 計(jì)算機(jī)語言，方便人與計(jì)算機(jī)之間進(jìn)行信息交流的語言，這種語言也叫程序設(shè)

23、計(jì)語言，它是編寫計(jì)算機(jī)程序的重要工具。 隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，計(jì)算機(jī)語言也在不斷的發(fā)展，一般分為機(jī)器語言、匯編語言和高級(jí)語言。 程序設(shè)計(jì)語言u(píng)機(jī)器語言機(jī)器語言n 機(jī)器語言就是計(jì)算機(jī)的指令系統(tǒng)n 指令是使用二進(jìn)制（0和1）編碼表示的n 優(yōu)點(diǎn)：可以直接被計(jì)算機(jī)執(zhí)行n 缺點(diǎn)：記不住、難理解、效率低、不易維護(hù)不同的機(jī)器語言程序，相互不兼容n 現(xiàn)在已不直接用機(jī)器語言編制程序！B8 5E 01B8 6D 0203 D8B8 7C 042B C3操作碼操作數(shù)地址1條機(jī)器指令程序設(shè)計(jì)語言u(píng)匯編語言匯編語言n 用助記符號(hào)來表示機(jī)器指令中的操作符與操作數(shù)。n 優(yōu)點(diǎn)：n操作數(shù)直接使用十進(jìn)制n程序相對(duì)容易理解n 缺點(diǎn)：n大型程序難以開發(fā)n依賴于具體計(jì)