作者: 文竹 出自: vczx.com
//用循环单链表实现队列的基本操作
//算法的实现：
#include
#include
#include
typedef int DateType;
struct Node;
typedef struct Node *PNode;
struct Node//结点结构
{
DateType info;
PNode link;
};
//函数声明
int isEmptyQueue_link(PNode &p);
void enQueue_link(PNode &p,DateType x);
void deQueue_link(PNode &p);
DateType frontQueue_link(PNode &p);
void scan_link(PNode &p);
//主函数
void main()
{
PNode head=NULL;
int i=1,x,y;
while(i)
{
printf("**********************************************************************\n");
printf("请选择：1 判断队列是否为空 2 进队列 3 出队列 4 取队列头部元素的值\n");
printf(" 5 遍历队列 0 退出程序\n");
printf("**********************************************************************\n");
scanf("%d",&i);
switch(i)
{case 1:y=isEmptyQueue_link(head);
if(y==1)
printf("队列为空!\n");
else printf("队列非空！\n");
break;
case 2:printf("请你输入进队列的元素值: ");
scanf("%d",&x);
enQueue_link(head,x);
break;
case 3:deQueue_link(head);
break;
case 4:y=frontQueue_link(head);
if(y!=65535)
printf("队列头部元素的值为：%d\n",y);
break;
case 5:scan_link(head);
break;
default:if(i!=0)
printf("选择有错!请你重新选择!\n");
}
}
}
int isEmptyQueue_link(PNode &p)//判断队列是否为空
{
return(p==NULL);
}
void enQueue_link(PNode &p,DateType x)//入队列
{
PNode flag=NULL;//flag 始终指向第一个结点
PNode q=NULL;
if(p==NULL)//创建第一个结点
{if((p=(PNode)malloc(sizeof(struct Node)))==NULL)
printf("空间分配失败!\n");
p->info=x;
p->link=p;//头指针p 始终指向尾结点
flag=p;
}
else //创建其他结点
{ flag=p->link;//在改变头指针指向前使flag始终保持指向首结点
q=p;
if((p=(PNode)malloc(sizeof(struct Node)))==NULL)
printf("空间分配失败!\n");
p->info=x;
q->link=p;
p->link=flag;}
}
void deQueue_link(PNode &p)//出队列
{
PNode q;
if(p==NULL)
printf("队列为空的!\n");
else
if(p->link==p)//只有一个结点的删除处理
{free(p);
p=NULL;}
else //两个或者两个以上结点的时候的删除处理
{ q=p->link;
p->link=p->link->link;
free(q);
}
}
DateType frontQueue_link(PNode &p)//取队列头部元素值
{
if(p==NULL)
{printf("队列是空的!\n");
return 65535;//返回一个特殊值
}
else return(p->link->info);
}
void scan_link(PNode &p)//遍历队列
{
PNode q;
int i=1;
if(p==NULL)
printf("队列是空的!\n");
else
{ for(q=p->link;q!=p;q=q->link)
printf("第%d个元素是 %d\n",i++,q->info);
printf("第%d个元素是 %d\n",i++,q->info);
}
}
//