Помощь - Поиск - Пользователи - Календарь
Полная версия: Удаление элементов из конца списка
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
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);
...

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.