計(jì)算機(jī)基礎(chǔ)課件

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

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

3、軟件。其主要的功能是進(jìn)持應(yīng)用軟件的開(kāi)發(fā)和運(yùn)行的軟件。其主要的功能是進(jìn)行調(diào)度、監(jiān)控和維護(hù)系統(tǒng)等等。系統(tǒng)軟件是行調(diào)度、監(jiān)控和維護(hù)系統(tǒng)等等。系統(tǒng)軟件是用戶(hù)和裸用戶(hù)和裸機(jī)的接口機(jī)的接口。 1. 計(jì)算機(jī)系統(tǒng)的組成計(jì)算機(jī)系統(tǒng)的組成2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)2. 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展的四個(gè)階段：1.第一階段：第一階段：“誕生階段誕生階段”以主機(jī)為中心的聯(lián)機(jī)終端系統(tǒng)，“計(jì)算機(jī)終端”系統(tǒng)2.第二階段：第二階段：“

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

5、“形成階段形成階段 ” 通信子網(wǎng)為中心的主機(jī)互連特征 多個(gè)終端聯(lián)機(jī)系統(tǒng)互聯(lián)，形成了多主機(jī)互聯(lián)網(wǎng)絡(luò) 網(wǎng)絡(luò)結(jié)構(gòu)從“主機(jī)終端” 轉(zhuǎn)變?yōu)椤爸鳈C(jī)主機(jī)”HOSTHOSTHOSTTTTTTTTTTT通信線(xiàn)路3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)演變階段1 通信任務(wù)從主機(jī)中分離，由通信控制處理機(jī)（CCP）完成 CCP：處理主機(jī)之間通信任務(wù)的專(zhuān)用計(jì)算機(jī)CCPCCPHOSTHOSTTTTTTTCCPHOSTTT3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)兩層網(wǎng)絡(luò)概念的出現(xiàn) 由CCP組成的傳輸網(wǎng)絡(luò)通信子網(wǎng)通信子網(wǎng)，提供信息傳輸服務(wù) 建立在通信子網(wǎng)基礎(chǔ)上的主機(jī)集合資源子資源子網(wǎng)網(wǎng)，提供計(jì)算資源CCPCCPHOSTHOSTTTTTTTCCPHOST

6、TTT通信子網(wǎng)通信子網(wǎng)3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)18演變階段2 通信子網(wǎng)規(guī)模逐漸擴(kuò)大 私有社會(huì)公用 公用數(shù)據(jù)通信網(wǎng) PSTN X.25 優(yōu)點(diǎn) 降低用戶(hù)系統(tǒng)建設(shè)成本 提高通信線(xiàn)路利用率 兼容性好公用數(shù)據(jù)公用數(shù)據(jù)通信網(wǎng)通信網(wǎng)HOSTHOSTTTTTTTHOSTTTTT3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(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è)備之間的兼容性和互操作性是推動(dòng)網(wǎng)絡(luò)體系結(jié)構(gòu)的標(biāo)準(zhǔn)化的原動(dòng)力 而兼容性和互操作性的最終目的仍是資源共享標(biāo)準(zhǔn)化的時(shí)機(jī)？ 先制定標(biāo)準(zhǔn)再開(kāi)發(fā)還是先開(kāi)發(fā)再制定標(biāo)準(zhǔn)？ 各廠(chǎng)商、研究機(jī)構(gòu)、大學(xué)在網(wǎng)絡(luò)技術(shù)、方法、理論等方面的研究

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

8、OSI 與 TCP/IP 體系結(jié)構(gòu)的比較 應(yīng)用層傳輸層網(wǎng)絡(luò)層表示層會(huì)話(huà)層數(shù)據(jù)鏈路層物理層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. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)分層的好處分層的好處 1. 各層之間是獨(dú)立的。2. 靈活性好。3. 結(jié)構(gòu)上可分割開(kāi)。4. 易于實(shí)現(xiàn)和維護(hù)。5. 能促進(jìn)標(biāo)準(zhǔn)化工作。 若層數(shù)太少，就會(huì)使每一層的協(xié)議太復(fù)雜。層數(shù)太多又會(huì)在描述和綜合各層功能的系統(tǒng)工程任務(wù)時(shí)遇到較多的困難。 3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)五層協(xié)議的體系結(jié)構(gòu) ：TCP/IP 是四層的體系結(jié)構(gòu)

9、：應(yīng)用層、運(yùn)輸層、網(wǎng)際層和網(wǎng)絡(luò)接口層。最下面的網(wǎng)絡(luò)接口層并沒(méi)有具體內(nèi)容。因此往往采取折中的辦法，即綜合 OSI 和 TCP/IP的優(yōu)點(diǎn)，采用一種只有五層協(xié)議的體系結(jié)構(gòu) 。 3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī) 1 向計(jì)算機(jī) 2 發(fā)送數(shù)據(jù) 5432154321計(jì)算機(jī) 1AP2AP1計(jì)算機(jī) 2應(yīng) 用 程 序 數(shù) 據(jù)應(yīng)用層首部H510100110100101 比 特 流 110101110101注意觀(guān)察加入或剝?nèi)ナ撞浚ㄎ膊浚┑膶哟螒?yīng) 用 程 序 數(shù) 據(jù)H5應(yīng) 用 程 序 數(shù) 據(jù)H4H5應(yīng) 用 程 序 數(shù) 據(jù)H3H4H5應(yīng) 用 程 序 數(shù) 據(jù)H4運(yùn)輸層首部H3網(wǎng)絡(luò)層首部H2鏈路層首部T2鏈路層尾部3. 計(jì)

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

11、它收發(fā)的數(shù)據(jù)。網(wǎng)橋?qū)儆贠SI模型的數(shù)據(jù)鏈路層 3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)交換機(jī)交換機(jī)屬于OSI模型的數(shù)據(jù)鏈路層，并且，它還能夠解析出MAC地址信息。事實(shí)上，它相當(dāng)于多個(gè)網(wǎng)橋。 3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)路由器路由器是一種多端口設(shè)備，它可以連接不同傳輸速率并運(yùn)行于各種環(huán)境的局域網(wǎng)和廣域網(wǎng)，也可以采用不同的協(xié)議。路由器屬于OSI模型的網(wǎng)絡(luò)層設(shè)備。3. 計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)數(shù)據(jù)庫(kù)系統(tǒng)的產(chǎn)生與發(fā)展數(shù)據(jù)庫(kù)基本概念數(shù)據(jù)庫(kù)基本概念1）數(shù)據(jù)）數(shù)據(jù)(Data)數(shù)據(jù)是描述事物的符號(hào)記錄。2）信息）信息(Information) 通常被認(rèn)為是具有一定含義的、經(jīng)過(guò)加工的、對(duì)決策有價(jià)值的數(shù)據(jù)。3）數(shù)據(jù)庫(kù)）數(shù)據(jù)庫(kù)(Dat

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

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

14、模式：對(duì)關(guān)系的描述4. 數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)關(guān)系的性質(zhì)1)關(guān)系中每一數(shù)據(jù)項(xiàng)不可再分，是最基本的單位。2)每一列數(shù)據(jù)項(xiàng)是同屬性的。列數(shù)根據(jù)需要而設(shè)，且各列的順序是任意的。3)每一行記錄由一個(gè)事物的諸多屬性項(xiàng)構(gòu)成。記錄的順序可以是任意的。4)一個(gè)關(guān)系是一張二維表，不允許有相同的字段名，也不允許有相同的記錄行。5)每個(gè)關(guān)系都有稱(chēng)之為關(guān)鍵字的屬性集唯一標(biāo)識(shí)各元組。4. 數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)5. 軟件工程軟件工程5. 軟件工程軟件工程軟件開(kāi)發(fā)V模型5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程5. 軟件工程軟件工程數(shù)據(jù)數(shù)據(jù)(Data)：在計(jì)算機(jī)科學(xué)中是所有

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

16、是一個(gè)數(shù)據(jù)元素，通常作為整體進(jìn)行處理。人是一個(gè)數(shù)據(jù)元素，通常作為整體進(jìn)行處理。 數(shù)據(jù)元素還不是組成數(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)包含下面三個(gè)方面：一種數(shù)據(jù)結(jié)構(gòu)包含下面三個(gè)方面：邏輯結(jié)

17、構(gòu)邏輯結(jié)構(gòu)：表示數(shù)據(jù)元素之間的邏輯關(guān)系。：表示數(shù)據(jù)元素之間的邏輯關(guān)系。 Data_Structure=( D, S )物理結(jié)構(gòu)物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映射：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映射（或表示），（或表示）， 又稱(chēng)存儲(chǔ)結(jié)構(gòu)，也稱(chēng)存儲(chǔ)表示又稱(chēng)存儲(chǔ)結(jié)構(gòu)，也稱(chēng)存儲(chǔ)表示結(jié)構(gòu)的行為特征結(jié)構(gòu)的行為特征 作用于數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算。例如：檢索，作用于數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算。例如：檢索，插入，刪除等。插入，刪除等。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ù)元素間除“同

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

19、1345 元素元素1 1 1346 1346 元素元素2 2 1347 1347 元素元素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存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序( 2 ) 鏈?zhǔn)酱鎯?chǔ)以附加信息（指針）表示數(shù)據(jù)元素間的邏輯關(guān)系所有元素存放在可以不連續(xù)的存儲(chǔ)單元中，但元素之間的關(guān)系可以通過(guò)地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的。 6. 數(shù)據(jù)

20、結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序1536元素21400元素11346元素3 元素41345h存儲(chǔ)地址存儲(chǔ)地址 存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容 指針指針 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 鏈?zhǔn)酱鎯?chǔ) h6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序(3)索引存儲(chǔ) 使用該方法存放元素的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)稱(chēng)為索引項(xiàng)，索引項(xiàng)的一般形式是：（關(guān)鍵字，地址），其中的關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)

21、的那些數(shù)據(jù)項(xiàng)。 (4)散列存儲(chǔ)通過(guò)構(gòu)造散列函數(shù)，用函數(shù)的值來(lái)確定元素存放的地址。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算 線(xiàn)性結(jié)構(gòu) 非線(xiàn)性結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 線(xiàn)性表?xiàng)ｊ?duì)列樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：檢索、排序、插入、刪除、修改等6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序算法 是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。n算法是指解決問(wèn)題的一種方法或一個(gè)過(guò)程。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 N.沃思（沃思（Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法

22、+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)程序設(shè)計(jì)：為計(jì)算機(jī)處理問(wèn)題編制一組指令集：為計(jì)算機(jī)處理問(wèn)題編制一組指令集算法算法：怎樣處理問(wèn)題，解決問(wèn)題的策略：怎樣處理問(wèn)題，解決問(wèn)題的策略數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：要處理的信息如何表示，問(wèn)題的表：要處理的信息如何表示，問(wè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)以上公式說(shuō)明了如下兩個(gè)問(wèn)題：以上公式說(shuō)明了如下兩個(gè)問(wèn)題： （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è)計(jì)依賴(lài)于

23、作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)）算法的設(shè)計(jì)依賴(lài)于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)算法）算法）。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序算法的算法的5個(gè)特性個(gè)特性有窮性有窮性：算法必須總是在執(zhí)行有窮步后結(jié)束，：算法必須總是在執(zhí)行有窮步后結(jié)束，每一步在有窮時(shí)間內(nèi)完成。每一步在有窮時(shí)間內(nèi)完成。確定性確定性：組成算法的每條指令是清晰，無(wú)歧義：組成算法的每條指令是清晰，無(wú)歧義的。的?？尚行钥尚行裕核惴ㄊ强蓤?zhí)行的。：算法是可執(zhí)行的。輸入輸入：有零個(gè)或多個(gè)外部提供的量作為輸入。：有零個(gè)或多個(gè)外部提供的量作為輸入。輸出輸出：算法產(chǎn)生至少一個(gè)量作為輸出。：算法產(chǎn)生至少一個(gè)量作為輸出。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)

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

25、。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法設(shè)計(jì)的要求 3.健壯性：適當(dāng)處理任何錯(cuò)誤輸入。 對(duì)于輸入非法的數(shù)據(jù)時(shí)，算法能夠給出反應(yīng)作出處理，而不會(huì)出現(xiàn)莫名奇妙的錯(cuò)誤。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法設(shè)計(jì)的要求 4.效率和低存儲(chǔ)量需求。 效率是指算法執(zhí)行的時(shí)間，執(zhí)行時(shí)間短的算法效率高。 存儲(chǔ)量需求是指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間，顯然是越低越好。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序 算法效率的度量 算法的時(shí)間代價(jià)(或稱(chēng)時(shí)間復(fù)雜度) 執(zhí)行時(shí)間越短，算法效率越高。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序度量算法的執(zhí)行時(shí)間度量算法的執(zhí)行時(shí)間(1)事后

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

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

28、函數(shù)f(n),算法的時(shí)間量度記作 T(n)=O(f(n) 它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。 稱(chēng)做算法的漸近時(shí)間復(fù)雜度（asymptotic time complexity),簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。 6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序時(shí)間復(fù)雜度的意義時(shí)間復(fù)雜度的意義 反映了隨著問(wèn)題規(guī)模的增加，算法消耗時(shí)間的反映了隨著問(wèn)題規(guī)模的增加，算法消耗時(shí)間的增加度。增加度。問(wèn)題規(guī)模增加執(zhí)行時(shí)間增長(zhǎng)快執(zhí)行時(shí)間增長(zhǎng)慢算法效率低算法效率高6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序算法A：int i, sum = 0, n = 100;for(i = 1; i = n

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

30、 in; i+) S(i);for (i=0; in; i+) for (j=0; jn; j+) S(i,j);f(n)=n，時(shí)間復(fù)雜度為O(n)f(n)=n2，時(shí)間復(fù)雜度為O(n2)S(i);f(n)=1，時(shí)間復(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分類(lèi)分類(lèi)機(jī)器語(yǔ)言機(jī)器語(yǔ)言匯編語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言高級(jí)語(yǔ)言（2） 語(yǔ)言處理程序語(yǔ)言處理程序6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序C語(yǔ)言的發(fā)展及其特點(diǎn) 運(yùn)算

31、符豐富。 有有34種運(yùn)算符種運(yùn)算符 把括號(hào)、賦值、強(qiáng)制類(lèi)型轉(zhuǎn)換等都作為運(yùn)算符處理把括號(hào)、賦值、強(qiáng)制類(lèi)型轉(zhuǎn)換等都作為運(yùn)算符處理 表達(dá)式類(lèi)型多樣化表達(dá)式類(lèi)型多樣化6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序C語(yǔ)言的發(fā)展及其特點(diǎn) 數(shù)據(jù)類(lèi)型豐富。 包括包括:整型、浮點(diǎn)型、字符型、數(shù)組類(lèi)型、指針類(lèi)型、整型、浮點(diǎn)型、字符型、數(shù)組類(lèi)型、指針類(lèi)型、結(jié)構(gòu)體類(lèi)型、共用體類(lèi)型；結(jié)構(gòu)體類(lèi)型、共用體類(lèi)型； C99又?jǐn)U充了復(fù)數(shù)浮點(diǎn)類(lèi)型、超長(zhǎng)整型又?jǐn)U充了復(fù)數(shù)浮點(diǎn)類(lèi)型、超長(zhǎng)整型(long long)、布、布爾類(lèi)型爾類(lèi)型(bool)； 指針類(lèi)型數(shù)據(jù)，能用來(lái)實(shí)現(xiàn)各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)指針類(lèi)型數(shù)據(jù)，能用來(lái)實(shí)現(xiàn)各種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)(如鏈如鏈表、樹(shù)、棧等表、樹(shù)、棧等)的運(yùn)算。的運(yùn)算。6. 數(shù)據(jù)結(jié)構(gòu)、算法、程序數(shù)據(jù)結(jié)構(gòu)、算法、程序C語(yǔ)言的發(fā)展及其特點(diǎn) 具有結(jié)構(gòu)化的控制語(yǔ)句 如如ifelse語(yǔ)句、語(yǔ)句、while語(yǔ)句、語(yǔ)句、dowhile語(yǔ)句、語(yǔ)句、switch語(yǔ)語(yǔ)句、句、for語(yǔ)句語(yǔ)句 用函數(shù)作為程序的模塊單位，便于實(shí)現(xiàn)程序的模塊化用函數(shù)作為程序的模塊單位，便于實(shí)現(xiàn)程序的模塊化 C語(yǔ)言是完全模塊化和結(jié)構(gòu)化的語(yǔ)言語(yǔ)言是完全模塊化和結(jié)構(gòu)化的語(yǔ)言6. 數(shù)據(jù)結(jié)構(gòu)、算法、