Связанный список, вставить в конец C++

Question

Я писал простую функцию для вставки в конец связанного списка на C++, но, в конце концов, он отображает только первые данные. Я не могу понять, что случилось. Это функция:

void InsertAtEnd (node* &firstNode, string name){ 

     node* temp=firstNode; 

     while(temp!=NULL) temp=temp->next; 

      temp = new node; 
     temp->data=name; 
     temp->next=NULL; 

     if(firstNode==NULL) firstNode=temp; 

} 

Answer 1

То, что вы написали:

• если firstNode имеет нулевое значение, он заменяется одним узлом temp, который не имеет следующий узел (и ничей next является temp)

• Else, если firstNode не является нулевым, ничего не происходит, за исключением того, что temp узел выделяется и просачивается.

Ниже более правильный код:

void insertAtEnd(node* &first, string name) { 
    // create node 
    node* temp = new node; 
    temp->data = name; 
    temp->next = NULL; 

    if(!first) { // empty list becomes the new node 
     first = temp; 
     return; 
    } else { // find last and link the new node 
     node* last = first; 
     while(last->next) last=last->next; 
     last->next = temp; 
    } 
} 

Кроме того, я хотел бы предложить добавить конструктор к node:

struct node { 
    std::string data; 
    node* next; 
    node(const std::string & val, node* n = 0) : data(val), next(n) {} 
    node(node* n = 0) : next(n) {} 
}; 

, который позволит вам создать temp узел, как это:

node* temp = new node(name); 

Answer 2

Последний элемент в вашем списке никогда не имеет next Указатель установлен на новый элемент в списке.

Answer 3

Проблема в том, что вы заменяете голову связанного списка новым элементом и в процессе теряете ссылку на фактический список.

Для вставки в конце концов, вы хотите изменить состояние while на:

while(temp->next != null) 

После цикла, temp будет указывать на последний элемент в списке. Затем создайте новый узел:

node* newNode = new node; 
newNode->data = name; 
newNode->next = NULL; 

Затем изменить temp s рядом с этим новым узлом:

temp->next = newNode; 

Вам также не нужно проходить firstNode в качестве ссылки, если вы не хотите NULL следует рассматривать как связанный список с длиной 0. В этом случае вам нужно будет значительно изменить свой метод, чтобы он мог обрабатывать случай, когда firstNode равен NULL отдельно, так как в этом случае вы не можете оценить firstNode->next без ошибки сегментации.

Answer 4

Вы сделали две основные ошибки:

1. При прокрутке списка, вы скатываются последний элемент и начать строительство в пустоте позади него. Поиск первого NULL за последний элемент бесполезен. Вы должны найти последний элемент (тот, у которого есть его «следующий» равный NULL). Итерация над temp->next, а не temp.

2. Если вы хотите добавить элемент в конец, вы должны переписать NULL последнего указателя своим адресом. Вместо этого вы пишете новый элемент в начале списка.

   недействительного InsertAtEnd (узел * & firstNode, имя строки) { узла * newnode = новый узел; newnode-> data = name; newnode-> next = NULL;

   if (firstNode == NULL) { firstNode = newnode; } else { node * last = firstNode; while (last-> next! = NULL) last = last-> next; last-> next = newnode; }}

Заметим, что это становится немного аккуратнее, если вы убедитесь, что никогда не кормить NULL, но есть все списки всегда инициализируются по крайней мере один элемент. Кроме того, вставка в начало списка намного проще, чем добавление в конце: newnode->next=firstNode; firstNode=newnode.

Answer 5

Если вы не хотите использовать ссылочный указатель, вы можете использовать указатель на указатель. Мой полный код выглядит следующим образом:

void insertAtEnd(struct node **p,int new_data) 
{ 
    struct node *new_node=(struct node *)malloc(sizeof(struct node)); 
    new_node->data=new_data; 
    new_node->next=NULL; 
    if((*p)==NULL)//if list is empty 
    { 
     *p=new_node; 
     return; 
    } 
    struct node* last=*p;//initailly points to the 1st node 
    while((last)->next != NULL)//traverse till the last node 
     last=last->next; 
    last->next=new_node; 
} 
void printlist(struct node *node) 
{ 
    while(node != NULL); 
    { 
     printf("%d->",node->data); 
     node=node->next; 
    } 
} 
int main() 
{ 
    struct node *root=NULL; 
    insertAtEnd(&root,1); 
    insertAtEnd(&root,2); 
    insertAtEnd(&root,3); 
    insertAtEnd(&root,4); 
    insertAtEnd(&root,5); 
    printlist(root); 
return 0; 
}  

Понимание необходимости ниже двух переменных является ключом к пониманию проблемы:

1. STRUCT узел ** р: Потому что мы должны связать его с корнем узел, созданный в основном.
2. struct node * last: Потому что, если не используется, исходный контент будет изменен с содержимым следующего узла внутри цикла while. В конце будет напечатано только 2 элемента, последние 2 узла, что нежелательно.

Answer 6

void InsertAtEnd (node* &firstNode, string name){ 

     node* temp=firstNode; 

     while(temp && temp->next!=NULL) temp=temp->next; 

     node * temp1 = new node; 
     temp1->data=name; 
     temp1->next=NULL; 
     if(temp==NULL) 
      firstNode=temp1; 
     else 
      temp->next= temp1; 


} 

в то время как цикл будет возвращаться при темпе == NULL в коде вместо этого вы должны вернуть последний указатель узла из в то время как цикл, как этот

while(temp && temp->next!=NULL) temp=temp->next; 

и назначить новый узел к следующему указателю возвращаемого временного узла добавятся данные в хвост связанного списка.

Answer 7

Вы можете использовать этот код:

void insertAtEnd(Node* firstNode, string name) 
{ 
    Node* newn = new Node;    //create new node 
    while(firstNode->next != NULL) //find the last element in yur list 
     firstNode = firstNode->next; //he is the one that points to NULL 
    firstNode->next = newn;    //make it to point to the new element 
    newn->next = NULL;  //make your new element to be the last (NULL) 
    newn->data = name;  //assign data. 
} 

Answer 8

void addlast (int a) 
{ 

    node* temp = new node; 
    temp->data = a; 
    temp->next = NULL; 
    temp->prev=NULL; 
    if(count == maxnum) 
    { 
     top = temp; 
     count++; 
    } 
    else 
    { 
     node* last = top; 
     while(last->next) 
      last=last->next; 
     last->next = temp; 
    } 
}