計(jì)算機(jī)軟件技術(shù)基礎(chǔ)

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