C++数据结构之单链表的实现

C++数据结构之单链表的实现可分为以下步骤：

1. 定义链表节点类

链表节点类需要包含两个成员变量，一个是存储数据的变量，另一个是指向下一个节点的指针变量。同时，需要实现构造函数和析构函数。

class Node{
public:
    int data;           // 存储节点数据
    Node* next;         // 指向下一个节点的指针

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

2. 定义单链表类

单链表类需要简单定义两个私有成员变量，分别是头指针和链表长度。对外提供公有接口实现链表的基本操作，例如插入、删除、查找、遍历等。

class SinglyLinkedList{
private:
    Node* head;     // 头指针
    int length;     // 链表长度

public:
    SinglyLinkedList():head(nullptr),length(0){}      // 构造函数

    ~SinglyLinkedList(){
        // 遍历到链表尾部，依次删除每一个节点
        Node* cur = head;
        while(cur){
            Node* next = cur->next;
            delete cur;
            cur = next;
        }
    }

    // 在链表头部插入节点
    void insertAtHead(int data){
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
        length++;
    }

    // 在链表尾部插入节点
    void insertAtTail(int data){
        Node* newNode = new Node(data);
        if(head == nullptr){
            head = newNode;
        }else{
            Node* cur = head;
            while(cur->next){
                cur = cur->next;
            }
            cur->next = newNode;
        }
        length++;
    }

    // 删除链表中第一个与指定值相等的节点
    void deleteNode(int data){
        Node* cur = head;
        Node* pre = head;
        while(cur){
            if(cur->data == data){
                pre->next = cur->next;
                delete cur;
                length--;
                return;
            }else{
                pre = cur;
                cur = cur->next;
            }
        }
    }

    // 查找链表中第一个与指定值相等的节点，并返回其地址
    Node* search(int data){
        Node* cur = head;
        while(cur){
            if(cur->data == data){
                return cur;
            }else{
                cur = cur->next;
            }
        }
        return nullptr;
    }

    // 遍历链表，并输出每个节点的值
    void traverse(){
        Node* cur = head;
        while(cur){
            cout << cur->data << " ";
            cur = cur->next;
        }
        cout << endl;
    }

    // 返回链表的长度
    int getLength(){
        return length;
    }
};

3. 示例说明

示例1

int main(){
    // 创建一个空链表
    SinglyLinkedList sl;

    // 在链表头部插入三个节点
    sl.insertAtHead(1);
    sl.insertAtHead(2);
    sl.insertAtHead(3);

    // 在链表尾部插入两个节点
    sl.insertAtTail(4);
    sl.insertAtTail(5);

    cout << "链表长度：" << sl.getLength() << endl;

    // 遍历链表，输出每个节点的值
    sl.traverse();

    // 删除值为3的节点
    sl.deleteNode(3);
    cout << "删除节点后的链表：" << endl;
    sl.traverse();

    // 查询值为4的节点
    Node* node = sl.search(4);
    if(node != nullptr){
        cout << "查找成功，节点值为：" << node->data << endl;
    }else{
        cout << "查询失败，未找到指定节点！" << endl;
    }

    return 0;
}

输出：

链表长度：5
3 2 1 4 5 
删除节点后的链表：
2 1 4 5 
查找成功，节点值为：4

示例2

int main(){
    // 创建一个空链表
    SinglyLinkedList sl;

    // 在链表头部插入三个节点
    sl.insertAtHead(1);
    sl.insertAtHead(2);
    sl.insertAtHead(3);

    // 遍历链表，输出每个节点的值
    sl.traverse();

    // 查询值为4的节点
    Node* node = sl.search(4);
    if(node != nullptr){
        cout << "查找成功，节点值为：" << node->data << endl;
    }else{
        cout << "查询失败，未找到指定节点！" << endl;
    }

    return 0;
}

输出：

3 2 1 
查询失败，未找到指定节点！