}
////////////////////////////////////////////////////////////////
typedefstructQNode//定义队列数据结构
{
intdata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;//头指针
QueuePtrrear;//尾指针
}LinkQueue;
//定义链表结点
typedefstructLNode//定义循环链表数据结构
{
intdata;
intflag;//访问位
intmodify;//修改位
structLNode*next;
}LNode,*LinkList;
//////////////////////////////////////////////////////////////////////////对循环链表的一些操作
intCreatList(LinkList&L)//创建循环带有头结点的链表
{
L=(LinkList)malloc(sizeof(LNode));
if(!
L)exit(-1);
L->next=L;
L->flag=0;
return1;
}
intExchange_LNode(LinkList&L,inte,inti)//将链表L中序号为i的结点替换为内容为e的结点
{
if(L->next==L)exit(-1);
LinkListp,q;
intj=0;
p=(LinkList)malloc(sizeof(LNode));
q=(LinkList)malloc(sizeof(LNode));
q->data=e;
p=L;
for(j=0;j
p=p->next;
q->next=p->next->next;
p->next=q;
q->flag=1;//设置新结点的访问位为1
q->modify=0;//设置新结点的修改位为0
return1;
}
intInsert_LNode(LinkList&L,inte)//在循环链表中插入新的结点,从L头结点开始依次向后插入
{
LinkListp,q;
p=(LinkList)malloc(sizeof(LNode));
q=(LinkList)malloc(sizeof(LNode));
q->data=e;
q->flag=1;//设置新结点的访问位为1
q->modify=0;//设置新结点的修改位为0
p=L;
while(p->next!
=L)
{
p=p->next;
}
p->next=q;
q->next=L;
return1;
}
boolSearch_LinkList(LinkList&L,inte,int&i)//找到链表L中内容为e的结点,并用i返回其位置,i=1表示第一个非头结点,依次类推
{
i=1;
if(L->next==L)exit(-1);
LinkListp;
p=(LinkList)malloc(sizeof(LNode));
if(!
p)exit(-1);
p=L->next;//p指向链表的第一个结点(非头结点)
while(p!
=L&&p->data!
=e)
{
p=p->next;
i++;
}
if(p==L)//没有找到符合要求的结点
returnfalse;
returntrue;
}
voidSearch_LL_Flag(LinkList&L,int&i)//用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点,以此类推
{
i=1;
LinkListp;
p=(LinkList)malloc(sizeof(LNode));
if(!
p)exit(-1);
p=L->next;
while(p->flag!
=0)
{
p->flag=0;//修改访问标志位为0
p=p->next;
if(p==L)//跳过头结点
p=p->next;
i++;
if(i==4)//跳过头结点
i=1;
}
//return1;
}
voidSet_LL_Flag(LinkList&L,inti)//设置链表L中的序号为i的结点的flag标志为1;
{
LinkListp;
p=(LinkList)malloc(sizeof(LNode));
if(!
p)exit(-1);
p=L->next;
if(i==1)
p->flag=1;
if(i==2)
{
p=p->next;
p->flag=1;
}
if(i==3)
{
p=p->next;
p=p->next;
p->flag=1;
}
}
intSearch_LL_ModifyClock(LinkList&L,int&modify_num)//找到改进的CLOCK算法所需要淘汰的页,用modify_num返回其位置
{
modify_num=1;
if(L->next==L)exit(-1);
LinkListp;
p=(LinkList)malloc(sizeof(LNode));
if(!
p)exit(-1);
p=L->next;//p指向链表的第一个结点(非头结点)
while(p!
=L)//第一轮扫描A=0并且M=0的结点
{
if(p->flag==0&&p->modify==0)
break;//找到
p=p->next;
modify_num++;
}
if(p==L)
{
modify_num=1;
p=L->next;
while(p!
=L)//第二轮扫描A=0并且M=1的结点,同时修改访问过的结点的访问位为0
{
if(p->flag!
=0)
p->flag=0;
elseif(p->modify==1)
break;
p=p->next;
modify_num++;
}
}
if(p==L)
{
modify_num=1;
p=L->next;
while(p!
=L)//第三轮扫描A=0并且M=0的结点
{
if(p->flag==0&&p->modify==0)
break;
p=p->next;
modify_num++;
}
if(p==L)
{
modify_num=1;
p=L->next;
while(p!
=L)//第四轮扫描A=0并且M=1的结点
{
if(p->flag!
=0)
p->flag=0;
elseif(p->modify==1)
break;
p=p->next;
modify_num++;
}
}
}
return1;
}
voidSet_LL_modify(LinkList&L,inti)//设置链表L中的序号为i的结点的modify标志为1;
{
LinkListp;
p=(LinkList)malloc(sizeof(LNode));
if(!
p)exit(-1);
p=L->next;
if(i==0)
p->modify=1;
if(i==1)
{
p=p->next;
p->modify=1;
}
if(i==2)
{
p=p->next;
p=p->next;
p->modify=1;
}
}
intDestroyLinkList(LinkList&L)//删除链表,并释放链表空间
{
LinkListp,q;
p=(LinkList)malloc(sizeof(LNode));
if(!
p)exit(-1);
q=(LinkList)malloc(sizeof(LNode));
if(!
q)exit(-1);
p=L->next;
while(p!
=L)
{
q=p->next;
free(p);
p=q;
}
free(q);
return1;
}
////////////////////////////////////////////////////////////////对队列的一些操作
intInitQueue(LinkQueue&Q)//队列初始化
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!
Q.front)exit(-1);
Q.front->next=NULL;
return1;
}
intEnQueue(LinkQueue&Q,inte)//插入元素e为Q的新的队尾元素
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!
p)exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return1;
}
intDeQueue(LinkQueue&Q,int&e)//若队列不空,则删除Q的队头元素,用e返回其值
{
if(Q.front==Q.rear)return-1;
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return1;
}
boolSearchQueue(LinkQueue&Q,inte,int&i)//寻找队列Q中结点data域等于e的结点,并用i返回其在Q中的位置
{
i=1;
if(Q.front==Q.rear)exit(-1);
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!
p)exit(-1);
p=Q.front->next;//p指向队列的第一个节点(非头结点)
while(p!
=NULL&&p->data!
=e)
{
p=p->next;
i++;
}
if(!
p)
returnfalse;
returntrue;
}
intDelMid_Queue(LinkQueue&Q,int&e)//删除Q的中间元素,并用e返回其值
{
if(Q.front==Q.rear)return-1;
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!
p)exit(-1);
p=Q.front->next;
e=p->next->data;
p->next=p->next->next;
return1;
}
intDestroyQueue(LinkQueue&Q)//删除队列并释放空间
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return1;
}
//////////////////////////////////////////////////////////////
intmax1(inta,intb,intc)//返回a,b,c中的最大值
{
if(a
if(areturna;
}
intgetnum(inta,intb)//用b返回元素a在被引用数列中的下一个位置
{
for(;b{
if(a