노드를 이중 연결 목록에 삽입

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