#include?
#include?
#include?
#define?N?500????//定義隨機請求數組大小

/*==========================頁框結構定義=====================*/
typedef?struct?PageList?//頁表
{
	int?PageID;??//頁號
	int?A;???????//訪問位
	int?M;		//修改位
}Elem;
typedef?struct?LNode
{
	Elem?data;
	LNode?*next;
}*linkList;


/*======================LRU鏈表定義=======================*/
typedef?struct?LRUList??
{
	int?data;
	LRUList?*next;
}LRUList;


/*=====================FIFO隊列定義=======================*/
typedef?struct?Node
{
	int?data;
	struct?Node?*next;
}Node;
typedef?struct?FIFOqueue
{
	struct	Node?*front;
	struct??Node?*rear;
}FIFOqueue;

/*====================SClock循環鏈表定義==================*/
typedef?struct?SNode
{
	int?data;
	struct?SNode?*next;

}SClockList;
?
/*===========================所有函數及全局變量聲明================================*/
int?current;							//當前填入的頁框數
int?miss;								//缺頁次數
double?rate;							//缺頁率	
void?Init（）;							//頁表初始化
void?Optimal（int?[]）;					//最佳置換
void?Random（int?[]）;					//隨機置換算法
void?FIFO（int?[]）;						//先進先出
void?LRU（int?[]）;						//LRU
void?SClock（int?[]）;					//簡單clock
void?MClock（int?[]）;					//改進clock
void?InFIFO（FIFOqueueint）;				//進隊列操作
int?OutFIFO（FIFOqueue）;					//出隊列操作
void?DeleteLRU（LRUList?*int）;			//刪除LRU一個節點
void?AddLRU（LRUList?*int）;				//在LRU鏈表頭添加節點
void?Show（int?）;						//顯示
int?Find（int?）;							//查找頁面函數
int?max（intintint）;					//三數找最大函數
int?Count（intint[]）;					//最佳置換計算步數函數
void?InsertSclock（SClockList?*intint）;//在Sclock鏈表中插入節點
void?DeleteSclock（SClockList?*int）;	//刪除Sclock鏈表中一個節點
linkList???first;?
linkList???middle;
linkList???last;
LRUList????*head;
FIFOqueue?*queue;
SClockList?*sc;


/*==============================FIFO隊列基本操作===========================================*/
void?InFIFO（FIFOqueue?*queueint?a）????????????????????//入隊函數
{
	Node?*p;
	p=（Node?*）malloc（sizeof（Node））;
	p->data=a;
	p->next=NULL;
	queue->rear->next=p;
	queue->rear=p;
}
int?OutFIFO（FIFOqueue?*queue）???????????????????????????//出隊函數
{
	Node?*p;
	int?a;
	if?（queue->front==queue->rear）
	{}
	else
	{
		p=queue->front->next;
		queue->front->next=p->next;??????????//隊頭元素出隊
		if?（queue->rear==p）
			queue->rear=queue->front;
		a=p->data;
		free（p）;		
		return?a;
	}
	return?-1;
}


/*================================LRU鏈表基本操作=============================================*/
void?AddLRU（LRUList?*headint?a）????????????????????//添加節點至鏈表頭
{
	LRUList?*p=NULL*q=NULL;
	q=head;
	p=（LRUList?*）malloc（sizeof（LRUList））;
	p->next=q->next;
	q->next=p;
	p->data=a;
}
void?DeleteLRU（LRUList?*headint?m）?????????????????//刪除節點
{
	LRUList?*p=NULL*q=NULL;
	q=head;
	p=head->next;
	while（p!=NULL）
	{
		if?（p->data!=m）
		{
			q=q->next;
			p=p->next;
		}
		else
			break;
	}
	q->next=p->next;
}


/*=============================SClock鏈表基本操作===========================================*/
void?InsertSclock（SClockList?*scint?mint?i）
{
	SClockL