搜索
C语言

c语言linklist

99ANYc3cd6
99ANYc3cd6 / / 0 评论 / 4 阅读
作者有点忙，还没来得及写简介......
预计阅读时长 29 分钟
位置： 首页 › C语言 › 正文

与数组不同,链表的元素在内存中不是连续存储的，它由一系列节点组成，每个节点包含两部分：

  1. 数据：要存储的实际内容。
  2. 指针：指向链表中下一个节点的内存地址。

通过这种方式,即使节点在内存中是分散的，我们也能通过指针将它们像一条“链子”一样串联起来。

链表的基本概念

节点结构

在 C 语言中，我们通常使用 struct (结构体) 来定义一个链表节点。

// 定义一个链表节点
typedef struct Node {
    int data;           // 数据域，这里以存储整数为例
    struct Node* next;  // 指针域，指向下一个节点
} Node;
  • typedef 关键字为 struct Node 创建了一个别名 Node，这样我们之后就可以直接使用 Node 来定义变量，而不需要每次都写 struct Node。
  • data 是用来存储数据的部分。
  • next 是一个指向 Node 结构体类型的指针，它负责连接下一个节点，链表的最后一个节点的 next 指针通常被设置为 NULL，表示链表的结束。

头指针

链表的第一个节点被称为头节点，我们并不直接存储头节点本身，而是存储一个指向头节点的指针，这个指针被称为头指针，对链表的所有操作，几乎都是从头指针开始的。

Node* head = NULL; // 定义一个头指针，初始时链表为空

链表的基本操作

下面我们来实现链表最常见的几种操作：创建、插入、删除、遍历和释放。

a. 创建和初始化链表

创建链表通常意味着向链表中添加第一个节点。

// 创建一个新节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 1. 分配内存
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1); // 内存不足，退出程序
    }
    newNode->data = value; // 2. 存储数据
    newNode->next = NULL;  // 3. 新节点的next指向NULL
    return newNode;         // 4. 返回新节点的地址
}

b. 遍历链表

从头指针开始,依次访问每个节点，直到遇到 NULL。

void printList(Node* head) {
    Node* current = head; // 从头节点开始
    printf("链表内容: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next; // 移动到下一个节点
    }
    printf("NULL\n"); // 打印链表结束标志
}

c. 在链表头部插入节点

这是最高效的插入操作,时间复杂度为 O(1)。

// 在链表头部插入一个新节点
void insertAtBeginning(Node** headRef, int value) {
    Node* newNode = createNode(value); // 创建新节点
    newNode->next = *headRef; // 新节点的next指向原来的头节点
    *headRef = newNode;       // 更新头指针，使其指向新节点
}

注意：这里的参数是 Node** headRef，即指向头指针的指针，因为我们需要修改 head 这个指针本身（让它指向新节点），而不仅仅是修改它所指向的内容，在 C 语言中，要修改一个指针，必须传递它的地址。

d. 在链表尾部插入节点

这个操作需要遍历整个链表,时间复杂度为 O(n)。

// 在链表尾部插入一个新节点
void insertAtEnd(Node** headRef, int value) {
    Node* newNode = createNode(value);
    // 如果链表为空，新节点就是头节点
    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }
    // 否则，遍历到链表的最后一个节点
    Node* current = *headRef;
    while (current->next != NULL) {
        current = current->next;
    }
    // 将最后一个节点的next指向新节点
    current->next = newNode;
}

e. 在指定位置插入节点

这是一个更通用的插入操作,同样需要遍历。

// 在指定位置插入节点 (位置从0开始)
void insertAtPosition(Node** headRef, int value, int position) {
    if (position < 0) {
        printf("位置无效！\n");
        return;
    }
    // 如果在头部插入
    if (position == 0) {
        insertAtBeginning(headRef, value);
        return;
    }
    Node* newNode = createNode(value);
    Node* current = *headRef;
    int currentPos = 0;
    // 遍历到要插入位置的前一个节点
    while (current != NULL && currentPos < position - 1) {
        current = current->next;
        currentPos++;
    }
    // 如果位置超出链表长度
    if (current == NULL) {
        printf("位置超出链表长度！\n");
        free(newNode); // 释放新节点内存
        return;
    }
    // 插入节点
    newNode->next = current->next;
    current->next = newNode;
}

f. 删除节点

删除节点也需要找到要删除节点的前一个节点。

// 删除值为value的第一个节点
void deleteNode(Node** headRef, int value) {
    Node* temp = *headRef;
    Node* prev = NULL;
    // 如果要删除的是头节点
    if (temp != NULL && temp->data == value) {
        *headRef = temp->next; // 更新头指针
        free(temp);            // 释放旧头节点的内存
        return;
    }
    // 否则，遍历查找要删除的节点
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }
    // 如果没找到值为value的节点
    if (temp == NULL) {
        printf("未找到值为 %d 的节点，\n", value);
        return;
    }
    // 找到了，prev->next 指向 temp->next，跳过 temp
    prev->next = temp->next;
    free(temp); // 释放被删除节点的内存
}

g. 释放整个链表

为了避免内存泄漏,当链表不再需要时，必须释放所有节点占用的内存。

void freeList(Node** headRef) {
    Node* current = *headRef;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next; // 保存下一个节点的地址
        free(current);            // 释放当前节点
        current = nextNode;       // 移动到下一个节点
    }
    *headRef = NULL; // 将头指针设为NULL，表示链表已空
}

完整示例代码

下面是一个将所有操作整合在一起的完整 C 程序。

#include <stdio.h>
#include <stdlib.h>
// 1. 定义链表节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 2. 创建新节点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}
// 3. 在头部插入
void insertAtBeginning(Node** headRef, int value) {
    Node* newNode = createNode(value);
    newNode->next = *headRef;
    *headRef = newNode;
    printf("在头部插入 %d\n", value);
}
// 4. 在尾部插入
void insertAtEnd(Node** headRef, int value) {
    Node* newNode = createNode(value);
    if (*headRef == NULL) {
        *headRef = newNode;
        printf("在尾部插入 %d (链表为空，成为头节点)\n", value);
        return;
    }
    Node* current = *headRef;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    printf("在尾部插入 %d\n", value);
}
// 5. 遍历并打印链表
void printList(Node* head) {
    Node* current = head;
    printf("当前链表: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}
// 6. 删除节点
void deleteNode(Node** headRef, int value) {
    Node* temp = *headRef;
    Node* prev = NULL;
    if (temp != NULL && temp->data == value) {
        *headRef = temp->next;
        free(temp);
        printf("删除值为 %d 的节点 (原头节点)\n", value);
        return;
    }
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("未找到值为 %d 的节点，\n", value);
        return;
    }
    prev->next = temp->next;
    free(temp);
    printf("删除值为 %d 的节点\n", value);
}
// 7. 释放整个链表
void freeList(Node** headRef) {
    Node* current = *headRef;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *headRef = NULL;
    printf("链表已释放，\n");
}
// 主函数
int main() {
    Node* head = NULL; // 初始化一个空链表
    // --- 测试插入操作 ---
    insertAtEnd(&head, 10);     // 链表: 10 -> NULL
    insertAtBeginning(&head, 5); // 链表: 5 -> 10 -> NULL
    insertAtEnd(&head, 20);     // 链表: 5 -> 10 -> 20 -> NULL
    insertAtBeginning(&head, 2); // 链表: 2 -> 5 -> 10 -> 20 -> NULL
    insertAtPosition(&head, 99, 2); // 链表: 2 -> 5 -> 99 -> 10 -> 20 -> NULL
    // --- 测试遍历操作 ---
    printList(head);
    // --- 测试删除操作 ---
    deleteNode(&head, 99);      // 删除中间节点
    deleteNode(&head, 2);       // 删除头节点
    deleteNode(&head, 20);      // 删除尾节点
    deleteNode(&head, 100);     // 删除不存在的节点
    printList(head);
    // --- 测试释放操作 ---
    freeList(&head);
    printList(head); // 此时head为NULL，应该打印 "当前链表: NULL"
    return 0;
}

链表的优缺点

优点

  1. 动态大小：可以在运行时动态地增加或减少大小，不像数组需要预先分配固定大小的内存。
  2. 高效的插入和删除：在已知位置的情况下（尤其是头部），插入和删除操作非常快（时间复杂度为 O(1)）。
  3. 内存利用率高：不需要分配连续的内存块，可以更灵活地利用内存。

缺点

  1. 访问速度慢：无法像数组那样通过索引直接访问元素，必须从头指针开始逐个遍历，访问第 n 个元素的时间复杂度为 O(n)。
  2. 额外的内存开销：每个节点除了存储数据，还需要一个额外的指针来存储下一个节点的地址，这会占用额外的内存。
  3. 实现复杂：相比于数组，链表的指针操作（如插入、删除）逻辑更复杂，容易出错（例如忘记处理 NULL 指针或内存泄漏）。

linklist 在 C 语言中是通过结构体和指针实现的，理解 struct 和 (指针) 是掌握链表的关键，链表是动态数据结构的基础，其变种（如双向链表、循环链表）在操作系统、数据库、网络协议等众多领域都有广泛应用。

-- 展开阅读全文 --
头像
fclose;c语言
« 上一篇 03-01
原创织梦新闻网站模板有何独特优势？
下一篇 » 03-01

相关文章

c语言链表linklist
取消
微信二维码
支付宝二维码

目录[+]