将节点插入到双链表中

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个原因，并且你假设如果指针仍然在头部，你必须在后面插入它，但是也许它刚刚离开，因为只有一个元素你呢必须在头部之前插入新的。

所以你可能必须做一些事情，如：

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