Osztályozása és példák adatstruktúrák - studopediya
Mint az a fenti definíció strukturálása adatok fennállására utal (vagy telephely) közöttük néhány kapcsolatok (linkek). Attól függően, hogy a természet e kapcsolatok számos osztályozási adatstruktúrák.
Ezek közül az első, úgy rendelésére kapcsolatban. A sorrendben az adatszerkezet vannak osztva a megrendelt és rendezetlen.
Egy példa a rendezetlen szerkezetek készlet - nem határozza meg a az elemek sorrendjét őket; Az egyetlen dolog, hogy be lehet állítani bármilyen konkrét adatokat, így ez az ő tulajdonában (vagy nem tartozó) a kiválasztott készüléket.
A következő jel osztályozási struktúrák egyenletességét. Alkalmazni egységes struktúrát, amely csak egyetlen elemi adattípust. Nem egyenletes szerkezetek egyesítjük adatok a különböző típusú. Példák a homogén szerkezetek tömbök, több halom. készít felvételt, inhomogén szerkezetek.
Egy másik funkció a természet közötti kapcsolat az elemek. A kölcsönös alárendelt elemei az adatstruktúra vannak osztva lineáris és nemlineáris.
A lineáris szerkezetek minden elem egyenlő. Ezek közé tartozik egy tömb, set, verem, sorban.
A nem-lineáris szerkezetek az elemek között van egy alárendeltségi viszony, vagy lehet összekapcsolva logikai feltételeket. Ezek közé tartozik a fák, grafikonok, keretek.
Ennek alapján a kiválasztott besorolás funkciók, fontolja meg, és jellemezze néhány adat struktúrákat.
Massive lineáris rendezett halmaz homogén adatok.
· A „megrendelt” azt jelenti, hogy a tömb elemei vannak számozva;
· A „lineáris” jelzi az egyenlőség valamennyi tag;
· A „homogén” kifejezés a következő: abban az esetben, ahol egy sor van kialakítva elemi adatok, ez az adat lehet, hogy csak az egyik típusú, így például egy sor szám vagy karakter tömb; Azonban lehetséges, hogy a tömb elemei lesznek komplex (strukturális) információkat, mint például egy sor tömbök - ebben az esetben, „homogén” azt jelenti, hogy minden sejt azonos szerkezetű és méretű.
A száma indexek, hogy meghatározza a helyzetét az elem a tömbben, úgynevezett dimenzionalitásának a tömb.
Például, ha egy indexet, úgynevezett egydimenziós tömb; Gyakran az ilyen tömb is nevezik egy vektor, sor vagy oszlop. Rögzíteni egydimenziós tömb elemeit használják km kijelölése; a jelölést m programozási nyelvek (i) vagy m [i].
Tömb, amelynek elemeit a két index, az úgynevezett egy kétdimenziós vagy mátrix. Példa megjelölése: G [3,5]; ahol az első index a sor számát, és a második index - oszlop számát, amely a kereszteződésekben a tétel.
Tömbök három mutató úgynevezett háromdimenziós, stb A maximális mérete a tömb lehet korlátozni bizonyos szintaktikai programozási nyelvek vagy nincs ilyen korlátozás.
A maximális érték a tömb indexe határozza meg a felbontást. a tömb mérete van megadva a program leírása az egység, mint az a program végrehajtását fenntartva tárolásához szükséges memória tömb. Ha végrehajtása során a program a tömb mérete nem változik (vagy nem lehet változtatni), akkor ebben az esetben beszélhetünk egy fix méretű tömbök; ha a meghatározás a tömb, vagy megváltoztathatja a méretét előfordulnak a során a program, az ilyen tömbök nevezzük dinamikus (dinamikusan leírt).
A megengedhető műveletek sorozata a tömb elemeinek által meghatározott típusú adatok (az elemi vagy strukturált), amelyek a tömb van kialakítva. Bizonyos programozási nyelvek az elrendezés felett egésze határozza értékadó operátor M: = <выражение> - Ebben az esetben, minden eleme a tömb van rendelve ugyanazt az értéket, egyenlő a számított érték a kifejezés; hozzárendelés művelet is lehetséges, hogy két azonos típusú, mérete és alakja olyan tömbök M2 = M1 - érték-hozzárendelést elemenkénti (M2 (i, j, k): = M1 (i, j, k) ..).
Különösen fontos a karakter tömbök - nevezzük őket zsinór vagy húr adatok (például a String típusú PASCAL'e). Ezek egy sor lehetséges műveletek, bizonytalan egyetlen karakter adatokat. Elsősorban ez a konkatenáció (kombináció) vonalak kialakulását egy új sor. Ezen kívül vannak olyan műveletek helyettesítési a sor, és meghatározzák annak számszerű jellemzőit.
Ellentétben egy köteg sorban csak azokat az információkat a kivonás a rendet „first in - first out”, azaz aljáról a köteg.
Az adatok tehát a rend és elrendezése azok egyenlő - tehát a szerkezet rendezett és lineáris. Általában azonban tartalmazhatnak a különböző típusú adatok sejtek a verem - ez az alapja inhomogén szerkezetű.
Az ismertetett eljárás megszervezésének adatok, célszerű, ha dolgozik, rutinok, megszakítás, megoldása sok problémát.
Fa, vagy hierarchia egy példa egy lineáris szerkezet. A szintet az egyes elemek az ott (kivéve a legfelső) az egyik és csak az egyik eleme a következő (magasabb) szintjének. a legmagasabb szinten az úgynevezett gyökér elem, és a legalacsonyabb szintre - levelek.
Az áramkör egy ilyen szerkezet ábrán látható. Az egyes elemek lehetnek egyenletes vagy nem. Egy példa egy ilyen szervezet a fájl szerkezetét a külső tárolóeszközök a számítógép.
Gyakran a kapcsolat a bemutatott adatok a grafikonon - egy sor pontok és vonalak, amelyben minden egyes vonal köti össze a két pontot. A számítástechnikában pont veszi ész-szerkezet (rendszer az adatok, és így tovább.), És a vonal - arányát jelenti a az elemek között. Ismerkedjen számos kapcsolódó kifejezések használatával grafikonok.
A pontokat nevezzük a gráf, a vonal - bordák. Ha a széle összeköti két csúcsát, akkor azt mondjuk, hogy a széle esemény ezen csúcspontok, és maguk csúcsok nevezzük szomszédos. Az élek száma incidens a vertex, az úgynevezett fokú csúcsok. Ha két élek incidens ugyanazon pontpár, hívják őket több. A borda, amely ugyanazt a két csúcsot, úgynevezett hurok.
Ábra. 6.3 is. 1 graph kap egy listát a csúcsok és egy listát a élek, ahol minden egyes éle jelzi egy pár csúcsok esemény egy (1,2); b (1,4); A (2, 0,4); 6 (2.3); e (3,4); f (2,3); g (4,4).
Szomszédos pár csúcsok (2,3), (2,4), (1,2), (1,4), (3,4). Rib d egy hurok; bordák d és f - többszörösei. Fok csúcsok 2 és 4 egyenlő 4; csúcsok 3 -3; csúcsokat 1 - 2.
Összekötő élek csúcsok lehet egy irányba -, akkor azt mondják, hogy orientált és képviseli egy nyíl. Graph, amelyben az összes éleket orientált, azt mondják, hogy orientált; bordái gyakran nevezik ívek. Arcs úgynevezett többszörösei, ha azok csatlakoztassa azonos vertex és ugyanabban az irányban. A kijelölő ív mindig megjelenik az első csúcs, ahonnan kezdődik, például látható. 6.3, b (2,3).
Útvonal - sorozatát élek, ahol a végén az előző élre egybeesik az elején a következő, például egy. c, e, a grafikonon Route 1, ahol a végső csúcs egybeesik a start, az úgynevezett ciklust, például. E, D az oszlopon 2. Egy gráf összefüggő, ha van egy útvonal bármely két csúcsához. Összefüggő gráf n csúcsú tartalmaz legalább n -1 bordák.
Besorolása szerint korábban tárgyalt gráf egy rendezett, nem-lineáris, nem egységes szerkezet. A koncepció grafikon, mert a magas világosság és általánosság számítógép úgy viselkedik, mint az elsődleges eszköze leíró adatok struktúrák, rendszerek, megrendelés teljesítésére műveleteket. Egy példa egy folyamatábra a program.
Abból a szempontból, gyakorlati haszna nagy érdeklődés mutatkozik egyféle képező adatok rendezett, egyenes, nem egységes szerkezet. Meg lehet tekinteni, mint egy olyan struktúra, mint egy sor heterogén strukturált adatok.
A szerkezet az úgynevezett asztal, és az egyes sorok - rekord (logikai rekord). Mivel a nagy jelentőségű ez a struktúra fog foglalkozni részletesebben.
Vissza a Tartalomjegyzék: Elméleti alapjait számítástechnika