Dynamické datové struktury – Pascal – Fórum – Programujte.com

Ahoj,

nemá někdo nějaký dobrý materiál o ukazatelých a dynamických datových strukturách? Aby to nejlépe pochopil i samouk. Díky moc :)

Tady je jeden trochu starší a dost zhuštěný, ale mělo by tam být všechno:

http://mircosoft.mzf.cz/texty/UKAZ.TXT

#1 Boi
Samoukovi bych doporučil, aby se místo zastaralého způsobu práce s dynamickými strukturami věnoval objektům. Je to totéž, jen je tam vyšší úroveň abstrakce.

#3 Kit
To by mě docela zajímalo. Jak se dá dynamická struktura nahradit objektem?

#4 Mircosoft
Nikde nevidím tu dynamickou strukturu, na kterou se ptáš, ale ve vyšších jazycích už dynamické struktury nenajdeš - jsou nahrazeny právě objekty a kolekcemi. Uvnitř to jsou stále dynamické struktury, ale to už nikoho nezajímá, protože k nim není přímý přístup.

#5 Kit

Aha, takže použít hotový objekt je moderní, zatímco zkoušet takový objekt vytvořit je zastaralé. Už to chápu :-).

#6 Mircosoft
Není to zastaralé, ale je to low-level. To je trošku rozdíl.

#7 Kit
Asi je to low level... ale hard level pro mě :D 

Musím říct, že je to zatím nejtěžší část, kterou jsem nějak moc dobře ještě nepochopil :(

Jak vypadá spoják chápu.. přidat do seznamu prvek, přečíst seznam, vypsat určitý prvek OK... ale udělat s tím nějaké operace např. smaž určitý prvek, připoj prvek za určitý prvek, rozděl seznam, otoč seznam atd... jsem KO..

#8 Boi

Zkus si to poskladat z karticek, ktere budes ukladat na ocislovane pozice (= Adresa v pameti) nekde jinde na velkem papiru. Na kazdem papirku muzes mit nejake data + adresu dalsiho papirku (cislo pozice na tom velkem papiru).

Ukazatel je pak adresa, na ktere se nachazi listek na papire. Nula znamena ze tam nic neni. Jinak v programovani je to promenna, kam se vejde adresa na libovolne misto v pameti.

Budes mit jeden ukazatel na zacatek, a na kazdem listecku budes mit take ukazatel na dalsi listecek.

A ted si zkus udelat treba zasobnik. Musis samozrejme pocitat s tim, ze pocitac nevidi jako clovek a vi jen, kde je ulozena adresa prvniho listku. Take nemuze delat vic veci najednou, pokud chce nejakou hodnotu pouzit vickrat, musi si ji pamatovat, a tak dale.

Ok, tak jsem došel k problému...

Nejsem schopen vytvořit proceduru pro přidání prvku na konec seznamu..

Proceduru, která přidá prvek na začátek seznamu chápu a nepřijde mi nijak složitá.

procedure Pridej(var Seznam: Spoj; X: Integer);
var Novy: Spoj;
begin
	new(Novy);
	Novy^.Hodnota := X;
	Novy^.Dalsi := Seznam;
	Seznam := Novy;
end;

Díky

end;

#10 Boi
Je to pokazde stejne: prochazis prvky a jak narazis na posledni prvek (nema naslednika), tak do nej vlozis odkaz na dalsi. Musi se akorat dat pozor, aby ten prvni vubec existoval.

Pojem dynamicka struktura chapu jako v pascalu record. Coz moc dynamicke neni, pac se to musi definovat predem, ale budiz.

google = pascal record simple example
Hned prvni stranka je
http://pascal-programming.info/lesson11.php
Vemu si ten uplne posledni nejdelsi priklad.
- Str25 ja struktura string delky 25
- TBookRec je struktura asociativni pole s nekolika prvky zalozenymi na strukture Str25 (v jinem jazyce nazvane object nebo class)
- bookRecArray je struktura pole zalozene na strukture TBookRec;
- kdyz pak do toho pridavam, tak
bookRecArray[i].Title = ...
Cili, to, co ty muzes ted hodit pres ukazatel je podle meho spis cele to pole bookRecArray. Pripadne by mozna slo vsechno, ale bylo by to asi narocne na zatez pri vetsim poctu prvku, treba 50.000.

google = pascal new record example (nezda se mi tvuj zapis pouziti new)
http://www.tutorialspoint.com/…_records.htm
na konci stranky je takovy dlouhy example

program exRecords;
type
BooksPtr = ^ Books;
Books = record
   title: packed array [1..50] of char;
   author: packed array [1..50] of char;
   subject: packed array [1..100] of char;
   book_id: longint;
end;

var
  (* Declare Book1 and Book2 of pointer type that refers to Book type *)
   Book1, Book2: BooksPtr; 

begin
   new(Book1);
   new(book2);
   
   (* book 1 specification *)
   Book1^.title  := 'C Programming';
   Book1^.author := 'Nuha Ali '; 
   Book1^.subject := 'C Programming Tutorial';
   Book1^.book_id := 6495407;
   
   (* book 2 specification *)
   Book2^.title := 'Telecom Billing';
   Book2^.author := 'Zara Ali';
   Book2^.subject := 'Telecom Billing Tutorial';
   Book2^.book_id := 6495700;
   
   (* print Book1 info *)
   writeln ('Book 1 title : ', Book1^.title);
   writeln('Book 1 author : ', Book1^.author);
   writeln( 'Book 1 subject : ', Book1^.subject);
   writeln( 'Book 1 book_id : ', Book1^.book_id);
   
   (* print Book2 info *)
   writeln ('Book 2 title : ', Book2^.title);
   writeln('Book 2 author : ', Book2^.author);
   writeln( 'Book 2 subject : ', Book2^.subject);
   writeln( 'Book 2 book_id : ', Book2^.book_id);
   
   dispose(Book1); 
   dispose(Book2);
end.

Seznam := Novy;
To nepridava na zacatek seznamu, ale prepisuje celou promeneou Seznam obsahem promenne Novy. Abys to pridaval do pole, musel by byt seznam pole a muselo by to byt zapsane tak, jak jsem psal na zacatku bookRecArray[i] = novy

#10 Boi
V nejjednodušším případě to může vypadat nějak takhle. Máš nový prvek:

new(novy);
novy^.hodnota:=neco;
novy^.dalsi:=nil;

Projdi si seznam až k poslednímu prvku (Posledni je pomocná proměnná):

posledni:=prvni;
while posledni^.dalsi<>nil do posledni:=posledni^.dalsi;

A za ten poslední prvek napoj ten nový:

posledni^.dalsi:=novy;

Hotovo.

Předpokládám, že konec seznamu si značíš nulovým ukazatelem na další prvek (hodnota nil).

Kdyby to mělo fungovat obecně, musel by se ošetřit i případ, kdy je seznam prázdný. Třeba takhle:

if prvni=nil then prvni:=novy
             else begin
                  ...nalezení posledniho prvku...
                  posledni^.dalsi:=novy;
                  end;