队列-数据结构 C语言.ppt

队列 队列的定义 前面所讲的栈是一种后进先出的数据结构，而在实际问题中还经常使用一种“先进先出” (FIFO---First In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。如图3.11 所示是一个有5 个元素的队列。入队的顺序依次为a1、a2 、a3 、a4 、a5 ，出队时的顺序将依然是a1、a2 、a3 、a4 、a5 。 显然，队列也是一种运算受限制的线性表，所以又叫先进先出表。在日常生活中队列的例子很多，如排队买东西，排头的买完后走掉，新来的排在队尾。在队列上进行的基本操作有： 链队列 链队列的实现 typedef int QElemType; typedef int Status; typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QNodePtr; typedef struct{ QNodePtr front; QNodePtr rear; }LinkQueue; 队列的数据类型定义 【LinkQueue.c】链队列的实现 文件包含 #define OK 1 #define ERROR 0 #define OVERFLOW -1 宏定义 #include stdio.h #include stdlib.h 构造一个空队列Q Status InitQueue(LinkQueue *Q){ (*Q).front=(*Q).rear=(QNodePtr)malloc(sizeof(QNode)); if(!(*Q).front)exit(OVERFLOW); (*Q).front-next=NULL; return OK; } 销毁队列Q Status DestroyQueue(LinkQueue *Q){ while((*Q).front){ (*Q).rear=(*Q).front-next; free((*Q).front); (*Q).front=(*Q).rear; } return OK; } 判断是否为空队列 Status QueueEmpty(LinkQueue Q){ return Q.front==Q.rear; } 返回队列的长度 int QueueLength (LinkQueue Q){ int len=0; QNodePtr p; p=Q.front-next; while(p){ len++; p=p-next; } return len; } Status GetHead(LinkQueue Q,QElemType *e){ if(!QueueEmpty(Q)){ *e=Q.front-next-data; return OK; }else{ return ERROR; } } 获取队列首元素 Status EnQueue(LinkQueue *Q,QElemType e){ QNodePtr p; p=(QNodePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p-data=e; p-next=NULL; (*Q).rear-next=p; (*Q).rear=p; return OK; } 入队 出队，并返回队首元素 Status DeQueue(LinkQueue *Q,QElemType *e){ QNodePtr p; if((*Q).front==(*Q).rear)return ERROR; p=(*Q).front-next; *e=p-data; (*Q).front-next=p-next; //当队列最后一个元素删除时，队尾指针丢失，需对其重新赋值 if((*Q).rear==p)(*Q).rear=(*Q).front; free(p); return OK; } Status QueueTraverse(LinkQueue Q,Status(*visit)(QNodePtr)){ QNodePtr p; p=Q.front-next; while(p){ if(!visit(p))return ERROR; p=p-next; } return OK; } 遍历队列 访问函数 Status visit(QNodePtr p){ printf(%d ,p-data); return OK; } 【queue1.c】测试 #include Li