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

成書過程

修訂情況

該教材由徐士良、葛兵編著，主要修訂了第一版的前3章。

出版工作

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

出版社工作人員

責任編輯	責任校對	責任印製
焦虹、薛陽	時翠蘭	孟凡玉

內容簡介

該教材中所有算法均採用C++描述。全書共6章，介紹了計算機軟體設計的基礎知識、方法與實用技術。主要內容包括：算法，基本數據結構及其運算，查找與排序技術，資源管理技術，資料庫技術，套用軟體設計與開發技術。在每章後都配有一定數量的習題。

教材目錄

第1章算法

1.1算法的基本概念1

1.1.1算法的基本特徵1

1.1.2算法的基本要素2

1.2算法設計基本方法3

1.3算法的複雜度分析9

1.3.1算法的時間複雜度9

1.3.2算法的空間複雜度11

習題12

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

2.1數據結構的基本概念13

2.1.1兩個例子13

2.1.2什麼是數據結構16

2.1.3數據結構的圖形表示19

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

2.2.1線性表及其運算21

2.2.2棧及其套用30

2.2.3佇列及其套用41

2.3線性鍊表及其運算52

2.3.1線性鍊表的基本概念52

2.3.2線性鍊表的基本運算66

2.3.3循環鍊表71

2.3.4多項式的表示與運算75

2.4數組83

2.4.1數組的順序存儲結構83

2.4.2規則矩陣的壓縮84

2.4.3一般稀疏矩陣的表示87

2.5樹與二叉樹113

2.5.1樹的基本概念113

2.5.2二叉樹及其基本性質116

2.5.3二叉樹的遍歷119

2.5.4二叉樹的存儲結構120

2.5.5穿線二叉樹126

2.5.6表達式的線性化138

2.6圖140

2.6.1圖的基本概念140

2.6.2圖的存儲結構141

2.6.3圖的遍歷145

2.6.4圖鄰接表類146

習題152

第3章查找與排序技術

3.1基本的查找技術155

3.1.1順序查找155

3.1.2有序表的對分查找155

3.1.3分塊查找160

3.2哈希表技術161

3.2.1哈希表的基本概念161

3.2.2幾種常用的哈希表164

3.3基本的排序技術182

3.3.1冒泡排序與快速排序183

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

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

3.3.4其他排序方法簡介196

3.4二叉排序樹及其查找200

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

3.4.2二叉排序樹的插入202

3.4.3二叉排序樹的刪除204

3.4.4二叉排序樹查找206

3.5多層索引樹及其查找208

3.5.1B－樹209

3.5.2B+樹219

3.6拓撲分類229

習題232

第4章資源管理技術

4.1作業系統的概念234

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

4.1.2作業系統的發展過程235

4.1.3作業系統的分類238

4.2多道程式設計241

4.2.1並發程式設計241

4.2.2進程244

4.2.3進程之間的通信249

4.2.4多道程式的組織254

4.3存儲空間的組織255

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

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

習題266

第5章資料庫技術

5.1資料庫基本概念267

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

5.1.2數據描述272

5.1.3數據模型275

5.2關係代數278

5.3資料庫設計285

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

5.3.2資料庫設計的過程286

5.3.3數據字典293

5.4關係資料庫語言SQL294

5.4.1SQL語言概述294

5.4.2資料庫定義298

5.4.3數據查詢303

5.4.4數據修改312

5.4.5數據控制315

5.4.6嵌入式SQL318

習題323

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

6.1軟體工程概述325

6.1.1軟體工程的概念325

6.1.2軟體生命周期326

6.1.3軟體支援環境328

6.2軟體詳細設計的表達329

6.2.1程式流程圖330

6.2.2NS圖331

6.2.3問題分析圖PAD332

6.2.4判定表332

6.2.5過程設計語言333

6.3結構化分析與設計方法334

6.3.1套用軟體開發的原則和方法334

6.3.2結構化分析方法336

6.3.3結構化設計方法340

6.4測試與調試基本技術346

6.4.1測試346

6.4.2調試353

6.5軟體開發新技術355

6.5.1原型方法355

6.5.2瀑布模型356

6.5.3面向對象技術357

習題358

參考文獻359

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

教學資源

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

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

教材特色

該教材主要是針對非計算機專業的學生對於計算機軟體技術的需要，將有關軟體基礎知識以及套用技術介紹給讀者。其特點如下：

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

作者簡介

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