Problematika zoznamov, zásobníkov atď.. je v objektovom programovaní veľmi dôležitá vec. Takže pôjdem s jej vysvetľovaním veľmi pomaličky. Najjednoduchším nástrojom na ukladanie viacerých objektov sú polia, ktoré sme dosť podrobne rozobrali v minulej sérii. Dnes sa k ním vrátim, aby som poukázal v čom spočívajú určité ich obmedzenia a načo si treba dávať pozor.
>>Polia ako zoznamy
Polia majú nevýhodu v tom, že sa ich veľkosť dá len veľmi ťažko dynamicky meniť. Napríklad chcete načítavať nejaké údaje z klávesnice, ale neviete aký bude ich konkrétny počet. Samozrejme, že v tomto prípade môžete použiť pole, ale zároveň musíte mať nejaký predpoklad aký bude maximálny počet údajov.
Problém nastáva, keď sa podmienky použitia programu zmenia a množstvo vstupných údajov prekročí maximálny predpokladaný rozsah. Vtedy máme dve možnosti :
- - buď priamo prerobiť časť programu na vyšší rozsah a znova ho spustiť, čo je ale v súčasnosti nepoužiteľné.
- - alebo rátať s takouto možnosťou a program navrhnúť tak, aby si bol schopný vytvoriť nové, väčšie pole a prekopírovať do neho staré hodnoty, čo je ale časovo náročná operácia.
Pre lepšiu predstavu uvádzam príklad, ktorý to práve takto rieši :
Príklad 4.1
using System;
class MainClass
{
static int maxRozsah = 5;
//--------------------------------------------
static void Main(string[] args)
{
int [] poleCisiel = new int[maxRozsah];
int cislo;
Console.WriteLine("Pre ukoncenie vkladania cisiel");
Console.WriteLine("Napiste -1");
int i = 0; // >i< je iteracna premenna
do
{
// testujeme moznost prekrocenia rozsahu
if ( i == maxRozsah)
{
// nami definovana funkcia
ZvacsiRozsah(ref poleCisiel,2);
Console.WriteLine("Novy rozsah je {0}",
maxRozsah);
}
//nacitanie cisla z klavesnice
cislo = Convert.ToInt32((Console.ReadLine()));
poleCisiel[i] = cislo;
i++;
}while(cislo!=-1);
// vypise vsetky nacitane cisla
Console.WriteLine("Vlozili ste:");
for(int j=0; j<poleCisiel.Length-2; j++)
Console.WriteLine(poleCisiel[j]);
Console.ReadKey();
}
//----------------------------------------------
static void ZvacsiRozsah(ref int [] pole, int oKolko)
{
maxRozsah = maxRozsah + oKolko;
// vytvorime nove pole
int [] novePole = new int[maxRozsah];
// prekopirujeme stare prvky
for(int i = 0; i < pole.Length; i++)
{
novePole[i] = pole[i];
}
// zamenime ukazovatelov, preto ref
// takto sa daju menit vstupne parametre
pole = novePole;
}
}
Príklad na stiahnutie (src+ exe)
Na zväčšovanie rozsahu pola sme použili vlastnú funkciu ZvacsiRozsah, ktorá musí mať ako parameter referenciu (ukazovateľ) na pôvodné pole. Všimnite si slovíčko ref v deklarácii hlavičky funkcie. Prekopírovanie starých prvkov zaberá určitý čas, ktorý narastá samozrejme s počtom prvkov.
Tým, že sme nahradili referenciu starého pola novo vytvoreným (alokovaným) poľom, prichystali sme robotu pre Garbage Collector, ktorý zistí že pamäť potrebná pre staré pole sa už v programe nikde nevyužíva a bude je musieť niekedy vyčistiť (nemusí to nastať hneď), čo tiež spomalí program v prípade, ak by sa pole dosť často predlžovalo.
Záver 1 : Polia ako zoznamy sa dajú výhodne použiť len v jednoduchých programoch.
>>Zreťazené zoznamy
Tento spôsob tvorby zoznamov je komplikovanejší (na pochopenie), ale odstraňuje “statickosť polí“. Základným princípom je fakt, že:
Jedna trieda môže v sebe obsahovať odkaz na ďalšiu triedu rovnakého typu (u nás je typ Zoznam) ako je ona a postupne môžeme toto pravidlo opakovať a tým vytvárať zoznam. Pozrite na obrázok!
>>Princíp tvorby zreťazených zoznamov
Navrhneme si nejakú triedu (v našom prípade s menom Zoznam) a jedna z jej položiek je odkaz na ďalší prvok zoznamu. Pozrite sa do príkladu nižšie.
1. Vytvoríme prvý prvok, hlavu (head) zoznamu, ktorý má zatiaľ položku ďalší prvok prázdnu. Natavíme zároveň tento prvok ako prvý aj posledný (keďže je sám).
2. Nový prvok vkladáme do zoznamu ako položku .dalsi posledného prvku a až potom tento nový prvok vyhlásime ako posledný prvok predĺženého zoznamu..
Príklad 4.2
using System;
class MainClass
{
//------------------------------------------
static void Main(string[] args)
{
Zoznam zoz = new Zoznam();
int cislo;
// nacitanie zoznamu
do{
cislo = Convert.ToInt32(Console.ReadLine());
zoz.Pridaj(cislo);
}while(cislo!=-1);
Console.WriteLine("Vlozili ste:");
Zoznam prvok = zoz.prvy;
// pocet - staticka premenna
for(int i=0; i < Zoznam.pocet-2; i++)
{
Console.WriteLine(prvok.Hodnota);
// finta :-), ako prejst cely
// zretazeny zoznam
prvok = prvok.dalsi;
}
Console.ReadKey();
}
}
//------------------------------------------
class Zoznam
{
int hodnota;
public Zoznam prvy;
Zoznam posledny;
public Zoznam dalsi; // !!!!!! PODSTATA
public static int pocet = 0;
//--------------------------------------------
// Konstruktor, inicializacia objektu
public Zoznam()
{
if(pocet == 0) prvy = this;
posledny = this;
pocet++;
}
//-------------------------------------------
public void Pridaj(int cislo)
{
// Ak zatial nebol priradeny ziaden prvok
// ale prvy (head) je uz pripraveny
// netreba ho vytvarat
if(pocet ==1)
{
prvy.Hodnota = cislo;
pocet++;
return;
}
// Ak pridavame druhy a dalsi prvok
Zoznam novyPrvok = new Zoznam();
novyPrvok.Hodnota = cislo;
// Pridanie noveho prvku do zoznamu
this.posledny.dalsi = novyPrvok;
this.posledny = novyPrvok;
}
// Vlastnost, property
public int Hodnota
{
get { return hodnota ;}
set { hodnota = value; }
}
}
Príklad na stiahnutie (src+ exe)
Tento program ma skoro taký istý výstup ako predchádzajúci program. Rozdiel je v tom, že zoznam sa dynamicky rozširuje pri vkladaní zakaždým iba o jeden prvok, ktorý sa napojí na „chvost“ (posledný) prvok zoznamu. Zreťazený zoznam môžeme zakresliť iným spôsobom aj takto:
Náš navrhnutý zoznam je už dostatočne pružný oproti poliam, ale má tiež svoje muchy :-). Ak ste dobre pochopili príklad vidíte, že medzi prvkami sa dá pohybovať iba jedným smerom a to vždy od začiatku => je to jednosmerný zoznam.
Ak by sme chceli, aby bol prvok obojsmerný, museli by sme pridať do každého prvku ešte položku : .predchádzajúci.
Viem, že zreťazené zoznamy robia začiatočníkom spočiatku problémy, tak ak ste niečomu nepochopili, alebo poznáte lepší spôsob ako vysvetliť zreťazené zoznamy, napíšte prosím do diskusie.
Záver 2 : Zreťazené zoznamy nemajú vôbec žiadny problém s prolongáciou (pekný pojem čo? :-) To som minule počul v knižnici, keď som si predlžoval knihu). Nevýhodou, je že nemôže k jednotlivým prvkom pristupovať pomocou indexov ako v poliach, ale musíme vždy začínať od prvého (prípadne od posledného u obojsmerných zoznamov) prvku.
>>Dobrá správa na záver
Pre všetkých, ktorí nepochopili zreťazené zoznamy, ale pochopili, že len s poliami by ďaleko nezašli mám dobrú správu : Triedy, ktoré realizujú zreťazené zoznamy sú už v knižniciach C# štandardne naprogramované a prichystané na použitie.
Možno si teraz hovoríte „načo nás trápil s vysvetľovaním zreťazených zoznamov, keď ich už niekto naprogramoval za nás ?“ Ja som si zas povedal, že keď sa niekto dostal až po tento diel seriálu, tak to s programovaním myslí vážne (C# has you :-) ) a vtedy je dobre vedieť „ako veci naozaj fungujú“ :-)
>>Čo bude v ďalšom dieli ?
Ukážeme si prácu so štandardnými triedami pre zoznamy, zásobníky atď. Podelím sa s Vami s mojím nadšením nad objavením nového príkazu (skôr syntaxe) v C# 2.0 a to s yield. Zatiaľ Vám prezradím len to, že so sa s takouto konštrukciou nestretol v žiadnom inom programovacom jazyku.
Michal Čižmár
micitn@orangemail.sk
