Поиск и защита односвязных списков в C ++ - PullRequest
Новая
       40

Поиск и защита односвязных списков в C ++

0 голосов
/ 02 марта 2019

У меня есть один вопрос, касающийся поиска элементов в односвязном списке 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 case: мой список содержит следующие элементы: [0, 1, 2, 3]

Если я ищу 3, я легко нахожу в концеиз списка.Ницца.

ВОПРОСЫ: 2 case: Мой список содержит следующие элементы: [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;
}

Программа.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");
}

Еще один вопрос: как я могу защитить свою структуру таким образом, чтобы пользователь программы не мог испортить изменение ссылок / ссылок напрямую.Например, в Program.cpp любой программист может просто сделать это: 

secondNode->next = zeroNode

1 Ответ

0 голосов
/ 02 марта 2019

Ответ на ваш первый вопрос зависит от того, что вам нужно.Если вы делаете это как учебный проект, реализуйте то, что считаете нужным.То, что вы описали, подходит для поиска по значению.

Лучший способ запретить пользователям прямой доступ к вашим членам Node в таких случаях, как это полное абстрагирование типа Node.Вы можете сделать это, просто объявив и определив Node в вашем исходном файле и используя предварительные объявления Node * в своем заголовке.Пользователи, включающие ваш заголовок, не будут иметь никакого представления о вашем типе узла. 

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


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

// define ll methods

Если вы хотите, чтобы пользователь знал о типе узла, одно из решений - сделать его членов закрытыми.создайте метод доступа к общедоступным значениям и сделайте Узел другом класса SinglyLinkedList.

...