数据结构算法C语言实现（十一）--- 3.4队列的链式表示和实现

一.简介

FIFO。

二.头文件

  1 //3_4_part1.h
  2 /**
  3 author:zhaoyu
  4 email:zhaoyu1995.com@gmail.com
  5 date:2016-6-9
  6 note:realize my textbook <<数据结构（C语言版）>>
  7 */
  8 //Page 61
  9 #include <cstdio>
 10 #include "head.h"
 11 #define QElemType int
 12 //----单链队列：队列的链式存储结构----
 13 typedef struct QNode{
 14     QElemType data;
 15     struct QNode *next;
 16 }QNode, *QueuePtr;
 17 typedef struct{
 18     QueuePtr front;//队列头指针
 19     QueuePtr rear;//队列尾指针
 20 }LinkQueue;
 21 //基本操作的声明及实现
 22 Status InitQueue(LinkQueue &Q)
 23 {
 24     //构造一个空队列
 25     Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
 26     if (!Q.front)
 27     {
 28         exit(OVERFLOW);
 29     }
 30     Q.front->next = NULL;
 31     return OK;
 32 }
 33 Status DestroyQueue(LinkQueue &Q)
 34 {
 35     //销毁队列 Q ，Q 不存在
 36     while (Q.front)
 37     {
 38         Q.rear = Q.front->next;
 39         free(Q.front);
 40         Q.front = Q.rear;
 41     }
 42     return OK;
 43 }
 44 Status ClearQueue(LinkQueue &Q)
 45 {
 46     //将 Q 清为空队列
 47 }
 48 Status QueueEmpty(LinkQueue Q)
 49 {
 50     //若队列 Q 为空，则返回 TRUE，否则返回 FALSE
 51 }
 52 int QueueLength(LinkQueue Q)
 53 {
 54     //返回 Q 的元素个数
 55 }
 56 Status GetHead(LinkQueue Q, QElemType &e)
 57 {
 58     //若队列不空，则用 e 返回 Q 的队列头元素， 并返回 OK，
 59     //否则返回 ERROR
 60
 61 }
 62 Status EnQueue(LinkQueue &Q, QElemType e)
 63 {
 64     //插入 e 为 Q 的新的队尾元素
 65     QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
 66     if (!p)
 67     {
 68         exit(OVERFLOW);
 69     }
 70     p->data = e;
 71     p->next = NULL;
 72     Q.rear->next = p;
 73     Q.rear = p;
 74     return OK;
 75 }
 76 Status DeQueue(LinkQueue &Q, QElemType &e)
 77 {
 78     //若队列不空，则删除 Q 的队头元素，用 e 返回其值，
 79     //并返回 OK，否则返回 ERROR
 80     if (Q.front == Q.rear)
 81     {
 82         return ERROR;
 83     }
 84     QueuePtr p = Q.front->next;
 85     e = p->data;
 86     Q.front->next = p->next;
 87     if (Q.rear == p)
 88     {
 89         Q.rear = Q.front;
 90     }
 91     free(p);
 92     return OK;
 93 }
 94 void visit(void)
 95 {
 96
 97 }
 98 Status QueueTraverse(LinkQueue Q, void visit())
 99 {
100
101 }
102 void PrintQueue(LinkQueue Q)
103 {
104     //QueuePtr p = Q.front;注意头结点、头指针
105     QueuePtr p = Q.front->next;
106     while (p)
107     {
108         printf("%d\t", p->data);
109         if (p == Q.rear)
110         {
111             break;
112         }
113         p = p->next;
114     }
115     printf("\n");
116 }

3_4_part1.h

三.CPP文件

 1 #include "3_4_part1.h"
 2 int main(int argc, char const *argv[])
 3 {
 4     LinkQueue Q;
 5     InitQueue(Q);
 6     for (int i = 1; i < 10; i++)
 7     {
 8         EnQueue(Q, i);
 9     }
10     PrintQueue(Q);
11     int e;
12     for (int i = 0; i < 5; ++i)
13     {
14         DeQueue(Q, e);
15         printf("%d\t", e);
16     }
17     return 0;
18 }

3_4_part1.cpp

四.测试