Обход одного связанного списка в порядке

Question

Я пытаюсь продумать способ прохождения одного связанного списка.

Это до сих пор, что я сделал:

#include <iostream> 

typedef struct node {                
     int data;    // will store information 
     node *next;    // the reference to the next node 
}; 


int printList(node *traverse) { 
    if (traverse->next == NULL) { 
     return -1; 
    } 
    traverse=traverse->next; 
    printList(traverse); 
    cout << traverse->data << endl; 
    return 0; 
} 

int main() { 
    node *head = NULL;  
    for (int i = 0; i < 10; i++) { 
     node *newEntry = new node; 
     newEntry->data = i; 
     newEntry->next = head; 
     head = newEntry; 
    } 
    printList(head); 
    return 0; 
} 

Я не могу думать способ напечатать последнюю цифру (9) в printList() функции. Как я смогу добиться этого? Мой второй вопрос: как я могу проходить то же самое в цикле while, а не с рекурсивной функцией.

Как некоторые из вас пытались ответить прежде, я не ищу, чтобы пройти это от 9 до 0, это должно пройти от 0 до 9, вы можете увидеть выход из http://codepad.org/ynEdGc9S

Answer 1

Вместо if (traverse->next == NULL) попробовать if (traverse == NULL)

Таким образом, вы печатаете текущий узел, если это фактический узел с данными в нем. Затем вы возвращаетесь. В конце концов, в конце вы перечислите указатель NULL, который вы можете легко избежать.

Answer 2

Почему вы не меняете эти утверждения?

traverse=traverse->next; 
printList(traverse); 
cout << traverse->data << endl; 

Это должно быть изменено на:

cout << traverse->data << endl; 
traverse=traverse->next; 
printList(traverse); 

Это должно работать. А потом, изменить

if(traverse->next==NULL) 

в

if(traverse==NULL) 

Answer 3

В ответ на вторую часть, ваш код может выглядеть следующим образом:

void printList_iter(node* node) 
{ 
    while (node) 
    { 
     cout << node->data << endl; 
     node = node->next; 
    } 
} 

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

Answer 4

Есть несколько вещей здесь:

---

В main()способом вы создаете список неверен. Нарисуйте то, что вы делаете, вы поймете, что ваш head - последний элемент в списке, то есть он, вероятно, будет иметь значение 9. (Распечатайте значение главы непосредственно перед вызовом printList, чтобы проверить это).

Поясню (следовать в вашем коде) с итерации г = 1:

Текущее состояние: head=[0]

1. новый временный узел выделяется [ ]
2. Затем вы назначаете данные его [1]
3. Затем вы устанавливаете этот временный узел рядом с головой [1]-->[0] ; head=[0]
4. n вы назначили голову этому временному узлу [1]-->[0] ; head = [1]

Итак, вы можете видеть, что здесь происходит. Голова должна быть [0], а ее следующая должна быть [1] не наоборот.

Вы можете изучить и подумать о правильном способе этого.

---

printList, это распечатка рекурсивного стека, а не обход. Траверс будет печатать их в обратном порядке, потому что ваш список находится в обратном порядке (проверьте предыдущий раздел^почему).

Это правильный способ печати ссылки в обход. Это напечатает элементы списка так, как они есть. Когда вы проверили траверс-> next == NULL, пройденный последний элемент. Поскольку вы только что закончили рекурсию с возвратом -1, последний элемент никогда не печатался.

int printList(node *traverse) { 
    if (traverse == NULL) { 
     return -1; 
    } 
    cout << traverse->data << endl; 
    printList(traverse->next); 
    return 0; 
} 

---

Итерационный

int printList(node *traverse) { 
    while(traverse != NULL) { 
    cout << traverse->data << endl; 
    traverse = traverse->next; 
    } 
} 

---

Не стесняйтесь задавать вопросы и т.д.