「队列-链式结构」C语言实现

文章目录
  1. 链式队列示意图
  2. 结构定义
  3. 源码
  4. 模块化

链式队列示意图

结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*------------------------- 链式队列结构定义 ------------------------*/

typedef int ElemType;

// 定义链式节点的数据类型
typedef struct node {
    ElemType data;
    struct node * pNext;
} Node, *pNode;

// 利用链式节点构造链式队列的数据类型
typedef struct linkqueue {
    pNode pFront;
    pNode pRear;
} LinkQueue, *pLinkQueue;

/*------------------------- 链式队列结构定义 ------------------------*/

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/*
 * 功能: 队列-链式结构
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/A1-LatestVersion
 * Date: 2022-09-16
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


/*------------------------- 链式队列结构定义 ------------------------*/

typedef int ElemType;

// 定义链式节点的数据类型
typedef struct node {
    ElemType data;
    struct node * pNext;
} Node, *pNode;

// 利用链式节点构造链式队列的数据类型
typedef struct linkqueue {
    pNode pFront;
    pNode pRear;
} LinkQueue, *pLinkQueue;

// 链式队列示意图：https://img.arctee.cn/one/202209162337604.png

/*------------------------- 链式队列结构定义 ------------------------*/


// 函数前置声明
void InitQueue(pLinkQueue Q);
bool EnQueue(pLinkQueue Q, ElemType elem);
void Traverse(pLinkQueue Q);
bool IsEmpty(pLinkQueue Q);
bool DeQueue(pLinkQueue Q, ElemType * pElem);
void DestoryQueue(pLinkQueue Q);
void ClearQueue(pLinkQueue Q);


// 主函数
int main(void)
{
    LinkQueue Q;

    InitQueue(&Q);

    printf("入队：");
    EnQueue(&Q, 1);
    EnQueue(&Q, 2);
    EnQueue(&Q, 3);
    EnQueue(&Q, 4);
    EnQueue(&Q, 5);
    Traverse(&Q);

    printf("出队：");
    ElemType e;
    DeQueue(&Q, &e);
    DeQueue(&Q, &e);
    DeQueue(&Q, &e);
    Traverse(&Q);

    return 0;
}

// 初始化
void InitQueue(pLinkQueue Q)
{
    // 创建头节点
    pNode pHead = (pNode)malloc(sizeof(Node));
    if ( NULL == pHead ) {
        printf("内存分配失败！");
        exit(-1);
    }
    pHead->pNext = NULL;

    // 头指针、尾指针均指向头节点
    Q->pFront = Q->pRear = pHead;
}

// 入队
bool EnQueue(pLinkQueue Q, ElemType elem)
{
    // 创建新节点
    pNode pNew = (pNode)malloc(sizeof(Node));
    if ( NULL == pNew ) {
        printf("内存分配失败，无法入队！");
        return false;
    }
    pNew->data = elem;
    pNew->pNext = NULL;

    // 将新节点连接到队列尾部，然后将尾指针指向新节点
    Q->pRear->pNext = pNew;
    Q->pRear = pNew;

    return true;
}

// 遍历队列
void Traverse(pLinkQueue Q)
{
    pNode p = Q->pFront;  

    while ( p != Q->pRear ) {
        // 头指针的后驱节点才是第一个有效数据
        printf("%d ", p->pNext->data);
        p = p->pNext;
    }
    printf("\n");
}

// 是否为空
bool IsEmpty(pLinkQueue Q)
{
    return (Q->pFront == Q->pRear );
}

// 出队
bool DeQueue(pLinkQueue Q, ElemType * pElem)
{
    if ( IsEmpty(Q) ) {
        printf("队列为空，出队失败！");
        return false;
    }

    pNode p = Q->pFront;

    *pElem = p->pNext->data;
    Q->pFront = p->pNext;  // 将头指针往后移动一位

    free(p);
    p = NULL;

    return true;
}

// 销毁队列
void DestoryQueue(pLinkQueue Q)
{
    pNode p = Q->pFront;

    while( p != NULL ) {
        Q = p->pNext;
        free(p);
        p = Q;
    }
}

// 清空队列
// 保留头节点
void ClearQueue(pLinkQueue Q)
{
    pNode p = Q->pFront->pNext;

    DestoryQueue(p);
    Q->pRear = Q->pFront;
    Q->pFront->pNext = NULL;
}

模块化

linkQueue.h 文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_

#include <stdbool.h>


/*------------------------- 链式队列结构定义 ------------------------*/

typedef int QElemType;  // 这里的 int 根据实际更改  

// 定义链式节点的数据类型
typedef struct qNode {
    QElemType data;
    struct qNode * pNext;
} QNode, *pQNode;

// 利用链式节点构造链式队列的数据类型
typedef struct linkqueue {
    pQNode pFront;
    pQNode pRear;
} LinkQueue, *pLinkQueue;

// 链式队列示意图：https://img.arctee.cn/one/202209162337604.png

/*------------------------- 链式队列结构定义 ------------------------*/


extern void InitQueue(pLinkQueue Q);
extern bool EnQueue(pLinkQueue Q, QElemType elem);
extern void Traverse(pLinkQueue Q);
extern bool QueueIsEmpty(pLinkQueue Q);
extern bool DeQueue(pLinkQueue Q, QElemType * pElem);
extern void DestoryQueue(pLinkQueue Q);
extern void ClearQueue(pLinkQueue Q);


#endif

linkQueue.c 文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include "linkQueue.h"


// 初始化
void InitQueue(pLinkQueue Q)
{
    // 创建头节点
    pQNode pHead = (pQNode)malloc(sizeof(QNode));
    if ( NULL == pHead ) {
        printf("内存分配失败！");
        exit(-1);
    }
    pHead->pNext = NULL;

    // 头指针、尾指针均指向头节点
    Q->pFront = Q->pRear = pHead;
}

// 入队
bool EnQueue(pLinkQueue Q, QElemType elem)
{
    // 创建新节点
    pQNode pNew = (pQNode)malloc(sizeof(QNode));
    if ( NULL == pNew ) {
        printf("内存分配失败，无法入队！");
        return false;
    }
    pNew->data = elem;
    pNew->pNext = NULL;

    // 将新节点连接到队列尾部，然后将尾指针指向新节点
    Q->pRear->pNext = pNew;
    Q->pRear = pNew;

    return true;
}

// 遍历队列
void Traverse(pLinkQueue Q)
{
    pQNode p = Q->pFront;  

    while ( p != Q->pRear ) {
        // 头指针的后驱节点才是第一个有效数据
        printf("%d ", p->pNext->data);
        p = p->pNext;
    }
    printf("\n");
}

// 是否为空
bool QueueIsEmpty(pLinkQueue Q)
{
    return (Q->pFront == Q->pRear );
}

// 出队
bool DeQueue(pLinkQueue Q, QElemType * pElem)
{
    if ( QueueIsEmpty(Q) ) {
        printf("队列为空，出队失败！");
        return false;
    }

    pQNode p = Q->pFront;

    *pElem = p->pNext->data;
    Q->pFront = p->pNext;  // 将头指针往后移动一位

    free(p);
    p = NULL;

    return true;
}

// 销毁队列
void DestoryQueue(pLinkQueue Q)
{
    pQNode p = Q->pFront;


    while( p != NULL ) {
        Q->pFront = p->pNext;
        free(p);
        p = Q->pFront;
    }
}

// 清空队列
// 保留头节点
void ClearQueue(pLinkQueue Q)
{
    DestoryQueue(Q);
    InitQueue(Q);
}