Icoding题解

题干

队列 循环链表表示队列

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），请完成下列任务：

1: 队列初始化，成功返回真，否则返回假： bool init_queue(LinkQueue *LQ);

2: 入队列，成功返回真，否则返回假： bool enter_queue(LinkQueue *LQ, ElemType x);

3: 出队列，成功返回真，且*x为出队的值，否则返回假 bool leave_queue(LinkQueue *LQ, ElemType *x);

相关定义如下：

1
2
3
4
typedef struct _QueueNode {
    ElemType data;          // 数据域
    struct _QueueNode *next;      // 指针域
}LinkQueueNode, *LinkQueue;

分析

  • 简要分析题干：
    链表表示队列的方法是非常常见的。这里需要注意题目给的条件，只有一个指向尾结点的指针，而且没有头指针。
    链表是循环链表，其头结点是空的。

  • 应当注意的问题：

    1. 队列先进先出的特性
    2. 链表队列的初始化方法
    3. 链表队列入队方法
    4. 链表队列出队方法

  • 解题思路：

    1. 初始化队列
      1. 分配一个空间当作头指针
      2. 如果分配空间失败了，就返回false
      3. 返回指向头结点的指针
      4. 注意头指针的next指向自己
    2. 入队列
      1. 为新结点分配空间
      2. 给新结点赋值
      3. 新结点指向队列指针的next，也就是头指针
      4. 再将队列指针的next指向新结点
      5. 队列指针更新为新结点
      6. 中途如果队列不存在、新结点空间分配失败都会导致返回假
    3. 出队列
      1. 出队列是头指针指向的第一个结点被删除
      2. 如果队列为空，返回false
      3. 头结点的next被临时变量存储
      4. 头结点的next的next若为空，则头结点的next指向自己
      5. 若不为空，头结点的next指向头结点的next的next
      6. 临时变量指向的空间被释放

注释代码

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
bool init_queue(LinkQueue *LQ) {
    //这个函数为什么要传入*LQ而不是LQ？
    //函数要求返回的是布尔值，其值代表函数的操作是否成功
    //因此，我们无法返回一个LinkQueue类型的指针
    //只能通过指向指针的指针，对我们要修改的指针进行操作，并且将操作的结果反映在函数之外
    if (*LQ == NULL)
        return false;
    *LQ = (LinkQueue)malloc(sizeof(LinkQueueNode));
    //分配空间失败则返回假
    if (*LQ == NULL)
        return false;
    //next指向自己，这是循环链表的性质，即最后一个结点指向第一个结点
    //在这里，头结点既是第一个结点，又是最后一个结点
    (*LQ)->next = *LQ;
    (*LQ)->data = 0;
    
    return true;
}

bool enter_queue(LinkQueue *LQ, ElemType x) {
    LinkQueue Temp = NULL;
    Temp = (LinkQueue)malloc(sizeof(LinkQueueNode));
    //分配空间失败返回假
    if (Temp == NULL)
        return false;
    //把数据赋值给新结点的数据域
    Temp->data = x;
    //尾指针的next赋值给Temp的next，这样我们就把头结点的位置交给了新结点
    Temp->next = (*LQ)->next;
    //Temp取代原尾结点成为新的尾结点
    (*LQ)->next = Temp;
    //更新尾指针位置
    (*LQ) = Temp;

    return true;    
}

bool leave_queue(LinkQueue *LQ, ElemType *x) {
    //如果尾指针的next指向自己，这说明队列只有一个头结点
    //队列为空，无法出队
    if ((*LQ)->next == (*LQ))
        return false;
    LinkQueue Temp;
    LinkQueue Head = (*LQ)->next;
    //头指针的next即第一个结点被临时存储
    //用 Temp 表示要出队的结点
    Temp = Head->next;
    *x = Temp->data;
    //将头结点连接向出队结点的下一个结点
    Head->next = Temp->next;

    //需要注意，这里会出现特殊情况：
    //假如队伍中只有一个结点，(*LQ)的指向需要更改为头结点
    //假如队伍中有多个结点，释放掉第一个结点并不会导致(*LQ)的指向为空
    //如果头结点的下一个结点就是尾结点
    //说明队列中只有一个结点，释放这个结点的时候(*LQ)需要更改位置
    if (Temp == (*LQ)) {
        //将 *LQ 指向头结点
        (*LQ) = Head;
    }
    free(Temp);

    return true;
}

完整代码

完整代码的版本和前面带注释的版本都是可以通过icoding检测的。
对比两者的差别有助于更好地理解题目。
个人觉得这个版本的出队写得更优雅一点。

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
bool init_queue(LinkQueue *LQ)
{
    *LQ = (LinkQueue)malloc(sizeof(LinkQueueNode));
    if(*LQ == NULL)
        return false;
    (*LQ)->data = 0;
    (*LQ)->next = (*LQ);
    return true;
}

bool enter_queue(LinkQueue *LQ, ElemType x)
{
    LinkQueue Temp = (LinkQueue)malloc(sizeof(LinkQueueNode));

    if(Temp == NULL)
        return false;

    Temp->data = x;
    Temp->next = (*LQ)->next;
    (*LQ)->next = Temp;
    (*LQ) = (*LQ)->next;
    return true;
}

bool leave_queue(LinkQueue *LQ, ElemType *x)
{
	LinkQueue HeadNode = (*LQ)->next;
    LinkQueue LeaveNode = (*LQ)->next->next;
    if (HeadNode == LeaveNode)
        return false;
    *x = LeaveNode->data;
    HeadNode->next = LeaveNode->next;
    if ((LeaveNode) == (*LQ))
        (*LQ) = (*LQ)->next;
    free(LeaveNode);
    return true;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。