Zjednodušení algoritmu pro mazání ze struktury – Pascal – Fórum – Programujte.com

Dobrý den,

ustavičně uvažuji nad zjednodušením jednoho dílčí procedury, kterou jsem napsal. Už několik hodin hledám způsoby jak více a více zredukovat časovou složitost následujícího kódu, aby se neprováděli žádné akce, které nejsou nezbytné a také se snažím doladit ho do spolehlivé podoby tak, aby nic nemohlo způsobit pád programu. Myslím, že algoritmus už je vcelku obstojný, ale i přes to bych ho chtěl dát i sem, zda vaše zkušenější oko neuvidí nějaké lepší řešení.

Jedná se o algoritmus pro odebrání prvku ze struktury. Tady je zdrojový kód:

type UkPrvek = ^Prvek;
      Prvek = record
        Data: byte;
        Dalsi: UkPrvek;
      end; 
      Zasobnik = record
        Zac, Kon: UkPrvek;
      end;
      
  procedure Odeber(var Z: Zasobnik; D: byte);
  var Poz, Pom: UkPrvek;
      Zarazka : boolean;
  begin
  Zarazka:=false;
    if not Empty(Z) then
      with Z do begin
        Poz:=Zac;
        if ( Poz^.Data = D ) then begin
          Zac:=Zac^.Dalsi;
          dispose(Poz);  
        end else
          while ( Poz^.Dalsi <> nil ) and ( Zarazka = false ) do begin
            if ( Poz^.Dalsi^.Data = D ) then begin
              Pom:=Poz^.Dalsi;
              if ( Pom = Kon ) then begin
                Kon:=Poz;
                Poz^.Dalsi:=nil;
              end else begin
                Poz^.Dalsi:=Pom^.Dalsi;
                Poz:=Poz^.Dalsi;
                Zarazka:=true;
              end;
              dispose(Pom);
            end else Poz:=Poz^.Dalsi; 
          end; 
      end;
  end;

Nejvíce mě na algoritmu trápí to, že jsem použil Zarazka : boolean; a přemýšlím nad tím, jak bez tohoto prvku zajistit to, aby v případě, že prvek naleznu se neprocházel zbytek struktury aniž bych použil break, nebo podobné zlo. 

#1 Petr Zakopal
Nezkoumal jsem ten algoritmus (zatím), ale z principu - má-li to být struktura Zásobník, tak ten přece má mít pouze jeden způsob "mazání" a to je odebrání z vrcholu zásobníku.

Mazání kdekoliv uprostřed seznamu je možné jen u struktury "seznam".

Takže buď to máš špatně pojmenované, nebo děláš něco, co bys neměl...

#1 Petr Zakopal
Jinak ten algoritmus se zdá v pořádku. Kdo ti řekl, že break je zlo? Nechceš.li požít break, nezbyde než použít zdvojenou podmínku tak jak to máš.

Jen můžeš zjednodušit ten zápis - je zbytečné do podmínky psát zarazka=false, stačí napsat not zarazka, případně pokud použiješ obrácenou logiku, tak ještě jednodušeji na začátku nenasel=true, když najdeš tak nenasel=false a do podmínky cyklu napsat while ( Poz^.Dalsi <> nil ) and nenasel

#2 JoDiK
využívám pouze zásobníkového vkládání. mazání provádím podle potřeb programu

děkuji... a co do stability algoritmu...nevidíte v něm něco co by jej mohlo shodit?

#5 Petr Zakopal
To zjistí testování programu se všemi možnými kombinacemi...

prázdný seznam, hledaná hodnota na začátku/na konci, uprostřed...

Ještě pro jistotu bych chtěl zkonzultovat funkci:

  function Empty(var Z: Zasobnik): boolean;
  begin
    Empty:=Z.Zac=nil;
  end;

Tato funkce je využita i v proceduře uvedené výše. Pouze bych si chtěl potvrdit mé tvrzení: "Není nutno kontrolovat, zda i proměnná Kon je rovna nil, protože pokud je proměnná Zac rovna nil není možné, aby proměnná Kon nebyla také nil" je toto tvrzení pravdivé? Já myslím, že je, ale stejně bych to rád slyšel i od někoho zkušenějšího.

Na test prázdnosti stačí zkontrolovat začátek. Kon vlastně ani není potřeba, konec seznamu poznáš podle nulového ukazatele Dalsi.

V tom tvém mazacím algoritmu chybí vynulování ukazatele Kon v případě, kdy mažeš jediný prvek z jednoprvkového seznamu. Potom bych v tom cyklu prohodil pořadí podmínek - napřed test Zarážky, až potom dat za Poz - protože jestli už mazání proběhlo, není už v Poz žádná smysluplná adresa. Na PC ti to projde (čtení nealokované paměti nevadí), ale třeba takový mainframe by ti program okamžitě shodil. Jinak se zdá, že je všechno v pořádku.

Zjednodušovat by se dalo. Zarážku můžeme vyhodit, stejně tak i úvodní test prázdnosti zásobníku a vyjít nám může třeba tohle:

procedure Odeber(var Z: Zasobnik; D: byte);
var Poz, Pom: UkPrvek;
Begin
with Z do
 begin
 Poz:=Zac;
 while (poz<>nil)and(poz^.data<>D) do begin
                                      pom:=poz;
                                      poz:=poz^.dalsi;
                                      end;
 if poz<>nil then begin
                  if poz=zac then begin
                                  if kon=zac then kon:=nil;
                                  Zac:=Zac^.Dalsi;
                                  end
                             else begin
                                  pom^.dalsi:=poz^.dalsi;
                                  if kon=poz then kon:=pom;
                                  end;
                  dispose(poz);
                  end;
 end;
End;

Ale asi by to šlo i jinak.