本文共 6869 字,大约阅读时间需要 22 分钟。
队列:具有一定操作约束的线性表;只能在一端插入,在另一端删除;先进先出:First In First Out(FIFO)。
/* 定义队列的基本数据结果 */#define MaxSize 20typedef int ElementType;typedef struct _Queue{ ElementType Data[ MaxSize ]; int rear; int front;} Queue;
/* 创建一个空队列 */Queue *CreatQueue(){ Queue *Q = (Queue*)malloc(sizeof(Queue)); if(NULL != Q) { Q->front = 0; Q->rear = 0; } return Q;}
/* 向循环队列尾部插入一个元素 */void AddQ( Queue *PtrQ, ElementType item){ if ( IsFullQ(PtrQ) ) { printf("The queue is full!\n"); return; } PtrQ->rear = (PtrQ->rear+1)% MaxSize; PtrQ->Data[PtrQ->rear] = item;}
/* 删除循环队列的队头的元素 */ElementType DeleteQ ( Queue *PtrQ ){ if ( IsEmptyQ(PtrQ) ) { printf("The queue is empty!\n"); return -1; } else { PtrQ->front = (PtrQ->front+1)% MaxSize; return PtrQ->Data[PtrQ->front]; }}
/* 循环队列的顺序存储实现 */#include#include /* 定义队列的基本数据结果 */#define MaxSize 20typedef int ElementType;typedef struct _Queue{ ElementType Data[ MaxSize ]; int rear; int front;} Queue;/* 创建一个空队列 */Queue *CreatQueue(){ Queue *Q = (Queue*)malloc(sizeof(Queue)); if(NULL != Q) { Q->front = 0; Q->rear = 0; } return Q;}/* 消除一个队列 */void DestroyQueue(Queue *PtrQ){ if(NULL != PtrQ) free(PtrQ); PtrQ = NULL;}/* 判断队列是否为空,1为空,0非空 */int IsEmptyQ( Queue *PtrQ ){ return (PtrQ->front == PtrQ->rear);}/* 判断队列是否为满,1为满,0为空 */int IsFullQ( Queue *PtrQ ){ return ((PtrQ->rear+1)%MaxSize == PtrQ->front);}/* 向循环队列尾部插入一个元素 */void AddQ( Queue *PtrQ, ElementType item){ if ( IsFullQ(PtrQ) ) { printf("The queue is full!\n"); return; } PtrQ->rear = (PtrQ->rear+1)% MaxSize; PtrQ->Data[PtrQ->rear] = item;}/* 删除循环队列的队头的元素 */ElementType DeleteQ ( Queue *PtrQ ){ if ( IsEmptyQ(PtrQ) ) { printf("The queue is empty!\n"); return -1; } else { PtrQ->front = (PtrQ->front+1)% MaxSize; return PtrQ->Data[PtrQ->front]; }}/* 遍历一个循环队列 */void TraversalQ( Queue *PtrQ ){ int front, rear, i; if(!IsEmptyQ(PtrQ)) { front = PtrQ->front; rear = PtrQ->rear; for(i = front; i != rear; i = (i+1)%MaxSize) printf("%d ", PtrQ->Data[(i+1)%MaxSize]); printf("\n"); }}/* 程序入口 */int main(){ int i; ElementType temp; Queue *queue = NULL; /* 创建一个循环队列 */ queue = CreatQueue(); if(NULL == queue) { printf("CreatQueue is failed!\n"); return -1; } /* 向循环队列中插入五个元素 */ printf("Input 5 numbers : "); for(i = 0; i < 5; i++) { scanf("%d", &temp); AddQ(queue, temp); } printf("****************************************TraversalQ*******************************\n"); TraversalQ(queue); printf("****************************************AddQ once********************************\n"); printf("Input 1 number : "); scanf("%d", &temp); AddQ(queue, temp); TraversalQ(queue); printf("****************************************DeleteQ twice****************************\n"); DeleteQ(queue); DeleteQ(queue); TraversalQ(queue); DestroyQueue(queue); // 销毁一个循环队列 return 0;}
/* 定义链式队列的基本数据结构 */typedef int ElementType;typedef struct Node{ ElementType Data; struct Node *Next;}QNode;typedef struct { /* 链队列结构 */ QNode *rear; /* 指向队尾结点 */ QNode *front; /* 指向队头结点 */} LinkQueue;
/* 创建一个空队列 */LinkQueue *CreatQueue(){ LinkQueue *Q = (LinkQueue *)malloc(sizeof(LinkQueue)); if(NULL != Q) { Q->front = NULL; Q->rear = NULL; } return Q;}
/* 向队列尾部插入一个元素 */void AddQ( LinkQueue *PtrQ, ElementType item){ QNode *TempCell = NULL; TempCell = (QNode*)malloc(sizeof(QNode)); if(NULL == TempCell) { printf("Malloc is failed!\n"); return; } TempCell->Data = item; // 赋值给分配的结点 if ( IsEmptyQ(PtrQ) ) // 判断队列是否为空 { PtrQ->rear = PtrQ->front= TempCell; TempCell->Next = NULL; } else { PtrQ->rear->Next = TempCell; TempCell->Next = NULL; PtrQ->rear = TempCell; }}
/* 从队列头部删除一个元素 */ElementType DeleteQ ( LinkQueue *PtrQ ){ QNode *FrontCell; ElementType FrontElem; if ( IsEmptyQ(PtrQ) ) { printf("The link queue is empty!\n"); return -1; } FrontCell = PtrQ->front; if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */ PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */ else PtrQ->front = PtrQ->front->Next; FrontElem = FrontCell->Data; free( FrontCell ); /* 释放被删除结点空间 */ return FrontElem;}
/* 队列的链式存储实现 */#include#include /* 定义链式队列的基本数据结构 */typedef int ElementType;typedef struct Node{ ElementType Data; struct Node *Next;}QNode;typedef struct { /* 链队列结构 */ QNode *rear; /* 指向队尾结点 */ QNode *front; /* 指向队头结点 */} LinkQueue;/* 创建一个空队列 */LinkQueue *CreatQueue(){ LinkQueue *Q = (LinkQueue *)malloc(sizeof(LinkQueue)); if(NULL != Q) { Q->front = NULL; Q->rear = NULL; } return Q;}/* 消除一个队列 */void DestroyQueue(LinkQueue *PtrQ){ while(!IsEmptyQ(PtrQ)) { DeleteQ(PtrQ); } free(PtrQ); PtrQ = NULL;}/* 判断队列是否为空,1为空,0非空 */int IsEmptyQ( LinkQueue *PtrQ ){ return (PtrQ->front == NULL);}/* 向队列尾部插入一个元素 */void AddQ( LinkQueue *PtrQ, ElementType item){ QNode *TempCell = NULL; TempCell = (QNode*)malloc(sizeof(QNode)); if(NULL == TempCell) { printf("Malloc is failed!\n"); return; } TempCell->Data = item; // 赋值给分配的结点 if ( IsEmptyQ(PtrQ) ) // 判断队列是否为空 { PtrQ->rear = PtrQ->front= TempCell; TempCell->Next = NULL; } else { PtrQ->rear->Next = TempCell; TempCell->Next = NULL; PtrQ->rear = TempCell; }}/* 从队列头部删除一个元素 */ElementType DeleteQ ( LinkQueue *PtrQ ){ QNode *FrontCell; ElementType FrontElem; if ( IsEmptyQ(PtrQ) ) { printf("The link queue is empty!\n"); return -1; } FrontCell = PtrQ->front; if ( PtrQ->front == PtrQ->rear) /* 若队列只有一个元素 */ PtrQ->front = PtrQ->rear = NULL; /* 删除后队列置为空 */ else PtrQ->front = PtrQ->front->Next; FrontElem = FrontCell->Data; free( FrontCell ); /* 释放被删除结点空间 */ return FrontElem;}/* 遍历一个队列 */void TraversalQ( LinkQueue *PtrQ ){ QNode *FrontCell; QNode *RearCell; if(!IsEmptyQ(PtrQ)) { FrontCell = PtrQ->front; RearCell = PtrQ->rear; while(FrontCell != RearCell) // 把前面n-1个结点元素值打印出来 { printf("%d ", FrontCell->Data); FrontCell = FrontCell->Next; } printf("%d ", RearCell->Data); // 把最后一个结点元素值打印出来 printf("\n"); }}/* 程序入口 */int main(){ int i; ElementType temp; LinkQueue *queue = NULL; /* 创建一个循环队列 */ queue = CreatQueue(); if(NULL == queue) { printf("CreatQueue is failed!\n"); return -1; } /* 向循环队列中插入五个元素 */ printf("Input 5 numbers : "); for(i = 0; i < 5; i++) { scanf("%d", &temp); AddQ(queue, temp); } printf("****************************************TraversalQ*******************************\n"); TraversalQ(queue); printf("****************************************AddQ once********************************\n"); printf("Input 1 number : "); scanf("%d", &temp); AddQ(queue, temp); TraversalQ(queue); printf("****************************************DeleteQ twice****************************\n"); DeleteQ(queue); DeleteQ(queue); TraversalQ(queue); DestroyQueue(queue); // 销毁一个队列 return 0;}
转载地址:http://qlgoi.baihongyu.com/