計算機軟體技術基礎（第四版）

成書過程

修訂情況

該次修訂保持了前三版的特點，在第三版的基礎上進行了如下幾方面的調整與修改。

所有算法程式均採用C++語言進行描述。由於C++語言既可用於面向過程的程式設計，又支持面向對象的程式設計，因此，作者在對算法進行描述時，儘量採用最合適的程式設計方法。例如，對於同一批數據進行同類操作的單個算法採用面向過程的方法；對於基本的數據結構（如順序存儲與鏈式存儲的線性表、棧、佇列等）採用面向對象的方法，將數據與運算封裝成類。
在第2章的2.7節中增加了最短距離問題的內容。
在第3章中增加了字元串匹配的內容。

出版工作

2014年9月1日，該教材由清華大學出版社出版。

出版社工作人員

責任編輯	封面設計	責任校對	責任印製
焦虹	傅瑞學	時翠蘭	劉海龍

內容簡介

該教材針對高等學校的大學生、研究生以及科技工作者與研究人員學習計算機軟體套用技術的需要，介紹了計算機軟體設計的基礎知識、方法與實用技術。全書共7章，主要內容包括集合與算法的基本概念、基本數據結構及其運算、查找與排序技術、資源管理技術、資料庫設計技術、編譯技術概述、套用軟體設計與開發技術。每章都配有一定數量的習題。

教材目錄

第1章預備知識

1.1集合1

1.1.1集合及其基本運算1

1.1.2自然數集與數學歸納法3

1.1.3笛卡兒積5

1.1.4二元關係5

1.2算法6

1.2.1算法的基本概念6

1.2.2算法設計基本方法8

1.2.3算法的複雜度分析13

習題15

第2章基本數據結構及其運算

2.1數據結構的基本概念17

2.1.1什麼是數據結構17

2.1.2數據結構的圖形表示20

2.2線性表及其順序存儲結構22

2.2.1線性表及其運算22

2.2.2棧及其套用31

2.2.3佇列及其套用41

2.3線性鍊表52

2.3.1線性鍊表的基本概念52

2.3.2線性鍊表的插入與刪除56

2.3.3帶鏈的棧與佇列61

2.3.4循環鍊表68

2.3.5多項式的表示與運算71

2.4線性表的索引存儲結構78

2.4.1索引存儲的概念78

2.4.2“順序·索引·順序”存儲方式80

2.4.3“順序·索引·連結”存儲方式81

2.4.4多重索引存儲結構82

2.5數組83

2.5.1數組的順序存儲結構83

2.5.2規則矩陣的壓縮83

2.5.3一般稀疏矩陣的表示86

2.6樹與二叉樹112

2.6.1樹的基本概念112

2.6.2二叉樹及其基本性質115

2.6.3二叉樹的遍歷118

2.6.4二叉樹的存儲結構119

2.6.5穿線二叉樹124

2.6.6表達式的線性化136

2.7圖138

2.7.1圖的基本概念138

2.7.2圖的存儲結構139

2.7.3圖的遍歷143

2.7.4最短距離問題144

2.7.5圖鄰接表類146

習題155

第3章查找與排序技術

3.1基本的查找技術158

3.1.1順序查找158

3.1.2有序表的對分查找158

3.1.3分塊查找163

3.2哈希表技術164

3.2.1哈希表的基本概念164

3.2.2幾種常用的哈希表167

3.3基本的排序技術185

3.3.1冒泡排序與快速排序185

3.3.2簡單插入排序與希爾排序190

3.3.3簡單選擇排序與堆排序192

3.3.4其他排序方法簡介195

3.4二叉排序樹及其查找199

3.4.1二叉排序樹的基本概念200

3.4.2二叉排序樹的插入201

3.4.3二叉排序樹的刪除202

3.4.4二叉排序樹查找204

3.5多層索引樹及其查找206

3.5.1B－樹207

3.5.2B+樹217

3.6拓撲分類227

3.7字元串匹配229

3.7.1字元串的基本概念229

3.7.2字元串匹配的KMP算法230

習題235

第4章資源管理技術

4.1作業系統的概念237

4.1.1作業系統的功能與任務237

4.1.2作業系統的發展過程238

4.1.3作業系統的分類241

4.2多道程式設計244

4.2.1並發程式設計244

4.2.2進程247

4.2.3進程之間的通信251

4.2.4多道程式的組織256

4.3存儲空間的組織257

4.3.1記憶體儲器的管理技術257

4.3.2外存儲器中檔案的組織結構261

習題268

第5章資料庫設計技術

5.1資料庫基本概念269

5.1.1資料庫技術與資料庫系統269

5.1.2數據描述274

5.1.3數據模型276

5.2關係代數280

5.3資料庫設計286

5.3.1資料庫設計的基本概念286

5.3.2資料庫設計的過程287

5.3.3數據字典293

習題295

第6章編譯技術概述

6.1編譯程式的工作過程及其基本組成297

6.1.1編譯程式的工作過程297

6.1.2編譯程式的基本組成298

6.2狀態矩陣法的編譯過程299

6.2.1狀態矩陣法的基本原理299

6.2.2狀態矩陣的壓縮300

6.3詞法分析302

6.3.1詞法分析的任務302

6.3.2讀字元程式303

6.3.3狀態矩陣法的詞法分析過程304

6.3.4算術常數的識別和翻譯307

6.4中間語言表示310

6.4.1波蘭表示310

6.4.2三元組表示312

6.5語法的分析與加工316

習題321

第7章套用軟體設計與開發技術

7.1軟體工程概述322

7.1.1軟體工程的概念322

7.1.2軟體生命周期322

7.1.3軟體支援環境325

7.2軟體詳細設計的表達326

7.2.1程式流程圖326

7.2.2NS圖327

7.2.3問題分析圖PAD329

7.2.4判定表329

7.2.5過程設計語言PDL330

7.3結構化分析與設計方法331

7.3.1套用軟體開發的原則和方法331

7.3.2結構化分析方法332

7.3.3結構化設計方法336

7.4測試與調試基本技術342

7.4.1測試342

7.4.2調試349

7.5軟體開發新技術351

7.5.1原型方法351

7.5.2瀑布模型352

7.5.3面向對象技術353

習題354

參考文獻355

（註：目錄排版順序為從左列至右列）

教學資源

該教材有配套教材——《計算機軟體技術基礎習題解答（第四版）》。

書名	書號	出版社	出版時間	作者
《計算機軟體技術基礎習題解答（第四版）》	9787302486077	清華大學出版社	2017.12.01	徐士良、葛兵

教材特色

該教材主要針對高等學校非計算機專業的學生學習計算機軟體技術的需要，介紹有關軟體基礎知識及套用技術。其特點如下：

系統性：該教材不是將計算機專業各門課程的內容簡單地拼裝在一起，而是針對學生對軟體套用技術的需要，將其有機結合；全書以數據結構與算法為基礎，以軟體技術為線索；
強調套用：該教材強調以套用為目的，書中內容圍繞解決軟體開發中所遇到的軟體技術問題來展開；在介紹系統軟體（如作業系統）時也適當介紹一些原理，但主要還是介紹實現系統軟體中的技術，以便讀者將這些技術用到套用軟體的開發中；
可讀性強：該教材通過實例引出基本概念。

作者簡介

徐士良，清華大學信息認知與智慧型系統研究所老師，已經退休。