C封装单链循环队列对象

SingleCircularLinkedListQueue单链循环队列

单链循环队列用单向循环链表实现。
github源码

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；