C++ 将节点插入双向链表

Inserting node into Doubly Linked List

提问by pmqtr

I am wanting to insert a newnode that will contain a name into the correct position of the Doubly Linked List. Basically an Insertion sort is what I want to achieve here.

我想在双向链表的正确位置插入一个包含名称的新节点。基本上，插入排序是我想在这里实现的。

This is the code for the insert function however there is problems:

这是插入函数的代码，但存在问题：

• It breaks the Doubly Linked List if you insert a node with the same value more than once!
• It is not properly sorting the list.

• 如果多次插入具有相同值的节点，则会破坏双向链表！
• 它没有正确排序列表。

Here is the code for the class:

这是该类的代码：

class Doubly
{
private:
        struct node
           {
              string name; //stores name
              node* next; //points to next node
              node* prev; //points to previous node
           };

           node* head; //points to the first node in the list
           node* last; //points to the last node in the list

        public:

            Doubly(); //cstrctr
            ~Doubly(); //dstrctr

       bool empty() const { return head==NULL; }
       void insert(const string& );
       void remove(const string& );
       void print(ostream& OutStream) const;
       void sort (bool);
};

Here is the code for insert:

这是插入的代码：

void Doubly::insert (const string& input)
{
    // Insertion into an Empty List.

if(empty()) //create a new list with one node = Head/Null
    {

       node* name = new node;
       head = name;
       last = name;
       name -> prev = NULL;
       name -> next = NULL;
       name -> name = input; //

    }

    //Insertion into a populated list
else
    {
        node* newnode;
        newnode = head;

        while (input > newnode -> name && newnode -> next != last -> next)
                        newnode = newnode -> next;

            if (newnode == head)
                {
                     node* name = new node;
                     name -> name = input;
                     name -> prev = newnode;
                     name -> next = NULL;
                     head -> next = name;
                     last = name;
                }

           else
           {
               if (newnode == last && input > last -> name) //Add the name to the end of the linked list
                   {
                         last -> next = new node;
                         (last -> next) -> prev = last;
                         last = last -> next;
                         last -> next = NULL;
                         last -> name = input;  
                   }
               else
                   {
                     node* name = new node;
                     name -> name = input;
                     name -> next = newnode;
                     (newnode -> prev) -> next = name;
                     name -> prev = newnode -> prev;
                     newnode -> prev = name;
                   }
          }
    }
}

回答by pconcepcion

I think the problem is when inserting at the head of the list, and you only have one element, the while (input > newnode -> name && newnode -> next != last -> next)can exit because of 2 reasons, and you are asuming that if the pointer is still at the head you have to insert it afterwards, but maybe it just went out of the while because there was only one element and you have to insert the new one before the head.

我认为问题是在插入列表的头部时，你只有一个元素，while (input > newnode -> name && newnode -> next != last -> next)可以退出，原因有两个，你假设如果指针仍然在头部，你必须在之后插入它，但是也许它只是暂时消失了，因为只有一个元素，您必须在头部之前插入新元素。

So you probably have to do something like:

因此，您可能必须执行以下操作：

   if (newnode->next == head->next) { 
        // Create the node and set the common values for all the cases 
        node* name = new node;
        name->name = input;
        if (input > newnode->name) { // Insert as second element
             name->prev = newnode;
             name->next = NULL;
             newnode->prev = NULL;
             newnodw->next = name;  
             head = newnode;
             last = name;                
        }
        else { // Insert as first element
             name->prev = NULL;
             name->next = newnode;
             newnode->prev = name;
             newnodw->next = NULL; 
             head = name;
             last = newnode;
        }

回答by Prakher Agarwal

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct dnode
{
  int data;
  struct dnode *p,*n;
};
  typedef struct dnode dnode;
  dnode *start,*last;
  dnode *createNode(int ele)
  {
   dnode *nnode;
   nnode=(dnode*)malloc(sizeof(dnode));
   nnode->n=NULL;
   nnode->data=ele;
   return nnode;
  }
   dnode *insertBegining(int ele)
   {
    dnode *nnode,*curr,*prev;
    nnode=createNode(ele);
    if(start==NULL)
    {
     start=nnode;
     nnode->p=NULL;
     return start;
    }
    curr=start;
    start=nnode;
    nnode->p=NULL;
    nnode->n=curr;
    curr->p=nnode;
    return start;
   }
  dnode *insertLast(int ele)
  {
   dnode *nnode,*curr,*prev;
   nnode=createNode(ele);
   if(start==NULL)
   {
    start=nnode;
    nnode->p=NULL;
    return start;
   }
  curr=start;
  while(curr!=NULL)
  {
   prev=curr;
   curr=curr->n;
  }
 prev->n=nnode;
 nnode->p=prev;
 return start;
}
void display()
{
 dnode *curr;
 curr=start;
 while(curr!=NULL)
 {
  printf("%d--->",curr->data);
  curr=curr->n;
 }
}
 void main()
 {
  int ch,ele;
  clrscr();
  do
  {
   printf("\nEnter choice");
   printf("\n1-insert beginning");
   printf("\n2-insert last");
   printf("\n3-display");
   printf("\n4-Exit");
   scanf("%d",&ch);
   switch(ch)
   {
    case 1:
    printf("\nEnter Number");
    scanf("%d",&ele);
    insertBegining(ele);
    break;
    case 2:
    printf("enter number");
    scanf("%d",&ele);
    insertLast(ele);
    break;
    case 3:
    display();
    break;
   }
  }
  while(ch!=4);
  getch();
  }