計(jì)算機(jī)科學(xué)的基礎(chǔ)

計(jì)算機(jī)科學(xué)的基礎(chǔ)目錄\h第1章計(jì)算機(jī)科學(xué)：將抽象機(jī)械化\h1.1本書(shū)主要內(nèi)容\h1.1.1數(shù)據(jù)模型\h1.1.2數(shù)據(jù)結(jié)構(gòu)\h1.1.3算法\h1.1.4基本思路\h1.2本章主要內(nèi)容\h1.3數(shù)據(jù)模型\h1.3.1編程語(yǔ)言數(shù)據(jù)模型\h1.3.2系統(tǒng)軟件的數(shù)據(jù)模型\h1.3.3電路的數(shù)據(jù)模型\h1.3.4習(xí)題\h1.4C語(yǔ)言數(shù)據(jù)模型\h1.4.1C語(yǔ)言類型系統(tǒng)\h1.4.2函數(shù)\h1.4.3C語(yǔ)言數(shù)據(jù)模型中的操作\h1.4.4數(shù)據(jù)對(duì)象的創(chuàng)建和銷毀\h1.4.5數(shù)據(jù)的訪問(wèn)和修改\h1.4.6數(shù)據(jù)的組合\h1.4.7習(xí)題\h1.5算法和程序設(shè)計(jì)\h1.5.1軟件的創(chuàng)建\h1.5.2編程風(fēng)格\h1.6本書(shū)中用到的一些C語(yǔ)言約定\h1.7小結(jié)\h1.8參考文獻(xiàn)\h第2章迭代、歸納和遞歸\h2.1本章主要內(nèi)容\h2.2迭代\h2.2.1排序\h2.2.2選擇排序：一種迭代排序算法\h2.2.3習(xí)題\h2.3歸納證明\h2.3.1歸納證明為何有效\h2.3.2檢錯(cuò)碼\h2.3.3習(xí)題\h2.4完全歸納\h2.4.1使用多個(gè)依據(jù)情況進(jìn)行歸納\h2.4.2驗(yàn)證完全歸納\h2.4.3算術(shù)表達(dá)式的規(guī)范形式\h2.4.4習(xí)題\h2.5證明程序的屬性\h2.5.1循環(huán)不變式\h2.5.2while循環(huán)的循環(huán)不變式\h2.5.3習(xí)題\h2.6遞歸定義\h2.6.1表達(dá)式\h2.6.2平衡圓括號(hào)\h2.6.3習(xí)題\h2.7遞歸函數(shù)\h習(xí)題\h2.8歸并排序：遞歸的排序算法\h2.8.1合并\h2.8.2分割表\h2.8.3排序算法\h2.8.4完整的程序\h2.8.5習(xí)題\h2.9證明遞歸程序的屬性\h習(xí)題\h2.10小結(jié)\h2.11參考文獻(xiàn)\h第3章程序的運(yùn)行時(shí)間\h3.1本章主要內(nèi)容\h3.2算法的選擇\h3.3度量運(yùn)行時(shí)間\h3.3.1基準(zhǔn)測(cè)試\h3.3.2對(duì)程序的分析\h3.3.3運(yùn)行時(shí)間\h3.3.4不同運(yùn)行時(shí)間的比較\h3.3.5習(xí)題\h3.4大O運(yùn)行時(shí)間和近似運(yùn)行時(shí)間\h3.4.1大O的定義\h3.4.2證明大O關(guān)系\h3.4.3證明大O關(guān)系不成立\h3.4.4習(xí)題\h3.5簡(jiǎn)化大O表達(dá)式\h3.5.1大O表達(dá)式的傳遞律\h3.5.2描述程序的運(yùn)行時(shí)間\h3.5.3緊湊性\h3.5.4簡(jiǎn)單性\h3.5.5求和規(guī)則\h3.5.6不相稱函數(shù)\h3.5.7習(xí)題\h3.6分析程序的運(yùn)行時(shí)間\h3.6.1簡(jiǎn)單語(yǔ)句的運(yùn)行時(shí)間\h3.6.2簡(jiǎn)單for循環(huán)的運(yùn)行時(shí)間\h3.6.3選擇語(yǔ)句的運(yùn)行時(shí)間\h3.6.4程序塊的運(yùn)行時(shí)間\h3.6.5復(fù)雜循環(huán)的運(yùn)行時(shí)間\h3.6.6習(xí)題\h3.7邊界運(yùn)行時(shí)間的遞歸規(guī)則\h3.7.1程序結(jié)構(gòu)的樹(shù)表示\h3.7.2攀爬結(jié)構(gòu)樹(shù)以確定運(yùn)行時(shí)間\h3.7.3循環(huán)運(yùn)行時(shí)間更精確的上界\h3.7.4習(xí)題\h3.8含函數(shù)調(diào)用的程序的分析\h習(xí)題\h3.9遞歸函數(shù)的分析\h習(xí)題\h3.10歸并排序的分析\h3.10.1merge函數(shù)的分析\h3.10.2split函數(shù)的分析\h3.10.3MergeSort函數(shù)\h3.10.4習(xí)題\h3.11為遞推關(guān)系求解\h3.11.1通過(guò)反復(fù)代換為遞推關(guān)系求解\h3.11.2通過(guò)猜測(cè)解為遞推關(guān)系求解\h3.11.3習(xí)題\h3.12小結(jié)\h3.13參考文獻(xiàn)\h第4章組合與概率\h4.1本章主要內(nèi)容\h4.2為分配計(jì)數(shù)\h4.2.1為分配計(jì)數(shù)的規(guī)則\h4.2.2為位串計(jì)數(shù)\h4.2.3習(xí)題\h4.3為排列計(jì)數(shù)\h4.3.1排列公式\h4.3.2排序要花多久\h4.3.3習(xí)題\h4.4有序選擇\h4.4.1無(wú)放回選擇的一般規(guī)則\h4.4.2習(xí)題\h4.5無(wú)序選擇\h4.5.1為組合計(jì)數(shù)\h4.5.2n選m的遞歸定義\h4.5.3計(jì)算的算法的運(yùn)行時(shí)間\h4.5.4函數(shù)的圖像\h4.5.5二項(xiàng)式系數(shù)\h4.5.6習(xí)題\h4.6相同項(xiàng)的次序\h習(xí)題\h4.7將對(duì)象分裝入箱\h4.7.1裝箱問(wèn)題的一般規(guī)則\h4.7.2分裝有區(qū)別的對(duì)象\h4.7.3習(xí)題\h4.8計(jì)數(shù)規(guī)則的組合\h4.8.1將計(jì)數(shù)分解為一系列選擇\h4.8.2用計(jì)數(shù)的差來(lái)計(jì)算計(jì)數(shù)\h4.8.3將計(jì)數(shù)表示為子情況的和\h4.8.4習(xí)題\h4.9概率論簡(jiǎn)介\h4.9.1概率空間\h4.9.2概率的計(jì)算\h4.9.3基本關(guān)系\h4.9.4習(xí)題\h4.10條件概率\h4.10.1獨(dú)立實(shí)驗(yàn)\h4.10.2概率的分配律\h4.10.3獨(dú)立實(shí)驗(yàn)的乘積法則\h4.10.4習(xí)題\h4.11概率推理\h4.11.1OR結(jié)合的兩個(gè)事件的概率\h4.11.2AND結(jié)合的事件的概率\h4.11.3處理事件間關(guān)系的一些方法\h4.11.4習(xí)題\h4.12期望值的計(jì)算\h習(xí)題\h4.13概率在程序設(shè)計(jì)中的應(yīng)用\h4.13.1概率分析\h4.13.2使用概率的算法\h4.13.3習(xí)題\h4.14小結(jié)\h4.15參考文獻(xiàn)\h第5章樹(shù)\h5.1本章主要內(nèi)容\h5.2基本術(shù)語(yǔ)\h5.2.1樹(shù)的等價(jià)遞歸定義\h5.2.2路徑、祖先和子孫\h5.2.3子樹(shù)\h5.2.4葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)\h5.2.5高度和深度\h5.2.6有序樹(shù)\h5.2.7標(biāo)號(hào)樹(shù)\h5.2.8表達(dá)式樹(shù)——一類重要的樹(shù)\h5.2.9習(xí)題\h5.3樹(shù)的數(shù)據(jù)結(jié)構(gòu)\h5.3.1樹(shù)的指針數(shù)組表示\h5.3.2樹(shù)的最左子節(jié)點(diǎn)右兄弟節(jié)點(diǎn)表示\h5.3.3父指針\h5.3.4習(xí)題\h5.4對(duì)樹(shù)的遞歸\h習(xí)題\h5.5結(jié)構(gòu)歸納法\h5.5.1結(jié)構(gòu)歸納法為何有效\h5.5.2習(xí)題\h5.6二叉樹(shù)\h5.6.1二叉樹(shù)的術(shù)語(yǔ)\h5.6.2二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)\h5.6.3對(duì)二叉樹(shù)的遞歸\h5.6.4習(xí)題\h5.7二叉查找樹(shù)\h5.7.1用二叉查找樹(shù)實(shí)現(xiàn)詞典\h5.7.2二叉查找樹(shù)中元素的查找\h5.7.3二叉查找樹(shù)元素的插入\h5.7.4二叉查找樹(shù)元素的刪除\h5.7.5習(xí)題\h5.8二叉查找樹(shù)操作的效率\h5.8.1最壞情況\h5.8.2最佳情況\h5.8.3一般情況\h5.8.4習(xí)題\h5.9優(yōu)先級(jí)隊(duì)列和偏序樹(shù)\h5.9.1偏序樹(shù)\h5.9.2平衡偏序樹(shù)和堆\h5.9.3優(yōu)先級(jí)隊(duì)列操作在堆上的執(zhí)行\(zhòng)h5.9.4優(yōu)先級(jí)隊(duì)列操作的運(yùn)行時(shí)間\h5.9.5習(xí)題\h5.10堆排序：利用平衡偏序樹(shù)排序\h5.10.1數(shù)組的堆化\h5.10.2Heapify的運(yùn)行時(shí)間\h5.10.3完整的堆排序算法\h5.10.4堆排序的運(yùn)行時(shí)間\h5.10.5習(xí)題\h5.11小結(jié)\h5.12參考文獻(xiàn)\h第6章表數(shù)據(jù)模型\h6.1本章主要內(nèi)容\h6.2基本術(shù)語(yǔ)\h6.2.1表的長(zhǎng)度\h6.2.2表的部分\h6.2.3表中元素的位置\h6.2.4習(xí)題\h6.3對(duì)表的操作\h6.3.1插入、刪除和查找\h6.3.2串接\h6.3.3表的其他操作\h6.3.4習(xí)題\h6.4鏈表數(shù)據(jù)結(jié)構(gòu)\h6.4.1詞典操作的鏈表實(shí)現(xiàn)\h6.4.2查找\h6.4.3刪除\h6.4.4插入\h6.4.5帶重復(fù)的插入、查找和刪除\h6.4.6表示詞典的已排序表\h6.4.7各種方法的比較\h6.4.8雙向鏈表\h6.4.9習(xí)題\h6.5表基于數(shù)組的實(shí)現(xiàn)\h6.5.1線性查找\h6.5.2帶哨兵的查找\h6.5.3利用二叉查找對(duì)已排序表進(jìn)行查找\h6.5.4習(xí)題\h6.6棧\h6.6.1對(duì)棧的操作\h6.6.2棧的數(shù)組實(shí)現(xiàn)\h6.6.3棧的鏈表實(shí)現(xiàn)\h6.6.4習(xí)題\h6.7使用棧實(shí)現(xiàn)函數(shù)調(diào)用\h習(xí)題\h6.8隊(duì)列\(zhòng)h6.8.1對(duì)隊(duì)列的操作\h6.8.2隊(duì)列的鏈表實(shí)現(xiàn)\h6.8.3習(xí)題\h6.9最長(zhǎng)公共子序列\(zhòng)h6.9.1對(duì)LCS計(jì)算的遞歸\h6.9.2用于LCS的動(dòng)態(tài)規(guī)劃算法\h6.9.3LCS的恢復(fù)\h6.9.4習(xí)題\h6.10字符串的表示\h6.10.1C語(yǔ)言中的字符串\h6.10.2定長(zhǎng)數(shù)組表示\h6.10.3字符串的鏈表表示\h6.10.4字符串的海量存儲(chǔ)\h6.10.5習(xí)題\h6.11小結(jié)\h6.12參考文獻(xiàn)\h第7章集合數(shù)據(jù)模型\h7.1本章主要內(nèi)容\h7.2基本定義\h7.2.1原子\h7.2.2通過(guò)抽象對(duì)集合的定義\h7.2.3集合的相等性\h7.2.4無(wú)限集\h7.2.5習(xí)題\h7.3集合的運(yùn)算\h7.3.1并集、交集和差集\h7.3.2文氏圖\h7.3.3并集、交集和差集的代數(shù)法則\h7.3.4利用文氏圖證明相等性\h7.3.5利用變形證明相等性\h7.3.6子集關(guān)系\h7.3.7通過(guò)證明則包含關(guān)系對(duì)相等性加以證明\h7.3.8集合的冪集\h7.3.9冪集的大小\h7.3.10習(xí)題\h7.4集合的鏈表實(shí)現(xiàn)\h7.4.1并集、交集和差集\h7.4.2使用已排序表的并集、交集和差集\h7.4.3并集運(yùn)算的運(yùn)行時(shí)間\h7.4.4交集和差集\h7.4.5習(xí)題\h7.5集合的特征向量實(shí)現(xiàn)\h7.5.1集合的數(shù)組實(shí)現(xiàn)\h7.5.2習(xí)題\h7.6散列\(zhòng)h7.6.1散列表數(shù)據(jù)結(jié)構(gòu)\h7.6.2詞典操作的散列表實(shí)現(xiàn)\h7.6.3散列表操作的運(yùn)行時(shí)間\h7.6.4習(xí)題\h7.7關(guān)系和函數(shù)\h7.7.1笛卡兒積\h7.7.2兩個(gè)以上集合的笛卡兒積\h7.7.3二元關(guān)系\h7.7.4關(guān)系的中綴表示\h7.7.5表示二元關(guān)系的圖\h7.7.6函數(shù)\h7.7.7一一對(duì)應(yīng)\h7.7.8習(xí)題\h7.8將函數(shù)作為數(shù)據(jù)來(lái)實(shí)現(xiàn)\h7.8.1對(duì)函數(shù)的操作\h7.8.2函數(shù)的鏈表表示\h7.8.3函數(shù)的向量表示\h7.8.4函數(shù)的散列表表示\h7.8.5對(duì)用散列表表示的函數(shù)的操作\h7.8.6函數(shù)操作的效率\h7.8.7習(xí)題\h7.9二元關(guān)系的實(shí)現(xiàn)\h7.9.1對(duì)二元關(guān)系的操作\h7.9.2二元關(guān)系的鏈表實(shí)現(xiàn)\h7.9.3特征向量法\h7.9.4二元關(guān)系的散列表表示\h7.9.5二元關(guān)系操作的運(yùn)行時(shí)間\h7.9.6習(xí)題\h7.10二元關(guān)系的一些特殊屬性\h7.10.1傳遞性\h7.10.2自反性\h7.10.3對(duì)稱性與反對(duì)稱性\h7.10.4偏序和全序\h7.10.5等價(jià)關(guān)系\h7.10.6等價(jià)類\h7.10.7關(guān)系的閉包\h7.10.8習(xí)題\h7.11無(wú)限集\h7.11.1無(wú)限集的正式定義\h7.11.2可數(shù)集與不可數(shù)集\h7.11.3習(xí)題\h7.12小結(jié)\h7.13參考文獻(xiàn)\h第8章關(guān)系數(shù)據(jù)模型\h8.1本章主要內(nèi)容\h8.2關(guān)系\h8.2.1關(guān)系的表示\h8.2.2數(shù)據(jù)庫(kù)\h8.2.3數(shù)據(jù)庫(kù)的查詢\h8.2.4表示關(guān)系的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)\h8.2.5習(xí)題\h8.3鍵\h8.3.1鍵的確定\h8.3.2習(xí)題\h8.4關(guān)系的主要存儲(chǔ)結(jié)構(gòu)\h8.4.1插入、刪除和查找操作\h8.4.2習(xí)題\h8.5輔助索引結(jié)構(gòu)\h8.5.1非鍵字段上的輔助索引\h8.5.2輔助索引結(jié)構(gòu)的更新\h8.5.3習(xí)題\h8.6關(guān)系間的導(dǎo)航\h8.6.1利用索引為導(dǎo)航提速\h8.6.2多關(guān)系上的導(dǎo)航\h8.6.3習(xí)題\h8.7關(guān)系代數(shù)\h8.7.1關(guān)系代數(shù)的操作數(shù)\h8.7.2關(guān)系代數(shù)的集合運(yùn)算符\h8.7.3選擇運(yùn)算符\h8.7.4投影運(yùn)算符\h8.7.5關(guān)系的聯(lián)接\h8.7.6自然聯(lián)接\h8.7.7關(guān)系代數(shù)表達(dá)式的表達(dá)式樹(shù)\h8.7.8習(xí)題\h8.8關(guān)系代數(shù)運(yùn)算的實(shí)現(xiàn)\h8.8.1并交差的實(shí)現(xiàn)\h8.8.2投影的實(shí)現(xiàn)\h8.8.3選擇的實(shí)現(xiàn)\h8.8.4聯(lián)接的實(shí)現(xiàn)\h8.8.5聯(lián)接方法的比較\h8.8.6習(xí)題\h8.9關(guān)系的代數(shù)法則\h8.9.1涉及并交差的法則\h8.9.2涉及聯(lián)接的法則\h8.9.3涉及選擇的法則\h8.9.4涉及投影的法則\h8.9.5習(xí)題\h8.10小結(jié)\h8.11參考文獻(xiàn)\h第9章圖數(shù)據(jù)模型\h9.1本章主要內(nèi)容\h9.2基本概念\h9.2.1前導(dǎo)和后繼\h9.2.2標(biāo)號(hào)\h9.2.3路徑\h9.2.4有環(huán)圖和無(wú)環(huán)圖\h9.2.5無(wú)環(huán)路徑\h9.2.6無(wú)向圖\h9.2.7無(wú)向圖中的路徑和環(huán)路\h9.2.8習(xí)題\h9.3圖的實(shí)現(xiàn)\h9.3.1鄰接表\h9.3.2鄰接矩陣\h9.3.3對(duì)圖的操作\h9.3.4無(wú)向圖的實(shí)現(xiàn)\h9.3.5標(biāo)號(hào)圖的表示\h9.3.6習(xí)題\h9.4無(wú)向圖的連通分支\h9.4.1作為等價(jià)類的連通分支\h9.4.2計(jì)算連通分支的算法\h9.4.3用于形成分支的數(shù)據(jù)結(jié)構(gòu)\h9.4.4連通分支算法的運(yùn)行時(shí)間\h9.4.5習(xí)題\h9.5最小生成樹(shù)\h9.5.1找到最小生成樹(shù)\h9.5.2克魯斯卡爾算法起效的原因\h9.5.3克魯斯卡爾算法的運(yùn)行時(shí)間\h9.5.4習(xí)題\h9.6深度優(yōu)先搜索\h9.6.1構(gòu)建深度優(yōu)先搜索樹(shù)\h9.6.2深度優(yōu)先搜索樹(shù)弧的分類\h9.6.3深度優(yōu)先搜索森林\h9.6.4深度優(yōu)先搜索算法的運(yùn)行時(shí)間\h9.6.5有向圖的后序遍歷\h9.6.6后序編號(hào)的特殊屬性\h9.6.7習(xí)題\h9.7深度優(yōu)先搜索的一些用途\h9.7.1有向圖中環(huán)路的尋找\h9.7.2無(wú)環(huán)測(cè)試的運(yùn)行時(shí)間\h9.7.3拓?fù)渑判騖h9.7.4可達(dá)性問(wèn)題\h9.7.5可達(dá)性測(cè)試的運(yùn)行時(shí)間\h9.7.6通過(guò)深度優(yōu)先搜索尋找連通分支\h9.7.7習(xí)題\h9.8用于尋找最短路徑的迪杰斯特拉算法\h9.8.1迪杰斯特拉算法起效的原因\h9.8.2迪杰斯特拉算法的數(shù)據(jù)結(jié)構(gòu)\h9.8.3迪杰斯特拉算法的輔助函數(shù)\h9.8.4初始化\h9.8.5迪杰斯特拉算法的實(shí)現(xiàn)\h9.8.6迪杰斯特拉算法的運(yùn)行時(shí)間\h9.8.7習(xí)題\h9.9最短路徑的弗洛伊德算法\h9.9.1弗洛伊德算法為何奏效\h9.9.2習(xí)題\h9.10圖論簡(jiǎn)介\h9.10.1完全圖\h9.10.2平面圖\h9.10.3平面性的應(yīng)用\h9.10.4圖著色\h9.10.5圖著色的應(yīng)用\h9.10.6團(tuán)\h9.10.7習(xí)題\h9.11小結(jié)\h9.12參考文獻(xiàn)\h第10章模式、自動(dòng)機(jī)和正則表達(dá)式\h10.1本章主要內(nèi)容\h10.2狀態(tài)機(jī)和自動(dòng)機(jī)\h10.2.1狀態(tài)機(jī)的圖表示\h10.2.2習(xí)題\h10.3確定自動(dòng)機(jī)和非確定自動(dòng)機(jī)\h10.3.1確定自動(dòng)機(jī)\h10.3.2非確定自動(dòng)機(jī)\h10.3.3非確定自動(dòng)機(jī)的接受\h10.3.4習(xí)題\h10.4從不確定到確定\h10.4.1自動(dòng)機(jī)的等價(jià)性\h10.4.2子集構(gòu)造\h10.4.3子集構(gòu)造起效的原因\h10.4.4習(xí)題\h10.5正則表達(dá)式\h10.5.1正則表達(dá)式的操作數(shù)\h10.5.2正則表達(dá)式的值\h10.5.3正則表達(dá)式的運(yùn)算\h10.5.4正則表達(dá)式運(yùn)算符的優(yōu)先級(jí)\h10.5.5正則表達(dá)式的其他一些示例\h10.5.6習(xí)題\h10.6UNIX對(duì)正則表達(dá)式的擴(kuò)展\h10.6.1字符類\h10.6.2行的開(kāi)頭和結(jié)尾\h10.6.3通配符\h10.6.4額外的運(yùn)算符\h10.6.5習(xí)題\h10.7正則表達(dá)式的代數(shù)法則\h10.7.1取并和串接與加法和乘法的類比\h10.7.2取并和串接與加法和乘法的區(qū)別\h10.7.3涉及閉包的等價(jià)\h10.7.4習(xí)題\h10.8從正則表達(dá)式到自動(dòng)機(jī)\h10.8.1具有ε轉(zhuǎn)換的自動(dòng)機(jī)\h10.8.2從正則表達(dá)式到具有ε轉(zhuǎn)換的自動(dòng)機(jī)\h10.8.3消除ε轉(zhuǎn)換\h10.8.4習(xí)題\h10.9從自動(dòng)機(jī)到正則表達(dá)式\h10.9.1狀態(tài)消除的構(gòu)造\h10.9.2自動(dòng)機(jī)的完全簡(jiǎn)化\h10.9.3習(xí)題\h10.10小結(jié)\h10.11參考文獻(xiàn)\h第11章模式的遞歸描述\h11.1本章主要內(nèi)容\h11.2上下文無(wú)關(guān)文法\h11.2.1與文法相關(guān)的術(shù)語(yǔ)\h11.2.2習(xí)題\h11.3源自文法的語(yǔ)言\h習(xí)題\h11.4分析樹(shù)\h11.4.1分析樹(shù)的構(gòu)建\h11.4.2分析樹(shù)為何“行得通”\h11.4.3習(xí)題\h11.5二義性和文法設(shè)計(jì)\h11.5.1表達(dá)式中的二義性\h11.5.2表示表達(dá)式的無(wú)二義文法\h11.5.3習(xí)題\h11.6分析樹(shù)的構(gòu)造\h11.6.1遞歸下降分析\h11.6.2用于平衡括號(hào)串的遞歸下降分析器\h11.6.3遞歸下降分析器的構(gòu)建\h11.6.4習(xí)題\h11.7表驅(qū)動(dòng)分析算法\h11.7.1分析表\h11.7.2表驅(qū)動(dòng)分析器的工作原理\h11.7.3分析樹(shù)的構(gòu)建\h11.7.4讓文法變得可分析\h11.7.5習(xí)題\h11.8文法與正則表達(dá)式\h11.8.1用文法模擬正則表達(dá)式\h第12章命題邏輯\h12.1本章主要內(nèi)容\h12.2什么是命題邏輯\h12.3邏輯表達(dá)式\h12.3.1邏輯運(yùn)算符的優(yōu)先級(jí)\h12.3.2邏輯表達(dá)式的求值\h12.3.3布爾函數(shù)\h12.3.4習(xí)題\h12.4真值表\h12.4.1真值表的大小\h12.4.2布爾函數(shù)數(shù)量的計(jì)算\h12.4.3更多邏輯運(yùn)算符\h12.4.4具有多個(gè)參數(shù)的運(yùn)算符\h12.4.5邏輯運(yùn)算符的結(jié)合性與優(yōu)先級(jí)\h12.4.6利用真值表為邏輯表達(dá)式求值\h12.4.7習(xí)題\h12.5從布爾函數(shù)到邏輯表達(dá)式\h12.5.1簡(jiǎn)化符號(hào)\h12.5.2從真值表構(gòu)建邏輯表達(dá)式\h12.5.3習(xí)題\h12.6利用卡諾圖設(shè)計(jì)邏輯表達(dá)式\h12.6.1卡諾圖\h12.6.2雙變量卡諾圖\h12.6.3蘊(yùn)涵項(xiàng)\h12.6.4質(zhì)蘊(yùn)涵項(xiàng)\h12.6.5三變量卡諾圖\h12.6.6四變量卡諾圖\h12.6.7習(xí)題\h12.7重言式\h12.7.1替換原則\h12.7.2重言式問(wèn)題\h12.7.3重言式測(cè)試的運(yùn)行時(shí)間\h12.7.4習(xí)題\h12.8邏輯表達(dá)式的一些代數(shù)法則\h12.8.1等價(jià)的法則\h12.8.2類似算術(shù)的法則\h12.8.3AND和OR與加和乘的區(qū)別\h12.8.4德摩根律\h12.8.5對(duì)偶性原理\h12.8.6涉及蘊(yùn)涵的法則\h12.8.7習(xí)題\h12.9重言式及證明方法\h12.9.1排中律\h12.9.2換質(zhì)位法\h12.9.3反證法\h12.9.4等價(jià)于真\h12.9.5習(xí)題\h12.10演繹\h12.10.1演繹證明的構(gòu)成\h12.10.2演繹證明“起作用”的原因\h12.10.3習(xí)題\h12.11分解證明\h12.11.1把邏輯表達(dá)式變成合取范式\h12.11.2利用分解的推理\h12.11.3利用反證法的分解證明\h12.11.4習(xí)題\h12.12小結(jié)\h12.13參考文獻(xiàn)\h第13章利用邏輯設(shè)計(jì)計(jì)算機(jī)元件\h13.1本章主要內(nèi)容\h13.2門(mén)\h13.3電路\h13.3.1組合電路和時(shí)序電路\h13.3.2習(xí)題\h13.4邏輯表達(dá)式和電路\h13.4.1從表達(dá)式到電路\h13.4.2從電路到邏輯表達(dá)式\h13.4.3習(xí)題\h13.5電路的一些物理限制\h13.5.1電路速度\h13.5.2大小限制\h13.5.3扇入和扇出限制\h13.5.4習(xí)題\h13.6分治加法電路\h13.6.1遞歸加法電路\h13.6.2分治加法器的延遲\h13.6.3分治加法器使用的門(mén)的數(shù)量\h13.6.4習(xí)題\h13.7多路復(fù)用器的設(shè)計(jì)\h13.7.1分治多路復(fù)用器\h13.7.2分治MUX的延遲\h13.7.3門(mén)的數(shù)量\h13.7.4習(xí)題\h13.8存儲(chǔ)單元\h13.9小結(jié)\h13.10參考文獻(xiàn)\h第14章謂詞邏輯\h14.1本章主要內(nèi)容\h14.2謂詞\h14.2.1原子公式\h14.2.2常量和變量的區(qū)分\h14.2.3習(xí)題\h14.3邏輯表達(dá)式\h14.3.1文字\h14.3.2邏輯表達(dá)式\h14.3.3其他術(shù)語(yǔ)\h14.3.4習(xí)題\h14.4量詞\h14.4.1邏輯表達(dá)式的遞歸定義\h14.4.2運(yùn)算符的優(yōu)先級(jí)\h14.4.3約束變量和自由變量\h14.4.4習(xí)題\h14.5解釋\h14.5.1表達(dá)式的含義\h14.5.2習(xí)題\h14.6重言式\h14.6.1替換原則\h14.6.2表達(dá)式的等價(jià)\h14.6.3習(xí)題\h14.7涉及量詞的重言式\h14.7.1變量的重命名\h14.7.2自由變量的全稱量詞化\h14.7.3閉表達(dá)式\h14.7.4把量詞移過(guò)NOT\h14.7.5把量詞移過(guò)AND和OR\h14.7.6前束式\h14.7.7量詞的重新排列\(zhòng)h14.7.8習(xí)題\h14.8謂詞邏輯中的證明\h14.8.1隱式全稱量詞\h14.8.2作為推理規(guī)則的變量替換\h14.8.3習(xí)題\h14.9根據(jù)規(guī)則和事實(shí)的證明\h14.9.1簡(jiǎn)化的推理規(guī)則\h14.9.2習(xí)題\h14.10真理和可證性\h14.10.1模型\h14.10.2蘊(yùn)涵\h14.10.3可證性與蘊(yùn)涵的比較\h14.10.4哥德?tīng)柌煌陚湫远ɡ韁h14.10.5計(jì)算機(jī)能完成的工作的限制\h14.10.6習(xí)題第1章計(jì)算機(jī)科學(xué)：將抽象機(jī)械化計(jì)算機(jī)科學(xué)是個(gè)新領(lǐng)域，不過(guò)它幾乎已經(jīng)觸及人類工作的每個(gè)方面。計(jì)算機(jī)、信息系統(tǒng)、文本編輯器、電子表格的普及，以及使得計(jì)算機(jī)更便于使用、人們生產(chǎn)效率的精彩應(yīng)用程序的激增，都顯示出計(jì)算機(jī)科學(xué)對(duì)社會(huì)的影響。該領(lǐng)域有個(gè)重要的部分，涉及如何讓程序設(shè)計(jì)更容易以及讓軟件更可靠。不過(guò)從根本上講，計(jì)算機(jī)科學(xué)是一門(mén)抽象的科學(xué)，它為人們思考問(wèn)題以及找到適當(dāng)?shù)臋C(jī)械化技術(shù)解決問(wèn)題而建立模型。其他科學(xué)是順其自然地研究宇宙。例如，物理學(xué)家的工作就是理解世界是如何運(yùn)轉(zhuǎn)的，而不是去創(chuàng)造一個(gè)用物理定律能更好地理解的世界。而計(jì)算機(jī)科學(xué)家則必須抽象現(xiàn)實(shí)世界中的問(wèn)題，使其既可以為計(jì)算機(jī)用戶所理解，又可以在計(jì)算機(jī)內(nèi)加以表示和操作。進(jìn)行抽象的過(guò)程有時(shí)很簡(jiǎn)單。例如，我們能熟練地用“命題邏輯”這種抽象方式，為制造計(jì)算機(jī)所使用的電子電路的行為建模。通過(guò)邏輯表達(dá)式進(jìn)行的電路建模是不準(zhǔn)確的，它簡(jiǎn)化了或者說(shuō)是抽象掉了很多細(xì)節(jié)，比如電子流經(jīng)電路和門(mén)所花的時(shí)間。然而，命題邏輯模型已經(jīng)足夠幫助我們順利設(shè)計(jì)計(jì)算機(jī)電路了。我們將在第12章中更多地探討命題邏輯。再舉個(gè)例子，假設(shè)我們要為各種課程的期末考試排定時(shí)間。也就是說(shuō)，我們必須為各門(mén)課程的考試指定時(shí)段，只有在沒(méi)有學(xué)生同時(shí)選擇某兩門(mén)課程的前提下，才將這兩門(mén)課程的考試安排在同一時(shí)段。如何為這一問(wèn)題建模，起初可能不太好確定。一種方式是為每門(mén)課程畫(huà)一個(gè)稱為節(jié)點(diǎn)（node）的圓，如果有學(xué)生同時(shí)選擇了兩門(mén)課程，就畫(huà)一條線來(lái)連接相應(yīng)的兩個(gè)節(jié)點(diǎn)，這條線稱為邊（edge）。圖1-1表示了5門(mén)課程可能的關(guān)系圖，這幅圖就是課程沖突圖。圖1-15門(mén)課程的課程沖突圖，兩門(mén)課程之間的邊表示至少有一個(gè)學(xué)生同時(shí)選擇了這兩門(mén)課程有了課程沖突圖，我們就可以通過(guò)在圖中反復(fù)找出并刪除“最大獨(dú)立集”來(lái)解決考試安排問(wèn)題。獨(dú)立集是沒(méi)有邊相連接的節(jié)點(diǎn)的集合。如果不能再向某獨(dú)立集添加圖中的其他節(jié)點(diǎn)了，那么就說(shuō)這個(gè)獨(dú)立集是最大獨(dú)立集。即，一個(gè)圖中包含節(jié)點(diǎn)數(shù)目最多的獨(dú)立集稱為最大獨(dú)立集。在說(shuō)課程時(shí)，最大獨(dú)立集就是指沒(méi)有共同學(xué)生的課程的最大集合。在圖1-1中，｛經(jīng)濟(jì)學(xué)，英語(yǔ)，物理｝就是一個(gè)最大獨(dú)立集。最大獨(dú)立集中的這些課程被指定到第一個(gè)時(shí)段。我們從圖中刪除第一個(gè)最大獨(dú)立集中的節(jié)點(diǎn)以及這些節(jié)點(diǎn)附帶的邊，接著在剩下的課程中找出最大獨(dú)立集。下一個(gè)可選的最大獨(dú)立集是單元素集｛計(jì)算機(jī)科學(xué)｝。這個(gè)最大獨(dú)立集中的課程便被分配到第二個(gè)時(shí)段。如此重復(fù)找出并刪除最大獨(dú)立集，直到課程沖突圖中不再有任何節(jié)點(diǎn)。至此，所有課程都已經(jīng)被分配到各時(shí)段中。本例中，在兩次迭代之后，課程沖突圖中就只剩下數(shù)學(xué)節(jié)點(diǎn)了，而它就組成了最后一個(gè)最大獨(dú)立集，將被指定到第三個(gè)時(shí)段中。形成的考試排期如下：時(shí)段課程考試1經(jīng)濟(jì)學(xué)，英語(yǔ)，物理2計(jì)算機(jī)科學(xué)3數(shù)學(xué)這一算法不見(jiàn)得會(huì)將各門(mén)需要考試的課程分布在數(shù)目盡可能少的時(shí)段中，不過(guò)它很簡(jiǎn)單，而且生成的時(shí)間安排中所含的時(shí)段數(shù)目往往接近最小值。利用第9章介紹的技術(shù)，它也很容易被設(shè)計(jì)成計(jì)算機(jī)程序。請(qǐng)注意，這種方式會(huì)將一些可能很重要的問(wèn)題細(xì)節(jié)抽象掉。例如，它可能會(huì)讓某個(gè)學(xué)生在5個(gè)連續(xù)的時(shí)段內(nèi)參加5科考試。也許我們可以建立這樣一個(gè)模型，對(duì)某個(gè)學(xué)生一次可能連續(xù)參加考試的科目數(shù)加以限制，不過(guò)這樣一來(lái)，建立的模型和考試安排問(wèn)題的解決方案都可能變得更加復(fù)雜。抽象：不用擔(dān)心讀者可能會(huì)對(duì)“抽象”這個(gè)詞有所忌憚，因?yàn)槲覀兌加羞@樣一種直覺(jué)：抽象的東西都是難以理解的。例如，人們一般會(huì)認(rèn)為抽象代數(shù)（研究群、環(huán)，諸如此類）要比高中時(shí)學(xué)的代數(shù)難。然而，我們所使用的抽象意味著簡(jiǎn)化，是將現(xiàn)實(shí)中復(fù)雜而詳細(xì)的情景替換為解決問(wèn)題所使用的可理解模型。也就是說(shuō)，我們將那些對(duì)解決問(wèn)題而言影響甚微或根本沒(méi)有影響的細(xì)節(jié)“抽象掉”了，從而建立一個(gè)讓我們能處理問(wèn)題實(shí)質(zhì)的模型。通常情況下，找到好的抽象方式是相當(dāng)困難的，因?yàn)橛?jì)算機(jī)能執(zhí)行的任務(wù)有限，執(zhí)行速度也有限。在計(jì)算機(jī)科學(xué)的初期階段，一些樂(lè)觀主義者認(rèn)為機(jī)器人很快就能像《星球大戰(zhàn)》中的C3PO機(jī)器人那樣神通廣大。自那時(shí)起，我們已經(jīng)了解到，要讓計(jì)算機(jī)（或機(jī)器人）具有“智能”行為，就需要為計(jì)算機(jī)提供一個(gè)本質(zhì)上跟人類所支配的世界一樣詳細(xì)的模型，不僅要包括事實(shí)（“薩莉的電話號(hào)碼是555-1234”），還要包括原則和關(guān)系（“如果拋出某物體，它通常會(huì)向下墜落”）。我們?cè)凇爸R(shí)的表示”這一問(wèn)題上已經(jīng)取得了很大的進(jìn)步，設(shè)計(jì)出了一些抽象方式，可用來(lái)構(gòu)建進(jìn)行某類推理的程序。有向圖便是這種抽象的一個(gè)例子，它用節(jié)點(diǎn)表示實(shí)體（“貓”或“松毛”），用從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)的箭頭（稱為弧）代表關(guān)系（“松毛是只貓”，“貓是動(dòng)物”，“松毛的牛奶碟子歸松毛所有”），圖1-2就展示了這樣一幅圖。圖1-2這幅圖用于表示與“松毛”相關(guān)的知識(shí)另一種實(shí)用的抽象是形式邏輯，它讓我們可以運(yùn)用推理規(guī)則推導(dǎo)事實(shí)，比如“如果X是只貓，Y是X的母親，那么Y是只貓”。不過(guò)，為現(xiàn)實(shí)世界或其關(guān)鍵部分建模（或者說(shuō)是對(duì)其進(jìn)行抽象）的過(guò)程，卻仍是計(jì)算機(jī)科學(xué)所面臨的一大挑戰(zhàn)，是近期沒(méi)法徹底解決的。1.1本書(shū)主要內(nèi)容本書(shū)目標(biāo)讀者應(yīng)當(dāng)具有一定的ANSIC語(yǔ)言程序設(shè)計(jì)實(shí)踐經(jīng)驗(yàn)，本書(shū)旨在為這些讀者介紹計(jì)算機(jī)科學(xué)的基本概念和重點(diǎn)內(nèi)容。書(shū)中強(qiáng)調(diào)了如下三種重要的問(wèn)題解決工具。1.數(shù)據(jù)模型。數(shù)據(jù)特征的抽象，用來(lái)描述問(wèn)題。我們已經(jīng)提到了兩種模型：邏輯和圖，而在本書(shū)中還會(huì)看到很多其他的模型。2.數(shù)據(jù)結(jié)構(gòu)。用來(lái)表示數(shù)據(jù)模型的編程語(yǔ)言結(jié)構(gòu)。例如，C語(yǔ)言提供了內(nèi)置的抽象，比如結(jié)構(gòu)和指針，使我們能夠構(gòu)建數(shù)據(jù)結(jié)構(gòu)，表示像圖這類的復(fù)雜抽象。3.算法。操作用數(shù)據(jù)模型抽象、數(shù)據(jù)結(jié)構(gòu)等形式表示的數(shù)據(jù)，從而獲取解決方案的技術(shù)。1.1.1數(shù)據(jù)模型我們?cè)趦煞N情況下會(huì)提到數(shù)據(jù)模型。像本章開(kāi)頭討論的圖這樣的數(shù)據(jù)模型，是常用于協(xié)助形成問(wèn)題解決方案的抽象。我們還會(huì)在本書(shū)中了解多種這樣的數(shù)據(jù)模型，比如第5章介紹的樹(shù)、第6章介紹的表、第7章介紹的集、第8章介紹的關(guān)系、第9章介紹的圖、第10章介紹的有限自動(dòng)機(jī)、第11章介紹的語(yǔ)法，以及第12章和第14章介紹的邏輯。數(shù)據(jù)模型還與編程語(yǔ)言及計(jì)算機(jī)相關(guān)。比如，C語(yǔ)言的數(shù)據(jù)模型就包含諸如字符、多種長(zhǎng)度的整數(shù)以及浮點(diǎn)數(shù)這類的抽象。C語(yǔ)言中的整數(shù)和浮點(diǎn)數(shù)只是數(shù)學(xué)意義上整數(shù)和實(shí)數(shù)的近似值，因?yàn)橛?jì)算機(jī)所能提供的算術(shù)精度是有限的。C語(yǔ)言數(shù)據(jù)模型還包括結(jié)構(gòu)、指針和函數(shù)這樣的類型，我們將在1.4節(jié)中詳細(xì)介紹。1.1.2數(shù)據(jù)結(jié)構(gòu)當(dāng)手頭問(wèn)題的數(shù)據(jù)模型不能直接用編程語(yǔ)言內(nèi)置的數(shù)據(jù)模型表示時(shí)，我們就必須使用該語(yǔ)言所支持的抽象來(lái)表示所需的數(shù)據(jù)模型。為此，我們研究了數(shù)據(jù)結(jié)構(gòu)，將編程語(yǔ)言中沒(méi)有顯式包含的抽象，以該語(yǔ)言的數(shù)據(jù)模型表示出來(lái)。不同的編程語(yǔ)言可能有著大不相同的數(shù)據(jù)模型。例如，與C語(yǔ)言不同，Lisp語(yǔ)言直接支持樹(shù)，而Prolog語(yǔ)言則內(nèi)置了邏輯數(shù)據(jù)模型。1.1.3算法算法是對(duì)可機(jī)械執(zhí)行的一系列步驟精準(zhǔn)而明確的規(guī)范。用來(lái)表示算法的可以是任何一種可被常人理解的語(yǔ)言，不過(guò)在計(jì)算機(jī)科學(xué)領(lǐng)域，算法多用編程語(yǔ)言正式地表現(xiàn)為計(jì)算機(jī)程序，或用編程語(yǔ)言混合英語(yǔ)語(yǔ)句的非正式風(fēng)格來(lái)表示。大家在學(xué)習(xí)編程時(shí)很可能已經(jīng)遇到過(guò)一些重要算法。例如，有不少為數(shù)組元素排序的算法，就是按照從小到大的順序排列數(shù)組元素。有一些諸如二叉查找（binarysearching）之類的查找算法很巧妙，可以通過(guò)反復(fù)將某給定元素在數(shù)組中可能出現(xiàn)的部分對(duì)半劃分，迅速地找到這個(gè)元素。這些算法以及其他一些解決常規(guī)問(wèn)題的“招數(shù)”，是計(jì)算機(jī)科學(xué)家們?cè)谠O(shè)計(jì)程序時(shí)會(huì)用到的工具。我們將在本書(shū)中學(xué)習(xí)諸多此類技巧，包括重要的排序和查找方法。此外，我們還要了解使一種算法優(yōu)于其他算法的因素。很多時(shí)候，運(yùn)行時(shí)間（runningtime），或者說(shuō)算法處理輸入所花的時(shí)間，是算法“質(zhì)量”的重要一環(huán)，我們會(huì)在第3章中討論。算法的其他方面也很重要，特別是簡(jiǎn)易性。理想情況下，算法應(yīng)該易于理解，并易于轉(zhuǎn)變成可運(yùn)轉(zhuǎn)的程序。而且，懂得相應(yīng)知識(shí)的人在閱讀了實(shí)現(xiàn)該算法的代碼后，應(yīng)該能理解由該算法轉(zhuǎn)變而來(lái)的程序。不過(guò)快速和簡(jiǎn)易往往是不能兩全的，所以我們必須要明智地選擇算法。1.1.4基本思路在進(jìn)一步閱讀本書(shū)的過(guò)程中，我們將遇到一些重要的統(tǒng)一原則。在這里要提以下兩點(diǎn)。1.設(shè)計(jì)代數(shù)。在底層模型得到充分了解的某些領(lǐng)域，我們可以提出一些表示法，以便表示和評(píng)價(jià)某些折衷的設(shè)計(jì)方案。通過(guò)這樣的認(rèn)識(shí)，我們可以提出一些設(shè)計(jì)理論以構(gòu)建出設(shè)計(jì)良好的系統(tǒng)。命題邏輯，加上第12章中的布爾代數(shù)這種相關(guān)的表示法，就是設(shè)計(jì)代數(shù)的一個(gè)好例子。有了它，我們可以為數(shù)字計(jì)算機(jī)中的子系統(tǒng)設(shè)計(jì)高效的電路。其他設(shè)計(jì)代數(shù)的例子還包括第7章中的集代數(shù)、第8章中的關(guān)系代數(shù)，以及第10章中的正則表達(dá)式代數(shù)。2.遞歸。作為一種可用來(lái)定義概念和解決問(wèn)題的實(shí)用技術(shù)，遞歸特別值得一提。我們會(huì)在第2章中詳細(xì)討論遞歸，本書(shū)后續(xù)內(nèi)容中也會(huì)反復(fù)用到它。每當(dāng)我們需要精確地定義對(duì)象，或需要解決問(wèn)題時(shí)，都應(yīng)該問(wèn)一問(wèn)：“遞歸解決方案應(yīng)當(dāng)是什么樣子呢？”遞歸方案的簡(jiǎn)易和效率常使其成為最優(yōu)方法。1.2本章主要內(nèi)容本章接下來(lái)的部分將為計(jì)算機(jī)科學(xué)的學(xué)習(xí)做好鋪墊，要介紹以下主要概念。數(shù)據(jù)模型（1.3節(jié)）。C語(yǔ)言的數(shù)據(jù)模型（1.4節(jié)）。軟件開(kāi)發(fā)流程的主要步驟（1.5節(jié)）。我們會(huì)介紹一些例子，講講抽象和模型出現(xiàn)在計(jì)算機(jī)系統(tǒng)的幾種方式。其中特別提到了編程語(yǔ)言中的模型、特定系統(tǒng)程序（比如操作系統(tǒng)）中的模型，以及計(jì)算機(jī)所使用電路中的模型。由于軟件是當(dāng)今計(jì)算機(jī)系統(tǒng)的重要組成部分，因此我們需要理解軟件開(kāi)發(fā)流程、模型和算法扮演的角色，以及軟件開(kāi)發(fā)中計(jì)算機(jī)科學(xué)只能以有限方式解決的那些方面。在1.6節(jié)中會(huì)介紹一些常規(guī)定義，它們?cè)谌珪?shū)的C語(yǔ)言程序中都將用到。1.3數(shù)據(jù)模型任何數(shù)學(xué)概念都可稱為數(shù)據(jù)模型。而在計(jì)算機(jī)科學(xué)領(lǐng)域，數(shù)據(jù)模型通常包含以下兩個(gè)方面。1.對(duì)象可以采用的值。例如，很多數(shù)據(jù)模型包含具有整數(shù)值的對(duì)象。數(shù)據(jù)模型的這個(gè)方面是靜態(tài)的，它告訴我們對(duì)象能接受哪些值。編程語(yǔ)言數(shù)據(jù)模型的這一靜態(tài)部分通常被稱為類型系統(tǒng)。2.數(shù)據(jù)的運(yùn)算。例如，我們常常會(huì)對(duì)整數(shù)執(zhí)行加法這樣的運(yùn)算。模型的這一方面是動(dòng)態(tài)的，它告訴我們改變值和創(chuàng)建新值的方式。1.3.1編程語(yǔ)言數(shù)據(jù)模型每種編程語(yǔ)言都有自己的數(shù)據(jù)模型，這些數(shù)據(jù)模型互不相同，而且通常有相當(dāng)大的差異。多數(shù)編程語(yǔ)言處理數(shù)據(jù)所遵循的基本原則是，每個(gè)程序都可以訪問(wèn)我們用于表示存儲(chǔ)區(qū)域的“框”。每個(gè)框都具有一個(gè)類型，比如int或char?？蛑锌梢源鎯?chǔ)類型對(duì)應(yīng)的值，通常將可以存儲(chǔ)到這些框中的值稱為數(shù)據(jù)對(duì)象。我們還要為這些框命名。一般來(lái)說(shuō)，框的名稱可以是任何指示該框的表述性詞語(yǔ)。我們通常會(huì)將框的名稱視作該程序的變量，不過(guò)情況并非完全如此。例如，如果x是遞歸函數(shù)F的局部變量，那么就可能會(huì)有很多名為x的框，每個(gè)x都與對(duì)F的不同調(diào)用相關(guān)聯(lián)。這樣的話，這種框的真實(shí)名稱就是x與對(duì)F的某次調(diào)用的組合。C語(yǔ)言中的多數(shù)數(shù)據(jù)類型都是我們熟悉的：整數(shù)、浮點(diǎn)數(shù)、字符、數(shù)組、結(jié)構(gòu)和指針。這些都是靜態(tài)的概念?？梢詫?duì)數(shù)據(jù)進(jìn)行的操作包括整數(shù)和浮點(diǎn)數(shù)的常規(guī)算術(shù)運(yùn)算、數(shù)組或結(jié)構(gòu)元素的存取操作，以及指針的解引用（也就是找到指針?biāo)赶虻脑兀?。這些運(yùn)算都只是C語(yǔ)言數(shù)據(jù)模型動(dòng)態(tài)部分的一部分。在程序設(shè)計(jì)課程中，我們可能會(huì)看到C語(yǔ)言中不包括的重要數(shù)據(jù)模型，比如表、樹(shù)和圖。用數(shù)學(xué)語(yǔ)言來(lái)講，表就是可以寫(xiě)成(a1,a2,…,an)這種形式的n個(gè)元素組成的序列，其中a1是第一個(gè)元素，a2是第二個(gè)，以此類推。表的運(yùn)算包含插入新元素、刪除元素，以及拼接表（也就是將一個(gè)表追加到另一表的末端）。示例1.1在C語(yǔ)言中，整數(shù)表可以用鏈表這種數(shù)據(jù)結(jié)構(gòu)表示，表的元素被存儲(chǔ)在鏈表的節(jié)點(diǎn)中。鏈表及其節(jié)點(diǎn)可用如下類型聲明定義。typedefstructCELL*LIST;

structCELL{

intelement;

structLISTnext;

};

該聲明定義了有著兩個(gè)字段的自引用結(jié)構(gòu)CELL。第一個(gè)字段是element，存放著表中元素的值，而且其類型為int。每個(gè)CELL的第二個(gè)字段是next，存放著指向節(jié)點(diǎn)的指針。請(qǐng)注意，LIST類型其實(shí)是指向CELL的指針。因此，CELL類型的結(jié)構(gòu)可以通過(guò)它們的next字段鏈接起來(lái)，構(gòu)成我們通常所說(shuō)的鏈表，如圖1-3所示。next字段既可以被視為指向下一個(gè)節(jié)點(diǎn)的指針，也可以代表從某節(jié)點(diǎn)起的整段鏈表。同理，整個(gè)鏈表也可以用指向鏈表第一個(gè)單元的LIST類型的指針表示。圖1-3表示表(a1,a2,…,an)的鏈表單元是用長(zhǎng)方形表示的，其左邊部分表示元素，右邊部分存放指針（表示為指向下一個(gè)單元的箭頭）。存放指針的方框中的點(diǎn)表示該指針為NULL1。第6章將更詳細(xì)地介紹表。1NULL是標(biāo)準(zhǔn)頭文件stdio.h中定義的符號(hào)常量，用來(lái)表示未指向任何內(nèi)容的指針的值。本書(shū)中的NULL指針都作此義解釋。數(shù)據(jù)模型與數(shù)據(jù)結(jié)構(gòu)盡管名稱類似，但“表”和“鏈表”卻是非常不同的概念。表是種數(shù)學(xué)抽象，或者說(shuō)是數(shù)據(jù)模型。而鏈表則是種數(shù)據(jù)結(jié)構(gòu)，是通常用于C語(yǔ)言及相似語(yǔ)言中的數(shù)據(jù)結(jié)構(gòu)，用來(lái)表示程序中的抽象表。而有些編程語(yǔ)言則不需要用數(shù)據(jù)結(jié)構(gòu)來(lái)表示抽象表。例如，表(a1,a2,…,an)在Lisp語(yǔ)言中可以直接表示為[a1,a2,…,an]，而在Prolog語(yǔ)言中也可以表示為類似形式。1.3.2系統(tǒng)軟件的數(shù)據(jù)模型數(shù)據(jù)模型不僅存在于編程語(yǔ)言中，而且存在于操作系統(tǒng)和應(yīng)用程序中。大家可能熟悉UNIX或MS-DOS這樣的操作系統(tǒng)，也可能熟悉MicrosoftWindows。2操作系統(tǒng)的功能是管理和調(diào)度計(jì)算機(jī)的資源。像UNIX這樣的操作系統(tǒng)，其數(shù)據(jù)模型具有文件、目錄和進(jìn)程這樣的概念。2如果對(duì)操作系統(tǒng)不熟悉，那么可以跳過(guò)下面幾個(gè)段落。不過(guò)大多數(shù)讀者都應(yīng)該接觸過(guò)操作系統(tǒng)，可能只是稱呼不同。例如，Macintosh“系統(tǒng)”就是一種操作系統(tǒng)，只是使用了不同的術(shù)語(yǔ)。例如，在蘋(píng)果用語(yǔ)中，目錄就被稱為“文件夾”。1.數(shù)據(jù)本身存儲(chǔ)在文件中，在UNIX系統(tǒng)中，文件都是字符串和字符。2.文件被組織成目錄，目錄就是文件和（或）其他目錄的集合。目錄和文件形成了樹(shù)形結(jié)構(gòu)，而文件處在樹(shù)葉的位置3。圖1-4中的樹(shù)可以表示UNIX操作系統(tǒng)的目錄結(jié)構(gòu)。目錄是用圓圈表示的。根目錄/包含名為mnt、usr、bin等的目錄。目錄/usr含有目錄ann和bob，而目錄ann下含有3個(gè)文件：a1、a2和a3。3不過(guò)，目錄中的“鏈接”可能會(huì)讓某個(gè)文件或目錄看起來(lái)像是幾個(gè)不同目錄的一部分。3.進(jìn)程是指程序的獨(dú)立執(zhí)行。進(jìn)程接受流作為輸入，并產(chǎn)生流作為輸出。在UNIX系統(tǒng)中，進(jìn)程可以通過(guò)管道連接，讓一個(gè)進(jìn)程的輸出作為下一個(gè)進(jìn)程的輸入。這種進(jìn)程組合可看作有著自己輸入輸出的獨(dú)立進(jìn)程。圖1-4具有代表性的UNIX目錄/文件結(jié)構(gòu)示例1.2想想如下UNIX命令行。bc|word|speak

符號(hào)|表示管道，該操作使符號(hào)左邊進(jìn)程的輸出成為符號(hào)右邊進(jìn)程的輸入。程序bc是桌面計(jì)算器，接受算術(shù)表達(dá)式（例如2+3）作為輸入，并生成答案5作為輸出。程序word用來(lái)將數(shù)字轉(zhuǎn)換成單詞，而speak則將單詞轉(zhuǎn)換成音素序列，接著通過(guò)揚(yáng)聲器將語(yǔ)音合成器合成的聲音播放出來(lái)。這三個(gè)程序通過(guò)管道連接起來(lái)，使這條UNIX命令行成為了一個(gè)進(jìn)程，并表現(xiàn)為一個(gè)“會(huì)說(shuō)話的”桌面計(jì)算器。它接受算術(shù)表達(dá)式作為輸入，并產(chǎn)生說(shuō)出來(lái)的答案作為輸出。本示例還可以說(shuō)明，將復(fù)雜的任務(wù)處理成多個(gè)簡(jiǎn)單功能的組合，實(shí)現(xiàn)起來(lái)可能會(huì)更加簡(jiǎn)單。操作系統(tǒng)還有其他許多方面，比如它如何控制數(shù)據(jù)安全以及與用戶的互動(dòng)。不過(guò)，即便是通過(guò)這些簡(jiǎn)單的觀察，也應(yīng)該很容易看出，操作系統(tǒng)的數(shù)據(jù)模型和編程語(yǔ)言的數(shù)據(jù)模型是相當(dāng)不同的。文本編輯器中有另一種數(shù)據(jù)模型。文本編輯器的每種數(shù)據(jù)模型都結(jié)合了文本字符串的表示和對(duì)文本的編輯操作。這種數(shù)據(jù)模型通常會(huì)包含行的概念，行和多數(shù)文件一樣，就是字符串。不過(guò)，與文件不同的是，行可能有著與其相關(guān)聯(lián)的行號(hào)。行還可能被組織成更大的單元（比如段落），而且對(duì)行進(jìn)行的操作通常適用于行內(nèi)的任何位置，而不會(huì)像多數(shù)常見(jiàn)的文件操作那樣，只是對(duì)前部進(jìn)行操作。一般的文本編輯器會(huì)支持“當(dāng)前”行（光標(biāo)所在的那一行）的概念，還可能支持行內(nèi)當(dāng)前位置的概念。文本編輯器執(zhí)行的操作包括對(duì)行的多種修改，比如在行內(nèi)刪除或插入字符、刪除行，以及創(chuàng)建新行。在一般的文本編輯器中還可以在已編輯文件的行中搜索特定的字符串。其實(shí)，如果看看其他熟悉的軟件，比如電子表格或視頻游戲，就會(huì)發(fā)現(xiàn)，每個(gè)調(diào)用程序都必須遵守被調(diào)用程序的數(shù)據(jù)模型。我們見(jiàn)到的各種數(shù)據(jù)模型通常彼此間截然不同，無(wú)論是用來(lái)表示數(shù)據(jù)的原語(yǔ)，還是向用戶提供的數(shù)據(jù)操作方式，全都不同。而且各數(shù)據(jù)模型都是通過(guò)數(shù)據(jù)結(jié)構(gòu)和使用它們的程序，用某種編程語(yǔ)言實(shí)現(xiàn)的。1.3.3電路的數(shù)據(jù)模型在本書(shū)中我們還會(huì)看到計(jì)算機(jī)電路使用的數(shù)據(jù)模型。這種模型就是命題邏輯，在計(jì)算機(jī)設(shè)計(jì)中是最實(shí)用的。計(jì)算機(jī)是由稱為門(mén)的基本元件組成的。每個(gè)門(mén)都有著一個(gè)或多個(gè)輸入以及一個(gè)輸出，輸入或輸出的值只能是0或1。門(mén)具有一個(gè)簡(jiǎn)單的功能，比如AND運(yùn)算（與運(yùn)算），就是如果所有輸入為1，那么輸出就是1，而如果至少有一個(gè)輸入為0，那么輸出就是0。從某個(gè)抽象層次來(lái)講，計(jì)算機(jī)設(shè)計(jì)就是選擇如何連接門(mén)來(lái)執(zhí)行計(jì)算機(jī)基本運(yùn)算的過(guò)程。當(dāng)然也存在其他很多與計(jì)算機(jī)設(shè)計(jì)相關(guān)的抽象層次。圖1-5展示了常見(jiàn)的與門(mén)符號(hào)以及對(duì)應(yīng)的真值表，該表指明了每對(duì)輸入值搭配經(jīng)過(guò)該門(mén)產(chǎn)生的輸出值4。我們將在第12章中介紹真值表，并在第13章中介紹門(mén)及門(mén)的互相連接。4請(qǐng)注意，若我們將1視為“真”，將0視為“假”，則與門(mén)執(zhí)行的是和C語(yǔ)言中&&運(yùn)算符相同的邏輯運(yùn)算。圖1-5與門(mén)及其真值表示例1.3執(zhí)行C語(yǔ)言賦值語(yǔ)句a=b+c，計(jì)算機(jī)會(huì)使用加法電路執(zhí)行加法運(yùn)算。在計(jì)算機(jī)中，所有數(shù)字都是以二進(jìn)制的形式，使用0和1這兩個(gè)數(shù)字（叫作二進(jìn)制數(shù)字，或簡(jiǎn)稱位）表示的。二進(jìn)制加法計(jì)算也遵守十進(jìn)制加法的法則，從右端的數(shù)字開(kāi)始相加，如果產(chǎn)生進(jìn)位，就將進(jìn)位加到右起第二位上，如果這一位上相加的結(jié)果還產(chǎn)生進(jìn)位，就繼續(xù)加到右起第三位上，以此類推。我們可以用幾個(gè)門(mén)來(lái)組建一位加法器（one-bitadder）電路，如圖1-6所示。兩個(gè)輸入位x和y，一個(gè)進(jìn)位輸入位c，經(jīng)過(guò)相加，形成一個(gè)和值位z，以及進(jìn)位輸出位d。更精確地講，如圖1-7所示，如果c、x和y中有不少于兩個(gè)的值為1，那么d的值就是1，而如果c、x和y中有奇數(shù)個(gè)（1個(gè)或3個(gè)）的值為1，那么z的值就是1。進(jìn)位輸出位后面跟上和值位（即dz）就形成了一個(gè)兩位的二進(jìn)制數(shù)，這就是x、y和c為1時(shí)的總值。在這種情況下，這個(gè)一位加法器就完成了輸入的相加運(yùn)算。圖1-6一位加法器：dz是x+y+c的和圖1-7一位加法器的真值表行波進(jìn)位加法算法在進(jìn)行十進(jìn)制數(shù)的加法時(shí)，我們都使用過(guò)行波進(jìn)位算法。拿456+829舉例，相加的步驟應(yīng)該如下所示。也就是說(shuō)，第一步，我們會(huì)將最右邊的位相加，6+9=15。記下5，并將進(jìn)位1放到第二列。第二步，我們將進(jìn)位輸入1與右起第二位的兩個(gè)數(shù)字相加，得到1+5+2=8。記下8，進(jìn)位是0。第三步，將進(jìn)位輸入0，與右起第三位上的數(shù)字相加，得到0+4+8=12。記下2，由于我們已經(jīng)計(jì)算到了最左邊的位，因此就不將1進(jìn)位，而是將其作為結(jié)果中最左邊的一位。二進(jìn)制行波進(jìn)位加法也有著相同的原理。只不過(guò)，在每一位上，進(jìn)位和要相加的“數(shù)字”要么是0，要么是1。因此一位加法器完整地描述了單個(gè)數(shù)位上的加法表。也就是說(shuō)，如果三個(gè)位都是0，那么和就是0，就記下0以及進(jìn)位0。如果三個(gè)位中有一個(gè)是1，那么和就是1，就記下1及進(jìn)位0。如果三個(gè)位中有兩個(gè)是1，那么和就是2，也就是二進(jìn)制數(shù)10，就記下0以及進(jìn)位1。如果三個(gè)位全是1，那么和就是3，也就是二進(jìn)制數(shù)11，就記下1及進(jìn)位1。例如，用行波進(jìn)位加法將二進(jìn)制數(shù)101和111相加的步驟如下所示。很多計(jì)算機(jī)用32位數(shù)字來(lái)表示整數(shù)。所以加法器電路可由32個(gè)一位加法器組合而成，如圖1-8所示。該電路通常稱為行波進(jìn)位加法器，因?yàn)檫M(jìn)位是從右向左一次一位行進(jìn)的。要注意，最右側(cè)（最低位）一位加法器的進(jìn)位總是0。位序列x31x30…x0表示一個(gè)加數(shù)，而y31y30…y0則表示另一個(gè)加數(shù)。和就是dz31z30…z0，也就是說(shuō)，和的第一位是最左側(cè)一位加法器的進(jìn)位輸出，而接下來(lái)的位就是從左往右各加法器的和值位。如圖1-8所示的電路是由位數(shù)據(jù)模型以及門(mén)的原始運(yùn)算形成的算法。不過(guò)這不是一種特別好的算法，因?yàn)橐遣挥?jì)算完最右側(cè)那一位，就不能計(jì)算z1或右起第二位的進(jìn)位輸出。不計(jì)算完右起第二位，就不能計(jì)算z2或右起第三位的進(jìn)位輸出，諸如此類。因此，該電路花費(fèi)的時(shí)間就是加數(shù)的位長(zhǎng)（在本例中是32）乘上每個(gè)一位加法器執(zhí)行運(yùn)算所需的時(shí)間。圖1-8行波進(jìn)位加法器：dz31z30…z0=x31x30…x0+y31y30…y0有人可能會(huì)認(rèn)為，進(jìn)位在每個(gè)一位加法器間“行進(jìn)”的需求，是加法定義中固有的。要是這些讀者知道計(jì)算機(jī)還有快得多的加法計(jì)算方式，肯定會(huì)大吃一驚的。我們將在第13章討論電路的設(shè)計(jì)時(shí)，介紹一種改進(jìn)過(guò)的加法算法。1.3.4習(xí)題1.解釋數(shù)據(jù)模型靜態(tài)方面和動(dòng)態(tài)方面的差異。2.描述自己最喜歡的視頻游戲的數(shù)據(jù)模型。區(qū)分其模型的靜態(tài)方面和動(dòng)態(tài)方面。提示：靜態(tài)部分不僅是指計(jì)分牌上不會(huì)移動(dòng)的部分。例如，在《吃豆人》游戲里，靜態(tài)部分不僅包括地圖，還包括“強(qiáng)化藥丸”和“怪物”等。3.描述自己最喜歡的文本編輯器的數(shù)據(jù)模型。4.描述電子表格程序的數(shù)據(jù)模型。1.4C語(yǔ)言數(shù)據(jù)模型在本節(jié)中，我們將重點(diǎn)介紹C語(yǔ)言所使用數(shù)據(jù)模型的重要部分。以圖1-9所示的C語(yǔ)言程序?yàn)槔摮绦蚴褂米兞縩um來(lái)計(jì)算其輸入中所含的字符數(shù)。#include<stdio.h>

main()

{

intnum;

num=0;

while(getchar()!=EOF)

++num;/*add1tonum*/

printf("%d\n",num);

}

圖1-9計(jì)算輸出所含字符數(shù)的C語(yǔ)言程序程序的第一行告訴C語(yǔ)言預(yù)處理器，將標(biāo)準(zhǔn)輸入/輸出文件stdio.h包含為源的一部分。該文件含有g(shù)etchar及printf函數(shù)的定義，以及表示文件結(jié)束的符號(hào)常量EOF。C語(yǔ)言程序本身也包含一系列的定義，既可以是函數(shù)的定義，也可以是數(shù)據(jù)的定義，其中必須要有main函數(shù)的定義。圖1-9所示程序的函數(shù)體中，第一條語(yǔ)句聲明了int類型的變量num（在C語(yǔ)言程序中，所有變量在使用前都必須先聲明），下一條語(yǔ)句將num初始化為0，接下來(lái)的while語(yǔ)句則使用庫(kù)函數(shù)getchar一次讀入一個(gè)輸入字符，并在每次字符讀入后遞增num變量，直到?jīng)]有輸入字符可供讀入為止。輸入中的特殊值EOF會(huì)提示文件已達(dá)末尾。printf語(yǔ)句則會(huì)將num的值以十進(jìn)制整數(shù)之后加上換行符的形式打印出來(lái)。1.4.1C語(yǔ)言類型系統(tǒng)首先介紹C語(yǔ)言數(shù)據(jù)模型的靜態(tài)部分——類型系統(tǒng)，它描述了數(shù)據(jù)可能擁有的值。隨后要討論C語(yǔ)言數(shù)據(jù)模型的動(dòng)態(tài)部分，也就是可以對(duì)數(shù)據(jù)進(jìn)行的操作。在C語(yǔ)言中，有著類型構(gòu)成的無(wú)限集合，其中的任意元素都可以成為與某個(gè)特定變量相關(guān)聯(lián)的類型。這些類型以及構(gòu)成類型的規(guī)則就形成了C語(yǔ)言的類型系統(tǒng)。類型系統(tǒng)包含整數(shù)這樣的基本類型以及一些類型構(gòu)成規(guī)則（type-formationrule），利用這些規(guī)則，我們可以用已知的類型逐步構(gòu)建更為復(fù)雜的類型。C語(yǔ)言的基本類型包括：1.字符（char、signedchar、unsignedchar）；2.整數(shù)（int、shortint、longint、unsigned）；3.浮點(diǎn)數(shù)（float、double、longdouble）；4.枚舉（enum）。整數(shù)和浮點(diǎn)數(shù)稱為算術(shù)類型。類型構(gòu)成規(guī)則假設(shè)我們已經(jīng)有了一些類型，可以是基本類型或使用這些規(guī)則構(gòu)建好的其他類型。以下是C語(yǔ)言中的一些類型構(gòu)成規(guī)則。1.數(shù)組類型?？梢杂靡韵侣暶鳂?gòu)建一個(gè)元素類型為T(mén)的數(shù)組：TA[n]該語(yǔ)句聲明了包含n個(gè)元素的數(shù)組A，其中每個(gè)元素都是T類型的。在C語(yǔ)言中，數(shù)組下標(biāo)是從0開(kāi)始的，所以數(shù)組的第一個(gè)元素是A[0]，而最后一個(gè)元素是A[n-1]。數(shù)組可由字符、算術(shù)類型、指針、結(jié)構(gòu)體、共用體或其他數(shù)組構(gòu)成。2.結(jié)構(gòu)體類型。在C語(yǔ)言中，結(jié)構(gòu)體是由稱為成員或字段的變量構(gòu)成的分組。在結(jié)構(gòu)體中，不同的成員可以具有不同的類型，但每個(gè)成員都必須具有某一個(gè)類型的元素。如果T1、T2、…、Tn是類型，而M1、M2、…、Mn是成員名稱，那么如下聲明structS{

T1M1;

T2M2;

…

TnMn;

}就定義了標(biāo)記（即其類型的名稱）為S而且具有n個(gè)成員的結(jié)構(gòu)體。對(duì)i=1、2、…、n來(lái)說(shuō)，第i個(gè)成員名稱為Mi，且其值為T(mén)i類型。示例1.1就展示了一個(gè)結(jié)構(gòu)體。該結(jié)構(gòu)體的標(biāo)記是CELL，并含有兩個(gè)成員。第一個(gè)成員的名稱是element，類型為整數(shù)。第二個(gè)成員名稱為next，它的類型是指向某個(gè)同類型結(jié)構(gòu)體的指針。結(jié)構(gòu)體標(biāo)記S是可選的，不過(guò)它可以在隨后的聲明中為表示類型提供方便的簡(jiǎn)寫(xiě)。例如，聲明structSmyRecord;定義了變量myRecord是一個(gè)類型為S的結(jié)構(gòu)體。3.共用體類型。共用體類型允許一個(gè)變量在程序執(zhí)行的不同時(shí)期具有不同的類型。聲明union{

T1M1;

T2M2;

…

TnMn;

}x;定義了變量x，可以存放類型為T(mén)1、T2、…、Tn中任意一種的值。成員名稱M1、M2、…、Mn用來(lái)指示x的值現(xiàn)在應(yīng)該是哪種類型。也就是說(shuō)，x.Mi就表明x的值是類型為T(mén)i的值。4.指針類型。C語(yǔ)言的獨(dú)特之處在于對(duì)指針的依賴。指針類型的變量包含某個(gè)存儲(chǔ)區(qū)域的地址。可以通過(guò)指針，間接地訪問(wèn)另一個(gè)變量。聲明T*p;定義了變量p是指向某個(gè)T類型變量的指針。用p來(lái)表示指向T的類型指針的框，框p的值就是個(gè)指針。我們往往將p的值表示成一個(gè)箭頭，而不是將其表示成T類型的對(duì)象本身，如圖1-10所示。真正出現(xiàn)在p框中的是T類型對(duì)象在計(jì)算機(jī)中存儲(chǔ)的地址（或位置）。圖1-10變量p是指向T的類型指針考慮如下聲明intx,*p;

在C語(yǔ)言中，一元運(yùn)算符&是用來(lái)獲取對(duì)象地址的，所以聲明p=&x;

將x的地址賦值給p，也就是說(shuō)，這讓p指向x。用在p前面的一元運(yùn)算符*會(huì)獲取p指向的框的值，所以聲明y=*p;

會(huì)將框p指向的內(nèi)容賦值給y。如果y是int類型的變量，那么p=&x;

y=*p;

就等價(jià)于賦值語(yǔ)句y=x;

示例1.4C語(yǔ)言的typedef結(jié)構(gòu)可用來(lái)創(chuàng)建類型名稱的同義字?？匆豢磮D1-11中的4個(gè)typedef聲明。依照對(duì)C語(yǔ)言中數(shù)據(jù)的傳統(tǒng)看法，類型type1是有10個(gè)槽（slot）的數(shù)組，每個(gè)槽中都存放著一個(gè)整數(shù)，如圖1-12a所示。同樣，類型type2的對(duì)象是指向這類數(shù)組的指針，如圖1-12b所示。而類型type3的結(jié)構(gòu)體則被表現(xiàn)為圖1-12c中所示的形式，每個(gè)字段都有一個(gè)槽與其對(duì)應(yīng)。請(qǐng)注意，字段名稱（例如field1）實(shí)際上并未與字段的值一起出現(xiàn)。最后，數(shù)組類型type4的對(duì)象將會(huì)有5個(gè)槽，每個(gè)槽都存放著類型type3的對(duì)象，即如圖1-12d所示的結(jié)構(gòu)體。typedefintDistance;

typedefinttype1[10];

typedeftype1*type2;

typedefstruct{

intfield1;

type2field2;

}type3;

typedeftype3type4[5];

圖1-11一些C語(yǔ)言typedef聲明圖1-12圖1-11中類型聲明的形象化表示類型、名字、變量和標(biāo)識(shí)符與數(shù)據(jù)對(duì)象相關(guān)的一些術(shù)語(yǔ)有不同的含義卻又容易混淆。首先，類型描述了數(shù)據(jù)對(duì)象的“形狀”。在C語(yǔ)言中，可以使用typedef結(jié)構(gòu)為已有的類型定義一個(gè)新名字T。typedef<類型描述符>T這里的類型描述符是個(gè)表達(dá)式，告訴我們T類型的對(duì)象是什么樣子。類型為T(mén)的typedef聲明實(shí)際上并沒(méi)有創(chuàng)建T類型的對(duì)象。要?jiǎng)?chuàng)建T類型的對(duì)象，需要使用如下形式的聲明Tx;這里的x是個(gè)標(biāo)識(shí)符，或者說(shuō)是“變量名”。x有可能是靜態(tài)的（不是任何函數(shù)的局部變量），在這種情況下，表示x的框在程序開(kāi)始時(shí)就創(chuàng)建了。如果x不是靜態(tài)的，那么它應(yīng)該是某個(gè)函數(shù)F的局部變量。在調(diào)用F時(shí)，就會(huì)創(chuàng)建一個(gè)名為“與本次對(duì)F的調(diào)用相關(guān)聯(lián)的x”的框。更準(zhǔn)確地說(shuō)，該框的名稱還是x，不過(guò)只在執(zhí)行本次對(duì)F的調(diào)用時(shí)，才使用標(biāo)識(shí)符x來(lái)表示該框。正如文中提到的，因?yàn)镕可能是遞歸函數(shù)，所以可能存在許多名稱涉及標(biāo)識(shí)符x的框。甚至可能會(huì)有其他函數(shù)使用標(biāo)識(shí)符x命名自己的某個(gè)變量。此外，名字比標(biāo)識(shí)符更具一般性，因?yàn)橛泻芏喾N表達(dá)式可以用來(lái)為框命名。例如，我們提到過(guò)*p可以是指針p指向的某個(gè)對(duì)象的名字，而該對(duì)象的其他名字也可以是復(fù)雜的表達(dá)式，比如(*p).f[2]或p->f[2]。這兩個(gè)復(fù)雜表達(dá)式是等價(jià)的，都表示指針p指向的結(jié)構(gòu)體中f字段數(shù)組的第二個(gè)元素。1.4.2函數(shù)函數(shù)也具有與之關(guān)聯(lián)的類型，即使我們沒(méi)有像處理程序變量那樣，將框或“值”與函數(shù)相關(guān)聯(lián)。對(duì)任意的一列類型T1、T2、…、Tn，我們可以定義一個(gè)函數(shù)，具有n個(gè)類型依次為這些類型的參數(shù)。這一列類型后面帶上函數(shù)返回的值（返回值）的類型，就是這個(gè)函數(shù)的“類型”。如果函數(shù)沒(méi)有返回值，那么該函數(shù)就是void類型的。一般情況下，可以應(yīng)用類型構(gòu)成規(guī)則任意地構(gòu)建類型，不過(guò)也存在一些限制。比如，不能構(gòu)建“函數(shù)數(shù)組”，不過(guò)構(gòu)建由指向函數(shù)的指針構(gòu)成的數(shù)組是可以的。在C語(yǔ)言中構(gòu)建類型的完整規(guī)則可以在ANSI標(biāo)準(zhǔn)中找到。1.4.3C語(yǔ)言數(shù)據(jù)模型中的操作C語(yǔ)言數(shù)據(jù)模型中的數(shù)據(jù)操作可分為以下三類。1.創(chuàng)建或銷毀數(shù)據(jù)對(duì)象的操作。2.訪問(wèn)或修改數(shù)據(jù)對(duì)象某些部分的操作。3.將若干數(shù)據(jù)對(duì)象的值組合起來(lái)，為某個(gè)數(shù)據(jù)對(duì)象生成新值的操作。1.4.4數(shù)據(jù)對(duì)象的創(chuàng)建和銷毀對(duì)于數(shù)據(jù)的創(chuàng)建，C語(yǔ)言提供了幾種簡(jiǎn)陋的機(jī)制。在函數(shù)被調(diào)用時(shí)，會(huì)創(chuàng)建對(duì)應(yīng)每個(gè)局部參數(shù)的框，這些框都用來(lái)存放參數(shù)的值。另一種數(shù)據(jù)創(chuàng)建機(jī)制是使用程序庫(kù)例程malloc(n)，該例程可以返回一個(gè)指針，指向n個(gè)未使用的連續(xù)字符位置，這些存儲(chǔ)空間可被malloc的調(diào)用者用來(lái)存儲(chǔ)數(shù)據(jù)。然后就可以在這一存儲(chǔ)區(qū)域中創(chuàng)建數(shù)據(jù)對(duì)象。C語(yǔ)言有著類似的方法來(lái)銷毀數(shù)據(jù)對(duì)象。當(dāng)函數(shù)返回時(shí)，該函數(shù)調(diào)用的局部參數(shù)將不復(fù)存在。例程free會(huì)釋放malloc創(chuàng)建的存儲(chǔ)空間。特別要說(shuō)的是，調(diào)用free(p)的效果是釋放p指向的存儲(chǔ)區(qū)域。若使用free去銷毀不是通過(guò)調(diào)用malloc創(chuàng)建的對(duì)象，會(huì)造成災(zāi)難性后果。1.4.5數(shù)據(jù)的訪問(wèn)和修改C語(yǔ)言具有訪問(wèn)對(duì)象某些部分的機(jī)制?？梢允褂胊[i]訪問(wèn)數(shù)組a的第i個(gè)元素，用x.m訪問(wèn)結(jié)構(gòu)x的成員m，還可以用*p訪問(wèn)指針p指向的對(duì)象。在C語(yǔ)言中，修改（或者說(shuō)是寫(xiě)）值主要是由賦值運(yùn)算符完成的，這讓我們可以改變對(duì)象的值。示例1.5如果變量a的類型是示例1.4中所定義的type4，那么(*a[0].field2)[3]=99;

就把值99賦給了數(shù)組a第一個(gè)元素所代表的結(jié)構(gòu)體中field2指向的數(shù)組的第4個(gè)元素。1.4.6數(shù)據(jù)的組合C語(yǔ)言有著豐富的運(yùn)算符，可用來(lái)對(duì)值進(jìn)行操作和組合。主要運(yùn)算符包括如下這些。1.算術(shù)運(yùn)算符。C語(yǔ)言提供了以下幾種算術(shù)運(yùn)算符。(a)用于整數(shù)和浮點(diǎn)數(shù)的常規(guī)二元算術(shù)運(yùn)算符+、-、*、/。整數(shù)除法會(huì)取整（4/3得1）。(b)一元的+和-運(yùn)算符。(c)取模運(yùn)算符i%j的結(jié)果是i除以j的余數(shù)。(d)遞增和遞減運(yùn)算符++和--，適用于單個(gè)整數(shù)變量反復(fù)從自身增加或減去1。這些運(yùn)算符可以出現(xiàn)在它們的操作數(shù)之前，也可以出現(xiàn)在它們的操作數(shù)之后，取決于我們是想在改變變量的值之前還是之后計(jì)算該表達(dá)式的值。2.邏輯運(yùn)算符。C語(yǔ)言中沒(méi)有布爾類型，它使用“0”來(lái)表示邏輯值“假”，使用“非0”表示邏輯值“真”。5C語(yǔ)言使用以下幾種邏輯運(yùn)算符。5我們將反復(fù)使用TRUE和FALSE作為已定義的常量1和0，來(lái)表示布爾值，詳見(jiàn)1.6節(jié)。(a)&&表示AND運(yùn)算。例如，表達(dá)式x&&y在兩個(gè)操作數(shù)都非0的情況下會(huì)返回1，否則返回0。不過(guò)，如果x的值為0，就不考慮y的值了。(b)||表示OR運(yùn)算。表達(dá)式x||y在x或y非0的情況下會(huì)返回1，否則返回0。不過(guò)，如果x的值非0，就不考慮y的值了。(c)一元的否定運(yùn)算符!x在x非0時(shí)返回0，在x=0時(shí)返回1。(d)條件運(yùn)算符是三元（三參數(shù)）運(yùn)算符，用一個(gè)問(wèn)號(hào)和一個(gè)冒號(hào)表示。表達(dá)式x?y:z在x為真（即x為非0）的情況下會(huì)返回y的值，在x為假（即x=0）的情況下會(huì)返回z的值。3.比較運(yùn)算符。對(duì)整數(shù)或浮點(diǎn)數(shù)使用6種關(guān)系比較運(yùn)算符之一（==、!=、<、>、<=、和>=），如果關(guān)系不成立，結(jié)果就為0，否則結(jié)果為1。4.位運(yùn)算運(yùn)算符。C語(yǔ)言提供了一些實(shí)用的位邏輯運(yùn)算符，將整數(shù)當(dāng)作與它們的二進(jìn)制形式相同的位字符串。這些運(yùn)算符包括，用于按位與的&，用于按位或的|，用于按位異或的^，用于左移位的<<，用于右移位的>>，以及用于左移位的波浪字符（~）。5.賦值運(yùn)算符。C語(yǔ)言使用=作為賦值運(yùn)算符。除此之外，還允許將x=x+y;這樣的表達(dá)式寫(xiě)為x+=y;這樣的簡(jiǎn)短形式。類似的格式也可以用于其他二元算術(shù)運(yùn)算符。6.強(qiáng)制轉(zhuǎn)換運(yùn)算符。強(qiáng)制轉(zhuǎn)換是指將某個(gè)類型的值轉(zhuǎn)換成另一個(gè)類型的等價(jià)值的過(guò)程。例如，如果x是浮點(diǎn)數(shù)，而i是整數(shù)，那么x=i會(huì)導(dǎo)致i的整數(shù)值被轉(zhuǎn)換成值相等的浮點(diǎn)數(shù)。在這里，強(qiáng)制轉(zhuǎn)換運(yùn)算符并未顯式出現(xiàn)，不過(guò)C語(yǔ)言編譯器會(huì)推斷從整數(shù)到浮點(diǎn)數(shù)的轉(zhuǎn)換是必要的，并自動(dòng)執(zhí)行所需的轉(zhuǎn)換步驟。1.4.7習(xí)題1.解釋C語(yǔ)言程序的標(biāo)識(shí)符與名字（用于“框”或數(shù)據(jù)對(duì)象）之間的區(qū)別。2.舉例說(shuō)出有多個(gè)名字的C語(yǔ)言數(shù)據(jù)對(duì)象。3.如果熟悉C語(yǔ)言之外的編程語(yǔ)言，描述一下它的類型系統(tǒng)和操作。1.5算法和程序設(shè)計(jì)對(duì)數(shù)據(jù)模型、它們的屬性及其適當(dāng)用途的研究是計(jì)算機(jī)科學(xué)的一大核心，而與其同等重要的一大核心便是對(duì)算法以及與其相關(guān)的數(shù)據(jù)結(jié)構(gòu)的研究。我們需要了解執(zhí)行常見(jiàn)任務(wù)的最佳方法，而且需要學(xué)習(xí)設(shè)計(jì)優(yōu)秀算法的主要技術(shù)。此外，我們還需要了解如何將數(shù)據(jù)結(jié)構(gòu)和算法的使用融入創(chuàng)建實(shí)用程序的過(guò)程中。數(shù)據(jù)模型、算法、數(shù)據(jù)結(jié)構(gòu)，以及它們?cè)诔绦蛑械膶?shí)現(xiàn)，這些主題相互依存，而且每個(gè)主題都會(huì)在本書(shū)中出現(xiàn)多次。在本節(jié)中，我們將粗略地提到一些與程序的設(shè)計(jì)和實(shí)現(xiàn)有關(guān)的知識(shí)。1.5.1軟件的創(chuàng)建在程序設(shè)計(jì)課上，當(dāng)我們拿到編程問(wèn)題時(shí)，可能需要設(shè)計(jì)解決問(wèn)題的算法、用某種語(yǔ)言實(shí)現(xiàn)該算法、編譯程序并用一些示例數(shù)據(jù)運(yùn)行它，然后提交該程序給老師打分。而在商業(yè)背景中，編程環(huán)境則完全不同。算法通常只不過(guò)是完整程序的一小部分，至少對(duì)那些簡(jiǎn)單平常到信手可拾的算法來(lái)說(shuō)是這樣。而程序通常是涉及硬件和軟件的更大系統(tǒng)的組件。程序及其所嵌入的完整系統(tǒng)，都是由程序員和工程師團(tuán)隊(duì)開(kāi)發(fā)的，這樣的團(tuán)隊(duì)可能有數(shù)百人的規(guī)模。軟件系統(tǒng)的開(kāi)發(fā)過(guò)程通常要跨越多個(gè)階段。雖然這些階段表面上可能和解決課堂編程任務(wù)所涉及的步驟有相似之處，但是構(gòu)建軟件系統(tǒng)來(lái)解決特定問(wèn)題的功夫多數(shù)并沒(méi)有花在編程上。下面要講的是一種理想化的場(chǎng)景。問(wèn)題的定義和需求說(shuō)明。在創(chuàng)建軟件系統(tǒng)的過(guò)程中，最難也是最重要的部分是定義真正的問(wèn)題所在并指明解決問(wèn)題所需的條件。通常，問(wèn)題的定義始于對(duì)用戶需求的分析，不過(guò)這些需求通常是不準(zhǔn)確的，而且很難寫(xiě)下來(lái)。系統(tǒng)架構(gòu)師可能要咨詢系統(tǒng)未來(lái)的用戶，并對(duì)需求說(shuō)明進(jìn)行迭代，直到詳解者（specifier，擬定需求說(shuō)明的人）和用戶都對(duì)定義和解決手頭問(wèn)題的需求說(shuō)明感到滿意為止。在需求說(shuō)明階段，為最終系統(tǒng)建立簡(jiǎn)單的原型或模型是有好處的，因?yàn)檫@樣可以深入了解系統(tǒng)的行為和可能的用途。數(shù)據(jù)建模也是問(wèn)題定義階段的一個(gè)重要工具。設(shè)計(jì)。一旦完成需求說(shuō)明，系統(tǒng)的上層設(shè)計(jì)就已成形，而且主要組成部分也確定了。開(kāi)發(fā)人員會(huì)擬定一份概述上層設(shè)計(jì)已完成的文檔，文檔中還可能包含系統(tǒng)的性能要求。該階段還可能引入有關(guān)某些主要組件的更詳細(xì)的需求說(shuō)明。高性價(jià)比的設(shè)計(jì)往往需要重用或修改以前構(gòu)造的組件，諸如面向?qū)ο蠹夹g(shù)這樣的多種軟件方法論推動(dòng)了組件的重用。實(shí)現(xiàn)。一旦敲定設(shè)計(jì)，就可以開(kāi)始實(shí)現(xiàn)組件了。本書(shū)中討論的很多算法都能在實(shí)現(xiàn)新組件的過(guò)程中派上用場(chǎng)。一旦完成組件的實(shí)現(xiàn)工作，就要對(duì)其進(jìn)行一系列的測(cè)試，以確保它能像需求說(shuō)明所說(shuō)的那樣工作。集成和系統(tǒng)測(cè)試。當(dāng)組件得到實(shí)現(xiàn)而且已經(jīng)單獨(dú)測(cè)試過(guò)，就應(yīng)該將整個(gè)系統(tǒng)組合起來(lái)并進(jìn)行測(cè)試。安裝和現(xiàn)場(chǎng)測(cè)試。一旦開(kāi)發(fā)人員覺(jué)得系統(tǒng)已經(jīng)能以令客戶滿意的狀態(tài)運(yùn)轉(zhuǎn)，就可以將系統(tǒng)安裝到客戶的辦公地點(diǎn)，并進(jìn)行最終的現(xiàn)場(chǎng)測(cè)試。維護(hù)。至此，我們可能會(huì)認(rèn)為已經(jīng)完成了大部分的工作。然而，還需要有維護(hù)工作。在很多情況下，維護(hù)可能要占據(jù)超過(guò)一半的系統(tǒng)開(kāi)發(fā)成本。維護(hù)可能涉及修改組件來(lái)消除不可預(yù)見(jiàn)的副作用、修正或提高系統(tǒng)性能，或增加新功能等目的。因?yàn)榫S護(hù)是軟件系統(tǒng)設(shè)計(jì)中很重要的部分，所以編寫(xiě)的程序務(wù)要正確、耐用、高效、可修改，并且能從一臺(tái)計(jì)算機(jī)移植到另一臺(tái)計(jì)算機(jī)。盡早地發(fā)現(xiàn)錯(cuò)誤很重要，最好是在問(wèn)題定義階段就能發(fā)現(xiàn)錯(cuò)誤。越到后面的階段，修復(fù)設(shè)計(jì)錯(cuò)誤或編程錯(cuò)誤的成本越高，對(duì)需求和設(shè)計(jì)的獨(dú)立審查有利于減少后續(xù)的錯(cuò)誤。1.5.2編程風(fēng)格編寫(xiě)他人能夠輕松閱讀和修改的程序，便能夠顯著減輕維護(hù)負(fù)擔(dān)。好的編程風(fēng)格都是練習(xí)的結(jié)果，建議大家一開(kāi)始就試著編寫(xiě)方便他人理解的程序。沒(méi)有什么神奇公式能確保程序的可讀性，不過(guò)還是有一些實(shí)用經(jīng)驗(yàn)可介紹給大家。1.將程序分成相關(guān)的模塊。2.為程序排版，使其結(jié)構(gòu)清晰。3.編寫(xiě)易于理解的注釋來(lái)解釋程序。清晰準(zhǔn)確地描述底層數(shù)據(jù)模型、用來(lái)表示數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)和每個(gè)例程所執(zhí)行的操作。在描述例程時(shí)，要陳述對(duì)其輸入作出的假設(shè)，并講清輸出和輸入有什么關(guān)系。4.對(duì)例程和變量使用有意義的名稱。5.盡可能避免使用明確的常數(shù)。例如，不要用數(shù)字7表示小矮人的個(gè)數(shù)，而是要使用諸如NumberOfDwarfs這樣定義的常量，這樣一來(lái)，如果決定再加上一個(gè)小矮人，就可以很方便地將該常量的值改為8。6.避免使用“全局變量”，即不要為整個(gè)程序定義變量，除非程序中的大多數(shù)例程都要使用該變量所表示的數(shù)據(jù)。另一個(gè)編程好習(xí)慣就是擁有成套測(cè)試輸入，可以在編程時(shí)對(duì)每行代碼進(jìn)行測(cè)試。每當(dāng)為程序增加了新功能，就可以運(yùn)行這套測(cè)試，以確保新程序在處理這些起作用的輸入時(shí)能和老程序行動(dòng)一致。1.6