#1 08. 02. 2012 19:29
Pascal - Lineární spojový seznam
Dobrý večer,
potřebuji pomoc.
Mám v Pascalu lineární spojový seznam který obsahuje několik atributů, jeden z atributů je věk. Potřebuji vytvořit proceduru která vezme ten věk uloží ho do proměnné (nejlépe součást nového seznamu) k proměnné přiřadí počítadlo, vezme další vek uloží jako další položku nového seznamu a opět přiřadí počítadlo, vezme další věk zkontroluje jestli není již v novém seznamu pokud je navýší počítadlo, pokud není přidá další položku do seznamu.
Výstupní nový seznam by měl vypadat takto:
Vek Pocet
20 5
23 3
14 1
38 2
Seznam nemá byt seřazený má být tvořen tak jak to postupně bud číst data z originálního seznamu.
Principielně vím jak to má fungovat, jen nevím které funkce na to použít.
Děkuji všem za rychlou a užitečnou odpověď
P.S.: Google mi žádnou takovou "statistiku výskytu" pro linearni seznamy nenašel.
Offline
- (téma jako nevyřešené označil(a) Krek)
#2 09. 02. 2012 18:37
Re: Pascal - Lineární spojový seznam
Počítám, že strukturou nového LSS je záznam (record), který obsahuje 3 údaje: věk, počet výskytů a ukazatel na další zázam (tedy LSS je jednosměrný).
Jelikož ten seznam věků není nijak setříděný, nezbývá, než v každé iteraci, kdy procházím starý LSS, projíždět nový spoják od začátku a hledat koincidenci (shodu), pokud shodu nenajdu (ukazatel na další prvek už je NIL), je třeba založit nový záznam a zapojit ho do nového LSS.
V tělu procedury tak principielně bude pouze cyklus, který bude procházet existující spoják, a v tomto cyklu jednoduché porovnávání (if-else), popřípadě volání jiné procedury na přidání nového prvku do LSS nebo přímý zápis (praktičtější) tohoto přidání v těle.
Offline
#3 10. 02. 2012 17:00
- RePRO
- Místo: Jihlava
- Příspěvky: 363
- Škola: AI VŠPJ (09-12, Bc.)
- Pozice: programátor
- Reputace: 11
- Web
Re: Pascal - Lineární spojový seznam
Zdravím,
algoritmus bych řešil následovně (tak, jak píše kolega Juxtapose).
Nechť je spojový seznam nesetříděn, to nám ale nevadí. Každý prvek v sobě uchovává následující atributy:
- věk
- počet výskytů
- ukazatel na další prvek
Algoritmus:
Začneme od prvního prvku, uložíme si jeho adresu. Projdeme celý seznam (do konce) a budeme porovnávat všechny následující prvky s prvkem prvním. Do pomocné proměnné si uložíme četnost v rámci shody a tu pak uložíme na tu adresu do atributu počet výskytů. Další iterace (druhý prvek) začne od n+1.
Někdy se může stát, že zbytečně projíždíme vždy celej seznam od n+1, ale tuto problematiku nyní neřešíme. Pokud budu mít dnes čas k večeru, tak to zkusím nadhodit, jak by to mohlo vypadat - nic obtížného. Myslím, že to bude moje premiéra Pascal a pointers.
Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.
Offline
#4 13. 02. 2012 16:01
- RePRO
- Místo: Jihlava
- Příspěvky: 363
- Škola: AI VŠPJ (09-12, Bc.)
- Pozice: programátor
- Reputace: 11
- Web
Re: Pascal - Lineární spojový seznam
Zdravím,
tak asi nějak takto, akorát se musí ještě v tom výpisu odstranit duplicity:
Code:
program SpojovySeznamVyskyt;
uses CRT;
type TPrvek = ^Prvek;
Prvek = record
vek: integer;
pocitadlo: integer;
dalsi: TPrvek;
end;
var
zacatek: TPrvek;
procedure vlozPrvek(vek: integer);
var
pom: TPrvek;
begin
if zacatek = nil
then
begin
new(pom);
pom^.vek := vek;
pom^.pocitadlo := 1;
pom^.dalsi := nil;
zacatek := pom;
end
else
begin
new (pom);
pom^.vek := vek;
pom^.pocitadlo := 1;
pom^.dalsi := zacatek;
zacatek := pom;
end;
end;
procedure vypsatSeznam;
var
pom: TPrvek;
begin
pom := zacatek;
while pom^.dalsi <> nil do
begin
writeln('Vek: ', pom^.vek:2, ' Vyskyt: ', pom^.pocitadlo:2);
pom := pom^.dalsi;
end;
end;
procedure vytvoritVyskyty;
var
pom: TPrvek;
pom2: TPrvek;
pomPocitadlo: integer;
begin
pom := zacatek;
pom2 := nil;
while pom^.dalsi <> nil do
begin
pom2 := pom;
pomPocitadlo := 0;
while pom2^.dalsi <> nil do
begin
if (pom^.vek = pom2^.vek) then
begin
pomPocitadlo := pomPocitadlo + 1;
end;
pom2 := pom2^.dalsi;
end;
pom^.pocitadlo := pomPocitadlo;
pom := pom^.dalsi;
end;
end;
begin
clrscr;
{ vytvorime seznam }
new(zacatek);
vlozPrvek(1);
vlozPrvek(2);
vlozPrvek(3);
vlozPrvek(4);
vlozPrvek(5);
vlozPrvek(5);
vlozPrvek(5);
vlozPrvek(3);
vytvoritVyskyty;
vypsatSeznam;
readln;
end.Srdcem trochu-programátor, duší rádoby-matematik a povoláním analytik-vývojář.
Offline