歡迎大家！計算機基礎課件全文共91頁，當前為第1頁。計算機基礎知識計算機組成計算機操作系統計算機網絡數據庫軟件工程數據結構、算法、程序計算機基礎課件全文共91頁，當前為第2頁。1.計算機系統的組成計算機是由存儲器、運算器、控制器、輸入設備和輸出設備等五大部件所構成。輸入設備控制器運算器輸出設備存儲器輸入信息輸出信息請求信號、數據流控制信號馮諾依曼，1945計算機基礎課件全文共91頁，當前為第3頁。計算機系統硬件系統軟件系統主機外設外存儲器(硬盤、光驅)輸入/輸出設備系統軟件應用軟件辦公處理軟件輔助工作軟件實時控制軟件……操作系統……CPU主板、顯卡、聲卡內存1.計算機系統的組成計算機基礎課件全文共91頁，當前為第4頁。系統軟件應用軟件計算機的軟件系統包括1.計算機系統的組成計算機基礎課件全文共91頁，當前為第5頁。（1）操作系統（2）語言處理程序（3）支撐軟件（4）數據庫系統

系統軟件是指控制和協調計算機及其外部設備，支持應用軟件的開發和運行的軟件。其主要的功能是進行調度、監控和維護系統等等。系統軟件是用戶和裸機的接口。1.計算機系統的組成計算機基礎課件全文共91頁，當前為第6頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第7頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第8頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第9頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第10頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第11頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第12頁。2.計算機操作系統計算機基礎課件全文共91頁，當前為第13頁。計算機網絡的發展的四個階段：1.第一階段：“誕生階段”以主機為中心的聯機終端系統，“計算機－終端”系統2.第二階段：“形成階段”以通信子網為中心的主機互連，“計算機-計算機”網絡3.第三階段：互聯互通階段體系結構標準化網絡層次結構，對每層進行了精確定義4.第四階段：高速網絡技術階段Internet網時代的到來

3.計算機網絡計算機基礎課件全文共91頁，當前為第14頁。1.第一階段：“誕生階段”

以主機為中心的聯機終端系統特征：終端(Terminal)共享主機(Host)的軟硬件資源單臺主機：執行計算和通信任務多臺終端：執行用戶交互(終端集中器/終端服務器)連接方式：本地或遠程TTTTTHOST通信線路3.計算機網絡計算機基礎課件全文共91頁，當前為第15頁。2.第二階段：“形成階段

”

通信子網為中心的主機互連特征多個終端聯機系統互聯，形成了多主機互聯網絡網絡結構從“主機－終端”轉變為“主機－主機”HOSTHOSTHOSTTTTTTTTTTT通信線路3.計算機網絡計算機基礎課件全文共91頁，當前為第16頁。演變階段1通信任務從主機中分離，由通信控制處理機（CCP）完成CCP：處理主機之間通信任務的專用計算機CCPCCPHOSTHOSTTTTTTTCCPHOSTTT3.計算機網絡計算機基礎課件全文共91頁，當前為第17頁。兩層網絡概念的出現由CCP組成的傳輸網絡——通信子網，提供信息傳輸服務建立在通信子網基礎上的主機集合——資源子網，提供計算資源CCPCCPHOSTHOSTTTTTTTCCPHOSTTTT通信子網3.計算機網絡計算機基礎課件全文共91頁，當前為第18頁。19演變階段2通信子網規模逐漸擴大私有→社會公用公用數據通信網PSTNX.25優點降低用戶系統建設成本提高通信線路利用率兼容性好公用數據通信網HOSTHOSTTTTTTTHOSTTTTT3.計算機網絡計算機基礎課件全文共91頁，當前為第19頁。3.第三階段：互聯互通階段

體系結構標準化網絡為什么需要標準化？不同網絡設備之間的兼容性和互操作性是推動網絡體系結構的標準化的原動力而兼容性和互操作性的最終目的仍是資源共享標準化的時機？先制定標準再開發還是先開發再制定標準？各廠商、研究機構、大學在網絡技術、方法、理論等方面的研究日趨成熟是基礎3.計算機網絡計算機基礎課件全文共91頁，當前為第20頁。4.第四階段：高速網絡技術階段因特網的出現標志著網絡時代的到來因特網是全球性的網絡豐富的信息和便利的使用是其規模迅速增長的主要驅動力截止到2000年,Internet的規模為網絡數達到105數量級,主機數達到107數量級,

用戶數108數量級，主干速率大于2.5Gbit/s3.計算機網絡計算機基礎課件全文共91頁，當前為第21頁。計算機網絡體系結構的形成相互通信的兩個計算機系統必須高度協調工作才行，而這“協調”是相當復雜的。“分層”可將龐大而復雜的問題，轉化為若干較小的局部問題，而這些較小的局部問題就比較易于研究和處理。3.計算機網絡計算機基礎課件全文共91頁，當前為第22頁。OSI與

TCP/IP體系結構的比較應用層傳輸層網絡層表示層會話層數據鏈路層物理層7654321OSI的體系結構應用層網絡接口層網際層IP(各種應用層協議如TELNET,FTP,SMTP等)傳輸層(TCP

或

UDP)TCP/IP的體系結構3.計算機網絡計算機基礎課件全文共91頁，當前為第23頁。分層的好處1.各層之間是獨立的。2.靈活性好。3.結構上可分割開。4.易于實現和維護。5.能促進標準化工作。若層數太少，就會使每一層的協議太復雜。層數太多又會在描述和綜合各層功能的系統工程任務時遇到較多的困難。3.計算機網絡計算機基礎課件全文共91頁，當前為第24頁。五層協議的體系結構： TCP/IP是四層的體系結構：應用層、運輸層、網際層和網絡接口層。

最下面的網絡接口層并沒有具體內容。

因此往往采取折中的辦法，即綜合

OSI和

TCP/IP的優點，采用一種只有五層協議的體系結構。3.計算機網絡計算機基礎課件全文共91頁，當前為第25頁。計算機

1

向計算機

2

發送數據5432154321計算機

1AP2AP1計算機

2應用程序數據應用層首部H510100110100101比特流110101110101注意觀察加入或剝去首部（尾部）的層次應用程序數據H5應用程序數據H4H5應用程序數據H3H4H5應用程序數據H4運輸層首部H3網絡層首部H2鏈路層首部T2鏈路層尾部3.計算機網絡計算機基礎課件全文共91頁，當前為第26頁。網絡接口卡網絡接口卡（NIC，簡稱網卡）能夠使工作站、服務器、打印機或其他節點通過網絡介質接收并發送數據。網絡接口卡常被稱為網絡適配器。屬于OSI模型的物理層。3.計算機網絡計算機基礎課件全文共91頁，當前為第27頁。中繼器中繼器是一種放大或模擬數字信號的網絡連接設備。中繼器屬于OSI模型中的物理層。它們只是轉發信號，但同時也轉發了信號的噪聲，3.計算機網絡計算機基礎課件全文共91頁，當前為第28頁。集線器集線器能與網絡中的打印服務器、交換器、文件服務器或其他的設備連接。集線器屬于OSI模型中的物理層。3.計算機網絡計算機基礎課件全文共91頁，當前為第29頁。網橋網橋這種設備看上去有點像中繼器。它具有單個的輸入端口和輸出端口，它與中繼器的不同之處就在于它能夠解析它收發的數據。網橋屬于OSI模型的數據鏈路層

3.計算機網絡計算機基礎課件全文共91頁，當前為第30頁。交換機交換機屬于OSI模型的數據鏈路層，并且，它還能夠解析出MAC地址信息。事實上，它相當于多個網橋。3.計算機網絡計算機基礎課件全文共91頁，當前為第31頁。路由器路由器是一種多端口設備，它可以連接不同傳輸速率并運行于各種環境的局域網和廣域網，也可以采用不同的協議。路由器屬于OSI模型的網絡層設備。3.計算機網絡計算機基礎課件全文共91頁，當前為第32頁。數據庫系統的產生與發展數據庫基本概念1）數據(Data)數據是描述事物的符號記錄。2）信息(Information)

通常被認為是具有一定含義的、經過加工的、對決策有價值的數據。3）數據庫(Database,DB)

數據庫是指長期存儲在計算機內，有組織的、可共享的數據集合。4.數據庫計算機基礎課件全文共91頁，當前為第33頁。數據結構是所研究的對象類型的集合。用于描述數據的靜態特征。包括：數據的類型、內容和性質的對象（事物）；數據之間聯系的對象（聯系）。數據操作是對數據庫中各種對象的實例允許執行的操作的集合。用于描述數據的動態特征。完整性約束完整性規則的集合。如性別只能有男和女之分，年齡不能為0等。數據模型概述4.數據庫計算機基礎課件全文共91頁，當前為第34頁。最常用的數據模型1．層次模型

層次模型（HierarchicalModel）是一種以記錄某一事物的類型為根節點的有向樹。4.數據庫計算機基礎課件全文共91頁，當前為第35頁。2．網狀模型最常用的數據模型網狀模型是層次模型的擴展，表示多個從屬關系的層次結構，呈現一種交叉關系的網狀結構。4.數據庫計算機基礎課件全文共91頁，當前為第36頁。關系模型（RelationalModel）是指雖具有相關性而非從屬性的平行的數據之間按照某種序列排列的集合關系。關系模型是由若干個關系模式組成的集合，關系模式的實例稱為關系，而每個關系實際上就是一張二維表格。4.數據庫最常用的數據模型3．關系模型計算機基礎課件全文共91頁，當前為第37頁。基本概念關系：一個關系對應一張表元組：表中的一行屬性：表中的一列主碼：表中的某個屬性或屬性組，它可以唯一確定一個元組域：屬性的取值范圍分量：元組中的一個屬性值關系模式：對關系的描述4.數據庫計算機基礎課件全文共91頁，當前為第38頁。關系的性質1)關系中每一數據項不可再分，是最基本的單位。2)每一列數據項是同屬性的。列數根據需要而設，且各列的順序是任意的。3)每一行記錄由一個事物的諸多屬性項構成。記錄的順序可以是任意的。4)一個關系是一張二維表，不允許有相同的字段名，也不允許有相同的記錄行。5)每個關系都有稱之為關鍵字的屬性集唯一標識各元組。4.數據庫計算機基礎課件全文共91頁，當前為第39頁。軟件工程把整個軟件開發過程視為一項工程，把整個工程分成若干個階段，制定每個階段的計劃，逐個實施。軟件生命周期的六個步驟，即制定計劃、需求分析、設計、程序編碼、測試及運行維護。5.軟件工程計算機基礎課件全文共91頁，當前為第40頁。5.軟件工程軟件開發V模型計算機基礎課件全文共91頁，當前為第41頁。制定計劃確定要開發軟件系統的總目標給出功能、性能、可靠性以及接口等方面的要求完成該軟件任務的可行性研究估計可利用的資源(硬件、軟件、人力等)、成本、效益、開發進度制定出完成開發任務的實施計劃，連同可行性研究報告，提交管理部門審查5.軟件工程計算機基礎課件全文共91頁，當前為第42頁。需求分析和定義對用戶提出的要求進行分析并給出詳細的定義編寫軟件需求說明書或系統功能說明書及初步的系統用戶手冊評審5.軟件工程計算機基礎課件全文共91頁，當前為第43頁。軟件設計概要設計

—把各項需求轉換成軟件的體系結構。結構中每一組成部分都是意義明確的模塊，每個模塊都和某些需求相對應。詳細設計

—對每個模塊要完成的工作進行具體的描述，為源程序編寫打下基礎。編寫設計說明書，提交評審。5.軟件工程計算機基礎課件全文共91頁，當前為第44頁。程序編寫(軟件實現)把軟件設計轉換成計算機可以接受的程序代碼，即寫成以某一種特定程序設計語言表示的“源程序清單”寫出的程序應當結構良好、清晰易讀，且與設計相一致5.軟件工程計算機基礎課件全文共91頁，當前為第45頁。軟件測試單元測試，查找各模塊在功能和結構上存在的問題并加以糾正集成測試，將已測試過的模塊按一定順序組裝起來按規定的各項需求，逐項進行有效性測試，決定已開發的軟件是否合格，能否交付用戶使用5.軟件工程計算機基礎課件全文共91頁，當前為第46頁。運行/維護改正性維護運行中發現了軟件中的錯誤需要修正適應性維護為了適應變化了的軟件工作環境，需做適當變更完善性維護為了增強軟件的功能需做變更預防性維護“把今天的方法學用于昨天的系統以滿足明天的需要”。為進一步改進軟件打基礎5.軟件工程計算機基礎課件全文共91頁，當前為第47頁。基本概念和術語數據(Data)：在計算機科學中是所有能輸入到計算機中并能被計算機程序處理的符號的總稱。數據包含的內容隨著計算機的發展而擴大例如：數字、字母、漢字、圖形、圖像、聲音都稱為數據。注意：專業術語中，數據已經不是“數值”。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第48頁。基本概念和術語數據元素(DataElement)：數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。人是一個數據元素，通常作為整體進行處理。數據元素還不是組成數據的最小單位。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第49頁。基本概念和術語數據結構（DataStructures):帶結構的數據元素的集合。

結構：數據元素之間存在的約束關系數據元素之間不是孤立的，而是相互之間存在著一種或多種特定的關系6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第50頁。一種數據結構包含下面三個方面：邏輯結構：表示數據元素之間的邏輯關系。

Data_Structure=(D,S)物理結構：數據結構在計算機存儲器中的映射（或表示），又稱存儲結構，也稱存儲表示結構的行為特征作用于數據結構上的運算。例如：檢索，插入，刪除等。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第51頁。邏輯結構根據數據元素間關系的基本特性，有四種基本數據結構集合——數據元素間除“同屬于一個集合”外，無其它關系線性結構——一個對一個，如線性表、棧、隊列樹形結構——一個對多個，如樹圖形結構——多個對多個，如圖6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第52頁。（1）順序存儲（向量存儲）以存儲位置的相對位置來表示數據元素之間的邏輯關系。存儲結構(storagestructure)：數據結構在計算機中的表示。要在計算機中實現數據結構的操作，如何在計算機中實現對各種數據及其關系的表示？6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第53頁。順序存儲存儲地址

存儲內容1345

元素11346

元素21347

元素31348

元素41349

元素5

……

……6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第54頁。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內容Loc(元素i)=Lo+（i-1)*m順序存儲6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第55頁。

(2)鏈式存儲以附加信息（指針）表示數據元素間的邏輯關系所有元素存放在可以不連續的存儲單元中，但元素之間的關系可以通過地址確定，邏輯上相鄰的元素存放到計算機內存后不一定是相鄰的。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第56頁。1536元素21400元素11346元素3∧元素41345h存儲地址

存儲內容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈式存儲

h6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第57頁。

(3)索引存儲使用該方法存放元素的同時，還建立附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是：（關鍵字，地址），其中的關鍵字是能唯一標識一個結點的那些數據項。

(4)散列存儲通過構造散列函數，用函數的值來確定元素存放的地址。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第58頁。數據的邏輯結構數據的存儲結構數據的運算

線性結構非線性結構

順序存儲

鏈式存儲線性表棧隊列樹形結構圖形結構數據結構的三個方面：：檢索、排序、插入、刪除、修改等6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第59頁。算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。算法是指解決問題的一種方法或一個過程。算法和算法分析6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第60頁。N.沃思（NiklausWirth)教授提出：

程序=算法+數據結構程序設計：為計算機處理問題編制一組指令集算法：怎樣處理問題，解決問題的策略數據結構：要處理的信息如何表示，問題的表示模型6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第61頁。N.沃思（NiklausWirth)教授提出：

程序=算法+數據結構以上公式說明了如下兩個問題：（1）數據上的算法決定如何構造和組織數據（算法→數據結構）。（2）算法的設計依賴于作為基礎的數據結構（數據結構→算法）。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第62頁。算法的5個特性有窮性：算法必須總是在執行有窮步后結束，每一步在有窮時間內完成。確定性：組成算法的每條指令是清晰，無歧義的。可行性：算法是可執行的。輸入：有零個或多個外部提供的量作為輸入。輸出：算法產生至少一個量作為輸出。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第63頁。數據結構的主要內容數學模型解題思路

問題抽象數據結構算法

數據類型程序設計編碼運行圖計算機解決問題的一般過程6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第64頁。

算法設計的要求

1.正確性：算法應當滿足具體問題的需求。正確的含義有4個層次的級別：1、程序不含語法錯誤；2、程序對于幾種輸入數據有正確的結果；3、程序對于典型、苛刻、刁難性的數據有正確的結果；4、對于一切合法的輸入數據都有正確結果。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第65頁。

算法設計的要求

2.可讀性：有助于人對算法的理解。

算法主要是為了人的閱讀和交流，晦澀難懂的程序容易隱藏錯誤，難以調試和修改。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第66頁。

算法設計的要求

3.健壯性：適當處理任何錯誤輸入。

對于輸入非法的數據時，算法能夠給出反應作出處理，而不會出現莫名奇妙的錯誤。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第67頁。

算法設計的要求

4.效率和低存儲量需求。

效率是指算法執行的時間，執行時間短的算法效率高。存儲量需求是指算法執行過程中所需要的最大存儲空間，顯然是越低越好。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第68頁。

算法效率的度量

算法的時間代價(或稱時間復雜度)

執行時間越短，算法效率越高。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第69頁。度量算法的執行時間(1)事后統計法：運行程序后通過若干統計數據來分辨優劣。缺陷：必須先運行依算法編制的程序，一些大型算法要運行則比較費時費力；所得時間的統計量依賴于計算機的硬件、軟件等環境因素，容易掩蓋算法本身的優劣。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第70頁。度量算法的執行時間(2)事前分析估算法依據的影響因素：依據的算法選用何種策略；問題的規模；書寫程序的語言；編譯程序時所產生的機器代碼的質量；機器執行指令的速度。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第71頁。度量算法的執行時間(2)事前分析估算法分析方法：找出算法中最重要的操作——基本操作，計算它們的運行次數。基本操作通常是算法最內層循環中最費時的操作6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第72頁。

時間復雜度一般情況下，算法中基本操作重復執行次數是問題規模n的某個函數f(n),算法的時間量度記作

T(n)=O(f(n))

它表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同。稱做算法的漸近時間復雜度（asymptotictimecomplexity),簡稱時間復雜度。

6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第73頁。時間復雜度的意義反映了隨著問題規模的增加，算法消耗時間的增加度。問題規模增加執行時間增長快執行時間增長慢算法效率低算法效率高6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第74頁。算法A：inti,sum=0,n=100;for(i=1;i<=n;i++){sum=sum+i;}printf(“%d”,sum);算法B：intsum=0,n=100;sum=(1+n)*n/2;printf(“%d”,sum);哪個算法效率更高？6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第75頁。由于時間復雜度考慮的只是問題規模n的增長率，則在難以精確計算基本操作執行次數的情況下，只需求出它關于n的增長率或階即可。f(n)=3n2+n6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第76頁。for(i=0;i<n;i++)S(i);for(i=0;i<n;i++)for(j=0;j<n;j++)S(i,j);f(n)=n，時間復雜度為O(n)f(n)=n2，時間復雜度為O(n2)S(i);f(n)=1，時間復雜度為O(1)6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第77頁。例：NXN矩陣相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0; for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];} 則時間復雜度：

f(n)=n3T(n)=O(n3)6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第78頁。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第79頁。評價算法運行時間的標準最好時間復雜度 算法對具有長度為n的任何輸入的最短運行時間最壞時間復雜度 算法對具有長度為n的任何輸入的最長運行時間平均時間復雜度 假設長度為n的所有可能的輸入概率相同的情況下算法的平均運行時間。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第80頁。算法的存儲空間需求算法的空間代價(或稱空間復雜度)本身所用指令、常數、變量和輸入數據對數據進行操作的工作單元為實現計算所需信息的輔助空間6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第81頁。1.2什么是計算機語言計算機語言發展階段：機器語言（由0和1組成的指令）符號語言（用英文字母和數字表示指令）高級語言（接近于人的自然語言和數學語言）

面向過程的語言

（非結構化的語言、結構化語言）

面向對象的語言低級語言計算機語言：人和計算機交流信息的、計算機和人都能識別的語言。6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第82頁。機器語言是計算機能直接識別，機器語言是由二進制的指令代碼組成的。如01001001匯編語言是面向機器的程序設計語言，它也和計算機的型號有關。如-o7010-o7111-q高級語言采用比較接近自然語言的文字和表達式等一系列符號來表示。如ift>10i=i+1elsei=i-1

endif分類機器語言匯編語言高級語言（2）語言處理程序6.數據結構、算法、程序計算機基礎課件全文共91頁，當前為第83頁。C