1.1 linkqueue.h
#ifndef LINKQUEUE_H #define LINKQUEUE_H #include <stdio.h> #include <malloc.h> typedef enum { OK=0, //正确 ERROR=1, //出错 TRUE=2, //为真 FALSE=3 //为假 }status; typedef int ElemType; //宏定义队列的数据类型 /* 链式队列：是指采用链式存储结构的队列，队列中每一个元素对应链表中的结点。 * 和链式栈类似，一般采用单链表来实现链式队列。 *************************************************************/ // 链式队列结点结构 typedef struct Node { ElemType data; //结点数据 //【负责建立队列各结点之间的联系，前一个结点的next指向后一个结点，形成链式队列】 struct Node *next; //后继结点 }LQNode; // 链式队列结构 typedef struct { LQNode *front; //链式队列的队头指针，总是指向队列的头结点(出队一次，第二个结点变为头结点) LQNode *rear; //链式队列的队尾指针，入队时指向新插入结点(总是指向队列的最后一个结点) }LinkQueue; //创建空队列 status initQueue(LinkQueue *pQHead); //销毁队列 void destroyQueue(LinkQueue *pQHead); //清空队列 void clearQueue(LinkQueue *pQHead); //判断队列是否为空 status isEmpityQueue(LinkQueue *pQHead); //获得队列长度 int getQueueLen(LinkQueue *pQHead); //新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素 status enQueue(LinkQueue *pQHead,ElemType element); //新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除] status deQueue(LinkQueue *pQHead,ElemType *pElement); //遍历队列 void queueTraverse(LinkQueue *pQHead); #endif // LINKQUEUE_H
1.2 linkqueue.c
#include "linkqueue.h" /********************************************************************* * 刚开始创建空队列时，队列的队头和队尾指针相等都指向头结点，头结点的数据域不存放数据 * 第一次入队，创建新结点，其数据域保存新插入元素，头结点的next指向新结点, * 并且队列的队尾指针指向新结点,队列的队头指针仍然指向头结点,依次类推 * 第一次出队，则队列的队头指针指向头结点的next,依次类推 *********************************************************************/ //创建空队列： pQHead即为队列头结点 status initQueue(LinkQueue *pQHead) { //队列头结点的队头和队尾指针申请内存 pQHead->front = pQHead->rear = (LQNode*)malloc(sizeof(LQNode)); if(!pQHead->front) //检测是否申请失败 { printf("pQHead->front malloc error! "); return ERROR; } //设置头结点指针域为空 pQHead->front->next = NULL; return OK; } //销毁队列 void destroyQueue(LinkQueue *pQHead) { free(pQHead->front); free(pQHead->rear); pQHead->front = pQHead->rear = NULL; } //清空队列 void clearQueue(LinkQueue *pQHead) { pQHead->front = pQHead->rear; } //判断队列是否为空 status isEmpityQueue(LinkQueue *pQHead) { //队头指针与队尾指针相等，说明队列为空 if(pQHead->front == pQHead->rear) return TRUE; return FALSE; } //获得队列长度 int getQueueLen(LinkQueue *pQHead) { LQNode *temp = pQHead->front; int length = 0; while(temp != pQHead->rear) { ++length; temp = temp->next; } return length; } //新元素入队:即链式队列的尾结点指针，指向存放新元素的新结点 status enQueue(LinkQueue *pQHead, ElemType element) { //创建新结点,并申请内存 LQNode *temp = (LQNode*)malloc(sizeof(LQNode)); if(!temp) { printf("temp malloc error! "); return ERROR; } temp->data = element; //将要插入元素存入新结点的数据域内 temp->next = NULL; //队列只能从队尾插入所以下一个结点初始化为NULL //链式队列元素为结点(LQNode) //pQHead->rear为队列的最后一个结点，当插入新结点temp时,pQHead->rear->next = temp //使前一个结点的next指向新结点，建立队列各结点之间的联系 pQHead->rear->next = temp; //将队尾结点的后继指针指向新结点,如果第一次入队， //则pQueue->rear->next相当于pQueue->front->next // pQHead->rear总是指向队列的最后一个结点 pQHead->rear = temp; //将队尾结点的指针指向新结点temp,temp变为最后一个结点 return OK; } status deQueue(LinkQueue *pQHead,ElemType *pElement) { //如果队列为空,则返回ERRIR if(isEmpityQueue(pQHead)==TRUE) { printf("queue is NULL! "); return ERROR; } //值入队一次后就出队，则pQueue->front->next==pQHead->rear->next,为第一个插入的结点 LQNode *temp = pQHead->front->next; //初始化temp为要出队的结点的指针 //如果要出队的结点为最后一个结点,使q->rear指向头结点防止出现悬空的指针 if(pQHead->front->next == pQHead->rear) pQHead->rear = pQHead->front; *pElement = temp->data; //将出队的数据元素存入*e pQHead->front->next = temp->next; //使下一个结点成为队头,如果没有下一个结点则为NULL free(temp); //删除要出队的结点 temp = NULL; return OK; } //遍历队列 void queueTraverse(LinkQueue *pQHead) { //如果队列为空 if(isEmpityQueue(pQHead)==TRUE) { printf(" queue is NULL! "); } LQNode *temp = pQHead->front; printf("将队列中的所有元素出队: "); while(temp != pQHead->rear) { temp = temp->next; printf("%d ", temp->data); } printf(" "); }
1.3 main.c
/********************************************* * C实现链式队列 2017/10/26 by nieXianFeng *********************************************/ #include <stdio.h> #include "linkqueue.h" int main() { int value; //用于保存出队的元素 //给头结点申请内存 LinkQueue *pQHead= (LinkQueue*)malloc(sizeof(LinkQueue)); if(!pQHead) //检测是否申请失败 { printf("pQHead malloc error! "); return ERROR; } //调用初始化队列的函数 initQueue(pQHead); //调用出队函数 enQueue(pQHead, 1); enQueue(pQHead, 2); enQueue(pQHead, 3); enQueue(pQHead, 4); enQueue(pQHead, 5); enQueue(pQHead, 6); enQueue(pQHead, 7); enQueue(pQHead, 8); //调用遍历队列的函数 queueTraverse(pQHead); //调用出队函数 if(deQueue(pQHead, &value)==OK) { printf("出队一次，元素为：%d ", value); } queueTraverse(pQHead); if(deQueue(pQHead, &value)==OK) { printf("出队一次，元素为：%d ", value); } queueTraverse(pQHead); printf("队列长度是%d ",getQueueLen(pQHead)); clearQueue(pQHead); //清空队列 queueTraverse(pQHead); free(pQHead); pQHead = NULL; return 0; }