C语言实现链表

发布于:2024-10-18 ⋅ 阅读:(41) ⋅ 点赞:(0)

链表(Linked List)是一种基本的数据结构,由一系列节点(Node)组成,每个节点包含数据域和指向下一个节点的指针。与数组不同,链表的元素在内存中不需要连续存储,这使得它在插入和删除元素时具有更好的性能表现。

在C语言中,实现链表需要定义节点的结构体,并通过指针来连接各个节点。

链表的基本结构

首先,我们需要定义链表节点的结构体:

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

// 定义链表节点结构体
typedef struct Node {
    int data;            // 数据域
    struct Node* next;   // 指向下一个节点的指针
} Node;

在这个结构体中:

  • data:存储节点的数据,可以是任意类型,根据需求进行调整。
  • next:指向链表中下一个节点的指针。如果是链表的最后一个节点,next指针为空 (NULL)。

创建节点

创建一个新的节点通常涉及分配内存空间并初始化其数据和指针。

// 创建一个新节点并返回指针
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配内存
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data; // 初始化数据
    newNode->next = NULL; // 初始化指针
    return newNode;
}

链表的基本操作

1. 插入节点

链表的插入操作包括在头部插入、在尾部插入和在指定位置插入。

在头部插入

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 insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("前一个节点不能为空\n");
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

2. 删除节点

删除操作包括删除头节点、删除尾节点和删除指定节点。

删除头节点

void deleteHead(Node** head) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

删除尾节点

void deleteTail(Node** head) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    if ((*head)->next == NULL) { // 只有一个节点
        free(*head);
        *head = NULL;
        return;
    }
    Node* temp = *head;
    while (temp->next->next != NULL) { // 找到倒数第二个节点
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

删除指定节点

假设要删除链表中第一个值为 key 的节点:

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;

    // 如果头节点自身就是要删除的节点
    if (temp != NULL && temp->data == key) {
        *head = temp->next; // 更新头指针
        free(temp);
        return;
    }

    // 查找要删除的节点,记录前驱节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // 未找到
    if (temp == NULL) {
        printf("未找到值为 %d 的节点\n", key);
        return;
    }

    // 从链表中移除节点
    prev->next = temp->next;
    free(temp);
}

3. 遍历链表

遍历链表用于显示所有节点的数据或进行其他操作。

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

4. 搜索节点

在链表中查找是否存在某个值的节点。

Node* search(Node* head, int key) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key) {
            return temp; // 找到节点
        }
        temp = temp->next;
    }
    return NULL; // 未找到
}

完整示例

下面是一个完整的示例程序,展示了如何创建链表并执行基本操作:

#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("内存分配失败\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 insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("前一个节点不能为空\n");
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// 删除头节点
void deleteHead(Node** head) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

// 删除尾节点
void deleteTail(Node** head) {
    if (*head == NULL) {
        printf("链表为空\n");
        return;
    }
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    Node* temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}

// 删除指定节点
void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("未找到值为 %d 的节点\n", key);
        return;
    }

    prev->next = temp->next;
    free(temp);
}

// 遍历链表
void traverseList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 搜索节点
Node* searchList(Node* head, int key) {
    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == key)
            return temp;
        temp = temp->next;
    }
    return NULL;
}

// 主函数示例
int main() {
    Node* head = NULL; // 初始化空链表

    // 插入节点
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);
    insertAtTail(&head, 4);
    insertAtTail(&head, 5);

    printf("链表内容: ");
    traverseList(head); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

    // 插入节点后操作
    Node* secondNode = head->next; // 节点2
    insertAfter(secondNode, 99);
    printf("插入99后链表内容: ");
    traverseList(head); // 输出: 1 -> 2 -> 99 -> 3 -> 4 -> 5 -> NULL

    // 删除头节点
    deleteHead(&head);
    printf("删除头节点后链表内容: ");
    traverseList(head); // 输出: 2 -> 99 -> 3 -> 4 -> 5 -> NULL

    // 删除尾节点
    deleteTail(&head);
    printf("删除尾节点后链表内容: ");
    traverseList(head); // 输出: 2 -> 99 -> 3 -> 4 -> NULL

    // 删除指定节点
    deleteNode(&head, 99);
    printf("删除值为99的节点后链表内容: ");
    traverseList(head); // 输出: 2 -> 3 -> 4 -> NULL

    // 搜索节点
    int key = 3;
    Node* found = searchList(head, key);
    if (found != NULL) {
        printf("找到值为 %d 的节点\n", found->data);
    } else {
        printf("未找到值为 %d 的节点\n", key);
    }

    // 释放剩余节点内存
    while (head != NULL) {
        deleteHead(&head);
    }

    return 0;
}

输出结果

链表内容: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
插入99后链表内容: 1 -> 2 -> 99 -> 3 -> 4 -> 5 -> NULL
删除头节点后链表内容: 2 -> 99 -> 3 -> 4 -> 5 -> NULL
删除尾节点后链表内容: 2 -> 99 -> 3 -> 4 -> NULL
删除值为99的节点后链表内容: 2 -> 3 -> 4 -> NULL
找到值为 3 的节点

链表的优缺点

优点

  1. 动态大小:链表的大小可以根据需要动态调整,不需要事先确定大小。
  2. 高效的插入和删除:在已知位置的情况下,插入和删除操作只需要修改指针,不需要移动其他元素。
  3. 节省内存:仅按需分配内存,不需要为不会用到的元素预留空间。

缺点

  1. 访问效率低:链表不支持随机访问,无法通过索引直接访问某个元素,需要从头开始遍历。
  2. 额外的内存开销:每个节点都需要额外存储指针,增加了内存消耗。
  3. 缓存局部性差:由于节点在内存中不连续,可能导致缓存命中率降低,影响性能。

链表的变种

  1. 双向链表(Doubly Linked List):每个节点不仅有指向下一个节点的指针,还有指向前一个节点的指针,便于双向遍历和操作。

    typedef struct DNode {
        int data;
        struct DNode* next;
        struct DNode* prev;
    } DNode;
    
  2. 循环链表(Circular Linked List):链表的最后一个节点指向头节点,形成一个环,适用于需要循环遍历的场景。

    void traverseCircularList(Node* head) {
        if (head == NULL) return;
        Node* temp = head;
        do {
            printf("%d -> ", temp->data);
            temp = temp->next;
        } while (temp != head);
        printf("HEAD\n");
    }
    
  3. 跳表(Skip List):在链表的基础上增加多级索引,提高搜索效率,常用于实现高效的有序数据结构。

总结

链表是C语言中一种灵活且高效的数据结构,特别适合需要频繁插入和删除元素的场景。虽然它在随机访问和内存使用上存在一些缺点,但通过不同的变种和优化,可以在多种应用中发挥重要作用。在实际开发中,根据具体需求选择合适的数据结构是至关重要的。