Вставка узла в двусвязный список - PullRequest
Новая
       0

Вставка узла в двусвязный список

1 голос
/ 23 марта 2011

Я хочу вставить новый узел, который будет содержать имя, в правильную позицию списка с двойной связью. По сути, здесь я хочу добиться сортировки вставками.

Это код для функции вставки, однако есть проблемы:

  • Он разрушает двусвязный список, если вы вставляете узел с одним и тем же значением более одного раза!
  • Неправильная сортировка списка.

Вот код для класса: 

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

Ответы [ 2 ]

1 голос
/ 23 марта 2011

Я думаю, что проблема заключается в вставке в начало списка, и у вас есть только один элемент, while (input > newnode -> name && newnode -> next != last -> next) может выйти по двум причинам, и вы предполагаете, что если указатель все еще находится в заголовке, у вас естьвставить его потом, но, возможно, он просто вышел из строя, потому что был только один элемент, и вам нужно вставить новый перед головой.

Так что вам, вероятно, нужно сделать что-то вроде: 

   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;
        }
0 голосов
/ 08 апреля 2013 
#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();
  }
...