Abstrakt datatype. Abstrakte datatyper

Alle innebygde datatyper er abstrakte, selv om de sjelden kalles det.

Abstraksjonskonsept

Abstraksjon er en dom eller fremstilling av et objekt som kun inneholder egenskaper som er essensielle i en gitt kontekst. Abstraksjon lar deg kombinere objektforekomster i grupper, der de generelle egenskapene til objekter kan ignoreres, dvs. abstrakt fra dem. Abstraksjon er et effektivt verktøy mot programmeringskompleksitet, som lar programmereren fokusere på de essensielle egenskapene til objekter. Typer abstraksjoner: prosessabstraksjon og dataabstraksjon.

Prosessabstraksjon. Alle subrutiner er abstraksjoner av prosesser, de definerer måten programmet bestemmer at en prosess må gjøres på, uten å spesifisere detaljene for nøyaktig hvordan det skal gjøres. Evnen til å abstrahere bort de mange detaljene i algoritmen som en subrutine kjører, lar deg lage, lese og forstå store programmer. Enhver dataabstraksjon er operasjoner, definert som prosessabstraksjoner.

Dataabstraksjon. En abstrakt datatype er en innkapsling som kun inneholder representasjoner av data av en bestemt type og rutiner som utfører operasjoner på data av den typen. Ved å bruke tilgangskontroll kan ikke-essensielle detaljer i en typebeskrivelse skjules fra eksterne moduler som bruker typen. Programmoduler som bruker en abstrakt datatype kan deklarere variabler av den typen selv om den faktiske representasjonen av typen er skjult for dem. En forekomst av en abstrakt datatype kalles et objekt.

Grunnen til å lage datatypeabstraksjon og prosessabstraksjon er et middel mot kompleksitet, en måte å gjøre store og/eller komplekse programmer mer håndterbare på.

Innkapsling

Dele et program inn i syntaktiske beholdere som inneholder grupper av logisk relaterte rutiner og data. Disse syntaktiske beholderne kalles moduler, og utviklingsprosessen er modularisering.

Å komponere et program fra sett med rutiner og data, som hver kan kompileres separat, uten å rekompilere resten av programmet. Dette settet kalles en kompileringsenhet.

Innkapsling er en måte å integrere subrutiner og dataene de behandler til en sammenhengende helhet. Innkapsling, som er kompilert enten separat eller uavhengig av de andre, er grunnlaget for et abstrakt system og den logiske organiseringen av et sett med relaterte beregninger.

Abstrakte brukerdefinerte datatyper

Abstrakte brukerdefinerte datatyper må ha følgende egenskaper:

1) typedefinisjon, som lar programmoduler deklarere variabler av denne typen, samtidig som de skaper en reell representasjon av disse variablene i minnet.

2) et sett med operasjoner for å manipulere objekter av denne typen.

Formell definisjon av en abstrakt datatype i sammenheng med brukerdefinerte typer: En abstrakt datatype er en datatype som tilfredsstiller følgende to betingelser.

Representasjon (typedefinisjon) og operasjoner på objekter av denne typen er inneholdt i en syntaktisk enhet, variabler av denne typen kan også opprettes i andre moduler.

Representasjonen av objekter av denne typen er skjult fra programmoduler som bruker denne typen; operasjoner kan utføres på objekter som er direkte gitt i definisjonen av typen.

Ved å pakke typerepresentasjonen og operasjonene inn i en separat syntaktisk enhet kan du organisere programmet som logiske enheter som kan kompileres separat. For det andre blir det mulig å modifisere representasjonene av objekter av en gitt type eller operasjoner med dem i en egen del av programmet. Det er fordeler med å skjule detaljene i en type presentasjon. Klienter kan ikke "se" detaljene i et objekts visning, og koden deres er uavhengig av den visningen. På denne måten kan objektrepresentasjoner endres når som helst uten at det kreves endringer i klientkoden. En annen åpenbar og viktig fordel med å skjule informasjon er økt pålitelighet. Klienter kan ikke direkte endre de underliggende representasjonene av objekter, enten med vilje eller ved et uhell, derfor økes integriteten til slike objekter. Objekter kan bare endres ved å bruke operasjonene som er gitt for dette.

Problemer med type design

Det skal være mulig å gjøre typenavn og subrutineoverskrifter synlige i abstraksjonsklienter. Dette lar klienter deklarere variabler av en abstrakt type og manipulere verdiene deres. Selv om typenavnet må være synlig fra utsiden, må definisjonen være skjult.

Det er svært få generelle innebygde operasjoner som kan utføres på objekter av abstrakte typer, i motsetning til de som er gitt av en typedefinisjon. Slike operasjoner inkluderer oppdrag og likestillings- og ulikhetsprøver. Hvis språket ikke tillater brukere å overbelaste oppdragsoperatøren, bør det være innebygd. Likestillings- og ulikhetskontroller må være forhåndsdefinert i noen tilfeller og ikke i andre. Typedesigneren må selv definere operasjonene for de fleste abstrakte datatyper.

Smalltalk, C ++ og Java støtter direkte abstrakte datatyper.

Abstrakte datatyper i C ++

Ada- og Modula-2-språkene gir innkapsling som kan brukes til å modellere abstrakte datatyper, mens C++ introduserer konseptet med en klasse som direkte støtter abstrakte datatyper. I C ++ er klasser typer, men Ada-pakker og Modula-2-moduler er ikke typer. Pakker og moduler importeres, slik at den importerende programenheten kan deklarere variabler av enhver type definert i pakken eller modulen. I et C++-program er variabler deklarert som enheter av typen denne klassen. Dermed er klasser mye mer som innebygde typer enn pakker eller moduler. En programenhet som ser en pakke på Ada-språket eller en modul på Modula-2-språket har tilgang til alle åpne enheter bare ved navn. En C++-programenhet som erklærer en forekomst av en klasse har også tilgang til alle offentlige enheter i den klassen, men bare gjennom en forekomst av den klassen.

Sist oppdatert: 08.04.2018

I tillegg til de vanlige timene har C # abstrakte klasser... En abstrakt klasse er som en vanlig klasse. Det kan også ha variabler, metoder, konstruktører, egenskaper. Det eneste er at det abstrakte nøkkelordet brukes når du definerer abstrakte klasser:

Abstrakt klasse Menneske (offentlig int Lengde (get; sett;) offentlig dobbel Vekt (get; sett;))

Men hovedforskjellen er at vi ikke kan bruke konstruktøren til en abstrakt klasse for å lage objektet. For eksempel som følger:

Menneske h = nytt Menneske ();

Hvorfor trenger vi abstrakte klasser? La oss si at vi i vårt banksektorprogram kan definere to hovedenheter: en bankkunde og en bankansatt. Hver av disse enhetene vil være forskjellige, for eksempel for en ansatt må du definere hans stilling, og for en klient - beløpet på kontoen. Følgelig vil klient og ansatt utgjøre separate klient- og ansattklasser. Samtidig kan begge disse enhetene ha noe til felles, for eksempel for- og etternavn, en annen felles funksjonalitet. Og det er bedre å flytte denne generelle funksjonaliteten inn i en separat klasse, for eksempel Person, som beskriver en person. Det vil si at ansatt- og klientklassene kommer fra Person-klassen. Og siden alle objekter i systemet vårt vil representere enten en bankansatt eller en klient, vil vi ikke opprette objekter direkte fra Person-klassen. Så det er fornuftig å gjøre det abstrakt:

Abstrakt klasse Person (public string Name (get; set;) public Person (string name) (Name = name;) public void Display () (Console.WriteLine (Name);)) class Client: Person (public int Sum (get) ; sett;) // kontobeløp offentlig Klient (strengnavn, int sum): base (navn) (Sum = sum;)) klasse Ansatt: Person (offentlig streng Stilling (get; sett;) // stilling offentlig Ansatt ( streng navn, strengposisjon): base (navn) (Posisjon = posisjon;))

Da kan vi bruke disse klassene:

Klientklient = ny klient ("Tom", 500); Ansatt ansatt = ny ansatt ("Bob", "Apple"); klient.Visning (); ansatt.Visning ();

Eller til og med slik:

Personklient = ny klient ("Tom", 500); Person ansatt = ny ansatt ("Bob", "Operator");

Men vi kan IKKE lage et Person-objekt ved å bruke konstruktøren til Person-klassen:

Person person = ny person ("Bill");

Til tross for at vi ikke direkte kan kalle konstruktøren til Person-klassen for å lage et objekt, kan konstruktøren i abstrakte klasser spille en viktig rolle, spesielt for å initialisere noen variabler og egenskaper som er felles for avledede klasser, som er sak med egenskapen Navn. Selv om eksemplet ovenfor ikke kaller personkonstruktøren, kan klient- og ansattavledede klasser referere til det.

Abstrakte klassemedlemmer

I tillegg til de vanlige egenskapene og metodene, kan en abstrakt klasse ha abstrakte klassemedlemmer, som er definert ved hjelp av det abstrakte nøkkelordet og har ingen funksjonalitet. Spesielt kan abstrakt være:

• Egenskaper

  Indeksører

Abstrakte klassemedlemmer må ikke ha den private modifikatoren. I dette tilfellet må den avledede klassen overstyre og implementere alle abstrakte metoder og egenskaper som er i den abstrakte basisklassen. Når den overstyres i en avledet klasse, deklareres en slik metode eller egenskap også med overstyringsmodifikatoren (som med vanlige overstyrende virtuelle metoder og egenskaper). Det bør også bemerkes at hvis en klasse har minst én abstrakt metode (eller abstrakt egenskap, indekserer, hendelse), så må denne klassen defineres som abstrakt.

Abstrakte medlemmer, som virtuelle, er en del av det polymorfe grensesnittet. Men hvis vi, når det gjelder virtuelle metoder, sier at den arvende klassen arver implementeringen, arves grensesnittet representert av disse abstrakte metodene i tilfelle av abstrakte metoder.

Abstrakte metoder

La oss for eksempel gjøre visningsmetoden abstrakt i eksemplet ovenfor:

Abstrakt klasse Person (public string Name (get; set;) public Person (string name) (Name = name;) public abstract void Visning ();) class Client: Person (public int Sum (get; set;) // sum på kontoen offentlig Client (strengnavn, int sum): base (navn) (Sum = sum;) offentlig overstyring void Display () (Console.WriteLine ($ "(Name) har en konto for beløpet (Sum)") ;)) klasse Ansatt: Person (offentlig streng Posisjon (get; sett;) // stilling offentlig Ansatt (strengnavn, strengposisjon): base (navn) (Posisjon = stilling;) offentlig overstyring void Visning () (Console.WriteLine ($ " (Posisjon) (Navn) ");))

Abstrakte egenskaper

Bruken av abstrakte egenskaper bør bemerkes. Å definere dem ligner på å definere autoegenskaper. For eksempel:

Abstrakt klasse Person (offentlig abstrakt streng Navn (get; sett;)) klasse Klient: Person (privat strengnavn; offentlig overstyrt streng Navn (få (retur "Mr / Ms." + Navn;) sett (navn = verdi;)) ) klasse Ansatt: Person (offentlig overstyringsstreng Navn (get; sett;))

Person-klassen definerer en abstrakt Navn-egenskap. Det ser ut som en bileiendom, men det er ikke en bileiendom. Siden denne egenskapen ikke trenger å implementeres, har den bare tomme get- og set-blokker. I avledede klasser kan vi overstyre denne egenskapen for å gjøre den til en fullstendig egenskap (som i Client-klassen) eller gjøre den automatisk (som i Employee-klassen).

Avslag på å implementere abstrakte medlemmer

Den avledede klassen må implementere alle abstrakte medlemmer av basisklassen. Imidlertid kan vi droppe implementeringen, men i dette tilfellet må den avledede klassen også defineres som abstrakt:

Abstrakt klasse Person (offentlig abstrakt streng Navn (get; sett;)) abstrakt klasse Manager: Person ()

Abstrakt klasseeksempel

Et lærebokeksempel er systemet med geometriske former. I virkeligheten er det ingen geometrisk figur som sådan. Det er en sirkel, et rektangel, en firkant, men det er rett og slett ingen figur. Imidlertid har både sirkelen og rektangelet noe til felles og er former:

// abstrakt klasse av figuren abstrakt klasse Figur (// abstrakt metode for å få omkretsen offentlig abstrakt flyte Perimeter (); // abstrakt metode for å få området offentlig abstrakt flyte Areal ();) // avledet klasse av rektangelklassen Rektangel: Figur (offentlig flytebredde (hent; sett;) offentlig flytehøyde (hent; sett;) offentlig rektangel (flytebredde, flytehøyde) (this.Width = width; this.Height = høyde;) // overstyre får perimeter public override float Perimeter () (retur Width * 2 + Height * 2;) // override får området public override float Area () (retur Width * Height;))

Vedlegg til arbeidsprogrammet for faget "Strukturer og algoritmer for databehandling i datamaskin"

Den abstrakte datatypen "Liste".

Liste- en sekvens av elementer av en bestemt type en1 , en2 , ..., en n, hvor n https://pandia.ru/text/78/308/images/image001_307.gif "width =" 13 "height =" 16 "> 1, deretter en1

Kalles det første elementet, og an- det siste elementet på listen. Listeelementer er lineært ordnet i henhold til deres plassering i listen. Ai element forut element ai+1 til Jeg = 1,2, n-1 og ai bør per ai-1 til Jeg = 2,3, n. Hvert element i listen ai Det har posisjon Jeg, Jeg=1,2, n. Det er en plassering i listen , betyr slutten på listen - null. Den følger det siste elementet i listen.

Operatører av ADT "List":

1. SETT INN ( x, R,L). Denne setningen setter inn et objekt NS i posisjon R i listen L, flytte elementer fra posisjon p og videre til neste høyere posisjon. Således, hvis listen L består av elementer en1 , en2 , ..., an a1, a2, ..., ap-1, x, ap, ..., enn.... Hvis p tar verdien null, så har vi en1 , en2 , ..., enn , , NS... Hvis i listen L ingen stilling R, da er resultatet av denne uttalelsen udefinert.

2. LOKALISER(x , L ). Denne funksjonen returnerer posisjonen til objektet NS i listen L. Hvis objektet er i listen x forekommer flere ganger, så returneres posisjonen til det første objektet fra begynnelsen av listen NS. Hvis objektet NS ikke på listen L så kommer den tilbake null.

3. HENTE(s , L ). Denne funksjonen returnerer elementet i posisjon R i listen L. Resultatet er udefinert hvis p = null eller i listen L ingen stilling R.

4. SLETT(s , L ). Denne operatøren fjerner elementet i posisjon R liste L. Så hvis listen L består av elementer en1 , en2 , ..., an, så etter å ha kjørt denne operatoren vil den se ut a1, a2, ...,, ap- Jeg , ap+ Jeg, ..., en n. Resultatet er udefinert hvis listen inneholder L ingen stilling R eller R = null.

5. NESTE ( p, L ) og FORRIGE (s, L ). Disse funksjonene returnerer henholdsvis neste og forrige posisjon fra posisjonen R i listen L. Hvis R - siste plassering på listen L, deretter NESTE (s, L) = null... NESTE-funksjonen er udefinert når p =null... FORRIGE-funksjonen er udefinert hvis p = 1. Begge funksjonene er udefinerte hvis listen L ingen stilling R.

6. MAKENULL( L ) ... Denne funksjonen lager en liste L tom og returnerer posisjonen null.

7. FØRST(L ). Denne funksjonen returnerer den første posisjonen i listen L. Hvis listen er tom, returneres posisjonen null.

8. SKRIV LISTE(L ). Skriver ut listeelementer L i den rekkefølgen de vises i listen.

Listevisning ved bruk av en matrise:

Listevisning ved hjelp av enkeltlenket liste:

Legende:

- en peker til begynnelsen av listen,

· siste - peker til siste element i listen ,

· makslengde - maksimal lengde (antall elementer) i listen.

Representerer en liste ved å bruke en dobbeltlenket liste:

Øvelser:

1. Skriv programmer for å sette inn, slette og søke i elementer i en sortert liste, bruk for å implementere listen

§ array,

§ pekere.

2. Skriv et program for å slå sammen

§ to sorterte lenkede lister,

§ n sorterte lenkede lister,

3. Gitt et polynom av formen

p (x) = c1 xe1 + c2 xe2 + + mednNSn, hvor e1> e2> ...> en> 0.

Et slikt polynom kan representeres som en koblet liste, der hvert element har tre felt: ett for koeffisienten medJeg den andre er for eksponenten eJeg den tredje er for en peker til neste element. For den beskrevne representasjonen av polynomer, skriv et program for addisjon og multiplikasjon av polynomer ved å bruke denne representasjonen.

4. Implementer LIST ADT for enhver datatype og dens INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST-setninger:

§ listen er gitt som en matrise,

§ listen er spesifisert som en enkeltlenket liste,

§ listen er spesifisert som en dobbeltlenket liste.

Arbeidsprogram avsnitt 2.1.2

Den abstrakte datatypen "Stack".

Stable - det er en spesiell type liste der alle innsettinger og slettinger gjøres i bare den ene enden høydepunkt , (topp). Tilbehøret brukes til stabelen LIFO(sist-inn-først-ut - sist inn - først ut).

Operatører av ATD "Stack":

1. MAKENULL(S). Tøm S-stabelen.

2. TOPP(S). Returnerer et element fra toppen av stabelen S. Vanligvis identifiseres toppen av stabelen med posisjon 1, så kan TOP (S) skrives i form av vanlige listeoperatorer som HENT (FØRST (S), S).

3. POP(S). Fjerner et element fra toppen av stabelen (spretter fra stabelen), når det gjelder listesetninger, kan denne setningen skrives som DELETE (FIRST (S), S).

4. TRYKK(x, S ). Setter inn et element NS til toppen av stabelen S (skyver gjenstanden på stabelen). Elementet som tidligere var på toppen av stabelen blir elementet ved siden av toppen osv. Når det gjelder generelle listeoperatorer, kan denne setningen skrives som INSERT (; c, FIRST (S), S).

5. TØMME(S) ... Denne funksjonen returnerer sann hvis stabelen S tom og falsk ellers.

array:

Stabelvisning ved hjelp av enkeltlenket liste:

Øvelser:

Implementer STACK ADT for enhver datatype og dens MAKENULL, TOP, POP, PUSH, EMPTY-operatører.

§ stabelen er satt som en matrise,

Stabelen er satt som en enkeltlenket liste.

Arbeidsprogram avsnitt 2.1.2

Den abstrakte datatypen "Kø".

Kø (kø) er en spesiell type liste der elementer settes inn fra en ende kalt bakre (bak), og fjernes fra den andre, front (front). Køer kalles også "FIFO-lister" (FIFO står for først-inn-først-ut: først inn, først ut). Operatører som utføres på køer ligner på stabeloperatører. Den vesentlige forskjellen mellom dem er at nye elementer settes inn slutten av listen heller enn i begynnelsen, som i stabler.

Operatører av ADT "Queue":

1. MAKENULL(Q) sletter kø Q , gjør den tom.

2. FRONT(Q) - en funksjon som returnerer det første elementet i køen Q. Du kan implementere denne funksjonen ved å bruke listeoperatorer som HENT (FØRSTE (Q), Q ).

3. KØ(en, Q) setter inn et element NS på slutten av køen Q.

Med listeoperatorer kan denne operatoren utføres slik: INSERT (x, END (Q), Q ).

4. AVKØ(Q) fjerner det første elementet i køen Q . Også implementerbar med listesetninger som DELETE (FIRST (Q), Q).

5. TØMME(Q) returnerer sann hvis og bare hvis Q er en tom kø.

syklisk array:

Legende:

Q- kø,

Q. front- peker til begynnelsen av køen,

Q. bak- en peker til slutten av køen.

Kø representasjon med enkeltlenket liste:

Øvelser:

Implementer QUEUE ADT for enhver datatype og dens MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY-setninger.

Køen er spesifisert som en sirkulær matrise,

Køen er spesifisert som en dobbeltlenket liste.

Abstrakt datatype "Tre".

Tre er en samling av elementer kalt knuter (hvorav en er definert som rot ), og relasjoner ("foreldre") som danner en hierarkisk struktur av noder. Noder, som listeelementer, kan være elementer av enhver type. Formelt kan et tre defineres rekursivt som følger.

1. En node er et tre. Den samme noden er også roten til dette treet.

2. La NS - dette er en node, en T1 , T2, ...,Tk- trær med røtter n1 . n2 , ..., nk hhv. Du kan bygge et nytt tre ved å gjøre NS forelder til noder n1 . n2 , ..., nk... I dette treet NS vil være roten, en T1 , T2, ...,Tk - undertrær denne roten. Noder n1 . n2 , ..., nk er kalt sønner knute NS.

Denne definisjonen inkluderer ofte konseptet null tre , det vil si et "tre" uten noder, et slikt tre er betegnet med ordet null .

Eksempel: Om kapittel i boken kan skjematisk representeres av et tre. Foreldre-sønn-forholdet vises som en linje. Trær er vanligvis tegnet fra topp til bunn slik at foreldrene er over "barna".

DIV_ADBLOCK135 ">

Nodehøyde et tre er lengden på den lengste veien fra denne noden til et blad. I eksemplet, høyden på noden Kapittel 1 er lik 1, node Kapittel 2 - 2, og node Ch. Z - 0. Trehøyde sammenfaller med høyden på roten. Node dybde er definert som lengden på banen (den er den eneste) fra roten til denne noden.

Sønner av en node er vanligvis sortert fra venstre til høyre. Derfor er de to trærne i figuren forskjellige, siden rekkefølgen til nodens sønner en annerledes. Hvis rekkefølgen av sønner ignoreres, kalles et slikt tre uordnet , ellers heter treet ryddig .

Operatører av ATD "Tree":

1. FORELDRE(n, T). Denne funksjonen returnerer den overordnede til noden NS i treet T. Hvis NS er en rot som ikke har noen forelder, så returnerer den i dette tilfellet null... Her null indikerer at et tre utenfor grensene har oppstått.

2. TIL VENSTRE__ BARN(n , T). Denne funksjonen returnerer underordnet lengst til venstre for noden. n i treet T. Hvis n er et blad (og har derfor ikke en sønn), så kommer det tilbake null.

3. IKKE SANT_ SØSKEN(n , T). Denne funksjonen returnerer nodens høyre søsken NS i treet T eller verdi null,. hvis den ikke eksisterer. Det er dette foreldrene er til for R knute NS og alle knutens sønner R, da blant disse sønnene er noden umiddelbart til høyre for. knute NS.

4. MERKELAPP(n , T ). Returnerer etiketten til noden n... tre T. Denne funksjonen krever at etiketter er definert på trenodene.

5. SKAPE(v , T 1 , T 2 , ..., Ti ,) er en familie av funksjoner som lager en ny rot for hver i = 0, 1, 2, ... r med etikett v og så for denne roten skaper i sønner, som blir røttene til undertrær T1 , T2, ....Ti;. Disse funksjonene returnerer et rotfestet tre r... Merk at hvis i = 0, returneres én node r, som er både en rot og et blad.

6. ROT(T ) returnerer noden som er roten til treet T, hvis T- Tomt tre kommer deretter tilbake null.

7. MAKENULL(T ). Denne operatøren lager treet T tomt tre.

Å representere et tre ved å bruke en rekke foreldre:

Trevisning ved hjelp av koblede lister:

Representasjon av treet ved hjelp av venstre sønner og høyre brødre.

Betegnelser i figuren:

noderom – en rekke trenoder,

merkelapp – nodeetikett, Overskrift – indeksen til venstre sønn i listen over sønner,

cellspase – en rekke lister over sønner av noder,

node – peker til en node i en matrisenoderom , neste – indeksen til høyre sønn i listen over sønner.

Øvelser:

1. Gitt et tre:

DIV_ADBLOCK137 ">

§ treet er gitt som en rekke nodeposter som inneholder indeksen til sønnen lengst til venstre, indeksen til høyre søsken og en etikett,

Et tilkoblet binært tre spesifiseres ved å bruke pekere til venstre og høyre sønner.

4. Skriv funksjoner for å krysse et binært tre i forover, bakover og symmetrisk rekkefølge.

Arbeidsprogram avsnitt 2.1.3

Den abstrakte datatypen "Sett".

Masse av er vanligvis avbildet som en sekvens av elementene, omsluttet av krøllete klammeparenteser, for eksempel betegner (1, 4) et sett som består av to elementer - tall 1 og 4. Rekkefølgen som elementene i settet er skrevet i er ikke avgjørende, slik at du kan skrive (4, 1) på samme måte som (1, 4), når du skriver samme sett. Settet er ikke en liste (i hvert fall på grunn av den vilkårlige rekkefølgen av skriveelementer). Det er ingen dupliserte elementer i settet ((1, 4, 1) er ikke et sett).

Det grunnleggende begrepet i settteori er begrepet relasjonen som tilhører settet angitt med symbolet. Dermed oppføringen NS NS tilhører ikke settet EN", det er. NS ikke medlem av settet EN... Det er et spesielt sett merket med et symbol kalt tomme, mange , og som ikke har noen elementer. Sett DIV_ADBLOCK138 ">

De sier at mengden EN inneholder i settet V(eller skrur på i en mengde V), skrevet EN V eller V EN hvis noe element i settet EN er også en del av settet V. Når EN V si også at settet EN er en en undergruppe av settet V.

For eksempel, (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif "width =" 15 "height =" 15 src = "> V og AB, så kalles mengden A eget, sant eller streng delmengde mengder V.

Hovedoperasjonene som utføres på sett er union, skjæring og forskjell. Konsolidering settene EN og V(angitt med EN V) kalles et sett som består av elementer som tilhører minst ett av settene EN og V.

Kryss settene EN og V(angitt med EN V) kalles et sett som kun består av de elementene som tilhører settet EN, og settet V. Forskjell settene EN og V(angitt med EN\ B) kalles et sett som bare består av de elementene i settet EN som ikke tilhører settet V.

For eksempel, hvis A = (a, b, c) og B = (b, a), så A B = (a, b, c, d), A B = (b) og A \ B = (a, c ) .

Operatører av ADT "Set":

1. UNION(EN, B, C) EN og V MED, lik EN V.

2. KRYSS(EN, B, C) har "input"-argumenter satt EN og V, og som et resultat - "output"-settet MED, lik EN V..

3. FORSKJELL(EN, B, C) har "input"-argumenter satt EN og V, og som et resultat - "output"-settet MED, lik A \ B.

4. SLÅ SAMMEN( EN , B, C) operatør utfører fusjon (slå sammen), eller forening av usammenhengende sett . Denne operatøren er ikke forskjellig fra operatøren. UNION, men her antas det at operanden setter ikke kryss (dvs. de har ingen felles elementer). Operatøren tildeler til settet MED betydning EN V, men resultatet vil være udefinert hvis A B, dvs. i tilfellet når settene EN og V har felles elementer.

5. medlem(x, A ) har argumenter satt EN og objekt NS av samme type som elementene i settet EN, og returnerer en boolsk verdi ekte(sant) hvis NS a "," b "," c ")) = "en". Operatøren MAKS.

11.LIK(EN , V ) returnerer verdien ekte hvis og bare hvis settene EN og V består av de samme elementene.

12. FINNE(x ) opererer i et miljø der det er et sett med usammenhengende sett. Den returnerer navnet (entall) på settet som har et element NS.

Sett representasjon:

Settet kan spesifiseres ved hjelp av en matrise eller en koblet liste.

Øvelser:

1. To sett A = (1, 2, 3) og B = (3, 4, 5) er gitt. Hva blir resultatet av å utføre følgende utsagn?

UNION (A.B. C),

KRYSSING (A, B, C),

FORSKJELL (A.B.C),

MEDLEM (l. A),

SETT INN (1, A),

SLETT (1, A),

2. Implementer Set ADT for enhver datatype og dens MAKENULL, UNION, INTERSECTION, MEMBER, MIN operatorer.

Settet er spesifisert ved hjelp av en matrise med fast lengde og en peker til den siste okkuperte posisjonen i matrisen,

Settet er spesifisert ved hjelp av en usortert lenket liste,

Settet er spesifisert ved hjelp av en sortert lenket liste,

Arbeidsprogram avsnitt 2.1.3

Spesielle typer sett

Binært søketre Abstrakt datatype

Binært søketre - en datastruktur for å representere sett, hvis elementer er ordnet etter en eller annen lineær ordensrelasjon. Binære søketrær kan implementere settoperatorer SETT INN, SLETT, MEDLEM og MIN, og deres utførelsestid er i gjennomsnitt av størrelsesorden O (log n) for sett som består av NS elementer.

Et kjennetegn ved et binært søketre er at nodene er merket med settelementer (trenoder inneholder settelementer). Dessuten er alle elementer lagret i nodene til det venstre undertreet til en hvilken som helst node NS, mindre enn elementet i noden NS, og alle elementene som er lagret i nodene til nodens høyre undertre NS, mer enn elementet i noden NS.

Eksempler på binære tre:

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

AVL-trevisningen er den samme som den binære søketrevisningen.

En annen type balansert søketre er 2-3 tre. Strukturen til et 2-3-tre er forskjellig fra strukturen til et binært søketre. For et 2-3-tre er det karakteristisk at alle noder har 2 eller 3 sønner, alle stier fra rot til blad har samme lengde, og alle elementer av settet er inneholdt i blader. Noder 2-3 av treet er delt inn i interne og terminale (blader). Interne noder brukes bare for å rute tresøk. Hver intern node inneholder nøklene til de minste elementene til den andre og tredje sønnen (hvis det er en tredje sønn) og pekere til nodene til sønnene.

Binært søk koblet trevisning:

Representasjon av et balansert tilkoblet 2-3 tre:

Øvelser:

1. Tegn alle mulige binære søketrær for de fire elementene 1, 2, 3 og 4.

2. Sett inn heltallene 7, 2, 9, 0, 5, 6, 8, 1 i et tomt binært søketre.

3. Vis resultatet av å fjerne tallet 7 og deretter tallet 2 fra treet som ble oppnådd i forrige øvelse.

4. Tegn et 2-3-tre som vil resultere fra å sette inn elementene 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 i det tomme settet (representert som 2-3-tre).

5. Vis resultatet av å fjerne element 3 fra 2-3 av treet som ble oppnådd i forrige oppgave.

3. Implementer søketreet ADT for enhver datatype og dens INSERT-, DELETE-, MEMBER- og MIN-setninger.

Treet er gitt som et koblet binært tre

Tre er oppgitt som 2-3 trær

Arbeidsprogram avsnitt 2.1.3

Abstrakt datatype "Ordbok".

Ordbok - et sett beregnet for lagring av "gjeldende" objekter med periodisk innsetting eller sletting av noen av dem. Fra tid til annen blir det også nødvendig å finne ut om et bestemt element er tilstede i et gitt sett. Ordboken er implementert ved hjelp av Ordbok ADT med operatører SETT INN,SLETT og MEDLEM... Ordbokoperatorsettet inkluderer også operatoren MAKENULLå initialisere ADT-datastrukturer.

En ordbok kan representeres ved hjelp av en hashtabell. Tabellen er bygget på grunnlag av følgende idé: et potensielt sett med elementer (eventuelt uendelig) er delt inn i et begrenset antall klasser. Til V klasser nummerert fra 0 til I 1, under konstruksjon hash-funksjon h slik at for ethvert element NS original sett funksjon h (x) tar en heltallsverdi fra intervallet 0, ..., V - 1, som tilsvarer klassen elementet tilhører NS. Element NS ringer ofte nøkkel, h ( x) - hasj-verdi x, og "klasser" - segmenter ... Hvordan løse hashing-kollisjoner (to elementer i et sett har samme verdi h (x)), brukes offentlig og privat hashing.

åpen hash-tabell

En rekke kalt segmenttabell og indeksert segmentnummer 0, 1, ..., B - 1 , inneholder overskrifter for V koblede lister. Element Jeg-th liste er et element i det originale settet som h(.x :) =Jeg.

Ordbok representasjon med privat hash-tabell

Segmenttabellen lagrer elementene i vokabularet direkte. Derfor kan bare ett ordbokelement lagres i hvert segment. Ved privat hashing brukes teknikken re-hashing ... Når du prøver å plassere et element x å segmentere med nummer h ( x ) , som allerede er okkupert av et annet element, velges en sekvens av segmentnummer h 1 ( x ) ,h 2 ( x ) , … hvor elementet kan plasseres. Belegget for hvert av disse segmentene kontrolleres sekvensielt inntil et ledig segment blir funnet. Elementet er plassert i den x ... Ulike kollisjonsoppløsningsmetoder brukes for å angi segmentnummer ved re-hashing. For eksempel lineær hashing-metode, mid-square-metode, tilfeldig hashing-metode

Øvelser:

1. Anta at du bruker hash-funksjonen h (i) = i% 7 for å hash heltall til en 7-segments hashtabell.

· Gi den resulterende hashtabellen hvis de nøyaktige kubene 1, 8, 27,64,125, 216,343 er satt inn i den;

· Gjenta forrige punkt for en lukket hashtabell med en lineær kollisjonsoppløsningsteknikk.

2. Anta at du har en privat hashtabell med 5 segmenter, en hashfunksjon h (i) = i% 5, og en lineær kollisjonsoppløsningsteknikk. Vis resultatet av å sette inn en sekvens med tallene 23, 48, 35, 4, 10 i den opprinnelig tomme hash-tabellen.

3. Implementer Dictionary ADT for tekststrenger og dens INSERT-setninger , SLETT, MEDLEM og MAKENULL

Ordboken er spesifisert ved hjelp av en åpen hash-tabell,

Ordboken er spesifisert ved å bruke en lukket hashtabell med en lineær kollisjonsoppløsningsteknikk,

Arbeidsprogram avsnitt 2.1.3

Den abstrakte datatypen "Display".

Vise - dette er et sett, på elementene som funksjonen for å vise elementer av samme type er definert ( definisjonsområder ) til elementer av en annen type ( rekke verdier ) av en annen type. Vise M samsvarer med et element d av typen domenetype fra omfang til element r av typen rangetype fra range: M(d) = r.Tomt display inneholder ingen elementer

Operatører av ADT "Display":

1. MAKENULL(M ). Lager visning M tømme.

2. TILDELE (M d, r). Gjør M(d) lik r uansett hvordan M(d) var tidligere definert.

3. BEREGNE ( M, d, r). Returnerer sann og tildeler en verdi til r M(d), hvis sistnevnte er definert, og returnerer false ellers.

Visningsvisning: kartleggingen kan implementeres effektivt ved hjelp av hash-tabeller. Her x setter verdien fra omfanget av tilordningsdefinisjonen, og tabellelementet med nummeret h ( x ) - et element fra serien.

Arbeidsprogram avsnitt 2.1.3

Abstrakt datatype for prioritert kø

Prioritert kø er et sett for elementene som prioritetsfunksjonen er satt til, det vil si for hvert element x sett, kan du beregne funksjonen R( x )- elementprioritet x , som vanligvis tar verdier fra et sett med reelle tall, eller mer generelt fra et lineært ordnet sett.

ADT "Priority Queue" basert på ADT "Set" med operatører SETT INN og SLETTMIN og også med operatøren MAKENULL for å initialisere datastrukturen. Operatør SETT INN for en prioritert kø forstås i vanlig forstand, mens SLETTMIN er en funksjon som returnerer elementet med lavest prioritet og, som en bieffekt, fjerner det fra settet.

Kø representasjon med en ordnet dobbeltlenket liste.

Kø representasjon med delvis bestilt tilkoblet tre:

Hovedideen bak denne implementeringen er å organisere elementene i køen i et binært tre. På det nedre nivået, hvor noen blader kan mangle, kan alle manglende blader være plassert bare til høyre for de nåværende bladene på lavere nivå. Det er mer viktig at treet delvis bestilt . Dette betyr at prioritet til noden v ikke større enn prioriteten til noen sønn av noden v, der nodeprioritet er prioritetsverdien til elementet som er lagret i denne noden. Det kan ses av figuren at små prioritetsverdier ikke kan vises på et høyere nivå, der det er store prioritetsverdier.

DELETEMIN-funksjonen returnerer elementet med lavest prioritet som må være roten til treet. For ikke å ødelegge treet og for å bevare den delvise rekkefølgen av prioritetsverdiene i treet etter at roten er fjernet, utføres følgende handlinger: noden lengst til høyre er plassert på det laveste nivået og midlertidig plassert i roten til treet. Dette elementet går så nedover grenene på treet (til lavere nivåer), og bytter plass med sønner med lavere prioritet underveis, til dette elementet blir et blad eller kommer i en posisjon der sønnene i det minste ikke vil ha mindre prioritet.

Representasjon av en kø ved bruk av en matrise som inneholder nodene til et delvis ordnet tre:

I en rekke EN den første n stillinger samsvarer n trenoder. Element EN inneholder roten til treet. Venstre sønn av en trenode EN[ Jeg], hvis det finnes, er det i cellen EN, og den rette sønnen, hvis han eksisterer, er i cellen EN. Omvendt, hvis sønnen er i cellen EN[ Jeg], da er dens forelder i cellen EN[ Jeg%2] ... Trenoder fyller celler EN, EN, … EN[ n] sekvensielt nivå for nivå, starter fra roten, og inne i nivået - fra venstre til høyre. Treet vist ovenfor vil bli representert i matrisen med følgende sekvens av nodene: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Øvelser:

1. Tegn et delvis ordnet tre ved å sette inn heltall 5, 6, 4, 9, 3, 1 og 7 i et tomt tre. Hva ville være resultatet av å bruke tre DELETEMIN-setninger suksessivt på dette treet?

2. Implementer Priority Queue ADT for enhver datatype og dens INSERT-, DELETEMIN- og MAKENULL-setninger

§ et delvis ordnet tre implementeres ved hjelp av pekere,

§ Et delvis ordnet tre implementeres ved hjelp av en matrise.

Arbeidsprogram avsnitt 2.1.3

Den abstrakte datatypen "Union of Sets".

ADT er en forening av objekter, som hver er et sett. Hovedhandlingene som utføres på et slikt sett er å kombinere settene i en bestemt rekkefølge, samt å sjekke om et bestemt objekt tilhører et bestemt sett. Disse oppgavene løses ved hjelp av operatører SLÅ SAMMEN(Tøm) og FINNE(Finne). MERGE-operatør ( EN, B, C) lager settet MED lik foreningen av sett EN og V hvis disse settene ikke krysser hverandre (det vil si ikke har felles elementer); denne operatøren er udefinert hvis settene EN og V krysse. FINN funksjon ( x) returnerer settet som elementet tilhører NS; i tilfelle når NS tilhører flere sett eller ikke tilhører noen, er verdien av denne funksjonen udefinert.

Operatører av ADT "Union of Sets":

1. SLÅ SAMMEN(EN , V) kombinerer komponenter EN og ... V, resultatet tilordnes enten A eller V.

2. FINNE(x ) - en funksjon som returnerer navnet på komponenten den tilhører NS.

3. FØRSTE(EN , NS ) oppretter en komponent kalt A som bare inneholder elementet NS.

Representasjon av forening av sett ved bruk av matriser:

Settnavnet er det samme som matriseindeksverdien setthoder ( navn 0 )

Legende:

setthoder - rekke setthoder:

§ med telle - antall elementer i settet,

§ første element - array indeksnavnmed det første elementet i settet,

navn – rekke lister over elementer i sett:

settnavn - navnet på settet som elementet tilhører, neste element - indeksen til det neste elementet i listen til det gitte settet (indeksverdi 0 brukes som slutten av listen).

Arbeidsprogram avsnitt 2.1.3

Abstrakt datatype “ Rettet graf "

Grunnleggende definisjoner:

Rettet graf (digraf ) G = (V, E) består av mange hjørner V og mange buer E. Toppunkt kalles også knuter , og buer - orienterte ribber . Buen kan representeres som et ordnet par hjørner ( u, w), hvor er toppen og kalt begynnelsen , en w - slutten buer.

De sier også at buen og -> w fører fra toppen til toppen w, og toppen w ved siden av med topp v.

Diagrameksempel 1:

Digraf-toppunkter kan brukes til å representere objekter, og buer kan brukes til å representere forhold mellom objekter.

Av i en digraf mener vi en sekvens av hjørner v1 , v2 , … , vn , , som det er buer for v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Denne stien starter på toppen v1 og passerer gjennom toppene v2 , v3 , ..., vn-1 ender på toppen vn. Banens lengde - antall buer som utgjør banen, i dette tilfellet er banelengden NS - 1 ... Som et spesielt tilfelle av en sti, vurder ett toppunkt v som en bane med lengde 0 fra toppunktet vTil samme toppen v... På figuren danner sekvensen av toppunktene 1, 2, 4 en bane med lengde 2 fra toppunkt 1 til toppunkt 4.

Stien heter enkel , hvis alle toppunktene på den, med mulig unntak av den første og den siste, er forskjellige. Syklus - det er en enkel bane med lengde minst 1 som starter og slutter ved samme toppunkt. På figuren danner toppunktene 3, 2, 4, 3 en syklus med lengde 3.

I mange applikasjoner er det praktisk å legge ved noe informasjon til toppunktene og buene til en digraf. For disse formålene brukes den merket digraph , det vil si en digraf der hver bue og/eller hvert toppunkt har tilsvarende etiketter. Etiketten kan være et navn, vekt eller verdi (av buer), eller en dataverdi av en gitt type.

Eksempel 2 på en merket digraf:

DIV_ADBLOCK149 ">

3. Transitiv lukkingsalgoritme (Warshalls algoritme):

For grafen G = (V, E) Algoritmen beregner transitivitetsmatrisen T, hvorav hvert element T[Jeg, j] = 1 bare når det er en sti fra toppen Jeg til toppen j og T[ Jeg, j] = 0 ellers.

4. Algoritme for å finne midten av en digraf:

La være og - vilkårlig toppunkt av en digraf G = (V, E). Eksentrisitet (maksimal fjerning) topper og definert som

maks (minimum banelengde fra toppen w til toppen v }

w V

Digraph sentrum G toppunktet med minimum eksentrisitet kalles. Med andre ord, sentrum av digrafen er toppunktet der maksimal avstand (banelengde) til andre toppunkter er minimal.

Eksempel: Sentrum av digrafen er toppunktet d

		Eksentr-t

5. Algoritme for å krysse digrafen i dybden (dybde-første søk):

Når du løser mange problemer knyttet til rettede grafer, kreves det en effektiv metode for systematisk kryssing av toppunkter og buer av digrafer. Denne metoden er den såkalte dybde-første søk - generalisering av preorder-tre-traversalmetoden. Dybdesøk starter ved å velge startpunkt v telle G, dette toppunktet er merket med en etikett besøkt (besøkt). Deretter for hvert toppunkt ved siden av toppunktet v og som ikke har vært besøkt før, brukes dybde-først-søk rekursivt. Når alle toppene som kan nås fra toppen v, vil bli «hedret» med et besøk, avsluttes søket. Hvis noen toppunkter ikke er besøkt, velges en av dem og søket gjentas. Denne prosessen fortsetter til alle toppunktene til digrafen er krysset G.

6. Algoritme for å konstruere et dyptspennende tre i en graf:

Når du krysser en graf ved å bruke dybde-først-søk, fører bare visse buer til ubesøkte hjørner. Slike buer som fører til nye hjørner kalles trebuer og form for grafen dybde-først spennende skog – dyptgående skog ... Når man bygger en skog, skilles det også mellom tre typer buer: omvendt, direkte og tverrgående. Omvendte buer - slike buer som går fra etterkommere til forfedre i spennskogen. Rette buer buer kalles som går fra forfedre til sanne etterkommere, men som ikke er trebuer.

Buer som forbinder hjørner som verken er forfedre eller etterkommere av hverandre kalles tverrgående buer ... Hvis sønnene til det ene toppunktet er plassert fra venstre til høyre i rekkefølgen de besøker, og hvis nye trær legges til skogen også fra venstre mot høyre, går alle tverrbuer fra høyre til venstre når de bygger et spenntre. .

For eksempel buer D-> C og G-> D- tverrgående, bue C-> EN- bakover, det er ingen rette buer.

Når du krysser et tre dypt, er det ofte praktisk å nummerere toppunktene i den rekkefølgen de besøkes. Slike tall kalles dybdetall.

Digrafrepresentasjon:

§ Representasjon av en digraf ved bruk av en tilstøtende matrise:

Adjacency matrise for digraph G - dette er en matrise EN størrelsen n n med boolske verdier, hvor EN[ Jeg, j] = ekte hvis og bare hvis det er en bue fra toppunktet Jeg til toppunktet j. Ofte i tilstøtende matriser, verdien ekte erstattes med 1, og verdien falsk- til 0.

En generalisering av representasjonen av en digraf ved bruk av en tilstøtende matrise kan betraktes som en representasjon av en merket digraf som også bruker en tilstøtende matrise, men for hvilken elementet EN[ Jeg, j] lik bueetikett jeg ->j. Hvis buer fra toppen Jeg til toppen j ikke eksisterer, da verdien A [ Jeg, j] kan ikke være verdien av noen gyldig etikett, men kan betraktes som en "tom" celle.

Adjacency-matrise for en merket digraf (eksempel 2):

§ Representasjon av en digraf ved bruk av tilstøtende lister:

Vertex tilstøtningsliste Jeg kalt listen over alle toppunktene ved siden av toppunktet Jeg, dessuten bestilt på en bestemt måte. Digraph G kan representeres ved hjelp av en matrise HODE(Tittel) hvis element HODE[Jeg] er en peker til listen over toppunktsadjacency Jeg.

Operatører av ATD "Orgraph":

De vanligste operatørene som utføres på rettet grafer inkluderer lesende toppunkt- og bueetiketter, innsetting og sletting av toppunkt og bue og traversering av buesekvens.

For å se et sett med tilstøtende hjørner, kreves følgende tre operatorer.

1. FØRST ( v) returnerer indeksen til det første toppunktet ved siden av toppunktet v. Hvis toppen v har ingen tilstøtende toppunkter, så returneres et "null" toppunkt null.

2. NESTE ( v, Jeg) returnerer indeksen til toppunktet ved siden av toppunktet v, følge indeksen Jeg. Hvis Jeg - dette er indeksen til det siste toppunktet ved siden av toppunktet v, så kommer den tilbake null.

3. VERTEX ( v,Jeg) returnerer toppen med indeks Jeg fra settet med hjørner ved siden av v.

Øvelser:

Gitt en rettet graf (digraf):

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

Et eksempel på en frakoblet graf:

Syklus (enkel) er en bane med (enkel) lengde på minst 3 fra et hvilket som helst toppunkt til seg selv. Grafen kalles syklisk , hvis den har minst én syklus. En tilkoblet asyklisk graf, som er et "tre uten rot", kalles gratis tre . Den andre figuren over viser en graf som består av to sammenkoblede komponenter, som hver er et fritt tre. Et fritt tre kan gjøres til et "vanlig" tre hvis noen toppunkt er utpekt som en rot, og alle kanter er orientert i retning fra denne roten.

Løse trær har to viktige egenskaper:

1. Hvert ledig tre med antall topper n, n > 1 , har akkurat n - 1 ribbeina.

2. Hvis du legger til en ny kant til et ledig tre, vil du definitivt få en syklus.

La være G = (V, E) - koblet graf der hver kant ( r, w) merket med et tall med(v, w), som kalles kostnaden for en fordel . Spennende tre telle G kalt et fritt tre som inneholder alle toppunkter V Greve G. Pris spenntreet beregnes som summen av kostnadene for alle kanter inkludert i dette treet

Grunnleggende algoritmer for behandling av urettede grafer:

1. Minimumskostnad som strekker seg over trekonstruksjon (Prims algoritme):

Mange topper bygges U hvorfra det spennede treet "vokser". La være V = (1, 2, ...,n}. Først U = (1). Ved hvert trinn i algoritmen finner man en fordel med lavest mulig kostnad ( u, v) slik at u U og v V \ U deretter toppen v er overført fra settet V \ U i en mengde U... Denne prosessen fortsetter til settet U vil ikke være lik settet V.

Den spennvidde konstruksjonssekvensen er gitt nedenfor.

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

3. DFS-gjennomgang av urettede grafer:

Dybde-først-søk brukes til å systematisk krysse alle toppunktene i grafen. Dybde-først-søkealgoritmen ligner på algoritmen for å krysse toppunktene til en digraf. Sistnevnte brukes også for urettede grafer, siden den urettede kanten (v, w) kan representeres som et par orienterte buer v -> w og w -> v.

Dybdetraversering kan brukes til å bygge et spenntre.

Grafen og spenntreet oppnådd ved å krysse hjørnene ved hjelp av dybde-først-søkemetoden er vist nedenfor:

4. Breadth First Søk etter urettede grafer

En annen metode for systematisk å krysse toppunktene til en graf kalles Bredde først søk . Det fikk navnet sitt på grunn av det faktum at når du når under kryssingen av ethvert toppunkt v videre tar vi for oss alle toppunktene ved siden av toppunktet v, det vil si at toppunktene skannes "i bredden". Denne teknikken kan også brukes på rettet grafer.

Akkurat som med dybde-først-søk, skaper BFS en spennskog når du krysser en graf. Hvis etter å ha nådd toppen NS når man vurderer ribben (x, y) toppunkt på ikke har vært besøkt før, så regnes denne kanten som kanten på treet. Hvis toppen på har allerede blitt besøkt, ribba (x, y) vil være en tverrkant, siden den forbinder hjørner som ikke er knyttet til hverandre ved arv.

Breadth First Spanning Tree er vist nedenfor.

Representasjon av en urettet graf ved bruk av en tilstøtende matrise:

For å representere urettede grafer, kan du bruke de samme metodene som for å representere rettede grafer, hvis den urettede kanten mellom toppunktene v og w sett som to orienterte buer fra toppunktet v til topp w og fra toppen w til toppen v.

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

Representerer en urettet graf ved bruk av tilstøtende lister:

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

1. Bygg:

minimumskostnad som strekker seg over treet ved hjelp av Prims algoritme;

minimumskostnad som strekker seg over tre ved bruk av Kruskals algoritme;

spenner over tre etter dybde-første søk, med start fra toppunktene a og d;

spenner over tre etter bredde-første søk, med start fra toppunktene a og d.

2. Implementer Prim og Kruskal sine algoritmer.

3. Implementer å bygge et spenntre ved å bruke dybde-først-søk

§ for en urettet graf representert av en tilstøtende matrise,

§ for urettet graf representert av tilstøtende lister.

4. Implementer spannende trekonstruksjon ved å bruke bredde-først-søk

§ for en urettet graf representert av en tilstøtende matrise,

§ for urettet graf representert av tilstøtende lister.

Den russiske føderasjonens departement for utdanning og vitenskap

Federal State Budgetary Education Institution

høyere profesjonsutdanning

NATIONAL RESEARCH atomar UNIVERSITY "MEPHI"

Dimitrovgrad Engineering Technological Institute

Avdeling Informasjonsteknologi

Å innrømme beskyttelse "" 2012

Hode stol Rakova O.A.

Kursarbeid

ved disiplin"Objektorientert programmering"

Tema:"Abstrakte datatyper. Lister"

Fullført: student gr. VT-31

Shayakov A.F.

Leder: Art. Foreleser ved IT-avdelingen

Alenin V.A.

Normkontroller: Art. Foreleser ved IT-avdelingen

Alenin V.A.

Karakter:

Beskyttelsesdato:

Dimitrovgrad, 2012

Den russiske føderasjonens departement for utdanning og vitenskap

Federal State Budgetary Education Institution

høyere profesjonsutdanning

NATIONAL RESEARCH atomar UNIVERSITY "MEPHI"

Dimitrovgrad Engineering Technological Institute

for semesteroppgave

Disiplin: Objektorientert programmering

Emne: Abstrakte datatyper. Lister

Kunstner: Shayakov A.F.

Leder: Alenin V.A.

1. Teoretisk del:

Abstrakte datatyper. Objektorientert programmeringskonsept. Lineære enkeltlenkede lister.

2.Praktisk del:

I C ++, skriv et program med en objektorientert struktur for å implementere lineære enkeltlenkede lister.

Vilkår for ferdigstillelse av arbeid etter planen:

Teoretisk del - 15 % innen uke 5

Praktisk del - 80 % innen uke 7

Eksperimentell del - ____% innen ____ uke

Beskyttelse - 100 % innen uke 10

Krav for registrering:

Oppgjøret og forklarende notat til semesteroppgaven skal leveres elektronisk og papirutgaver;

Rapportens volum skal være på minst 20 maskinskrevne sider eksklusiv vedlegg

RPZ er signert av den som er ansvarlig for reguleringskontrollen

Arbeidsleder _________________

Entreprenør ____________________

Utstedelsesdato "_____" ___________ 2012

A.F. SHAYAKOV TEMA: ABSTRAKTE DATATYPER. LISTER, Coursework / DITI, nr. 230105.65-Dimitrovgrad, 2012. - 29 sider, fig. 11, bibl. Navn 10, vedlegg 1.

Stikkord: lineære enkeltlenkede lister, C ++, objektorientert programmering.

Forskningsobjektet er lineære enkeltlenkede lister.

Hensikten med arbeidet er å studere lineære enkeltlenkede lister og skrive et program i C++ med en objektorientert struktur for deres implementering.

Konklusjoner: i dette arbeidet har vi fullt ut studert lineære enkeltlenkede lister, så vel som metodene for deres representasjon i minnet. Programmet skrevet på C++-språket samsvarer fullt ut med den objektorienterte strukturen, oppfyller sin hovedoppgave korrekt og effektivt - det implementerer lineære enkeltlenkede lister.

Innledning 6

1 Teoretisk del 7

1.1 Abstrakte datatyper. Lineære lister 7

1.2 Konsept for objektorientert programmering 8

2 Praktisk del 15

3 Testing 23

Konklusjon 25

Referanser 26

Vedlegg A 27

Introduksjon

Ofte, i prosessen med å jobbe med data, er det umulig å bestemme hvor mye minne som kreves for å lagre dem; minne bør tildeles under programkjøring etter behov i separate blokker. Blokker er knyttet til hverandre ved hjelp av pekere. Denne måten å organisere data på kalles en dynamisk datastruktur fordi den ligger i haug og endrer størrelse under programkjøring.

Lineære lister brukes i dette arbeidet fra dynamiske strukturer. En dynamisk struktur, i motsetning til en matrise eller post, kan okkupere ikke-sammenhengende områder av RAM.

Dynamiske strukturer er også mye brukt for mer effektivt arbeid med data, hvis størrelse er kjent, spesielt for å løse sorteringsproblemer.

Et element i enhver dynamisk struktur består av to deler: informasjon, for lagrings skyld strukturen er opprettet, og pekere, som sikrer koblingen av elementer med hverandre.

1. Teoretisk del

1.1 Abstrakte datatyper. Lineære lister

Abstrakte datatyper er nøkkelen i programmering. Abstraksjon innebærer separasjon og uavhengig vurdering av grensesnitt og implementering.

Dataabstraksjon innebærer definisjon og vurdering av abstrakte datatyper (ADT) eller, tilsvarende, nye datatyper lagt inn av brukeren.

En abstrakt datatype er en samling av data sammen med en rekke operasjoner som kan utføres på disse dataene.

Lineære lister

I en lineær liste er hvert element relatert til den neste, og muligens til den forrige. I det første tilfellet kalles listen ganske enkelt koblet, i det andre - dobbeltkoblet. Hvis det siste elementet er koblet med en peker til det første, er resultatet en sirkulær liste.

Hvert element i listen inneholder en nøkkel som identifiserer det elementet. Nøkkelen er vanligvis enten et heltall eller en streng og er en del av datafeltet. Ulike deler av datafeltet kan fungere som en nøkkel i arbeidet med listen. Nøklene til ulike elementer i listen kan være de samme.

Du kan utføre følgende operasjoner på lister:

innledende dannelse av listen (oppretting av det første elementet);

legge til et element på slutten av listen;

lese et element med en gitt nøkkel;

å sette inn et element på et gitt sted i listen (før eller etter et element med en gitt nøkkel);

slette et element med en gitt nøkkel;

rekkefølge listen etter nøkkel.

For å jobbe med en liste i et program, må du definere en peker til begynnelsen. Du kan også føre pekeren til slutten av listen for å gjøre det enklere å legge til nye elementer på slutten av listen.

1.2 Konsept for objektorientert programmering

I følge Grady Booch, en autoritet på objektorienterte programmeringsmetoder, "er objektorientert programmering (OOP) en programmeringsmetodikk som er basert på å representere et program som en samling av objekter, som hver er en implementering av en bestemt klasse ( type av en spesiell type), og klassene danner et hierarki basert på prinsippene for arv."

Objektorientert metodikk, i likhet med strukturell metodikk, ble laget med sikte på å disiplinere prosessen med å utvikle store programvarepakker og derved redusere kompleksiteten og kostnadene.

En objektorientert metodikk forfølger de samme målene som en strukturert metodikk, men den adresserer dem fra et annet utgangspunkt og lar deg i de fleste tilfeller administrere mer komplekse prosjekter enn en strukturert metodikk.

Som du vet, er et av prinsippene for prosjektkompleksitetsstyring dekomponering. Grady Booch skiller mellom to typer dekomponering: algoritmisk (som han kaller dekomponering støttet av strukturelle metoder) og objektorientert, forskjellen mellom disse, etter hans mening, er som følger: spesiell betydning for faktorer som enten forårsaker handlinger eller er objektene. for anvendelse av disse handlingene”.

Algoritmisk dekomponering tar med andre ord mer hensyn til strukturen av relasjoner mellom deler av et komplekst problem, mens objektorientert dekomponering fokuserer mer på relasjonenes natur.

I praksis anbefales det å bruke begge typer dekomponering: når du lager store prosjekter, anbefales det først å bruke en objektorientert tilnærming for å lage et generelt hierarki av objekter som gjenspeiler essensen av den programmerte oppgaven, og deretter bruke algoritmisk dekomponering inn i moduler for å forenkle utvikling og vedlikehold av programvarepakken.

OO-programmering er utvilsomt et av de mest interessante områdene for profesjonell programvareutvikling.

Objekter og klasser

De grunnleggende byggesteinene i et objektorientert program er objekter og klasser. I hovedsak kan et objekt representeres som noe følt eller forestilt og har en veldefinert atferd. Dermed kan et objekt enten sees eller berøres, eller i det minste vite at det for eksempel er representert som informasjon lagret i datamaskinens minne. La oss gi definisjonen av et objekt, og følge oppfatningen til GradiBuch: "Et objekt er en håndgripelig enhet som tydelig manifesterer sin oppførsel."

Et objekt er en del av virkeligheten som omgir oss, det vil si at det eksisterer i tid og rom (for første gang ble konseptet om et objekt i programmering introdusert på Simula-språket). Formelt sett er objektet ganske vanskelig å definere. Dette kan gjøres gjennom noen egenskaper, nemlig: et objekt har tilstand, atferd og kan identifiseres unikt (med andre ord har et unikt navn).

En klasse er et sett med objekter som har en felles struktur og felles oppførsel. En klasse er en beskrivelse (abstraksjon) som viser hvordan man konstruerer en variabel av denne klassen som eksisterer i tid og rom, kalt et objekt. Betydningen av setningene "beskrivelse av klassevariabler" og "beskrivelse av klasseobjekter" er den samme.

Objektet har en tilstand, oppførsel og pass (midler for sin unike identifikasjon); strukturen og oppførselen til objekter er beskrevet i klassene de er variabler av.

La oss nå definere begrepene tilstand, atferd og identifikasjon av et objekt.

Tilstanden til et objekt kombinerer alle dets datafelt (statisk komponent, dvs. uforandret) og gjeldende verdier for hvert av disse feltene (dynamisk komponent, dvs. endres vanligvis).

Atferd uttrykker dynamikken til endringer i tilstandene til et objekt og dets reaksjon på innkommende meldinger, dvs. hvordan et objekt endrer sine tilstander og samhandler med andre objekter.

Identifikasjon (gjenkjenning) av et objekt er en egenskap som lar deg skille et objekt fra andre objekter av samme eller forskjellige klasser. Identifikasjon utføres ved hjelp av et unikt navn (pass), som tildeles objektet i programmet, akkurat som enhver annen variabel.

Det har allerede blitt sagt ovenfor at den prosedyremessige (så vel som modulære) tilnærmingen lar deg bygge programmer som består av et sett med prosedyrer (subrutiner) som implementerer de gitte algoritmene. På den annen side representerer den objektorienterte tilnærmingen programmer som en samling av objekter som samhandler med hverandre. Samspillet mellom objekter utføres gjennom meldinger. La oss anta at objektet vårt er en sirkel. Da kan meldingen som sendes til dette objektet være: "tegn deg selv." Når vi sier at en melding sendes til et objekt, så kaller vi faktisk en funksjon til dette objektet (komponent-funksjon). Så i eksemplet ovenfor vil vi kalle en funksjon som vil tegne en sirkel på skjermen.

Innkapsling

Innkapsling er et av de grunnleggende prinsippene for objektorientert programmering, ideen om det er at alle egenskaper og metoder er kombinert i et objekt.

Selve navnet på begrepet «encapsulation» kommer fra det engelske ordet encapsulate, som bokstavelig talt betyr «å forsegle i en kapsel» eller «å dekke med et skall». Dermed inneholder et objekt (kapsel) metoder og egenskaper (innhold).

Innkapsling kan sees i en bredere forstand, langt utover objektorientert programmering generelt. Hvis vi snakker om innkapsling på høyest mulig abstraksjonsnivå, kan innkapsling betraktes som evnen til et objekt til å inneholde en rekke andre objekter. Så i forhold til et dataprogram kan vi si at det kapsler inn flere moduler, som hver i sin tur kapsler inn noen objekter som kapsler inn metoder og egenskaper, som forresten også kan være objekter, og så videre.

Basert på alt det ovennevnte, kan en annen representasjon av innkapsling være en hvilken som helst trestruktur der en hvilken som helst node på treet innkapsler alle sine nærmeste barn, som enten kan være blader (primitiver som ikke kan kapsle inn noe i seg selv) eller andre noder.

Og likevel, hvis vi snakker om objektorientert programmering, så er innkapsling foreningen av data og metoder i et objekt.

Noen ganger når vi snakker om innkapsling i objektorientert programmering, blir begrepet innkapsling likestilt med konseptet "black box" eller dataskjuling, men de er ikke det samme. Ja, i noen objektorienterte programmeringsspråk, ved hjelp av innkapsling, kan utvikleren gjøre objektet sitt til en svart boks, men dette implementeres ved hjelp av tilgangsmodifikatorer, som ikke er tilgjengelige i alle objektorienterte programmeringsspråk. Selve konseptet med innkapsling er mye bredere. Og enda mer enn det, vi kan gjøre alle egenskapene og metodene tilgjengelige utenfra, det vil si at det ikke kan være snakk om noen svart boks, men innkapsling vil fortsatt være tilstede i ethvert objekt. Derfor er det å skjule data ved hjelp av tilgangsmodifikatorer en konsekvens av innkapsling, men er på ingen måte identiske like konsepter.

For det første, takket være innkapsling, er objekter ikke lenger bare brukerdefinerte datastrukturer, hvis hovedformål ganske enkelt er å være logisk å kombinere flere separate datatyper innenfor rammen av en ny sammensatt datatype. Takket være innkapsling kan hvert objekt nå inneholde data som beskriver objektets tilstand, og dets oppførsel, beskrevet i form av metoder. Med andre ord, et objekt i objektorientert programmering har sluttet å være en primitiv passiv datatype, hvis kontroll er fullstendig prisgitt det ytre miljøet, men begynte å ha sin egen oppførsel, man kan til og med si at noen vil og sinn, evnen til å reagere aktivt på ytre påvirkninger og endre sin tilstand, og i henhold til sine egne lover og forskrifter.

For det andre gir innkapsling oss muligheten til å kontrollere tilgang til objektdata. Synlighetsbegrensning kan også sees på som en manifestasjon av objektets egen vilje - objektet bestemmer selv hva av dets oppførsel eller egenskaper som skal gjøres tilgjengelig for alle, hva som skal gjøres tilgjengelig kun for en viss rekke objekter, og hva som skal gjøres helt intimt, som den ikke vil vite noe annet objekt om. Hvorfor, men fordi bare objektet selv vet nøyaktig hvordan det skal jobbes med det og hvordan ikke. Du kan til og med si om en ny filosofi om programmering, der objekter er mer på objekter som noen handlinger utføres på, og, hvis jeg kan si det, en ny form for abstrakt syntetisk sinn, som samhandler som du kan oppnå ønsket resultat.

Og jeg gjentar nok en gang at det er takket være innkapsling at et objekt kan gis en eller annen vilje, fornuft, evnen til å reagere på ytre påvirkninger, og ikke være et passivt datalager.

Arv

Arv er en av de fire viktigste mekanismene for objektorientert programmering (sammen med innkapsling, polymorfisme og abstraksjon), som lar deg beskrive en ny klasse basert på en eksisterende (overordnet) klasse, mens egenskapene og funksjonaliteten til overordnet klasse er lånt av den nye klassen.

Med andre ord implementerer den arvende klassen spesifikasjonen til en allerede eksisterende klasse (basisklasse). Dette lar deg behandle objekter av den avledede klassen på samme måte som med objekter i basisklassen.

Arvetyper

Enkel arv

Klassen som arven kom fra kalles base eller parent (engelsk baseclass). Klasser som er avledet fra basen kalles avledet klasse.

Noen språk bruker abstrakte klasser. En abstrakt klasse er en klasse som inneholder minst én abstrakt metode, den er beskrevet i programmet, har felt, metoder og kan ikke brukes til å lage et objekt direkte. Det vil si at du bare kan arve fra en abstrakt klasse. Objekter lages kun på grunnlag av avledede klasser som er arvet fra abstraktet.

For eksempel kan en abstrakt klasse være grunnklassen "universitetsansatt", som klassene "graduate student", "professor" etc. er arvet fra. Siden avledede klasser har felles felt og funksjoner (for eksempel feltet "year". av fødsel"), kan disse klassemedlemmene beskrives i basisklassen. Programmet lager objekter basert på klassene "graduate student", "professor", men det er ingen vits i å lage et objekt basert på klassen "universitetsansatt".

Multippel arv

Med multippel arv kan en klasse ha mer enn én stamfar. I dette tilfellet arver klassen metodene til alle forfedre. Fordelen med denne tilnærmingen er større fleksibilitet. Multippel arv er implementert i C ++. Andre språk som gir denne muligheten inkluderer Python og Eiffel. Multippel arv støttes i UML.

Multippel arv er en potensiell kilde til feil som kan oppstå på grunn av tilstedeværelsen av de samme metodenavnene i forfedre. På språk som er posisjonert som arvere av C ++ (Java, C #, etc.), ble det besluttet å forlate multippel arv til fordel for grensesnitt. Du kan nesten alltid klare deg uten å bruke denne mekanismen. Men hvis et slikt behov likevel oppsto, for å løse konflikter med å bruke nedarvede metoder med samme navn, er det for eksempel mulig å bruke synlighetsutvidelsesoperasjonen - "::" - å kalle en spesifikk metode for en spesifikk forelder.

Et forsøk på å løse problemet med tilstedeværelsen av de samme metodenavnene i forfedre ble utført på Eiffel-språket, der det, når man beskriver en ny klasse, er nødvendig å eksplisitt indikere de importerte medlemmene av hver av de arvede klassene og deres navn. i barneklassen.

De fleste moderne objektorienterte programmeringsspråk (C #, C ++, Java, Delphi, etc.) støtter muligheten til samtidig å arve fra en stamfarklasse og implementere metoder for flere grensesnitt med samme klasse. Denne mekanismen lar deg i stor grad erstatte flere arv - grensesnittmetoder må overstyres eksplisitt, noe som eliminerer feil når du arver funksjonaliteten til de samme metodene til forskjellige stamfarklasser.

1. Praktisk del

For å løse dette problemet brukes en objektorientert programstruktur. Programmet er representert av to klasser og en hoved-cpp-fil som inneholder et brukergrensesnitt for å gjøre det lettere å jobbe med lister.

cList-klassen er en lineær, enkeltlenket liste over objekter i cElement-klassen.

cElement-klassen har følgende struktur:

clement * neste;

~ cElement (tomt);

void setdata (int);

void setref (cElement *);

cElement * getref ();

Datafeltet av typen int inneholder den numeriske verdien til listeelementet, det neste feltet av typen cElement * inneholder en lenke til neste element i listen. Setdata- og getdata-metodene brukes for å få tilgang til det private datafeltet til klassen for å få og følgelig angi verdien av dette feltet. Setref-metoden brukes til å sette en kobling fra gjeldende til neste element i listen, og getref brukes til å navigere til neste element.

void cElement :: setdata (int sd)

int cElement :: getdata ()

returnthis-> data;

void cElement :: setref (cElement * rf)

cElement * cElement :: getref ()

returnthis-> neste;

Implementeringen av disse metodene er ekstremt enkel, som man kan se fra programkodene presentert ovenfor.

La oss nå se på strukturen til cList-klassen

#include "cElement.h"

clement * hode;

void Legg til (int);

void Sett inn (int, int);

void Fjern (int);

void RemoveAll ();

Denne klassen inneholder en lenke til hodeelementet i listen - hode, av typen cElement *. Lagring av denne koblingen er nødvendig for riktig utførelse av operasjoner for å legge til, slette data og skrive ut listen. Faktum er at når du utfører noen av de ovennevnte operasjonene, gjentas listeelementene for å komme til ønsket, siden listen ikke har tilfeldig tilgang til elementene, så det er mer rasjonelt å starte opptellingen fra "hodet " på listen. I tillegg til å referere til begynnelsen av listen, vil hvert objekt i denne klassen ha et elcount-felt som inneholder antall elementer i listen.

La oss fortsette vår vurdering av denne klassen ved å undersøke metodene som er implementert i den for å jobbe med lister.

Legg til metode - legger til data på slutten av listen.

Som en parameter godtar denne metoden en numerisk verdi (variabel xd), som må lagres i det tilføyde listeelementet.

void cList :: Legg til (int xd)

Dette er hvordan et nytt element opprettes og verdien av dets numeriske felt settes:

cElement * temp = newcElement;

temp-> settdata (xd);

Etter det blir antall elementer i listen sjekket, hvis listen er tom, opprettes hodeelementet, ellers den "vanlige" komponenten i listen:

if (elcount == 0)

temp-> setref (NULL);

temp-> setref (NULL);

p-> setref (temp);

Du kan legge merke til at i konstruksjonen ovenfor brukes setref-metoden til cElement-klassen, som er nødvendig for å sette en lenke til neste element i listen, ellers vil listen være ubundet, noe som er full av datatap og feil program operasjon.

Ved første start av programmet brukes metoden beskrevet ovenfor for å legge til elementer i listen sekvensielt, som du deretter kan jobbe med; for å stoppe inndata på kommandolinjen, må du angi "stopp"-kommandoen i stedet for den numeriske verdien av varen (se figur 1).

Figur 1 - Prosessen med å legge til elementer i listen

Etter å ha lagt inn "stopp"-kommandoen, skrives listen ut og programmet går inn i kommandoventemodus (se figur 2).

Figur 2 - Utskrevet liste

Utskriftsmetode - skriver ut listen.

For utskrift er det viktig å kjenne til begynnelsen av listen for å konsekvent skrive ut verdiene til alle elementene i listen, så en lenke til "hodet" på listen settes i temp-variabelen, hvoretter faktum om eksistensen av listen er sjekket og den tilsvarende meldingen vises, hvis den ikke er bekreftet, hvis listen ikke er tom, vises den:

void cList :: Skriv ut ()

cElement * temp = hode;

hvis (temp == NULL) cout mens (temp! = NULL)

temp = temp-> getref ();

Del metode - sletting av startelementet i listen.

For å fjerne det første elementet, må du først overføre lenken til neste komponent i listen, gjøre den til den første på denne måten, og deretter slette det nødvendige elementet:

voidcList :: Del ()

cElement * temp = hode;

hode = hode-> getref ();

RemoveAll-metoden - fjerner hele listen.

Denne metoden er basert på ovenstående og består i å suksessivt slette de første elementene i listen til hele listen er slettet.

void cList :: RemoveAll ()

mens (elcount! = 0)

For å kjøre denne metoden, skriv inn "dellist"-kommandoen i menyen for arbeid med listen (se figur 3).

Figur 3 - Angi kommandoen for å tømme listen

Og hvis brukeren virkelig er trygg på handlingene sine, er det nødvendig å akseptere programmets tilbud, hvoretter hele listen vil bli slettet (se figur 4).

Figur 4 - Tom liste

Fjern metode - fjerner et spesifikt element fra listen.

Mindre radikal metode enn den forrige. Bare ett, spesifisert som en parameter, listeelement er fjernet. Det skjer som følger: programmet kontrollerer først riktigheten av den angitte parameteren, hvis nummeret på det slettede elementet er mindre enn ett eller flere enn det totale antallet elementer i listen, viser det en feilmelding, men hvis programmet har ingen klager på den angitte parameteren, blir de nødvendige koblingene til elementene som ligger i nærheten overført med den slettede, slik at listen forblir koblet, hvoretter det nødvendige elementet slettes.

void cList :: Fjern (int del)

cElement * cur = hode, * de;

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

hode = hode-> getref ();

mens (j! = del-1)

cur = cur-> getref ();

de = cur-> getref ();

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

coutsystem ("pause");

For å kjøre denne metoden, skriv inn "slett"-kommandoen i menyen for å jobbe med listen. Skriv deretter inn nummeret på elementet som skal slettes eller "tilbake"-kommandoen for å avbryte slettingen (se figur 5).

Figur 5 - Prosessen med å slette et listeelement

Listen etter fjerning av det fjerde elementet vil se slik ut (se figur 6).

Figur 6 - Liste etter sletting av ett element

Sett inn metode - setter inn et nytt element på et spesifisert sted i listen.

Denne metoden tar som parametere: posisjonen til det tilføyde elementet og dets numeriske verdi. Det nye elementet vil stå nøyaktig på det angitte stedet, og dermed vil elementene til høyre for det gjeldende bli forskjøvet med en posisjon. Når du legger til et nytt element i begynnelsen av listen, trenger du bare å overføre lenken fra dette elementet til det neste, og dermed koble listen og gi en lenke til det første elementet. En litt annen situasjon oppstår når du legger til et nytt element mellom to eksisterende, for dette, ved å bruke en løkke, gå til innsettingspunktet til elementet, og assosier deretter komponentene som ligger til høyre og venstre for det med det nye elementet. Tross alt, hva må for eksempel gjøres hvis det er nødvendig å forlenge kjeden: du må åpne den, deretter feste en ny lenke til den første delen av kjeden, fest den andre til samme lenke, noe lignende implementeres i denne metoden. Det er verdt å merke seg at hvis du angir en feil plassering for å legge til, som er mindre enn ett eller flere enn det totale antallet elementer, vil programmet vise en passende feilmelding.

void cList :: Sett inn (int pos, int val)

cElement * cur = hode;

cElement * temp = nytt cElement;

temp-> settdata (val);

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

temp-> setref (hode);

mens (j! = pos-1)

cur = cur-> getref ();

p = cur-> getref ();

cur-> setref (temp);

temp-> setref (p);

coutsystem ("pause");

For å kjøre denne metoden, skriv inn kommandoen "sett inn" i menyen for å jobbe med listen. Angi deretter posisjonen og den numeriske verdien til elementet som er lagt til eller "tilbake"-kommandoen for å avbryte slettingen (se figur 7).

Figur 7 - Prosessen med å sette inn et element

Etter å ha lagt til et element med en verdi på 111 til den tredje posisjonen, vil listen se slik ut (se figur 8).

Figur 8 - Liste etter å ha lagt til et element

I løpet av beskrivelsen ble menyen for å jobbe med listen nevnt mer enn en gang, det gjenstår å merke seg at denne menyen i stor grad letter arbeidet med listen. Algoritmen for arbeidet består i å syklisk kalle de samme metodene, skrive ut en liste, for eksempel, til en bestemt kommando er lagt inn. Listen over tilgjengelige kommandoer kan sees ved å skrive "hjelp" i konsollen (se figur 9)

Figur 9 - Tilgjengelige kommandoer

Den fullstendige menykoden er vist i vedlegg A.

1. Testing

Ofte i prosessen med arbeidet oppstår det situasjoner knyttet til feil datainntasting, noe som kan føre til at programmet mislykkes. Selvfølgelig må hvert program implementere beskyttelsesalgoritmer fra en uerfaren bruker, og forhindre at programmet krasjer. La oss vurdere hvordan slike algoritmer fungerer i det opprettede programmet.

Den første inntastingen av listen gjøres med følgende kode:

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

Før du kaller add-metoden for å legge til et nytt element i listen, sjekkes inndatastrengen. Atoi-funksjonen konverterer en streng til en numerisk verdi og returnerer NULL hvis inndatastrengen ikke er et tall. Når du skriver inn, vil alle linjer som ikke er tall bli ignorert, bortsett fra linjen med kommandoen for å stoppe inndata (se figur 10).

Figur 10 - Legge inn feil data

Etter å ha lagt inn slike data vil listen se slik ut (se figur 11).

Figur 11 - Mottatt liste

Programmet fortsetter å fungere korrekt etter, selv etter å ha lagt inn feilaktige data. Lignende metoder for å håndtere feil data brukes for resten av inndataoperasjonene i programmet.

Konklusjon

I dette arbeidet ble det innhentet konsepter om abstrakte datatyper, om prinsippene for deres representasjon i moderne programmeringsspråk, spesielt i C++. I de fleste moderne imperative språk er hovedkonseptet som brukes for å beskrive abstraksjoner i programkode den objektorienterte tilnærmingen. Objektorientert programmering (OOP), som den ADT-baserte programmeringsmetoden, er til en viss grad en utvikling av ideer om modulær programmering. Moduler er programkomponenter som har to viktige egenskaper:

Moduler skjuler implementeringsdetaljer.

Moduler kan gjenbrukes i ulike deler av programmet.

David Parnas presenterte i sitt arbeid fra 1972 moduler som abstrakte maskiner som lagrer tilstander i seg selv og tillater å endre denne tilstanden gjennom et spesifikt sett med operasjoner. Dette konseptet er grunnleggende, både for konseptet med abstrakte datatyper og for objektorientert programmering. Ved å trekke paralleller mellom arbeidet til Parnassus og moderne OOP-konsepter, er det lett å se forholdet mellom konseptene klasse og modul.

I dette arbeidet er lineære enkeltlenkede lister, som er en abstrakt datatype, representert av de utviklede modulene, for å få tilgang til tilstandene der spesielle operasjoner også er implementert, kalt metoder i objektorientert programmering.

Bibliografi

1. Ian Graham Objektorienterte metoder. Prinsipper og praksis = Objektorienterte metoder: Prinsipper og praksis. - 3. utg. - M .: "Williams", 2004. - S. 880.

2. Anthony Sintes Lær objektorientert programmering på 21 dager = Sams Lær deg selv objektorientert programmering på 21 dager. - M .: "Williams", 2002. - S. 672.

3. Bertrand Meyer Objektorientert design av programvaresystemer + CD. Internet University of Information Technologies - INTUIT.ru, russisk utgave, 2005

4. Billig V.A. Grunnleggende om programmering i C #. Internet University of Information Technologies - INTUIT.ru, 2006

5. "Nye programmeringsspråk og utviklingstendenser", V. Ushkova, 2005

6. Bjarne Stroustrup "The C ++ Programming Language" Spesialutgave eller 3. utg. Binom, Nevsky Dialect, ISBN 5-7989-0226-2, 5-7940-0064-3, 0-201-70073-5

7. Bjarne Stroustrup "Design og utvikling av C ++-språket". DMK-Press, Peter, ISBN 5-469-01217-4, 0-201-54330-3

8. Bjarne Stroustrup "Programmeringsprinsipper og praksis ved bruk av C ++". "ID Williams", 2011, ISBN 978-5-8459-1621-1 (russisk)

9. Grady Booch et al. "Object Oriented Analysis and Design with Sample Applications" 2. eller 3. utgave. Binom, Nevsky-dialekt, 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 "Using C ++ Effectively. 50 Best Practices for Improving Your Programs and Projects" DMK, Peter, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1

Vedlegg A

Menyprogramkode

#include "cList.h"

#include "string.h"

bruker navneområde std;

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

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

system ("cls");

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

coutmylist.Skriv ut ();

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

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

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

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

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

bytte (com_ind)

system ("cls");

system ("cls");

coutcoutcoutcoutcoutcoutcoutcoutcoutcom_ind = 0;

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

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

system ("cls");

// sette inn elementer

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

if (atoi (ss)! = NULL)

system ("cls");

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

if (atoi (ss)! = NULL)

mylist.Sett inn (pos, atoi (ss));

system ("cls");

// slett elementer

if (strstr (ss, "tilbake") == NULL) er definert av et sett med verdier gitt og et sett med operasjoner ... tilknyttede strukturer data – lister... Struktur data Er en samling av elementer data, mellom hvilke ... i datamaskinens minne kalles abstrakt eller logisk. Oftere...

Flere type data... Settene

Forelesning >> Informatikk, programmering

... type ligner på enkel typer data... Flertall typer er beskrevet i avsnitt typer... WU kan beskrives. Abstrakt beregningsstrukturer som beskriver input ... andre tilfeller typer alle komponenter liste må samsvare type filkomponenter. ...

Objektorienterte databaser data arbeider i distribuerte nettverk

Abstrakt >> Informatikk

Utvikle områder innen programmeringsspråk med abstrakt typer data og objektorienterte programmeringsspråk. ... typer data- liste og array. Hver bokstav er unikt identifisert av en indeks i matrisen og en ordinal in listen ...

Abstrakt informasjonssikkerhetsmodeller

Abstrakt >> Informatikk

Informasjonsbeskyttelse ……………………………………………… ..17 Abstrakt informasjonssikkerhetsmodeller ... styrer interaksjoner med begge typer data(Sertifiseringsregler): Alle ... ulike varianter og tillegg til eksisterende listen... Sikkerhetsnivåer - visse ...

Abstrakt datatype

Abstrakt datatype (ATD) er en datatype som gir et visst sett med funksjoner for å arbeide med elementer av denne typen, samt muligheten til å lage elementer av denne typen ved hjelp av spesialfunksjoner. Hele den interne strukturen av denne typen er skjult for programvareutvikleren - dette er essensen av abstraksjon. En abstrakt datatype definerer et sett med implementeringsuavhengige funksjoner for å manipulere verdiene. Spesifikke implementeringer av ADT-er kalles datastrukturer.

I programmering er abstrakte datatyper vanligvis representert som grensesnitt som skjuler de tilsvarende typeimplementeringene. Programmerere arbeider med abstrakte datatyper utelukkende gjennom grensesnittene, da implementeringen kan endre seg i fremtiden. Denne tilnærmingen er i samsvar med prinsippet om innkapsling i objektorientert programmering. Den sterke poenget med denne teknikken er implementeringsskjul. Når bare grensesnittet er publisert utenfor, så lenge datastrukturen støtter dette grensesnittet, vil alle programmer som jobber med den gitte strukturen til den abstrakte datatypen fortsette å fungere. Utviklerne av datastrukturer prøver, uten å endre det eksterne grensesnittet og semantikken til funksjoner, å gradvis avgrense implementeringene, forbedre algoritmene når det gjelder hastighet, pålitelighet og brukt minne.

Følgende eksempel illustrerer forskjellen mellom abstrakte datatyper og datastrukturer som implementerer abstrakte typer. Den abstrakte datatypelisten kan implementeres ved å bruke en matrise eller en lineær liste ved å bruke forskjellige dynamiske minneallokeringsmetoder. Imidlertid definerer hver implementering det samme settet med funksjoner som skal utføre det samme (i ytelse, ikke hastighet) for alle implementeringer.

Abstrakte datatyper lar deg oppnå modularitet av programvareprodukter og har flere alternative utskiftbare implementeringer av en separat modul.

Eksempler på ADT

se også

Lenker

• Lapshin V.A. Abstrakte datatyper i programmering

Wikimedia Foundation. 2010.

Se hva "Abstrakt datatype" er i andre ordbøker:

abstrakt datatype- En datatype (abstrakt klasse) definert ved å oppgi dens metoder og egenskaper, uten å skape deres konkrete implementering. Informasjonsteknologi-emner generelt EN Abstrakt datatypeADT ... Teknisk oversetterveiledning

I programmeringsteori, enhver type hvis verdier er verdier av noen andre typer, "pakket inn" av konstruktører av en algebraisk type. Med andre ord har en algebraisk datatype et sett med typekonstruktører, som hver ... ... Wikipedia

Heltall, heltallsdatatype (eng. Integer), i informatikk, en av de enkleste og vanligste datatypene i programmeringsspråk. Tjener til å representere heltall. Mange tall av denne typen representerer ... ... Wikipedia

Dette begrepet har andre betydninger, se sett (betydninger). Et sett, en type og datastruktur i informatikk, er en implementering av et matematisk objektsett. Datatypesett lar deg lagre et begrenset antall verdier ... ... Wikipedia

Noen programmeringsspråk gir en spesiell datatype for komplekse tall. Den innebygde typen gjør det enkelt å lagre og beregne komplekse verdier. Innhold 1 Aritmetikk over kompleks 2 Støtte på språk ... Wikipedia

Dette begrepet har andre betydninger, se Index . Pekerdiagram En peker (peker) er en variabel hvis verdiområde består av minneadresser og en spesiell verdi av nulladressen. ... ... Wikipedia

En av typene algebraiske datatyper, som er preget av det faktum at konstruktørene kan returnere verdier som ikke er av deres egen type. Dette konseptet er implementert i flere programmeringsspråk, spesielt i ML- og Haskell-språkene, og i ... ... Wikipedia

En egenskap er en abstrakt type som brukes i informatikk som "en enkel konseptuell modell for å strukturere objektorienterte programmer." Egenskaper ligner på mixins, men kan inkludere klassemetodedefinisjoner ... ... Wikipedia

Binært tre, et enkelt eksempel på en forgrenet tilkoblet datastruktur. Datastruktur er en programenhet som gjør det mulig å lagre ... Wikipedia

- (topptype) i typeteori, ofte betegnet som bare en topp eller et "fast" symbol (⊤), en universell type, det vil si en type som inneholder alle mulige objekter i det ønskede typesystemet. Den høyeste typen kalles noen ganger ... ... Wikipedia