Итерация от конца до начала односвязного списка без его обращения

Question

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

void writeWords(t_list *lp, FILE *fp, int total_num_words) {
    t_list *aux; 
    aux = lp;
    while(aux != NULL){
      writeOneWord((t_word*) getItemList(aux), fp, total_num_words);
      aux = getNextListElement(aux);
    }
}

То есть список повторяется в обычном порядке, содержимое каждого узла печатается как writeOneWord.

Теперь я сомневаюсь: как я уже сказал, я хочу иметь возможность перебирать список от конца до начала, и это при сохранении списка таким, какой он есть, поэтому нет обращений .Я знаю, что код должен соответствовать какой-то рекурсивной реализации, но до сих пор я пытался сделать это безрезультатно.Кто-нибудь может пролить свет на это?

Answer 1

Вы должны использовать двусвязный список.Но вот обходной путь:

void writeWordsBackwards(t_list *lp, FILE *fp, int total_num_words) {
    size_t i = 0;
    t_list words[total_num_words];
    for (size_t i = 0; lp && i < total_num_words; i += 1) {
        words[i] = lp;
        lp = getNextListElement(lp);
    }
    while (i >= 0) {
      writeOneWord((t_word*) getItemList(words[i]), fp, total_num_words);
      i -= 1;
    }
}

В отличие от рекурсивного подхода, он использует меньше стекового пространства.Но это все еще требует потенциально неограниченного количества стекового пространства;malloc, вероятно, предпочтительнее, чтобы избежать переполнения стека.

Answer 2

Вы определенно хотите рекурсивную функцию для этого.

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

void writeWords(t_list *lp, FILE *fp, int total_num_words) {
    if (lp != NULL) {
        writeWords(getNextListElement(lp), fp, total_num_words);
        writeOneWord((t_word*) getItemList(lp), fp, total_num_words);
    }
}