行业资讯

C语言单双线性及循环链表怎么实现

发布时间：2023-03-25 10:56:22 作者：iii
来源：亿速云 阅读：141

C语言单双线性及循环链表怎么实现

目录

  1. 引言
  2. 链表的基本概念
  3. 单链表的实现
  4. 双链表的实现
  5. 循环链表的实现
  6. 链表的应用场景
  7. 链表的优缺点
  8. 总结

引言

链表是一种常见的数据结构，广泛应用于各种编程场景中。与数组不同，链表在内存中不是连续存储的，而是通过指针将各个节点连接起来。链表的主要优势在于其动态性，可以根据需要动态地增加或删除节点，而不需要像数组那样预先分配固定大小的内存空间。

本文将详细介绍如何在C语言中实现单链表、双链表和循环链表，并探讨它们的应用场景、优缺点以及实现细节。

链表的基本概念

2.1 什么是链表

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的节点在内存中不是连续存储的，而是通过指针连接在一起。

2.2 链表的分类

链表主要分为以下几种类型：

单链表的实现

3.1 单链表的结构定义

在C语言中，单链表的结构通常定义如下：

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

3.2 单链表的创建

创建一个单链表通常需要初始化一个头节点，头节点不存储数据，只用于指向链表的第一个节点。

Node* createLinkedList() {
    Node* head = (Node*)malloc(sizeof(Node));
    if (head == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    head->next = NULL;
    return head;
}

3.3 单链表的插入

在单链表中插入节点通常有以下几种情况：

3.3.1 在链表头部插入节点

void insertAtHead(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

3.3.2 在链表尾部插入节点

void insertAtTail(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;

    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

3.3.3 在链表中间插入节点

void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

3.4 单链表的删除

在单链表中删除节点通常有以下几种情况：

3.4.1 删除链表头部节点

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

3.4.2 删除链表尾部节点

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

3.4.3 删除链表中间节点

void deleteAfter(Node* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) {
        printf("Previous node or next node cannot be NULL\n");
        return;
    }
    Node* temp = prevNode->next;
    prevNode->next = temp->next;
    free(temp);
}

3.5 单链表的遍历

遍历单链表意味着访问链表中的每一个节点，并执行某些操作（如打印节点的数据）。

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

3.6 单链表的查找

在单链表中查找某个特定的值，通常需要遍历链表，直到找到目标值或到达链表末尾。

Node* searchLinkedList(Node* head, int data) {
    Node* current = head->next;
    while (current != NULL) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

3.7 单链表的销毁

销毁单链表意味着释放链表中所有节点的内存。

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

双链表的实现

4.1 双链表的结构定义

在C语言中，双链表的结构通常定义如下：

typedef struct DNode {
    int data;            // 数据域
    struct DNode* prev;  // 指向前一个节点的指针
    struct DNode* next;  // 指向下一个节点的指针
} DNode;

4.2 双链表的创建

创建一个双链表通常需要初始化一个头节点，头节点不存储数据，只用于指向链表的第一个节点。

DNode* createDoublyLinkedList() {
    DNode* head = (DNode*)malloc(sizeof(DNode));
    if (head == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    head->prev = NULL;
    head->next = NULL;
    return head;
}

4.3 双链表的插入

在双链表中插入节点通常有以下几种情况：

4.3.1 在链表头部插入节点

void insertAtHead(DNode* head, int data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->prev = head;
    newNode->next = head->next;

    if (head->next != NULL) {
        head->next->prev = newNode;
    }
    head->next = newNode;
}

4.3.2 在链表尾部插入节点

void insertAtTail(DNode* head, int data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = NULL;

    DNode* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    newNode->prev = current;
}

4.3.3 在链表中间插入节点

void insertAfter(DNode* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = prevNode->next;
    newNode->prev = prevNode;

    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
}

4.4 双链表的删除

在双链表中删除节点通常有以下几种情况：

4.4.1 删除链表头部节点

void deleteAtHead(DNode* head) {
    if (head->next == NULL) {
        printf("List is empty\n");
        return;
    }
    DNode* temp = head->next;
    head->next = temp->next;
    if (temp->next != NULL) {
        temp->next->prev = head;
    }
    free(temp);
}

4.4.2 删除链表尾部节点

void deleteAtTail(DNode* head) {
    if (head->next == NULL) {
        printf("List is empty\n");
        return;
    }
    DNode* current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    DNode* temp = current->next;
    current->next = NULL;
    free(temp);
}

4.4.3 删除链表中间节点

void deleteAfter(DNode* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) {
        printf("Previous node or next node cannot be NULL\n");
        return;
    }
    DNode* temp = prevNode->next;
    prevNode->next = temp->next;
    if (temp->next != NULL) {
        temp->next->prev = prevNode;
    }
    free(temp);
}

4.5 双链表的遍历

遍历双链表意味着访问链表中的每一个节点，并执行某些操作（如打印节点的数据）。

void traverseDoublyLinkedList(DNode* head) {
    DNode* current = head->next;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

4.6 双链表的查找

在双链表中查找某个特定的值，通常需要遍历链表，直到找到目标值或到达链表末尾。

DNode* searchDoublyLinkedList(DNode* head, int data) {
    DNode* current = head->next;
    while (current != NULL) {
        if (current->data == data) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

4.7 双链表的销毁

销毁双链表意味着释放链表中所有节点的内存。

void destroyDoublyLinkedList(DNode* head) {
    DNode* current = head->next;
    while (current != NULL) {
        DNode* temp = current;
        current = current->next;
        free(temp);
    }
    head->next = NULL;
}

循环链表的实现

5.1 循环链表的结构定义

在C语言中，循环链表的结构通常定义如下：

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

5.2 循环链表的创建

创建一个循环链表通常需要初始化一个头节点，头节点不存储数据，只用于指向链表的第一个节点。

CNode* createCircularLinkedList() {
    CNode* head = (CNode*)malloc(sizeof(CNode));
    if (head == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    head->next = head;  // 头节点指向自己，形成循环
    return head;
}

5.3 循环链表的插入

在循环链表中插入节点通常有以下几种情况：

5.3.1 在链表头部插入节点

void insertAtHead(CNode* head, int data) {
    CNode* newNode = (CNode*)malloc(sizeof(CNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

5.3.2 在链表尾部插入节点

void insertAtTail(CNode* head, int data) {
    CNode* newNode = (CNode*)malloc(sizeof(CNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = head;

    CNode* current = head;
    while (current->next != head) {
        current = current->next;
    }
    current->next = newNode;
}

5.3.3 在链表中间插入节点

void insertAfter(CNode* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    CNode* newNode = (CNode*)malloc(sizeof(CNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = data;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

5.4 循环链表的删除

在循环链表中删除节点通常有以下几种情况：

5.4.1 删除链表头部节点

void deleteAtHead(CNode* head) {
    if (head->next == head) {
        printf("List is empty\n");
        return;
    }
    CNode* temp = head->next;
    head->next = temp->next;
    free(temp);
}

5.4.2 删除链表尾部节点

void deleteAtTail(CNode* head) {
    if (head->next == head) {
        printf("List is empty\n");
        return;
    }
    CNode* current = head;
    while (current->next->next != head) {
        current = current->next;
    }
    CNode* temp = current->next;
    current->next = head;
    free(temp);
}

5.4.3 删除链表中间节点

void deleteAfter(CNode* prevNode) {
    if (prevNode == NULL || prevNode->next == head) {
        printf("Previous node or next node cannot be NULL\n");
        return;
    }
    CNode* temp = prevNode->next;
    prevNode->next = temp->next;
    free(temp);
}

5.5 循环链表的遍历

遍历循环链表意味着访问链表中的每一个节点，并执行某些操作（如打印节点的数据）。

”`c void traverseCircularLinkedList(CNode* head) { CNode* current = head->next; while (current != head) { printf(“%d -> “, current

推荐阅读：
  1. php与C语言有什么区别
  2. 怎么执行C语言中二叉树中序遍历

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

c语言

上一篇：JavaEE内部类的注意事项有哪些

下一篇：MySQL长字符截断如何实现

相关阅读

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

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

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

7*24小时在线QQ：800811969

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