опять односвязанный список - Компьютерные священные войны

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

E>Можно просто найти конец и уничтожить, а потом уничтожать себе как хочешь.

Если у меня есть указатели на начало и конец, то я обойдусь одним проходом (собственно уничтожение). Тебе понадобится два прохода — первый проход в поисках предпоследнего элемента, второй -уничтожение.

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

PD>Если у меня есть указатели на начало и конец, то я обойдусь одним проходом (собственно уничтожение). Тебе понадобится два прохода — первый проход в поисках предпоследнего элемента, второй -уничтожение.

Ну и что?

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

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

PD>>Если у меня есть указатели на начало и конец, то я обойдусь одним проходом (собственно уничтожение). Тебе понадобится два прохода — первый проход в поисках предпоследнего элемента, второй -уничтожение.

E>Ну и что?

Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

>> #define SWAP(x, y)\
.>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.

предложи другой вариант без дополнительной памяти. даже без О(1).

.>>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.

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

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

PD>Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

Не всегда. Иногда "проще" лучше, чем "быстрее"

Всё равно в задаче другое просили, на самом деле.

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

E>>Не понятно, кстати, зачем всё это. Если уж мы нашли последний в списке, то можно бы его сразу грохнуть. Зачем тащить куда-то?
M>я забил на время (о нем ничего не сказано в условии), и пытался минимизировать затраты памяти. в иделе сведя их к 0.
Это я понял. Но я не понял, зачем свопы-то?

типа

bool delete_next( node* n )
{
    if( n == 0 || n->next == 0 ) {
        return false;
    }
    assert( n->next->next == 0 );
    delete n->next;
    n->next = 0;
    return true;
}

node* find_pre_last( node* n )
{
    assert( n != 0 );
    if( n->next == 0 ) {
        return 0;
    } 
    while( n->next->next != 0 ) {
        n = n->next;
    }
    return n;
}

bool delete_last( node* n ) { return delete_next( find_pre_last( n ) ); }

void destroy_list( node* n )
{
    if( n == 0 ) {
        return;
    }
    while( delete_last( n ) ) {
    }
    assert( n->next == 0 );
    delete n;
}

On 14/08/10 13:39, Muxa wrote:

> .>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и
> xor-магией.
> предложи другой вариант без дополнительной памяти. даже без О(1).
Не понял. А чем вариант Кодта не устраивает?

Posted via RSDN NNTP Server 2.1 beta

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

PD>>Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

E>Не всегда. Иногда "проще" лучше, чем "быстрее"

Хм, а чем твое решение лучше ?

>> предложи другой вариант без дополнительной памяти. даже без О(1).
.>Не понял. А чем вариант Кодта не устраивает?

On 14/08/10 19:43, Muxa wrote:

>> > предложи другой вариант без дополнительной памяти. *даже без О(1)*.
> .>Не понял. А чем вариант Кодта не устраивает?
Не понял. Это как? Посмотри определение O-нотации.

Posted via RSDN NNTP Server 2.1 beta

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

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

PD>>>Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

E>>Не всегда. Иногда "проще" лучше, чем "быстрее"

PD>Хм, а чем твое решение лучше ?
Очевидно, что ничем. Просто концептуально проще. Например со списком можно работать не нарушая его инвариантов, то есть его обычными методами/функциями

.>Не понял. Это как? Посмотри определение O-нотации.
это значит не используя дополнитольно ни одного байта (костантного значения дополнительной памяти).
т.е. имея только список и работая тольо с ним.

On 14/08/10 22:04, Muxa wrote:

> .>Не понял. Это как? Посмотри определение O-нотации.
> это значит не используя дополнитольно ни одного байта (костантного
Так это какое O?

> значения дополнительной памяти).
0 байт — тоже константное значение.

> т.е. имея только список и работая тольо с ним.
Приведи хоть один пример такого алгоритма.

Posted via RSDN NNTP Server 2.1 beta

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

PD>>Хм, а чем твое решение лучше ?
E>Очевидно, что ничем. Просто концептуально проще. Например со списком можно работать не нарушая его инвариантов, то есть его обычными методами/функциями

Уничтожить его надо, а не работать. После чего не останется ни списка, ни инвариантов

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

PD>Уничтожить его надо, а не работать. После чего не останется ни списка, ни инвариантов

Ну код разрушения тоже может быть обычным, а не каким-то особенным...

Скажем, если у списка есть методы delete_last и delete_first
то код может быть такой:

void list::delete_all() 
{
    if( !is_empty() ) {
        for( delete_last(); !is_empty(); delete_first() ) {
        }
    }
}

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

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

PD>>Уничтожить его надо, а не работать. После чего не останется ни списка, ни инвариантов

E>Ну код разрушения тоже может быть обычным, а не каким-то особенным...

О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.

.>Так это какое O?
О-нотация.

.>0 байт — тоже константное значение.
хорошо, ноль дополнительных байт можно использовать. больше — нельзя.

.>Приведи хоть один пример такого алгоритма.
проход по списку до конца:

while (e->next)
   e = e->next;

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

.>>0 байт — тоже константное значение.
M>хорошо, ноль дополнительных байт можно использовать. больше — нельзя.

.>>Приведи хоть один пример такого алгоритма.
M>проход по списку до конца:
M>

M>while (e->next)
M>   e = e->next;
M>

е занимает 0 байт?

	От:	Pavel Dvorkin
	Дата:	14.08.10 07:58
	Оценка:

	От:	Erop
	Дата:	14.08.10 08:11
	Оценка:

	От:	Pavel Dvorkin
	Дата:	14.08.10 09:17
	Оценка:

	От:	Muxa
	Дата:	14.08.10 10:39
	Оценка:

	От:	Muxa
	Дата:	14.08.10 10:40
	Оценка:

От:	samius	http://sams-tricks.blogspot.com
Дата:	15.08.10 12:03
Оценка: