lru.cpp

LRU对列队的实现,就是实现找出最近最少用的元素的算法.

#include "LRU.h"

//页数
int m_ipages;

//分配空间
Status InitQueue( Queue &Q )
{
   
	Q.base = new ElemType[MAXSIZE + 1];
	if( !Q.base )
		return ERROR;
	Q.front = Q.rear = 0;
	return OK;
}

//求得队列长度
Status QueueLength( Queue Q )
{
	return (Q.rear - Q.front + MAXSIZE + 1) % (MAXSIZE + 1);
}

//输入数据
Status EnQueue( Queue &Q, ElemType e)
{
    ElemType temp;
    if( (Q.rear + 1) % (MAXSIZE + 1 ) == Q.front )
	{
	   	for( temp = Q.front; temp < Q.rear-1 ; temp++ )
		{
		   Q.base[temp] = Q.base[temp+1];
		}
		Q.base[Q.rear-1] = e;
	}
	else
	{
	    Q.base[Q.rear] = e;
		Q.rear = (Q.rear + 1) % (MAXSIZE + 1);
	}
	return OK;
}


//逐个读出队列中的数据
Status VisualQueue( Queue Q )
{
	int i;
	for( i = Q.front; i < QueueLength(Q); i++ )
	{
		cout << Q.base[i] << "\t";
	}
	cout << endl;
	return OK;
}


//初始化队列
void Init( Queue &Q1, Queue &Q2 )
{
	InitQueue(Q1);
	InitQueue(Q2);

	ElemType *itemp;
	itemp = new ElemType[MAXSIZE];
	ElemType e;
	int length = 0;
	int i;
	ElemType *p = itemp;

	while( m_ipages < LEASTPAGES )
	{
		cout << "Enter pages of a task:";
		cin >> m_ipages;
	}

	srand(time(0));
	do
	{
		e = rand() % m_ipages + 1;
		*(itemp + length) = e;
		length++;
		i = 0;
		p = itemp;
		for( ; i < length - 1; i++ )
		{
			if( e == *(p + i) )
			{
				length--;
				break;
			}
		}

	}while( length < MAXSIZE );

	for( i = 0; i < MAXSIZE; i++ )
	{
		EnQueue( Q1, itemp[i] );
	}

	VisualQueue( Q1 );
	delete[] itemp;
}


//寻找函数
int find( Queue &Q, int nID )
{
    return Q.base[nID];

}
void play( Queue &Q1, Queue &Q2 )
{

    ElemType ID,finditem,initem;
	ElemType OutID;
	char select;
	int i;

	do{
		cout<<"请选择要更改数据ID:";
		cin>>ID;
		finditem = find( Q1, ID );
		cout<<"你要更改数据是:"<<finditem<<endl;
	
		cout<<"你要更改数据方式是A更新数据,B删除数据,Q退出:";
		cin>>select;
		if( select == 'A' )
		{
			cout<<"输入你要输入的值";
			cin>>initem;
			Q1.base[ID] = initem;
			EnQueue( Q2, initem );
			cout << "Q1:";
			VisualQueue( Q1 );
			cout << "Q2:";
			VisualQueue( Q2 );
			cout << endl;
		}
		if( select == 'B' )
		{
			for( i = ID; i<Q1.rear; i++ )
			{
				Q1.base[i] = Q1.base[i + 1];
			}
				
				srand(time(0)); 
				OutID = rand() % m_ipages + 1;
				Q1.base[Q1.rear-1] = OutID;
				cout << "Q1:";
				VisualQueue( Q1 );
				cout << "Q2:";
				VisualQueue( Q2 );
				cout << endl;
			
		}
		
	}while( select != 'Q' && select != 'q' );
}