一、鄰接表為什么不用set而用vector存儲(chǔ)
因?yàn)猷徑颖聿恍枰行颍皇怯脕泶孢叺摹`徑颖磔^好使用鏈?zhǔn)角跋蛐牵瑅ector存圖常數(shù)有點(diǎn)大。set的功能:有序、判重、查詢,這些對(duì)于鄰接表來說是累贅。鄰接表只需要把邊存下來并維護(hù)邊與邊之間的聯(lián)系即可。判重題目往往都會(huì)排除,有序和查詢就更用不到了。
鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
由兩部分組成:表頭結(jié)點(diǎn)表和邊表。
鄰接表中每個(gè)單鏈表的名列前茅個(gè)結(jié)點(diǎn)存放有關(guān)頂點(diǎn)的信息,把這一結(jié)點(diǎn)看成鏈表的表頭,其余結(jié)點(diǎn)存放有關(guān)邊的信息
(1)表頭結(jié)點(diǎn)表:包括數(shù)據(jù)域和鏈域,數(shù)據(jù)域存儲(chǔ)頂點(diǎn)的名稱,鏈域用于指向鏈表中名列前茅個(gè)結(jié)點(diǎn)(與頂點(diǎn)鄰接的名列前茅個(gè)頂點(diǎn))
(2)邊表:包括鄰接點(diǎn)域(指示與頂點(diǎn)鄰接的點(diǎn)在圖中的位置,即數(shù)組下標(biāo))、數(shù)據(jù)域(存儲(chǔ)和邊相關(guān)的信息,如權(quán)值)、鏈域(指示與頂點(diǎn)鄰接的下一條邊的結(jié)點(diǎn))。
延伸閱讀:
二、全局頁(yè)面置換算法
工作集模型工作集頁(yè)置換算法缺頁(yè)率置換算法功能:
當(dāng)缺頁(yè)中斷發(fā)生,需要調(diào)入新的頁(yè)面而內(nèi)存已滿時(shí),選擇內(nèi)存當(dāng)中哪個(gè)物理頁(yè)面被置換。
目標(biāo):
盡可能地減少頁(yè)面的換進(jìn)換出次數(shù)(既缺頁(yè)中斷的次數(shù))。具體來說,把未來不再使用的或短期內(nèi)較少使用的頁(yè)面換出,通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù)據(jù)來進(jìn)行預(yù)測(cè)。
頁(yè)面鎖定(frame locking):
用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵(time-critical)的應(yīng)用程序。實(shí)現(xiàn)的方法是L在頁(yè)表中添加鎖定標(biāo)志位(lock bit)。使其不在頁(yè)面置換算法范圍之內(nèi),也就說不會(huì)被換入換出。
通常只需要考慮頁(yè)號(hào),因?yàn)槠铺?hào)一般不起作用。只保留頁(yè)號(hào)。基于這個(gè)list來設(shè)計(jì)各種的頁(yè)面替換算法。
通過模擬一個(gè)頁(yè)面置換的行為并且記錄產(chǎn)生頁(yè)缺失數(shù)的數(shù)量。一般情況下,產(chǎn)生的缺頁(yè)次數(shù)越少,性能就越高。