将节点插入双向链表

Question

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

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

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

这是该类的代码：

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);
};

这是插入的代码：

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;
                   }
          }
    }
}

Answer 1

我认为问题是在列表头部插入时，并且只有一个元素，即 while (input > newnode -> name && newnode -> next != last ->; next) 可以因为 2 个原因而退出，并且您假设如果指针仍然位于头部，则必须随后将其插入，但也许它只是因为只有一个元素而退出了 while必须将新的插入到头部之前。

所以你可能必须做类似的事情：

   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;
        }

Answer 2

#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();
  }