一、鄰接表為什么不用set而用vector存儲
因為鄰接表不需要有序,它只是用來存邊的。鄰接表較好使用鏈式前向星,vector存圖常數有點大。set的功能:有序、判重、查詢,這些對于鄰接表來說是累贅。鄰接表只需要把邊存下來并維護邊與邊之間的聯系即可。判重題目往往都會排除,有序和查詢就更用不到了。
鄰接表是圖的一種鏈式存儲結構。
由兩部分組成:表頭結點表和邊表。
鄰接表中每個單鏈表的名列前茅個結點存放有關頂點的信息,把這一結點看成鏈表的表頭,其余結點存放有關邊的信息
(1)表頭結點表:包括數據域和鏈域,數據域存儲頂點的名稱,鏈域用于指向鏈表中名列前茅個結點(與頂點鄰接的名列前茅個頂點)
(2)邊表:包括鄰接點域(指示與頂點鄰接的點在圖中的位置,即數組下標)、數據域(存儲和邊相關的信息,如權值)、鏈域(指示與頂點鄰接的下一條邊的結點)。
延伸閱讀:
二、全局頁面置換算法
工作集模型工作集頁置換算法缺頁率置換算法功能:
當缺頁中斷發生,需要調入新的頁面而內存已滿時,選擇內存當中哪個物理頁面被置換。
目標:
盡可能地減少頁面的換進換出次數(既缺頁中斷的次數)。具體來說,把未來不再使用的或短期內較少使用的頁面換出,通常只能在局部性原理指導下依據過去的統計數據來進行預測。
頁面鎖定(frame locking):
用于描述必須常駐內存的操作系統的關鍵部分或時間關鍵(time-critical)的應用程序。實現的方法是L在頁表中添加鎖定標志位(lock bit)。使其不在頁面置換算法范圍之內,也就說不會被換入換出。
通常只需要考慮頁號,因為偏移號一般不起作用。只保留頁號。基于這個list來設計各種的頁面替換算法。
通過模擬一個頁面置換的行為并且記錄產生頁缺失數的數量。一般情況下,產生的缺頁次數越少,性能就越高。