数据结构算法-习题-答案-带头结点的循环链表表示队列-并且只设一个指针指向队尾元素结点(注意不设头指针).docx

数据结构算法题(假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针)试编写相应的队列初始化,入队列和出队列的算法!) (提供两种答案哦！！！)
一：
//既然是算法 就不用源码了 具体看注释
typedef int Datatype;

typedef struct queuenode
{
Datatype data;
struct queuenode *next;
}QueueNode; //以上是结点类型的定义

typedef struct
{
queuenode rear;
}LinkQueue; //只设一个指向队尾元素的指针

void InitQueue( LinkQueue &Q)
{
//置空队：就是使头结点成为队尾元素
Q.rear=(queuenode*)malloc(sizeof(queuenode))
QueueNode* s;
Q->rear = Q->rear->next;//将队尾指针指向头结点
while(Q->rear!=Q->rear->next) //当队列非空，将队中元素逐个出队
　　　　{
s=Q->rear->next;
Q->rear->next=s->next;
free(s);
} //回收结点空间
}

int EmptyQueue( LinkQueue &Q)
{ //判队空
//当头结点的next指针指向自己时为空队
return Q->rear->next->next==Q->rear->next;
}

void EnQueue( LinkQueue &Q, Datatype x)
{ //入队
//也就是在尾结点处插入元素
QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点
p->data=x; p->next=Q->rear->next;//初始化新结点并链入
Q-rear->next=p;
Q->rear=p;//将尾指针移至新结点
}

Datatype DeQueue( LinkQueue &Q,Datatype &x)
{
//出队,把头结点之后的元素摘下
Datatype t;
QueueNode *p;
if(EmptyQueue( Q ))
Error("Queue underflow");
p=Q->rear->next->next; //p指向将要摘下的结点
x=p->data; //保存结点中数据
if (p==Q->rear)
{ //当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点
Q->rear = Q->rear->next; Q->rear->next=p->next;
}
else
Q->rear->next->next=p->next;//摘下结点p
free(p);//释放被删结点
return x;
}

二：
typedef struct Node
{
 int data;
 struct Node *next;
}Node,*CiLNode;
typedef struct
{
 CiLNode CiLrear;
}CiQueue;

void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q
{
  Q=(CiLNode*)malloc(sizeof(CiLNode));
  Q->next=Q;
}//InitCiQueue

void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素
{
  p=(CiLNode*)malloc(sizeof(CiLNode));
  p->data=x;
  p->next=Q->next; //直接把p加在Q的后面
  Q->next=p;
  Q=p;  //修改尾指针
}

Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x
{
  if(Q==Q->next) return INFEASIBLE; //队列已空
  p=Q->next->next;
  x=p->data;
  Q->next->next=p->next;
  free(p);
  return OK;
}//DeCiQueue