SingleCircularLinkedListQueue单链循环队列
单链循环队列用单向循环链表实现。
SingleCircularLinkedListQueue.c文件
#include <stdio.h>
#include <malloc.h>
#include "SingleCircularLinkedListQueue.h"
static void clear(SingleCircularLinkedListQueue *This);
static int isEmpty(SingleCircularLinkedListQueue *This);
static int length(SingleCircularLinkedListQueue *This);
static QNode *getHead(SingleCircularLinkedListQueue *This);
static int enQueue(SingleCircularLinkedListQueue *This,QNode *n);
static int deQueue(SingleCircularLinkedListQueue *This,QNode *n);
static int traverse(SingleCircularLinkedListQueue *This,int (*visit)(QNode *n),int circular);
SingleCircularLinkedListQueue *InitSingleCircularLinkedListQueue(){
SingleCircularLinkedListQueue *Q = (SingleCircularLinkedListQueue *)malloc(sizeof(SingleCircularLinkedListQueue));
QNode *p = (QNode *)malloc(sizeof(QNode));
Q->This = p;
Q->front = p;
Q->tear = Q->front;
p->next = p;
Q->clear = clear;
Q->isEmpty = isEmpty;
Q->length = length;
Q->getHead = getHead;
Q->enQueue = enQueue;
Q->deQueue = deQueue;
Q->traverse = traverse;
return Q;
}
void DestroySingleCircularLinkedListQueue(SingleCircularLinkedListQueue *Q){
Q->clear(Q);
free(Q->This);
free(Q);
Q = NULL;
}
static void clear(SingleCircularLinkedListQueue *This){
QNode *head = This->This;
QNode *p = This->This->next;
QNode *temp = NULL;
while(p != head){
temp = p;
p = p->next;
free(temp);
}
p = This->This;
p->next = head;
This->front = p;
This->tear = This->front;
}
static int isEmpty(SingleCircularLinkedListQueue *This){
QNode *p = This->This;
if(p->next == p){
return 0;
}else{
return 1;
}
}
static int length(SingleCircularLinkedListQueue *This){
int j = 0;
QNode *head = This->This;
QNode *p = This->This->next;
while(p != head){
j++;
p = p->next;
}
return j;
}
static QNode *getHead(SingleCircularLinkedListQueue *This){
return This->front->next;
}
static int enQueue(SingleCircularLinkedListQueue *This,QNode *n){
QNode *head = This->This;
if(!n) return -1;
This->tear->next = n;
n->next = head;
This->tear = n;
return 0;
}
static int deQueue(SingleCircularLinkedListQueue *This,QNode *n){
if(This->front == This->tear){
n = NULL;
return -1;
}
QNode *temp = This->front->next;
*n = *(temp);
This->front->next = temp->next;
if(This->tear == temp) This->tear = This->front;
free(temp);
return 0;
}
static int traverse(SingleCircularLinkedListQueue *This,int (*visit)(QNode *n),int circular){
if(This->front == This->tear){
return -1;
}
QNode *head = This->front;
QNode *temp = This->front->next;
if(circular){
while(temp){
if(temp != head){
if(visit(temp) != 0) break;
}
temp = temp->next;
}
}else{
while(temp != head){
if(visit(temp) != 0) break;
temp = temp->next;
}
}
return 0;
}
SingleCircularLinkedListQueue.h文件
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _SINGLECIRCULARLINKEDLISTQUEUE_H
#define _SINGLECIRCULARLINKEDLISTQUEUE_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef struct QElemType{
int id;
char name[20];
}QElemType;
typedef struct QNode{
QElemType elem; //存储空间
struct QNode *next;
}QNode,*Queueptr;
typedef struct SingleCircularLinkedListQueue{
QNode *This;
Queueptr front; //队头
Queueptr tear; //队尾
void (*clear)(struct SingleCircularLinkedListQueue *This);
int (*isEmpty)(struct SingleCircularLinkedListQueue *This);
int (*length)(struct SingleCircularLinkedListQueue *This);
QNode *(*getHead)(struct SingleCircularLinkedListQueue *This);
int (*enQueue)(struct SingleCircularLinkedListQueue *This,QNode *n);
int (*deQueue)(struct SingleCircularLinkedListQueue *This,QNode *n);
int (*traverse)(struct SingleCircularLinkedListQueue *This,int (*visit)(QNode *n),int circular);
}SingleCircularLinkedListQueue;
/* Exported macro ------------------------------------------------------------*/
SingleCircularLinkedListQueue *InitSingleCircularLinkedListQueue();
void DestroySingleCircularLinkedListQueue(SingleCircularLinkedListQueue *Q);
#endif
testSingleCircularLinkedListQueue.c文件
#include <stdio.h>
#include <malloc.h>
#include "SingleCircularLinkedListQueue.h"
char name[][3] = {"xw","xh","xm","xg","xl","xz"};
void strCopy(char *str_a,char *str_b){
while(*str_b != '\0'){
*str_a++ = *str_b++;
}
*str_a = '\0';
}
int printQnode(QNode *node){
printf("id:%d,name:%s\n",node->elem.id,node->elem.name);
return 0;
}
int main(void){
int i;
QNode *node = NULL;
SingleCircularLinkedListQueue *queue = InitSingleCircularLinkedListQueue();
printf("queue is empty:%d\n",queue->isEmpty(queue));
for(i=0;i<6;i++){
node = (QNode *)malloc(sizeof(QNode));
node->elem.id = i;
strCopy(node->elem.name,name[i]);
queue->enQueue(queue,node);
}
queue->traverse(queue,printQnode,0);
printf("queue is empty:%d\n",queue->isEmpty(queue));
printf("queue length:%d\n",queue->length(queue));
while(queue->length(queue)){
node = queue->getHead(queue);
printf("present client: id=%d, name=%s\n",node->elem.id,node->elem.name);
node = (QNode *)malloc(sizeof(QNode));
queue->deQueue(queue,node);
printf("client :id=%d,name=%s finish!\n",node->elem.id,node->elem.name);
free(node);
node = NULL;
}
queue->clear(queue);
for (i = 10; i < 16; i++){
node = (QNode *)malloc(sizeof(QNode));
node->elem.id = i;
strCopy(node->elem.name,name[i-10]);
queue->enQueue(queue,node);
}
queue->traverse(queue,printQnode,1);
DestroySingleCircularLinkedListQueue(queue);
return 0;
}
编译：
gcc SingleCircularLinkedListQueue.c SingleCircularLinkedListQueue.h testSingleCircularLinkedListQueue.c -o testSingleCircularLinkedListQueue
运行testSingleCircularLinkedListQueue：
queue is empty:0
id:0,name:xw
id:1,name:xh
id:2,name:xm
id:3,name:xg
id:4,name:xl
id:5,name:xz
queue is empty:1
queue length:6
present client: id=0, name=xw
client :id=0,name=xw finish!
present client: id=1, name=xh
client :id=1,name=xh finish!
present client: id=2, name=xm
client :id=2,name=xm finish!
present client: id=3, name=xg
client :id=3,name=xg finish!
present client: id=4, name=xl
client :id=4,name=xl finish!
present client: id=5, name=xz
client :id=5,name=xz finish!
id:10,name:xw
id:11,name:xh
id:12,name:xm
id:13,name:xg
id:14,name:xl
id:15,name:xz
id:10,name:xw
id:11,name:xh
id:12,name:xm
id:13,name:xg
id:14,name:xl
id:15,name:xz
id:10,name:xw
id:11,name:xh
id:12,name:xm
id:13,name:xg
id:14,name:xl
id:15,name:xz
id:10,name:xw
id:11,name:xh
id:12,name:xm
id:13,name:xg
...
queue->traverse(queue,printQnode,0);
int circular = 0 表示队列只从头到尾遍历Qnode一遍；
int circular = 1 表示队列循环遍历Qnode，所以上面程序运行最后进入循环，不断遍历Qnode。
在实现的visit函数中，返回值如果不为0则退出遍历。
上述代码实现的visit函数为printQnode，返回值为0；
