Помощь - Поиск - Пользователи - Календарь
Полная версия: Удаление элементов в списках
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Tribunal
Мне нужно удалить из списка элементы, встречающиеся ровно 2 раза.

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

Код
var
   temp:integer;
   k:byte;
   p,h:t_ptr;
begin
t:=first;
while t^.next<>nil do
begin
   k:=0;
   p:=t^.next;
   while p<>nil do
    begin
      if p^.inf=t^.inf then begin
                            inc(k);
                            if k=2 then temp:=p^.inf;
                            end;
      p:=p^.Next;
    end;
   if k=2 then begin
               h:=first;
               while h<>nil do
                begin
                  if h^.inf=temp then dispose(h);
                  h:=h^.next;
                end;
               end;
   t:=t^.next;
end;
t:=first;
while t<>nil do
  begin
    writeln(t^.inf);
    t:=t^.next;
  end;
Бродяжник
if h^.inf=temp then dispose(h);
h:=h^.next;
Это как? Вначале удаляем элемент, а потом обращаемся к его полю? wacko.gif
И потом, где переключение ссылок?
Допустим, у меня есть A, В и С, объединенные в список. То есть A.next указывает на В, а В.next указывает на С. Я удаляю В, так ведь это же значит, что теперь A.next должно указывать на С. Где эта часть кода?
Tribunal
ну а если так?

Код
if k=2 then begin
               h:=first;
               while (h<>nil) and (h^.inf<>temp) do
                begin
                  dh:=h;
                  h:=h^.next;
                end;
               dh^.next:=h^.next;
               dispose(h);
               end;
volvo
Tribunal, проблема не только там, где тебе подсказал Бродяжник... Есть еще несколько очень узких мест в твоей программе... Смотри. Допустим, твой список целых чисел, имеет вид:
<1, 2, 3, 2, 4, 5, 3, 3>
Что происходит при применении твоего алгоритма? Пара двоек находится без проблем, об удалении сейчас не говорим... Допустим, они корректно удалились. Что будет дальше? Тройки. Вначале программа не будет ничего удалять, так как их тут три штуки (и это правильно, удалять их не надо...)

А вот потом, после просмотра 4 и 5, программка найдет только две тройки, и благополучно их удалит (ты же почему-то просматриваешь список с элемента, следующего за T; то, что перед T тоже могут быть уже пропущенные, и явно не удовлетворяющие условиям удаления элементы, ты выпустила из вида?)
Tribunal
да...
только как это исправить?

тогда получается нужно перебирать все элементы...?
а как это сделать?я пыталась,но не получилось.
поэтому сделала так.но и это не верно(
volvo
Задачка-то совсем не простая...
Я тут !smoke2.gif подумал, и вот что получилось (только протестируй, я тестировал на 3-х последовательностях, вроде работает):
type
t_ptr = ^TT;
TT = record
inf: integer;
next: t_ptr;
end;

var
i, n, k: integer;
disp: array[1 .. 2] of t_ptr;
first, t, p, h: t_ptr;

begin
first := nil;
readln(n);
while n > 0 do begin
new(p);
p^.next := first;
p^.inf := n;
first := p;
readln(n);
end;

t := first;
while t <> nil do begin
write(t^.inf:4);
t := t^.next;
end;
writeln;

t := first;
while t^.next <> nil do begin

p := first;

if first^.inf = t^.inf then k := 1 else k := 0;

while p^.next <> nil do begin
if p^.next.inf = t^.inf then inc(k);
p := p^.next;
end;

if k = 2 then begin

p := first;
i := 1;
while p^.next <> nil do begin
if p^.next.inf = t^.inf then begin

h := p^.next; p^.next := h^.next;
disp[ i ] := h; inc(i);

end;
p := p^.next;
end;

if first^.inf = t^.inf then begin
p := first;
first := first^.next;
disp[ i ] := p;
end;

for i := 1 to 2 do
dispose(disp[ i ]);
t := first;

end
else t := t^.next;
end;


t := first;
while t <> nil do begin
write(t^.inf:4);
t := t^.next;
end;
writeln;

end.

Тестировалось на этом (вводи без символов, только числа, после каждого - Enter):
1 тест: <1, 2, 3, 2, 4, 5, 3, 3, 7, 0>
2 тест: <2, 1, 2, 3, 2, 4, 5, 3, 3, 7, 5, 0>
3 тест: <2, 1, 2, 3, 2, 4, 5, 3, 3, 7, 8, 8, 5, 0>

Вопрос на засыпку: что будет, если в исходном списке меньше 2-х элементов? И как этого избежать?
Tribunal
спасибо большое за помощь...но возникли проблемы.
получившаяся программа работает не всегда.
я рэндомом задавала элементы списка.
и в некоторых случаях...причем совершенно различных
выдается ошибка на строке
Код
while p^.next <> nil do


почему это может происходить?не подскажете?
буду очень благодарна за помощь
volvo
Приводи содержимое списка перед попыткой удаления, иначе ничего сказать не могу... Все зависит от данных.

Кстати, какая ошибка выдается, и в каком именно месте? Эта строка встречается в нескольких местах программы...

P.S. Желательно привести также и тот кусок программы, где ты заполняешь список, чтобы быть уверенным, что ничего опасного там не происходит...
Tribunal
ошибка invalid pointer operation.

вот на таких,например,списках возникает такая ошибка:
1 9 9 7 4 -3
6 9 9 7 -1 5 -4 -5
4 9 -9 -9 -5 0 1 8 5 1

правда,делаю я в Delphi.
то есть программа компилируется.
даже иногда правильно работает.
и когда я отменяю эту ошибку,она в первом случае удаляет только один элемент из пары,а во втором всю пару
(например,здесь 4 9 -9 -9 -5 0 1 8 5 1)

и при ошибке выполнение программы останавливается
на этом куске
p := first;
i := 1;
while p^.next <> nil do begin
if p^.next.inf = t^.inf then begin


и вот кусок программы,где я заполняю список:
var
n,i:byte;
begin
randomize;
read(n);
new(first);
first^.next:=nil;
first^.inf:=random(20)-10;
for i:=1 to n-1 do
begin
new(t);
t^.inf:=random(20)-10;
t^.next:=nil;
t^.next:=first;
first:=t;
end;
end;
volvo
Да... Глюк в программе. Попробуй добавить Else вот тут:
    if k = 2 then begin

p := first;
i := 1;
while p^.next <> nil do begin
if p^.next.inf = t^.inf then begin

h := p^.next; p^.next := h^.next;
disp[ i ] := h; inc(i);

end
else p := p^.next; { <--- Здесь ... }
end;


Все приведенные тобой примеры ДО исправления не обрабатывались, как положено. После исправления удаляются все парные элементы (проверял в FPC, так что погоняй на Дельфях)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.