第八章 算法

算法：算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限的時間內(nèi)終止。

要點有四：

1 有序集合

2 明確步驟

3 產(chǎn)生結(jié)果

4 在有限的時間內(nèi)終止

三種結(jié)構(gòu)：順序，選擇，循環(huán)。

算法的表示：流程圖，偽代碼。

第九章 程序設(shè)計語言

演化：機器語言-符號語言-高級語言

構(gòu)建程序：編寫和編輯程序-編譯程序-用所需的庫模塊鏈接程序

語言的分類：

1 過程化語言：（1）FORTRAN；（2）COBOL；（3）Pascal; （4）C;（5）Ada

2 面向?qū)ο笳Z言：（1）C++; (2)Java

3 函數(shù)型語言： （1）LISP ；（2）Scheme

4 說明性語言： （1）prolog

5 專用語言：(1)HTML

第十章 軟件工程

軟件工程：利用合理的工程方法和原則來獲得在真實機器上工作的可靠軟件。

分析-設(shè)計-實現(xiàn)-測試

分析階段：

定義用戶-定義要求-定義需求-定義方法-

設(shè)計階段：1 模塊化 2 工具

實現(xiàn)階段：

1 工具：流程圖，偽代碼

2 編碼

測試階段：

（1）黑盒：測試功能，由需求出發(fā)

（2）白盒：測試邏輯，每條指令，每個情況都要測試

模塊化：

工具：UML

耦合：

（1）數(shù)據(jù)耦合：只從調(diào)用函數(shù)向被調(diào)用函數(shù)傳遞最少的需求數(shù)據(jù)；

（2）特征耦合：參數(shù)是數(shù)組或結(jié)構(gòu)這樣的復(fù)合數(shù)據(jù)；

（3）控制耦合：傳遞標志，指示函數(shù)的邏輯流程；

（4）全局耦合：用全局變量傳遞兩個或兩個以上的函數(shù)通訊；

（5）內(nèi)容耦合：直接引用另一個函數(shù)的數(shù)據(jù)或語句。

內(nèi)聚：

（1）功能內(nèi)聚：只包含一個處理過程；

（2）順序內(nèi)聚：包含兩個或多個緊密聯(lián)系的任務(wù)；

（3）通信內(nèi)聚：將使用同一數(shù)據(jù)的處理過程合并；

（4）控制內(nèi)聚：由控制流程控制的不相關(guān)的處理過程；

（5）瞬時內(nèi)聚：合并了總在一起發(fā)生卻不相關(guān)的處理過程

第十一章 數(shù)據(jù)結(jié)構(gòu)

這一章只介紹三種：數(shù)組，結(jié)構(gòu)，鏈表。

第十二章 抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型：

1.數(shù)據(jù)的聲明

2.操作的聲明

3.封裝數(shù)據(jù)和操作

線性列表：

1.廣義表：（1）有序列表；（2）無序列表

2.限制列表：（1）隊列；（2）堆棧

樹

二叉樹

圖

第十三章 文件結(jié)構(gòu)

文件是作為單元看待的相關(guān)數(shù)據(jù)的外部集合

存取方法：

1.順序存?。喉樞蛭募Y(jié)構(gòu)

2.隨機存?。海?）索引文件；（2）哈希文件

更新順序文件：

（1）舊主文件

（2）新主文件

（3）事務(wù)文件：包含要對主文件做的修改：ADR添加刪除修改

（4）錯誤報告文件

索引文件：索引將鍵映射到地址

（1）數(shù)據(jù)文件；

（2）索引

哈希文件：用一個函數(shù)來完成映射，不需要索引。

哈希方法：（1）直接法（2）求模法（3）數(shù)字析取法

沖突：兩個不同的記錄計算得到相同地址時發(fā)生

解決辦法：

（1）開放尋址：主區(qū)地址將查找開放的或空閑的記錄來存放新數(shù)據(jù)

（2）鏈表解決法：第一條記錄包含指向下一條記錄的指針

（3）桶哈希法：哈希到桶。桶能容納多個記錄的節(jié)點

文本文件和二進制文件：

文本文件是按字節(jié)編碼的，也就是定長編碼，怎么解釋已經(jīng)確定。

二進制文件是按值編碼的，自定義編碼，根據(jù)具體應(yīng)用指定某個值的意思。