当前位置： 首页 > article >正文

数据结构(一)链表

article 2024/11/20 15:16:21

目录

链表

单向链表

单向链表结构与基本操作

插入节点

删除节点

搜索节点

遍历链表

反转链表

双向链表

双向链表结构与基本操作

节点定义和创建

插入节点

删除节点

搜索节点

遍历链表

转链表反

在开始讲线性表之前，先给各位读者重新回顾一下链表

链表

单向链表

单向链表是一种基本的数据结构，由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储数据，而指针域存储指向列表中下一个节点的指针。单向链表的特点是数据元素的排列呈现单一方向，即每个节点仅指向下一个节点，直到最后一个节点的指针通常指向NULL，表示链表的结束。

单向链表结构与基本操作

在C语言中，单向链表的节点可以这样定义

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

 创建节点：初始化一个节点，通常需要提供数据，节点的next指针设置为NULL。

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}
插入节点

插入节点的基本过程：首先找到正确位置p，然后申请新结点t并对t的结点信息赋值，最后讲t插在p之后

插入到头部

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;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

插入到特定位置

在链表的特定位置插入节点需要遍历链表直到达到指定位置的前一个节点。

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 1) {
        insertAtHead(head, data);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            newNode->next = temp->next;
            temp->next = newNode;
        }
    }
}
删除节点

注意：删除一个节点后必须释放该节点的空间

删除头部节点

void deleteFromHead(Node** head) {
    if (*head != NULL) {
        Node* temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

删除尾部节点

删除尾部节点需要遍历整个链表以找到倒数第二个节点。

void deleteFromTail(Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
    } else {
        Node* temp = *head;
        while (temp->next->next != NULL) {
            temp = temp->next;
        }
        free(temp->next);
        temp->next = NULL;
    }
}

删除特定位置的节点

删除特定位置的节点需要遍历链表直到找到该位置的前一个节点。

void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteFromHead(head);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL || temp->next == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            Node* next = temp->next->next;
            free(temp->next);
            temp->next = next;
        }
    }
}
搜索节点

搜索节点涉及遍历链表以查找具有特定值的节点。

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}
遍历链表

遍历链表是访问链表中每个节点的基本操作。

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

反转链表需要改变每个节点的指针方向。

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

双向链表

双向链表（Doubly Linked List）是一种链式数据结构，其中每个节点包含数据部分以及两个指针，分别指向前一个节点和后一个节点。这种结构允许从两个方向遍历链表：向前和向后。双向链表在插入和删除操作中比单向链表更加灵活，因为可以直接访问前驱和后继节点。

双向链表结构与基本操作

节点定义和创建

创建一个双向链表节点，需要初始化数据和两个指针：

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->prev = NULL;
        newNode->next = NULL;
    }
    return newNode;
}
插入节点

插入到头部

在头部插入节点，需要更新头节点的prev指针和新节点的next指针。

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

插入到尾部

在尾部插入节点，需要遍历链表找到尾节点，然后更新尾节点的next指针和新节点的prev指针。

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}

插入到特定位置

在特定位置插入节点，需要更新前一个节点的next指针和新节点的prev指针，以及新节点的next指针和后一个节点的prev指针。

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 1) {
        insertAtHead(head, data);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position - 1; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            newNode->next = temp->next;
            newNode->prev = temp;
            if (temp->next != NULL) {
                temp->next->prev = newNode;
            }
            temp->next = newNode;
        }
    }
}
删除节点

删除头部节点：删除头部节点，需要更新头节点的prev指针和新头节点的next指针。

void deleteFromHead(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
}

删除尾部节点：删除尾部节点，需要遍历链表找到倒数第二个节点，然后更新其next指针

void deleteFromTail(Node** head) {
    if (*head == NULL) return;
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
    } else {
        Node* temp = *head;
        while (temp->next->next != NULL) {
            temp = temp->next;
        }
        free(temp->next);
        temp->next = NULL;
    }
}

删除特定位置的节点：删除特定位置的节点，需要更新前一个节点的next指针和后一个节点的prev指针

void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) return;
    if (position == 1) {
        deleteFromHead(head);
    } else {
        Node* temp = *head;
        for (int i = 1; temp != NULL && i < position; i++) {
            temp = temp->next;
        }
        if (temp == NULL) {
            printf("Position exceeds the length of the list.\n");
        } else {
            if (temp->prev != NULL) {
                temp->prev->next = temp->next;
            }
            if (temp->next != NULL) {
                temp->next->prev = temp->prev;
            }
            free(temp);
        }
    }
}
搜索节点

搜索节点，需要遍历链表直到找到具有特定值的节点。

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}
遍历链表

向前遍历

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

向后遍历

void printListBackward(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d <- ", current->data);
        current = current->prev;
    }
    printf("NULL\n");
}
转链表反
void reverseList(Node** head) {
    Node* temp = NULL;
    Node* current = *head;
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    if (temp != NULL) {
        *head = temp->prev;
    }
}


http://www.kler.cn/a/401666.html

相关文章：

  • Java 核心技术卷 I 学习记录八
  • 【初阶数据结构与算法】线性表之栈和队列的定义与实现（含源码和有效的括号练习）
  • 软件测试基础三十 （Python + Flask实现Mock平台搭建）
  • Misc_01转二维码(不是二进制)
  • RadSystems 自定义页面全攻略：个性化任务管理系统的实战设计
  • 机器学习3
  • 【Unity基础】对比Unity中两种粒子系统
  • ubuntu系统中使用docker-compose安装部署docker集群（本地）
  • 聚焦 NLP 和生成式 AI 的创新与未来 基础前置知识点
  • 多目标优化算法：多目标鳗鱼和石斑鱼优化算法（MOEGO）求解ZDT1、ZDT2、ZDT3、ZDT4、ZDT6，提供完整MATLAB代码
  • vue2+a-table——实现框选选中功能——js技能提升
  • 探索PyMuPDF：Python中的强大PDF处理库
  • 结构体位段+联合和枚举
  • Object.prototype.hasOwnProperty.call(item, key) 作用与用途
  • 2.5D视觉——Aruco码定位检测
  • 前端软件开发质量管控之应用质量 - 关于E2E测试的对象目的及不同方案特性对比（一）
  • ifuse不能挂载App Store下载的包ERROR: InstallationLookupFailed
  • 有关django、python版本、sqlite3版本冲突问题
  • Brave127编译指南 Linux篇-环境配置(五)
  • Python+7z.exe实现自动化压缩与解压
  • 【代码随想录|回溯算法排列问题】
  • 微信小程序-prettier 格式化
  • java实现贪心算法
  • SAM-Med2D 训练完成后boxes_prompt没有生成mask的问题
  • 首次实现！在Docker容器中运行macOS项目，自动化下载与Web体验
  • 高效整合：汤臣倍健营销云数据集成到金蝶云星辰V2解析