Удаление элементов в списках Опции

[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;

Сообщение отредактировано: Tribunal - 26.04.2006 14:53

[Бродяжник]

if h^.inf=temp then dispose(h);
h:=h^.next; 

Это как? Вначале удаляем элемент, а потом обращаемся к его полю?
И потом, где переключение ссылок?
Допустим, у меня есть 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]

да...
только как это исправить?

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

Сообщение отредактировано: Tribunal - 26.04.2006 20:26

[volvo]

Задачка-то совсем не простая...
Я тут подумал, и вот что получилось (только протестируй, я тестировал на 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, так что погоняй на Дельфях)