侧边栏壁纸
博主头像
张种恩的技术小栈博主等级

行动起来,活在当下

  • 累计撰写 748 篇文章
  • 累计创建 65 个标签
  • 累计收到 39 条评论

目 录CONTENT

文章目录

C语言学习小记(14)-链表

zze
zze
2024-04-15 / 0 评论 / 0 点赞 / 25 阅读 / 11746 字

不定期更新相关视频,抖音点击左上角加号后扫一扫右方侧边栏二维码关注我~正在更新《Shell其实很简单》系列

一、链表概述

链表是一种常见的线性数据结构,它通过指针将一系列动态分配的节点(Node)串联起来。每个节点通常包含两部分:数据域(Data Field)和指针域(Pointer Field)。数据域存储实际数据,而指针域存储指向下一个节点的指针(对于双向链表,还会有一个指向前一个节点的指针)。相比数组,链表在插入、删除元素时具有更好的灵活性,因为不需要移动元素,只需更改相应节点的指针即可。

二、链表类型

  1. 单链表(Singly Linked List) 每个节点只有一个指针,指向下一个节点。最后一个节点的指针通常设置为NULL,表示链表的结尾。

  2. 双链表(Doubly Linked List) 每个节点有两个指针,一个指向前一个节点(前驱指针),一个指向后一个节点(后继指针)。双链表在双向遍历、插入和删除操作中更为方便。

  3. 循环链表(Circular Linked List) 单链表或双链表的一种变体,其特点是最后一个节点的指针不再指向NULL,而是指向链表的头节点,形成一个环形结构。循环链表适用于需要循环遍历的场景。

三、链表操作

  1. 创建链表 初始化链表头节点(通常包含一个空指针),然后通过动态内存分配(如malloc)创建新节点,并将新节点插入到链表中。

  2. 插入节点

    • 头插法:在链表头部创建新节点,更新头节点指针。

    • 尾插法:找到链表尾部,创建新节点并更新尾节点的指针。

    • 指定位置插入:找到指定位置的前一个节点,创建新节点并更新前后节点的指针。

  3. 删除节点

    • 删除头节点:更新头节点指针,释放头节点内存。

    • 删除指定节点:找到指定节点的前一个节点,更新其指针以跳过待删除节点,然后释放待删除节点内存。

    • 删除尾节点:找到倒数第二个节点,更新其指针为NULL,释放尾节点内存。

  4. 遍历链表 从头节点开始,沿着指针逐个访问节点。对于单链表,只能向前遍历;对于双链表,可以向前或向后遍历。

  5. 查找节点 从头节点开始,按照一定的查找条件(如根据节点数据或索引)遍历链表,找到满足条件的节点。

  6. 合并链表 将两个已排序的链表合并为一个有序链表。

  7. 反转链表 改变节点指针方向,使得链表的遍历顺序反转。

四、链表优缺点

优点:

  • 动态分配内存,空间利用率高。

  • 插入、删除操作(除头节点外)时间复杂度为O(1),优于数组。

  • 适用于频繁插入、删除的场景。

缺点:

  • 需要额外的内存空间存储指针。

  • 遍历效率相对数组较低,无法随机访问。

  • 易于产生内存泄漏,需要仔细管理内存。

五、编程实践要点

  1. 内存管理:使用malloc动态分配节点内存,操作完成后使用free释放。避免内存泄漏和悬挂指针。

  2. 空指针检查:对链表操作中涉及的指针进行非空检查,防止空指针解引用引发程序崩溃。

  3. 边界条件处理:在插入、删除、查找等操作中,考虑链表为空、只有一个节点等边界情况。

  4. typedef 定义节点结构体:使用typedef定义节点结构体类型,提高代码可读性。

  5. 函数封装:将链表的创建、插入、删除、遍历等操作封装为函数,提高代码复用性。

六、示例

  • 单链表

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

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

// 创建链表
Node* create_list() {
    return NULL;
}

// 插入节点(尾插法)
void insert(Node** head, int value) {
    Node* new_node = (Node*) malloc(sizeof(Node));
    new_node->data = value;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
    }
}

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

int main() {
    Node* list = create_list();
    insert(&list, 1);
    insert(&list, 2);
    insert(&list, 3);

    printf("Traversing the list:\n");
    traverse(list);

    return 0;
}
  • 双链表

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

// 双链表节点结构定义
typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

// 创建空双链表
DNode* create_dlist() {
    return NULL;
}

// 创建新节点
DNode* create_node(int value) {
    DNode* new_node = (DNode*) malloc(sizeof(DNode));
    new_node->data = value;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

// 头部插入节点
void insert_front(DNode** head, int value) {
    DNode* new_node = create_node(value);

    if (*head == NULL) {
        *head = new_node;
    } else {
        new_node->next = *head;
        (*head)->prev = new_node;
        *head = new_node;
    }
}

// 尾部插入节点
void insert_back(DNode** head, int value) {
    DNode* new_node = create_node(value);

    if (*head == NULL) {
        *head = new_node;
    } else {
        DNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
    }
}

// 遍历双链表(正向)
void traverse_forward(DNode* head) {
    DNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    puts("NULL");
}

// 遍历双链表(反向)
void traverse_backward(DNode* head) {
    DNode* temp = head;
    if (temp != NULL) {
        while (temp->next != NULL) {
            temp = temp->next;
        }
    }
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    }
    puts("NULL");
}

int main() {
    DNode* dlist = create_dlist();
    insert_back(&dlist, 1);
    insert_back(&dlist, 2);
    insert_back(&dlist, 3);

    insert_front(&dlist, 4);
    insert_front(&dlist, 5);
    insert_front(&dlist, 6);

    printf("Forward traversal:\n");
    traverse_forward(dlist);

    printf("\nBackward traversal:\n");
    traverse_backward(dlist);

    return 0;
}
  • 循环链表

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

// 双链表节点结构定义
typedef struct DNode
{
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

// 创建空循环双链表
DNode *create_circular_dlist()
{
    return NULL;
}

// 创建新节点
DNode *create_node(int value)
{
    DNode *new_node = (DNode *)malloc(sizeof(DNode));
    new_node->data = value;
    new_node->prev = NULL;
    new_node->next = NULL;
    return new_node;
}

// 头部插入节点
void insert_front(DNode **head, int value)
{
    DNode *new_node = create_node(value);

    if (*head == NULL)
    {
        *head = new_node;
        new_node->next = new_node; // 创建单节点循环链表
        new_node->prev = new_node; // 更新新节点的prev指针,指向自身
    }
    else
    {
        new_node->next = *head;
        new_node->prev = (*head)->prev; // 更新新节点的prev指针,指向原头节点的前一个节点
        (*head)->prev->next = new_node; // 更新原头节点前一个节点的next指针,指向新节点
        (*head)->prev = new_node;       // 更新原头节点的prev指针,指向新节点
        *head = new_node;               // 更新头指针为新节点
    }
}

// 尾部插入节点
void insert_back(DNode **head, int value)
{
    DNode *new_node = create_node(value);

    if (*head == NULL)
    {
        *head = new_node;
        new_node->next = new_node; // 创建单节点循环链表
    }
    else
    {
        DNode *temp = *head;
        while (temp->next != *head)
        {
            temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
        new_node->next = *head;
        (*head)->prev = new_node;
    }
}

// 遍历循环双链表(正向)
void traverse_forward(DNode *head)
{
    if (head == NULL)
    {
        return;
    }

    DNode *temp = head;
    do
    {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);

    puts("");
}

// 遍历循环双链表(反向)
void traverse_backward(DNode *head)
{
    if (head == NULL)
    {
        return;
    }

    DNode *temp = head->prev; // 从头节点的前一个节点开始反向遍历
    do
    {
        printf("%d -> ", temp->data);
        temp = temp->prev;
    } while (temp != head->prev);

    puts("");
}

int main()
{
    DNode *cdlst = create_circular_dlist();
    insert_front(&cdlst, 1); // 头部插入节点
    insert_front(&cdlst, 2); // 头部插入节点
    insert_front(&cdlst, 3); // 头部插入节点
    insert_back(&cdlst, 4);  // 尾部插入节点
    insert_back(&cdlst, 5);  // 尾部插入节点
    insert_back(&cdlst, 6);  // 尾部插入节点

    printf("Forward traversal:\n");
    traverse_forward(cdlst);

    printf("\nBackward traversal:\n");
    traverse_backward(cdlst);

    return 0;
}

0

评论区