Abstracte en ingekapselde gegevenstypen. Het concept van objectgeoriënteerd programmeren

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 gegevenstype definieert een reeks functies die onafhankelijk zijn van de specifieke implementatie van het type om op zijn waarden te werken. Specifieke implementaties van ADT's 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 in lijn met het principe van inkapseling in objectgeoriënteerd programmeren. Sterk punt Deze techniek verbergt juist de implementatie. Aangezien alleen de interface buiten wordt gepubliceerd, zullen alle programma's die met de gegeven structuur met een abstract gegevenstype werken, zolang de gegevensstructuur deze interface ondersteunt, blijven werken. Ontwikkelaars van datastructuren proberen, zonder de externe interface en semantiek van functies te veranderen, implementaties geleidelijk te verfijnen en algoritmen te verbeteren in termen van snelheid, betrouwbaarheid en gebruikt geheugen.

Het verschil tussen abstracte gegevenstypen en gegevensstructuren die abstracte typen implementeren, kan worden geïllustreerd met het volgende voorbeeld. Het lijst abstracte gegevenstype kan worden geïmplementeerd met een array of een lineaire lijst, met behulp van verschillende methoden voor dynamische geheugentoewijzing. Elke implementatie definieert echter dezelfde set functies, die voor alle implementaties op dezelfde manier zouden moeten werken (in resultaat, niet in snelheid).

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

ADT-voorbeelden

zie ook

Links

• Lapshin V. A. Abstracte gegevenstypen 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 op te sommen zonder er een concrete implementatie van te maken. Onderwerpen informatietechnologie in het algemeen EN Samenvatting GegevenstypeADT ... Technisch vertalershandboek

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

Integer, integer datatype (English Integer), in de informatica, een van de eenvoudigste en meest voorkomende datatypes in programmeertalen. Wordt gebruikt om gehele getallen weer te geven. De reeks getallen van dit type is ... ... Wikipedia

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

Sommige programmeertalen bieden een speciaal datatype voor complexe getallen. De aanwezigheid van een ingebouwd type vereenvoudigt de opslag van complexe waarden en berekeningen daarop. Inhoud 1 Rekenen over complex 2 Ondersteuning in talen ... Wikipedia

Deze term heeft andere betekenissen, zie Index. Pointer-diagram Pointer (pointer, Engelse aanwijzer) is een variabele waarvan het waardenbereik bestaat uit adressen van geheugencellen 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 ML en Haskell, 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 als mixins, maar kunnen definities van klassenmethoden bevatten. ... ... Wikipedia

Een binaire boom is een eenvoudig voorbeeld van een vertakkende verbonden datastructuur. Datastructuur (Engelse datastructuur) een software-eenheid die opslag mogelijk maakt ... Wikipedia

- (toptype) in typetheorie, vaak eenvoudigweg aangeduid als 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 aangeduid als ... ... Wikipedia

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

Abstract 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

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

Exploitanten van ATD "Lijst":

1. INSERT( x, R,L). Deze operator voegt een object in x in positie R op de lijst L bewegende elementen van positie p en verder naar de volgende hogere positie. Dus als de lijst L bestaat uit elementen een1 , een2 , ..., eenN a1, a2, ..., ar-1, x, ar, ..., eenN.. Als p de waarde krijgt nul, dan hebben we een1 , een2 , ..., eenN , , X. 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 een object x op de lijst L. Als het object in de lijst staat x meer dan eens voorkomt, wordt de positie van het eerste object vanaf het begin van de lijst geretourneerd X. Als het object x niet op de lijst L, keert dan terug nul.

3. UITTREDEN(P , L ). Deze functie retourneert het element op positie R op 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- I , ap+ I, ..., een N. Het resultaat is niet gedefinieerd als het in de lijst staat L geen positie R of R = nul.

5. DE VOLGENDE( P, L ) en VORIGE(p, L ). Deze functies retourneren respectievelijk de volgende en vorige posities van de positie R op de lijst L. Als R - laatste positie in de lijst L dan VOLGENDE (P, L) = nul. De NEXT-functie is niet gedefinieerd wanneer: p=nul. De PREVIOUS-functie is niet gedefinieerd als p = 1. Beide functies zijn niet gedefinieerd als ze in de lijst staan 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 ). Drukt de elementen van een lijst af L in de volgorde waarin ze in de lijst voorkomen.

Een lijst weergeven met behulp van een array:

Lijstweergave met enkelvoudig gelinkte lijst:

Benamingen:

- aanwijzer naar het begin van de lijst,

· laatst - aanwijzer naar laatste element op de lijst ,

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

Een lijst weergeven met een dubbel gekoppelde lijst:

Opdrachten:

1. Schrijf programma's om elementen van een gesorteerde lijst in te voegen, te verwijderen en te vinden, en gebruik om de lijst te implementeren

§ reeks,

wijzers.

2. Schrijf een samenvoegprogramma

§ twee gesorteerde gekoppelde lijsten,

§ n gesorteerde gekoppelde lijsten,

3. Gegeven een polynoom van de vorm

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

Zo'n polynoom kan worden weergegeven als gekoppelde lijst, waarbij elk element drie velden heeft: één voor de coëfficiënt MetI de tweede is voor de exponent eI 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 een LIST ATD voor elk gegevenstype en de bijbehorende instructies INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST:

§ de lijst is gespecificeerd in reeks,

§ de lijst wordt gegeven als een enkelvoudig gelinkte lijst,

§ de lijst wordt weergegeven als een dubbel gelinkte lijst.

Werkprogramma paragraaf 2.1.2

Abstract gegevenstype "Stack".

Stapel - is een speciaal type lijst waar alle invoegingen en verwijderingen aan slechts één kant worden gedaan, genaamd bijeenkomst , (bovenkant). De stapeltoegangsmethode wordt gebruikt LIFO(last-in-first-out - laatste in - eerst uit).

ATD "Stack"-operators:

1. MAKENULL(S). Maakt stapel S leeg.

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

3. KNAL(S). Verwijdert een element van de bovenkant van de stapel (knalt het van de stapel), in termen van lijstoperatoren kan deze operator worden geschreven als DELETE(FIRST(S), S).

4. DUW(x, S ). Voegt een element in x naar de bovenkant van de stapel S (duwt het element op de stapel). Het element dat voorheen bovenaan de stapel stond, wordt het element dat bovenaan de stapel komt, enz. In termen van algemene lijstoperatoren gegeven operator kan worden geschreven als INSERT(;c, FIRST(S), S).

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

reeks:

Stapel representatie met enkelvoudig gelinkte lijst:

Opdrachten:

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

§ de stapel wordt gegeven als een array,

§ De stapel wordt gegeven als een enkelvoudig gekoppelde lijst.

Werkprogramma paragraaf 2.1.2

Abstract gegevenstype "Wachtrij".

Wachtrij (wachtrij) is een speciaal type lijst waar elementen vanaf het ene uiteinde worden ingevoegd, genaamd achterkant (achter), maar zijn verwijderd van de andere, voorkant (voorkant). Wachtrijen worden ook wel "FIFO-lijsten" genoemd (FIFO staat voor first-in-first-out). Wachtrij-operators zijn vergelijkbaar met stapel-operators. Het essentiële verschil tussen beide is dat het invoegen van nieuwe elementen wordt uitgevoerd in einde van lijst , en niet naar het begin, zoals bij stapels.

ATD "Wachtrij"-operators:

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 x tot het einde van wachtrij Q.

Met behulp van lijstoperatoren kan dit statement als volgt worden uitgevoerd: INSERT(x, END(Q), Q ).

4. DEQUEUE(Q) verwijdert het eerste element van wachtrij Q . Implementeer ook met lijstoperatoren zoals DELETE(FIRST(Q), Q).

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

cyclisch reeks:

Benamingen:

Q- wachtrij,

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

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

Een wachtrij vertegenwoordigen met enkelvoudig gelinkte lijst:

Opdrachten:

Implementeer een QUEUE ATD voor elk gegevenstype en de operators MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY.

§ de wachtrij is gespecificeerd als een cyclische array,

§ De wachtrij wordt weergegeven als een dubbel gelinkte lijst.

Abstract gegevenstype "Boom".

Boom 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 lijstitems, elk type item zijn. Formeel kan een boom als volgt recursief worden gedefinieerd.

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

2. Laten we P - dit is een knoop, een t1 , Т2, ...,Tk- bomen met wortels N1 . N2 , ..., nk respectievelijk. Je kunt een nieuwe boom bouwen door te doen P knooppunt ouder N1 . N2 , ..., nk. In deze boom P zal de wortel zijn, a t1 , Т2, ...,Tk - subbomen deze wortel. knopen N1 . N2 , ..., nk genaamd zonen knooppunt P.

Deze definitie omvat vaak het concept nulboom , d.w.z. "bomen" zonder knopen, zo'n boom wordt aangeduid met het woord nul .

Voorbeeld: Over de kop 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, zodat de ouders boven de "kinderen" staan.

DIV_ADBLOCK135">

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

De kinderen 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 P in een boom T. Als P is een wortel die geen ouder heeft, dan keert in dit geval terug nul. Hier nul geeft aan dat er een boomuitgang heeft plaatsgevonden.

2. LINKS__ KIND(N , T). Deze functie: geeft het meest linkse kind van een knoop terug N in een boom T. Als N is een blad (en heeft dus geen zoon), keert dan terug nul.

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

4. LABEL(N , t ). Retourneert het label van het knooppunt N. boom 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 voor elke i = 0, 1, 2,... een nieuwe wortel maken R gelabeld 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, Als t- lege boom keert dan terug nul.

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

Een boom weergeven met behulp van een reeks ouders:

Een boom weergeven met behulp van gekoppelde lijsten:

Voorstelling van een boom door, linker zonen en rechter broers.

Symbolen in de afbeelding:

nodespace – boomknooppuntarray,

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

cellenruimte – een reeks lijsten van knopenzonen,

knooppunt – aanwijzer naar knoop in 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 reeks knooppuntrecords die de index van de meest linkse zoon, de index van de rechterbroer en het label bevatten,

§ een verbonden binaire boom wordt gedefinieerd met verwijzingen naar de linker- en rechterzonen.

4. Schrijf binaire boomtraversale functies in voorwaartse, achterwaartse en symmetrische volgorde.

Werkprogramma paragraaf 2.1.3

Abstract gegevenstype "Set".

Een stelletje meestal afgebeeld als een opeenvolging van de elementen ingesloten in een beugel, bijvoorbeeld (1, 4) geeft een verzameling aan die bestaat uit twee elementen, de nummers 1 en 4. De volgorde waarin de elementen van de verzameling zijn geschreven is niet belangrijk, dus je kunt (4, 1) op dezelfde manier schrijven as (1, 4) , bij het schrijven van dezelfde set. Een set is geen lijst (althans op basis van een willekeurige volgorde waarin elementen zijn geschreven). De set heeft geen herhalende elementen ((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 x x hoort niet bij de set EEN", d.w.z. x is geen element van de set EEN. Er is een speciale set, aangeduid met het symbool , genaamd leeg, veel , en die geen elementen heeft. Stel DIV_ADBLOCK138"> . in

Ze zeggen dat velen EEN bevatte in veelvoud V(of gaat aan in de menigte V), spelt 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 velen EEN is 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 A B, dan heet de verzameling A eigen, waar of strikte subset sets V.

De belangrijkste bewerkingen die op sets worden uitgevoerd, zijn unie, intersectie en verschil. Vereniging sets EEN en V(aangeduid met EEN V) is een verzameling 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 wordt een verzameling genoemd die alleen bestaat uit die elementen die tot de verzameling behoren. EEN, en veel V. verschil sets EEN en V(aangeduid met EEN\ B) is een verzameling die alleen uit die elementen van de verzameling bestaat EEN, die niet tot de set behoren V.

Als bijvoorbeeld A \u003d (a, b, c) en B \u003d (b, a), dan AB \u003d (a, b, c, d), AB \u003d (b) en A \ B \u003d (a,c).

ADT "Set"-operators:

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

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

3. VERSCHIL(EEN, B, C) heeft "invoer" ingestelde argumenten 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 operand sets niet kruisen (d.w.z. niet hebben) 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 veel argumenten EEN en maak bezwaar x hetzelfde type als de elementen van de set EEN en retourneert een booleaanse waarde waar(waar) als x a", "b", "c"))= "een". De operator wordt op een vergelijkbare manier gedefinieerd MAX.

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

12. VINDEN(x ) werkt in een omgeving waar sprake is van een verzameling onsamenhangende verzamelingen. Het geeft de naam terug van de (enkele) set die het element bevat X.

Stel weergave in:

Een 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),

INVOEREN(1,A),

VERWIJDEREN (1, A),

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

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

de set wordt gedefinieerd met behulp van een ongesorteerde gekoppelde lijst,

de set wordt gedefinieerd met behulp van een gesorteerde gekoppelde lijst,

Werkprogramma paragraaf 2.1.3

Speciale soorten sets

Abstract gegevenstype "Binaire zoekboom"

Binaire zoekboom - een gegevensstructuur voor het representeren van verzamelingen waarvan de elementen zijn geordend volgens een lineaire orderelatie. Set-operators kunnen worden geïmplementeerd op binaire zoekbomen INSERT, VERWIJDEREN, LID en MIN, en hun uitvoeringstijd is gemiddeld in de orde van O (log n) voor sets bestaande uit P elementen.

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

Binaire boom voorbeelden:

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

De weergave van een AVL-boom verschilt niet van de weergave van een binaire zoekboom.

Een ander type uitgebalanceerde zoekboom is: 2-3 boom. De structuur van een 2-3-boom is anders dan de structuur van een binaire zoekboom. Voor een 2-3-boom is het typisch dat alle knooppunten 2 of 3 kinderen hebben, alle paden van de wortel naar het blad hebben dezelfde lengte , 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 om boomzoekopdrachten te routeren. Elk intern knooppunt bevat de minste elementsleutels van de tweede en derde zoon (als er een derde zoon is) en verwijzingen naar de zoonknooppunten.

Gelinkte binaire zoekboomweergave:

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 is van het invoegen van de elementen 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 in de lege verzameling (weergegeven als een 2-3-boom).

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

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

de boom wordt gegeven als een verbonden binaire boom

de boom wordt gegeven in de vorm van 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 te weten of een bepaald element in een bepaalde set aanwezig is. Het woordenboek is geïmplementeerd met behulp van de ADT "Woordenboek" met operators INVOEREN,VERWIJDEREN en LID. De set woordenboekoperatoren 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: de 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 x originele ingestelde functie: H(x) neemt een geheel getal uit het interval 0, ..., V- 1, wat overeenkomt met de klasse waartoe het element behoort X. Element x bel vaak sleutel, H( x) - hasj-x waarde en "lessen" segmenten . Hoe hash-botsingen op te lossen (twee elementen van een set hebben dezelfde waarde) H(x)) publieke en private hashing wordt toegepast.

open hashtafel

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

Een woordenboek vertegenwoordigen met gesloten hashtabel

De segmenttabel slaat de woordenboekelementen rechtstreeks op. Daarom kan in elk segment slechts één woordenboekelement worden opgeslagen. Bij private hashing wordt de techniek gebruikt herkauwen . Bij het plaatsen van een element x naar segmentnummer H ( x ) , die al bezet is door een ander element, wordt de 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 bevat een element x . Er worden verschillende methoden voor het oplossen van botsingen gebruikt om segmentnummers op te geven voor herhashing. Bijvoorbeeld lineaire hash-methode, mid-square-methode, willekeurige hash-methode

Opdrachten:

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

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

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

2. Stel dat we een gesloten hashtabel hebben met 5 shards, een hashfunctie h(i) = i % 5, en een lineaire techniek voor het oplossen van botsingen. Toon het resultaat van de invoeging in de aanvankelijk lege hashtabel van de reeks getallen 23, 48, 35, 4, 10.

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

het woordenboek is ingesteld met behulp van een open hash-tabel,

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

Werkprogramma paragraaf 2.1.3

Het abstracte gegevenstype Mapping.

Weergave - is een verzameling, op de elementen waarvan de functie van het weergeven van elementen van hetzelfde type is gedefinieerd ( domeinen ) naar elementen van een ander type ( bereiken ) van een ander type. Weergave m komt overeen met een element D domeintype uit elementbereik R bereiktype uit bereik: m(D) = R.Leeg display bevat geen elementen

Exploitanten van ATD "Display":

1. MAKENULL(m ). Maakt het display m leeg.

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

3. BEREKENEN( M, d, r). Retourneert true en stelt de variabele r in op de waarde m(D), als de laatste is gedefinieerd, en geeft anders false terug.

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

Werkprogramma paragraaf 2.1.3

Abstract gegevenstype "Prioriteitswachtrij"

prioriteits-rij - dit is een set voor de elementen waarvan de prioriteitsfunctie (prioriteit) is ingesteld, d.w.z. voor elk element x ingesteld, kunt u de functie berekenen: R( x )- element prioriteit x , die meestal waarden haalt uit de reeks reële getallen, of, in meer algemeen geval, van een lineair geordende set.

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

Een wachtrij vertegenwoordigen met geordende dubbel gelinkte lijst.

Het belangrijkste idee van deze implementatie is om de elementen van de wachtrij te organiseren in de vorm van een binaire boom. Op een lager niveau, waar enkele bladeren kunnen ontbreken, kunnen alle ontbrekende bladeren alleen rechts van de aanwezige bladeren op een lager niveau worden gevonden. Wat nog belangrijker is, de boom gedeeltelijk besteld . Dit betekent dat de prioriteit van het knooppunt v niet groter dan de prioriteit van een kind van een knoop v, waarbij knooppuntprioriteit de prioriteitswaarde is van het element dat is opgeslagen in het gegeven knooppunt. Uit de figuur blijkt dat kleine prioriteitswaarden niet op een hoger niveau kunnen verschijnen waar er grote prioriteitswaarden zijn.

De functie DELETEMIN retourneert het element 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, de volgende acties:: Het laagste niveau bevat het meest rechtse knooppunt en wordt tijdelijk aan de wortel van de boom geplaatst. Dit element daalt vervolgens langs de takken van de boom (naar lagere niveaus) en wisselt onderweg van plaats met zonen met een lagere prioriteit, totdat dit element ofwel een blad is of in een positie waar zijn zonen op zijn minst niet minder prioriteit hebben.

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

In array EEN eerst N posities komen overeen N boom knooppunten. Element EEN bevat de wortel van de boom. Linker kind van boomknooppunt EEN[ I], als het bestaat, bevindt het zich in de cel EEN, en de juiste zoon, als die bestaat, is in de cel EEN. Omgekeerd, als de zoon in de cel zit EEN[ I], dan zijn ouder in de cel EEN[ I%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 een array weergegeven door de volgende volgorde van zijn knooppunten: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Opdrachten:

1. Teken de gedeeltelijk geordende boom die het resultaat is van het invoegen van de gehele getallen 5, 6, 4, 9, 3, 1 en 7. Wat is het resultaat? consistente toepassing naar deze boom van drie DELETEMIN-instructies?

2. Implementeer een 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

Abstract gegevenstype "Union van sets".

Een ADT is een verzameling objecten, die elk een verzameling zijn. De belangrijkste bewerkingen die op een dergelijke verzameling worden uitgevoerd, zijn het combineren van de sets tot bepaalde volgorde, evenals bij het controleren of een bepaald object tot een specifieke set behoort. Deze taken worden opgelost met behulp van operators SAMENVOEGEN(Samenvoegen) en VINDEN(Vinden). SAMENVOEGEN( EEN, V, C) maakt een set MET gelijk aan de vereniging van verzamelingen EEN en V, als deze sets elkaar niet snijden (d.w.z. geen gemeenschappelijke elementen hebben); deze operator is niet gedefinieerd als de sets EEN en V snijden. VINDEN( x) geeft de set terug waartoe het element behoort X; voor het geval wanneer? x tot meerdere sets behoort of niet tot een ervan behoort, is de waarde van deze functie niet gedefinieerd.

Operators van de ADT “Combining Sets”:

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

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

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

De vereniging van sets weergeven met behulp van arrays:

De setnaam is hetzelfde als de matrixindexwaarde kopteksten instellen ( naam 0 )

Benamingen:

kopteksten instellen – array van set headers:

§ Met tante is het aantal elementen in de set,

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

namen – array van lijsten van set-elementen:

setnaam - de naam van de verzameling waartoe het element behoort, volgend element is de index van het volgende element in de lijst van de gegeven set (de 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 vele toppen V en veel bogen e. Vertices worden ook wel knopen , en de bogen georiënteerde randen . De boog kan worden weergegeven als een geordend paar hoekpunten ( jij, met wie), waar is de top en genaamd begin , een met wie - einde bogen.

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

Voorbeeld 1 digraaf:

De hoekpunten van een digraph kunnen worden gebruikt om objecten weer te geven, en de bogen kunnen worden gebruikt om relaties tussen objecten weer te geven.

manier in een digraaf heet 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 deze zaak padlengte is P - 1 . Beschouw als een speciaal geval van een pad één hoekpunt v als een pad met lengte 0 vanaf de top vNaar 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 gemakkelijk , als alle hoekpunten erop, behalve misschien de eerste en de laatste, verschillend zijn. Fiets - 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: gelabelde digraph , d.w.z. een digraph waarvoor elke boog en/of elk hoekpunt een overeenkomstig label heeft. Een label kan een naam, gewicht of kosten (van bogen) zijn, of een gegevenswaarde van een bepaald type.

Voorbeeld 2 gelabelde digraph:

DIV_ADBLOCK149">

3. Transitief sluitingsalgoritme (Warshall-algoritme):

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

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

Laat en - willekeurig hoekpunt van de digraph G = (V,E). Excentriciteit (maximale verwijdering) pieken en gedefinieerd als

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

met wie V

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

Voorbeeld: Het middelpunt van de digraph is het hoekpunt D

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

Bij het oplossen van veel problemen met gerichte grafieken is een efficiënte methode nodig om de hoekpunten en bogen van digraphs systematisch te doorlopen. Deze methode is de zogenaamde diepte-eerst zoeken - een veralgemening van de directe tree traversal-methode. Depth-First Search begint met de keuze van het initiële hoekpunt v Graaf G, dit hoekpunt is gelabeld bezocht (bezocht). Dan voor elk hoekpunt naast het hoekpunt v en die nog niet eerder is bezocht, wordt recursief een diepte-eerst zoekopdracht toegepast. Wanneer alle hoekpunten die vanaf het hoekpunt kunnen worden bereikt v, met een bezoek "beloond" wordt, stopt de zoektocht. Als sommige hoekpunten niet worden bezocht, wordt er een geselecteerd en wordt de zoekopdracht herhaald. Dit proces gaat door totdat alle hoekpunten van de digraph door de traversal zijn bedekt. G.

6. Het algoritme voor het construeren van een diepe opspannende boom van een graaf:

Bij het doorlopen van een grafiek met behulp van de diepte-eerst-zoekmethode, leiden alleen bepaalde bogen naar niet-bezochte hoekpunten. Dergelijke bogen die naar nieuwe hoekpunten leiden, worden boombogen genoemd en vormen de grafiek diepte-eerst zoeken in bos – diepe kern bos . Bij het aanleggen van een bos worden nog 3 soorten bogen onderscheiden: omgekeerd, recht en dwars. Omgekeerde bogen - zulke bogen die in het overspannende woud van afstammelingen naar voorouders gaan. Rechte bogen 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 gerangschikt 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 D->C en G->D- dwars, boog C-> EEN- achteruit, 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 diep genoemd.

Digraph vertegenwoordiging:

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

Aangrenzende matrix voor digraph G- dit is een matrix EEN maat N N met booleaanse waarden, waarbij EEN[ I, J] = waar als en slechts als er een boog is vanaf het hoekpunt I naar boven 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[ I, J] gelijk aan booglabel ik ->J. Als de bogen vanaf de bovenkant I naar de top J niet bestaat, dan is de waarde van A[ I, J] kan niet de waarde zijn van een geldig label, maar kan worden behandeld als een "lege" cel.

Aangrenzende matrix voor gelabelde digraph (voorbeeld 2):

§ Weergave van een digraph met behulp van aangrenzende lijsten:

Aangrenzende lijst voor een hoekpunt I heet de lijst van alle hoekpunten naast het hoekpunt I, en op een bepaalde manier besteld. digraaf G kan worden weergegeven met een array HOOFD(Header) wiens element HOOFD[I] is een verwijzing naar de lijst met aangrenzende punten I.

Exploitanten van ATD “Orgraf”:

De meest voorkomende operators die op gerichte grafieken worden uitgevoerd, zijn onder meer het lezen van hoekpunten en booglabels, het invoegen en verwijderen van hoekpunten en bogen en het doorlopen van boogreeksen.

De volgende drie operatoren zijn vereist om de reeks aangrenzende hoekpunten te bekijken.

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

2. VOLGENDE( v, I) geeft de index terug van het hoekpunt naast het hoekpunt v, volgende index I. Als I- is de index van het laatste hoekpunt naast het hoekpunt v, keert dan terug nul.

3.VERTEX( v,I) geeft het hoekpunt terug bij index I 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 Een (eenvoudig) pad is een (eenvoudig) pad met een lengte van ten minste 3 van een hoekpunt naar zichzelf. De graaf 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 af zijn gericht.

Vrije bomen hebben twee belangrijke eigenschappen:

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

2. Als er een nieuwe rand wordt toegevoegd aan een vrije boom, wordt een cyclus verkregen.

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

Basisalgoritmen voor het verwerken van ongerichte grafieken:

1. Een opspannende boom bouwen minimale kosten(Prim's algoritme):

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

De volgorde van het bouwen van een opspannende boom wordt hieronder gegeven.

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

3. Doorloop van ongerichte grafieken door eerst op diepte te zoeken:

Diepte-eerst zoeken wordt gebruikt om systematisch alle hoekpunten van een 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 een ongerichte rand (v, met wie) kan worden weergegeven als een paar georiënteerde bogen v -> met wie en met wie -> v.

Depth-first traversal kan worden gebruikt om een ​​opspannende boom te bouwen.

De grafiek en de opspannende boom die zijn verkregen door de hoekpunten ervan te doorlopen met behulp van de diepte-eerst-zoekmethode, worden hieronder weergegeven:

4. Doorkruisen van ongerichte grafieken door eerst te zoeken in de breedte

Een andere methode om systematisch de hoekpunten van een graaf te doorkruisen heet breedte-eerst zoeken . Het kreeg zijn naam vanwege het feit dat bij het bereiken tijdens de bypass van een hoekpunt v dan worden alle hoekpunten naast het hoekpunt beschouwd v, d.w.z. de hoekpunten worden "in de breedte" gescand. Deze methode kan ook worden toegepast op gerichte grafieken.

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

De opspannende boom verkregen door breedte-eerst zoeken wordt hieronder getoond.

Een ongerichte grafiek weergeven met behulp van een aangrenzende matrix:

Om ongerichte grafieken weer te geven, kunnen dezelfde methoden worden gebruikt als voor de weergave van gerichte grafieken, als de ongerichte rand tussen de hoekpunten v en met wie worden beschouwd als twee georiënteerde bogen vanaf het hoekpunt v naar bovenkant met wie en van boven met wie naar de top v.

https://pandia.ru/text/78/308/images/image051_12.gif" width="159" height="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 door het algoritme van Prim;

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

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

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

2. Implementeer de Prim- en Kruskal-algoritmen.

3. Implementeer de constructie van een spanningsboom met behulp van diepte-eerst zoeken

§ voor een ongerichte graaf vertegenwoordigd door een aangrenzende matrix,

§ voor een ongerichte grafiek vertegenwoordigd door aangrenzende lijsten.

4. Implementeer Breedte First Search Spanning Tree

§ voor een ongerichte graaf vertegenwoordigd door een aangrenzende matrix,

§ voor een ongerichte grafiek vertegenwoordigd door aangrenzende lijsten.

Met de C++-taal kunt u gegevenstypen maken die zich op dezelfde manier gedragen als de standaard C-taaltypen. Deze typen worden meestal abstracte gegevenstypen(BIJ D).
Structuren worden gebruikt om ADT in C-taal te implementeren. Maar het gebruik van gegevens structureel type: aanzienlijk beperkt in vergelijking met het gebruik basistypes gegevens. Structuurgegevens kunnen bijvoorbeeld niet worden gebruikt als operanden in verschillende operaties(optellen, aftrekken). Om dergelijke gegevens te manipuleren, moet u een reeks functies schrijven die verschillende acties uitvoeren, en deze functies aanroepen in plaats van bewerkingen.

Bovendien zijn de elementen van de constructie op geen enkele manier beschermd tegen onbedoelde wijziging. Dat wil zeggen, elke functie (zelfs niet uit de set tools voor het manipuleren van structurele gegevens) kan verwijzen naar een structuurelement. Dit druist in tegen een van de basisprincipes van objectgeoriënteerd programmeren, gegevensinkapseling: geen andere functies dan speciale functies voor het manipuleren van dit gegevenstype mogen toegang hebben tot gegevensleden.

Overweeg de implementatie van het concept van een datum met behulp van een struct om een ​​weergave van de datumdatum te definiëren en een reeks functies voor het werken met variabelen van dit type:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#erbij betrekken
struct datum
{
int maand; // maand
int dag; // dag
int jaar; // jaar
};
void set_date(datum* f, int d, int m, int y)
{
f->dag = d;
f->maand = m;
f->jaar = y;
}
ongeldig print_date(date*f)
{
printf("%d.%d.%d" , f->dag, f->maand, f->jaar);
}
int hoofd()
{
datum vandaag;
set_date(&vandaag, 2, 4, 2014);
print_date(&vandaag);
getchar();
retourneer 0;
}

In dit voorbeeld is er geen expliciete relatie tussen functies en gegevenstype. Om een ​​van de beschreven functies aan te roepen, moet u een aanwijzer naar een instantie van de structuur als argument doorgeven.

Een dergelijke relatie kan worden vastgesteld door functies te beschrijven als leden van een structuur. Deze functies kunnen inwerken op de gegevens in de structuur zelf.
Wanneer een structuur wordt gedeclareerd, worden de gegevens en functies standaard gedeeld, wat betekent dat objecten van het type structuur geen inkapseling of gegevensbescherming hebben:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#erbij betrekken
struct datum
{
int maand; // maand
int dag; // dag
int jaar; // jaar
void set_date (int d, int m, int y)
{
dag=d; maand=m; jaar=j;
}
void print_date (ongeldig);
};
ongeldige datum::print_date(ongeldig)
{
printf("%d.%d.%d" , dag, maand, jaar);
}
int hoofd()
{
datum vandaag;
vandaag.set_date (2, 4, 2014);
vandaag.print_date();
getchar();
retourneer 0;
}

Ledenfuncties en gegevensleden

Functies beschreven in het lichaam abstract type data, zijn lidfuncties of -methoden en kunnen alleen worden aangeroepen op een speciale variabele van het juiste type, met behulp van de standaardsyntaxis voor toegang tot lidgegevens of structuurvelden.

Functies van leden kunnen op twee manieren worden gedefinieerd:

• beschrijving van de functie direct in de beschrijving van de structuur;
• beschrijving van de functie buiten de structuur.

Lidfuncties die binnen een struct gedefinieerd zijn, zijn impliciet inline ( ). Als algemene regel geldt dat alleen korte, veelgebruikte lidfuncties moeten worden gedefinieerd binnen een struct:

void set(int m, int d, int y) (maand = m; dag = d; jaar = y;);

• een type is het retourtype van de lidfunctie
• BIJ D— naam van het abstracte gegevenstype (struct- of klassenaam)
• naam- naam lidfunctie

ongeldige datum::print_date(ongeldig)
( printf("%d.%d.%d", dag, maand, jaar);)

In een lidfunctie kunnen lidnamen worden gebruikt zonder een expliciete objectverwijzing. In dit geval verwijst de naam naar het lid van het object waarop de functie is aangeroepen.

Lidfuncties van dezelfde structuur kunnen polymorf zijn, dat wil zeggen overbelast.

Toegangsrechten

Het concept van een struct in C++ (in tegenstelling tot C) staat leden van een struct toe om openbaar, privé of beschermd te zijn:

• publiek - algemeen;
• privé - privé;
• beschermd - beschermd.

Het gebruik van het beschermde trefwoord is gerelateerd aan het concept van overerving.

Het gebruik van het privé-sleutelwoord beperkt de toegang tot leden die deze constructie volgen. Privéleden kunnen alleen worden gebruikt door een paar categorieën functies die toegangsrechten hebben voor die leden. Het zijn in feite lidfuncties van dezelfde structuur.
Het publieke trefwoord vormt een interface naar een structuurobject.

Het is standaard om lidgegevens in een privégebied (privé) te plaatsen en delen van lidfuncties - in het openbare deel (openbaar) van een abstract gegevenstype. In dit geval definieert het private (private) deel de gegevens- en hulpprogrammafuncties van het object, en implementeren de lidfuncties van het publieke deel methoden om met het object te werken.

Laten we de datumstructuur wijzigen om de gegevensrepresentatie te verbergen (gegevensinkapseling):

1
2
3
4
5
6
7
8

struct datum
{
privaat :
int maand, dag, jaar;
openbaar :
void set (int , int , int );
voidprint();
};

Ministerie van Onderwijs en Wetenschappen Russische Federatie

Federale staatsbegrotingsinstelling voor onderwijs

hoger beroepsonderwijs

NATIONALE NUCLEAIRE ONDERZOEKSUNIVERSITEIT MEPHI

Dimitrovgrad Engineering and Technology Institute

afdeling Informatie Technologie

Zorg voor bescherming "" 2012

Hoofd afdeling Rakova O.A.

cursus werk

door discipline"Object georiënteerd programmeren"

Onderwerp:“Abstracte gegevenstypen. Lijsten»

Voltooid: student gr. VT-31

Shayakov A.F.

Leider: Art. Leraar IT-afdeling

Alenin V.A.

Beheerder: Art. Leraar IT-afdeling

Alenin V.A.

Cijfer:

Beschermingsdatum:

Dimitrovgrad, 2012

Ministerie van Onderwijs en Wetenschappen van de Russische Federatie

Federale staatsbegrotingsinstelling voor onderwijs

hoger beroepsonderwijs

NATIONALE NUCLEAIRE ONDERZOEKSUNIVERSITEIT MEPHI

Dimitrovgrad Engineering and Technology Institute

voor scriptie

Discipline: Objectgeoriënteerd programmeren

Onderwerp: Abstracte gegevenstypen. Lijsten

Kunstenaar: Shayakov A.F.

Hoofd: Alenin V.A.

1. Theoretisch gedeelte:

Abstracte gegevenstypen. Het concept van objectgeoriënteerd programmeren. Lineaire enkelvoudig gekoppelde lijsten.

2.Praktisch deel:

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

Deadlines voor de uitvoering van werkzaamheden volgens planning:

Theoretisch gedeelte - 15% per 5 weken

Praktijkgedeelte - 80% tegen week 7

Experimentele sectie - ____% tegen ____ week

Bescherming - 100% na 10 weken

Ontwerp voorwaarden:

De afrekening en toelichting van het cursuswerk moeten in elektronische vorm en op papier worden ingediend;

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

RPP wordt ondertekend door de persoon die verantwoordelijk is voor normatieve controle

Hoofd werk _________________

Uitvoerder ______________________________

Datum van uitgifte "_____" ___________ 2012

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

Trefwoorden: lineaire enkelvoudig gelinkte lijsten, C++, objectgeoriënteerd programmeren.

Het onderzoeksobject zijn lineaire enkelvoudig gekoppelde lijsten.

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

Conclusies: in dit werk werden lineaire enkelvoudig gekoppelde lijsten, evenals methoden voor hun representatie in het geheugen, volledig bestudeerd. Een programma geschreven in de C++-taal voldoet volledig aan de objectgeoriënteerde structuur, voert correct en efficiënt zijn hoofdtaak uit - het implementeert lineaire enkelvoudig gelinkte 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

Tijdens het werken met gegevens is het vaak 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 dynamisch geheugen en de grootte verandert tijdens de uitvoering van het programma.

Van de dynamische structuren worden in dit werk lineaire lijsten gebruikt. Een dynamische structuur kan, in tegenstelling tot een array of een record, niet-aaneengesloten secties van RAM in beslag nemen.

Dynamische structuren worden veel gebruikt voor meer effectief werk met gegevens waarvan de grootte bekend is, vooral voor het oplossen van sorteerproblemen.

Een element van een dynamische structuur bestaat uit twee delen: informatie, om op te slaan welke de structuur is gemaakt, en pointers die koppelingen tussen elementen verschaffen.

1. Theoretisch gedeelte

1.1 Abstracte gegevenstypen. Lineaire lijsten

Het concept van abstracte datatypes staat centraal bij het programmeren. Abstractie impliceert scheiding en onafhankelijke overweging van interface en implementatie.

Gegevensabstractie omvat de definitie en overweging van abstracte gegevenstypen (ATD) of, equivalent, nieuwe gegevenstypen die door de gebruiker zijn geïntroduceerd.

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

Lineaire lijsten

In een lineaire lijst is elk element gerelateerd aan het volgende en mogelijk het vorige. In het eerste geval wordt de lijst enkelvoudig gekoppeld genoemd; in het tweede geval wordt deze dubbel gekoppeld genoemd. Als het laatste element door een pointer aan het eerste wordt gekoppeld, wordt een circulaire lijst verkregen.

Elk element van de lijst bevat een sleutel die dat element 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. Sleutels verschillende elementen lijsten kunnen overeenkomen.

U kunt de volgende bewerkingen op lijsten uitvoeren:

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

een element 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;

het sorteren van de lijst op sleutel.

Om met een lijst in het programma te werken, moet u een aanwijzer naar het begin definiëren. Om het toevoegen van nieuwe elementen aan het einde van de lijst gemakkelijker te maken, kunt u ook een aanwijzer naar het einde van de lijst plaatsen.

1.2 Concept van objectgeoriënteerd programmeren

Volgens de definitie van autoriteit op het gebied van objectgeoriënteerde methoden voor programma-ontwikkeling, Grady Booch, "is objectgeoriënteerd programmeren (OOP) een programmeermethodologie die is gebaseerd op het weergeven van een programma als een verzameling objecten, die elk een implementatie van een bepaalde klasse (speciaal soort type), en klassen vormen een hiërarchie op basis van de principes van erfelijkheid.

De objectgeoriënteerde methodologie, zoals de structurele methodologie, is gemaakt om het proces van het ontwikkelen van grote softwaresystemen te disciplineren en daardoor hun complexiteit en kosten te verminderen.

Objectgeoriënteerde methodologie streeft dezelfde doelen na als structurele methodologie, maar lost ze op vanuit een ander startpunt en stelt u in de meeste gevallen in staat om complexere projecten te beheren dan structurele methodologie.

Zoals u weet, is decompositie een van de principes van projectcomplexiteitsbeheer. Grady Booch onderscheidt twee soorten decompositie: algoritmisch (zoals hij decompositie ondersteund door structurele methoden noemt) en objectgeoriënteerd, waarbij het verschil naar zijn mening als volgt is: “De deling door algoritmen richt zich op de volgorde van gebeurtenissen, en de verdeling door objecten geeft bijzonder belang aan factoren die ofwel acties veroorzaken of het object 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 meer aandacht besteedt aan de aard van relaties.

In de praktijk wordt aanbevolen om beide soorten ontleding te gebruiken: bij het maken van grote projecten het is raadzaam om eerst een objectgeoriënteerde benadering toe te passen om een ​​gemeenschappelijke hiërarchie van objecten te creëren die de essentie van de programmeerbare taak weerspiegelt, en vervolgens algoritmische decompositie in modules te gebruiken 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 gezien als iets dat wordt gevoeld of ingebeeld en goed gedefinieerd gedrag vertoont. Zo kan een object ofwel worden gezien of aangeraakt, of tenminste weten dat het bestaat, het wordt bijvoorbeeld weergegeven als informatie die is opgeslagen in het geheugen van de computer. Laten we het geven objectdefinitie, vasthoudend aan de mening van Gradibooch: "Een object is een tastbare entiteit die zijn gedrag duidelijk manifesteert."

Een object maakt deel uit van de werkelijkheid om ons heen, d.w.z. 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 nogal moeilijk te definiëren. Dit kan door middel van enkele eigenschappen, namelijk: het object heeft een status, gedrag en is uniek te identificeren (met andere woorden, heeft een unieke naam).

Een klasse is een verzameling objecten met een gemeenschappelijke structuur en gemeenschappelijk gedrag. 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 "description" klasse variabelen" en "class object description" zijn hetzelfde.

Een object heeft een staat, een gedrag en een paspoort (een middel om het op unieke wijze te identificeren); de structuur en het gedrag van objecten worden beschreven in de klassen waarvan ze variabelen zijn.

Laten we nu de begrippen toestand, gedrag en objectidentificatie definiëren.

De toestand van een object combineert al zijn gegevensvelden (statische component, d.w.z. onveranderlijk) en de huidige waarden van elk van die 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 andere klassen. Identificatie wordt uitgevoerd door middel van unieke naam(paspoort), die echter, net als elke andere variabele, een object in het programma heeft.

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 bepaalde algoritmen implementeren. Aan de andere kant presenteert de objectgeoriënteerde benadering programma's als een reeks objecten die met elkaar in wisselwerking staan. Objecten communiceren via berichten. Laten we aannemen dat ons object een cirkel is. Dan kan het bericht dat naar dat object wordt gestuurd, "teken jezelf" zijn. Als we zeggen dat er een bericht naar een object wordt verzonden, roepen we eigenlijk een functie van dit object aan (een functiecomponent). 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". Het object (capsule) bevat dus methoden en eigenschappen (inhoud).

Het concept van inkapseling kan in een bredere zin worden beschouwd, ver buiten het bereik van 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 ​​bepaalde reeks andere objecten te bevatten. Dus in relatie tot computerprogramma we kunnen zeggen dat het verschillende modules inkapselt, die elk op hun beurt een aantal objecten inkapselen die methoden en eigenschappen op zich 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, wanneer we het hebben over inkapseling in objectgeoriënteerd programmeren, wordt het concept van inkapseling gelijkgesteld aan het concept van een "zwarte doos" of het verbergen van gegevens, maar dit is 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 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 beschikbaar stellen, 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 het zijn op geen enkele manier identieke concepten.

Ten eerste zijn objecten dankzij inkapseling niet langer alleen door de gebruiker gedefinieerde gegevensstructuren, waarvan het belangrijkste doel eenvoudigweg is om verschillende afzonderlijke gegevenstypen logisch te combineren binnen een nieuw samengesteld gegevenstype. Dankzij inkapseling kan elk object nu gegevens bevatten die de toestand van het object en zijn gedrag beschrijven, beschreven in de vorm van methoden. Met andere woorden, het object in objectgeoriënteerd programmeren is niet langer primitief passief type gegevens, waarvan het beheer volledig is overgeleverd aan de externe omgeving, maar begon zijn eigen gedrag te vertonen, je zou zelfs kunnen zeggen, enige wil en reden, het vermogen om actief te reageren op externe invloeden en zijn toestand naar eigen inzicht te veranderen wetten en regels.

Ten tweede geeft inkapseling ons de mogelijkheid om de toegang tot de gegevens van een object te controleren. Beperking van de zichtbaarheid kan ook worden beschouwd 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 kring van objecten en wat puur intiem wordt gemaakt , die het van geen enkel ander object zal weten. Waarom, maar omdat alleen het object zelf precies weet hoe je ermee kunt werken en hoe niet. Je kunt zelfs spreken van een nieuwe filosofie van programmeren, waarbij objecten meer lijken op objecten 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 nogmaals herhaal ik dat het dankzij inkapseling is dat een object kan worden begiftigd met enige wil, intelligentie, het vermogen om te reageren op externe invloeden in plaats van een passieve gegevensopslag te zijn.

Erfenis

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

Met andere woorden, de afgeleide klasse implementeert de specificatie van een reeds bestaande klasse (de basisklasse). Hiermee kunt u objecten van de descendant-klasse op dezelfde manier behandelen als met objecten van de basisklasse.

Overervingstypen

eenvoudige overerving

De klasse waaruit de overerving plaatsvond, wordt de basis of ouder genoemd (Engelse basisklasse). Klassen die afstammen van de basis worden afstammelingen, erfgenamen of afgeleide klassen genoemd (eng. afgeleide klasse).

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 en 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.

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

Meerdere overerving

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

Meervoudige overerving is een mogelijke bron van fouten die kunnen ontstaan ​​door dezelfde methodenamen in voorouders te hebben. In talen die worden gepositioneerd als opvolgers van C++ (Java, C#, etc.) werd besloten om meervoudige overerving af te schaffen ten gunste van interfaces. U kunt bijna altijd zonder dit mechanisme. Als een dergelijke behoefte zich desondanks 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 bepaalde ouder.

Een poging om het probleem op te lossen van het hebben van dezelfde methodenamen in voorouders werd gedaan 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 klas kind.

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

1. Praktijkgedeelte

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

De klasse cList is een lineaire enkelvoudig gekoppelde lijst die bestaat uit objecten van de klasse cElement.

De klasse cElement heeft de volgende structuur:

cElement *volgende;

~cElement(leeg);

ongeldige setdata(int);

void setref(cElement*);

cElement* getref();

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

void cElement::setdata(int sd)

int cElement::getdata()

returnthis->data;

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.

Overweeg nu de structuur van de klasse cList

#include"cElement.h"

cElement *hoofd;

voidAdd(int);

ongeldig Insert(int, int);

ongeldig Verwijderen(int);

voidRemoveAll();

Deze klasse bevat een verwijzing naar het head-element van de lijst - head, van het type cElement*. Het opslaan van deze koppeling is nodig voor het correct uitvoeren van de bewerkingen van het toevoegen, verwijderen van gegevens en het afdrukken van de lijst. Het ding is Dat, bij het uitvoeren van een van de bovenstaande bewerkingen, worden de elementen van de lijst herhaald om de gewenste te bereiken, aangezien de lijst geen willekeurige toegang tot de elementen heeft, dus het is rationeler om de opsomming te starten vanaf de "kop" 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 de overweging van deze klasse voortzetten door de methoden te bestuderen die erin zijn geïmplementeerd voor het werken met lijsten.

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

Deze methode heeft als parameter een numerieke waarde (variabele xd), die moet worden opgeslagen in het toegevoegde lijstelement.

void cLijst::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 van de lijst gecontroleerd, als de lijst leeg is, wordt het head-element gemaakt, anders de "gewone" component van de lijst:

if (elcount==0)

temp->setref(NULL);

temp->setref(NULL);

p->setref(temp);

U kunt zien dat de bovenstaande constructie de setref-methode van de cElement-klasse gebruikt, die nodig is om een ​​verwijzing naar het volgende element van de lijst in te stellen, anders is de lijst niet gerelateerd, wat gepaard gaat met gegevensverlies en onjuiste programmabewerking.

Wanneer u het programma voor het eerst start, wordt de hierboven beschreven methode gebruikt om achtereenvolgens elementen aan de lijst toe te voegen, waarmee u vervolgens kunt werken. Om de invoer op de opdrachtregel te stoppen, moet u de opdracht "stop" invoeren in plaats van de numerieke waarde van het element (zie figuur 1).

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

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

Afbeelding 2 - Afgedrukte lijst

Afdrukmethode - lijst afdrukken.

Voor het printen is het belangrijk om het begin van de lijst te kennen om de waarden van alle elementen van de lijst achter elkaar af te drukken, dus een verwijzing naar de "kop" van de lijst wordt gezet in de temp variabele, 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 op het scherm weergegeven:

void cLijst::Print()

cElement * temp = hoofd;

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

temp = temp->getref();

Del-methode - het eerste element van de lijst verwijderen.

Om het initiële element te verwijderen, moet u eerst de verwijzing naar de volgende lijstcomponent overbrengen, waardoor deze op deze manier de eerste wordt, en vervolgens het vereiste element verwijderen:

voidcList::Del()

cElement * temp = hoofd;

hoofd = hoofd->getref();

De 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::RemoveAll()

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 - Een opdracht 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

De methode Verwijderen - verwijdert een specifiek element van de lijst.

Minder radicale methode dan de vorige. Slechts één element van de lijst die als parameter is opgegeven, wordt verwijderd. Dit gebeurt als volgt: het programma controleert eerst de juistheid van de ingevoerde parameter, als het aantal van het te verwijderen 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 links 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::Remove(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 van 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 element invoegen in gespecificeerde plaats in de lijst.

Deze methode heeft als parameters: de positie van het toegevoegde element en zijn numerieke waarde. Het nieuwe element wordt precies op de opgegeven plaats geplaatst, dus de elementen rechts van het huidige worden één positie 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 gespecificeerd. Een iets andere situatie doet zich voor bij het toevoegen van een nieuw element tussen twee bestaande, gebruik hiervoor een lus om het invoegpunt van het element te bereiken en verbind vervolgens de componenten rechts en links ervan met het nieuwe element. Immers, wat moet er bijvoorbeeld gebeuren als het nodig is om de ketting te verlengen: het is nodig om hem te openen, dan een nieuwe schakel aan het eerste deel van de ketting bevestigen, de tweede aan dezelfde schakel bevestigen, iets vergelijkbaar is geïmplementeerd in deze methode. Het is vermeldenswaard dat als u een onjuiste positie opgeeft om toe te voegen, die kleiner is dan één of groter is dan het totale aantal elementen, het programma de juiste foutmelding zal weergeven.

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

cElement *cur = hoofd;

cElement *temp = nieuw cElement;

temp->setdata(val);

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, moet u de opdracht "insert" in het menu invoeren om met de lijst te werken. Voer vervolgens de positie en numerieke waarde in van het toe te voegen element, of het "terug"-commando om het verwijderen te annuleren (zie figuur 7).

Afbeelding 7 - Het proces van het invoegen van een element

De lijst na het toevoegen van het element met de waarde 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, moet nog worden opgemerkt dat: dit menu maakt het veel gemakkelijker om met de lijst te werken. Het algoritme van zijn werk bestaat uit het cyclisch aanroepen 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)

Figuur 9 - Beschikbare opdrachten

De volledige programmacode voor het menu staat in bijlage A.

1. Testen

Vaak zijn er tijdens het werk situaties die verband houden met: onjuiste invoer gegevens, waardoor het programma kan crashen. Natuurlijk moet elk programma beveiligingsalgoritmen implementeren tegen: onervaren gebruiker 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 wordt geïmplementeerd door de volgende code:

if (atoi(ss)!=NULL)

mijnlijst.Toevoegen(atoi(ss));

Voordat de methode add wordt aangeroepen om een ​​nieuw element aan de lijst toe te voegen, wordt de ingevoerde string gecontroleerd. De functie atoi converteert een tekenreekswaarde naar een numerieke waarde en retourneert NULL als de invoertekenreeks geen getal is. Dus alle regels die geen nummers zijn, worden tijdens het invoeren genegeerd, behalve de regel met het invoerstopcommando (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 andere invoerbewerkingen die in het programma aanwezig zijn.

Gevolgtrekking

In dit werk werden de concepten van abstracte gegevenstypen, de principes van hun representatie in moderne programmeertalen, in het bijzonder in C ++, verkregen. 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), evenals de op ADT gebaseerde benadering van programmeren, is tot op zekere hoogte de 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 bepaalde 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 Parnassus en moderne concepten van OOP, 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 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 Leer jezelf objectgericht programmeren in 21 dagen = Sams leer jezelf objectgericht programmeren in 21 dagen. - M.: "Williams", 2002. - S. 672.

3. Bertrand Meyer Objectgericht ontwerpen van softwaresystemen + CD. Internet Universiteit voor Informatietechnologie - INTUIT.ru, Russische editie, 2005

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

5. "Nieuwe programmeertalen en trends in hun ontwikkeling", Ushkova V., 2005

6. Bjorn Stroustrup "The C++ Programming Language" Speciale editie of 3e editie ed. Binom, Nevsky Dialect, ISBN 5-7989-0226-2, 5-7940-0064-3, 0-201-70073-5

7. Bjarne Stroustrup "Het ontwerp en de 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 tips om uw programma's en projecten te verbeteren" DMK, Peter, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1

bijlage A

Menu programmeercode

#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,"add")!=NULL) com_ind=2;

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

if (strstr(com,"delete")!=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,"back")==NULL)

if (atoi(ss)!=NULL)

mijnlijst.Toevoegen(atoi(ss));

systeem("cls");

// voeg elementen in

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

if (atoi(ss)!=NULL)

systeem("cls");

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

if (atoi(ss)!=NULL)

mijnlijst.Insert(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...

De ontwikkeling van abstracte modellen voor data en manieren om deze data te verwerken is essentieel onderdeel bezig met het oplossen van problemen met behulp van een computer. Voorbeelden hiervan zien we zowel op een laag niveau in het dagelijkse programmeren (bijvoorbeeld bij het gebruik van arrays en gelinkte lijsten, besproken in), als op een hoog niveau bij het oplossen van toegepaste problemen (zoals bij het oplossen van het verbindingsprobleem met behulp van het join-search forest in de "Inleiding"). Deze lezing bespreekt abstracte datatypes ( abstract datatype , hierna ADT), waarmee je programma's kunt maken met behulp van abstracties op hoog niveau. Met abstracte gegevenstypen kunt u de abstracte (conceptuele) transformaties die programma's op gegevens uitvoeren, scheiden van een bepaalde weergave van een gegevensstructuur en een bepaalde implementatie van een algoritme.

Alles computersystemen gebaseerd op abstractieniveaus: bepaalde fysieke eigenschappen van silicium en andere materialen maken het mogelijk een abstract model van een bit te gebruiken, dat de binaire waarden 0-1 kan aannemen; vervolgens wordt een abstract model van de machine gebouwd op de dynamische eigenschappen van de waarden van een bepaalde set bits; verder, gebaseerd op het werkingsprincipe van de machine onder controle van het programma op: machinetaal er wordt een abstract model van de programmeertaal gebouwd; en eindelijk bouwen abstract concept algoritme geïmplementeerd als een C++-programma. Abstracte datatypes maken het mogelijk om dit proces verder te brengen en abstracte mechanismen voor bepaalde rekentaken op een hoger niveau te ontwikkelen dan het C++-systeem biedt, toepassingsspecifieke abstracte mechanismen te ontwikkelen die geschikt zijn voor het oplossen van problemen in tal van toepassingsgebieden, en abstracte hogere mechanismen op niveau die deze basisconstructies gebruiken. Abstracte gegevenstypen bieden ons een oneindig uitbreidbare set van hulpmiddelen om steeds meer nieuwe problemen op te lossen.

Enerzijds bevrijdt het gebruik van abstracte constructies ons van zorgen over de gedetailleerde implementatie ervan; aan de andere kant, wanneer? prestatie programma belangrijk is, moet u weten wat de implementatiekosten zijn basishandelingen. We gebruiken veel basisabstracties die zijn ingebouwd in hardware computer en dienen als basis voor machine-instructies; andere abstracties in software implementeren; en gebruik aanvullende abstracties van eerder geschreven systeemsoftware. Abstracte constructies op hoog niveau zijn vaak gebaseerd op meer eenvoudige ontwerpen. Op alle niveaus geldt hetzelfde basisprincipe: je moet de belangrijkste bewerkingen in programma's en de belangrijkste kenmerken van data vinden, en vervolgens beide op abstract niveau lokaliseren en effectieve concrete mechanismen ontwikkelen voor de implementatie ervan. In deze lezing zullen we veel voorbeelden bekijken van de toepassing van dit principe.

Het ontwikkelen van een nieuw abstractieniveau vereist (1) het definiëren van de abstracte objecten die moeten worden gemanipuleerd en de bewerkingen die daarop moeten worden uitgevoerd; (2) vertegenwoordigen de gegevens in één of andere gegevensstructuur en voeren de verrichtingen uit; (3) en (het allerbelangrijkste) om ervoor te zorgen dat deze objecten gemakkelijk te gebruiken zijn voor het oplossen van toegepaste problemen. Deze punten zijn ook van toepassing op: eenvoudige soorten gegevens, zodat de basismechanismen voor het ondersteunen van gegevenstypen, die werden besproken in "Elementaire gegevensstructuren", voor onze doeleinden kunnen worden aangepast. De C++-taal biedt echter een belangrijke uitbreiding van het structmechanisme dat een klasse wordt genoemd. Klassen zijn uitermate nuttig bij het creëren van abstractieniveaus en worden daarom in de rest van het boek als het belangrijkste hulpmiddel voor dit doel beschouwd.

Definitie 4.1. Een abstract datatype (ATD) is een datatype (een set waarden en een set bewerkingen op die waarden) dat alleen toegankelijk is via een interface. Het programma dat de ADT gebruikt, wordt de client genoemd en het programma dat de specificatie van dit gegevenstype bevat, wordt de implementatie genoemd.

Het is het woord dat het gegevenstype alleen maar abstract maakt: in het geval van een ADT hebben clientprogramma's op geen enkele andere manier toegang tot gegevenswaarden dan de bewerkingen die in de interface worden beschreven. De weergave van deze gegevens en de functies die deze bewerkingen uitvoeren, bevinden zich in de implementatie en zijn volledig gescheiden door een interface van de klant. We zeggen dat de interface ondoorzichtig is: de klant kan de implementatie niet zien via de interface.

In C++-programma's wordt dit onderscheid meestal wat duidelijker gemaakt, omdat het het gemakkelijkst is om een ​​interface te maken door: data weergave, maar specificeren dat clientprogramma's geen directe toegang tot de gegevens hebben. Met andere woorden, klantontwikkelaars weten misschien: data weergave, maar kan het op geen enkele manier gebruiken.

Beschouw als voorbeeld de gegevenstype-interface voor punten (programma 3.3) uit paragraaf 3.1 "Elementaire gegevensstructuren". Deze interface verklaart expliciet dat punten worden weergegeven als structuren die bestaan ​​uit een paar getallen met drijvende komma, aangeduid met x en y. Dit gebruik van gegevenstypen is gebruikelijk in grote systemen software: we ontwikkelen een reeks conventies voor gegevensrepresentatie (en definiëren ook een reeks gerelateerde bewerkingen) en stellen deze regels beschikbaar via een interface zodat ze kunnen worden gebruikt door clientprogramma's die deel uitmaken van een groot systeem. Het datatype zorgt ervoor dat alle onderdelen van het systeem consistent zijn met de weergave van de onderliggende systeembrede datastructuren. Hoe goed deze strategie ook is, ze heeft één nadeel: als het nodig is om te veranderen data weergave, moet u alle clientprogramma's wijzigen. Programma 3.3 geeft ons weer een eenvoudig voorbeeld: een van de redenen voor het ontwikkelen van dit gegevenstype is het gemak van clientprogramma's die met punten werken, en we verwachten dat clients indien nodig toegang zullen hebben tot individuele coördinaten van een punt. Maar we kunnen niet overschakelen naar een andere gegevensweergave (bijvoorbeeld poolcoördinaten of 3D-coördinaten, of zelfs andere gegevenstypen voor individuele coördinaten) zonder alle clientprogramma's te wijzigen.

Programma 4.1 daarentegen bevat een implementatie van een abstract gegevenstype dat overeenkomt met het gegevenstype in Programma 3.3, maar met een C++-taalklasse die zowel de gegevens als de bijbehorende bewerkingen tegelijk definieert. Programma 4.2 is klantenprogramma A die werkt met dit gegevenstype. Deze twee programma's voeren dezelfde berekeningen uit als programma's 3.3 en 3.8. Ze illustreren een aantal van de belangrijkste eigenschappen van de klassen die we nu zullen beschouwen.

Wanneer we een definitie zoals int i in een programma schrijven, vertellen we het systeem om een ​​geheugengebied te reserveren voor gegevens van het (ingebouwde) type int, waarnaar verwezen kan worden als i. De C++-taal heeft de term object voor dergelijke entiteiten. Wanneer een definitie zoals POINT p in een programma wordt geschreven, wordt er gezegd dat er een object van de klasse POINT wordt gemaakt, waarnaar kan worden verwezen met de naam p. In ons voorbeeld bevat elk object twee gegevenselementen, x en y genaamd. Net als bij structuren kunnen ze worden aangeduid met namen als p.y.

De gegevensleden x en y worden gegevensleden van de klasse genoemd. De klasse kan ook lidfuncties definiëren die de bewerkingen implementeren die aan dit gegevenstype zijn gekoppeld. De klasse die in Programma 4.1 is gedefinieerd, heeft bijvoorbeeld twee lidfuncties genaamd POINT en distance .

Clientprogramma's, zoals programma 4.2, kunnen de lidfuncties aanroepen die aan een object zijn gekoppeld door hun namen op dezelfde manier op te geven als de namen van de gegevens in sommige structureren. De uitdrukking p.distance(q) berekent bijvoorbeeld de afstand tussen de punten p en q (dezelfde afstand moet worden geretourneerd door q.distance(p) aan te roepen). De functie POINT(), de eerste functie in Programma 4.1, is een speciale lidfunctie die een constructor wordt genoemd: deze heeft dezelfde naam als een klasse en wordt aangeroepen wanneer een object van die klasse moet worden gemaakt.

Programma 4.1. Uitvoering van de klasse PUNT (punt)

Deze klasse definieert een gegevenstype dat bestaat uit een reeks waarden die "paren van drijvende-kommagetallen" zijn (ervan uitgaande dat ze worden geïnterpreteerd als punten in een Cartesiaans vlak), evenals twee lidfuncties die zijn gedefinieerd voor alle instanties van het PUNT class: functie POINT() , een constructor die coördinaten initialiseert met willekeurige waarden van 0 tot 1, en een distance(POINT)-functie die de afstand tot een ander punt berekent. Data weergave is privé en alleen ledenfuncties kunnen het openen of wijzigen. De ledenfuncties zelf zijn openbaar (openbaar) en beschikbaar voor elke klant. De code kan bijvoorbeeld worden opgeslagen in een bestand met de naam POINT .cxx.

#erbij betrekken class POINT (privé: float x, y; public: POINT() ( x = 1.0*rand()/RAND_MAX; y = 1.0*rand()/RAND_MAX; ) float distance(POINT a) ( float dx = xa.x , dy = ya.y; return sqrt(dx*dx + dy*dy); ));

Programma 4.2. Clientprogramma voor de POINT-klasse (het dichtstbijzijnde punt vinden)

Deze versie van het 3.8-programma is een client die de POINT ADT gebruikt die is gedefinieerd in programma 4.3. De nieuwe bewerking maakt een array van POINT-objecten (door de POINT()-constructor aan te roepen om elk object te initialiseren met willekeurige coördinaatwaarden). De uitdrukking a[i].distance(a[j]) roept de lidfunctie distance op het object a[i] aan met argument a[j] .

#erbij betrekken #erbij betrekken #include "POINT.cxx" int main(int argc, char *argv) ( float d = atof(argv); int i, cnt = 0, N = atoi(argv); PUNT *a = nieuw PUNT[N]; voor (i = 0; i< N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

Het definiëren van POINT p in het clientprogramma resulteert in het toewijzen van een geheugengebied voor een nieuw object en vervolgens (met behulp van de POINT()-functie) het toewijzen van elk van zijn twee gegevenselementen een willekeurige waarde in het bereik van 0 tot 1.

Deze programmeerstijl, ook wel objectgeoriënteerd programmeren genoemd, wordt volledig ondersteund door de C++-klasseconstructie. Een klasse kan worden gezien als een uitbreiding van het concept van structuur, waarbij niet alleen gegevens worden gecombineerd, maar ook bewerkingen op die gegevens worden gedefinieerd. Er kunnen veel verschillende objecten zijn die tot dezelfde klasse behoren, maar ze zijn allemaal vergelijkbaar omdat hun gegevensleden dezelfde reeks waarden kunnen aannemen en dezelfde reeks bewerkingen kan worden uitgevoerd op die gegevensleden - in het algemeen zijn ze instanties van hetzelfde gegevenstype. Bij objectgeoriënteerd programmeren zijn objecten ontworpen om hun gegevensleden te verwerken (in tegenstelling tot het gebruik van onafhankelijke functies om gegevens die in objecten zijn opgeslagen te verwerken).

We kijken naar het voorbeeld van een kleine klasse die hierboven is beschreven om vertrouwd te raken met de basiskenmerken van klassen; dus het is verre van compleet. In echte code voor de puntklasse zullen we veel meer bewerkingen hebben. In programma 4.1 zijn er bijvoorbeeld niet eens bewerkingen waarmee u de waarden van de x- en y-coördinaten kunt achterhalen. Zoals we zullen zien, is het toevoegen van deze en andere bewerkingen een vrij eenvoudige taak. In deel 5 zullen we klassen voor punten en andere geometrische abstracties zoals lijnen en polygonen nader bekijken.

In C++ (maar niet in C) kunnen structuren ook bijbehorende functies hebben. Het belangrijkste verschil tussen klassen en structuren heeft te maken met toegang tot informatie, die wordt gekenmerkt door trefwoorden.