链接的有序名称列表C++

Question

我有一个我必须创建的链接列表的问题。 程序应该接受用户输入的名称，然后将它们放入链接列表中。这个列表应按字母顺序排序，所以当添加一个新节点时，它应该到正确的位置。

我的代码看起来是这样的，现在：

struct node 
{ 
    string info; 
    node *next; 
}; 

class Passenger 
{ 
private: 
    node* pname; 
public: 
    void insert(string); 
    Passenger(); 
};//closes Passenger class 

Passenger::Passenger() 
{ 
    pname = new node; 
    pname -> info = "ABC"; 
    pname -> next = NULL; 
} 

void Passenger::insert(string name) 
{ 
    node *temp, *p, *s; 
    p = pname; 
    s = pname; 
    temp = new node; 
    temp->info = name; 
    if(p-> info == "ABC") //new pname linked list, put temp at the front                   
    { 
     p->info = name; 
     p->next = NULL; 
    } 

    //if there is already one in the list                           
    while(s != NULL) 
    { 
     cout<<"inside while loop"<<endl; 

     //if new node goes to left                             
     if(temp->info < s->info) 
     { 
      temp->next = p; 
      pname = temp; 
     }//closes if    
     if(temp->info > s->info) 
     { 
      if(p->next != NULL) 
      { 
       s = s->next; 
       if(s->next == NULL) 
       s->next = temp; 
      }//closes if                               
     }//closes if                                
     p = p->next; 
     s = s->next; 
    }//closes while  

我真的不知道如何去改变它，它的作品。当列表中有一个节点，然后添加第二个节点时，我完成了它。但是，如果有2个节点已经存在，我不知道如何排序在第三或第四个节点。

戴夫

Answer 1

BTW，较包含“ABC”是荒谬的前哨淋巴结空列表。如果有人想要存储以此开头的列表呢？使用NULL指针来表示一个空列表是一个近乎普遍的约定。

另外，节点不一定是不同的类型。列表类本身可以是一个节点。所以这个类的一个实例只是第一个节点的一个实例，带有一个指向列表其余部分的指针。或者，为了更好地处理空列表，可以使用容器类来保持指向头部的指针（并且可以选择尾部，以便快速尾部插入）。如果你喜欢，实现助手函数可以是节点的成员函数，而不是容器类，所以你可以在任何子列表上调用它们。

---

当我学习链表，我经常发现它有助于借鉴一张纸节点和箭头的指针圈，就像在数据结构教科书。然后，在思考整个过程和任何特殊情况（列表的开头或结尾）时，您不必在思维上保持尽可能多的空间。

---

您可以将问题分为两部分：搜索和插入。

您的搜索功能应该在插入位置之前返回一个指向节点的指针。即最后一个节点的字符串比较小于您插入的字符串。你在那个函数中的循环需要向前看下一个元素，或者保留一个指针。无论哪种方式，您需要返回到之前的节点停止循环的节点。

在节点之后插入很容易。当需要插入新列表的头部时有一种特殊情况，因为没有要修改的节点指向新的当前列表。但是你不需要关心你插入的节点是否是列表的结尾。

您可以减少特殊情况的数量by using a "dummy" node pointing to the actual first element。与InsertNth相比，此技巧可能无法用于基于比较的插入。我的answer on that question将事情分解为查找和插入，并且以类似C的风格编写，即使这是一个Java代码审查问题。请参阅InsertAfter和InsertBefore方法。