#include?
#include?
#include?
#define?N?500????//定義隨機(jī)請求數(shù)組大小

/*==========================頁框結(jié)構(gòu)定義=====================*/
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隊(duì)列定義=======================*/
typedef?struct?Node
{
	int?data;
	struct?Node?*next;
}Node;
typedef?struct?FIFOqueue
{
	struct	Node?*front;
	struct??Node?*rear;
}FIFOqueue;

/*====================SClock循環(huán)鏈表定義==================*/
typedef?struct?SNode
{
	int?data;
	struct?SNode?*next;

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


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


/*================================LRU鏈表基本操作=============================================*/
void?AddLRU（LRUList?*headint?a）????????????????????//添加節(jié)點(diǎn)至鏈表頭
{
	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）?????????????????//刪除節(jié)點(diǎn)
{
	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