//OPT---最佳置換算法
#if?1
//by?liuhao
//選擇永不使用或者最長時間不被使用的頁面進行置換
//每次操作完之后重置隊列
//?7?0?1?2?0?3?0?4?2?3?0?3?2?1?2?0?1?7?0?1
//結果：缺頁數：9???置換數：6???缺頁率：45%
#include?
#include?
#include?
#include?//sort（）頭文件
using?namespace?std;

struct?pages
{
	int?value;
	int?time;
};
bool?GreaterSort（pages?a?pages?b）
{
	return?（a.time?>?b.time）;
}


int?main（）
{
	deque??dq;
	deque::iterator?pos;
	int?blockNum;//物理塊數
	int?pageNum;//訪問頁面個數
	int?missPageNum?=?0;//缺頁數
	int?pageLabel;//當前輸入的頁面標簽
	vector?pageList;//頁面訪問序列

	cout?<
	cout?<	cin?>>?blockNum;

	cout?<	cin?>>?pageNum;

	cout?<	for?（int?i?=?0;?i?	{
		cin?>>?pageLabel;
		pageList.push_back（pageLabel）;
	}


	for?（int?i?=?0;?i?	{
		if?（dq.size（）?		{
			bool?flag?=?false;
			for?（pos?=?dq.begin（）;?pos?!=?dq.end（）;?pos++）
			{
				if?（（*pos）.value?==?pageList[i]）//存在元素和它相同
				{
					flag?=?true;
					break;
				}??//存在該元素
			}

			if?（!flag）?//不存在此元素
			{
				missPageNum++;//缺頁數+1
				pages?temp;
				temp.value?=?pageList[i];

				bool?flag2?=?false;
				for?（int?j?=?i?+?1;?j?				{
					if?（pageList[j]?==?pageList[i]）
					{
						flag2?=?true;
						temp.time?=?j?-?i;
						break;
					}
				}
				if?（!flag2）
					temp.time?=?pageNum;//如果后面序列沒有出現，time設置為總訪問頁面個數
				dq.push_back（temp）;
			}
		}
		else?//不存在多余頁框
		{
			bool?flag?=?false;
			for?（pos?=?dq.begin（）;?pos?!=?dq.end（）;?pos++）
			{
				if?（（*pos）.value?==?pageList[i]）
				{
					flag?=?true;
					break;
				}??//存在該元素
			}

			if?（!flag）?//不存在此元素?則置換time最大的項
			{
				missPageNum++;//缺頁數+1
				//?按照time從大到小排序
				sort（dq.begin（）?dq.end（）?GreaterSort）;
				int?maxTime?=?dq.front（）.time;//第物理塊中第一個頁面的time
				dq.pop_front（）;//time值最大的出隊列

				pages?temp;
				temp.value?=?pageList[i];
				bool?flag2?=?false;

				for?（int?j?=?i?+?1;?j?				{
					if?（pageList[j]?==?pageList[i]）
					{
						flag2?=?true;
						temp.time?=?j?-?i;
						break;
					}
				}

				if?（!flag2）
					temp.time?=?pageNum;
				dq.push_back（temp）;
			}
		}
		//每次之后重置
		cout?<		for?（pos?=?dq.begin（）;?pos?!=?dq.end（）;?pos++）
		{
			cout?<			int?flag?=?false;
			for?（int?j?=?i?+?1;?j?			if?（pageList[j]?==?（*pos）.value）
			{
				flag?=?true;
				（*pos）.time?=?j?-?i;
				break;
			}
			if?（!flag）
				（*pos）.time?=?pageNum;
			//cout?<???“;
		}
		cout?<	}
	cout?<	cout?<	cout?<	system（“pause“）

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2019-05-13?17:31??頁面置換算法\
?????目錄???????????0??2019-05-13?16:50??頁面置換算法\Debug\
?????文件??????115200??2019-05-13?17:36??頁面置換算法\Debug\頁面置換算法.exe
?????文件??????576792??2019-05-13?17:36??頁面置換算法\Debug\頁面置換算法.ilk
?????文件?????1412096??2019-05-13?17:36??頁面置換算法\Debug\頁面置換算法.pdb
?????文件??????????22??2019-05-13?17:31??頁面置換算法\頁面置換算法.opensdf
?????文件?????7864320??2019-05-13?17:32??頁面置換算法\頁面置換算法.sdf
?????文件????????1000??2019-05-11?11:08??頁面置換算法\頁面置換算法.sln
?????文件???????27648??2019-05-11?23:57??頁面置換算法\頁面置換算法.v12.suo
?????目錄???????????0??2019-05-13?17:36??頁面置換算法\頁面置換算法\
?????目錄???????????0??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\
?????文件??????400320??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\main.obj
?????文件??????486400??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\vc120.idb
?????文件??????446464??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\vc120.pdb
?????文件????????2754??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.log
?????目錄???????????0??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\
?????文件????????1238??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\cl.command.1.tlog
?????文件???????18940??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\CL.read.1.tlog
?????文件?????????452??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\CL.write.1.tlog
?????文件????????5862??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\link.command.1.tlog
?????文件????????8262??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\link.read.1.tlog
?????文件?????????430??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\link.write.1.tlog
?????文件?????????195??2019-05-13?17:36??頁面置換算法\頁面置換算法\Debug\頁面置換算法.tlog\頁面置換算法.lastbuildstate
?????文件????????7981??2019-05-13?17:36??頁面置換算法\頁面置換算法\main.cpp
?????文件????????4095??2019-05-11?13:13??頁面置換算法\頁面置換算法\頁面置換算法.vcxproj
?????文件?????????945??2019-05-11?13:13??頁面置換算法\頁面置換算法\頁面置換算法.vcxproj.filters