【正文】 k與 mid指向的記錄比較， 若 k==r[mid].key， 找成功， 若 kr[mid].key， 則 high=mid1； 若 kr[mid].key， 則 low=mid+1； 重復(fù)上述操作，直至 lowhigh時，查找失敗。 二、對分查找（折半查找、二分法查找） 查找 23和 79的過程如下圖： mid =[ (low+high) / 2] ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high=mid1 mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) high low=mid+1 mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid 查找方法比較 順序查找 折半查找 分塊查找 ASL 最大 最小 兩者之間 表結(jié)構(gòu) 有序表、無序表 有序表 分塊有序表 存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)線性鏈表 順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)線性鏈表 四、二叉排序樹查找 （ 1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值； 1．定義： 二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹： （ 3）它的左、右子樹也都分別是二叉排序樹。 （ 2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值； 3. 二叉排序樹的生成 對于任意的一組數(shù)據(jù)元素序列 { R1， R2， … ，Rn}，生成二叉排序樹的過程如下： 1）令 R1為二叉排序樹的根結(jié)點； 2）若 R2R1，令 R2為 R1的左子樹的根結(jié)點；否則，R2為 R1的右子樹的根結(jié)點； 3） R2， … ， Rn結(jié)點插入方法同上。 10 10 18 10 18 3 10 18 3 8 10 18 3 12 3 10 18 8 12 2 10 18 3 8 12 2 7 10 18 3 8 12 2 7 1 8 序列 {10， 18， 3， 8， 12， 2， 7， 1}構(gòu)成一棵二叉排序樹的過程 上述查找過程可見，在查找過程中，生成了一條查找路徑： 從根結(jié)點出發(fā)，沿 ? 動態(tài)查找，就是在查找失敗時進(jìn)行“插入”操作，將要查找的關(guān)鍵字插入到結(jié)構(gòu)中； ? 若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。 二叉排序樹在生成（插入）過程中，若其形態(tài)始終保持“ 勻稱 ” ，亦接近平衡二叉樹，則平均查找長度就小；反之，平均查找長度就長。 二叉排序樹的平均查找長度介于對分查找與線性查找之間。 20,8,6,17,54,32,3,80 20 8 54 6 17 32 80 3 54,32,20,8, 17,6,80,3 20 8 54 6 17 32 80 3 ASL=(1+2*2+3*4+4)/8= ASL=(1+2*2+3+4+5*2+6)/8= 哈希函數(shù)： 在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系，是可以根據(jù)關(guān)鍵字的值而直接計算出元素所在位置的函數(shù) , 可表示 H（ KEY） 。 哈希表： 哈希表是一種存儲結(jié)構(gòu)，是能用散列技術(shù)進(jìn)行查找的表， 也叫 散列存儲 。 通過哈希函數(shù)和解決沖突的辦法把鍵值存放在哈希表中。 采用哈希技術(shù)主要目標(biāo)是提高查找效率，要求縮短查表和填表的時間 . 哈希查找 ： 又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程 。 沖突 ： 兩個不同的關(guān)鍵字 K1和 K2計算出相同的存儲位置的現(xiàn)象稱為沖突， K1和 K2互為 同義詞 。 哈希函數(shù) /哈希表的基本概念 1） 直接定址法： H(K)=K 或 H(K)=A*K+B； (其中 A、 B為常數(shù) )； 取關(guān)鍵字或關(guān)鍵字的某個 線性函數(shù)值 為散列地址 。 例：某公司一險種投保費交納表 （ 20年 ） ， 將年份作關(guān)鍵字 ，哈希函數(shù)取關(guān)鍵字本身 ， 若查找第 3年應(yīng)交納的保費 ， 只要查找表的第 3項即可 。 地址 01 02 03 …… 20 年份 1 2 3 …… . 20 保費 …… . …… . …… . …… …… 哈希函數(shù)的構(gòu)造方法 2） 數(shù)字分析法 : 該法適用于較大的靜態(tài)數(shù)據(jù) ， 在已知所有關(guān)鍵字鍵值的情況下 ， 分析每一位的數(shù)字分布是否均勻 ， 刪除不均勻分配的數(shù)字位 ， 根據(jù)存儲空間的大小來確定所取地址的位數(shù) 。 542 42 2241 542 81 3678 542 22 8171 542 38 9671 542 54 1577 542 88 6376 542 19 3552 422 836 281 396 515 853 135 存儲空間從01000 3） 平方取中法 : 若一組關(guān)鍵字的值在每一位上對某些數(shù)字的重復(fù)頻度都很高 ， 就不宜采用數(shù)字分析法 ， 取關(guān)鍵字平方后的中間幾位為哈希函數(shù) 。 H(Key) = Key2 = an an1 … a2 a1 0100,1100,1200,1160,2060,2061,2163,2261,2262 設(shè)存儲空間 01000 平方后，取 4位構(gòu)成哈希地址如下： 010,210,440,345,243,247,678,112,116 4） 除留余數(shù)法 ： 取關(guān)鍵字被不大于散列表表長 m 的數(shù) p除后所得的余數(shù)為哈希函數(shù)。 即 H（ K） =K MOD p （ p?m） p一般選取小于等于表長的質(zhì)數(shù) 。 H（ K） = K MOD p + C （ p?m） C 的作用可以調(diào)節(jié)最終的地址范圍，為小于表長的某一整型常數(shù) 。 5） 折疊法： 將關(guān)鍵字的值分為幾段，爾后疊加求和 。 A、 移位折疊，將各段左對齊后相加 ； B、 邊界折疊，將奇數(shù)段、偶數(shù)段倒排后相加 。 排序中的關(guān)鍵字可是主關(guān)鍵字也可是次關(guān)鍵字，若是主關(guān)鍵字則排序結(jié)果唯一；若是次關(guān)鍵字則結(jié)果不唯一。因為在帶排序列中可能存在次關(guān)鍵字相同的記錄，若 Ki=Kj，在排序前 Ri 領(lǐng)先于Rj ，排序后順序不變，則稱該方法是穩(wěn)定的，反之，是不穩(wěn)定的。 若待排序記錄在排序過程中全部是存放在內(nèi)存里的，則稱該排序為內(nèi)排序； 若待排序記錄非常多，許借助外存來輔助存儲待排序記錄，則稱該排序為外排序。 排序功能：將一個數(shù)據(jù)元素的任意序列，重新排成一個按關(guān)鍵字有序的序列。 其過程分兩步： 首先比較兩個關(guān)鍵字的大小； 然后將記錄從一個位置移動到另一個位置。 典型的排序方法有： ? 插入 排序 ? 選擇排序 ? 交換排序 ? 快速排序 ? 歸并排序 堆排序是一種選擇排序 。 堆是具有特定條件的順序存儲的完全二叉樹 ，其特定條件是：任何一個非葉子結(jié)點的關(guān)鍵字大于等于 （ 或小于等于 ） 子女的關(guān)鍵字的值 。 堆排序 把自堆頂至葉子的調(diào)整過程稱為 “ 篩選 ” 。 從一個無序序列建堆的過程就是一個反復(fù) “ 篩選 ” 的過程 。 方法與構(gòu)造堆類似 。 (2) 輸出堆頂元素并調(diào)整建新堆的過程 (篩選 ) 65 25 36 56 49 78 41 11 (b) 65 36 56 49 78 41 11 (c) 25 11 25 36 56 49 78 41 65 (a) 25 49 36 56 65 78 41 (d) 11 25 56 49 78 11 65 41 36 (a)無序序列 n=8, int(n/2)=4開始 25 56 49 36 11 65 41 78 (b)78被篩選后的狀態(tài) 25 56 41 36 11 65 49 78 (c)49被篩選后的狀態(tài) 25 11 41 36 56 65 49 78 (d)56被篩選后的狀態(tài) (e)被篩選之后建成堆 11 25 41 36 56 65 49 78 (3) 由無序建初始堆的過程 ( 25,56,49,78,11,65,41,36 ) 基本思想： 對待排序記錄的關(guān)鍵字進(jìn)行兩兩比較，若出現(xiàn)不滿足順序的一對記錄，則交換之，直到全部記錄均滿足排序要求為止。 有 冒泡 和 快速排序 兩種。 三、交換排序 五、內(nèi)部排序方法的分析與選擇 排序方法 平均時間復(fù)雜度 輔助空間 穩(wěn)定性 直接插入排序 O(n2) O(1) 穩(wěn)定的 二分法插入排序 O(n2) O(1) 穩(wěn)定的 直接選擇排序 O(n2) O(1) 穩(wěn)定的 堆排序 O(nlog2n) O(1) 不穩(wěn)定的 起泡排序 O(n2) O(1) 穩(wěn)定的 快速排序 O(nlog2n) O(log2n) 不穩(wěn)定的 歸并排序 O(nlog2n) O(n) 穩(wěn)定的 操 作 系 統(tǒng) 操作系統(tǒng)就是能有效地管理計算機(jī)系統(tǒng)中的各種軟、硬件資源，合理地組織計算機(jī)的工作流程，為用戶創(chuàng)造良好工作環(huán)境的系統(tǒng)軟件。 操作系統(tǒng)是與裸機(jī)最接近的軟件層。 操作系統(tǒng)的功能： 處理機(jī)管理 存儲管理 設(shè)備管理 文件管理 操作系統(tǒng)的主要設(shè)計目標(biāo) ? 方便用戶使用 ? 擴(kuò)大機(jī)器功能 ? 提高系統(tǒng)效率 ? 構(gòu)筑開放環(huán)境 第二節(jié) 處理器管理 處理器管理就是要解決用戶提交的作業(yè)何時調(diào)入內(nèi)存，在調(diào)入內(nèi)存的各個作業(yè)程序間如何分配處理器，以達(dá)到各到程序能協(xié)調(diào)一致地運(yùn)行，而系統(tǒng)資源又能得到最大程度的利用。 進(jìn)程概念的引入 多道程序系統(tǒng)中程序并發(fā)性執(zhí)行 ， 為了競爭有限的資源 ， 相互間存在依賴與制約的關(guān)系 ， 因此他們在系統(tǒng)中的狀態(tài)是不斷變化的 ，即時而運(yùn)行 ， 時而停頓 。 程序執(zhí)行時所產(chǎn)生的問題使得傳統(tǒng)的程序概念已經(jīng)不足以對其進(jìn)行描述 ， 為之引入 進(jìn)程 （ Process)。 一、基本概念和術(shù)語 進(jìn)程的定義 進(jìn)程是一種活動 ， 它由一個動作系列組成 ， 每個動作是在某個數(shù)據(jù)集上執(zhí)行一段程序 ， 整個活動的結(jié)果是提供一種系統(tǒng)或用戶功能 。 一旦操作系統(tǒng)接受了某用戶的作業(yè) ， 并把他調(diào)入內(nèi)存執(zhí)行 ， 系統(tǒng)就為此作業(yè)創(chuàng)建一個或多個進(jìn)程 。 因此進(jìn)程可看作是程序的一次執(zhí)行 ， 即在指定內(nèi)存區(qū)域中的一組指令序列的執(zhí)行過程 。 多個進(jìn)程可并發(fā)運(yùn)行 ， 并可能由各種原因隨時中斷 。 進(jìn)程的主要特征 1） 動態(tài)性： 執(zhí)行初期被創(chuàng)建 ， 執(zhí)行結(jié)束被撤消； 2） 并發(fā)性： 并發(fā)執(zhí)行提高了計算機(jī)的系統(tǒng)資源的利用率； 3） 獨立性： 進(jìn)程是一個能夠獨立運(yùn)行的基本單位； 4） 異步性： 進(jìn)程相互制約 ， 其執(zhí)行具有間斷性 。 作業(yè) 、 作業(yè)步 作業(yè)是用戶在一次算題過程中或一個事物處理中要求計算機(jī)系統(tǒng)所做的工作的集合 。 一個作業(yè)由一系列有序的作業(yè)步組成 。 一個作業(yè)步運(yùn)行的結(jié)果產(chǎn)生下一個作業(yè)步所需的文件 。 作業(yè)的四種狀態(tài)： 提交 、 后備 、 執(zhí)行 、 完成 。 這是作業(yè)從進(jìn)入系統(tǒng)到運(yùn)行結(jié)束要經(jīng)歷的四種狀態(tài) 。 輔存 內(nèi)存 提交 后備 執(zhí)行 完成 設(shè)備管理 作業(yè)管理 去分配 運(yùn)行 就緒 阻塞 事件發(fā)生