Наследование C ++ проектирование связанного списка

Question

Я хотел создать связанный список ListList, который наследуется от класса List. ListList использует функции из List, но имеет свои собственные функции. Он имеет собственный указатель начала, указывающий на начало списка, и собственную структуру Node, которая содержит различное количество элементов.

Но, похоже, когда одна из функций List вызывается из ListList, List использует собственный указатель начала и Node. Но я хочу использовать указатель начала ListList и Node. Может ли кто-нибудь помочь мне понять это? Я мог бы опубликовать некоторый код, но я не знаю, какая часть будет иметь отношение ...

это тот, который я назвал Список выше

class LinkList
{
public:
LinkList(); //constructor that sets the start pointer to NULL, to show that the list is empty
~LinkList(); //destructor that deletes each node in the linked list
LinkList(const LinkList &original); //copy constructor
void addToken(string token); //creates a node with the given token and places it at the beginning of the linked list
string showList(); //returns a string of tokens, separated by commas and spaces
bool findToken(string token); //searches linked list for the given token, returns true if the token is in the list
string getToken(string word); //searches linked list for a token that begins with the given word.
                              //Returns the full token if there's a token that begins with the given word, else returns an empty string
void deleteList();
protected:

struct Node //each node of the linked list, held together by the next pointer
{
    string token;
    bool second_word; //tells whether or not there is a space within the token (a two-word keyword)
                      //This could be easily changed to an int that tells how many words are within the keyword (for multi-word keywords)
    Node *next; //pointer to the next node of the linked list. NULL if there is no next node
};

Node *start; //pointer to the beginning of the linked list, and the last added node
bool twoWordToken(string token); //returns true if there is a space located within a token, meaning the token consists of two words.
};

Это тот, который я назвал ListList выше

class LinkListList: public LinkList
{
public:
LinkListList(); //modified contructor initiates the pointers start and ptrNode
~LinkListList(); //modified destructor deletes all nodes and secondaryList nodes
LinkListList(const LinkListList &original); //copy constructor
bool addSubList(LinkList subList, string commandWord); //calls setPtrNode, then adds the given subList to that node
bool findSubToken(string commandWord, string token); //calls setPtrNode, then calls on that node's secondaryList's findToken function
                                                     //returns true if the findToken function returns true, else returns false
string showSubList(string commandWord); //returns a string of tokens, separated by commas and spaces, representing the subList of the given token
string getSubToken(string word, string commandWord); //searches commandWord's subList for a token that begins with the given word.
                                              //Returns the full token if there's a token that begins with the given word, else returns an empty string
private:

struct Node //each node of the linked list, held together by the next pointer
{
    string token;
    bool second_word; //tells whether or not there is a space within the token (a two-word keyword)
    LinkList secondaryList; //keeps a list of all related words
    Node *next;
};

Node *start; //pointer to the beginning of the linked list
Node *ptrNode; //this pointer is used for the functions
void setPtrNode(string token); //sets ptrNode to point to the node containing the specified token. ptrNode is NULL if the token could not be found  
};

Answer 1

Редактировать : Понятно.

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

Вот один из возможных способов структурирования структур данных:

• Общий связанный список:

  template <typename T>
  class LinkedList { ... };
  

• Класс, который использует связанные списки для представления любого списка слов, который вы создаете:

  class TokenList {
    struct Token {
      string word;
      LinkedList<string> related;
    };
    LinkedList<Token> list;
    // Methods to add/search/remove tokens from the lists and sublists
  };
  

(Кроме того, я подозреваю, что структура данных, которую вы на самом деле ищете, map, но это другое обсуждение.)

Answer 2

Похоже, вы ищете отношения Has-A , а не отношения Is-A .

Я бы посоветовал вашему LinkListList иметь список списков первого типа вместо использования наследования.

Answer 3

Виртуальная функция в базовом классе позволяет наследникам предоставлять ее переопределение. Когда базовый класс (или внешние вызывающие абоненты, воспринимающие его как базовый класс) вызывает функцию в производном экземпляре, он знает, что нужно искать это переопределение в производном классе, а не использовать тот, что в базовом классе.

Если вы управляете базовым классом List (в отличие от предоставленного базового класса), вы можете реструктурировать его, чтобы использовать виртуальные функции в ключевых местах, чтобы производный класс ListList мог перенаправлять их в свою собственную логику, оставаясь при этом доступным для доступа к коду например, как список, так что вы можете создать список и передать его чему-то, ожидающему список.

Но если вы не можете изменить Список и у него еще нет виртуальных функций, которые вы можете переопределить, вы не сможете это сделать. Возможно, вам придется искать другой (более низкий) базовый класс или создать ListList (или LinkedList?) Как отдельный класс, а не как производный. Он мог бы предоставить функцию ToList () для экспорта своего содержимого в виде стандартного List (и конструктор, принимающий функцию List и / или From (List) для импорта из List обратно в ListList). Но, вероятно, это больше работы, чтобы использовать его таким образом, в зависимости от того, что вам на самом деле нужно делать с ним, который вы изначально рассчитывали получить из List.

Отредактировано: С кодом, который вы сейчас разместили, похоже, что наследование может быть не тем, что вам действительно нужно, в конце концов, как указывает @rmn. Поэтому, хотя этот ответ, как мы надеемся, немного объясняет, как работают виртуальные функции (применительно к первоначально заданному вопросу), он может не относиться к тому, что вы действительно пытаетесь сделать с двумя классами.

Answer 4

Я думаю, что вашему классу List нужны некоторые виртуальные функции. Он ничего не знает о ListList, поэтому вряд ли можно ожидать использования членов производного класса.