C语言数据结构之链队列的基本操作
程序员文章站
2022-06-21 15:53:59
目录1.队列的定义2.队列的表示和实现(1) 初始化操作(2)销毁队列(3) 入队操作(4) 出队操作附录完整代码:总结1.队列的定义队列 (queue)是另一种限定性的线性表,它只允许在表的一端插入...
1.队列的定义
队列 (queue)是另一种限定性的线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出(fist in fist out,缩写为fifo)的特性。在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front)。 假设队列为q=(a1,a2,…,an),那么a1就是队头元素,an则是队尾元素。队列中的元素是按照a1、a2、…、an的顺序进入的, 退出队列也必须按照同样的次序依次出队,也就是说,只有在a1、a2、…、an-1都离开队列之后,an才能退出队列。
2.队列的表示和实现
链队列可以定义如下:
#define true 1 #define false 0 typedef struct qnode{ qelemtype data; struct qnode *next; }qnode, *queueptr; typedef struct{ queueptr front; queueptr rear; }linkqueue;
(1) 初始化操作
status initqueue(linkqueue &q) { q.front = q.rear = (queueptr) malloc(sizeof(qnode)); if(!q.front) exit ( overflow); q.front ->next = null; return ok; }
(2)销毁队列
status destroyqueue(linkqueue &q) { while(q.front) { q.rear = q.front->next; free (q.front); q.front = q.rear; } return ok; }
(3) 入队操作
status enqueue (linkqueue &q, qelemtype e) { p= (queueptr) malloc(sizeof(qnode)); if (!p) exit ( overflow); p->data = e; p->next = null; q.rear -> next =p; q.rear = p; return ok; }
(4) 出队操作
status dequeue (linkqueue &q, qelemtype &e) { 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; }
附录完整代码:
#include<iostream> using namespace std; #define ok 1 #define false 0 typedef int qelemtype; typedef int status; typedef struct qnode{ qelemtype data; struct qnode *next; }qnode,*queueptr; typedef struct{ queueptr font; queueptr near; }linkqueue; status initqueue(linkqueue &q) { q.font=(queueptr)malloc(sizeof(qnode)); if(!q.font) exit(false); q.font->next=null; q.near=q.font; return ok; } status queueempty(linkqueue q) { if(q.font->next) return ok; return false; } status enqueue(linkqueue &q,qelemtype e) { queueptr p=(queueptr)malloc(sizeof(qnode)); p->data=e; q.near->next = p; q.near = q.near->next; p->next = null; return ok; } status dequeue(linkqueue &q,qelemtype &e) { if(!q.font->next) return false; queueptr p; p=q.font->next; e=p->data; q.font->next=p->next; if(q.near==p) q.near=q.font; //当是最后一个元素时,q.font=null,q.near=q.font free(p); return ok; } status clearqueue(linkqueue &q) { queueptr p; p=q.font->next; queueptr q; while(p) { q=p; p=p->next; q.font->next=p; free(q); } q.near=q.font; return ok; } void menu() { cout<<"初始化队列:1"<<endl; cout<<"入队:2"<<endl; cout<<"出队:3"<<endl; cout<<"清空队列:4"<<endl; cout<<"退出:5"<<endl; } int main() { linkqueue q; while(true) { int n; menu(); scanf("%d",&n); int e=-1; switch(n) { case 1: initqueue(q); continue; case 2: printf("请输入一个元素"); scanf("%d",&e); enqueue(q,e); continue; case 3: dequeue(q,e); printf("\n出队元素%d\n",e); continue; case 4: clearqueue(q); printf("清空成功\n"); continue; default: break; } if(n==5)break; } }
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注的更多内容!