行业资讯

C语言链表的操作有哪些

发布时间：2022-04-22 15:04:06 作者：iii
来源：亿速云 阅读：127

C语言链表的操作有哪些

链表是一种常见的数据结构，广泛应用于各种编程场景中。与数组不同，链表通过指针将一组零散的内存块串联起来，形成一个逻辑上的线性序列。链表的主要优势在于其动态性，可以高效地进行插入和删除操作，而不需要像数组那样频繁地进行内存的重新分配和复制。

在C语言中，链表通常通过结构体和指针来实现。本文将详细介绍C语言中链表的各种操作，包括链表的创建、插入、删除、遍历、查找、排序等。

1. 链表的基本概念

链表由一系列节点（Node）组成，每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。链表的最后一个节点的指针域通常指向NULL，表示链表的结束。

struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
};

链表可以分为单向链表、双向链表和循环链表等类型。本文主要讨论单向链表的基本操作。

2. 链表的创建

链表的创建通常包括两个步骤：定义节点结构和创建链表。

2.1 定义节点结构

首先，我们需要定义一个结构体来表示链表的节点。每个节点包含一个数据域和一个指向下一个节点的指针。

struct Node {
    int data;
    struct Node* next;
};

2.2 创建链表

创建链表的过程通常包括以下几个步骤：

  1. 创建一个头节点（head），并将其指针初始化为NULL。
  2. 逐个添加新节点，并将它们链接起来。
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// 创建链表
struct Node* createLinkedList(int n) {
    struct Node* head = NULL;
    struct Node* temp = NULL;
    struct Node* p = NULL;

    for (int i = 0; i < n; i++) {
        // 创建新节点
        temp = (struct Node*)malloc(sizeof(struct Node));
        printf("Enter the data for node %d: ", i + 1);
        scanf("%d", &(temp->data));
        temp->next = NULL;

        // 如果链表为空，将新节点作为头节点
        if (head == NULL) {
            head = temp;
        } else {
            // 否则，将新节点链接到链表的末尾
            p = head;
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = temp;
        }
    }

    return head;
}

2.3 示例

int main() {
    int n;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    struct Node* head = createLinkedList(n);

    // 打印链表
    struct Node* p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");

    return 0;
}

3. 链表的插入操作

链表的插入操作包括在链表的头部、尾部和中间插入新节点。插入操作的关键在于正确地调整指针的指向。

3.1 在链表头部插入节点

在链表头部插入节点是最简单的插入操作。只需要将新节点的next指针指向当前的头节点，然后将头节点更新为新节点。

struct Node* insertAtHead(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    head = newNode;
    return head;
}

3.2 在链表尾部插入节点

在链表尾部插入节点需要遍历链表，找到最后一个节点，然后将新节点链接到最后一个节点的next指针。

struct Node* insertAtTail(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
    } else {
        struct Node* p = head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }

    return head;
}

3.3 在链表中间插入节点

在链表中间插入节点需要指定插入位置。通常，我们会根据节点的位置或数据值来确定插入点。

struct Node* insertAtPosition(struct Node* head, int data, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;

    if (position == 1) {
        newNode->next = head;
        head = newNode;
    } else {
        struct Node* p = head;
        for (int i = 1; i < position - 1 && p != NULL; i++) {
            p = p->next;
        }
        if (p == NULL) {
            printf("Position out of range\n");
        } else {
            newNode->next = p->next;
            p->next = newNode;
        }
    }

    return head;
}

3.4 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 打印链表
    struct Node* p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");

    return 0;
}

4. 链表的删除操作

链表的删除操作包括删除链表的头部节点、尾部节点和中间节点。删除操作的关键在于正确地调整指针的指向，并释放被删除节点的内存。

4.1 删除链表头部节点

删除链表头部节点只需要将头节点指向下一个节点，并释放原头节点的内存。

struct Node* deleteAtHead(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
    } else {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }
    return head;
}

4.2 删除链表尾部节点

删除链表尾部节点需要遍历链表，找到倒数第二个节点，然后将其next指针指向NULL，并释放最后一个节点的内存。

struct Node* deleteAtTail(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
    } else if (head->next == NULL) {
        free(head);
        head = NULL;
    } else {
        struct Node* p = head;
        while (p->next->next != NULL) {
            p = p->next;
        }
        free(p->next);
        p->next = NULL;
    }
    return head;
}

4.3 删除链表中间节点

删除链表中间节点需要指定删除位置。通常，我们会根据节点的位置或数据值来确定删除点。

struct Node* deleteAtPosition(struct Node* head, int position) {
    if (head == NULL) {
        printf("List is empty\n");
    } else if (position == 1) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    } else {
        struct Node* p = head;
        for (int i = 1; i < position - 1 && p != NULL; i++) {
            p = p->next;
        }
        if (p == NULL || p->next == NULL) {
            printf("Position out of range\n");
        } else {
            struct Node* temp = p->next;
            p->next = p->next->next;
            free(temp);
        }
    }
    return head;
}

4.4 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 打印链表
    struct Node* p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");

    head = deleteAtHead(head);
    head = deleteAtTail(head);
    head = deleteAtPosition(head, 2);

    // 打印链表
    p = head;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");

    return 0;
}

5. 链表的遍历操作

链表的遍历操作是指访问链表中的每一个节点，并对其进行某种操作（如打印节点数据）。遍历操作通常通过一个循环来实现，从头节点开始，依次访问每个节点，直到遇到NULL为止。

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

5.1 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 打印链表
    printLinkedList(head);

    return 0;
}

6. 链表的查找操作

链表的查找操作是指根据某种条件（如数据值）在链表中查找特定的节点。查找操作通常通过遍历链表来实现。

6.1 查找节点

struct Node* searchNode(struct Node* head, int key) {
    struct Node* p = head;
    while (p != NULL) {
        if (p->data == key) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

6.2 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 查找节点
    struct Node* result = searchNode(head, 15);
    if (result != NULL) {
        printf("Node found: %d\n", result->data);
    } else {
        printf("Node not found\n");
    }

    return 0;
}

7. 链表的排序操作

链表的排序操作是指将链表中的节点按照某种顺序（如升序或降序）重新排列。链表的排序通常通过交换节点的数据或调整节点的指针来实现。

7.1 冒泡排序

冒泡排序是一种简单的排序算法，通过多次遍历链表，比较相邻节点的数据，并交换它们的位置，直到链表有序。

void bubbleSort(struct Node* head) {
    int swapped;
    struct Node* p;
    struct Node* last = NULL;

    if (head == NULL) {
        return;
    }

    do {
        swapped = 0;
        p = head;

        while (p->next != last) {
            if (p->data > p->next->data) {
                int temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
                swapped = 1;
            }
            p = p->next;
        }
        last = p;
    } while (swapped);
}

7.2 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 打印链表
    printLinkedList(head);

    // 排序链表
    bubbleSort(head);

    // 打印链表
    printLinkedList(head);

    return 0;
}

8. 链表的反转操作

链表的反转操作是指将链表中的节点顺序颠倒过来。反转操作通常通过调整节点的指针来实现。

8.1 反转链表

struct Node* reverseLinkedList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    head = prev;
    return head;
}

8.2 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 打印链表
    printLinkedList(head);

    // 反转链表
    head = reverseLinkedList(head);

    // 打印链表
    printLinkedList(head);

    return 0;
}

9. 链表的合并操作

链表的合并操作是指将两个有序链表合并为一个有序链表。合并操作通常通过比较两个链表的节点数据，并调整指针的指向来实现。

9.1 合并两个有序链表

struct Node* mergeSortedLists(struct Node* head1, struct Node* head2) {
    struct Node* result = NULL;
    struct Node** lastPtrRef = &result;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            *lastPtrRef = head1;
            head1 = head1->next;
        } else {
            *lastPtrRef = head2;
            head2 = head2->next;
        }
        lastPtrRef = &((*lastPtrRef)->next);
    }

    if (head1 != NULL) {
        *lastPtrRef = head1;
    } else {
        *lastPtrRef = head2;
    }

    return result;
}

9.2 示例

int main() {
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;

    head1 = insertAtHead(head1, 15);
    head1 = insertAtHead(head1, 10);
    head1 = insertAtHead(head1, 5);

    head2 = insertAtHead(head2, 20);
    head2 = insertAtHead(head2, 3);
    head2 = insertAtHead(head2, 2);

    // 打印链表1
    printLinkedList(head1);

    // 打印链表2
    printLinkedList(head2);

    // 合并链表
    struct Node* mergedHead = mergeSortedLists(head1, head2);

    // 打印合并后的链表
    printLinkedList(mergedHead);

    return 0;
}

10. 链表的销毁操作

链表的销毁操作是指释放链表中所有节点的内存，防止内存泄漏。销毁操作通常通过遍历链表，逐个释放节点的内存来实现。

10.1 销毁链表

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

10.2 示例

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 10);
    head = insertAtHead(head, 20);
    head = insertAtTail(head, 30);
    head = insertAtPosition(head, 15, 2);

    // 打印链表
    printLinkedList(head);

    // 销毁链表
    destroyLinkedList(head);

    return 0;
}

11. 总结

链表是一种非常灵活的数据结构，适用于需要频繁插入和删除操作的场景。在C语言中，链表通过结构体和指针来实现，操作链表的代码需要特别注意指针的使用和内存的管理。

本文详细介绍了C语言中链表的各种操作，包括链表的创建、插入、删除、遍历、查找、排序、反转、合并和销毁等。掌握这些操作对于理解和应用链表数据结构至关重要。希望本文能够帮助读者更好地理解和应用链表。

推荐阅读：
  1. 链表的基本操作
  2. C语言的指针、链表的原理和操作

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c语言

上一篇：Python整蛊小程序代码怎么写

下一篇：node导出模块的两种方式是什么

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号