Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Ада и другие языки _ Удаление элементов из конца списка

Автор: 18192123 16.05.2007 21:02

Как можно удалить определённое число элементов из конца односвязного линейного списка?

Автор: volvo 16.05.2007 21:13

Я тебе уже говорил: пробегать по ВСЕМУ списку, считать число элементов в нем, потом сначала отсчитывать столько, сколько должно остаться, а остальные - удалять...

Автор: 18192123 16.05.2007 22:19

Цитата(volvo @ 16.05.2007 18:13) *

Я тебе уже говорил: пробегать по ВСЕМУ списку, считать число элементов в нем, потом сначала отсчитывать столько, сколько должно остаться, а остальные - удалять...

Я не пойму, как это сделать...
попробывала иначе (берём 2 подряд элемента, пусть p1 и p2. продвигаем их по списку
пока p2 не станет нулём. значит,p1 - указатель на последний, этот
элемент можно удалять. и так 5 раз) - не получилось....ничего не выводится в файл ( а должны быть оставшиеся элементы)


for (i=1; i==3; i++) // удалим 3 последних элементов
{
p1=lst;
p2=p1->next;

while (p2)
{p1=p1->next;
p2=p2->next;}
free(p1);
p1 = NULL;
}

for (p1=lst;p1;) //вывод оставшихся элементов
{ fprintf(f,"%s\n",p1->number);
p1=(T=p1)->next;
free(T);

} lst=NULL;



Автор: volvo 16.05.2007 22:50

Цитата
Я не пойму, как это сделать...
Как-то вот так:
for(n = 0, p = lst; p; p = p -> next, n += 1);
for(p = lst; n > 5; p = p -> next);

// теперь p содержит адрес последнего элемента, который
// должен остаться в списке, это нужно, чтобы его next сбросить в NULL
// (предварительно запомнив где-то в доп. переменной), а потом просто
// проходить по отсеченному "хвосту" и удалять по одному элементу ...

Автор: 18192123 17.05.2007 0:50

Цитата(volvo @ 16.05.2007 19:50) *



// теперь p содержит адрес последнего элемента, который
// должен остаться в списке, это нужно, чтобы его next сбросить в NULL
// (предварительно запомнив где-то в доп. переменной), а потом просто
// проходить по отсеченному "хвосту" и удалять по одному элементу ...




for (n=0,p=lst;p;p=p->next,n+=1);
for(p=lst;n>5;p=p->next);
(T=p)->next=NULL;
for (T; T; T=T->next)
free(T);



Так? (по-моему у меня сново что-то не то...)

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

for (p1=lst;p1;) // lst - голова списка
{ fprintf(f,"%s\n",p1->number);
p1=(T=p1)->next;
free(T);

} lst=NULL;




Автор: volvo 17.05.2007 1:09

Цитата
по-моему у меня сново что-то не то
Естественно... Ты же удаляешь элемент T, а потом у уже удаленного переходишь по указателю next? Так нельзя... Надо так, например:

(T=p) -> next = NULL;
for(;T;) {
to_delete = T;
T = T -> next;
free(to_delete);
}

Автор: 18192123 17.05.2007 1:56

Цитата(volvo @ 16.05.2007 22:09) *

Естественно... Ты же удаляешь элемент T, а потом у уже удаленного переходишь по указателю next? Так нельзя... Надо так, например:

(T=p) -> next = NULL;
for(;T;) {
to_delete = T;
T = T -> next;
free(to_delete);
}


Ага..теперь поняла
А теперь, чтобы вывести оставшиеся элементы, я должна в цикле идти от головы списка до последнего оставшегося элемента (а что у нас после удаления выступает в качестве него?)

Автор: volvo 17.05.2007 2:00

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

Добавлено через 3 мин.
Стой, стой... Не так:

Цитата
(T=p) -> next = NULL;
, а вот так надо:

T = p -> next; // запоминаешь куда указывал предыдущий элемент
p -> next = NULL; // и потом уже указатель обнуляешь



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

Автор: 18192123 17.05.2007 2:42

Цитата(volvo @ 16.05.2007 23:00) *

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


т.е.

lst=p;
while (p)
{
fprintf(f, "%s",p->number);
p=p->next;
free(p);
}
lst=NULL;


???

Автор: volvo 17.05.2007 3:08

Ты постоянно наступаешь на те же грабли...

lst=p;
while (p)
{
fprintf(f, "%s",p->number);
T = p; // !!! ты должна СОХРАНЯТЬ значение...
p = p->next; // потом продвигать указатель...
free(T); // и только потом удалять сохраненное значение
}
lst=NULL;



Я больше не буду повторять эти прописные истины... Только в этом треде я написал правильный код минимум 4 раза, ты опять все переворачиваешь по-своему...

Автор: 18192123 17.05.2007 3:58

Цитата(volvo @ 16.05.2007 19:50) *

for(n = 0, p = lst; p; p = p -> next, n += 1);
for(p = lst; n > 5; p = p -> next);




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

Автор: 18192123 17.05.2007 5:16

сделала всё, как было объяснено, но оставшиеся элементы не выводятся (а должны).
В чём же может быть причина?

Автор: volvo 17.05.2007 5:53

Вот этот вариант только что у меня прекрасно отработал:

...
printf("!!! starting !!!\n");
root = read_list();
for(p = root; p; p = p -> next)
printf("%s\n", p -> number);

for(n = 0, p = root; p; p = p -> next, n += 1);
for(p = root; n > 6; p = p -> next) n -= 1;
T = p -> next;
p -> next = NULL;
for(;T;) {
T = (p = T) -> next;
free(p);
}


printf("!!!after deleting!!!\n");
for(p = root; p; p = p -> next)
printf("%s\n", p -> number);
...