luzhijian.cpp

一个单列表的循环例子

//用循环单链表实现队列的基本操作
//算法的实现：
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

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注意：输入整数后请回车\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);
	}
}
//