Abstract gegevenstype. Abstracte gegevenstypen

Alle ingebouwde datatypes zijn abstract, al worden ze zelden zo genoemd.

abstractie concept

Abstractie is een oordeel of voorstelling over een object dat alleen eigenschappen bevat die essentieel zijn in een bepaalde context. Met abstractie kunt u objectinstanties combineren tot groepen, waarbinnen de algemene eigenschappen van objecten kunnen worden genegeerd, d.w.z. van hen abstraheren. Abstractie is een effectief hulpmiddel tegen programmeercomplexiteit, waardoor de programmeur zich kan concentreren op de essentiële eigenschappen van objecten. Soorten abstracties: procesabstractie en data abstractie.

Proces abstractie. Alle subroutines zijn abstracties van processen, ze definiëren de manier waarop het programma bepaalt dat een bepaald proces moet worden uitgevoerd, zonder de details te specificeren van hoe het precies moet. De mogelijkheid om de vele details van het algoritme dat een subroutine uitvoert te abstraheren, stelt u in staat om grote programma's te maken, te lezen en te begrijpen. Elke data-abstractie zijn bewerkingen, gedefinieerd als procesabstracties.

Data abstractie. Een abstract gegevenstype is een inkapseling die alleen representaties bevat van gegevens van een bepaald type en routines die bewerkingen uitvoeren op gegevens van dat type. Door gebruik te maken van toegangscontrole kunnen niet-essentiële details van een typebeschrijving worden verborgen voor externe modules die het type gebruiken. Programmamodules die een abstract gegevenstype gebruiken, kunnen variabelen van dat type declareren, ook al is de feitelijke weergave van het type voor hen verborgen. Een instantie van een abstract gegevenstype wordt een object genoemd.

De reden voor het maken van datatype-abstracties en procesabstracties is een middel tegen complexiteit, een manier om grote en/of complexe programma's beter beheersbaar te maken.

inkapseling

Een programma opdelen in syntactische containers die groepen logisch gerelateerde routines en gegevens bevatten. Deze syntactische containers worden modules genoemd en het ontwikkelingsproces is modularisatie.

Een programma samenstellen uit sets van routines en gegevens, die elk afzonderlijk kunnen worden gecompileerd, zonder de rest van het programma opnieuw te compileren. Deze set wordt een compilatie-eenheid genoemd.

Inkapseling is een manier om routines en de gegevens die ze verwerken te integreren tot een samenhangend geheel. Inkapseling, die afzonderlijk of onafhankelijk wordt samengesteld, vormt de basis van een abstract systeem en de logische organisatie van een reeks gerelateerde berekeningen.

Abstracte door de gebruiker gedefinieerde gegevenstypen

Abstracte, door de gebruiker gedefinieerde gegevenstypen moeten de volgende eigenschappen hebben:

1) typedefinitie, waarmee programmamodules variabelen van dit type kunnen declareren, terwijl ze een echte weergave van deze variabelen in het geheugen creëren.

2) een reeks bewerkingen voor het manipuleren van objecten van dit type.

Formele definitie van een abstract gegevenstype in de context van door de gebruiker gedefinieerde typen: Een abstract gegevenstype is een gegevenstype dat aan de volgende twee voorwaarden voldoet.

Representatie (typedefinitie) en bewerkingen op objecten van dit type zijn opgenomen in één syntactische eenheid, variabelen van dit type kunnen in andere modules worden gemaakt.

De weergave van objecten van dit type is verborgen voor programmamodules die dit type gebruiken; bewerkingen kunnen worden uitgevoerd op objecten die direct in de definitie van het type zijn voorzien.

Door de typeweergave en bewerkingen in een afzonderlijke syntactische eenheid te stoppen, kunt u uw programma organiseren als logische eenheden die afzonderlijk kunnen worden gecompileerd. Ten tweede wordt het mogelijk om de representaties van objecten van een bepaald type of bewerkingen ermee te wijzigen in een apart deel van het programma. Het verbergen van de details van de presentatie van een type heeft voordelen. Clients kunnen de details van de weergave van een object niet "zien", en hun code is onafhankelijk van die weergave. Op deze manier kunnen objectrepresentaties op elk moment worden gewijzigd zonder dat wijzigingen in de klantcode nodig zijn. Een ander voor de hand liggend en belangrijk voordeel van het verbergen van informatie is een grotere betrouwbaarheid. Klanten kunnen de onderliggende representaties van objecten niet direct wijzigen, opzettelijk of per ongeluk, daarom wordt de integriteit van dergelijke objecten verhoogd. Objecten kunnen alleen worden gewijzigd met behulp van de daarvoor bestemde bewerkingen.

Typeontwerpproblemen

Het moet mogelijk zijn om de typenaam en subroutine-headers zichtbaar te maken in abstractie-clients. Hierdoor kunnen clients variabelen van een abstract type declareren en hun waarden manipuleren. Hoewel de typenaam van buitenaf zichtbaar moet zijn, moet de definitie ervan verborgen zijn.

Er zijn zeer weinig algemene ingebouwde bewerkingen die kunnen worden uitgevoerd op objecten van abstracte typen, in tegenstelling tot die welke worden geboden door een typedefinitie. Dergelijke operaties omvatten opdrachten en gelijkheids- en ongelijkheidstoetsen. Als de taal gebruikers niet toestaat de toewijzingsoperator te overbelasten, moet deze inline zijn. In sommige gevallen moeten gelijkheids- en ongelijkheidscontroles vooraf worden gedefinieerd en in andere niet. De letterontwerper moet de bewerkingen voor de meeste abstracte gegevenstypen zelf definiëren.

Smalltalk, C++ en Java ondersteunen rechtstreeks abstracte gegevenstypen.

Abstracte gegevenstypen in C ++

De talen Ada en Modula-2 bieden inkapseling die kan worden gebruikt om abstracte gegevenstypen te modelleren, terwijl C++ het concept introduceert van een klasse die abstracte gegevenstypen direct ondersteunt. In C++ zijn klassen typen, maar Ada-pakketten en Modula-2-modules zijn geen typen. Pakketten en modules worden geïmporteerd, waardoor de importerende programma-eenheid variabelen van elk type gedefinieerd in het pakket of de module kan declareren. In een C++-programma worden variabelen gedeclareerd als entiteiten van het type van deze klasse. Klassen lijken dus veel meer op ingebouwde typen dan op pakketten of modules. Een programma-eenheid die een pakket in Ada-taal of een module in Modula-2-taal ziet, heeft toegang tot alle open entiteiten, simpelweg door hun naam. Een C++-programma-eenheid die een instantie van een klasse declareert, heeft ook toegang tot alle openbare entiteiten in die klasse, maar alleen via een instantie van die klasse.

Laatste update: 08/04/2018

Naast de gebruikelijke lessen heeft C# abstracte lessen... Een abstracte klas is als een gewone klas. Het kan ook variabelen, methoden, constructors, eigenschappen hebben. Het enige is dat het abstracte trefwoord wordt gebruikt bij het definiëren van abstracte klassen:

Abstracte klasse Mens (public int Lengte (get; set;) public double Weight (get; set;))

Maar het belangrijkste verschil is dat we de constructor van een abstracte klasse niet kunnen gebruiken om zijn object te maken. Bijvoorbeeld als volgt:

Mens h = nieuw Mens ();

Waarom hebben we abstracte lessen nodig? Laten we zeggen dat we in ons programma voor de banksector twee hoofdentiteiten kunnen definiëren: een bankklant en een bankmedewerker. Elk van deze entiteiten zal anders zijn, bijvoorbeeld voor een werknemer, u moet zijn positie definiëren, en voor een klant - het bedrag op de rekening. Dienovereenkomstig zullen Klant en Medewerker aparte klassen Cliënt en Medewerker vormen. Tegelijkertijd kunnen beide entiteiten iets gemeen hebben, bijvoorbeeld voor- en achternaam, een andere gemeenschappelijke functionaliteit. En het is beter om deze algemene functionaliteit naar een aparte klasse te verplaatsen, bijvoorbeeld Persoon, die een persoon beschrijft. Dat wil zeggen dat de klassen Medewerker (werknemer) en Klant (bankcliënt) zullen worden afgeleid van de klasse Persoon. En aangezien alle objecten in ons systeem een ​​bankmedewerker of een klant vertegenwoordigen, zullen we geen objecten rechtstreeks vanuit de klasse Persoon maken. Het is dus logisch om het abstract te maken:

Abstracte klasse Persoon (public string Name (get; set;) public Person (string name) (Name = name;) public void Display () (Console.WriteLine (Name);)) class Client: Person (public int Sum (get ; set ;) // rekeningbedrag publiek Klant (string naam, int sum): base (name) (Sum = sum;)) class Werknemer: Persoon (public string Positie (get; set;) // position public Medewerker ( string naam, tekenreekspositie): basis (naam) (Positie = positie;))

Dan kunnen we deze klassen gebruiken:

Klant klant = nieuwe klant ("Tom", 500); Medewerker medewerker = nieuwe medewerker ("Bob", "Apple"); klant.Weergave (); werknemer.Weergave ();

Of zelfs zo:

Persoon cliënt = nieuwe cliënt ("Tom", 500); Persoon werknemer = nieuwe werknemer ("Bob", "Operator");

Maar we kunnen GEEN Person-object maken met behulp van de constructor van de Person-klasse:

Persoon persoon = nieuwe Persoon ("Bill");

Ondanks het feit dat we de constructor van de klasse Person niet rechtstreeks kunnen aanroepen om een ​​object te maken, kan de constructor in abstracte klassen niettemin een belangrijke rol spelen, in het bijzonder bij het initialiseren van enkele variabelen en eigenschappen die gemeenschappelijk zijn voor afgeleide klassen, zoals de geval met de eigenschap Naam. Hoewel het bovenstaande voorbeeld de constructor Persoon niet aanroept, kunnen de afgeleide klassen Client en Employee ernaar verwijzen.

Leden van de abstracte klas

Naast de gebruikelijke eigenschappen en methoden, kan een abstracte klasse leden van de abstracte klasse hebben, die zijn gedefinieerd met het trefwoord abstract en geen functionaliteit hebben. In het bijzonder kan abstract zijn:

• Eigendommen

  Indexeerders

Leden van abstracte klassen mogen de privé-modifier niet hebben. In dit geval moet de afgeleide klasse alle abstracte methoden en eigenschappen in de abstracte basisklasse overschrijven en implementeren. Wanneer deze wordt overschreven in een afgeleide klasse, wordt een dergelijke methode of eigenschap ook gedeclareerd met de override-modifier (zoals bij normale overschrijvende virtuele methoden en eigenschappen). Er moet ook worden opgemerkt dat als een klasse ten minste één abstracte methode (of abstracte eigenschap, indexer, gebeurtenis) heeft, deze klasse als abstract moet worden gedefinieerd.

Abstracte leden maken, net als virtuele, deel uit van een polymorfe interface. Maar als we in het geval van virtuele methoden zeggen dat de ervende klasse de implementatie erft, wordt in het geval van abstracte methoden de interface die door deze abstracte methoden wordt vertegenwoordigd, geërfd.

abstracte methoden

Laten we bijvoorbeeld de weergavemethode abstract maken in het bovenstaande voorbeeld:

Abstracte klasse Persoon (public string Name (get; set;) public Person (string name) (Name = name;) public abstract void Display ();) class Client: Person (public int Sum (get; set;) // sum op het account public Client (string name, int sum): base (name) (Sum = sum;) public override void Display () (Console.WriteLine ($ "(Name) heeft een account voor het bedrag (Sum)") ;)) class Werknemer: Persoon (public string Positie (get; set;) // position public Werknemer (string name, string position): base (name) (Position = position;) public override void Display () (Console.WriteLine ($ " (Positie) (Naam) ");))

abstracte eigenschappen

Het gebruik van abstracte eigenschappen moet worden opgemerkt. Het definiëren ervan is vergelijkbaar met het definiëren van automatische eigenschappen. Bijvoorbeeld:

Abstracte klasse Persoon (openbare abstracte tekenreeks Naam (get; set;)) klasse Client: Persoon (privétekenreeksnaam; openbare overschrijvingsreeks Naam (get (retourneer "Mr / Ms." + Naam;) set (naam = waarde;)) ) klasse Werknemer: Persoon (openbare overschrijvingsreeks Naam (get; set;))

De klasse Person definieert de abstracte eigenschap Name. Het ziet eruit als een auto-eigenschap, maar het is geen auto-eigenschap. Aangezien deze eigenschap niet geïmplementeerd hoeft te worden, heeft deze alleen lege get- en set-blokken. In afgeleide klassen kunnen we deze eigenschap overschrijven om er een volledige eigenschap van te maken (zoals in de klasse Client), of deze automatisch maken (zoals in de klasse Werknemer).

De implementatie van abstracte leden dumpen

De afgeleide klasse moet alle abstracte leden van de basisklasse implementeren. We kunnen ons echter afmelden voor de implementatie, maar in dit geval moet de afgeleide klasse ook als abstract worden gedefinieerd:

Abstracte klasse Persoon (openbare abstracte tekenreeks Naam (get; set;)) abstracte klasse Manager: Persoon ()

Voorbeeld van een abstracte klas

Een schoolvoorbeeld is het systeem van geometrische vormen. In werkelijkheid is er geen geometrische figuur als zodanig. Er is een cirkel, een rechthoek, een vierkant, maar er is gewoon geen figuur. Zowel de cirkel als de rechthoek hebben echter iets gemeen en zijn vormen:

// abstracte klasse van de figuur abstracte klasse Figuur (// abstracte methode om de omtrek te krijgen public abstract float Perimeter (); // abstracte methode om de area public abstract float te krijgen Area ();) // afgeleide klasse van de rechthoekklasse Rechthoek: figuur (public float Width (get; set;) public float Height (get; set;) public Rectangle (float width, float height) (this.Width = width; this.Height = height;) // overschrijven van het verkrijgen van de perimeter public override float Perimeter () (retour Breedte * 2 + Hoogte * 2;) // override krijgen van het gebied public override float Area () (retour Breedte * Hoogte;))

Bijlage bij het werkprogramma voor het vakgebied "Structuren en algoritmen voor gegevensverwerking in een computer"

Het abstracte gegevenstype "Lijst".

Lijst- een reeks elementen van een bepaald type een1 , een2 , ..., een N, waar N https://pandia.ru/text/78/308/images/image001_307.gif "width =" 13 "height =" 16 "> 1, dan een1

Wordt het eerste element genoemd en een- het laatste element van de lijst. Lijstitems zijn lineair gerangschikt volgens hun positie in de lijst. Ai-element voorafgegaan element ai+1 voor l = 1,2, N-1 en ai zou moeten per ai-1 voor l = 2,3, N. Elk item in de lijst ai Het heeft positie l, l=1,2, N. Er is een positie in de lijst , wat het einde van de lijst betekent - nul. Het volgt het laatste item in de lijst.

Exploitanten van ADT "Lijst":

1. INVOEGEN ( x, R,L). Deze instructie voegt een object in NS in positie R in de lijst L, bewegende elementen van positie p en verder naar de eerstvolgende hogere positie. Dus als de lijst L bestaat uit elementen een1 , een2 , ..., eenN a1, a2, ..., ap-1, x, ap, ..., eenN.... Als p de waarde krijgt nul, dan hebben we een1 , een2 , ..., eenN , , NS... Als in de lijst L geen positie R, dan is het resultaat van deze verklaring niet gedefinieerd.

2. BEVIND ZICH(x , L ). Deze functie retourneert de positie van het object NS in de lijst L. Als het object in de lijst staat x meerdere keren voorkomt, wordt de positie van het eerste object vanaf het begin van de lijst geretourneerd NS. Als het object NS niet op de lijst L dan keert het terug nul.

3. UITTREDEN(P , L ). Deze functie retourneert het element op positie R in de lijst L. Het resultaat is ongedefinieerd als p = nul of in de lijst L geen positie R.

4. VERWIJDEREN(P , L ). Deze operator verwijdert het element op positie R lijst L. Dus als de lijst L bestaat uit elementen een1 , een2 , ..., eenN, dan ziet het er na het uitvoeren van deze operator uit als: a1, a2, ...,, ap- l , ap+ l, ..., een N. Het resultaat is niet gedefinieerd als de lijst bevat: L geen positie R of R = nul.

5. DE VOLGENDE ( P, L ) en VORIGE (blz, L ). Deze functies retourneren respectievelijk de volgende en vorige posities van de positie R in de lijst L. Indien R - laatste positie in de lijst L, dan VOLGENDE (P, L) = nul... NEXT-functie is niet gedefinieerd wanneer: p =nul... De PREVIOUS-functie is niet gedefinieerd als p = 1. Beide functies zijn niet gedefinieerd als de lijst L geen positie R.

6. MAKENULL( L ) ... Deze functie maakt een lijst L leeg en geeft de positie terug nul.

7. EERST(L ). Deze functie retourneert de eerste positie in de lijst L. Als de lijst leeg is, wordt de positie geretourneerd nul.

8. AFDRUKLIJST(L ). Lijstitems afdrukken L in de volgorde waarin ze in de lijst voorkomen.

Lijstweergave met een array:

Lijstweergave met enkelvoudig gelinkte lijst:

Legende:

- een verwijzing naar het begin van de lijst,

· laatste - aanwijzer naar het laatste item in de lijst ,

· maximale lengte - de maximale lengte (aantal elementen) in de lijst.

Een lijst weergeven met een dubbel gekoppelde lijst:

Opdrachten:

1. Programma's schrijven voor het invoegen, verwijderen en doorzoeken van elementen van een gesorteerde lijst, om de lijst te implementeren

§ reeks,

wijzers.

2. Schrijf een programma om samen te voegen

§ twee gesorteerde gekoppelde lijsten,

§ n gesorteerde gekoppelde lijsten,

3. Gegeven een polynoom van de vorm

p (x) = c1 xe1 + C2 xe2 + + metNNSN, waar e1> e2> ...> eN> 0.

Zo'n polynoom kan worden weergegeven als een gekoppelde lijst, waarbij elk element drie velden heeft: één voor de coëfficiënt metl de tweede is voor de exponent el de derde is voor een verwijzing naar het volgende element. Schrijf voor de beschreven representatie van polynomen een programma voor het optellen en vermenigvuldigen van polynomen met behulp van deze representatie.

4. Implementeer de LIST ADT voor elk gegevenstype en de bijbehorende instructies INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST:

§ de lijst wordt gegeven als een array,

§ de lijst is gespecificeerd als een enkelvoudig gekoppelde lijst,

§ de lijst is gespecificeerd als een dubbel gelinkte lijst.

Werkprogramma paragraaf 2.1.2

Het abstracte gegevenstype "Stack".

Stapel - het is een speciaal type lijst waarin alle invoegingen en verwijderingen aan slechts één uiteinde worden gedaan, genaamd top , (bovenkant). De accessor wordt gebruikt voor de stapel LIFO(last-in-first-out - laatste in - eerst uit).

Exploitanten van ATD "Stack":

1. MAKENULL(S). Leeg de S-stack.

2. BOVENKANT(S). Retourneert het item van de bovenkant van de stapel S. Gewoonlijk wordt de bovenkant van de stapel geïdentificeerd door positie 1, dan kan TOP (S) in termen van algemene lijstoperatoren worden geschreven als RETRIEVE (FIRST (S), S).

3. KNAL(S). Verwijdert een item van de bovenkant van de stapel (knalt uit de stapel), in termen van lijstverklaringen kan deze verklaring worden geschreven als DELETE (FIRST (S), S).

4. DUW(x, S ). Voegt een element in NS naar de bovenkant van de stapel S (duwt het item op de stapel). Het item dat eerder bovenaan de stapel lag, wordt het item dat bovenaan stond, enz. In termen van algemene lijstoperatoren kan deze instructie worden geschreven als INSERT (; c, FIRST (S), S).

5. LEEG(S) ... Deze functie retourneert waar als de stapel S leeg, en anders vals.

reeks:

Stapelweergave met enkelvoudig gelinkte lijst:

Opdrachten:

Implementeer de STACK ADT voor elk gegevenstype en de operators MAKENULL, TOP, POP, PUSH, EMPTY.

§ de stapel is gespecificeerd als een array,

De stapel is ingesteld als een enkelvoudig gekoppelde lijst.

Werkprogramma paragraaf 2.1.2

Het abstracte gegevenstype "Wachtrij".

Rij (wachtrij) is een speciaal type lijst waar items vanaf het ene uiteinde worden ingevoegd, genaamd hindi (achter), en zijn verwijderd van de andere, voorkant (voorkant). Wachtrijen worden ook wel "FIFO-lijsten" genoemd (FIFO staat voor first-in-first-out: first in, first out). Operators die op wachtrijen worden uitgevoerd, zijn vergelijkbaar met stack-operators. Het essentiële verschil tussen beide is dat er nieuwe elementen worden ingevoegd einde van lijst in plaats van aan het begin, zoals in stapels.

Exploitanten van ADT "Wachtrij":

1. MAKENULL(Q) wist wachtrij Q , leeg maken.

2. VOORKANT(Q) - een functie die het eerste element van de wachtrij retourneert Q. U kunt deze functie implementeren met behulp van lijstoperatoren zoals RETRIEVE (FIRST (Q), Q ).

3. INSCHRIJVEN(een, Q) voegt een element in NS aan het einde van de wachtrij Q.

Met lijstoperatoren kan deze operator als volgt worden uitgevoerd: INSERT (x, END (Q), Q ).

4. DEQUEUE(Q) verwijdert het eerste element van de wachtrij Q . Ook uitvoerbaar met lijststatements zoals DELETE (FIRST (Q), Q).

5. LEEG(Q) geeft true terug als en alleen als Q een lege wachtrij is.

cyclisch reeks:

Legende:

Q- rij,

Q. voorkant- aanwijzer naar het begin van de wachtrij,

Q. achterkant- een wijzer naar het einde van de wachtrij.

Wachtrijweergave met enkelvoudig gelinkte lijst:

Opdrachten:

Implementeer de QUEUE ADT voor elk gegevenstype en de bijbehorende MAKENULL-, FRONT-, ENQUEUE-, DEQUEUE-, EMPTY-instructies.

De wachtrij wordt gespecificeerd als een cirkelvormige array,

De wachtrij wordt gespecificeerd als een dubbel gekoppelde lijst.

Abstract gegevenstype "Boom".

Hout is een verzameling elementen genaamd knopen (waarvan er één is gedefinieerd als wortel ), en relaties ("ouder") die een hiërarchische structuur van knooppunten vormen. Knooppunten kunnen, net als lijstelementen, elementen van elk type zijn. Formeel kan een boom als volgt recursief worden gedefinieerd.

1. Eén knoop is een boom. Hetzelfde knooppunt is ook de wortel van deze boom.

2. Laten we NS - dit is een knoop, een t1 , T2, ...,Tk- bomen met wortels N1 . N2 , ..., nk respectievelijk. Je kunt een nieuwe boom bouwen door te doen NS ouder van knooppunten N1 . N2 , ..., nk... In deze boom NS zal de wortel zijn, a t1 , T2, ...,Tk - subbomen deze wortel. Knooppunten N1 . N2 , ..., nk worden genoemd zonen knoop NS.

Deze definitie omvat vaak het concept nulboom , dat wil zeggen, een "boom" zonder knopen, zo'n boom wordt aangeduid met het woord nul .

Voorbeeld: Over hoofdstuk van het boek kan schematisch worden weergegeven door een boom. De ouder-zoonrelatie wordt weergegeven als een lijn. Bomen worden meestal van boven naar beneden getekend met ouders boven de "kinderen".

DIV_ADBLOCK135 ">

Knooppunt hoogte een boom is de lengte van het langste pad van deze knoop naar een blad. In het voorbeeld is de hoogte van de knoop Hoofdstuk 1 is gelijk aan 1, knoop Hoofdstuk 2 - 2, en knooppunt Ch. Z-0. Boom hoogte samenvalt met de hoogte van de wortel. Knooppunt diepte wordt gedefinieerd als de lengte van het pad (het is het enige) van de wortel naar dit knooppunt.

Zonen van een knoop worden meestal van links naar rechts geordend. Daarom zijn de twee bomen in de figuur verschillend, aangezien de volgorde van de zonen van de knoop een verschillend. Als de volgorde van zonen wordt genegeerd, wordt zo'n boom genoemd ongeordend , anders heet de boom ordelijk .

Exploitanten van ATD "Tree":

1. OUDER(N, T). Deze functie retourneert de ouder van het knooppunt NS in de boom T. Indien NS een wortel is die geen ouder heeft, dan keert het in dit geval terug nul... Hier nul geeft aan dat er een out-of-bounds tree is opgetreden.

2. LINKS__ KIND(N , T). Deze functie retourneert het meest linkse kind van het knooppunt. N in de boom T. Indien N is een blad (en heeft dus geen zoon), dan keert het terug nul.

3. RECHTSAF_ BROER OF ZUS(N , T). Deze functie retourneert de rechter broer of zus van het knooppunt NS in de boom t of waarde nul,.als het niet bestaat. Dit is waar de ouder voor is R knoop NS en alle zonen van de knoop R, dan is onder deze zonen de knoop direct rechts van. knoop NS.

4. LABEL(N , t ). Retourneert het label van het knooppunt N... hout T. Deze functie vereist dat er labels worden gedefinieerd op de boomknooppunten.

5. CREËREN(v , t 1 , t 2 , ..., Ti ,) is een familie van functies die een nieuwe wortel maken voor elke i = 0, 1, 2, ... R met etiket v en dan creëert deze wortel i zonen, die de wortels van subbomen worden t1 , T2, ....Ti;. Deze functies retourneren een geroote boom R... Merk op dat als i = 0, er één knoop wordt geretourneerd R, die zowel een wortel als een blad is.

6. WORTEL(t ) geeft het knooppunt terug dat de wortel van de boom is t, Indien t- lege boom keert dan terug nul.

7. MAKENULL(t ). Deze operator maakt de boom t lege boom.

Een boom weergeven met behulp van een reeks ouders:

Boomstructuur met gelinkte lijsten:

Het vertegenwoordigen van de boom door middel van linker zonen en rechter broers.

Benamingen in de afbeelding:

nodespace – een reeks boomknooppunten,

label – knooppunt label, koptekst – de index van de linker zoon in de lijst van zonen,

cellpase – een reeks lijsten van knopenzonen,

knooppunt – een aanwijzer naar een knoop in een arraynodespace , De volgende – de index van de juiste zoon in de lijst met zonen.

Opdrachten:

1. Gegeven een boom:

DIV_ADBLOCK137 ">

§ de boom wordt gegeven als een array van knooppuntrecords met de index van de meest linkse zoon, de index van de rechter broer of zus en een label,

Een verbonden binaire boom wordt gespecificeerd met verwijzingen naar de linker- en rechterzonen.

4. Schrijf functies voor het doorlopen van een binaire boom in voorwaartse, achterwaartse en symmetrische volgorde.

Werkprogramma paragraaf 2.1.3

Het abstracte gegevenstype "Set".

Veel wordt meestal afgebeeld als een opeenvolging van zijn elementen, ingesloten tussen accolades, bijvoorbeeld (1, 4) geeft een set aan die uit twee elementen bestaat - nummers 1 en 4. De volgorde waarin de elementen van de set zijn geschreven is niet essentieel, dus je kunt (4, 1) op dezelfde manier schrijven als (1, 4), wanneer je dezelfde set schrijft. De set is geen lijst (althans vanwege de willekeurige volgorde van elementen). Er zijn geen dubbele elementen in de set ((1, 4, 1) is geen set).

Het fundamentele concept van de verzamelingenleer is het concept van de relatie behorend tot de set aangegeven met het symbool. Dus de invoer NS NS hoort niet bij de set EEN", d.w.z. NS geen lid van de set EEN... Er is een speciale set aangeduid met een symbool genaamd leeg, veel , en die geen elementen heeft. Stel DIV_ADBLOCK138 "> . in

Ze zeggen dat de menigte EEN bevat in de set V(of gaat aan in een menigte V), geschreven EEN V of V EEN als een element van de set EEN is ook een element van de set V. Wanneer EEN V zeg ook dat de set EEN is een een subset van de set V.

Bijvoorbeeld (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif "width =" 15 "height =" 15 src = "> V en AB, dan heet de verzameling A eigen, waar of strikte subset menigten V.

De belangrijkste bewerkingen die op sets worden uitgevoerd, zijn unie, intersectie en verschil. consolidatie sets EEN en V(aangeduid met EEN V) wordt een verzameling genoemd die bestaat uit elementen die tot ten minste één van de verzamelingen behoren EEN en V.

Kruispunt sets EEN en V(aangeduid met EEN V) een verzameling genoemd die alleen bestaat uit die elementen die bij de verzameling horen EEN, en de set V. Verschil sets EEN en V(aangeduid met EEN\ B) wordt een verzameling genoemd die alleen uit die elementen van de verzameling bestaat EEN die niet tot de set behoren V.

Bijvoorbeeld, als A = (a, b, c) en B = (b, a), dan is A B = (a, b, c, d), A B = (b) en A \ B = (a, c ) .

Exploitanten van ADT "Set":

1. UNIE(EEN, B, C) EEN en V MET, Gelijk EEN V.

2. KRUISPUNT(EEN, B, C) heeft "invoer"-argumenten ingesteld EEN en V, en als resultaat - de "output" set MET, Gelijk EEN V..

3. VERSCHIL(EEN, B, C) heeft "invoer"-argumenten ingesteld EEN en V, en als resultaat - de "output" set MET, Gelijk A \ B.

4. SAMENVOEGEN( EEN , B, C) operator voert uit fusie (samenvoegen), of vereniging van onsamenhangende verzamelingen . Deze operator verschilt niet van de operator. UNIE, maar hier wordt aangenomen dat de operand set niet kruisen (d.w.z. ze hebben geen gemeenschappelijke elementen). De operator wijst de set toe MET betekenis EEN V, maar het resultaat zal ongedefinieerd zijn als A B, d.w.z. in het geval dat de sets EEN en V gemeenschappelijke elementen hebben.

5. lid(x, A ) heeft argumenten ingesteld EEN en maak bezwaar NS van hetzelfde type als de elementen van de verzameling EEN en retourneert een booleaanse waarde waar(waar) als NS a "," b "," c ")) = "een". de exploitant MAX.

11.GELIJK(EEN , V ) geeft de waarde terug waar als en slechts als de sets EEN en V bestaan ​​uit dezelfde elementen.

12. VIND(x ) werkt in een omgeving waar sprake is van een verzameling onsamenhangende verzamelingen. Het geeft de naam (enkelvoud) terug van de set die een element heeft NS.

Stel weergave in:

De set kan worden gespecificeerd met behulp van een array of een gekoppelde lijst.

Opdrachten:

1. Er worden twee sets A = (1, 2, 3) en B = (3, 4, 5) gegeven. Wat zal het resultaat zijn van het uitvoeren van de volgende instructies?

UNIE (ABC),

KRUISPUNT (A, B, C),

VERSCHIL (ABC),

LID (l.A),

INVOEGEN (1, A),

VERWIJDEREN (1, A),

2. Implementeer de Set ADT voor elk gegevenstype en de operators MAKENULL, UNION, INTERSECTION, MEMBER, MIN.

De set wordt gespecificeerd met behulp van een array met vaste lengte en een pointer naar de laatste bezette positie in de array,

De set wordt gespecificeerd met behulp van een ongesorteerde gekoppelde lijst,

De set wordt gespecificeerd met behulp van een gesorteerde gekoppelde lijst,

Werkprogramma paragraaf 2.1.3

Speciale soorten sets

Binaire zoekboom Abstract gegevenstype

Binaire zoekboom - een gegevensstructuur voor het representeren van verzamelingen, waarvan de elementen zijn geordend volgens een lineaire ordeningsrelatie. Binaire zoekbomen kunnen set-operators implementeren INSERT, VERWIJDEREN, LID en MIN, en hun uitvoeringstijd is gemiddeld in de orde van O (log n) voor sets bestaande uit NS elementen.

Een kenmerk van een binaire zoekboom is dat de knooppunten zijn gelabeld met set-elementen (boomknooppunten bevatten set-elementen). Bovendien zijn alle elementen die zijn opgeslagen in de knooppunten van de linker subboom van een knooppunt NS, kleiner dan het element in het knooppunt NS, en alle elementen die zijn opgeslagen in de knooppunten van de rechter subboom van het knooppunt NS, meer dan het element in het knooppunt NS.

Binaire boom voorbeelden:

https://pandia.ru/text/78/308/images/image023_7.jpg "width =" 277 "height =" 122 src = ">

De AVL-structuurweergave is hetzelfde als de binaire zoekstructuurweergave.

Een ander type uitgebalanceerde zoekboom is: 2-3 hout. De structuur van een 2-3-boom verschilt van de structuur van een binaire zoekboom. Voor 2-3 bomen is het kenmerkend dat alle knopen 2 of 3 zonen hebben, alle paden van wortel tot blad even lang zijn en alle elementen van de set zijn opgenomen in de bladeren. Knooppunten 2-3 van de boom zijn verdeeld in intern en terminal (bladeren). Interne knooppunten worden alleen gebruikt voor het doorzoeken van boomstructuren. Elke interne knoop bevat de sleutels van de kleinste elementen van de tweede en derde zonen (als er een derde zoon is) en verwijzingen naar de knopen van de zonen.

Binaire zoekverbonden boomstructuur:

Vertegenwoordiging van een gebalanceerde aangesloten 2-3-boom:

Opdrachten:

1. Teken alle mogelijke binaire zoekbomen voor de vier elementen 1, 2, 3 en 4.

2. Voeg de gehele getallen 7, 2, 9, 0, 5, 6, 8, 1 in een lege binaire zoekboom in.

3. Laat het resultaat zien van het verwijderen van nummer 7 en vervolgens nummer 2 uit de boom verkregen in de vorige oefening.

4. Teken een 2-3 boom die het resultaat zal zijn van het invoegen van de elementen 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 in de lege verzameling (weergegeven als 2-3 bomen).

5. Toon het resultaat van het verwijderen van element 3 uit 2-3 van de boom die in de vorige oefening is verkregen.

3. Implementeer de Search Tree ADT voor elk gegevenstype en de bijbehorende INSERT-, DELETE-, MEMBER- en MIN-instructies.

De boom wordt gegeven als een verbonden binaire boom

Boom wordt gegeven als 2-3 bomen

Werkprogramma paragraaf 2.1.3

Abstract gegevenstype "Woordenboek".

Woordenboek - een set bedoeld voor het opslaan van "huidige" objecten met periodieke invoeging of verwijdering van enkele ervan. Van tijd tot tijd wordt het ook nodig om uit te zoeken of een bepaald element in een bepaalde set aanwezig is. Het woordenboek wordt geïmplementeerd met behulp van de Dictionary ADT met operators INVOEREN,VERWIJDEREN en LID... De woordenboekoperatorset bevat ook de operator MAKENULL om ADT-gegevensstructuren te initialiseren.

Een woordenboek kan worden weergegeven met behulp van een hashtabel. De tabel is gebouwd op basis van het volgende idee: een potentiële verzameling elementen (mogelijk oneindig) wordt verdeeld in een eindig aantal klassen. Voor V klassen genummerd van 0 tot IN 1, in opbouw hash-functie H zodat voor elk element NS originele ingestelde functie: H (x) neemt een geheel getal uit het interval 0, ..., V- 1, wat overeenkomt met de klasse waartoe het element behoort NS. Element NS bel vaak toets, H ( x) - hasj-waarde x, en "lessen" - segmenten ... Hoe hashing-botsingen op te lossen (twee elementen van een set hebben dezelfde waarde) H (x)), worden zowel publieke als private hashing toegepast.

open hashtafel

Een array genaamd segmenttabel en geïndexeerd segmentnummers 0, 1, ..., B - 1 , bevat kopteksten voor V gekoppelde lijsten. Element l-de lijst is een element van de originele set waarvoor H(.x :) =l.

Woordenboek representatie met privé hashtafel

De segmenttabel slaat direct de elementen van het vocabulaire op. Daarom kan in elk segment slechts één woordenboekelement worden opgeslagen. Bij private hashing wordt de techniek gebruikt opnieuw hashen ... Bij het plaatsen van een element x genummerd segmenteren H ( x ) , die al bezet is door een ander element, wordt een reeks segmentnummers geselecteerd H 1 ( x ) ,H 2 ( x ) , … waar het element kan worden geplaatst. De bezetting van elk van deze segmenten wordt achtereenvolgens gecontroleerd totdat een vrij segment is gevonden. Het element wordt erin geplaatst x ... Er worden verschillende methoden voor het oplossen van botsingen gebruikt om segmentnummers in te stellen bij het opnieuw hashen. Bijvoorbeeld lineaire hash-methode, mid-square-methode, willekeurige hash-methode

Opdrachten:

1. Stel dat u de hashfunctie h (i) = i% 7 gebruikt om gehele getallen in een hashtabel met 7 segmenten te hashen.

· Geef de resulterende hashtabel als de exacte kubussen 1, 8, 27,64,125, 216.343 erin zijn ingevoegd;

· Herhaal het vorige punt voor een gesloten hash-tabel met een techniek voor het oplossen van lineaire botsingen.

2. Stel dat er een private hashtabel is met 5 segmenten, een hashfunctie h (i) = i% 5, en een lineaire collisie-resolutietechniek. Toon het resultaat van het invoegen van de reeks getallen 23, 48, 35, 4, 10 in de aanvankelijk lege hashtabel.

3. Implementeer de Dictionary ADT voor tekstreeksen en de bijbehorende INSERT-instructies , VERWIJDEREN, LID en MAKENULL

Het woordenboek wordt gespecificeerd met behulp van een open hash-tabel,

Het woordenboek wordt gespecificeerd met behulp van een gesloten hash-tabel met een lineaire techniek voor het oplossen van botsingen,

Werkprogramma paragraaf 2.1.3

Het abstracte gegevenstype "Weergave".

Weergave - dit is een set, op de elementen waarvan de functie van het weergeven van elementen van hetzelfde type is gedefinieerd ( gebieden van definitie ) naar elementen van een ander type ( bereik van waarden ) van een ander type. Weergave m komt overeen met een element NS van type domeintype van bereik tot element R van type bereiktype uit bereik: m(NS) = R.Leeg display bevat geen elementen

Exploitanten van ADT "Display":

1. MAKENULL(m ). Maakt weergave m leeg.

2. TOEWIJZEN (m d,r). Doet m(NS) Gelijk R het maakt niet uit hoe m(NS) eerder was gedefinieerd.

3. COMPUTER ( M, d, r). Retourneert waar en wijst een waarde toe aan r m(NS), als de laatste is gedefinieerd, en geeft anders false terug.

Weergave bekijken: de mapping kan efficiënt worden geïmplementeerd met behulp van hash-tabellen. Hier x specificeert de waarde van het weergavedefinitiebereik en het tabelelement met het nummer H ( x ) - een element uit het assortiment.

Werkprogramma paragraaf 2.1.3

Prioriteitswachtrij Abstract gegevenstype

Prioriteits-rij is een verzameling voor de elementen waarvan de prioriteitsfunctie is ingesteld, dat wil zeggen voor elk element x ingesteld, kunt u de functie berekenen: R( x )- element prioriteit x , die meestal waarden haalt uit een reeks reële getallen, of, meer in het algemeen, uit een lineair geordende reeks.

ADT "Prioriteitswachtrij" gebaseerd op ADT "Set" met operators INSERT en VERWIJDEREN en ook met de operator MAKENULL om de gegevensstructuur te initialiseren. Operator INSERT voor een prioriteitswachtrij wordt in de gebruikelijke zin opgevat, terwijl: VERWIJDEREN is een functie die het element met de laagste prioriteit retourneert en, als neveneffect, het uit de set verwijdert.

Wachtrijweergave met een geordende dubbel gelinkte lijst.

Wachtrijweergave met gedeeltelijk geordende verbonden boom:

Het belangrijkste idee achter deze implementatie is om de elementen van de wachtrij in een binaire boom te organiseren. Op het lagere niveau, waar enkele bladeren kunnen ontbreken, kunnen alle ontbrekende bladeren zich alleen rechts van de huidige bladeren op een lager niveau bevinden. Het is belangrijker dat de boom gedeeltelijk besteld . Dit betekent dat de prioriteit van het knooppunt v niet groter dan de prioriteit van een zoon van het knooppunt v, waarbij knooppuntprioriteit de prioriteitswaarde is van het item dat in dit knooppunt is opgeslagen. Uit de figuur is te zien dat kleine prioriteitswaarden niet op een hoger niveau kunnen verschijnen, waar er grote prioriteitswaarden zijn.

De functie VERWIJDEREN retourneert het item met de laagste prioriteit dat de wortel van de boom moet zijn. Om de boom niet te vernietigen en de gedeeltelijke volgorde van de prioriteitswaarden op de boom te behouden nadat de wortel is verwijderd, worden de volgende acties uitgevoerd: het meest rechtse knooppunt bevindt zich op het laagste niveau en wordt tijdelijk bij de wortel geplaatst van de boom. Dit element daalt vervolgens langs de takken van de boom (naar lagere niveaus), terwijl het onderweg van plaats wisselt met de zonen met een lagere prioriteit, totdat dit element een blad wordt of in een positie komt waar zijn zonen op zijn minst niet minder prioriteit zullen hebben.

Weergave van een wachtrij met behulp van een array die de knooppunten van een gedeeltelijk geordende boom bevat:

In een array EEN de eerste N posities komen overeen N boom knooppunten. Element EEN bevat de wortel van de boom. Linker zoon van een boomknooppunt EEN[ l], als het bestaat, bevindt het zich in de cel EEN, en de juiste zoon, als hij bestaat, is in de cel EEN. Omgekeerd, als de zoon in de cel zit EEN[ l], dan is de ouder in de cel EEN[ l%2] ... Boomknooppunten vullen cellen EEN, EEN, … EEN[ N] achtereenvolgens niveau voor niveau, beginnend bij de wortel en binnen het niveau - van links naar rechts. De hierboven getoonde boom wordt in de array weergegeven door de volgende volgorde van zijn knooppunten: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Opdrachten:

1. Teken een gedeeltelijk geordende boom door de gehele getallen 5, 6, 4, 9, 3, 1 en 7 in een lege boom te plaatsen. Wat zou het resultaat zijn van het achtereenvolgens toepassen van drie DELETEMIN-instructies op deze boom?

2. Implementeer de Priority Queue ADT voor elk gegevenstype en de bijbehorende INSERT-, DELETEMIN- en MAKENULL-instructies

§ een gedeeltelijk geordende boom wordt geïmplementeerd met behulp van pointers,

§ Een gedeeltelijk geordende boom wordt geïmplementeerd met behulp van een array.

Werkprogramma paragraaf 2.1.3

Het abstracte gegevenstype "Union of Sets".

ADT is een unie van objecten, die elk een verzameling zijn. De belangrijkste acties die op zo'n set worden uitgevoerd, zijn om de sets in een bepaalde volgorde te combineren en om te controleren of een bepaald object tot een bepaalde set behoort. Deze taken worden opgelost met behulp van operators SAMENVOEGEN(afvoer) en VIND(Vind). MERGE-operator ( EEN, B, C) maakt de set MET gelijk aan de vereniging van verzamelingen EEN en V als deze sets elkaar niet snijden (dat wil zeggen, ze hebben geen gemeenschappelijke elementen); deze operator is niet gedefinieerd als de sets EEN en V snijden. FIND-functie ( x) geeft de set terug waartoe het element behoort NS; in het geval dat NS behoort tot meerdere sets of behoort niet tot een set, de waarde van deze functie is niet gedefinieerd.

Exploitanten van de ADT “Union of Sets”:

1. SAMENVOEGEN(EEN , V) combineert componenten EEN en ... v, het resultaat wordt toegewezen aan A of V.

2. VIND(x ) - een functie die de naam retourneert van het onderdeel waartoe het behoort NS.

3. VOORLETTER(EEN , NS ) maakt een component met de naam A die alleen het element bevat NS.

Vertegenwoordiging van de vereniging van sets met behulp van arrays:

De setnaam is hetzelfde als de matrixindexwaarde setheaders ( naam 0 )

Legende:

setheaders - array van set-headers:

§ met tante - het aantal elementen in de set,

§ eerste element - matrixindexnamenmet het eerste element van de set,

namen – array van lijsten van elementen van sets:

setnaam - de naam van de verzameling waartoe het element behoort, volgend element - de index van het volgende element in de lijst van de gegeven set (indexwaarde 0 wordt gebruikt als het einde van de lijst).

Werkprogramma paragraaf 2.1.3

Abstract gegevenstype “ gerichte grafiek "

Basisdefinities:

gerichte grafiek (digraaf ) G = (V, E) bestaat uit veel hoekpunten V en veel bogen e. Vertices worden ook wel knopen , en bogen - georiënteerde ribben . De boog kan worden weergegeven als een geordend paar hoekpunten ( jij, met wie), waar is de top en genaamd het begin , een met wie - het einde bogen.

Ze zeggen ook dat de boog en -> met wie leidt van boven naar boven w, en de top met wie aangrenzend met bovenkant v.

Digraph voorbeeld 1:

Digraph hoekpunten kunnen worden gebruikt om objecten weer te geven, en bogen kunnen worden gebruikt om relaties tussen objecten weer te geven.

Door in een digraaf bedoelen we een reeks hoekpunten v1 , v2 , … , vn , , waarvoor er bogen zijn v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Dit pad begint bovenaan v1 en door de toppen gaan v2 , v3 , ..., vn-1 eindigt bovenaan vn. Pad lengte - het aantal bogen waaruit het pad bestaat, in dit geval is de padlengte NS - 1 ... Beschouw als een speciaal geval van een pad één hoekpunt v als een pad met lengte 0 vanaf het hoekpunt vTot dezelfde piek v... In de figuur vormt de reeks hoekpunten 1, 2, 4 een pad met lengte 2 van hoekpunt 1 naar hoekpunt 4.

Het pad heet eenvoudig , als alle hoekpunten erop, met de mogelijke uitzondering van de eerste en de laatste, verschillend zijn. Fiets - het is een eenvoudig pad met een lengte van minimaal 1 dat begint en eindigt bij hetzelfde hoekpunt. In de figuur vormen de hoekpunten 3, 2, 4, 3 een cyclus van lengte 3.

In veel toepassingen is het handig om wat informatie aan de hoekpunten en bogen van een digraph toe te voegen. Voor deze doeleinden wordt het gebruikt: getagd digraph , dat wil zeggen, een digraph waarin elke boog en/of elk hoekpunt corresponderende labels heeft. Het label kan een naam, gewicht of waarde (bogen) zijn, of een gegevenswaarde van een bepaald type.

Voorbeeld 2 van een gelabelde digraph:

DIV_ADBLOCK149 ">

3. Transitief sluitingsalgoritme (algoritme van Warshall):

Voor de grafiek G = (V, E) het algoritme berekent de transitiviteitsmatrix t, waarvan elk element t[l, J] = 1 alleen als er een pad van boven is l naar de top J en t[ l, J] = 0 anders.

4. Algoritme voor het vinden van het midden van een digraph:

laten zijn en - willekeurig hoekpunt van een digraph G = (V, E). Excentriciteit (maximale verwijdering) topjes en gedefinieerd als

max (minimale padlengte vanaf de bovenkant) met wie naar de top v }

met wie V

digraph centrum G het hoekpunt met de minimale excentriciteit wordt genoemd. Met andere woorden, het midden van de digraph is het hoekpunt waarvoor de maximale afstand (padlengte) tot andere hoekpunten minimaal is.

Voorbeeld: Het midden van de digraph is het hoekpunt NS

		excentriek

5. Algoritme voor het doorlopen van de digraph in de diepte (diepte-eerst zoeken):

Bij het oplossen van veel problemen met betrekking tot gerichte grafieken is een efficiënte methode vereist voor het systematisch doorlopen van hoekpunten en bogen van digraphs. Deze methode is de zogenaamde diepte-eerst zoeken - generalisatie van de preorder tree traversal-methode. Zoeken op diepte begint met het selecteren van het startpunt v Graaf G, dit hoekpunt is gemarkeerd met een label bezocht (bezocht). Dan voor elk hoekpunt naast het hoekpunt v en die nog niet eerder is bezocht, wordt diepte-eerst zoeken recursief toegepast. Wanneer alle toppen die kunnen worden bereikt vanaf de top v, met een bezoek "vereerd" wordt, stopt de zoektocht. Als sommige hoekpunten niet zijn bezocht, wordt er een geselecteerd en wordt de zoekopdracht herhaald. Dit proces gaat door totdat alle hoekpunten van de digraph zijn doorlopen G.

6. Algoritme voor het construeren van een diepe opspannende boom van een grafiek:

Bij het doorlopen van een grafiek met diepte-eerst zoeken, leiden alleen bepaalde bogen naar niet-bezochte hoekpunten. Dergelijke bogen die naar nieuwe hoekpunten leiden, worden boombogen genoemd en vormen de grafiek diepte-eerst overspannend bos – diep overspannen bos ... Bij de aanleg van een bos worden ook drie soorten bogen onderscheiden: omgekeerd, direct en transversaal. Omgekeerde bogen - zulke bogen die van afstammelingen naar voorouders gaan in het uitgestrekte bos. Rechte bogen Er worden bogen genoemd die van voorouders naar echte afstammelingen gaan, maar die geen boombogen zijn.

Bogen die hoekpunten verbinden die geen voorouders of afstammelingen van elkaar zijn, worden genoemd dwarsbogen ... Als bij het construeren van een opspannende boom de zonen van één hoekpunt van links naar rechts worden geplaatst in de volgorde waarin ze worden bezocht, en als nieuwe bomen ook van links naar rechts aan het bos worden toegevoegd, dan gaan alle dwarsbogen van rechts naar links .

Bijvoorbeeld bogen NS-> C en G-> D- dwars, boog C-> EEN- achteruit, er zijn geen rechte bogen.

Bij het diep doorkruisen van een boom is het vaak handig om de hoekpunten te nummeren in de volgorde waarin ze worden bezocht. Dergelijke getallen worden dieptegetallen genoemd.

Digraph vertegenwoordiging:

§ Weergave van een digraph met behulp van een aangrenzende matrix:

Aangrenzende matrix voor digraph G - dit is een matrix EEN de grootte N N met booleaanse waarden, waarbij EEN[ l, J] = waar als en slechts als er een boog is vanaf het hoekpunt l naar hoekpunt j. Vaak is in aangrenzende matrices de waarde waar wordt vervangen door 1, en de waarde vals- naar 0.

Een generalisatie van de representatie van een digraph met behulp van een aangrenzende matrix kan worden beschouwd als een representatie van een gelabelde digraph die ook een aangrenzende matrix gebruikt, maar waarvoor het element EEN[ l, J] gelijk aan booglabel ik ->J. Als bogen vanaf de bovenkant l naar de top J niet bestaat, dan is de waarde A [ l, J] kan niet de waarde zijn van een geldig label, maar kan worden beschouwd als een "lege" cel.

Aangrenzende matrix voor een gelabelde digraph (voorbeeld 2):

§ Weergave van een digraph met behulp van aangrenzende lijsten:

Vertex nabijheidslijst l noemde de lijst van alle hoekpunten naast het hoekpunt l, bovendien op een bepaalde manier geordend. Digraaf G kan worden weergegeven door middel van een array HOOFD(Titel) wiens element HOOFD[l] is een verwijzing naar de lijst met vertex-nabijheid l.

Exploitanten van ATD "Orgraph":

De meest voorkomende operatoren die op gerichte grafieken worden uitgevoerd, zijn onder meer het lezen van hoekpunt en booglabel, hoekpunt en boog invoegen en verwijderen, en het doorlopen van boogreeksen.

Om een ​​reeks aangrenzende hoekpunten te bekijken, zijn de volgende drie operatoren vereist.

1. EERSTE ( v) geeft de index van het eerste hoekpunt naast het hoekpunt v. Als de top v heeft geen aangrenzende hoekpunten, dan wordt een "nul" hoekpunt geretourneerd nul.

2. VOLGENDE ( v, l) geeft de index terug van het hoekpunt naast het hoekpunt v, de index volgen l. Indien l - dit is de index van het laatste hoekpunt naast het hoekpunt v, dan keert het terug nul.

3. VERTEX ( v,l) geeft de top terug met index l van de verzameling hoekpunten aangrenzend aan v.

Opdrachten:

Gegeven een gerichte graaf (digraph):

https://pandia.ru/text/78/308/images/image043_12.gif "width =" 125 "height =" 100 src = ">

Een voorbeeld van een niet-verbonden grafiek:

Fiets (eenvoudig) is een pad van (eenvoudige) lengte van ten minste 3 van elk hoekpunt naar zichzelf. De grafiek heet cyclisch , als het ten minste één cyclus heeft. Een verbonden acyclische graaf, die een "boom zonder wortel" is, heet gratis boom . De tweede figuur hierboven toont een grafiek die bestaat uit twee verbonden componenten, die elk een vrije boom zijn. Van een vrije boom kan een "gewone" boom worden gemaakt als een hoekpunt als wortel is aangewezen en alle randen in de richting van deze wortel zijn georiënteerd.

Losse bomen hebben twee belangrijke eigenschappen:

1. Elke vrije boom met het aantal hoekpunten N, N > 1 , heeft precies N - 1 ribben.

2. Als je een nieuwe rand toevoegt aan een gratis boom, krijg je zeker een cyclus.

laten zijn G = (V, E) - verbonden grafiek waarin elke rand ( R, met wie) gemarkeerd met een nummer met(v, w), Wat genoemd wordt als rib kosten . overspannende boom Graaf G een vrije boom genoemd die alle hoekpunten bevat V Graaf G. Prijs de opspannende boom wordt berekend als de som van de kosten van alle randen in deze boom

Basisalgoritmen voor het verwerken van ongerichte grafieken:

1. Minimale kosten voor constructie van bomen (Prim's algoritme):

Er worden veel toppen gebouwd jij waaruit de opspannende boom "groeit". laten zijn V = (1, 2, ...,N}. Aanvankelijk U = (1). Bij elke stap van het algoritme wordt een voordeel van de minste kosten gevonden ( jij, v) zoals dat jij jij en v V \ U dan top v wordt overgenomen van de set V \ U in een menigte jij... Dit proces gaat door totdat de set jij zal niet gelijk zijn aan de set V.

De opspannende boomconstructievolgorde wordt hieronder gegeven.

https://pandia.ru/text/78/308/images/image048_12.gif "width =" 501 "height =" 384 src = ">

3. DFS-doorgang van ongerichte grafieken:

Diepte-eerst zoeken wordt gebruikt om systematisch alle hoekpunten van de grafiek te doorkruisen. Het diepte-eerst zoekalgoritme is vergelijkbaar met het algoritme voor het doorlopen van de hoekpunten van een digraph. De laatste wordt ook gebruikt voor ongerichte grafieken, aangezien de ongerichte rand (v, met wie) kan worden weergegeven als een paar georiënteerde bogen v -> met wie en met wie -> v.

Dieptetraversal kan worden gebruikt om een ​​opspannende boom te construeren.

De grafiek en de opspannende boom verkregen door het doorlopen van de hoekpunten met behulp van de depth-first zoekmethode worden hieronder getoond:

4. Breedte Zoek eerst op ongerichte grafieken

Een andere methode om systematisch de hoekpunten van een graaf te doorkruisen heet Breedte Eerste zoekopdracht . Het dankt zijn naam aan het feit dat bij het bereiken tijdens het doorlopen van een hoekpunt v verder beschouwen we alle hoekpunten naast het hoekpunt v, dat wil zeggen, de hoekpunten worden "in de breedte" gescand. Deze techniek kan ook worden toegepast op gerichte grafieken.

Net als bij diepte-eerst zoeken, creëert breedte-eerst zoeken een overspannend bos bij het doorkruisen van een grafiek. Als na het bereiken van de top NS als je naar de rib kijkt (x, y) hoekpunt Bij nog niet eerder is bezocht, dan wordt deze rand beschouwd als de rand van de boom. Als de top Bij is al bezocht, de rib (x, y) zal een dwarsrand zijn, omdat het hoekpunten verbindt die niet door overerving met elkaar verbonden zijn.

De Breedte First Spanning Tree wordt hieronder weergegeven.

Weergave van een ongerichte graaf met behulp van een aangrenzende matrix:

Om ongerichte grafieken weer te geven, kunt u dezelfde methoden gebruiken als voor het weergeven van gerichte grafieken, als de ongerichte rand tussen de hoekpunten v en met wie gezien als twee georiënteerde bogen vanaf het hoekpunt v naar de top met wie en van boven met wie naar de top v.

https://pandia.ru/text/78/308/images/image051_12.gif "breedte =" 159 "hoogte =" 106 ">

Een ongerichte grafiek weergeven met behulp van aangrenzende lijsten:

https://pandia.ru/text/78/308/images/image053_12.gif "width =" 339 "height =" 115 src = ">

1. Bouw:

minimale kosten opspannende boom met behulp van het algoritme van Prim;

minimale kosten opspannende boom met behulp van Kruskal's algoritme;

omspannende boom door diepte-eerst zoeken, beginnend bij hoekpunten a en d;

opspannende boom door breedte-eerst zoeken, beginnend bij hoekpunten a en d.

2. Implementeer de algoritmen van Prim en Kruskal.

3. Implementeer het bouwen van een opspannende boom met behulp van diepte-eerst zoeken

§ voor een ongerichte graaf vertegenwoordigd door een aangrenzende matrix,

§ voor ongerichte grafiek vertegenwoordigd door aangrenzende lijsten.

4. Implementeer de constructie van spanbomen met behulp van Breadth First Search

§ voor een ongerichte graaf vertegenwoordigd door een aangrenzende matrix,

§ voor ongerichte grafiek vertegenwoordigd door aangrenzende lijsten.

Ministerie van Onderwijs en Wetenschappen van de Russische Federatie

Federale staatsbegrotingsinstelling voor onderwijs

hoger beroepsonderwijs

NATIONALE ONDERZOEK NUCLEAIRE UNIVERSITEIT "MEPHI"

Dimitrovgrad Engineering Technologisch Instituut

afdeling Informatie Technologie

Toegeven aan bescherming "" 2012

Hoofd stoel Rakova O.A.

cursus werk

door discipline"Object georiënteerd programmeren"

Thema:“Abstracte gegevenstypen. Lijsten "

Voltooid: student gr. VT-31

Shayakov A.F.

Leider: Art. docent bij de afdeling ICT

Alenin V.A.

Normcontroller: Art. docent bij de afdeling ICT

Alenin V.A.

Cijfer:

Beschermingsdatum:

Dimitrovgrad, 2012

Ministerie van Onderwijs en Wetenschappen van de Russische Federatie

Federale staatsbegrotingsinstelling voor onderwijs

hoger beroepsonderwijs

NATIONALE ONDERZOEK NUCLEAIRE UNIVERSITEIT "MEPHI"

Dimitrovgrad Engineering Technologisch Instituut

voor scriptie

Discipline: objectgeoriënteerd programmeren

Onderwerp: Abstracte gegevenstypen. Lijsten

Kunstenaar: Shayakov A.F.

Hoofd: V.A. Alenin

1. Theoretisch deel:

Abstracte gegevenstypen. Objectgeoriënteerd programmeerconcept. Lineaire enkelvoudig gekoppelde lijsten.

2.Praktisch deel:

Schrijf in C++ een programma met een objectgeoriënteerde structuur om lineaire enkelvoudig gelinkte lijsten te implementeren.

Termijnen van voltooiing van het werk op schema:

Theoretisch gedeelte - 15% per week 5

Praktijkgedeelte - 80% tegen week 7

Experimentele sectie - ____% per ____ week

Bescherming - 100% tegen week 10

Vereisten voor registratie:

De afrekening en toelichting van de term paper dienen elektronisch en op papier te worden ingediend;

Het volume van het rapport moet minimaal 20 getypte pagina's zijn exclusief bijlagen

RPZ is ondertekend door de persoon die verantwoordelijk is voor de wettelijke controle

Werkleider _________________

Aannemer _________________________

Uitgiftedatum "_____" ___________ 2012

A.F. SHAYAKOV THEMA: ABSTRACTE GEGEVENSTYPES. LIJSTEN, cursussen / DITI, nr. 230105.65-Dimitrovgrad, 2012. - 29 pagina's, afb. 11, bibl. naam 10, bijlage 1.

Trefwoorden: lineair enkelvoudig gekoppelde lijsten, C++, objectgeoriënteerd programmeren.

Het onderzoeksobject zijn lineaire enkelvoudig gekoppelde lijsten.

Het doel van het werk is het bestuderen van lineaire enkelvoudig gekoppelde lijsten en het schrijven van een programma in C++ met een objectgeoriënteerde structuur voor hun implementatie.

Conclusies: in dit werk hebben we lineaire enkelvoudig gekoppelde lijsten volledig bestudeerd, evenals de methoden voor hun representatie in het geheugen. Het programma geschreven in de C ++ -taal voldoet volledig aan de objectgeoriënteerde structuur, vervult correct en efficiënt zijn hoofdtaak - het implementeert lineaire enkelvoudig gekoppelde lijsten.

Inleiding 6

1 Theoretisch deel 7

1.1 Abstracte gegevenstypen. Lineaire lijsten 7

1.2 Concept van objectgeoriënteerd programmeren 8

2 Praktijkgedeelte 15

3 Testen 23

Conclusie 25

Referenties 26

Bijlage A 27

Invoering

Vaak is het tijdens het werken met gegevens onmogelijk om te bepalen hoeveel geheugen nodig is om ze op te slaan; geheugen moet tijdens de uitvoering van het programma zo nodig in afzonderlijke blokken worden toegewezen. Blokken worden aan elkaar gekoppeld door middel van pointers. Deze manier om gegevens te ordenen wordt een dynamische gegevensstructuur genoemd omdat deze zich in een heap bevindt en tijdens de uitvoering van het programma van grootte verandert.

In dit werk worden lineaire lijsten gebruikt vanuit dynamische structuren. Een dynamische structuur kan, in tegenstelling tot een array of record, niet-aaneengesloten RAM-gebieden in beslag nemen.

Dynamische structuren worden ook veel gebruikt voor efficiënter werken met data waarvan de omvang bekend is, vooral voor het oplossen van sorteerproblemen.

Een element van elke dynamische structuur bestaat uit twee delen: informatief, ter wille van de opslag waarvan de structuur wordt gemaakt, en pointers die zorgen voor de verbinding van elementen met elkaar.

1. Theoretisch gedeelte

1.1 Abstracte gegevenstypen. Lineaire lijsten

Abstracte datatypes zijn sleutelbegrippen bij het programmeren. Abstractie impliceert scheiding en onafhankelijke overweging van interface en implementatie.

Gegevensabstractie omvat de definitie en overweging van abstracte gegevenstypen (ADT's) of, wat hetzelfde is, nieuwe gegevenstypen die door de gebruiker zijn ingevoerd.

Een abstract gegevenstype is een verzameling gegevens samen met vele bewerkingen die op die gegevens kunnen worden uitgevoerd.

Lineaire lijsten

In een lineaire lijst is elk item gerelateerd aan het volgende en mogelijk het vorige. In het eerste geval wordt de lijst eenvoudig verbonden genoemd, in het tweede - dubbel verbonden. Als het laatste element door een aanwijzer naar het eerste is gekoppeld, is het resultaat een cirkelvormige lijst.

Elk item in de lijst bevat een sleutel die dat item identificeert. De sleutel is meestal een geheel getal of een tekenreeks en maakt deel uit van het gegevensveld. Verschillende delen van het gegevensveld kunnen als sleutel fungeren bij het werken met de lijst. De sleutels van verschillende elementen van de lijst kunnen hetzelfde zijn.

U kunt de volgende bewerkingen op lijsten uitvoeren:

initiële vorming van de lijst (creatie van het eerste element);

een item toevoegen aan het einde van de lijst;

het lezen van een element met een bepaalde sleutel;

een element invoegen op een bepaalde plaats in de lijst (voor of na een element met een bepaalde sleutel);

het verwijderen van een element met een bepaalde sleutel;

de lijst per toets bestellen.

Om met een lijst in een programma te werken, moet u een aanwijzer naar het begin definiëren. U kunt de aanwijzer ook naar het einde van de lijst bewegen om het gemakkelijker te maken om nieuwe items aan het einde van de lijst toe te voegen.

1.2 Concept van objectgeoriënteerd programmeren

Volgens Grady Booch, een autoriteit op het gebied van objectgeoriënteerde programmeermethoden, "is objectgeoriënteerd programmeren (OOP) een programmeermethodologie die is gebaseerd op het weergeven van een programma als een verzameling objecten, die elk een implementatie zijn van een bepaalde klasse ( soort van speciale soort), en de klassen vormen een hiërarchie op basis van de principes van overerving."

Objectgeoriënteerde methodologie, zoals structurele methodologie, werd gecreëerd met als doel het proces van het ontwikkelen van grote softwarepakketten te disciplineren en daardoor hun complexiteit en kosten te verminderen.

Een objectgeoriënteerde methodologie streeft dezelfde doelen na als een gestructureerde methodologie, maar benadert ze vanuit een ander uitgangspunt en stelt u in de meeste gevallen in staat om complexere projecten te beheren dan een gestructureerde methodologie.

Zoals u weet, is decompositie een van de principes van projectcomplexiteitsbeheer. Grady Booch onderscheidt twee soorten decompositie: algoritmische (zoals hij decompositie noemt ondersteund door structurele methoden) en objectgeoriënteerd, waarbij het verschil naar zijn mening als volgt is: speciale betekenis voor factoren, die ofwel acties veroorzaken, ofwel de objecten zijn van toepassing van deze acties ”.

Met andere woorden, algoritmische decompositie houdt meer rekening met de structuur van relaties tussen delen van een complex probleem, terwijl objectgeoriënteerde decompositie zich meer richt op de aard van relaties.

In de praktijk wordt aanbevolen om beide soorten decompositie te gebruiken: bij het maken van grote projecten is het raadzaam om eerst een objectgeoriënteerde benadering toe te passen om een ​​algemene hiërarchie van objecten te creëren die de essentie van de geprogrammeerde taak weerspiegelt, en vervolgens algoritmische decompositie te gebruiken in modules om de ontwikkeling en het onderhoud van het softwarepakket te vereenvoudigen.

OO-programmering is ongetwijfeld een van de meest interessante gebieden voor professionele softwareontwikkeling.

Objecten en klassen

De basisbouwstenen van een objectgeoriënteerd programma zijn objecten en klassen. Inhoudelijk kan een object worden weergegeven als iets dat wordt gevoeld of ingebeeld en heeft het een goed gedefinieerd gedrag. Zo kan een object ofwel worden gezien of aangeraakt, of tenminste weten dat het bijvoorbeeld wordt weergegeven als informatie die is opgeslagen in het geheugen van de computer. Laten we de definitie van een object geven, in overeenstemming met de mening van GradiBuch: "Een object is een tastbare entiteit die zijn gedrag duidelijk manifesteert."

Een object is een deel van de werkelijkheid die ons omringt, dat wil zeggen, het bestaat in tijd en ruimte (voor de eerste keer werd het concept van een object in de programmering geïntroduceerd in de Simula-taal). Formeel is het object moeilijk te definiëren. Dit kan door middel van enkele eigenschappen, namelijk: een object heeft status, gedrag en is uniek te identificeren (met andere woorden, heeft een unieke naam).

Een klasse is een verzameling objecten die een gemeenschappelijke structuur en gemeenschappelijk gedrag delen. Een klasse is een beschrijving (abstractie) die laat zien hoe een variabele van deze klasse kan worden geconstrueerd die in tijd en ruimte bestaat, een object genoemd. De betekenis van de zinnen "beschrijving van klassevariabelen" en "beschrijving van klasseobjecten" is hetzelfde.

Het object heeft een staat, gedrag en paspoort (middel voor zijn unieke identificatie); de structuur en het gedrag van objecten worden beschreven in de klassen waarvan ze variabelen zijn.

Laten we nu de concepten van toestand, gedrag en identificatie van een object definiëren.

De toestand van een object combineert al zijn gegevensvelden (statische component, d.w.z. onveranderlijk) en de huidige waarden van elk van deze velden (dynamische component, d.w.z. meestal veranderend).

Gedrag drukt de dynamiek uit van veranderingen in de toestand van een object en zijn reactie op inkomende berichten, d.w.z. hoe een object van toestand verandert en interageert met andere objecten.

Identificatie (herkenning) van een object is een eigenschap waarmee u een object kunt onderscheiden van andere objecten van dezelfde of verschillende klassen. Identificatie gebeurt door middel van een unieke naam (paspoort), die net als elke andere variabele in het programma aan het object wordt toegekend.

Hierboven is al gezegd dat de procedurele (en ook modulaire) benadering het mogelijk maakt om programma's te bouwen die bestaan ​​uit een reeks procedures (subroutines) die de gegeven algoritmen implementeren. Aan de andere kant stelt de objectgeoriënteerde benadering programma's voor als een verzameling objecten die met elkaar interageren. De interactie van objecten wordt uitgevoerd door middel van berichten. Laten we aannemen dat ons object een cirkel is. Dan zou het bericht dat naar dit object wordt gestuurd, kunnen zijn: "teken jezelf". Als we zeggen dat een bericht wordt doorgegeven aan een object, dan roepen we in feite een functie van dit object aan (component-functie). Dus in het bovenstaande voorbeeld zullen we een functie aanroepen die een cirkel op het scherm zal tekenen.

inkapseling

Inkapseling is een van de fundamentele principes van objectgeoriënteerd programmeren, waarvan het idee is dat alle eigenschappen en methoden worden gecombineerd binnen een object.

De naam van de term "inkapseling" komt van het Engelse woord encapsulate, wat letterlijk betekent "in een capsule verzegelen" of "bedekken met een schaal". Een object (capsule) bevat dus methoden en eigenschappen (inhoud).

Inkapseling kan in een bredere zin worden gezien, veel verder dan objectgeoriënteerd programmeren in het algemeen. Als we het hebben over inkapseling op het hoogst mogelijke abstractieniveau, dan kan inkapseling worden gezien als het vermogen van een object om een ​​verscheidenheid aan andere objecten te bevatten. Dus met betrekking tot een computerprogramma kunnen we zeggen dat het verschillende modules inkapselt, die elk op hun beurt een aantal objecten inkapselen die methoden en eigenschappen inkapselen, die trouwens ook objecten kunnen zijn, enzovoort.

Op basis van al het bovenstaande kan een andere weergave van inkapseling elke boomstructuur zijn waarin elk knooppunt van de boom al zijn directe kinderen inkapselt, wat ofwel bladeren kunnen zijn (primitieven die niets op zichzelf kunnen inkapselen) of andere knooppunten.

En toch, als we het hebben over objectgeoriënteerd programmeren, dan is inkapseling de vereniging van gegevens en methoden binnen een object.

Soms sprekend van inkapseling in objectgeoriënteerd programmeren, wordt het concept van inkapseling gelijkgesteld aan het concept van "zwarte doos" of gegevens verbergen, maar ze zijn niet hetzelfde. Ja, in sommige objectgeoriënteerde programmeertalen kan de ontwikkelaar met behulp van inkapseling van zijn object een zwarte doos maken, maar dit wordt geïmplementeerd met behulp van toegangsmodificaties, die niet in alle objectgeoriënteerde programmeertalen beschikbaar zijn. Het concept van inkapseling is veel breder. En zelfs meer dan dat, we kunnen alle eigenschappen en methoden van buitenaf toegankelijk maken, dat wil zeggen, er kan geen sprake zijn van een black box, maar inkapseling zal nog steeds in elk object aanwezig zijn. Daarom is het verbergen van gegevens door middel van toegangsmodifiers een gevolg van inkapseling, maar zijn op geen enkele manier identieke concepten.

Ten eerste zijn objecten dankzij inkapseling niet langer alleen door de gebruiker gedefinieerde datastructuren, waarvan het hoofddoel eenvoudigweg logisch is om verschillende afzonderlijke datatypes te combineren in het kader van een nieuw samengesteld datatype. Dankzij inkapseling kan elk object nu gegevens bevatten die de toestand van het object en zijn gedrag beschrijven in de vorm van methoden. Met andere woorden, een object in objectgeoriënteerd programmeren is niet langer een primitief passief gegevenstype waarvan de controle volledig overgeleverd is aan de externe omgeving, maar begon zijn eigen gedrag te vertonen, je zou zelfs kunnen zeggen dat een zekere wil en geest, het vermogen om actief te reageren op externe invloeden en de staat ervan te veranderen, en volgens hun eigen wet- en regelgeving.

Ten tweede geeft inkapseling ons de mogelijkheid om de toegang tot objectgegevens te controleren. Zichtbaarheidsbeperking kan ook worden gezien als een manifestatie van de eigen wil van het object - het object beslist zelf welk gedrag of eigenschappen voor iedereen beschikbaar worden gesteld, wat alleen beschikbaar wordt gesteld aan een bepaalde reeks objecten en wat volledig intiem, waarover het geen ander object zal kennen. Waarom, maar omdat alleen het object zelf precies weet hoe ermee te werken en hoe niet. Je kunt zelfs spreken van een nieuwe filosofie van programmeren, waarbij objecten meer op objecten zijn waarop bepaalde acties worden uitgevoerd, en, als ik het zo mag zeggen, een nieuwe vorm van abstracte synthetische geest, interactie waarmee je het gewenste resultaat kunt bereiken.

En ik herhaal nogmaals dat het dankzij inkapseling is dat een object kan worden begiftigd met enige wil, rede, het vermogen om te reageren op externe invloeden, en geen passieve gegevensopslag te zijn.

Erfenis

Overerving is een van de vier belangrijkste mechanismen van objectgeoriënteerd programmeren (samen met inkapseling, polymorfisme en abstractie), waarmee je een nieuwe klasse kunt beschrijven op basis van een bestaande (bovenliggende) klasse, terwijl de eigenschappen en functionaliteit van de bovenliggende klasse worden geleend door de nieuwe klas.

Met andere woorden, de overervende klasse implementeert de specificatie van een reeds bestaande klasse (basisklasse). Hierdoor kunt u objecten van de overgeërfde klasse op dezelfde manier behandelen als met objecten van de basisklasse.

Overervingstypen

eenvoudige overerving

De klasse waaruit de overerving afkomstig is, wordt base of parent (Engelse baseclass) genoemd. Klassen die afstammen van de basis worden afstammelingen, afstammelingen of afgeleide klassen genoemd.

Sommige talen gebruiken abstracte klassen. Een abstracte klasse is een klasse die ten minste één abstracte methode bevat, deze wordt beschreven in het programma, heeft velden, methoden en kan niet worden gebruikt om rechtstreeks een object te maken. Dat wil zeggen, u kunt alleen erven van een abstracte klasse. Objecten worden alleen gemaakt op basis van afgeleide klassen die zijn overgenomen van de samenvatting.

Een abstracte klasse kan bijvoorbeeld een basisklasse "universiteitsmedewerker" zijn, waarvan de klassen "afgestudeerde student", "professor", enz. worden geërfd. Aangezien afgeleide klassen gemeenschappelijke velden en functies hebben (bijvoorbeeld het veld "jaar van geboorte"), kunnen deze klasseleden worden beschreven in de basisklasse. Het programma maakt objecten op basis van de klassen "afstudeerder", "hoogleraar", maar het heeft geen zin om een ​​object te maken op basis van de klasse "universiteitsmedewerker".

meervoudige overerving

Bij meervoudige overerving kan een klasse meer dan één voorouder hebben. In dit geval erft de klasse de methoden van alle voorouders. Het voordeel van deze aanpak is een grotere flexibiliteit. Meervoudige overerving is geïmplementeerd in C++. Andere talen die deze mogelijkheid bieden zijn onder andere Python en Eiffel. Meerdere overerving wordt ondersteund in de UML.

Meervoudige overerving is een mogelijke bron van fouten die kunnen optreden als gevolg van de aanwezigheid van dezelfde methodenamen in voorouders. In talen die gepositioneerd zijn als erfgenamen van C++ (Java, C#, etc.) werd besloten om meervoudige overerving te laten varen ten gunste van interfaces. U kunt bijna altijd zonder dit mechanisme. Als een dergelijke behoefte zich echter toch voordoet, is het, om conflicten bij het gebruik van overgenomen methoden met dezelfde naam op te lossen, bijvoorbeeld mogelijk om de zic- "::" - toe te passen om een ​​specifieke methode van een specifieke ouder.

Een poging om het probleem van de aanwezigheid van dezelfde methodenamen in voorouders op te lossen, werd ondernomen in de Eiffel-taal, waarin het bij het beschrijven van een nieuwe klasse noodzakelijk is om expliciet de geïmporteerde leden van elk van de overgeërfde klassen en hun naamgeving aan te geven in de kinderklas.

De meeste moderne objectgeoriënteerde programmeertalen (C #, C ++, Java, Delphi, enz.) ondersteunen de mogelijkheid om gelijktijdig te erven van een voorouderklasse en methoden van verschillende interfaces met dezelfde klasse te implementeren. Met dit mechanisme kunt u meerdere overervingen grotendeels vervangen - interfacemethoden moeten expliciet worden overschreven, waardoor fouten worden geëlimineerd bij het overnemen van de functionaliteit van dezelfde methoden van verschillende voorouderklassen.

1. Praktijkgedeelte

Om dit probleem op te lossen, wordt een objectgeoriënteerde programmastructuur gebruikt. Het programma wordt vertegenwoordigd door twee klassen en een hoofd-cpp-bestand met een gebruikersinterface voor het gemak van het werken met lijsten.

De klasse cList is een lineaire, enkelvoudig gekoppelde lijst met objecten van de klasse cElement.

De klasse cElement heeft de volgende structuur:

cElement * volgende;

~ cElement (ongeldig);

ongeldige setdata (int);

void setref (cElement *);

cElement * getref ();

Het dataveld van het type int bevat de numerieke waarde van het list element, het volgende veld van het cElement * type bevat een link naar het volgende element in de lijst. De methoden setdata en getdata worden gebruikt om toegang te krijgen tot het privégegevensveld van de klasse om de waarde van dit veld te krijgen en dienovereenkomstig in te stellen. De setref-methode wordt gebruikt om een ​​link in te stellen van het huidige naar het volgende item in de lijst, en getref wordt gebruikt om naar het volgende item te navigeren.

void cElement :: setdata (int sd)

int cElement :: getdata ()

geef dit terug-> gegevens;

void cElement :: setref (cElement * rf)

cElement * cElement :: getref ()

returnthis-> volgende;

De implementatie van deze methoden is uiterst eenvoudig, zoals blijkt uit hun programmacodes die hierboven zijn weergegeven.

Laten we nu eens kijken naar de structuur van de klasse cList

#include "cElement.h"

cElement * hoofd;

ongeldig Toevoegen (int);

ongeldig Invoegen (int, int);

ongeldig Verwijderen (int);

ongeldig Alles verwijderen ();

Deze klasse bevat een link naar het head-element van de lijst - head, van het type cElement *. Het opslaan van deze koppeling is nodig voor het correct uitvoeren van bewerkingen voor het toevoegen, verwijderen van gegevens en het afdrukken van de lijst. Het feit is dat bij het uitvoeren van een van de bovenstaande bewerkingen de lijstitems worden opgesomd om de gewenste te bereiken, aangezien de lijst geen willekeurige toegang tot de elementen heeft, daarom is het rationeler om de opsomming te starten vanaf de " hoofd" van de lijst. Naast de link naar het begin van de lijst, heeft elk object van deze klasse een elcount-veld dat het aantal elementen in de lijst bevat.

Laten we ons onderzoek van deze klasse voortzetten door de methoden te onderzoeken die erin zijn geïmplementeerd voor het werken met lijsten.

Methode toevoegen - gegevens toevoegen aan het einde van de lijst.

Als parameter accepteert deze methode een numerieke waarde (variabele xd), die moet worden opgeslagen in het toegevoegde lijstitem.

void cList :: Toevoegen (int xd)

Dit is hoe een nieuw element wordt gemaakt en de waarde van het numerieke veld wordt ingesteld:

cElement * temp = nieuwcElement;

temp-> setdata (xd);

Daarna wordt het aantal elementen in de lijst gecontroleerd, als de lijst leeg is, wordt het head-element gemaakt, anders de "gewone" component van de lijst:

als (elcount == 0)

temp-> setref (NULL);

temp-> setref (NULL);

p -> setref (temp);

U kunt opmerken dat de bovenstaande constructie de setref-methode van de cElement-klasse gebruikt, die nodig is om een ​​link naar het volgende element in de lijst in te stellen, anders zal de lijst ongebonden zijn, wat gepaard gaat met gegevensverlies en onjuiste programmawerking.

Bij de eerste start van het programma wordt de hierboven beschreven methode gebruikt om achtereenvolgens items aan de lijst toe te voegen, waarmee u vervolgens kunt werken; om de invoer in de opdrachtregel te stoppen, moet u de opdracht "stop" invoeren in plaats van de numerieke waarde van het item (zie afbeelding 1).

Afbeelding 1 - Het proces van het toevoegen van items aan de lijst

Na het invoeren van het "stop"-commando wordt de lijst afgedrukt en gaat het programma in de wachtmodus voor commando's (zie figuur 2).

Afbeelding 2 - Afgedrukte lijst

Afdrukmethode - drukt de lijst af.

Voor het printen is het belangrijk om het begin van de lijst te kennen om zo de waarden van alle elementen van de lijst consistent af te drukken, dus in de temp variabele wordt een link naar de "head" van de lijst gezet, waarna de het bestaan ​​van de lijst wordt gecontroleerd en het bijbehorende bericht wordt weergegeven, als het niet wordt bevestigd, als de lijst niet leeg is, wordt het weergegeven:

void cLijst :: Afdrukken ()

cElement * temp = hoofd;

if (temp == NULL) cout while (temp! = NULL)

temp = temp-> getref ();

Del-methode - het startelement van de lijst verwijderen.

Om het eerste element te verwijderen, moet u eerst de link naar het volgende onderdeel van de lijst verplaatsen, waardoor het op deze manier de eerste wordt, en vervolgens het vereiste element verwijderen:

voidcList :: Del ()

cElement * temp = hoofd;

hoofd = hoofd-> getref ();

RemoveAll-methode - verwijdert de volledige lijst.

Deze methode is gebaseerd op het bovenstaande en bestaat uit het achtereenvolgens verwijderen van de eerste elementen van de lijst totdat de hele lijst is verwijderd.

void cList :: Alles verwijderen ()

terwijl (elcount! = 0)

Om deze methode uit te voeren, voert u de opdracht "dellist" in het menu voor het werken met de lijst in (zie afbeelding 3).

Afbeelding 3 - Het commando invoeren om de lijst te wissen

En als de gebruiker echt vertrouwen heeft in zijn acties, is het noodzakelijk om het aanbod van het programma te accepteren, waarna de hele lijst wordt verwijderd (zie figuur 4).

Afbeelding 4 - Lege lijst

Methode verwijderen - verwijdert een specifiek item uit de lijst.

Minder radicale methode dan de vorige. Slechts één lijstitem dat als parameter is opgegeven, wordt verwijderd. Dit gebeurt als volgt: het programma controleert eerst de juistheid van de ingevoerde parameter, als het nummer van het verwijderde element kleiner is dan één of meer dan het totaal aantal elementen in de lijst, dan geeft het een foutmelding, maar als het programma geen klachten heeft over de ingevoerde parameter, dan worden de noodzakelijke koppelingen van de elementen die zich in de buurt bevinden, overgedragen met de verwijderde, zodat de lijst gekoppeld blijft, waarna het vereiste element wordt verwijderd.

void cList :: Verwijderen (int del)

cElement * cur = hoofd, * de;

if ((del> = 1) && (del

hoofd = hoofd-> getref ();

terwijl (j! = del-1)

cur = cur-> getref ();

de = cur-> getref ();

cur-> setref (de-> getref ());

coutsystem ("pauze");

Om deze methode uit te voeren, voert u de opdracht "delete" in het menu voor het werken met de lijst in. Voer vervolgens het nummer van het te verwijderen element in of het "terug"-commando om het verwijderen te annuleren (zie figuur 5).

Afbeelding 5 - Het proces voor het verwijderen van een lijstitem

De lijst ziet er na het verwijderen van het vierde element als volgt uit (zie figuur 6).

Afbeelding 6 - Lijst na het verwijderen van één element

Invoegmethode - een nieuw item invoegen op een opgegeven locatie in de lijst.

Deze methode heeft als parameters: de positie van het toegevoegde element en zijn numerieke waarde. Het nieuwe element zal precies op de opgegeven plaats staan, dus de elementen rechts van het huidige zullen één positie worden verschoven. Wanneer u een nieuw element aan het begin van de lijst toevoegt, hoeft u alleen maar de link van dit element naar het volgende over te brengen, waardoor de lijst wordt gekoppeld en een link naar het oorspronkelijke element wordt verschaft. Een iets andere situatie doet zich voor bij het toevoegen van een nieuw element tussen twee bestaande, hiervoor gaat u met behulp van een lus naar het invoegpunt van het element en koppelt u vervolgens de componenten rechts en links ervan aan het nieuwe element. Immers, wat moet er bijvoorbeeld gebeuren als het nodig is om de ketting te verlengen: je moet hem openen, dan een nieuwe schakel aan het eerste deel van de ketting bevestigen, de tweede aan dezelfde schakel bevestigen, iets soortgelijks wordt in deze methode geïmplementeerd. Het is vermeldenswaard dat als u een onjuiste positie opgeeft voor het toevoegen, die kleiner is dan één of meer dan het totale aantal elementen, het programma een passende foutmelding zal weergeven.

void cList :: Invoegen (int pos, int val)

cElement * cur = hoofd;

cElement * temp = nieuw cElement;

temp-> setdata (waarde);

if ((pos> = 1) && (pos

temp-> setref (hoofd);

terwijl (j! = pos-1)

cur = cur-> getref ();

p = cur-> getref ();

cur-> setref (temp);

temp-> setref (p);

coutsystem ("pauze");

Om deze methode uit te voeren, voert u de opdracht "insert" in het menu voor het werken met de lijst in. Voer vervolgens de positie en numerieke waarde van het toegevoegde element of het "terug"-commando in om het verwijderen te annuleren (zie figuur 7).

Afbeelding 7 - Het proces van het invoegen van een element

Na het toevoegen van een element met een waarde van 111 aan de derde positie, ziet de lijst er als volgt uit (zie figuur 8).

Afbeelding 8 - Lijst na het toevoegen van een element

In de loop van de beschrijving is het menu voor het werken met de lijst meer dan eens genoemd, het moet nog worden opgemerkt dat dit menu het werken met de lijst enorm vergemakkelijkt. Het algoritme van zijn werk bestaat uit een cyclische oproep van dezelfde methoden, bijvoorbeeld het afdrukken van een lijst totdat een bepaald commando wordt ingevoerd. De lijst met beschikbare commando's kan worden bekeken door "help" in de console te typen (zie figuur 9)

Afbeelding 9 - Beschikbare opdrachten

De volledige menucode staat in Bijlage A.

1. Testen

Vaak doen zich tijdens het werk situaties voor die verband houden met onjuiste gegevensinvoer, waardoor het programma kan mislukken. Natuurlijk moet elk programma beveiligingsalgoritmen van een onervaren gebruiker implementeren, om te voorkomen dat het programma crasht. Laten we eens kijken hoe dergelijke algoritmen werken in het gemaakte programma.

De eerste invoer van de lijst gebeurt met de volgende code:

if (atoi (ss)! = NULL)

mijnlijst.Toevoegen (atoi (ss));

Voordat de add-methode wordt aangeroepen om een ​​nieuw item aan de lijst toe te voegen, wordt de invoerreeks gecontroleerd. De functie atoi converteert een tekenreeks naar een numerieke waarde en retourneert NULL als de invoertekenreeks geen getal is. Dus bij het invoeren worden alle regels die geen cijfers zijn genegeerd, behalve de regel met het commando om de invoer te stoppen (zie afbeelding 10).

Afbeelding 10 - Verkeerde gegevens invoeren

Na het invoeren van dergelijke gegevens ziet de lijst er als volgt uit (zie figuur 11).

Afbeelding 11 - Ontvangen lijst

Het programma blijft correct werken na het invoeren van foutieve gegevens. Soortgelijke methoden voor het omgaan met onjuiste gegevens worden gebruikt voor de rest van de invoerbewerkingen die in het programma aanwezig zijn.

Conclusie

In dit werk werden concepten verkregen over abstracte datatypes, over de principes van hun representatie in moderne programmeertalen, in het bijzonder in C++. In de meeste moderne imperatieve talen is het belangrijkste concept dat wordt gebruikt om abstracties in programmacode te beschrijven de objectgeoriënteerde benadering. Objectgeoriënteerd programmeren (OOP) is, net als de op ADT gebaseerde benadering van programmeren, tot op zekere hoogte een ontwikkeling van ideeën over modulair programmeren. Modules zijn programmaonderdelen die twee belangrijke eigenschappen hebben:

Modules verbergen implementatiedetails.

Modules kunnen worden hergebruikt in verschillende delen van het programma.

David Parnas presenteerde in zijn werk uit 1972 modules als abstracte machines die toestanden in zichzelf opslaan en deze toestand door een specifieke reeks bewerkingen laten veranderen. Dit concept is basaal, zowel voor het concept van abstracte datatypes als voor objectgeoriënteerd programmeren. Door parallellen te trekken tussen het werk van Parnas en moderne OOP-concepten, is het gemakkelijk om de relatie tussen de concepten klasse en module te zien.

In dit werk worden lineaire enkelvoudig-gekoppelde lijsten, die een abstract gegevenstype zijn, weergegeven door de ontwikkelde modules, voor toegang tot de toestanden waarvan ook speciale bewerkingen zijn geïmplementeerd, methoden genoemd in objectgeoriënteerd programmeren.

Bibliografie

1. Ian Graham Objectgeoriënteerde methoden. Principes en praktijk = objectgeoriënteerde methoden: principes en praktijk. - 3e druk. - M.: "Williams", 2004. - S. 880.

2. Anthony Sintes Meester objectgericht programmeren in 21 dagen = Sams leert uzelf objectgericht programmeren in 21 dagen. - M.: "Williams", 2002. - P. 672.

3. Bertrand Meyer Objectgericht ontwerpen van softwaresystemen + CD. Internet University of Information Technologies - INTUIT.ru, Russische editie, 2005

4. Billig V.A. Grondbeginselen van C # Programmeren. Internet Universiteit voor Informatietechnologie - INTUIT.ru, 2006

5. "Nieuwe programmeertalen en tendensen van hun ontwikkeling", V. Ushkova, 2005

6. Bjarne Stroustrup "The C ++ Programming Language" Special Edition of 3rd ed. Binom, Nevsky Dialect, ISBN 5-7989-0226-2, 5-7940-0064-3, 0-201-70073-5

7. Bjarne Stroustrup "Ontwerp en evolutie van de C++-taal". DMK-Press, Peter, ISBN 5-469-01217-4, 0-201-54330-3

8. Bjarne Stroustrup "Programmeerprincipes en praktijk van het gebruik van C ++". "ID Williams", 2011, ISBN 978-5-8459-1621-1 (Russisch)

9. Grady Booch et al. "Objectgeoriënteerde analyse en ontwerp met voorbeeldtoepassingen" 2e of 3e editie. Binom, Nevsky-dialect, Williams ISBN 978-5-8459-1401-9, 0-201-89551-X, 0-8053-5340-2, 5-7989-0067-3, 5-7940-0017-1

10. Scott Meyers "C++ effectief gebruiken. 50 beste praktijken voor het verbeteren van uw programma's en projecten" DMK, Peter, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1

Bijlage A

Menu programmacode

#include "cList.h"

#include "string.h"

namespace std; gebruiken;

coutwhile (strstr (ss, "stop") == NULL)

if (atoi (ss)! = NULL)

mijnlijst.Toevoegen (atoi (ss));

systeem ("cls");

while (strstr (com, "exit") == NULL)

coutmylist.Print ();

if (strstr (com, "help")! = NULL) com_ind = 1;

if (strstr (com, "toevoegen")! = NULL) com_ind = 2;

if (strstr (com, "insert")! = NULL) com_ind = 3;

if (strstr (com, "verwijderen")! = NULL) com_ind = 4;

if (strstr (com, "dellist")! = NULL) com_ind = 5;

schakelaar (com_in)

systeem ("cls");

systeem ("cls");

coutcoutcoutcoutcoutcoutcom_ind = 0;

if (strstr (ss, "terug") == NULL)

if (atoi (ss)! = NULL)

mijnlijst.Toevoegen (atoi (ss));

systeem ("cls");

// voeg elementen in

if (strstr (ss, "terug") == NULL)

if (atoi (ss)! = NULL)

systeem ("cls");

if (strstr (ss, "terug") == NULL)

if (atoi (ss)! = NULL)

mijnlijst.Invoegen (pos, atoi (ss));

systeem ("cls");

// elementen verwijderen

if (strstr (ss, "back") == NULL) wordt gedefinieerd door een reeks waarden gegeven en een reeks operaties ... verbonden structuren gegevens – lijsten... Structuur gegevens Is een verzameling elementen gegevens, waartussen ... in het computergeheugen wordt genoemd abstract of logisch. Vaker...

Meerdere soort van gegevens... de sets

Lezing >> Informatica, programmeren

... soort van gelijk aan simple types gegevens... Meervoud types beschreven in sectie: types... WU kan worden beschreven. Abstract computationele structuren die input beschrijven ... andere gevallen types alle componenten lijst moet overeenkomen type bestandscomponenten. ...

Objectgeoriënteerde databases gegevens werken in gedistribueerde netwerken

Samenvatting >> Informatica

Gebieden van programmeertalen ontwikkelen met abstract types gegevens en objectgeoriënteerde programmeertalen. ... types gegevens- lijst en array. Elke letterlijke wordt uniek geïdentificeerd door een index in de array en een ordinale in de lijst ...

Abstract informatiebeveiligingsmodellen

Samenvatting >> Informatica

Informatiebeveiliging ……………………………………………… ..17 Abstract informatiebeveiligingsmodellen ... die de interactie met beide regelen types gegevens(Certificatieregels): Alle ... diverse variaties en aanvullingen op bestaande de lijst... Beveiligingsniveaus - bepaalde ...

Abstract gegevenstype

Abstract gegevenstype (BIJ D) is een gegevenstype dat een bepaalde reeks functies biedt voor het werken met elementen van dit type, evenals de mogelijkheid om elementen van dit type te maken met behulp van speciale functies. De hele interne structuur van dit type is verborgen voor de softwareontwikkelaar - dit is de essentie van abstractie. Een abstract datatype definieert een set implementatie-onafhankelijke functies van het type om op zijn waarden te werken. De specifieke implementaties van de ADT worden datastructuren genoemd.

Bij het programmeren worden abstracte gegevenstypen meestal weergegeven als interfaces die de bijbehorende type-implementaties verbergen. Programmeurs werken uitsluitend met abstracte gegevenstypen via hun interfaces, omdat de implementatie in de toekomst kan veranderen. Deze benadering is consistent met het principe van inkapseling in objectgeoriënteerd programmeren. Het sterke punt van deze techniek is het verbergen van de implementatie. Zodra alleen de interface buiten is gepubliceerd, blijven alle programma's die met de gegeven structuur van het abstracte gegevenstype werken, zolang de gegevensstructuur deze interface ondersteunt. Ontwikkelaars van datastructuren proberen, zonder de externe interface en semantiek van functies te veranderen, de implementaties geleidelijk te verfijnen en de algoritmen te verbeteren in termen van snelheid, betrouwbaarheid en gebruikt geheugen.

Het verschil tussen abstracte gegevenstypen en gegevensstructuren die abstracte typen implementeren, kan aan de hand van het volgende voorbeeld worden geïllustreerd. De abstracte gegevenstypelijst kan worden geïmplementeerd met behulp van een array of een lineaire lijst met behulp van verschillende dynamische geheugentoewijzingsmethoden. Elke implementatie definieert echter dezelfde set functies die hetzelfde zouden moeten presteren (in prestaties, niet in snelheid) voor alle implementaties.

Met abstracte gegevenstypen kunt u modulariteit van softwareproducten bereiken en verschillende alternatieve verwisselbare implementaties van een afzonderlijke module hebben.

Voorbeelden van ADT

zie ook

Links

• Lapshin V.A.Abstracte datatypes in programmeren

Wikimedia Stichting. 2010.

Kijk wat "Abstract gegevenstype" is in andere woordenboeken:

abstract gegevenstype- Een gegevenstype (abstracte klasse) gedefinieerd door de methoden en eigenschappen ervan op te sommen, zonder hun concrete implementatie te creëren. Informatietechnologie onderwerpen in het algemeen EN Samenvatting Data TypeADT ... Handleiding voor technische vertalers

In de programmeertheorie, elk type waarvan de waarden waarden zijn van een ander type, "verpakt" door constructors van een algebraïsch type. Met andere woorden, een algebraïsch gegevenstype heeft een reeks typeconstructors, die elk ... ... Wikipedia

Integer, integer datatype (eng. Integer), in de informatica, een van de eenvoudigste en meest voorkomende datatypes in programmeertalen. Dient om gehele getallen weer te geven. Veel getallen van dit type vertegenwoordigen ... ... Wikipedia

Deze term heeft andere betekenissen, zie set (betekenissen). Een set, een type- en datastructuur in de informatica, is een implementatie van een wiskundige objectenset. Met de gegevenstypeset kunt u een beperkt aantal waarden opslaan ... ... Wikipedia

Sommige programmeertalen bieden een speciaal datatype voor complexe getallen. Het ingebouwde type maakt het eenvoudig om complexe waarden op te slaan en te berekenen. Inhoud 1 Rekenen over complex 2 Ondersteuning in talen ... Wikipedia

Deze term heeft andere betekenissen, zie Index. Pointerdiagram Een pointer (pointer) is een variabele waarvan het waardebereik bestaat uit geheugenadressen en een speciale waarde van het nuladres. ... ... Wikipedia

Een van de soorten algebraïsche gegevenstypen, die wordt gekenmerkt door het feit dat de constructeurs waarden kunnen retourneren die niet van hun eigen type zijn. Dit concept is geïmplementeerd in verschillende programmeertalen, met name in de ML- en Haskell-talen, en in ... ... Wikipedia

Een eigenschap is een abstract type dat in de informatica wordt gebruikt als 'een eenvoudig conceptueel model voor het structureren van objectgeoriënteerde programma's'. Eigenschappen zijn vergelijkbaar met mixins, maar kunnen definities van klassenmethoden bevatten. ... ... Wikipedia

Binaire boom, een eenvoudig voorbeeld van een vertakkende verbonden datastructuur. Datastructuur is een programma-eenheid die het mogelijk maakt om ... Wikipedia

- (toptype) in typetheorie, vaak aangeduid als alleen een top of een "vast" symbool (⊤), een universeel type, dat wil zeggen een type dat elk mogelijk object in het gewenste typesysteem bevat. Het hoogste type wordt soms ... ... Wikipedia