C++ - 通过排序将节点添加到循环链表

我必须创建一个带有函数的循环链表，该函数在特定位置添加一个节点（该列表应该按变量的值升序排序info）。该功能被称为add_node。我认为最好的做法是创建两个指针 - 头部和下一个节点，然后使用while循环将下一个元素与新节点进行比较，如果它位于适当的位置 - 将它放在这两个之间。不幸的是，这个函数只在添加比列表中最大值小的元素时才起作用。该功能应该如何正确排列节点？C++ - 通过排序将节点添加到循环链表

代码：

#include<iostream> 
#include<cstdio> 
#include<cstdlib> 

using namespace std; 

class Circular 
    { 
     struct node 
     { 
      int info; 
      struct node *next; 
     }*head; 

    public: 
     void create_node(int value); 
     void add_node(int value); 
     void display_list(); 
     Circular() 
     { 
      head = nullptr; 
     } 
    }; 

void Circular::create_node(int value) 
{ 
    node *newnode; 
    newnode = new node; 
    newnode->info = value; 
    if (head == nullptr) 
    { 
     head = newnode; 
     newnode->next = head; 
    } 
    else 
    { 
     newnode->next = head->next; 
     head->next = newnode; 
     head = newnode; 
    } 
} 

void Circular::add_node(int value) 
{ 
    if (head == nullptr) 
    { 
     cout<<"List has not been created yet"<<endl; 
     return; 
    } 

    node *newnode, *ptr2, *ptr1; 
    newnode = new node; 
    newnode->info = value; 
    newnode->next=nullptr; 

    ptr1=head; 
    ptr2=head->next; 
    while(newnode->info > ptr2->info) 
    { 
     ptr1 = ptr1->next; 
     ptr2 = ptr2->next; 

     if(ptr2 == head) break; 
    } 
    ptr1->next = newnode; 
    newnode->next = ptr2; 

} 
void Circular::display_list() 
{ 
    node *s; 
    if (head == nullptr) 
    { 
     cout<<"List is empty"<<endl; 
     return; 
    } 
    s = head->next; 
    cout<<"Circular Link List: "<<endl; 
    while (s != head) 
    { 
     cout<<s->info<<"->"; 
     s = s->next; 
    } 
    cout<<s->info<<endl<<endl; 

} 

int main() 
{ 
    int choice, element; 
    Circular cl; 
    while (1) 
    { 
     cout<<"1.Create node"<<endl; 
     cout<<"2.Add node"<<endl; 
     cout<<"3.Display"<<endl; 
     cout<<"9.Quit"<<endl; 
     cout<<"Enter your choice : "; 
     cin>>choice; 
     switch(choice) 
     { 
     case 1: 
      cout<<"Enter the element: "; 
      cin>>element; 
      cl.create_node(element); 
      cout<<endl; 
      break; 
     case 2: 
      cout<<"Enter the element: "; 
      cin>>element; 
      cl.add_node(element); 
      cout<<endl; 
      break; 
     case 3: 
      cl.display_list(); 
      break; 
     case 9: 
      exit(1); 
      break; 
     default: 
      cout<<"Wrong choice"<<endl; 
     } 
    } 
    return 0; 
}

来源

2016-11-26 Berek

仔细看看'add_node'。 '头'*从不改变*。这是错误的。你的不变是'头部'指向*最大*元素。插入时需要考虑到这一点。当插入大于当前最大值的元素时，您必须调整“head”。（您还需要修复中断条件，因为最大的元素需要在当前头后插入）。或者，使'head'指向最小的元素（并在小于当前最小值的元素被插入时对其进行调整）。 –

铅笔和纸在这里是你的朋友。画出清单。绘制一个节点。逐步绘制所需的链接变化以将节点放置到位。将图纸转换为代码。关闭主题，'cout <<“列表尚未创建”<< endl;'冒犯了我的敏感性。我期望将一个节点添加到空列表中，以将添加的节点设置为首部。 – user4581301

谢谢，我做了一些改变。 – Berek

我想出这个：

void Circular::add_node(int value) 
{ 
    node *newnode, *ptr2, *ptr1, *temp; 
    newnode = new node; 
    newnode->info = value; 
    newnode->next=nullptr; 

    if (head == nullptr) 
    { 
     head = newnode; 
     newnode->next = head; 
    } 

    ptr1=head; 
    ptr2=head->next; 
    while(newnode->info > ptr2->info) 
    { 
     ptr1 = ptr1->next; 
     ptr2 = ptr2->next; 

     if(ptr2 == head) break; 
    } 
    if(ptr2->info < newnode->info) 
    { 
     temp=new node; 
     temp->info= ptr2->info; 
     temp->next= ptr2->next; 
     ptr2->next=newnode; 
     newnode->next=temp->next; 
     head=newnode; 

     delete temp; 
    } 
    else 
    { 
     ptr1->next = newnode; 
     newnode->next = ptr2; 
    } 

}

看来，它的作品。但是，我不知道有没有更好的方法来做到这一点？

来源

2016-11-26 22:37:52 Berek

的代码似乎并没有处理的（newnode->资讯）< (head->信息），其中newnode将成为新的头，最后一个节点的下一个指针的情况下，将需要更新，以指向新的头节点（newnode ）。在扫描要添加节点的位置时，在案例ptr2 == head中不需要临时节点。 – rcgldr

感谢您的意见，我会尽力改善代码。 – Berek

如果一个节点在头部之前插入，那么最后一个节点的下一个指针不会更新为指向新的头部节点，并且代码当前没有简单的方法来查找列表中的最后一个节点。

通常的处理方法还有尾指针（指向最后一个节点的指针）。由于这是一个循环列表，因此只需要为该类保留一个尾指针，因为可以在任何时候使用head = tail-> next;

可选：可以更新add_node以处理空列表，从而不需要create_node。

来源

2016-11-27 00:12:00 rcgldr

C++ - 通过排序将节点添加到循环链表

回答

相关问题