链接列表插入

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

所以你就有了大部分困难的东西。你要做的就是完成插入函数，这个函数有两种特殊情况。

1)当head_p为空时(列表为空) 2)当head_p不为空时(列表不为空)

在insert方法中使用它，您将获得给定的const char *string_p并从它创建一个ListEntry。然后将创建的ListEntry插入到列表中。

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