#include#include #include #include #include using namespace std;typedef unsigned char uint8;typedef unsigned short uint16;typedef unsigned int uint32;typedef int DataType; //类型定义typedef struct _QueueNode{ DataType dt; _QueueNode *next;}QueueNode;typedef struct _LinkedQueue{ QueueNode *first; QueueNode *rear;}LinkedQueue;/******************************************************************************** 函数名称:CreateLinkedQueue* 函数功能:创建一个队列* 输入参数:无* 输出参数:无* 返 回 值: LinkedQueue指针*******************************************************************************/LinkedQueue *CreateLinkedQueue(void){ LinkedQueue *lq = (LinkedQueue*)malloc(sizeof(LinkedQueue)); lq->first = NULL; lq->rear = NULL; return lq;}/******************************************************************************** 函数名称:AddNodeLinkedQueue* 函数功能:（入队）在队列尾添加一个节点* 输入参数:LinkedQueue **lq, DataType dt* 输出参数:无* 返 回 值: >0 入队成功 <0 入队失败*******************************************************************************/int AddNodeLinkedQueue(LinkedQueue **lq, DataType dt){ if(NULL == *lq) return -1; if(NULL == (*lq)->first) { QueueNode *qn = (QueueNode*)malloc(sizeof(QueueNode)); qn->next = NULL; memcpy((uint8 *)&(qn->dt),(uint8 *)&dt, sizeof(DataType)); (*lq)->first = qn; (*lq)->rear = qn; return 1; } QueueNode *qn = (QueueNode*)malloc(sizeof(QueueNode)); qn->next = NULL; memcpy((uint8 *)&(qn->dt),(uint8 *)&dt, sizeof(DataType)); qn->next = (*lq)->rear; (*lq)->rear = qn; return 2;}/******************************************************************************** 函数名称:VisitAllNodeLinkedQueue* 函数功能:遍历整个队列* 输入参数:LinkedQueue *lq* 输出参数:无* 返 回 值: 无*******************************************************************************/void VisitAllNodeLinkedQueue(LinkedQueue *lq){ if(NULL == lq) return; QueueNode *qn = lq->rear; printf("["); while(NULL != qn) { printf("%d",qn->dt); qn = qn->next; if(NULL != qn) printf(","); } printf("]\n");}/******************************************************************************** 函数名称:GetRearLinkedQueue* 函数功能:取得队尾，但不删除节点* 输入参数:LinkedQueue *lq* 输出参数:QueueNode **node* 返 回 值: >0成功，<0失败*******************************************************************************/int GetRearLinkedQueue(LinkedQueue *lq, QueueNode **node){ if(NULL == lq || NULL == lq->rear) return -1; *node = lq->rear; return 1;}/******************************************************************************** 函数名称:GetFirstLinkedQueue* 函数功能:取得队头，但不删除节点* 输入参数:LinkedQueue *lq* 输出参数:QueueNode **node* 返 回 值: >0成功，<0失败*******************************************************************************/int GetFirstLinkedQueue(LinkedQueue *lq, QueueNode **node){ if(NULL == lq || NULL == lq->rear) return -1; *node = lq->first; return 1;}/******************************************************************************** 函数名称:RemoveFirstLinkedQueue* 函数功能:出队，删除节点* 输入参数:LinkedQueue **lq* 输出参数:LinkedQueue **lq* 返 回 值: >0 出队成功 <0 出队失败*******************************************************************************/int RemoveFirstLinkedQueue(LinkedQueue **lq){ if(NULL == (*lq) || NULL == (*lq)->rear) return -1; QueueNode *pre_node = (*lq)->rear; QueueNode *curr_node = (*lq)->rear; QueueNode *head_node = (*lq)->rear; while(NULL != curr_node->next) { pre_node = curr_node; curr_node = curr_node->next; } if(pre_node == curr_node) { memset((uint8 *)&(curr_node->dt), 0x00, sizeof(DataType)); free(curr_node); curr_node = NULL; (*lq)->rear = NULL; (*lq)->first = NULL; return 1; } memset((uint8 *)&(curr_node), 0x00, sizeof(DataType)); free(curr_node); curr_node = NULL; (*lq)->first = pre_node; (*lq)->first->next = NULL; return 2;}/******************************************************************************** 函数名称:GetLenLinkedQueue* 函数功能:取得队列长度* 输入参数:LinkedQueue **lq* 输出参数:无* 返 回 值: 长度*******************************************************************************/int GetLenLinkedQueue(LinkedQueue *lq){ if(NULL == lq || NULL == lq->rear) return 0; QueueNode *qn = lq->rear; int len = 0; while(NULL != qn) { qn = qn->next; len++; } return len;}int main(){ LinkedQueue *lq = CreateLinkedQueue(); QueueNode *qn = NULL; AddNodeLinkedQueue(&lq, 1); AddNodeLinkedQueue(&lq, 2); //AddNodeLinkedQueue(&lq, 3); //AddNodeLinkedQueue(&lq, 4); VisitAllNodeLinkedQueue(lq); printf("queue first: %d\n",GetFirstLinkedQueue(lq,&qn)>0?qn->dt:-1); printf("queue rear: %d\n",GetRearLinkedQueue(lq,&qn)>0?qn->dt:-1); RemoveFirstLinkedQueue(&lq); VisitAllNodeLinkedQueue(lq); printf("queue first: %d\n",GetFirstLinkedQueue(lq,&qn)>0?qn->dt:-1); printf("queue rear: %d\n",GetRearLinkedQueue(lq,&qn)>0?qn->dt:-1); printf("queue len : %d\n",GetLenLinkedQueue(lq)); return 1;}