数据结构——队列

2019-11-06 08:15:07

字体：大中小

来源：转载

供稿：网友

- 算法1： 链队列(存储结构由c3-2.h定义)的基本操作(9个)

void InitQueue(LinkQueue &Q) { // 构造一个空队列Q。 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); // 生成头结点 if(!Q.front) // 生成头结点失败 exit(OVERFLOW); Q.front->next=NULL; // 头结点的next域为空 } void DestroyQueue(LinkQueue &Q) { // 销毁队列Q(无论空否均可)。 while(Q.front) // Q.front不为空 { Q.rear=Q.front->next; // Q.rear指向Q.front的下一个结点 free(Q.front); // 释放Q.front所指结点 Q.front=Q.rear; // Q.front指向Q.front的下一个结点 } } void ClearQueue(LinkQueue &Q) { // 将队列Q清为空队列 DestroyQueue(Q); // 销毁队列Q InitQueue(Q); // 重新构造空队列Q } Status QueueEmpty(LinkQueue Q) { // 若队列Q为空队列，则返回TRUE；否则返回FALSE if(Q.front->next==NULL) return TRUE; else return FALSE; } int QueueLength(LinkQueue Q) { // 求队列Q的长度 int i=0; // 计数器，初值为0 QueuePtr p=Q.front; // p指向头结点 while(Q.rear!=p) // p所指不是尾结点 { i++; // 计数器+1 p=p->next; // p指向下一个结点 } return i; } Status GetHead(LinkQueue Q,QElemType &e) { // 若队列Q不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR QueuePtr p; if(Q.front==Q.rear) // 队列空 return ERROR; p=Q.front->next; // p指向队头结点 e=p->data; // 将队头元素的值赋给e return OK; } void EnQueue(LinkQueue &Q,QElemType e) { // 插入元素e为队列Q的新的队尾元素。在教科书第62页 QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); // 动态生成新结点 if(!p) exit(OVERFLOW); // 失败则退出 p->data=e; // 将值e赋给新结点 p->next=NULL; // 新结点的指针域为空 Q.rear->next=p; // 原队尾结点的指针指向新结点 Q.rear=p; // 尾指针指向新结点 } Status DeQueue(LinkQueue &Q,QElemType &e) { // 若队列Q不空，删除Q的队头元素，用e返回其值， // 并返回OK；否则返回ERROR。 QueuePtr p; if(Q.front==Q.rear) // 队列空 return ERROR; p=Q.front->next; // p指向队头结点 e=p->data; // 将队头元素的值赋给e Q.front->next=p->next; // 头结点指向下一个结点 if(Q.rear==p) // 删除的是队尾结点 Q.rear=Q.front; // 修改队尾指针指向头结点(空队列) free(p); // 释放队头结点 return OK; } void QueueTraverse(LinkQueue Q,void(*visit)(QElemType)) { // 从队头到队尾依次对队列Q中每个元素调用函数visit() QueuePtr p=Q.front->next; // p指向队头结点 while(p) // p指向结点 { visit(p->data); // 对p所指元素调用visit() p=p->next; // p指向下一个结点 } PRintf("/n"); }

- 算法2： 用单链表的基本操作实现链队列(存储结构由c3-2.h定义)的基本操作(9个)

typedef QElemType ElemType; // 定义单链表的元素类型为队列的元素类型 #define LinkList QueuePtr // 定义单链表的类型为相应的链队列的类型 #define LNode QNode #include"bo2-2.cpp" // 单链表的基本操作 void InitQueue(LinkQueue &Q) { // 构造一个空队列Q InitList(Q.front); // 以Q.front为头指针，构造空链表(调用单链表的基本操作) Q.rear=Q.front; // Q.rear与Q.front共同指向链队列的头结点 } void DestroyQueue(LinkQueue &Q) { // 销毁队列Q(无论空否均可) DestroyList(Q.front); // 销毁Q.front为头指针的链表，且置Q.front为空 Q.rear=Q.front; // 置Q.rear也为空 } void ClearQueue(LinkQueue &Q) { // 将队列Q清为空队列 ClearList(Q.front); // 清空以Q.front为头指针的链表，头结点的指针域为空 Q.rear=Q.front; // Q.rear也指向空队列的头结点 } Status QueueEmpty(LinkQueue Q) { // 若队列Q为空队列，则返回TRUE；否则返回FALSE return ListEmpty(Q.front); // 以Q.front为头指针的单链表为空，则队列Q为空，反之亦然 } int QueueLength(LinkQueue Q) { // 求队列Q的长度 return ListLength(Q.front); // 队列Q的长度即为以Q.front为头指针的单链表的长度 } Status GetHead(LinkQueue Q,QElemType &e) { // 若队列Q不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR return GetElem(Q.front,1,e); // 队头元素即为以Q.front为头指针的单链表的第1个元素 } void EnQueue(LinkQueue &Q,QElemType e) { // 插入元素e为队列Q的新的队尾元素 ListInsert(Q.front,ListLength(Q.front)+1,e); // 在最后一个元素之后插入e } Status DeQueue(LinkQueue &Q,QElemType &e) { // 若队列Q不空，删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR if(Q.front->next==Q.rear) // 队列仅有1个元素(删除的也是队尾元素) Q.rear=Q.front; // 令队尾指针指向头结点 return ListDelete(Q.front,1,e); // 删除以Q.front为头指针的单链表的第1个元素 } void QueueTraverse(LinkQueue Q,void(*visit)(QElemType)) { // 从队头到队尾依次对队列Q中每个元素调用函数visit() ListTraverse(Q.front,visit); // 依次对以Q.front为头指针的单链表的元素调用visit() }

- 算法3： 循环队列(存储结构由c3-3.h定义)的基本操作(9个)

void InitQueue(SQQueue &Q) { // 构造一个空队列Q。在教科书第64页 Q.base=(QElemType*)malloc(MAX_QSIZE*sizeof(QElemType)); if(!Q.base) // 存储分配失败 exit(OVERFLOW); Q.front=Q.rear=0; } void DestroyQueue(SqQueue &Q) { // 销毁队列Q，Q不再存在 if(Q.base) // 队列Q存在 free(Q.base); // 释放Q.base所指的存储空间 Q.base=NULL; // Q.base不指向任何存储单元 Q.front=Q.rear=0; } void ClearQueue(SqQueue &Q) { // 将队列Q清为空队列 Q.front=Q.rear=0; } Status QueueEmpty(SqQueue Q) { // 若队列Q为空队列，则返回TRUE；否则返回FALSE if(Q.front==Q.rear) // 队列空的标志 return TRUE; else return FALSE; } Status GetHead(SqQueue Q,QElemType &e) { // 若队列Q不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR if(Q.front==Q.rear) // 队列空 return ERROR; e=Q.base[Q.front]; // 将队头元素的值赋给e return OK; } Status EnQueue(SqQueue &Q,QElemType e) { // 插入元素e为队列Q的新的队尾元素。在教科书第65页 if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满 return ERROR; Q.base[Q.rear]=e; // 将e插在队尾 Q.rear=(Q.rear+1)%MAX_QSIZE; // 队尾指针+1后对MAX_QSIZE取余 return OK; } int QueueLength(SqQueue Q) { // 返回队列Q的元素个数，即队列的长度。在教科书第64页 return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE; } Status DeQueue(SqQueue &Q,QElemType &e) // 在教科书第65页 { // 若队列Q不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR if(Q.front==Q.rear) // 队列空 return ERROR; e=Q.base[Q.front]; // 将队头元素的值赋给e Q.front=(Q.front+1)%MAX_QSIZE; // 移动队头指针 return OK; } void QueueTraverse(SqQueue Q,void(*visit)(QElemType)) { // 从队头到队尾依次对队列Q中每个元素调用函数visit() int i=Q.front; // i最初指向队头元素 while(i!=Q.rear) // i指向队列Q中的元素 { visit(Q.base[i]); // 对i所指元素调用函数visit() i=(i+1)%MAX_QSIZE; // i指向下一个元素 } printf("/n"); }

上一篇：Windows进程间通信--共享内存

下一篇：在Linux下编译OpenCV_Contrib