C++中搜索和保护单链表

Question

我有一个关于在 ints 的单链表中搜索元素的问题，在本例中，使用 C++。我正在创建自己的锻炼列表版本。这是代码

假设我有两个搜索功能。我知道我们需要遍历整个列表直到找到元素，因为我们没有像数组那样的直接访问权限。这两个函数是：

bool search(int n); // Traverse the list till find n.
bool search(Node* node, int n); Traverse the list till find n only after *node (included)

1 个案例：我的列表有以下元素：[0, 1, 2, 3]

如果我搜索 3，我很容易在列表末尾找到。不错。

问题： 2 案例：我的列表有以下元素：[0, 1, 2, 3, 3, 3, 4, 5, 6]

如果我搜索 3：

bool search(int n);

我将始终获取第一个 3 元素，除非我有对第二个或第三个 3 元素的引用以传递给该函数：

bool search(Node* node, int n);

我的问题是这是否是单向链表中的正确搜索算法。这两种类型的功能还是我应该有其他类型。

下面是我的实际代码（我没有放搜索代码）：

SingleLinkedList.h

struct Node {
    int data;
    Node* next;

    Node(int d = 0)
        : data {d}, next {nullptr}
    {}
};

class SinglyLinkedList {
public:
    SinglyLinkedList();
    ~SinglyLinkedList();

    void display();
    bool addFirst(const int); // Add a node to the beginning of the list.
    bool addFirst(Node*); // Add a node to the beginning of the list.
    bool addLast(const int); // Add a node to the end of the list.
    bool addLast(Node*); // Add a node to the end of the list.

private:
    Node* head;
    Node* tail;
};

SinglyLinkedList.h

#include "SinglyLinkedList.h"
#include <iostream>

SinglyLinkedList::SinglyLinkedList()
    : head {nullptr}, tail {nullptr}
{}

SinglyLinkedList::~SinglyLinkedList() {
    Node* iterationNode = head;
    Node* actualNode {nullptr};

    while (iterationNode != nullptr) {
        actualNode = iterationNode;
        iterationNode = iterationNode->next;

        delete actualNode;
    }
}

void SinglyLinkedList::display() {
    std::cout << "################### Displaying Linked List ###################" << std::endl;

    if (head == nullptr) {
        std::cout << "Linked List is empty!" << std::endl;
    }
    else {
        Node* iterationNode = head;

        std::cout << "[ ";

        while (iterationNode != nullptr) {
            std::cout << iterationNode->data << " ";
            iterationNode = iterationNode->next;
        }
        iterationNode = nullptr;
        std::cout << "]" << std::endl;
    }

    std::cout << "##############################################################" << std::endl;
}

bool SinglyLinkedList::addFirst(const int n) {
    Node* element = new Node {n};

    if (head == nullptr) {
        head = element;
        tail = element;
    }
    else {
        element->next = head;
        head = element;
    }

    return true;
}

bool SinglyLinkedList::addFirst(Node* element) {
    if (head == nullptr) {
        head = element;
        tail = element;
    }
    else {
        element->next = head;
        head = element;
    }

    return true;
}

bool SinglyLinkedList::addLast(const int n) {
    Node* element = new Node {n};

    if (head == nullptr) {
        head = element;
        tail = element;
    }
    else {
        tail->next = element;
        tail = element;
    }

    return true;
}

bool SinglyLinkedList::addLast(Node* element) {
    if (head == nullptr) {
        head = element;
        tail = element;
    }
    else {
        tail->next = element;
        tail = element;
    }

    return true;
}

Program.cpp

#include <iostream>
#include "SinglyLinkedList.h"

int main() {
    {
        SinglyLinkedList list;

        list.display();
        list.addFirst(5);
        list.addFirst(4);
        list.addFirst(3);

        Node* secondNode = new Node {2};
        list.addFirst(secondNode);

        Node* firstNode = new Node {1};
        list.addFirst(firstNode);

        Node* zeroNode = new Node;
        list.addFirst(zeroNode);

        list.addLast(6);

        list.display();
    }

    system("pause");
}

另一个问题是，我怎样才能保护我的结构，使程序的用户不会直接更改 links/references。例如，在 Program.cpp 中，任何程序员都可以简单地这样做：

secondNode->next = zeroNode

Answer 1

第一个问题的答案取决于您的需要。如果您将其作为一个学习项目来执行，请实施您认为合适的任何内容。您描述的内容适合按值搜索。

防止用户在这种情况下直接访问您的 Node 成员的最佳方法是完全抽象出 Node 类型。您可以通过在源文件中声明和定义 Node 并在 header 中使用 Node* 的前向声明来简单地做到这一点。包含您的 header 的用户将不会对您的节点类型有任何概念。

// SinglyLinkedList.h
class SinglyLinkedList {
  //...//
  struct Node* head; // head node is forward declared
  //...//
}

// SinglyLinkedList.cc
struct Node {
  //...
};

// define ll methods

如果您确实希望用户了解节点类型，一种解决方案是将其成员设为私有，创建一个 public 值访问器方法，并将节点设为 friend单链表 class.

C++中搜索和保护单链表

Search and protecting singly linked list in C++

c++

algorithm

search

linked-list

singly-linked-list