clock.cpp

这是编写的一个操作系统的clock算法。是在vc++环境下编绎的。

#include<iostream.h>
template<typename T>class List;
template<typename T>class Node                   //结点类模板
{
public:
  T info;
  int A;
  int M;
  Node<T> *link;
public:
  Node();                                        //建立头结点的构造函数
  Node(const T & data);                          //建立一般结点的构造函数
                             
  friend class List<T>;                          //规定List为node的友员类
};
template<typename T>Node<T>::Node(){link=NULL;}
template<typename T>Node<T>::Node(const T & data)
{
  info=data;

  A=1;
  M=0;
  link=NULL;
}


template <typename T>class List                 //循环链表类模板
{
public:
	Node<T> *head;
public:
	List();
	~List();
	void Makeempty();
	Node<T>*find0(T data);             //查找内存中是否有输入
	Node<T>*find1(T data);             //查找A=0,M=0的模板
	Node<T>*find2(T data);             //查找A=0,M=1的模板并将访问的A复0             
	void Printlist();                            //输出链表
	void Insertrear(T data);                 //向后生成链表
	void tihuan(Node<T>*p,T data);               //替换函数
	void Pset1(Node<T> *p);                      //将访问的页A置0
	void Pset2(Node<T> *p);                      //将要修改的页M置1 
	void Change();
};
template<typename T>List<T>::List()
{
	head=new Node<T>();
	head->link=head;
}
template<typename T>List<T>::~List()
{
	Makeempty();
	delete head;
}
template<typename T>void List<T>::Makeempty()
{
	Node<T>*tempb,*del;
	tempb=head->link;
	while(tempb!=head)
	{
		tempb=tempb->link;
		del=tempb;
		delete del;
	}
	delete tempb;
}
template<typename T>Node<T>*List<T>::find0(T data)
{
	Node<T> *tempb;
	tempb=head->link;
	while(tempb!=head)
	{
		if(tempb->info==data)
			return tempb;
		tempb=tempb->link;
	}
	return NULL;
}
template<typename T>Node<T>*List<T>::find1(T data)
{
    Node<T> *tempb;
	tempb=head->link;
	while(tempb!=head)
	{
		if(tempb->A==0&&tempb->M==0)
			return tempb;
		tempb=tempb->link;
	}
	return NULL;
} 
template<typename T>Node<T>*List<T>::find2(T data) 
{
    Node<T> *tempb;
	tempb=head->link;
	while(tempb!=head)
	{
		if(tempb->A==0&&tempb->M==1)
			return tempb;
		tempb->A=0;
		tempb=tempb->link;
	}
	return NULL;
}
template<typename T>void List<T>::Printlist()
{
	Node<T> *tempb;
	tempb=head->link;
	cout<<"页号"<<'\t'<<"A"<<'\t'<<"M"<<endl;
	while(tempb!=head)
	{
		cout<<tempb->info<<'\t'<<tempb->A<<'\t'<<tempb->M<<endl;
		tempb=tempb->link;
	}
}
template<typename T> void List<T>::Insertrear(T data)
{
	Node<T> *p=new Node<T>(data);
	Node<T> *tempb,*tail;
	tempb=head;
	while(tempb->link!=head)
	{
		tempb=tempb->link;
	}
	tail=tempb;
    p->link=tail->link;
	tail->link=p;
}  
template<typename T>void List<T>::tihuan(Node<T>*p,T data)
{
	p->info=data;
	p->A=1;
	p->M=0;
}
template<typename T>void List<T>::Pset1(Node<T>*p)
{
	cout<<"huan,huan,huan,"<<endl;
	p->A=1;
}
template<typename T>void List<T>::Pset2(Node<T>*p)
{
	p->M=1;
}
template<typename T>void List<T>::Change()
{
	    T num;
		Node<T> *m;
		char flag;
		cout<<"是否要修改指定的页?Y/N(y/n)"<<endl;
		cin>>flag;
		switch(flag)
		{
		case 'y':
		case 'Y':
		    cout<<"请输入指定的页:"<<endl;
input:	    cin>>num;
			if(!(m=find0(num)))
			{
				cout<<"没有指定的页,请重输:"<<endl;
				goto input;
			}
			Pset2(m);
			Printlist();
        case 'n':
		case 'N':break;
		}
}
void main()
{
	Node<double> *m;
	List<double> *www=new List<double>();
    double num;
	int n=0;
	while(1)
	{
		if(n<5)
		{
			cout<<"请输入要访问的页面号："<<endl;
			cin>>num;
			www->Insertrear(num);
			n++;
		}else
		{
			www->Change();
        	cout<<"请输入要访问的页面号："<<endl;
			cin>>num;
head:		if((m=www->find0(num)))
			{
				cout<<"find0"<<endl;
				www->tihuan(m,num);
			}
			else if((m=www->find1(num)))
			{
				cout<<"find1"<<endl;
				www->tihuan(m,num);
			}
			else if((m=www->find2(num)))
			{
				cout<<"find2"<<endl;
				www->tihuan(m,num);
			}
			else
			{
				goto head;
			}
		}
		www->Printlist();
	}
}