如何以不可变方式将基于双向链表的Deque传递给函数？

在C语言中，直接用const Deque确实只能保证Deque结构体本身的成员（head、tail指针）不可被重新赋值，但无法阻止通过这些指针修改指向的节点数据。要实现类似C++中const std::deque<int>&的不可变传递效果，你需要手动定义不可变版本的结构体类型，让编译器帮你阻止所有对数据的修改操作。

具体实现步骤 #

1. 定义可变与不可变的节点类型 #

首先，为节点定义一个不可变的指针类型，确保通过这个指针无法修改节点的内容：

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

typedef struct Node Node;
struct Node {
    int val;
    Node* prev;
    Node* next;
};

// 不可变版本的Node指针：无法通过该指针修改节点的val、prev、next
typedef const Node ConstNode;

2. 定义可变与不可变的Deque类型 #

接着，定义一个仅包含不可变节点指针的Deque结构体，用于只读操作的函数参数：

// 可变Deque：用于修改操作（push、pop、clear等）
typedef struct {
    Node* head;
    Node* tail;
} Deque;

// 不可变Deque：用于只读操作（size、isEmpty等）
typedef struct {
    ConstNode* head;
    ConstNode* tail;
} ConstDeque;

3. 拆分API函数 #

将Deque的操作分为两类，分别对应不同的参数类型：

• 只读函数：接收ConstDeque或const ConstDeque*，明确告知调用者不会修改数据
• 修改函数：接收Deque*，允许修改链表结构和节点数据

修改你示例中的deque_size为只读函数：

// 只读函数：接收不可变Deque，编译器会阻止任何修改操作
int deque_size(ConstDeque dq) {
    int sz = 0;
    ConstNode* current = dq.head;
    while (current)
    {
        current = current->next;
        sz++;
    }

    // 以下代码会触发编译错误：无法通过ConstNode*修改节点的val
    // if (dq.head)
    //     dq.head->val = 42;
    return sz;
}

4. 安全转换可变Deque为不可变Deque #

可变的Deque可以安全地转换为ConstDeque（权限降级），你可以直接赋值，或者写一个简单的辅助函数：

// 辅助函数：将可变Deque转换为不可变版本
static inline ConstDeque deque_as_const(Deque* dq) {
    ConstDeque cdq = {.head = dq->head, .tail = dq->tail};
    return cdq;
}

修改后的完整示例 #

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

typedef struct Node Node;
struct Node {
    int val;
    Node* prev;
    Node* next;
};

typedef const Node ConstNode;

typedef struct {
    Node* head;
    Node* tail;
} Deque;

typedef struct {
    ConstNode* head;
    ConstNode* tail;
} ConstDeque;

static inline ConstDeque deque_as_const(Deque* dq) {
    ConstDeque cdq = {.head = dq->head, .tail = dq->tail};
    return cdq;
}

int deque_size(ConstDeque dq) {
    int sz = 0;
    ConstNode* current = dq.head;
    while (current)
    {
        current = current->next;
        sz++;
    }

    // 尝试修改会触发编译错误
    // if (dq.head)
    //     dq.head->val = 42;
    return sz;
}

// 示例修改函数：向Deque尾部添加节点
void deque_push_back(Deque* dq, int val) {
    Node* node = malloc(sizeof(*node));
    node->val = val;
    node->next = NULL;
    node->prev = dq->tail;

    if (dq->tail) {
        dq->tail->next = node;
    } else {
        dq->head = node;
    }
    dq->tail = node;
}

int main(void) {
    Deque dq = {.head = NULL, .tail = NULL};
    deque_push_back(&dq, 1);

    printf("first value: %d\n", dq.head->val);
    // 传递不可变版本给只读函数
    printf("deque size: %d\n", deque_size(deque_as_const(&dq)));
    printf("first value: %d\n", dq.head->val);

    // 可以正常调用修改函数
    deque_push_back(&dq, 2);
    printf("deque size after push: %d\n", deque_size(deque_as_const(&dq)));

    return 0;
}

关键说明 #

• 编译时检查：通过ConstDeque传递的Deque，编译器会阻止任何通过其指针修改节点数据或链表结构的操作，彻底避免意外修改。
• API语义明确：只读函数使用ConstDeque作为参数，向调用者清晰传达"此函数不会修改Deque"的承诺，类似C++中const引用的效果。
• 安全性：禁止将ConstDeque转换回Deque（这会绕过const检查，属于未定义行为），确保不可变传递的安全性。

内容的提问来源于stack exchange，提问作者poss