Память с использованием списков - Домашнее задание

Question

Так что в основном я борюсь с вопросом 5 в этом задании, http://www.student.cs.uwaterloo.ca/~cs136/assignments/a5/

Нам в основном даны функции, которые действуют как функции списка схем, и в вопросе 5 я должен создать функцию с именем iappend, которая добавляет два списка. Это мой код, и он, кажется, работает.

ilist iappend(ilist il1, ilist il2) {
    ilist acc = iempty();
    ilist acc1 = iempty();
    ilist a;
    while (!iempty_huh(il1)) {
        acc1 = icons(ifirst(il1), acc1);
        il1 = irest(il1);
    }
    while (!iempty_huh(il2)) {
        acc1 = icons(ifirst(il2), acc1);
        il2 = irest(il2);
    }
    a = acc1;
    while (!iempty_huh(acc1)) {
        acc = icons(ifirst(acc1), acc);
        acc1 = irest(acc1);
    }
    idelete(a);
    return acc;
}

Новая проблема, может ли кто-нибудь помочь мне написать код, чтобы я не создавал временный список? Мне нужно закодировать его таким образом, чтобы я не использовал idelete .... любые предложения помогли бы:)

Answer 1

По сути, вы должны имитировать рекурсивное решение, используя вспомогательные списки в качестве стека, и у вас есть эта идея.Но чтобы быть более эффективным, попробуйте это.Сначала сделайте обратную копию первого списка, просто с помощью простого пока не пустого цикла.Затем продолжите расширение этой перевернутой копии со вторым списком, снова с помощью простого пока не пустого цикла.Теперь у вас есть обратная копия двух списков, добавленных вместе: (обратная секунда) || (обратная первая);сделайте копию с обратным обращением (т. е. в правильном порядке) с помощью еще одного пока не пустого цикла.Вы должны быть в состоянии сделать это без каких-либо тестов «если» - циклы while должны правильно обрабатывать пустые углы списка.

Кроме того, не удаляйте аргументы - это вызывает проблемы.Но, конечно, удалите обратную копию, сделанную первыми двумя циклами и использованную третьим;по сути это стек рекурсивной версии.

Answer 2

Две подсказки: (щелчок, нажатие), одна петля

дополнительная подсказка

если iList является структурой {item, next_iList_ptr}, вы можете скопировать свое значение и указать следующий узел для следующей итерации в списке. переключиться на второй после первого.

Answer 3

Грубо говоря: переберите первый список, сделав копию, и запомните последнюю ячейку копии; затем создайте копию второго списка из этого.