如何在C语言中实现一个简单的链表？请给出链表节点的定义和链表的基本操作函数。

C语言面试题 4月前 0 25

在C语言中，实现一个简单的链表涉及到定义链表节点的结构体和编写一系列操作这些节点的函数。链表是一种动态数据结构，可以在运行时动态地插入或删除节点，不需要事先知道数据的数量。链表的每个节点至少包含两个部分：一个是存储数据的部分，另一个是指向列表中下一个节点的指针。

链表节点的定义

首先，我们定义一个链表节点的结构体，假设我们的链表存储的是整数数据：

typedef struct Node {
    int data;         // 数据部分
    struct Node* next; // 指向下一个节点的指针
} Node;

基本操作函数

接下来，我们定义几个基本的操作函数，包括创建新节点、在链表头部插入节点、在链表尾部插入节点、打印链表和释放链表。

创建新节点

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Allocation Error\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

在链表头部插入节点

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

在链表尾部插入节点

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

打印链表

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

释放链表

void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

示例使用

int main() {
    Node* head = NULL; // 初始化链表为空

    // 插入数据
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);
    insertAtTail(&head, 4);

    // 打印链表
    printList(head);

    // 释放链表内存
    freeList(head);

    return 0;
}

这个例子展示了如何定义链表节点、创建链表、在链表的头部和尾部插入新节点、打印链表以及释放链表占用的内存。链表是一种基础且强大的数据结构，广泛用于实现各种复杂的数据结构和算法。