链表的初始化、取值、查找、插入、删除-Toy模板网

这篇具有很好参考价值的文章主要介绍了链表的初始化、取值、查找、插入、删除。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链表是一种常见的数据结构，它的节点不像数组一样是连续的，而是通过指针链接在一起的。下面是链表的初始化、取值、查找、插入和删除的示例代码，均使用C语言实现，并带有标头。

链表初始化代码：

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

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 初始化链表
ListNode* initList() {
    ListNode *head = (ListNode*)malloc(sizeof(ListNode)); // 创建头结点
    head->next = NULL;
    return head;
}

以上代码中，定义了一个`ListNode`结构体，其中`val`表示节点的值，`next`表示指向下一个节点的指针。在`initList`函数中，创建一个头结点，并将其指针域设置为`NULL`。

链表取值代码：

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

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 取出链表中第i个节点的值
int getVal(ListNode *head, int i) {
    ListNode *p = head->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        printf("Error: Invalid index\n");
        exit(1);
    }
    return p->val;
}

这段代码定义了一个链表节点结构体ListNode，包括节点的值val和指向下一个节点的指针next。另外，还定义了一个函数getVal，用于取出链表中第i个节点的值。

在函数中，首先定义了一个指向头节点的指针p，并初始化为head->next，表示指向第一个节点。同时，定义一个整型变量j，用于记录当前遍历到的节点位置。

接下来使用while循环遍历链表，每次将p指向下一个节点，并将j加1。如果遍历结束后p为空或者j>i，说明所寻找的节点不存在，此时输出错误信息并退出程序。否则，返回p所指向节点的值val。

链表查找代码：

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

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 查找链表中第一个值为val的节点，并返回其指针
ListNode* findNode(ListNode *head, int val) {
    ListNode *p = head->next;
    while (p && p->val != val) {
        p = p->next;
    }
    return p;
}

以上代码中，定义了一个`ListNode`结构体，其中`val`表示节点的值，`next`表示指向下一个节点的指针。在`findNode`函数中，使用循环遍历

链表的插入

链表是一种常用的数据结构，由若干个节点组成，每个节点包括一个数据域和一个指针域。指针域指向下一个节点，最后一个节点的指针域为 NULL。

链表的优点是插入和删除操作的时间复杂度为 O(1)，即不受链表长度的影响。缺点是访问节点的时间复杂度为 O(n)，其中 n 表示链表的长度。

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

// 定义链表节点结构体
typedef struct node {
    int data;
    struct node *next;
} Node;

// 创建链表并返回链表头
Node* createList() {
    Node *head = (Node*) malloc(sizeof(Node));  // 创建头节点
    head->next = NULL;
    return head;
}

// 在链表的指定位置插入一个节点
void insert(Node *head, int data, int index) {
    // 创建新节点并初始化
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    // 找到插入位置的前一个节点
    Node *p = head;  // 从头节点开始查找
    int i = 0;
    while (p->next && i < index) {  // p->next 表示当前节点的下一个节点，直到找到插入位置的前一个节点
        p = p->next;
        i++;
    }

    if (i == index) {
        // 在链表中插入新节点
        newNode->next = p->next;  // 先将新节点的 next 指向原来的节点
        p->next = newNode;  // 再将前一个节点的 next 指向新节点
    } else {
        printf("插入位置超出链表长度！\n");
    }
}

// 遍历链表并打印节点数据
void printList(Node *head) {
    Node *p = head->next;  // 从第一个节点开始遍历
    while (p) {  // p 表示当前节点，直到遍历到最后一个节点
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    Node *head = createList();  // 创建链表并获得链表头

    // 在链表中插入节点并打印链表
    insert(head, 1, 0);
    insert(head, 2, 1);
    insert(head, 3, 2);
    insert(head, 4, 1);
    printList(head);

    return 0;
}

链表的删除文章来源地址https://www.toymoban.com/news/detail-724984.html

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

// 定义链表节点结构体
typedef struct node {
    int data;
    struct node *next;
} Node;

// 创建链表并返回链表头
Node* createList() {
    Node *head = (Node*) malloc(sizeof(Node));  // 创建头节点
    head->next = NULL;
    return head;
}

// 在链表的指定位置插入一个节点
void insert(Node *head, int data, int index) {
    // 创建新节点并初始化
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    // 找到插入位置的前一个节点
    Node *p = head;  // 从头节点开始查找
    int i = 0;
    while (p->next && i < index) {  // p->next 表示当前节点的下一个节点，直到找到插入位置的前一个节点
        p = p->next;
        i++;
    }

    if (i == index) {
        // 在链表中插入新节点
        newNode->next = p->next;  // 先将新节点的 next 指向原来的节点
        p->next = newNode;  // 再将前一个节点的 next 指向新节点
    } else {
        printf("插入位置超出链表长度！\n");
    }
}

// 在链表的指定位置删除一个节点
void delete(Node *head, int index) {
    // 找到需要删除的节点的前一个节点
    Node *p = head;
    int i = 0;
    while (p->next && i < index) {  // p->next 表示当前节点的下一个节点，直到找到需要删除的节点的前一个节点
        p = p->next;
        i++;
    }

    if (i == index && p->next) {
        // 删除节点并释放内存
        Node *temp = p->next;  // 先保存需要删除的节点
        p->next = temp->next;  // 将需要删除的节点的前一个节点的 next 指向需要删除的节点的下一个节点
        free(temp);  // 释放需要删除的节点的内存
    } else {
        printf("删除位置超出链表长度或链表为空！\n");
    }
}

// 遍历链表并打印节点数据
void printList(Node *head) {
    Node *p = head->next;  // 从第一个节点开始遍历
    while (p) {  // p 表示当前节点，直到遍历到最后一个节点
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    Node *head = createList();  // 创建链表并获得链表头

    // 在链表中插入节点并打印链表
    insert(head, 1, 0);
    insert(head, 2, 1);
    insert(head, 3, 2);
    insert(head, 4, 1);
    printList(head);

    // 在链表中删除节点并打印链表
    delete(head, 2);
    printList(head);

    delete(head, 0);
    printList(head);

    delete(head, 2);
    printList(head);

    return 0;
}

到了这里，关于链表的初始化、取值、查找、插入、删除的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！