C语言版本链表详解

admin管理员组

文章数量:1441529

C语言版本链表详解

前言

链表（Linked List）是一种常见的数据结构，它允许我们动态地分配内存，并通过指针将元素链接在一起。在C语言中，链表通常通过结构体（struct）和指针来实现。下面，我将为你详细解释链表的基本概念以及如何在C语言中实现链表。

链表的基本概念

1. 节点（Node）：链表中的每一个元素都称为一个节点。节点通常包含一个数据域（用于存储数据）和一个指针域（用于指向下一个节点）。
2. 头节点（Head Node）：链表的第一个节点，通常包含一个特殊的指针（如NULL）作为链表的结束标志。
3. 尾节点（Tail Node）：链表的最后一个节点，其指针域通常指向NULL。
4. 单向链表（Single Linked List）：每个节点只包含一个指向下一个节点的指针。
5. 双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向下一个节点，另一个指向前一个节点。

示例

C语言实现单向链表

下面是一个简单的单向链表的C语言实现：

代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>  
#include <stdlib.h>  
  
// 定义链表节点结构体  
typedef struct Node {  
    int data;  
    struct Node* next;  
} Node;  
  
// 创建新节点  
Node* createNode(int data) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    if (!newNode) {  
        printf("Memory allocation failed\n");  
        exit(0);  
    }  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  
  
// 在链表末尾添加节点  
void appendNode(Node** head, int data) {  
    Node* newNode = createNode(data);  
    if (*head == NULL) {  
        *head = newNode;  
    } else {  
        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("\n");  
}  
  
int main() {  
    Node* head = NULL;  
    appendNode(&head, 1);  
    appendNode(&head, 2);  
    appendNode(&head, 3);  
    printList(head);  // 输出: 1 2 3  
    return 0;  
}

这个示例中，我们定义了一个Node结构体来表示链表的节点，并提供了创建新节点、在链表末尾添加节点和打印链表的函数。在main函数中，我们创建了一个链表并添加了三个节点，然后打印出链表的内容。

C语言实现双向链表

在C语言中实现双向链表（Doubly Linked List）与实现单向链表类似，但每个节点需要包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。下面是一个简单的双向链表实现示例：

代码语言：javascript代码运行次数：0运行复制

#include <stdio.h>  
#include <stdlib.h>  
  
// 定义双向链表节点结构体  
typedef struct Node {  
    int data;  
    struct Node* next;  
    struct Node* prev;  
} Node;  
  
// 创建新节点  
Node* createNode(int data) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    if (!newNode) {  
        printf("Memory allocation failed\n");  
        exit(0);  
    }  
    newNode->data = data;  
    newNode->next = NULL;  
    newNode->prev = NULL; // 双向链表节点还需要初始化prev为NULL  
    return newNode;  
}  
  
// 在链表末尾添加节点  
void appendNode(Node** head, int data) {  
    Node* newNode = createNode(data);  
    if (*head == NULL) {  
        *head = newNode;  
    } else {  
        Node* temp = *head;  
        while (temp->next != NULL) {  
            temp = temp->next;  
        }  
        temp->next = newNode;  
        newNode->prev = temp; // 双向链表需要设置prev指针  
    }  
}  
  
// 在链表开头添加节点  
void prependNode(Node** head, int data) {  
    Node* newNode = createNode(data);  
    if (*head == NULL) {  
        *head = newNode;  
    } else {  
        newNode->next = *head;  
        (*head)->prev = newNode; // 更新头节点的prev指针  
        *head = newNode; // 更新头指针  
    }  
}  
  
// 打印链表  
void printList(Node* head) {  
    Node* temp = head;  
    while (temp != NULL) {  
        printf("%d ", temp->data);  
        temp = temp->next;  
    }  
    printf("\n");  
}  
  
// 清理链表内存  
void freeList(Node* head) {  
    Node* temp;  
    while (head != NULL) {  
        temp = head;  
        head = head->next;  
        free(temp);  
    }  
}  
  
int main() {  
    Node* head = NULL;  
    appendNode(&head, 1);  
    appendNode(&head, 2);  
    prependNode(&head, 0); // 在开头添加节点  
    printList(head);  // 输出: 0 1 2  
    freeList(head);    // 释放链表内存  
    return 0;  
}

在这个示例中，我们定义了一个Node结构体来表示双向链表的节点，包含了data、next和prev三个成员。createNode函数用于创建新节点，并初始化next和prev为NULL。appendNode函数用于在链表末尾添加节点，同时更新了新节点的prev指针。prependNode函数用于在链表开头添加节点，同时更新了新节点的next指针和头节点的prev指针。printList函数用于打印链表的内容，只遍历next指针。最后，freeList函数用于释放链表占用的内存。

注意，在添加或删除节点时，需要确保正确更新相关节点的prev和next指针，以避免链表断开或形成环。同时，在释放链表内存时，也要确保遍历整个链表并释放每个节点的内存。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-06-07，如有侵权请联系 cloudcommunity@tencent 删除前往查看指针null函数链表内存

本文标签： C语言版本链表详解