1、計算機基礎(chǔ)知識計算機基礎(chǔ)知識計算機組成計算機組成計算機操作系統(tǒng)計算機操作系統(tǒng)計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)數(shù)據(jù)庫數(shù)據(jù)庫軟件工程軟件工程數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序陳 海 新2017.04.271. 計算機系統(tǒng)的組成計算機系統(tǒng)的組成計算機是由存儲器、運算器、控制器、輸入設(shè)備和輸出設(shè)備等五大部件所構(gòu)成。 輸入設(shè)備輸入設(shè)備控制器控制器運算器運算器輸出設(shè)備輸出設(shè)備存儲器存儲器輸入信息輸入信息輸出信息輸出信息請求信號、數(shù)據(jù)流請求信號、數(shù)據(jù)流控制信號控制信號馮諾依曼，1945計算機系統(tǒng)計算機系統(tǒng)硬件系統(tǒng)硬件系統(tǒng)軟件系統(tǒng)軟件系統(tǒng)主機主機外設(shè)外設(shè)外存儲器外存儲器( (硬盤、光驅(qū)硬盤、光驅(qū)) )輸入輸入/ /

2、輸出設(shè)備輸出設(shè)備系統(tǒng)軟件系統(tǒng)軟件應(yīng)用軟件應(yīng)用軟件辦公處理軟件辦公處理軟件輔助工作軟件輔助工作軟件實時控制軟件實時控制軟件操作系統(tǒng)操作系統(tǒng)CPUCPU主板、顯卡、聲卡主板、顯卡、聲卡內(nèi)存內(nèi)存1. 計算機系統(tǒng)的組成計算機系統(tǒng)的組成系系統(tǒng)統(tǒng)軟軟件件應(yīng)應(yīng)用用軟軟件件1. 計算機系統(tǒng)的組成計算機系統(tǒng)的組成（1）操作系統(tǒng)）操作系統(tǒng) （2）語言處理程序）語言處理程序 （3）支撐軟件）支撐軟件 （4）數(shù)據(jù)庫系統(tǒng)）數(shù)據(jù)庫系統(tǒng) 系統(tǒng)軟件是指控制和協(xié)調(diào)計算機及其外部設(shè)備，支系統(tǒng)軟件是指控制和協(xié)調(diào)計算機及其外部設(shè)備，支持應(yīng)用軟件的開發(fā)和運行的軟件。其主要的功能是進持應(yīng)用軟件的開發(fā)和運行的軟件。其主要的功能是進行調(diào)度、

3、監(jiān)控和維護系統(tǒng)等等。系統(tǒng)軟件是行調(diào)度、監(jiān)控和維護系統(tǒng)等等。系統(tǒng)軟件是用戶和裸用戶和裸機的接口機的接口。 1. 計算機系統(tǒng)的組成計算機系統(tǒng)的組成2. 計算機操作系統(tǒng)計算機操作系統(tǒng)2. 計算機操作系統(tǒng)計算機操作系統(tǒng)2. 計算機操作系統(tǒng)計算機操作系統(tǒng)2. 計算機操作系統(tǒng)計算機操作系統(tǒng)2. 計算機操作系統(tǒng)計算機操作系統(tǒng)2. 計算機操作系統(tǒng)計算機操作系統(tǒng)2. 計算機操作系統(tǒng)計算機操作系統(tǒng)計算機網(wǎng)絡(luò)的發(fā)展的四個階段：1.第一階段：第一階段：“誕生階段誕生階段”以主機為中心的聯(lián)機終端系統(tǒng)，“計算機終端”系統(tǒng)2.第二階段：第二階段：“形成階段形成階段 ”以通信子網(wǎng)為中心的主機互連，“計算機-計算機”網(wǎng)絡(luò)3.第

4、三階段：互聯(lián)互通階段第三階段：互聯(lián)互通階段 體系結(jié)構(gòu)標(biāo)準(zhǔn)化網(wǎng)絡(luò)層次結(jié)構(gòu)，對每層進行了精確定義4.第四階段：高速網(wǎng)絡(luò)技術(shù)階段第四階段：高速網(wǎng)絡(luò)技術(shù)階段Internet網(wǎng)時代的到來 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)1.第一階段：第一階段：“誕生階段誕生階段” 以主機為中心的聯(lián)機終端系統(tǒng)特征：終端(Terminal)共享主機(Host)的軟硬件資源單臺主機：執(zhí)行計算和通信任務(wù)多臺終端：執(zhí)行用戶交互(終端集中器/終端服務(wù)器)連接方式：本地或遠(yuǎn)程TTTTTHOST通信線通信線路路3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)2.第二階段：第二階段：“形成階段形成階段 ” 通信子網(wǎng)為中心的主機互連特征 多個終端聯(lián)機系統(tǒng)互聯(lián)，形成了

5、多主機互聯(lián)網(wǎng)絡(luò) 網(wǎng)絡(luò)結(jié)構(gòu)從“主機終端” 轉(zhuǎn)變?yōu)椤爸鳈C主機”HOSTHOSTHOSTTTTTTTTTTT通信線路3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)演變階段1 通信任務(wù)從主機中分離，由通信控制處理機（CCP）完成 CCP：處理主機之間通信任務(wù)的專用計算機CCPCCPHOSTHOSTTTTTTTCCPHOSTTT3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)兩層網(wǎng)絡(luò)概念的出現(xiàn)由CCP組成的傳輸網(wǎng)絡(luò)通信子網(wǎng)通信子網(wǎng)，提供信息傳輸服務(wù)建立在通信子網(wǎng)基礎(chǔ)上的主機集合資源子網(wǎng)資源子網(wǎng)，提供計算資源CCPCCPHOSTHOSTTTTTTTCCPHOSTTTT通信子網(wǎng)通信子網(wǎng)3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)18演變階段2 通信子網(wǎng)規(guī)模逐漸擴大

6、私有社會公用 公用數(shù)據(jù)通信網(wǎng) PSTN X.25 優(yōu)點 降低用戶系統(tǒng)建設(shè)成本 提高通信線路利用率 兼容性好公用數(shù)據(jù)公用數(shù)據(jù)通信網(wǎng)通信網(wǎng)HOSTHOSTTTTTTTHOSTTTTT3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)3.第三階段：互聯(lián)互通階段第三階段：互聯(lián)互通階段 體系結(jié)構(gòu)標(biāo)準(zhǔn)化網(wǎng)絡(luò)為什么需要標(biāo)準(zhǔn)化？ 不同網(wǎng)絡(luò)設(shè)備之間的兼容性和互操作性是推動網(wǎng)絡(luò)體系結(jié)構(gòu)的標(biāo)準(zhǔn)化的原動力 而兼容性和互操作性的最終目的仍是資源共享標(biāo)準(zhǔn)化的時機？ 先制定標(biāo)準(zhǔn)再開發(fā)還是先開發(fā)再制定標(biāo)準(zhǔn)？ 各廠商、研究機構(gòu)、大學(xué)在網(wǎng)絡(luò)技術(shù)、方法、理論等方面的研究日趨成熟是基礎(chǔ)3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)4.第四階段：高速網(wǎng)絡(luò)技術(shù)階段第四階段：高速網(wǎng)

7、絡(luò)技術(shù)階段 因特網(wǎng)的出現(xiàn)標(biāo)志著網(wǎng)絡(luò)時代的到來因特網(wǎng)是全球性的網(wǎng)絡(luò)豐富的信息和便利的使用是其規(guī)模迅速增長的主要驅(qū)動力截止到2000年, Internet的規(guī)模為 網(wǎng)絡(luò)數(shù)達(dá)到105數(shù)量級, 主機數(shù)達(dá)到107數(shù)量級, 用戶數(shù)108數(shù)量級，主干速率大于2.5Gbit/s3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò) 計算機網(wǎng)絡(luò)體系結(jié)構(gòu)的形成相互通信的兩個計算機系統(tǒng)必須高度協(xié)調(diào)工作才行，而這“協(xié)調(diào)”是相當(dāng)復(fù)雜的。 “分層”可將龐大而復(fù)雜的問題，轉(zhuǎn)化為若干較小的局部問題，而這些較小的局部問題就比較易于研究和處理。 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)OSI 與 TCP/IP 體系結(jié)構(gòu)的比較 應(yīng)用層傳輸層網(wǎng)絡(luò)層表示層會話層數(shù)據(jù)鏈路層物理

8、層7654321OSI 的體系結(jié)構(gòu)應(yīng)用層網(wǎng)絡(luò)接口層網(wǎng)際層 IP (各種應(yīng)用層協(xié)議如TELNET, FTP, SMTP 等)傳輸層(TCP 或 UDP)TCP/IP 的體系結(jié)構(gòu)3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)分層的好處分層的好處 1. 各層之間是獨立的。2. 靈活性好。3. 結(jié)構(gòu)上可分割開。4. 易于實現(xiàn)和維護。5. 能促進標(biāo)準(zhǔn)化工作。 若層數(shù)太少，就會使每一層的協(xié)議太復(fù)雜。層數(shù)太多又會在描述和綜合各層功能的系統(tǒng)工程任務(wù)時遇到較多的困難。 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)五層協(xié)議的體系結(jié)構(gòu) ：TCP/IP 是四層的體系結(jié)構(gòu)：應(yīng)用層、運輸層、網(wǎng)際層和網(wǎng)絡(luò)接口層。最下面的網(wǎng)絡(luò)接口層并沒有具體內(nèi)容。因此往往采取折

9、中的辦法，即綜合 OSI 和 TCP/IP的優(yōu)點，采用一種只有五層協(xié)議的體系結(jié)構(gòu) 。 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)計算機 1 向計算機 2 發(fā)送數(shù)據(jù) 5432154321計算機 1AP2AP1計算機 2應(yīng) 用 程 序 數(shù) 據(jù)應(yīng)用層首部H510100110100101 比 特 流 110101110101注意觀察加入或剝?nèi)ナ撞浚ㄎ膊浚┑膶哟螒?yīng) 用 程 序 數(shù) 據(jù)H5應(yīng) 用 程 序 數(shù) 據(jù)H4H5應(yīng) 用 程 序 數(shù) 據(jù)H3H4H5應(yīng) 用 程 序 數(shù) 據(jù)H4運輸層首部H3網(wǎng)絡(luò)層首部H2鏈路層首部T2鏈路層尾部3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)網(wǎng)絡(luò)接口卡網(wǎng)絡(luò)接口卡（NIC，簡稱網(wǎng)卡）能夠使工作站、服務(wù)器、打印機

10、或其他節(jié)點通過網(wǎng)絡(luò)介質(zhì)接收并發(fā)送數(shù)據(jù)。網(wǎng)絡(luò)接口卡常被稱為網(wǎng)絡(luò)適配器。屬于OSI模型的物理層。 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)中繼器中繼器是一種放大或模擬數(shù)字信號的網(wǎng)絡(luò)連接設(shè)備。中繼器屬于OSI模型中的物理層。它們只是轉(zhuǎn)發(fā)信號，但同時也轉(zhuǎn)發(fā)了信號的噪聲， 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)集線器集線器能與網(wǎng)絡(luò)中的打印服務(wù)器、交換器、文件服務(wù)器或其他的設(shè)備連接。 集線器屬于OSI模型中的物理層。 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)網(wǎng)橋網(wǎng)橋這種設(shè)備看上去有點像中繼器。它具有單個的輸入端口和輸出端口，它與中繼器的不同之處就在于它能夠解析它收發(fā)的數(shù)據(jù)。網(wǎng)橋?qū)儆贠SI模型的數(shù)據(jù)鏈路層 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)交換機交換機屬

11、于OSI模型的數(shù)據(jù)鏈路層，并且，它還能夠解析出MAC地址信息。事實上，它相當(dāng)于多個網(wǎng)橋。 3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)路由器路由器是一種多端口設(shè)備，它可以連接不同傳輸速率并運行于各種環(huán)境的局域網(wǎng)和廣域網(wǎng)，也可以采用不同的協(xié)議。路由器屬于OSI模型的網(wǎng)絡(luò)層設(shè)備。3. 計算機網(wǎng)絡(luò)計算機網(wǎng)絡(luò)數(shù)據(jù)庫系統(tǒng)的產(chǎn)生與發(fā)展數(shù)據(jù)庫基本概念數(shù)據(jù)庫基本概念1）數(shù)據(jù)）數(shù)據(jù)(Data)數(shù)據(jù)是描述事物的符號記錄。2）信息）信息(Information) 通常被認(rèn)為是具有一定含義的、經(jīng)過加工的、對決策有價值的數(shù)據(jù)。3）數(shù)據(jù)庫）數(shù)據(jù)庫(Database, DB) 數(shù)據(jù)庫是指長期存儲在計算機內(nèi)，有組織的、可共享的數(shù)據(jù)集合。4.

12、數(shù)據(jù)庫數(shù)據(jù)庫l 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 是所研究的對象類型的集合。用于描述數(shù)據(jù)的靜態(tài)特征。包括：數(shù)據(jù)的類型、內(nèi)容和性質(zhì)的對象（事物）；數(shù)據(jù)之間聯(lián)系的對象（聯(lián)系）。l 數(shù)據(jù)操作數(shù)據(jù)操作 是對數(shù)據(jù)庫中各種對象的實例允許執(zhí)行的操作的集合。用于描述數(shù)據(jù)的動態(tài)特征。l 完整性約束完整性約束 完整性規(guī)則的集合。如性別只能有男和女之分，年齡不能為0等。數(shù)據(jù)模型概述數(shù)據(jù)模型概述4. 數(shù)據(jù)庫數(shù)據(jù)庫最常用的數(shù)據(jù)模型最常用的數(shù)據(jù)模型1層次模型 層次模型（Hierarchical Model）是一種以記錄某一事物的類型為根節(jié)點的有向樹。4. 數(shù)據(jù)庫數(shù)據(jù)庫2網(wǎng)狀模型 最常用的數(shù)據(jù)模型最常用的數(shù)據(jù)模型 網(wǎng)狀模型是層次模型的擴展

13、，表示多個從屬關(guān)系的層次結(jié)構(gòu)，呈現(xiàn)一種交叉關(guān)系的網(wǎng)狀結(jié)構(gòu)。4. 數(shù)據(jù)庫數(shù)據(jù)庫 關(guān)系模型（Relational Model）是指雖具有相關(guān)性而非從屬性的平行的數(shù)據(jù)之間按照某種序列排列的集合關(guān)系。關(guān)系模型是由若干個關(guān)系模式組成的集合，關(guān)系模式的實例稱為關(guān)系，而每個關(guān)系實際上就是一張二維表格。 4. 數(shù)據(jù)庫數(shù)據(jù)庫最常用的數(shù)據(jù)模型最常用的數(shù)據(jù)模型3關(guān)系模型 基本概念關(guān)系：一個關(guān)系對應(yīng)一張表元組：表中的一行屬性：表中的一列主碼：表中的某個屬性或?qū)傩越M，它可以唯一確定一個元組域：屬性的取值范圍分量：元組中的一個屬性值關(guān)系模式：對關(guān)系的描述4. 數(shù)據(jù)庫數(shù)據(jù)庫關(guān)系的性質(zhì)1)關(guān)系中每一數(shù)據(jù)項不可再分，是最基本的

14、單位。2)每一列數(shù)據(jù)項是同屬性的。列數(shù)根據(jù)需要而設(shè)，且各列的順序是任意的。3)每一行記錄由一個事物的諸多屬性項構(gòu)成。記錄的順序可以是任意的。4)一個關(guān)系是一張二維表，不允許有相同的字段名，也不允許有相同的記錄行。5)每個關(guān)系都有稱之為關(guān)鍵字的屬性集唯一標(biāo)識各元組。4. 數(shù)據(jù)庫數(shù)據(jù)庫5. 軟件工程軟件工程5. 軟件工程軟件工程軟件開發(fā)V模型5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程數(shù)據(jù)數(shù)據(jù)(Data)：在計算機科學(xué)中是所有能輸：在計算機科學(xué)中是所有能輸入到計算機中并能被計算機程序處理的入到計算機中并能被計算

15、機程序處理的符號符號的總稱。的總稱。 數(shù)據(jù)包含的內(nèi)容隨著計算機的發(fā)展而擴大數(shù)據(jù)包含的內(nèi)容隨著計算機的發(fā)展而擴大 例如：數(shù)字、字母、漢字、圖形、圖像、聲例如：數(shù)字、字母、漢字、圖形、圖像、聲音都稱為數(shù)據(jù)。音都稱為數(shù)據(jù)。 注意：專業(yè)術(shù)語中，數(shù)據(jù)已經(jīng)不是注意：專業(yè)術(shù)語中，數(shù)據(jù)已經(jīng)不是“數(shù)值數(shù)值”。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)元素數(shù)據(jù)元素(Data Element)：數(shù)據(jù)的基本單位，：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考在計算機程序中通常作為一個整體進行考慮和處理。慮和處理。 人是一個數(shù)據(jù)元素，通常作為整體進行處理。人是一個數(shù)據(jù)元素，通常作為整體進行處理。 數(shù)據(jù)元

16、素還不是組成數(shù)據(jù)的最小單位。數(shù)據(jù)元素還不是組成數(shù)據(jù)的最小單位。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data Structures):帶結(jié)構(gòu)的數(shù)據(jù)帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。元素的集合。 結(jié)構(gòu)：數(shù)據(jù)元素之間存在的約束關(guān)系結(jié)構(gòu)：數(shù)據(jù)元素之間存在的約束關(guān)系 數(shù)據(jù)元素之間不是孤立的，而是相互之間存數(shù)據(jù)元素之間不是孤立的，而是相互之間存在著一種或多種特定的關(guān)系在著一種或多種特定的關(guān)系6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序一種數(shù)據(jù)結(jié)構(gòu)包含下面三個方面：一種數(shù)據(jù)結(jié)構(gòu)包含下面三個方面：邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：表示數(shù)據(jù)元素之間的邏輯關(guān)系。：表示數(shù)據(jù)元素之間的邏輯關(guān)系。 Data_St

17、ructure=( D, S )物理結(jié)構(gòu)物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的映射：數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的映射（或表示），（或表示）， 又稱存儲結(jié)構(gòu)，也稱存儲表示又稱存儲結(jié)構(gòu)，也稱存儲表示結(jié)構(gòu)的行為特征結(jié)構(gòu)的行為特征 作用于數(shù)據(jù)結(jié)構(gòu)上的運算。例如：檢索，作用于數(shù)據(jù)結(jié)構(gòu)上的運算。例如：檢索，插入，刪除等。插入，刪除等。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)集合集合數(shù)據(jù)元素間除數(shù)據(jù)元素間除“同屬于一個集合同屬于一個集合”外，無外，無其它關(guān)系其它關(guān)系線性結(jié)構(gòu)線性結(jié)構(gòu)一個對一個，如

18、線性表、棧、隊列一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)樹形結(jié)構(gòu)一個對多個，如樹一個對多個，如樹圖形結(jié)構(gòu)圖形結(jié)構(gòu)多個對多個，如圖多個對多個，如圖6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序（1）順序存儲（向量存儲）以存儲位置的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。存儲結(jié)構(gòu)(storage structure)：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。要在計算機中實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的操作，如何在計算機中實現(xiàn)對各種數(shù)據(jù)及其關(guān)系的表示？6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序順序存儲存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 1345 1345 元素元素1 1 1346 1346 元素元素2 2 1347 1347 元素

19、元素3 3 1348 1348 元素元素4 4 1349 1349 元素元素5 5 6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序( 2 ) 鏈?zhǔn)酱鎯σ愿郊有畔ⅲㄖ羔槪┍硎緮?shù)據(jù)元素間的邏輯關(guān)系所有元素存放在可以不連續(xù)的存儲單元中，但元素之間的關(guān)系可以通過地址確定，邏輯上相鄰的元素存放到計算機內(nèi)存后不一定是相鄰的。 6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序1536元素21400元素11346元素3 元素4

20、1345h存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 指針指針 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 鏈?zhǔn)酱鎯?h6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序(3)索引存儲 使用該方法存放元素的同時，還建立附加的索引表，索引表中的每一項稱為索引項，索引項的一般形式是：（關(guān)鍵字，地址），其中的關(guān)鍵字是能唯一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項。 (4)散列存儲通過構(gòu)造散列函數(shù)，用函數(shù)的值來確定元素存放的地址。6.

21、數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存儲 鏈?zhǔn)酱鎯?線性表棧隊列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：檢索、排序、插入、刪除、修改等6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序算法 是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。n算法是指解決問題的一種方法或一個過程。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 N.沃思（沃思（Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計程序設(shè)計：為計算機處理問題編制一組指令集：為計算機處理問題編

22、制一組指令集算法算法：怎樣處理問題，解決問題的策略：怎樣處理問題，解決問題的策略數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：要處理的信息如何表示，問題的表：要處理的信息如何表示，問題的表示模型示模型6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 N.沃思（沃思（Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)以上公式說明了如下兩個問題：以上公式說明了如下兩個問題： （1）數(shù)據(jù)上的算法決定如何構(gòu)造和組織數(shù)據(jù)）數(shù)據(jù)上的算法決定如何構(gòu)造和組織數(shù)據(jù)（算法（算法數(shù)據(jù)結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)）。 （2）算法的設(shè)計依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)）算法的設(shè)計依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)算法）算法）

23、。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序算法的算法的5個特性個特性有窮性有窮性：算法必須總是在執(zhí)行有窮步后結(jié)束，：算法必須總是在執(zhí)行有窮步后結(jié)束，每一步在有窮時間內(nèi)完成。每一步在有窮時間內(nèi)完成。確定性確定性：組成算法的每條指令是清晰，無歧義：組成算法的每條指令是清晰，無歧義的。的?？尚行钥尚行裕核惴ㄊ强蓤?zhí)行的。：算法是可執(zhí)行的。輸入輸入：有零個或多個外部提供的量作為輸入。：有零個或多個外部提供的量作為輸入。輸出輸出：算法產(chǎn)生至少一個量作為輸出。：算法產(chǎn)生至少一個量作為輸出。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容數(shù)學(xué)模型解題思路 問題抽象數(shù)據(jù)結(jié)

24、構(gòu)算法 數(shù)據(jù)類型程序設(shè)計編碼運行圖 計算機解決問題的一般過程6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法設(shè)計的要求 1.正確性：算法應(yīng)當(dāng)滿足具體問題的需求。正確的含義有4個層次的級別：1、程序不含語法錯誤；2、程序?qū)τ趲追N輸入數(shù)據(jù)有正確的結(jié)果；3、程序?qū)τ诘湫?、苛刻、刁難性的數(shù)據(jù)有正確的結(jié)果；4、對于一切合法的輸入數(shù)據(jù)都有正確結(jié)果。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法設(shè)計的要求 2.可讀性：有助于人對算法的理解。 算法主要是為了人的閱讀和交流，晦澀難懂的程序容易隱藏錯誤，難以調(diào)試和修改。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法設(shè)計的要求 3.健壯性：適當(dāng)處理

25、任何錯誤輸入。 對于輸入非法的數(shù)據(jù)時，算法能夠給出反應(yīng)作出處理，而不會出現(xiàn)莫名奇妙的錯誤。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法設(shè)計的要求 4.效率和低存儲量需求。 效率是指算法執(zhí)行的時間，執(zhí)行時間短的算法效率高。 存儲量需求是指算法執(zhí)行過程中所需要的最大存儲空間，顯然是越低越好。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法效率的度量 算法的時間代價(或稱時間復(fù)雜度) 執(zhí)行時間越短，算法效率越高。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序度量算法的執(zhí)行時間度量算法的執(zhí)行時間(1)事后統(tǒng)計法：運行程序后通過若干統(tǒng)計事后統(tǒng)計法：運行程序后通過若干統(tǒng)計數(shù)據(jù)來分辨優(yōu)劣。數(shù)據(jù)來

26、分辨優(yōu)劣。缺陷：缺陷： 必須先運行依算法編制的程序，一些大型算必須先運行依算法編制的程序，一些大型算法要運行則比較費時費力；法要運行則比較費時費力； 所得時間的統(tǒng)計量依賴于計算機的硬件、軟所得時間的統(tǒng)計量依賴于計算機的硬件、軟件等環(huán)境因素，容易掩蓋算法本身的優(yōu)劣。件等環(huán)境因素，容易掩蓋算法本身的優(yōu)劣。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序度量算法的執(zhí)行時間度量算法的執(zhí)行時間(2)事前分析估算法事前分析估算法依據(jù)的影響因素：依據(jù)的影響因素： 依據(jù)的算法選用何種策略；依據(jù)的算法選用何種策略； 問題的規(guī)模；問題的規(guī)模； 書寫程序的語言；書寫程序的語言； 編譯程序時所產(chǎn)生的機器代碼的質(zhì)量；編譯

27、程序時所產(chǎn)生的機器代碼的質(zhì)量； 機器執(zhí)行指令的速度。機器執(zhí)行指令的速度。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序度量算法的執(zhí)行時間度量算法的執(zhí)行時間(2)事前分析估算法事前分析估算法分析方法：分析方法： 找出算法中最重要的操作找出算法中最重要的操作基本操作基本操作，計，計算它們的算它們的運行次數(shù)運行次數(shù)。 基本操作通常是算法基本操作通常是算法最內(nèi)層循環(huán)中最費時的操作最內(nèi)層循環(huán)中最費時的操作6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 時間復(fù)雜度 一般情況下，算法中基本操作重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間量度記作 T(n)=O(f(n) 它表示隨問題規(guī)模n的增大，算

28、法執(zhí)行時間的增長率和f(n)的增長率相同。 稱做算法的漸近時間復(fù)雜度（asymptotic time complexity),簡稱時間復(fù)雜度。 6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序時間復(fù)雜度的意義時間復(fù)雜度的意義 反映了隨著問題規(guī)模的增加，算法消耗時間的反映了隨著問題規(guī)模的增加，算法消耗時間的增加度。增加度。問題規(guī)模增加執(zhí)行時間增長快執(zhí)行時間增長慢算法效率低算法效率高6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序算法A：int i, sum = 0, n = 100;for(i = 1; i = n; i +) sum = sum + i;printf ( “%d”, sum);算法

29、B：int sum = 0, n = 100;sum = ( 1+n ) * n/2;printf ( “%d”, sum);哪個算法效率更高？6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序由于時間復(fù)雜度考慮的只是問題規(guī)模由于時間復(fù)雜度考慮的只是問題規(guī)模n的增長的增長率，則在難以精確計算基本操作執(zhí)行次數(shù)的率，則在難以精確計算基本操作執(zhí)行次數(shù)的情況下，只需求出它情況下，只需求出它關(guān)于關(guān)于n的增長率或階的增長率或階即即可?？?。f(n) = 3n2+n6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序for (i=0; in; i+) S(i);for (i=0; in; i+) for (j=0; j

30、n; j+) S(i,j);f(n)=n，時間復(fù)雜度為O(n)f(n)=n2，時間復(fù)雜度為O(n2)S(i);f(n)=1，時間復(fù)雜度為O(1)6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序例：NXN矩陣相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k10 i=i+1 else i=i-1 endif（2） 語言處理程序語言處理程序6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序C語言的發(fā)展及其特點運算符豐富。有有34種運算符種運算符把括號、賦值、強制類型轉(zhuǎn)換等都作為運算符處理把括號、賦值、強制類型轉(zhuǎn)換等都作為運算符處理表達(dá)式類型多樣化表達(dá)式類

31、型多樣化6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序C語言的發(fā)展及其特點數(shù)據(jù)類型豐富。包括包括:整型、浮點型、字符型、數(shù)組類型、指針類型、結(jié)整型、浮點型、字符型、數(shù)組類型、指針類型、結(jié)構(gòu)體類型、共用體類型；構(gòu)體類型、共用體類型；C99又?jǐn)U充了復(fù)數(shù)浮點類型、超長整型又?jǐn)U充了復(fù)數(shù)浮點類型、超長整型(long long)、布爾、布爾類型類型(bool)；指針類型數(shù)據(jù)，能用來實現(xiàn)各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)指針類型數(shù)據(jù)，能用來實現(xiàn)各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)(如鏈表、如鏈表、樹、棧等樹、棧等)的運算。的運算。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序C語言的發(fā)展及其特點具有結(jié)構(gòu)化的控制語句如如ifelse語句、語句、while語句、語句、dowhile語句、語句、switch語句、語句、for語句語句用函數(shù)作為程序的模塊單位，便于實現(xiàn)程序的模塊化用函數(shù)作為程序的模塊單位，便于實現(xiàn)程序的模塊化C語言是完全模塊化和結(jié)構(gòu)化的語言語言是完全模塊化和結(jié)構(gòu)化的語言6. 數(shù)據(jù)結(jié)構(gòu)、算法、