Utviklingen av abstrakte modeller for data og hvordan man behandler disse dataene er en kritisk komponent i prosessen med å løse problemer med en datamaskin. Vi ser eksempler på dette både på et lavt nivå i hverdagsprogrammering (for eksempel ved bruk av arrays og koblede lister omtalt i), og på et høyt nivå ved løsning av anvendte problemer (som når man løser et tilkoblingsproblem ved å bruke en union-search-skog i "Introduksjon") ... Dette foredraget diskuterer abstrakte datatyper (heretter ADT), som lar deg lage programmer ved hjelp av abstraksjoner på høyt nivå. Abstrakte datatyper lar deg koble fra de abstrakte (konseptuelle) transformasjonene som programmer utfører på data fra en bestemt representasjon av en datastruktur eller en bestemt implementering av en algoritme.
Alle datasystemer er basert på abstraksjonsnivåer: visse fysiske egenskaper til silisium og andre materialer gjør at en abstrakt modell av en bit kan tas i bruk, som kan ta binære verdier 0-1; deretter bygges en abstrakt modell av maskinen på de dynamiske egenskapene til verdiene til et visst sett med biter; videre, på grunnlag av prinsippet om drift av en maskin under kontroll av et program i et maskinspråk, konstrueres en abstrakt modell av et programmeringsspråk; og til slutt konstrueres et abstrakt konsept av en algoritme, som implementeres som et program i C++-språket. Abstrakte datatyper gjør det mulig å fortsette denne prosessen videre og utvikle abstrakte mekanismer for visse beregningsproblemer på et høyere nivå enn det som tilbys av C++-systemet, utvikle abstrakte mekanismer orientert mot spesifikke applikasjoner og egnet for å løse problemer i en rekke applikasjonsområder, samt skape abstrakte mekanismer på høyere nivå som bruker disse grunnleggende konstruksjonene. Abstrakte datatyper gir oss et uendelig utvidbart sett med verktøy for å løse flere og flere nye problemer.
På den ene siden frigjør bruken av abstrakte konstruksjoner deg fra bekymringer om deres detaljerte implementering; på den annen side når opptreden programmet er viktig, du må vite kostnadene ved å utføre grunnleggende operasjoner. Vi bruker mange grunnleggende abstraksjoner innebygd maskinvare datamaskin og tjener som grunnlag for maskininstruksjoner; vi implementerer andre abstraksjoner i programvare; og bruke ekstra abstraksjoner levert av tidligere skrevet systemprogramvare. Abstrakt design på høyt nivå er ofte basert på enklere design. På alle nivåer fungerer det samme grunnleggende prinsippet: det er nødvendig å finne de viktigste operasjonene i programmer og de viktigste egenskapene til dataene, og deretter nøyaktig definere både på et abstrakt nivå og utvikle effektive konkrete mekanismer for implementeringen av dem. I denne forelesningen skal vi se på mange eksempler på anvendelsen av dette prinsippet.
For å utvikle et nytt abstraksjonsnivå, må du (1) definere de abstrakte objektene som må manipuleres og operasjonene som må utføres på dem; (2) representere data i en eller annen datastruktur og implementere operasjoner; (3) og (viktigst) for å sikre at disse objektene er praktiske å bruke for å løse brukte problemer. Disse punktene gjelder også for enkle datatyper, så de grunnleggende mekanismene for å støtte datatyper som ble diskutert i Elementary Data Structures kan tilpasses våre formål. Imidlertid tilbyr C ++-språket en viktig utvidelse av strukturmekanismen kalt en klasse. Klasser er ekstremt nyttige for å skape abstraksjonsnivåer og anses derfor som det primære verktøyet som brukes til dette formålet gjennom resten av denne boken.
Definisjon 4.1. En abstrakt datatype (ADT) er en datatype (et sett med verdier og et sett med operasjoner for disse verdiene) som kun er tilgjengelig via et grensesnitt. Et program som bruker en ADT vil bli kalt en klient, og et program som inneholder en spesifikasjon av denne datatypen kalles en implementering.
Det er ordet som bare gjør datatypen abstrakt: i tilfelle ADT har ikke klientprogrammer tilgang til dataverdier på noen annen måte, bortsett fra operasjonene beskrevet i grensesnittet. Presentasjonen av disse dataene og funksjonene som implementerer disse operasjonene er i implementering og er fullstendig atskilt av grensesnittet fra klienten. Vi sier at grensesnittet er ugjennomsiktig: klienten kan ikke se implementeringen gjennom grensesnittet.
I C++-programmer er dette skillet vanligvis gjort litt tydeligere, siden den enkleste måten å lage et grensesnitt på er å inkludere datapresentasjon men spesifiserer at klientprogrammer ikke har direkte tilgang til dataene. Med andre ord kan utviklere av klientprogramvare vite det datapresentasjon men kan ikke bruke det på noen måte.
Som et eksempel kan du vurdere datatypegrensesnittet for punkter (program 3.3) fra seksjon 3.1 "Elementære datastrukturer". Dette grensesnittet erklærer eksplisitt at punkter er representert som strukturer som består av et par med flytende kommatall, betegnet x og y. Denne bruken av datatyper er vanlig i store programvaresystemer: vi utvikler et sett med konvensjoner for presentasjon av data (og definerer også en rekke tilhørende operasjoner) og gjør disse reglene tilgjengelige gjennom et grensesnitt slik at de kan brukes av klientprogrammer som er en del av et stort system. Datatypen sikrer at alle deler av systemet er konsistente med representasjonen av de underliggende systemomfattende datastrukturene. Så god som denne strategien er, har den én feil: hvis du trenger å endre datapresentasjon, så må alle klientprogrammene endres. Program 3.3 gir oss igjen et enkelt eksempel: en av grunnene til å utvikle denne typen data er bekvemmeligheten av klientprogrammer med poeng, og vi forventer at klienter har tilgang til individuelle punktkoordinater når det er nødvendig. Men vi kan ikke flytte til en annen datarepresentasjon (si polare koordinater, eller 3D-koordinater, eller til og med forskjellige datatyper for individuelle koordinater) uten å endre alle klientprogrammer.
I motsetning til dette inneholder Program 4.1 en implementering av en abstrakt datatype som tilsvarer datatypen til Program 3.3, men bruker en C++-klasse som umiddelbart definerer både dataene og tilhørende operasjoner. Program 4.2 er et klientprogram som fungerer med denne datatypen. Disse to programmene utfører de samme beregningene som Program 3.3 og 3.8. De illustrerer noen av de grunnleggende egenskapene til klasser som vi nå skal se på.
Når vi skriver en definisjon som int i i et program, ber vi systemet om å reservere et minneområde for (innebygde) int-data, som kan nås med navnet i. I C ++-språket er det begrepet objekt for slike enheter. Når du skriver en definisjon som POINT p i et program, sies det at du lager et objekt av klassen POINT, som kan nås med navnet p. I vårt eksempel inneholder hvert objekt to dataelementer, kalt x og y. Som med strukturer, kan de refereres til med navn som p.y.
Datamedlemmene x og y kalles datamedlemmer i klassen. En klasse kan også definere medlemsfunksjoner som implementerer operasjonene knyttet til den datatypen. For eksempel har klassen definert i Program 4.1 to medlemsfunksjoner kalt POINT og distance.
Klientprogrammer, for eksempel Program 4.2, kan kalle medlemsfunksjoner knyttet til et objekt, og spesifisere navnene deres på samme måte som navnene på data som finnes i en struktur. For eksempel beregner uttrykket p.distance (q) avstanden mellom punktene p og q (den samme avstanden skal returneres ved å kalle q.distance (p)). POINT ()-funksjonen, den første i Program 4.1, er en spesiell medlemsfunksjon kalt en konstruktør: den har samme navn som en klasse og kalles når et objekt i den klassen må opprettes.
Program 4.1. POINT-klasseimplementering (prikk)
Denne klassen definerer en datatype som består av et sett med verdier som er "flytende punktpar" (antatt å bli tolket som punkter på det kartesiske planet), og to medlemsfunksjoner definert for alle forekomster av POINT-klassen: funksjon POINT (), som er en konstruktør som initialiserer koordinater til tilfeldige verdier fra 0 til 1, og en avstandsfunksjon (POINT) som beregner avstanden til et annet punkt. Datapresentasjon er privat, og bare medlemsfunksjoner kan få tilgang til eller endre det. Selve medlemsfunksjonene er offentlige og tilgjengelige for enhver klient. Koden kan for eksempel lagres i en fil som heter POINT .cxx.
#inkludere
Program 4.2. Klientprogram for klasse POINT (finner nærmeste punkt)
Denne versjonen av program 3.8 er en klient som bruker POINT ADT definert i program 4.3. Den nye operatøren oppretter en rekke POINT-objekter (ved å kalle POINT ()-konstruktøren for å initialisere hvert objekt med tilfeldige koordinater). Uttrykket a [i] .distance (a [j]) kaller på objekt a [i] avstandselementfunksjonen med argumentet a [j].
#inkludere
Å definere PUNKT p i klientprogrammet resulterer i allokering av et minneområde for et nytt objekt og deretter (ved å bruke PUNKT ()-funksjonen) til å tildele hver av de to dataelementene en tilfeldig verdi i området fra 0 til 1.
Denne programmeringsstilen, noen ganger referert til som objektorientert programmering, støttes fullt ut av C++-klassekonstruksjonen. En klasse kan betraktes som en utvidelse av strukturbegrepet, der ikke bare data kombineres, men også operasjoner med disse dataene er definert. Det kan være mange forskjellige objekter som tilhører samme klasse, men de er alle like ved at medlemsdataene deres kan ha det samme settet med verdier, og det samme settet med operasjoner kan utføres på disse medlemsdataene - generelt sett er de forekomster av samme datatype. I objektorientert programmering er objekter designet for å behandle medlemsdataene deres (i motsetning til å bruke uavhengige funksjoner for å behandle dataene som er lagret i objekter).
Vi ser på det lille klasseeksemplet beskrevet ovenfor bare for å bli kjent med de grunnleggende funksjonene til klasser; derfor er den langt fra komplett. I reell kode for poengklassen vil vi ha mye flere operasjoner. For eksempel har ikke Program 4.1 operasjoner som lar deg finne ut verdiene til x- og y-koordinatene. Som vi skal se, er det en ganske enkel oppgave å legge til disse og andre operasjoner. I del 5 skal vi se nærmere på klasser for punkt og andre geometriske abstraksjoner som linjer og polygoner.
I C ++ (men ikke C) kan strukturer også ha funksjoner knyttet til seg. Den viktigste forskjellen mellom klasser og strukturer har å gjøre med tilgang til informasjon, som er preget av nøkkelord.
God dag, Khabrav-beboere!
Følgende innlegg er et sammendrag av mine tanker om karakteren til klasser og ADTs. Disse refleksjonene er supplert med interessante sitater fra bøker av programvareutviklingsguruer.
Introduksjon
La oss starte med å nærme oss definisjonen av ADT. ADT er først og fremst en datatype, som betyr følgende: tilstedeværelsen av visse tilgjengelige operasjoner på elementer av denne typen;
samt dataene som disse operasjonene utføres på (verdiområde).
Hva betyr ordet "abstrakt"? Først og fremst betyr begrepet "abstrakthet" å fokusere på noe viktig, og samtidig må vi distrahere oss fra uviktige detaljer for øyeblikket. Definisjonen av abstrakthet er godt dekket i boken av Grady Booch. Definisjonen høres slik ut:
Abstraksjon er valg og formidling av et sett med objekter med felles egenskaper som definerer deres konseptuelle grenser og skiller dem fra alle andre typer objekter.
Med andre ord lar abstraksjon oss "kaste lys" på dataene til objekter vi trenger og samtidig "skyggelegge" de dataene som ikke er viktige for oss.
Så, hva skjer hvis du slår sammen begrepene "datatype" og "abstraksjon"? Vi vil få en datatype som gir oss et sett med operasjoner som sikrer atferden til objekter av denne datatypen, og denne datatypen vil også skjule dataene som denne atferden er implementert med. Derfor kommer vi til konseptet ADT:
En ADT er en datatype som skjuler sin interne implementering for klienter.
Overraskende, ved å bruke abstraksjon, lar ADT oss ikke tenke på implementeringsdetaljer på lavt nivå, men å jobbe med en enhet på høyt nivå i den virkelige verden (Steve McConnell).
Jeg tror at når du utvikler en ADT, må du først definere et grensesnitt, siden grensesnittet ikke skal være avhengig av den interne representasjonen av dataene i ADT. Etter å ha definert operasjonene som utgjør grensesnittet, må du fokusere på dataene som vil implementere den spesifiserte oppførselen til ADT. Som et resultat vil vi få en slags datastruktur – en mekanisme som lar deg lagre og behandle data. Samtidig er det fine med ADT at hvis vi ønsker å endre den interne representasjonen av dataene, trenger vi ikke å vandre gjennom hele programmet og endre hver linje med kode som avhenger av dataene vi ønsker å endring. ADT-en kapsler inn disse dataene, som lar deg endre oppførselen til objekter av denne typen, i stedet for hele programmet.
Fordeler med ATD
Bruken av ADT har mange fordeler (alle beskrevne fordeler finnes i boken av Steve McConnell "Code Perfect"):
- Innkapsling av implementeringsdetaljer.
Dette betyr at når vi kapsler inn detaljene om hvordan ADT fungerer, gir vi klienten et grensesnitt der han kan samhandle med ADT. Ved å endre implementeringsdetaljene vil ikke kundens oppfatning av ADT endres.
- Redusert kompleksitet.
Ved å abstrahere fra implementeringsdetaljer fokuserer vi på grensesnittet, som er hva ADT kan gjøre, snarere enn hvordan det gjøres. Dessuten lar ADT oss jobbe med essensen av den virkelige verden.
- Begrense omfanget av databruk.
Ved å bruke ADT kan vi være sikre på at dataene som representerer den interne strukturen til ADT ikke vil avhenge av andre deler av koden. Samtidig realiseres "uavhengigheten" til ADT.
- Høyt informasjonsinnhold i grensesnittet.
ADT lar deg representere hele grensesnittet når det gjelder domeneenheter, noe som du ser øker grensesnittets lesbarhet og informasjonsinnhold.
Steve McConnell anbefaler å representere datatyper på lavt nivå som stack eller list som ADT-er. Spør deg selv hva listen er. Hvis den presenterer en liste over bankansatte, så betrakt ATD som en liste over bankansatte.
Så vi fant ut hva en ADT er og kalte fordelene ved bruken. Nå er det verdt å merke seg at når du utvikler klasser i OOP, bør du først og fremst tenke på ADT. Samtidig, som Steve McConnell sa, programmerer du ikke på språket, men ved hjelp av språket. Det vil si at du vil programmere utenfor språket, ikke begrenset til tanker i form av arrays eller enkle datatyper. I stedet vil du tenke på et høyt abstraksjonsnivå (for eksempel i form av regneark eller medarbeiderlister). En klasse er ikke noe mer enn et tillegg og en måte å implementere ADT-konseptet på. Vi kan til og med representere klassen som en formel:
Klasse = ADT + arv + polymorfisme.
Så hvorfor skal man tenke på ADTs når man designer klasser. For det første må vi bestemme hvilke operasjoner som skal utgjøre grensesnittet til den fremtidige klassen, hvilke data som skal skjules og hvilke som skal gis offentlig tilgang. Vi må tenke på å gjøre grensesnittet svært informativt, enkelt å optimalisere og validere koden, og hvordan vi kan gi riktig abstraksjon slik at vi kan tenke på virkelige enheter i stedet for implementeringsdetaljer på lavt nivå. Jeg mener at det er etter definisjonen av ADT at vi bør tenke på spørsmålene om arv og polymorfisme.
Det er verdt å merke seg at konseptet ADT har funnet en bred anvendelse i OOP, fordi det er dette konseptet som utfyller OOP og lar deg redusere kompleksiteten til programmer i den raskt skiftende verden av programvarekrav.
Jeg skrev denne artikkelen for å trekke utviklernes oppmerksomhet til ADT for å forbedre kvaliteten på arbeidet og programvareutvikling.
Brukte kilder:
Steve McConnell - Code Perfect;
Robert Sedgwick - "Algorithms in Java".
Det er vanlig å kalle en abstrakt type en datatype som ikke er eksplisitt tilgjengelig i et programmeringsspråk; i denne forstand er dette konseptet relativt - en datatype som er fraværende i ett programmeringsspråk kan være tilstede i et annet.
Abstrakt datatype (ADT) bestemmes uavhengig av hvordan den implementeres:
settet med mulige verdier av denne typen,
og et sett med operasjoner på verdier av denne typen.
Bruken av ADT kan begrenses til stadiet av programvareutvikling, men for eksplisitt bruk i programmet må du ha implementeringen basert på de allerede eksisterende (og tidligere implementerte) datatypene i programmeringsspråket:
en måte å representere verdier av denne typen,
og implementering av operasjoner på verdier av denne typen.
ADT er ikke forhåndsdefinert i programmeringsspråket, og enda mer enn det, operasjonene for å konstruere slike typer, forhåndsdefinert i språket, skifter spørsmålet om hvordan man skal representere verdier av denne typen og hvordan man implementerer operasjoner med verdier av denne typen på utvikler-programmereren. Derfor, for slike datatyper, spørsmålet om valg av definisjoner og metoder for implementering av operasjoner av skjemaet konstruktør (verdier og datalagre) av denne typen, velger og modifikator komponenter (verdier og datalagre) av denne typen er utvikler-programmererens ansvar.
I konseptet ADT har følgende konsepter en spesiell status: grensesnitt åpen for brukeren, og realisering skjult for ham. Den spesielle rollen til disse konseptene i konseptet ADT er knyttet til den grunnleggende bestemmelsen om uavhengigheten til konseptet ADT fra metoden for implementeringen.
I moderne "praktiske programmeringsspråk" brukes vanligvis den forhåndsdefinerte typen konstruksjonsoperasjon for å konstruere ADT-er klasse , som gir utvikler-programmereren ikke bare midler til å gruppere data og operasjoner (med disse dataene) i en enkelt helhet, men også midler for innkapsling, arv og polymorfisme for å kontrollere måten å konstruere og få tilgang til slike data. Merk at en klasse beskriver en mulig implementering av en ADT, kartleggingen av en klasse til en ADT uttrykkes av en abstraksjonsfunksjon, men den inverse relasjonen er vanligvis ikke funksjonell, det kan være flere implementeringer av samme ADT.
I forskning på abstrakte datatyper, den viktige rollen til konseptet " type parameterisering ". Faktisk, for eksempel, er "Stack" ADT ikke avhengig av typen stabelelementer, men det er umulig å implementere denne ADT ved å peke på "elementer av samme type". I programmeringsspråket Ada ble de tilsvarende midlene for å konstruere parameteriserte datatyper inkludert i utgangspunktet, og i moderne "praktiske programmeringsspråk" hvilke verktøy har dukket opp bare siden utviklingen av STL-biblioteket. I dag inntar konseptet "generisk programmering" en betydelig posisjon i praktisk programmering på grunn av inkluderingen i "praktiske programmeringsspråk" midler for å konstruere parameteriserte datatyper (maler, mal , generisk) .
Alt det ovennevnte betyr at fra et metodisk og teoretisk synspunkt er det nødvendig med en mer detaljert og presis definisjon av begrepet "abstrakt datatype". I teorien er begrepet "abstrakt datatype" vanligvis definert som multi-sortert (multi-base) algebraisk system , der, i tillegg til settet med mulige verdier (bærer) og et sett med operasjoner på slike verdier, er følgende konsepter uthevet:
Sorter og signatur - disse konseptene lar deg klassifisere både medieelementer og operasjoner med dem etter deres typer (for operasjoner, etter typene argumenter og returverdi).
Predikater er relasjoner på elementene i bæreren. Dette gjør det mulig å bestemme rekkevidden av mulige verdier ved å pålegge begrensninger (krav) på tillatte verdier, samt å arbeide i en naturlig tolkning med vilkårlige logiske uttrykk uten å tvinge dem til å bli tolket som medlemskapsfunksjoner for sett eller som flerverdier operasjoner.
På dette grunnlaget er det mulig å vurdere abstrakte datatyper fra et enkelt integrert logisk-algebraisk synspunkt, inkludert spørsmål om konstruktører (typer og verdier), velgere og egenskapsmodifikatorer for objekter av denne typen.
Konseptene "datastruktur" og "abstrakt datatype" er noe like. Du kan selvfølgelig vurdere at disse konseptene bare er to syn på det samme. Måten å representere ADT-verdier på er alltid basert på en eller annen datastruktur, mindre eller mer kompleks, og implementeringen av operasjoner med slike verdier avhenger naturligvis av denne valgte datastrukturen. På den annen side, hvis vi vil, kan vi alltid designe datastrukturen som interesserte oss som en ADT.
Men likevel vil vi skille mellom disse to konseptene, gitt:
En abstrakt datatype innebærer et visst nivå av abstraksjon med det formål å fikse en anvendt (domenespesifikk) datatype, uavhengig av hvordan den er implementert, og det er mulig å inkludere denne datatypen i et applikasjonsbibliotek, vel, i det minste for en spesifikk utvikling av et spesifikt programvaresystem. En ADT kan ha flere alternative implementeringer basert på ulike datastrukturer.
Datastruktur er snarere et opplegg for dataorganisering og -styring, som innebærer passende konkretisering når det brukes i spesifikke situasjoner når man løser spesifikke problemer.
For det første hører matematiske grunnleggende algebraiske systemer - sekvenser, sett, relasjoner og avbildninger (funksjonelle relasjoner, funksjoner) - naturlig til abstrakte datatyper. Men i programmering er forgrunnen ikke studiet av de generelle egenskapene til disse matematiske konseptene, men mulighetene for deres bruk i utviklingen av modeller for å løse problemer i fagområdet, algoritmer for å løse disse problemene og effektiv implementering av de utviklede algoritmer. Det er derfor i programmering i form av ADT-er, på den ene siden dannes begrensede versjoner av disse grunnleggende algebraiske systemene, og på den andre siden utvides de med spesialiserte sett med operasjoner som er av pragmatisk interesse fra et synspunkt av bruksområdet.
1.2. Abstrakte datatyper
De fleste konseptene som ble introdusert i forrige seksjon er vanligvis introdusert i et programmeringskurs for nybegynnere og bør være kjent for deg. Bare abstrakte datatyper kan være nye, så la oss først diskutere deres rolle i programutviklingsprosessen. Først av alt, la oss sammenligne en abstrakt datatype med et så kjent konsept som en prosedyre.
En prosedyre, et integrert programmeringsverktøy, kan sees på som et generisk konsept for en operatør. I motsetning til de innebygde operatørene i et programmeringsspråk (addisjon, multiplikasjon, etc.), som er begrenset i sine muligheter, kan programmereren bruke prosedyrer for å lage sine egne operatører og bruke dem på operander av forskjellige typer, ikke bare grunnleggende. Et eksempel på en slik operatorprosedyre er standard matrisemultiplikasjonsrutine.
En annen fordel med prosedyrer (foruten muligheten til å opprette nye operatører) er muligheten til å bruke dem til innkapsling deler av algoritmen ved å plassere i en egen del av programmet alle operatører som er ansvarlige for et visst aspekt av programmets funksjon. Eksempel på innkapsling: bruk av én prosedyre for å lese inndata av enhver type og kontrollere korrektheten. Fordelen med innkapsling er at vi vet hvilke innkapslede utsagn som må endres i tilfelle problemer med funksjonen til programmet. For eksempel, hvis det er nødvendig å organisere verifiseringen av inngangsdataene for positive verdier, bør bare noen få linjer med kode endres, og vi vet nøyaktig hvor disse linjene er plassert.
Definisjon av en abstrakt datatype
Vi definerer abstrakt datatype(ADT) som en matematisk modell med et sett med operatorer definert i denne modellen. Et enkelt eksempel på ADT er et sett med heltall med operatorer av union, skjæringspunkt og forskjell av sett. I ADT-modellen kan operatører ha som operander ikke bare data definert av ADT, men også data av andre typer: standardtyper av programmeringsspråket eller definert i andre ADT-er. Resultatet av operatørens handling kan også være av en annen type enn de som er definert i denne ADT-modellen. Men vi antar at minst én operand eller resultat av en hvilken som helst operatør har datatypen definert i den betraktede ADT-modellen.
De to karakteristiske egenskapene til prosedyrer - generalisering og innkapsling - diskutert ovenfor er utmerket for abstrakte datatyper. En ADT kan tenkes på som en generalisering av enkle datatyper (heltall, reelle tall, etc.), akkurat som en prosedyre er en generalisering av enkle operatorer (+, -, etc.). En ADT innkapsler datatyper i den forstand at definisjonen av en type og alle utsagn utført på data av den typen er plassert i en del av programmet. Hvis det er nødvendig å endre ADT-implementeringen, vet vi hvor vi skal finne og hva vi skal endre i en liten del av programmet, og vi kan være sikre på at dette ikke vil føre til feil noen steder i programmet når vi arbeider med denne datatypen. Dessuten, utenfor avsnittet om definisjonen av ADT-operatører, kan vi vurdere ADT-typer som primære typer, siden deklarasjonen av typer ikke formelt er knyttet til implementeringen av dem. Men i dette tilfellet kan det oppstå vanskeligheter, siden noen operatører kan startes for mer enn én ADT og referanser til disse operatørene må være i seksjoner av flere ADT.
For å illustrere de grunnleggende ideene bak opprettelsen av en ADT, bør du vurdere den grådige rutinen fra forrige seksjon (Listing 1.3), som bruker enkle dataoperatorer på datatypen abstrakt LIST (liste over heltall). Disse operatørene må utføre følgende handlinger på variabelen newclr av typen LIST.
1. Gjør listen tom.
2. Velg det første elementet i listen, og returner verdien hvis listen er tom null.
3. Velg neste element i listen og returner verdien null, hvis det ikke er noe neste element.
4. Sett inn et heltall i listen.
Det er mulig å bruke ulike datastrukturer som du effektivt kan utføre de beskrevne handlingene med. (Datastrukturer vil bli diskutert i detalj i emne 2.) Hvis du i Listing 1.3 erstatter de tilsvarende operatorene med uttrykk
MAKENULL (newcJr);
w: = FØRST (newcJr);
w: = NESTE (nycfr);
INSERT (v, newclr);
da vil en av hovedaspektene (og fordelene) med abstrakte datatyper bli forstått. Du kan implementere en datatype på hvilken som helst måte, og programmer som bruker objekter av denne typen er ikke avhengig av hvordan typen implementeres - prosedyrene som implementerer operatører for denne datatypen er ansvarlige for dette.
La oss gå tilbake til den abstrakte datatypen GRAPH (Graph). Objekter av denne typen krever operatører som utfører følgende handlinger.
1. Det første umalte toppunktet velges.
2. Sjekk om det er en kant mellom de to toppunktene.
3. Merk toppunktet med farge.
4. Velg neste umalte toppunkt.
Åpenbart forblir andre operatører ute av syne av den grådige prosedyren, for eksempel å sette inn toppunkter og kanter i grafen eller markere alle toppunktene i grafen som åpne. De ulike datastrukturene som støtter denne datatypen vil bli dekket i emne 6 og 7.
Det bør understrekes at antallet operatører brukt på objektene i denne matematiske modellen ikke er begrenset. Hvert sett med operatører definerer en egen ADT. Her er eksempler på operatorer som du kan definere for SET (Sett) abstrakt datatype.
1. MAKENULL (A), Denne prosedyren gjør settet A tomt.
2. UNION (A, B, C). Denne prosedyren har to "input"-argumenter, sett A og B, og tildeler foreningen av disse settene til "output"-argumentet, sett C.
3. STØRRELSE (A). Denne funksjonen har et sett argument A og returnerer et objekt av heltallstype lik antall elementer i sett A. Begrepet ADT-implementering innebærer følgende: oversettelse av erklæringer som definerer variabler av denne abstrakte datatypen til programmeringsspråksetninger, pluss prosedyrer for hver operatør utført på ADT-objekter. Gjennomføringen avhenger av datastrukturer, som representerer ADT. Hver datastruktur er bygget på grunnlag av de grunnleggende datatypene til programmeringsspråket som brukes ved å bruke datastruktureringsverktøyene som er tilgjengelige på dette språket. Array- og poststrukturer er to viktige datastruktureringsverktøy tilgjengelig i Pascal. For eksempel kan en av de mulige implementeringene av en variabel S av typen SET være en matrise som inneholder elementer av settet S.
En av hovedgrunnene for å definere to forskjellige ADT-er innenfor samme modell er at det må utføres forskjellige handlinger på objektene til disse ADT-ene, dvs. definere operatører av forskjellige typer. I denne synopsis blir bare noen få grunnleggende matematiske modeller, som settteori og grafteori, vurdert, men for forskjellige implementeringer vil forskjellige sett med operatører bli bygget basert på disse modellene av visse ADT-er.
Ideelt sett er det ønskelig å skrive programmer på et språk hvis grunnleggende datatyper og operatører er tilstrekkelige til å implementere ADT. Fra dette synspunktet er ikke Pascal-språket et veldig egnet språk for å implementere ulike ADT-er, men på den annen side er det vanskelig å finne et annet programmeringsspråk der det ville være mulig å deklarere ADT-er direkte. For mer informasjon om slike programmeringsspråk, se de bibliografiske notatene på slutten av emnet.
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: V.A. Alenin
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 implementering av dem.
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 kjøringen av programmet 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: informativ, for lagrings skyld strukturen er opprettet, og pekere som sikrer koblingen av elementer med hverandre.
Teoretisk del
1.1 Abstrakte datatyper. Lineære lister
Abstrakte datatyper er nøkkelbegreper i programmering. Abstraksjon innebærer separasjon og uavhengig vurdering av grensesnitt og implementering.
Dataabstraksjon innebærer definisjon og vurdering av abstrakte datatyper (ADT) eller, som er det samme, nye datatyper som legges inn av brukeren.
En abstrakt datatype er en samling av data sammen med mange 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 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 spesiell type), og klassene danner et hierarki basert på prinsippene for arv."
Objektorientert metodikk, som strukturell metodikk, ble skapt 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 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ølte 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, ved å 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 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 deler 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 en 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 trelignende struktur der en hvilken som helst node på treet innkapsler alle sine umiddelbare 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 dataskjul, 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 egenskaper og metoder 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, kan man til og med si, noen vil og sinn, evnen til å aktivt reagere 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 for programmering, der objekter er mer på objekter som noen handlinger utføres over, og, hvis jeg kan si det, en ny form for abstrakt syntetisk sinn, som samhandler med 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 arvede klassen på samme måte som med objekter i basisklassen.
Arvetyper
Enkel arv
Klassen som arv stammer fra kalles base eller parent (engelsk baseclass). Klasser som stammer fra basen kalles etterkommere, etterkommere eller avledede klasser.
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 basisklassen "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 oppstår, for å løse konflikter med bruk av nedarvede metoder med samme navn, er det for eksempel mulig å bruke operasjonen for synlighetsforlengelse - "::" - å 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.
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, blir listeelementene oppregnet for å nå den ønskede, siden listen ikke har tilfeldig tilgang til elementene, derfor er det mer rasjonelt å starte opptellingen fra " hodet" på listen. I tillegg til lenken 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 undersøkelse 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 konstruksjonen ovenfor bruker setref-metoden til cElement-klassen, som er nødvendig for å sette en kobling til neste element i listen, ellers vil listen være ubundet, noe som er full av datatap og feil programdrift.
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 eksistensen av listen kontrolleres 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 flytte 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 - Skrive inn 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 listeelement angitt som en parameter fjernes. 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 hjelp av en løkke, gå til innsettingspunktet til elementet, og tilknytt 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 et syklisk anrop av de samme metodene, for eksempel å skrive ut en liste 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.
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 tilnærmingen til programmering, 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 lar denne tilstanden endres 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 Parnas 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 Mestre 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 C #-programmering. 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 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 >> InformatikkUtvikle 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 >> InformatikkInformasjonsbeskyttelse ……………………………………………… ..17 Abstrakt informasjonssikkerhetsmodeller ... styrer interaksjoner med begge typer data(Sertifiseringsregler): Alle ... ulike varianter og tillegg til eksisterende listen... Sikkerhetsnivåer - visse ...
