c++ - 链表插入

Question

我正在努力处理这个链表示例，我无法更改下面第二个代码块中的任何代码，但我可以自由编辑此函数。因此，我相信节点的使用不会起作用，因为我无法将它们添加到任何地方。有什么想法吗？

// Insert the given string into the linked-list such that the
// entries in the linked-list are in alphabetical order
bool List::insert(const char *string_p)
{
    // Please write the list insert function
  return SUCCESS;
}

不能修改的代码如下

class ListEntry
{
  public:
    explicit     ListEntry();
    explicit     ListEntry(const char *string_p);
                 ~ListEntry();
    string       getData();
    void         setData(const char* string_p);
    void         setData(string string);
    ListEntry   *getNext();
    ListEntry   *getPrevious();
    ListEntry   *prev_p;   // pointer to previous entry in the linked-list
    ListEntry   *next_p;   // pointer to next entry in the linked-list

  private:
    string          data;      // entry's string
};

// Represents the linked-list object
class List
{
  public:
    List();
    ~List();

    bool printForward();
    bool printReverse();
    bool insert(const char *string_p);

  private:
    int        entryCount;  // number of entries present in the linked-list
    ListEntry *head_p;      // pointer to the first entry in the list
    ListEntry *tail_p;      // pointer to the last entry in the list
};

// ListEntry constructor
ListEntry::ListEntry()
{
  this->prev_p = NULL;
  this->next_p = NULL;
  return;
}

// ListEntry constructor
ListEntry::ListEntry(const char *string_p)
{
  this->data   = string_p;
  this->prev_p = NULL;
  this->next_p = NULL;
  return;
}

// List entry destructor 
ListEntry::~ListEntry()
{
  return;
}

// Return the stored string object
string ListEntry::getData()
{
  return this->data;
}

// Set the internal string data from a char*
void ListEntry::setData(const char* string_p)
{
  this->data = string_p;
}

// Set the internal string data from a string
void ListEntry::setData(string string)
{
  this->data = string;
}

// Returns reference to the next entry in the list
ListEntry *ListEntry::getNext()
{
  return this->next_p;
}

// Returns reference to the previous entry in the list
ListEntry *ListEntry::getPrevious()
{
  return this->prev_p;
}

// List constructor
List::List()
{
  this->entryCount = 0;
  this->head_p     = NULL;
  this->tail_p     = NULL;
}

// List destructor
List::~List()
{
  // Delete all entries in the list
  ListEntry *entry_p   = this->head_p;
  ListEntry *current_p = this->head_p;

  while (entry_p != NULL)
  {
    current_p = entry_p; 
    entry_p = entry_p->getNext();
    delete current_p;
  }
 }

// Output linked list in order from head to tail
// printing out the string data from each list entry
bool List::printForward()
{
  ListEntry *entry_p = this->head_p;
  int count = 0;

  cout << "FORWARD: " << this->entryCount << " entries\n";
  while (entry_p != NULL)
  {
    cout << entry_p->getData() << " ";

    if (++count % 5 == 0 || entry_p == this->tail_p)
    {
      cout << endl;
    }

    entry_p = entry_p->getNext();
  }

  return SUCCESS;
}

// Output linked list in reverse order from tail to head
// printing out the string data from each list entry
bool List::printReverse()
{
  ListEntry *entry_p = this->tail_p;
  int count = 0;

  cout << "REVERSE: " << this->entryCount << " entries\n";
  while (entry_p != NULL)
  {
    cout << entry_p->getData() << " ";

    if (++count % 5 == 0 || entry_p == this->head_p)
    {
      cout << endl;
    }

    entry_p = entry_p->getPrevious();
  }

  return SUCCESS;
}

Answer 1

所以你已经解决了大部分困难的问题。您需要做的是完成有 2 个特殊情况的插入功能。

1)当head_p为null时(list为空)2)当head_p不为null时(list不为空)

在插入方法中使用它，您可以获取给定的 const char *string_p 并从中创建一个 ListEntry。从那里将创建的 ListEntry 插入到列表中。

如果 head_p 为空，那么您基本上是在创建列表，并且需要将头指针和结束指针设置为新的 ListEntry。如果列表不为空，则必须将其添加到末尾。这需要更新 ListEntry 中的 prev_p 和 next_p 指针(将此作为练习留给您)。