【正文】 輔存 內存 提交 后備 執(zhí)行 完成 設備管理 作業(yè)管理 去分配 運行 就緒 阻塞 事件發(fā)生 2。 作業(yè)的四種狀態(tài)： 提交 、 后備 、 執(zhí)行 、 完成 。 一個作業(yè)由一系列有序的作業(yè)步組成 。 進程的主要特征 1） 動態(tài)性： 執(zhí)行初期被創(chuàng)建 ， 執(zhí)行結束被撤消； 2） 并發(fā)性： 并發(fā)執(zhí)行提高了計算機的系統(tǒng)資源的利用率； 3） 獨立性： 進程是一個能夠獨立運行的基本單位； 4） 異步性： 進程相互制約 ， 其執(zhí)行具有間斷性 。 因此進程可看作是程序的一次執(zhí)行 ， 即在指定內存區(qū)域中的一組指令序列的執(zhí)行過程 。 一、基本概念和術語 進程的定義 進程是一種活動 ， 它由一個動作系列組成 ， 每個動作是在某個數(shù)據(jù)集上執(zhí)行一段程序 ， 整個活動的結果是提供一種系統(tǒng)或用戶功能 。 進程概念的引入 多道程序系統(tǒng)中程序并發(fā)性執(zhí)行 ， 為了競爭有限的資源 ， 相互間存在依賴與制約的關系 ， 因此他們在系統(tǒng)中的狀態(tài)是不斷變化的 ，即時而運行 ， 時而停頓 。 操作系統(tǒng)是與裸機最接近的軟件層。 有 冒泡 和 快速排序 兩種。 方法與構造堆類似 。 堆排序 把自堆頂至葉子的調整過程稱為 “ 篩選 ” 。 典型的排序方法有： ? 插入 排序 ? 選擇排序 ? 交換排序 ? 快速排序 ? 歸并排序 堆排序是一種選擇排序 。 排序功能：將一個數(shù)據(jù)元素的任意序列，重新排成一個按關鍵字有序的序列。因為在帶排序列中可能存在次關鍵字相同的記錄，若 Ki=Kj，在排序前 Ri 領先于Rj ，排序后順序不變，則稱該方法是穩(wěn)定的，反之，是不穩(wěn)定的。 A、 移位折疊，將各段左對齊后相加 ； B、 邊界折疊，將奇數(shù)段、偶數(shù)段倒排后相加 。 H（ K） = K MOD p + C （ p?m） C 的作用可以調節(jié)最終的地址范圍，為小于表長的某一整型常數(shù) 。 H(Key) = Key2 = an an1 … a2 a1 0100,1100,1200,1160,2060,2061,2163,2261,2262 設存儲空間 01000 平方后，取 4位構成哈希地址如下： 010,210,440,345,243,247,678,112,116 4） 除留余數(shù)法 ： 取關鍵字被不大于散列表表長 m 的數(shù) p除后所得的余數(shù)為哈希函數(shù)。 地址 01 02 03 …… 20 年份 1 2 3 …… . 20 保費 …… . …… . …… . …… …… 哈希函數(shù)的構造方法 2） 數(shù)字分析法 : 該法適用于較大的靜態(tài)數(shù)據(jù) ， 在已知所有關鍵字鍵值的情況下 ， 分析每一位的數(shù)字分布是否均勻 ， 刪除不均勻分配的數(shù)字位 ， 根據(jù)存儲空間的大小來確定所取地址的位數(shù) 。 哈希函數(shù) /哈希表的基本概念 1） 直接定址法： H(K)=K 或 H(K)=A*K+B； (其中 A、 B為常數(shù) )； 取關鍵字或關鍵字的某個 線性函數(shù)值 為散列地址 。 采用哈希技術主要目標是提高查找效率，要求縮短查表和填表的時間 . 哈希查找 ： 又叫散列查找，利用哈希函數(shù)進行查找的過程 。 哈希表： 哈希表是一種存儲結構，是能用散列技術進行查找的表， 也叫 散列存儲 。 二叉排序樹的平均查找長度介于對分查找與線性查找之間。 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}構成一棵二叉排序樹的過程 上述查找過程可見，在查找過程中，生成了一條查找路徑： 從根結點出發(fā)，沿 ? 動態(tài)查找，就是在查找失敗時進行“插入”操作，將要查找的關鍵字插入到結構中； ? 若二叉排序樹為空樹，則新插入的結點為新的根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。 二、對分查找（折半查找、二分法查找） 查找 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 最大 最小 兩者之間 表結構 有序表、無序表 有序表 分塊有序表 存儲結構 順序存儲結構線性鏈表 順序存儲結構 順序存儲結構線性鏈表 四、二叉排序樹查找 （ 1）若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值； 1．定義： 二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹： （ 3）它的左、右子樹也都分別是二叉排序樹。 適用條件：必須在具有順序存儲結構的有序表中進行 。 找到：返回元素在線性表中的存儲位置；未找到：返回 0。 /*從表尾往前查 */ return( i)。 ST[0].key=Key。 查找的結果：查找成功，則返回找到滿足條件的結點； 查找失敗，則返回找不到滿足條件的結點的信息。 不同的數(shù)據(jù)結構采用不同的查找方法，查找的效率直接影響數(shù)據(jù)處理的效率； 關鍵字 ——是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它可以標識一個數(shù)據(jù)元素 . 查找方法評價：查找速度、占用存儲空間多少、算法本身復雜程度、 平均查找長度 ASL(Average Search Length)。 弗洛伊德算法思想：逐步試著在原直接路徑中考慮其它頂點作為中間點，如增加中間點后得到的路徑較原路徑長度減小，則以此新路徑長度代替原值而修改矩陣元素；若增加中間點后的路徑比原路徑更長，就維持原相應的矩陣元素值不變。 廣度優(yōu)先遍歷 (BFS) 從圖的某一頂點 V0出發(fā)，訪問此頂點后，依次訪問 V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止。 V1 V3 V2 V4 V1 V3 V2 V4 鄰接表 4 3 2 1 ∧ 3 ∧ 4 ∧ 4 ∧ 1 4 3 2 1 2 1 ∧ 1 1 3 ∧ 4 ∧ 4 ∧ 2 V1 V2 V4 V5 V3 V7 V6 V8 V1?V2?V4?V8? V5?V3?V6?V7 V1 V2 V4 V5 V3 V7 V6 V8 V1?V2?V4?V8?V3?V6?V7?V5 三、圖的 遍歷 從圖中某一頂點出發(fā)，訪遍圖中其余頂點 ,且使每個頂點僅被訪問且僅被訪問一次。在鄰接表中，對圖中的每個結點建立一個單鏈表。 缺點：浪費空間，可用處理“稀疏”矩陣的方式去處理。 V1 V3 V2 V4 V1 V2 V3 V4 V1 0 1 1 1 V2 1 0 0 1 V3 1 0 0 0 V4 1 1 0 0 特點：由上述可知，無向圖或網(wǎng)絡的鄰接矩陣是對稱的。 一、 圖的基本概念 有向圖 (Digraph) G1 G=( V, E ) 頂點集合 V={V1 ， V2 ， V3 ， V4 } 弧的集合 E={V1 ， V3, V3 ， V4, V2 ， V4, V4， V1 } V1 V3 V2 V4 G1 無向圖 (Undigraph) G2 V1 V3 V2 V4 G2 頂點集合 V={V1 ， V2 ， V3 ， V4 } 邊的集合 E={(V1, V3), (V1, V2), (V1, V4),(V2, V4)} 頂點 (V1, V3)與 (V1, V3)表示同一條邊 權： 與圖的邊或弧相關的數(shù)叫權 (Weight） ， 可以表示從一個頂點到另一個頂點的距離或耗費； 帶權的圖叫 網(wǎng) ； 子圖： 圖 G(V,E)和圖 G’(V’,E’),若 V’?V， E’?E， 則稱 G’為 G的子圖； 頂點的 度： 無向圖中 ， 頂點的度為與每個頂點相連的邊的數(shù)目； 有向圖中 ， 頂點的度分成入度與出度； 入度： 以該頂點為頭的弧的數(shù)目； 出度： 以該頂點為尾的弧的數(shù)目； 二、圖的相關術語 V1 V3 V2 V4 V1 V3 V2 V4 路徑： 路徑是頂點的序列 V={Vi0,Vi1,…… Vin}， 滿足 (Vij1,Vij)?E 或 Vij1,Vij?E,(1j?n)； 路徑上的邊或弧的數(shù)目，稱為該 路徑的長度 。 A C S 各字符編碼是 T ； A C S 00 01 10 110 111 上述電文編碼： 11010111011101000011111000011000 哈夫曼編碼 圖 (Graph)： 圖 G是由兩個集合 V(G)和 E(G)組成的 ,記為 G=(V,E） ， 其中： V(G)是頂點的非空有限集； E(G)是邊的有限集合，邊是頂點的無序對或有序對； 有向圖： 有向圖 G是由兩個集合 V(G)和 E(G)組成的， 其中： V(G)是頂點的非空有限集， E(G)是有向邊（也稱 弧 ）的有限集合，弧是頂點的有序對，記為 v,w， v,w是頂點， v為弧尾， w為弧頭， （ v,w)!=(w,v)。 A C S 各字符編碼是 T ； A C S 00 01 10 110 111 上述電文編碼： 11010111011101000011111000011000 哈夫曼編碼 利用哈夫曼樹構造通訊中的電文編碼 （ 前綴碼 ） 。 18 a 7 11 c d b 5 6 2 4 (d) a b c d 7 5 2 4 (a) 哈夫曼樹的構造過程 6 c d (b) a b 7 5 11 b c d (c) a 7 方法： 1） 用 { 2， 4， 2， 3， 3 }作為葉子結點的權值生成一棵哈夫曼樹 ， 并將對應權值 wi的葉子結點注明對應的字符； 2） 約定左分支表示字符 “ 0”， 右分支表示字符 ‘ 1’ 3） 從葉子結點開始 ， 順著雙親反推上去 ， 直到根結點 ， 路徑上的 ‘ 0’或 ‘ 1’連接的序列就是結點對應的字符的二進制編碼的逆序 。 Tn},每棵二叉樹僅有一個帶權為 wi的根結點；