数据结构：实验六（单循环链表实现链式队列）_链队用单循环链表表示

单循环链表实现的链式队列，只设头指针，不设尾指针

#include "LLQueue.h"

int main()
{
    LLQueue lq;
    QueueInit(&lq);
    for (int i = 0; i < 5; i++)
    {
        QueueAppend(&lq, i + 1);
        printf("%d 入队列\n", i + 1);
    }
    int x;
    for (int i = 0; i < 5; i++)
    {
        QueueDelete(&lq, &x);
        printf("%d 出队列\n", x);
    }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LLQueue.h：

#include "stdio.h"
#include "stdlib.h"
#define DataType int
typedef struct sqnode
{
    DataType data;
    sqnode *next;
}LQNode;
typedef struct
{
    LQNode *real;
}LLQueue;

void QueueInit(LLQueue *Q)
{
    //如果带头节点，改为
    /*
        head->next=NULL;
        Q->real=NULL;
    */
    Q->real = NULL;
}

int QueueNotEmpty(LLQueue Q)
{
    //如果带头节点，则改为head->next==NULL
    if (Q.real == NULL)
        return 0;
    else return 1;
}

void QueueAppend(LLQueue *Q, DataType x)
{
    LQNode *p;
    p = (LQNode *)malloc(sizeof(LQNode));
    p->data = x;
    //如果带头节点，则改为
    /*
        if(head->next!=NULL)
        {
            p->next=head->next;
            Q->real->next=p;
            Q->real=p;
        }
    */
    if (Q->real != NULL)
    {
        p->next = Q->real->next;//新节点的next指向real的next，即队头，构成循环
        Q->real->next = p;//队尾增加新节点
        Q->real = p;//移动尾指针
    }
    //如果带头节点改为
    /*
        else
        {
            head->next=p;
            Q->real=p;
            Q->real->next = head->next;
        }
    */
    else
    {
        Q->real = p;//移动尾指针
        Q->real->next = Q->real;//构成循环
    }
}

int QueueDelete(LLQueue *Q, DataType *x)
{
    LQNode *p;
    //如果带头节点，判断条件改为head->next==NULL
    if (Q->real == NULL)
    {
        printf("队列已空无数据元素出队列");
        return 0;
    }
    else
    {
        //如果带头节点改为
        /*
             *x=head->next->data;
             p=head->next;
             head->next=p->next;
             if(head->next==NULL)
                Q->real=NULL;
             free(p);
             return 1;
        */
        if (Q->real->next == Q->real)//如果是最后一个元素
        {
            *x = Q->real->data;
            p=Q->real;
            Q->real = NULL;
        }
        else
        {
            *x = Q->real->next->data;
            p = Q->real->next;//队尾的next，即队头
            Q->real->next = p->next;//队尾的两个next
        }
        free(p);
        return 1;
    }
}
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