循环链表--链队

   链对：是采用链式存储的队列，它有点类似于单链表，但是其操作受到限制，只允许在表头删除节点和在表尾插入节点。

   在单链表中最重要的一个参数是头指针，而在链对列中，还需要有个尾指针。为了方便运算，还增加了一个对头节点，即第一个有效节点，头节点后的第一个节点。

 

typedef int datatype;
typedef int* pdatatype;

typedef struct _Linklist
{
 datatype data;
 struct _Linklist *next;
}Linklist, *pLinklist;

 

typedef struct _linkqueue

{

    pLinklist front;  //指向头节点。它后面指向对头节点

    pLinklist rear;   //指向对尾节点。

}linkqueue, *plinkqueue;

 

1. 置空队

 

置空队就是建立一个头节点，并把头尾指针都指向头节点。注意：头节点是不存放数据的。

void SetNull(pLinkqueue q)
{
 q->front = (pLinklist)malloc(sizeof(Linklist));
 q->front->next = NULL;
 q->rear = q->front;
}

 

2. 判断空

当头指针等于尾指针时，对空。

int Empty(pLinkqueue q)
{
 if (q->front == q->rear)
 {
  return 1;
 }
 else
 {
  return 0;
 }
}

 

3. 入队

入队时，将新的节点插入到链队列的尾部，同时将尾指针指向这个节点。

void InQueue(pLinkqueue q, datatype x)
{
 q->rear->next = (pLinklist)malloc(sizeof(Linklist));
 if (q->rear->next != NULL)
 {
  q->rear = q->rear->next;
  q->rear->data = x;
  q->rear->next = NULL;
 }
}

 

4. 出队

如果出对时，删除的是对头节点，要注意对列的长度大于1还是等于1的情况，这个时候要注意尾指针的修改，如果等于1，则要删除尾指针指向的节点。如果删除的是头节点。

如果删除头节点就么有这个问题。

下面是删除头节点的实现：

datatype DeleteQueue(pLinkqueue q)
{
 pLinklist s;
 if (Empty(q))
 {
  printf("The queue is empty");
  return NULL;
 }

 s = q->front;
 q->front = q->front->next;
 free(s);
 return q->front->data;
}

 

总结：对于对列而言，Linklist定义的是其中的一个节点。而一个头节点就可以代表一个对列。对于链对而言，Linkqueue中包含两个变量：一个头指针，一个尾指针。

对于顺序队列和链对而言，它们判断空，出队，入队方法都一样。