計算機軟件技術基礎

第1 章 數(shù)據(jù)結構.............................................................................................................1
1.1 數(shù)據(jù)結構的基本概念.................................................................................................... 1
1.1.1 數(shù)據(jù)結構的研究內容及其重要性...................................................................... 1
1.1.2 數(shù)據(jù)結構的基本概念和術語............................................................................. 2
1.1.3 數(shù)據(jù)結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型.............................................................. 5
1.2 線性結構....................................................................................................................... 7
1.2.1 線性表............................................................................................................... 7
1.2.2 棧和隊列......................................................................................................... 22
1.2.3 數(shù)組和廣義表.................................................................................................. 29
1.2.4 串..................................................................................................................... 37
1.3 樹和二叉樹................................................................................................................. 39
1.3.1 樹形結構基本概念.......................................................................................... 39
1.3.2 二叉樹............................................................................................................. 42
1.3.3 二叉樹的遍歷.................................................................................................. 46
1.3.4 樹、森林與二叉樹的轉換............................................................................... 49
1.3.5 哈夫曼樹和哈夫曼編碼................................................................................... 50
1.3.6 二叉排序樹...................................................................................................... 53
1.4 圖................................................................................................................................ 54
1.4.1 圖的基本概念.................................................................................................. 54
1.4.2 有向圖和無向圖.............................................................................................. 54
1.4.3 子圖與路徑...................................................................................................... 56
1.4.4 連通圖和連通分量.......................................................................................... 56
1.4.5 圖的存儲結構.................................................................................................. 57
1.4.6 圖的遍歷......................................................................................................... 59
1.5 查找和排序................................................................................................................. 61
1.5.1 查找................................................................................................................. 61
1.5.2 排序................................................................................................................. 69
本章小結.............................................................................................................................. 79
習題..................................................................................................................................... 79
第2 章 計算機操作系統(tǒng)................................................................................................ 91
2.1 計算機操作系統(tǒng)簡介.................................................................................................. 91
2.1.1 操作系統(tǒng)概述.................................................................................................. 91
2.1.2 操作系統(tǒng)的發(fā)展及分類................................................................................... 92
2.1.3 操作系統(tǒng)的主要特征和功能........................................................................... 96
2 計算機軟件技術基礎
2.2 處理器管理................................................................................................................. 98
2.2.1 程序執(zhí)行的基本特征...................................................................................... 98
2.2.2 進程的定義及特征.......................................................................................... 99
2.2.3 進程的狀態(tài)和轉換.........................................................................................100
2.2.4 進程的描述.....................................................................................................103
2.2.5 處理器調度.....................................................................................................107
2.2.6 進程調度........................................................................................................110
2.2.7 并發(fā)進程........................................................................................................113
2.2.8 臨界區(qū)管理.....................................................................................................116
2.2.9 進程消息傳遞.................................................................................................124
2.2.10 死鎖..............................................................................................................127
2.2.11 作業(yè)調度.......................................................................................................128
2.2.12 線程..............................................................................................................130
2.3 存儲管理....................................................................................................................134
2.3.1 存儲管理概述.................................................................................................134
2.3.2 連續(xù)存儲管理.................................................................................................137
2.3.3 可變分區(qū)存儲管理.........................................................................................138
2.3.4 主存擴充技術.................................................................................................140
2.3.5 分頁式存儲管理.............................................................................................141
2.3.6 分段式存儲管理.............................................................................................144
2.3.7 段頁式存儲管理.............................................................................................145
2.3.8 虛擬存儲管理.................................................................................................146
2.4 設備管理....................................................................................................................149
2.4.1 設備管理概述.................................................................................................149
2.4.2 I/O 控制方式..................................................................................................152
2.4.3 設備的分配.....................................................................................................155
2.4.4 設備無關性和緩沖技術..................................................................................157
2.4.5 設備驅動程序.................................................................................................159
2.5 文件管理....................................................................................................................160
2.5.1 文件系統(tǒng)的基本概念.....................................................................................160