湖北网站制作公司,建设网站企业邮箱,绵阳网络推广公司,网站互动推广1. 背景说明 队列(queue)是一种先进先出(first in first out,缩为 FIFO)的线性表。它只允许在表的一端进行插入#xff0c;而在另一端删除元素。 2. 示例代码 1#xff09;status.h
/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H/* 函数结果…1. 背景说明 队列(queue)是一种先进先出(first in first out,缩为 FIFO)的线性表。它只允许在表的一端进行插入而在另一端删除元素。 2. 示例代码 1status.h
/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H/* 函数结果状态码 */
#define TRUE 1 /* 返回值为真 */
#define FALSE 0 /* 返回值为假 */
#define RET_OK 0 /* 返回值正确 */
#define INFEASIABLE 2 /* 返回值未知 */
#define ERR_MEMORY 3 /* 访问内存错 */
#define ERR_NULL_PTR 4 /* 空指针错误 */
#define ERR_MEMORY_ALLOCATE 5 /* 内存分配错 */
#define ERR_NULL_STACK 6 /* 栈元素为空 */
#define ERR_PARA 7 /* 函数参数错 */
#define ERR_OPEN_FILE 8 /* 打开文件错 */
#define ERR_NULL_QUEUE 9 /* 队列为空错 */
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码如 OK 等 */
typedef int Bollean; /* Boolean 是布尔类型,其值是 TRUE 或 FALSE */#endif // !STATUS_H 2) linkQueue.h
/* 单链队列 —— 队列的链式存储结构头文件 */#ifndef LINKQUEUE_H
#define LINKQUEUE_H#include status.htypedef int QElemType;typedef struct QNode {QElemType data;struct QNode *next;
} QNode, *QueuePtr;typedef struct {QueuePtr front, rear;
} LinkQueue;/* 构造一个空队列 Q */
Status InitQueue(LinkQueue *Q);/* 销毁队列 Q(无论空否均可) */
Status DestroyQueue(LinkQueue *Q);/* 将 Q 清为空队列 */
Status ClearQueue(LinkQueue *Q);/* 若 Q 为空队列,则返回 TRUE,否则返回 FALSE */
Bollean QueueEmpty(const LinkQueue *Q);/* 求队列的长度 */
int QueueLength(LinkQueue *Q);/* 若队列不空,则用 e 返回 Q 的队头元素,并返回 OK, 否则返回 ERROR */
Status GetQueueHead(const LinkQueue *Q, QElemType *e);/* 插入元素 e 为 Q 的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e);/* 若队列不空,删除 Q 的队头元素,用 e 返回其值,并返回 OK, 否则返回 ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e);/* 从队头到队尾依次对队列 Q 中每个元素调用函数 vi() */
Status QueueTraverse(const LinkQueue *Q, void(*vi)(QElemType));#endif // !LINKQUEUE_H3) linkQueue.c
/* 单链队列 —— 队列的链式存储结构源文件 */#include linkQueue.h
#include stdio.h
#include stdlib.h/* 构造一个空队列 Q */
Status InitQueue(LinkQueue *Q)
{Q-front Q-rear (QueuePtr)malloc(sizeof(QNode));if (!Q-front) {printf(FuncName: %-15s Line: %-5d ErrorCode: %-3d\n, __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}Q-front-next NULL;return RET_OK;
}/* 销毁队列 Q(无论空否均可) */
Status DestroyQueue(LinkQueue *Q)
{while (Q-front) {Q-rear Q-front-next;free(Q-front);Q-front Q-rear;}return RET_OK;
}/* 将 Q 清为空队列 */
Status ClearQueue(LinkQueue *Q)
{Q-rear Q-front;QueuePtr p Q-front-next;Q-front-next NULL;QueuePtr q NULL;while (p) {q p;p p-next;free(q);}return RET_OK;
}/* 若 Q 为空队列,则返回 TRUE,否则返回 FALSE */
Bollean QueueEmpty(const LinkQueue *Q)
{return (Q-front Q-rear) ? TRUE : FALSE;
}/* 求队列的长度 */
int QueueLength(LinkQueue *Q)
{int length 0;QueuePtr p Q-front;while (p ! Q-rear) {length;p p-next;}return length;
}/* 若队列不空,则用 e 返回 Q 的队头元素(队头元素为 front 的下一个元素), 并返回 OK, 否则返回 ERROR */
Status GetQueueHead(const LinkQueue *Q, QElemType *e)
{if (Q-front Q-rear) {printf(FuncName: %-15s Line: %-5d ErrorCode: %-3d\n, __func__, __LINE__, ERR_NULL_QUEUE);return ERR_NULL_QUEUE;}*e Q-front-next-data;return RET_OK;
}static QueuePtr MakeNewQueueNode(QElemType e)
{QueuePtr p (QueuePtr)malloc(sizeof(QNode));if (!p) {printf(FuncName: %-15s Line: %-5d ErrorCode: %-3d\n, __func__, __LINE__, ERR_MEMORY_ALLOCATE);return NULL;}p-data e;p-next NULL;return p;
}/* 插入元素 e 为 Q 的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e)
{QueuePtr p MakeNewQueueNode(e);if (p NULL) {printf(FuncName: %-15s Line: %-5d ErrorCode: %-3d\n, __func__, __LINE__, ERR_NULL_PTR);return ERR_NULL_PTR;}Q-rear-next p;Q-rear p;return RET_OK;
}/* 若队列不空,删除 Q 的队头元素,用 e 返回其值,并返回 OK, 否则返回 ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e)
{if (Q-front Q-rear) {printf(FuncName: %-15s Line: %-5d ErrorCode: %-3d\n, __func__, __LINE__, ERR_NULL_QUEUE);return ERR_NULL_QUEUE;}QueuePtr p Q-front-next;*e p-data;Q-front-next p-next;if (Q-rear p) {Q-rear Q-front;}free(p);return RET_OK;
}/* 从队头到队尾依次对队列 Q 中每个元素调用函数 vi() */
Status QueueTraverse(const LinkQueue *Q, void(*vi)(QElemType))
{QueuePtr p Q-front-next;while (p) {vi(p-data);p p-next;}return RET_OK;
} 4) auxiliary.h
/* 辅助函数头文件 */#ifndef AUXILIARY_H
#define AUXILIARY_H#include linkQueue.h/* 打印栈元素 */
void Print(QElemType e);#endif // !AUXILIARY_H 5) auxiliary.c
/* 辅助函数实现源文件 */#include auxiliary.h
#include stdio.h/* 打印栈元素 */
void Print(QElemType e)
{printf(%d , e);
} 6) main.c
/* 入口程序源文件 */#include status.h
#include auxiliary.h
#include linkQueue.h
#include stdio.hint main(void)
{LinkQueue Q;Status ret InitQueue(Q);if (ret RET_OK) {printf(Initialize queue success!\n);}printf(The queue is %s\n, (QueueEmpty(Q) TRUE) ? empty : not empty);printf(The length of the queue is %d\n, QueueLength(Q));EnQueue(Q, -5);EnQueue(Q, 5);EnQueue(Q, 10);printf(After insert 3 elements, the length of the queue is %d\n, QueueLength(Q));printf(The queue is %s\n, (QueueEmpty(Q) TRUE) ? empty : not empty);printf(The elements of the queue is: );QueueTraverse(Q, Print);printf(\n);QElemType e;ret GetQueueHead(Q, e);if (ret RET_OK) {printf(The element of the head of the queue is %d\n, e);}DeQueue(Q, e);printf(Delete the element of the head of the queue %d\n, e);ret GetQueueHead(Q, e);if (ret RET_OK) {printf(The new element of the head of the queue is %d\n, e);}ClearQueue(Q);printf(After clear the queue, Q.front %p, Q.rear %p, Q.front-next %p\n,Q.front, Q.rear, Q.front-next);DestroyQueue(Q);printf(After destroy the queue, Q.front %p, Q.rear %p\n, Q.front, Q.rear);return 0;
} 3. 输出示例 注意free() 函数的作用并不仅仅把内存释放还将指针置为空。
