На собеседовании задали задачку:
есть односвязанный список, необходимо его очистить эффективно начиная с конца без привлечения доплонительных внешних ресурсов (например дополнительной памяти).

сколько я не ломаю голову — без привлечения внешних ресурсов очистить это список не поулчается — только бегать по нему от начала до конца.

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

2. развернуть список и удалить его с головы. но здесь два момента — первый развернув список мы получаем новый объект и насколько корректно (формально) это решение — уже ставит под вопрос этот подход, но это не важно (практически задачу этот подход решает), вопрос два — как развернуть односвязанный список не прибегая к дополнительным ресурсам (памяти)?

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

собственно интересно, а есть ли фокус как обернуть односвязанный список без применения внешних ресурсов?

Здравствуйте, ssp_alex, Вы писали:

_>На собеседовании задали задачку:
_>есть односвязанный список, необходимо его очистить эффективно начиная с конца без привлечения доплонительных внешних ресурсов (например дополнительной памяти).

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

Условие задачи позволяет использование памяти в объеме O(C). Запрет идет на объем памяти, измеряющийся некой неконстантной функцией от размера списка, т.е. O(n), O(Log n) и т.п.

Т.е. на два узла память по-любому найдется.

Здравствуйте, ssp_alex, Вы писали:

_>2. развернуть список и удалить его с головы. но здесь два момента — первый развернув список мы получаем новый объект и насколько корректно (формально) это решение — уже ставит под вопрос этот подход, но это не важно (практически задачу этот подход решает), вопрос два — как развернуть односвязанный список не прибегая к дополнительным ресурсам (памяти)?

_>сколько я голову не ломаю, но без дополнительных переменных — односвязанный список не перевернуть, надо по любому хранить в памяти адреса двух узлов.
Без дополнительной памяти почти всегда означает «без дополнительной памяти по объёму зависящей от входных данных», то есть две переменные создать можно.

Здравствуйте, RomikT, Вы писали:

RT>Здравствуйте, ssp_alex, Вы писали:

_>>2. развернуть список и удалить его с головы. но здесь два момента — первый развернув список мы получаем новый объект и насколько корректно (формально) это решение — уже ставит под вопрос этот подход, но это не важно (практически задачу этот подход решает), вопрос два — как развернуть односвязанный список не прибегая к дополнительным ресурсам (памяти)?

_>>сколько я голову не ломаю, но без дополнительных переменных — односвязанный список не перевернуть, надо по любому хранить в памяти адреса двух узлов.
RT>Без дополнительной памяти почти всегда означает «без дополнительной памяти по объёму зависящей от входных данных», то есть две переменные создать можно.

ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, ssp_alex, Вы писали:

_>>На собеседовании задали задачку:
_>>есть односвязанный список, необходимо его очистить эффективно начиная с конца без привлечения доплонительных внешних ресурсов (например дополнительной памяти).

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

S>Условие задачи позволяет использование памяти в объеме O(C). Запрет идет на объем памяти, измеряющийся некой неконстантной функцией от размера списка, т.е. O(n), O(Log n) и т.п.

S>Т.е. на два узла память по-любому найдется.

да вот фиг знает что имелось ввиду под запретом на доп. память (вернее я выяснил, что имелось именно то что вы написали, но теперь уже поздно), но задачи похожие мне попадались и если в ТЗ сказанно нет доп памяти — занчит ее нет (не все пишут для PC и под NIX-ы, есть еще например микроконтроллеры и специализированные процессоры), а если в описи передаваемого оборудования есть виртуальные машины — то их надо передать на склад.

Здравствуйте, ssp_alex, Вы писали:

_>ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

Если пишешь на асме, то эти доп. переменные -- регистры. А если на языке высокого уровня, то это некая абстракция. Тот же С может положить их в регистр, например.

_>ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

Это вы умозрительно или по опыту разработки АБС или "системы наведения спутника на цель" ? В риалтаймовых системах как две последние, нет такой вещи как "дефицит памяти", т.к. динамическое распределение памяти в реалтайме практически никогда недопустимо. А то, что память для алгоритма --- константная,
означает, что ее можно распределить во время компиляции. Другими словами --- отмазки это все.

Здравствуйте, dmz, Вы писали:



_>>ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

dmz>Это вы умозрительно или по опыту разработки АБС или "системы наведения спутника на цель" ? В риалтаймовых системах как две последние, нет такой вещи как "дефицит памяти", т.к. динамическое распределение памяти в реалтайме практически никогда недопустимо. А то, что память для алгоритма --- константная,
dmz>означает, что ее можно распределить во время компиляции. Другими словами --- отмазки это все.

угу. Посыпая голову пеплом, пошел повторять Мат.Часть.

_>1. рекурсивно пройти по списку запоминая узлы, а потом удалить список. но здесь нарушение условия задачи — сохранение информации об адресах узлов это уже привлечение дополнительной памяти, так что этот вариант отпадает.
зачем в этом случае запоминать что-то?

void free_list(elem){     // очистить список начиная с элемента elem, но в обратном порядке
  if (el == NULL)         // если конец списка
    return;               // выход
  free_list(elem.next);   // рекурсивно очищаем начиная с elem.next (след. элемент списка)
  free(elem);             // очищаем текущий
}

// где-то в main
  free_list(list.head);

Здравствуйте, Muxa, Вы писали:

_>>1. рекурсивно пройти по списку запоминая узлы, а потом удалить список. но здесь нарушение условия задачи — сохранение информации об адресах узлов это уже привлечение дополнительной памяти, так что этот вариант отпадает.
M>зачем в этом случае запоминать что-то?
M>

M>void free_list(elem){     // очистить список начиная с элемента elem, но в обратном порядке
M>  if (el == NULL)         // если конец списка
M>    return;               // выход
M>  free_list(elem.next);   // рекурсивно очищаем начиная с elem.next (след. элемент списка)
M>  free(elem);             // очищаем текущий
M>}

M>// где-то в main
M>  free_list(list.head);
M>

Внимание, вопрос! А стек для рекурсии у нас бесплатный, да?

К>Внимание, вопрос! А стек для рекурсии у нас бесплатный, да?
у нас да, у вас — хз.
(думаем дальше)

Здравствуйте, Muxa, Вы писали:

К>>Внимание, вопрос! А стек для рекурсии у нас бесплатный, да?
M>у нас да, у вас — хз.

M>(думаем дальше)

А что тут думать. Реверсируем список по живому (т.е. меняем указатели в узлах списка) и затем коцаем с головы.

К>А что тут думать. Реверсируем список по живому (т.е. меняем указатели в узлах списка) и затем коцаем с головы.
ну придумай как это сделать без доп. памяти.
мой вариант пока что требует дополнительно память под две переменные (длина списка — int, переменная цикла — int) + одна переменная на стэке — указатель на элемент списка.

#include <stdio.h>
#include <stdlib.h>

struct list_elem {
    list_elem *next;
    int *value;
};

#define SWAP(x, y)\
        (x).value = (int *)((int)(x).value ^ (int)(y).value);\
        (y).value = (int *)((int)(x).value ^ (int)(y).value);\
        (x).value = (int *)((int)(x).value ^ (int)(y).value);

void free_elem(list_elem *e){
    free(e->value);
}

void shift_list(list_elem *e){
    while(e->next != NULL){
        SWAP(*e, *(e->next));
        e = e->next;
    }
}

int main(int argc, char* argv[]) {
    // формируем список
    list_elem e5; e5.next = NULL; e5.value = (int*)malloc(sizeof(int)*1); *e5.value = 5;
    list_elem e4; e4.next = &e5;  e4.value = (int*)malloc(sizeof(int)*1); *e4.value = 4;
    list_elem e3; e3.next = &e4;  e3.value = (int*)malloc(sizeof(int)*1); *e3.value = 3;
    list_elem e2; e2.next = &e3;  e2.value = (int*)malloc(sizeof(int)*1); *e2.value = 2;
    list_elem e1; e1.next = &e2;  e1.value = (int*)malloc(sizeof(int)*1); *e1.value = 1;
    list_elem e0; e0.next = &e1;  e0.value = (int*)malloc(sizeof(int)*1); *e0.value = 0;
    list_elem *e = &e0;

    int n = 5; // ну, или находим сколько у нас элементов в списке (-1), если это заранее неизвестно

                                            // магия
    while (e->next != NULL){
        for (int i = 0; i < n; i++)         // этот цикл поднимает последний элемент списка в начало
            shift_list(e);                  // путем циклического сдвига списка

        free_elem(e);                       // освобождаем поднятый элемент

        e = e->next;                        // переходим к следующему
        n--;
    }
    free_elem(e);                           // освобождаем послдений оставшийся

    return 0;
}

Здравствуйте, Muxa, Вы писали:

К>>А что тут думать. Реверсируем список по живому (т.е. меняем указатели в узлах списка) и затем коцаем с головы.
M>ну придумай как это сделать без доп. памяти.

"Без доп.памяти" — это, всё-таки, фикция.

С единичной памятью (два дополнительных указателя) — элементарно. За линейное время, в отличие от твоего квадратичного.

Node* pop(Node*& head)
{
  Node* node = head;
  head = head->next;
  return node;
}
void push(Node*& head, Node* node)
{
  node->next = head;
  head = node;
}

void free_from_tail(Node* head)
{
  Node* rhead = NULL;
  while(head)  push(rhead, pop(head));
  while(rhead) free(pop(rhead));
}

К>За линейное время, в отличие от твоего квадратичного.
кубического.

Здравствуйте, Muxa, Вы писали:

К>>За линейное время, в отличие от твоего квадратичного.
M>кубического.

Facepalm! Действительно, кубического.

Здравствуйте, ssp_alex, Вы писали:

_>есть односвязанный список, необходимо его очистить эффективно начиная с конца без привлечения доплонительных внешних ресурсов (например дополнительной памяти).

Если именно так сформулировано, то очень просто

Замыкаем список в кольцо и уничтожаем элементы, начиная с последнего.

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

On 13/08/10 16:42, Muxa wrote:
> #define SWAP(x, y)\
Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.

Здравствуйте, Pavel Dvorkin, Вы писали:

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

Зачем так париться-то?
Можно просто найти конец и уничтожить, а потом уничтожать себе как хочешь.

Только я бы сказал, что это решение соответствует формулировке "начав с конца", а не "начиная с конца"...

Здравствуйте, ., Вы писали:

.>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.
Не понятно, кстати, зачем всё это. Если уж мы нашли последний в списке, то можно бы его сразу грохнуть. Зачем тащить куда-то?