【数据结构】线性表（二）单链表及其基本操作（创建、插入、删除、修改、遍历打印）

2024-07-30 09:24:47 浏览数 (1)

前文、线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。

按顺序存储方式存储的线性表具有顺序存储结构，一般称之为顺序表。换言之，在程序中采用定长的一维数组，按照顺序存储方式存储的线性表，被称为顺序表。若顺序表中的元素按其值有序，则称其为有序顺序表。

在高级程序设计语言中，“数组”这种数据类型同样具有随机存储的特性，因此用高级程序设计语言实现线性表的顺序存储结构时，通常选择数组。因此，数组的长度就是顺序表的最大长度（MaxSize），顺序表的实际长度为length，其值必须小于等于MaxSize。

【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）-CSDN博客

https://blog.csdn.net/m0_63834988/article/details/132089038?spm=1001.2014.3001.5501

四、线性表的链接存储结构

顺序表的优点是存取速度快。但是，无论是插入一个结点，还是删除一个结点，都需要调整一批结点的地址。要克服该缺点，就必须给出一种不同于顺序存储的存储方式。用链接存储方式存储的线性表被称为链表，可以克服上述缺点。

链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加删除结点，动态调整。

1. 单链表（C语言）

在链接存储结构中，插入和删除操作相对于顺序存储结构而言更加高效，时间复杂度为O(1)。而查找操作的时间复杂度为O(n)。

a. 链表节点结构
代码语言：javascript复制
typedef struct Node {
    int data;
    struct Node* next;
} Node;

链表节点的结构体 Node，包含一个整数数据 data 和一个指向下一个节点的指针 next

b. 创建新节点
代码语言：javascript复制
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}
  • 创建一个新的节点并返回指向该节点的指针：
    • 使用 malloc 分配了节点的内存空间；
    • 将传入的数据赋值给节点的 data 字段，并将 next 字段设置为 NULL。
c. 在链表末尾插入新节点
代码语言：javascript复制
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        printf("内存分配失败！n");
        return;
    }

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    printf("已在链表末尾插入节点：%d", data);
}
  • 调用 createNode 函数创建一个新节点；
  • 检查内存分配是否成功；
    • 如果成功，则根据链表是否为空来确定新节点的位置。
  • 若链表为空，则将新节点设置为头节点；
  • 否则，遍历链表找到最后一个节点，并将最后一个节点的 next 指针指向新节点。
d. 删除指定节点
代码语言：javascript复制
void deleteNode(Node** head, int data) {
    if (*head == NULL) {
        printf("链表为空！n");
        return;
    }

    Node* temp = *head;
    Node* prev = NULL;

    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        free(temp);
        printf("已删除节点：%d", data);
        return;
    }

    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("节点 %d 不存在！n", data);
        return;
    }

    prev->next = temp->next;
    free(temp);
    printf("已删除节点：%d", data);
}
  • 检查链表是否为空，如果为空则输出相应的提示信息。
  • 遍历链表，找到要删除的节点。
    • 如果找到了节点，则修改前一个节点的 next 指针，使其跳过要删除的节点，并释放该节点的内存空间。
    • 如果没有找到要删除的节点，则输出相应的提示信息。
e. 修改指定节点的数据
代码语言：javascript复制
void modifyNode(Node* head, int oldData, int newData) {
    if (head == NULL) {
        printf("链表为空！n");
        return;
    }

    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == oldData) {
            temp->data = newData;
            printf("已将节点 %d 修改为 %dn", oldData, newData);
            return;
        }
        temp = temp->next;
    }

    printf("节点 %d 不存在！n", oldData);
}

查找~删除~修改……这里不重复介绍，懂的都懂，不懂我也没办法

f. 遍历链表并打印
代码语言：javascript复制
void printList(Node* head) {
    if (head == NULL) {
        printf("链表为空！n");
        return;
    }

    Node* temp = head;
    printf("链表节点数据：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("n");
}
  • 检查链表是否为空，如果为空则输出相应的提示信息。
  • 使用一个临时指针变量 temp 来遍历链表，依次访问每个节点并打印其数据。
g. 主函数
代码语言：javascript复制
nt main() {
    Node* head = NULL;  // 头节点

    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    printList(head);

    deleteNode(&head, 2);

    printList(head);

    deleteNode(&head, 4);

    return 0;
}
  • 创建了一个头节点 head；
  • 调用 insertAtEnd 函数三次，在链表末尾插入了三个节点；
  • 调用 printList 函数打印链表的节点数据；
  • 调用 deleteNode 函数删除链表中的一个节点，并再次打印链表的节点数据；
  • 调用 deleteNode 函数尝试删除一个不存在的节点。

C语言代码整合

代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}

// 在链表末尾插入新节点
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        printf("内存分配失败！n");
        return;
    }

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    printf("已在链表末尾插入节点：%d", data);
}

// 删除指定节点
void deleteNode(Node** head, int data) {
    if (*head == NULL) {
        printf("链表为空！n");
        return;
    }

    Node* temp = *head;
    Node* prev = NULL;

    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        free(temp);
        printf("已删除节点：%d", data);
        return;
    }

    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("节点 %d 不存在！n", data);
        return;
    }

    prev->next = temp->next;
    free(temp);
    printf("已删除节点：%d", data);
}
// 修改指定节点的数据
void modifyNode(Node* head, int oldData, int newData) {
    if (head == NULL) {
        printf("链表为空！n");
        return;
    }

    Node* temp = head;
    while (temp != NULL) {
        if (temp->data == oldData) {
            temp->data = newData;
            printf("已将节点 %d 修改为 %dn", oldData, newData);
            return;
        }
        temp = temp->next;
    }

    printf("节点 %d 不存在！n", oldData);
}
// 遍历链表并打印节点数据
void printList(Node* head) {
    if (head == NULL) {
        printf("链表为空！n");
        return;
    }

    Node* temp = head;
    printf("链表节点数据：");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("n");
}

// 主函数测试链表操作
int main() {
    Node* head = NULL;  // 头节点

    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    printList(head);

    deleteNode(&head, 2);

    printList(head);

    deleteNode(&head, 4);

    return 0;
}

Cpp代码整合

与C语言基本相同，这里不再过多介绍

代码语言：javascript复制
#include <iostream>

// 定义链表节点结构
class Node {
public:
    int data;
    Node* next;

    // 构造函数
    Node(int data) : data(data), next(nullptr) {}
};

// 链表类
class LinkedList {
private:
    Node* head;

public:
    // 构造函数
    LinkedList() : head(nullptr) {}

    // 析构函数，用于释放链表内存
    ~LinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }

    // 在链表末尾插入新节点
    void insertAtEnd(int data) {
        Node* newNode = new Node(data);

        if (head == nullptr) {
            head = newNode;
        } else {
            Node* temp = head;
            while (temp->next != nullptr) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        std::cout << "已在链表末尾插入节点：" << data << std::endl;
    }

    // 删除指定节点
    void deleteNode(int data) {
        if (head == nullptr) {
            std::cout << "链表为空！" << std::endl;
            return;
        }

        Node* temp = head;
        Node* prev = nullptr;

        if (temp != nullptr && temp->data == data) {
            head = temp->next;
            delete temp;
            std::cout << "已删除节点：" << data << std::endl;
            return;
        }

        while (temp != nullptr && temp->data != data) {
            prev = temp;
            temp = temp->next;
        }

        if (temp == nullptr) {
            std::cout << "节点 " << data << " 不存在！" << std::endl;
            return;
        }

        prev->next = temp->next;
        delete temp;
        std::cout << "已删除节点：" << data << std::endl;
    }

    // 修改指定节点的数据
    void modifyNode(int oldData, int newData) {
        if (head == nullptr) {
            std::cout << "链表为空！" << std::endl;
            return;
        }

        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == oldData) {
                temp->data = newData;
                std::cout << "已将节点 " << oldData << " 修改为 " << newData << std::endl;
                return;
            }
            temp = temp->next;
        }

        std::cout << "节点 " << oldData << " 不存在！" << std::endl;
    }

    // 遍历链表并打印节点数据
    void printList() {
        if (head == nullptr) {
            std::cout << "链表为空！" << std::endl;
            return;
        }

        Node* temp = head;
        std::cout << "链表节点数据：";
        while (temp != nullptr) {
            std::cout << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    LinkedList list;

    list.insertAtEnd(1);
    list.insertAtEnd(2);
    list.insertAtEnd(3);

    list.printList();

    list.deleteNode(2);

    list.printList();

    list.deleteNode(4);

    return 0;
}
遍历 链表 数据 存储 数据结构

0 人点赞