Zjednodušení algoritmu pro mazání ze struktury – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Petr Zakopal
~ Anonymní uživatel
13 příspěvků
19. 1. 2013   #1
-
0
-

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. 

Nahlásit jako SPAM
IP: 94.112.188.–
Reklama
Reklama
JoDiK
~ Anonymní uživatel
981 příspěvků
19. 1. 2013   #2
-
0
-

#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...

Nahlásit jako SPAM
IP: 88.103.233.–
JoDiK
~ Anonymní uživatel
981 příspěvků
19. 1. 2013   #3
-
0
-

#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

Nahlásit jako SPAM
IP: 88.103.233.–
Petr Zakopal
~ Anonymní uživatel
13 příspěvků
19. 1. 2013   #4
-
0
-

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

Nahlásit jako SPAM
IP: 94.112.188.–
Petr Zakopal
~ Anonymní uživatel
13 příspěvků
19. 1. 2013   #5
-
0
-

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

Nahlásit jako SPAM
IP: 94.112.188.–
JoDiK
~ Anonymní uživatel
981 příspěvků
19. 1. 2013   #6
-
0
-

#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...

Nahlásit jako SPAM
IP: 88.103.233.–
Petr Zakopal
~ Anonymní uživatel
13 příspěvků
19. 1. 2013   #7
-
0
-

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.

Nahlásit jako SPAM
IP: 94.112.188.–
Mircosoft+1
Věrný člen
21. 1. 2013   #8
-
0
-

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.

Nahlásit jako SPAM
IP: 212.118.224.–
Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 7 hostů

Podobná vlákna

Zjednodušení kodu — založil Empty

Zjednodušení kódu — založil sXe

Zjednodušení kódu — založil Sergei

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý