Abstrakt datatyp. Abstrakta datatyper

Alla inbyggda datatyper är abstrakta, även om de sällan kallas så.

Abstraktion koncept

Abstraktion är en bedömning eller representation om ett objekt som endast innehåller egenskaper som är väsentliga i ett givet sammanhang. Abstraktion låter dig kombinera objektinstanser till grupper, inom vilka objektens allmänna egenskaper kan ignoreras, d.v.s. abstrakt från dem. Abstraktion är ett effektivt verktyg mot programmeringskomplexitet, vilket gör att programmeraren kan fokusera på objektens väsentliga egenskaper. Typer av abstraktioner: processabstraktion och dataabstraktion.

Processabstraktion. Alla subrutiner är abstraktioner av processer, de definierar det sätt på vilket programmet bestämmer att någon process måste göras, utan att specificera detaljerna om exakt hur det ska göras. Möjligheten att abstrahera bort de många detaljerna i algoritmen som en subrutin kör gör att du kan skapa, läsa och förstå stora program. Alla dataabstraktioner är operationer, definierade som processabstraktioner.

Dataabstraktion. En abstrakt datatyp är en inkapsling som endast innehåller representationer av data av en viss typ och rutiner som utför operationer på data av den typen. Genom att använda åtkomstkontroll kan icke väsentliga detaljer i en typbeskrivning döljas från externa moduler som använder typen. Programmoduler som använder en abstrakt datatyp kan deklarera variabler av den typen även om den faktiska representationen av typen är dold för dem. En instans av en abstrakt datatyp kallas ett objekt.

Anledningen till att skapa datatypabstraktioner och processabstraktioner är ett medel mot komplexitet, ett sätt att göra stora och/eller komplexa program mer hanterbara.

Inkapsling

Dela upp ett program i syntaktiska behållare som innehåller grupper av logiskt relaterade rutiner och data. Dessa syntaktiska behållare kallas moduler, och utvecklingsprocessen är modularisering.

Att komponera ett program från uppsättningar av rutiner och data, som var och en kan kompileras separat, utan att återkompilera resten av programmet. Denna uppsättning kallas en kompileringsenhet.

Inkapsling är ett sätt att integrera rutiner och den data de bearbetar till en sammanhängande helhet. Inkapsling, som kompileras antingen separat eller oberoende, är grunden för ett abstrakt system och den logiska organisationen av en uppsättning relaterade beräkningar.

Abstrakta användardefinierade datatyper

Abstrakta användardefinierade datatyper måste ha följande egenskaper:

1) typdefinition, som tillåter programmoduler att deklarera variabler av denna typ, samtidigt som de skapar en verklig representation av dessa variabler i minnet.

2) en uppsättning operationer för att manipulera objekt av denna typ.

Formell definition av en abstrakt datatyp i sammanhanget av användardefinierade typer: En abstrakt datatyp är en datatyp som uppfyller följande två villkor.

Representation (typdefinition) och operationer på objekt av denna typ finns i en syntaktisk enhet, variabler av denna typ kan skapas i andra moduler.

Representationen av objekt av denna typ är dold från programmoduler som använder denna typ; operationer kan utföras på objekt som är direkt tillhandahållna i definitionen av typen.

Genom att packa typrepresentationen och operationerna i en separat syntaktisk enhet kan du organisera ditt program som logiska enheter som kan kompileras separat. För det andra blir det möjligt att modifiera representationerna av objekt av en given typ eller operationer med dem i en separat del av programmet. Det finns fördelar med att dölja detaljerna i en typs presentation. Klienter kan inte "se" detaljerna i ett objekts vy, och deras kod är oberoende av den vyn. På detta sätt kan objektrepresentationer ändras när som helst utan att det krävs ändringar i klientkoden. En annan uppenbar och viktig fördel med att dölja information är ökad tillförlitlighet. Klienter kan inte direkt ändra de underliggande representationerna av objekt, varken avsiktligt eller oavsiktligt, därför ökar integriteten för sådana objekt. Objekt kan endast modifieras med de operationer som tillhandahålls för detta.

Typdesignproblem

Det bör vara möjligt att göra typnamnet och subrutinhuvudena synliga i abstraktionsklienter. Detta tillåter klienter att deklarera variabler av abstrakt typ och manipulera deras värden. Även om typnamnet måste vara synligt från utsidan, måste dess definition vara dold.

Det finns väldigt få generella inbyggda operationer som kan utföras på objekt av abstrakta typer, till skillnad från de som tillhandahålls av en typdefinition. Sådan verksamhet omfattar uppdrag och jämställdhets- och ojämlikhetstest. Om språket inte tillåter användare att överbelasta uppdragsoperatören, bör det vara inline. Jämställdhets- och ojämlikhetskontroller måste vara fördefinierade i vissa fall och inte i andra. Typdesignern måste själv definiera operationerna för de flesta abstrakta datatyper.

Smalltalk, C++ och Java stöder direkt abstrakta datatyper.

Abstrakta datatyper i C ++

Språken Ada och Modula-2 tillhandahåller inkapsling som kan användas för att modellera abstrakta datatyper, medan C++ introducerar konceptet med en klass som direkt stöder abstrakta datatyper. I C ++ är klasser typer, men Ada-paket och Modula-2-moduler är inte typer. Paket och moduler importeras, vilket gör att den importerande programenheten kan deklarera variabler av vilken typ som helst som definieras i paketet eller modulen. I ett C++-program deklareras variabler som entiteter av typen av denna klass. Således är klasser mycket mer som inbyggda typer än paket eller moduler. En programenhet som ser ett paket på Ada-språket eller en modul på Modula-2-språket har tillgång till alla öppna enheter helt enkelt genom deras namn. En C++-programenhet som deklarerar en instans av en klass har också tillgång till alla offentliga enheter i den klassen, men endast genom en instans av den klassen.

Senast uppdaterad: 2018-04-08

Utöver de vanliga klasserna har C # abstrakta klasser... En abstrakt klass är som en vanlig klass. Det kan också ha variabler, metoder, konstruktorer, egenskaper. Det enda är att det abstrakta nyckelordet används när man definierar abstrakta klasser:

Abstrakt klass Människan (public int Längd (get; set;) public double Vikt (get; set;))

Men den största skillnaden är att vi inte kan använda konstruktören för en abstrakt klass för att skapa dess objekt. Till exempel enligt följande:

Människan h = ny människa ();

Varför behöver vi abstrakta klasser? Låt oss säga att vi i vårt banksektorprogram kan definiera två huvudenheter: en bankkund och en bankanställd. Var och en av dessa enheter kommer att vara olika, till exempel för en anställd måste du definiera hans position och för en klient - beloppet på kontot. Följaktligen kommer klient och anställd utgöra separata klient- och anställdklasser. Samtidigt kan båda dessa enheter ha något gemensamt, till exempel för- och efternamn, någon annan gemensam funktionalitet. Och det är bättre att flytta denna allmänna funktionalitet till någon separat klass, till exempel Person, som beskriver en person. Det vill säga klasserna Anställd (anställd) och Kund (bankklient) kommer från klassen Person. Och eftersom alla objekt i vårt system kommer att representera antingen en bankanställd eller en kund, kommer vi inte att skapa objekt direkt från klassen Person. Så det är vettigt att göra det abstrakt:

Abstrakt klass Person (public string Namn (get; set;) public Person (string name) (Name = name;) public void Display () (Console.WriteLine (Name);)) class Client: Person (public int Sum (get) ; set;) // kontobelopp offentligt Kund (strängnamn, int summa): bas (namn) (Summa = summa;)) klass Anställd: Person (offentlig sträng Position (get; set;) // position offentlig Anställd ( sträng namn, strängposition): bas (namn) (Position = position;))

Då kan vi använda dessa klasser:

Klientklient = ny klient ("Tom", 500); Anställd anställd = ny anställd ("Bob", "Apple"); client.Display (); anställd.Visa ();

Eller till och med så här:

Personklient = ny klient ("Tom", 500); Person anställd = ny anställd ("Bob", "operatör");

Men vi kan INTE skapa ett Person-objekt med hjälp av konstruktorn för klassen Person:

Person person = ny person ("Bill");

Men trots det faktum att vi inte direkt kan anropa konstruktören av klassen Person för att skapa ett objekt, kan konstruktorn i abstrakta klasser ändå spela en viktig roll, i synnerhet för att initiera vissa variabler och egenskaper som är gemensamma för härledda klasser, liksom fall med egenskapen Namn. Även om exemplet ovan inte anropar personkonstruktören, kan klasserna härledda från klient och anställd hänvisa till det.

Abstrakta klassmedlemmar

Utöver de vanliga egenskaperna och metoderna kan en abstrakt klass ha abstrakta klassmedlemmar, som definieras med det abstrakta nyckelordet och inte har någon funktionalitet. I synnerhet kan abstrakt vara:

• Egenskaper

  Indexerare

Abstrakta klassmedlemmar får inte ha den privata modifieraren. I det här fallet måste den härledda klassen åsidosätta och implementera alla abstrakta metoder och egenskaper som finns i den abstrakta basklassen. När den åsidosätts i en härledd klass, deklareras en sådan metod eller egenskap också med åsidosättningsmodifieraren (som med vanliga åsidosättande virtuella metoder och egenskaper). Det bör också noteras att om en klass har minst en abstrakt metod (eller abstrakt egenskap, indexerare, händelse), måste denna klass definieras som abstrakt.

Abstrakta medlemmar, liksom virtuella, är en del av ett polymorft gränssnitt. Men om vi, när det gäller virtuella metoder, säger att den ärvda klassen ärver implementeringen, ärvs i fallet med abstrakta metoder gränssnittet som representeras av dessa abstrakta metoder.

Abstrakta metoder

Låt oss till exempel göra visningsmetoden abstrakt i exemplet ovan:

Abstrakt klass Person (public string Namn (get; set;) public Person (string name) (Name = name;) public abstract void Visa ();) class Client: Person (public int Sum (get; set;) // summa på kontot public Client (strängnamn, int summa): bas (namn) (Sum = summa;) public override void Display () (Console.WriteLine ($ "(Name) har ett konto för summan (Sum)") ;)) klass Anställd: Person (public string Position (get; set;) // position public Employee (string name, string position): base (name) (Position = position;) public override void Display () (Console.WriteLine ($ " (Position) (Namn) ");))

Abstrakta egenskaper

Användningen av abstrakta egenskaper bör noteras. Att definiera dem liknar att definiera autoegenskaper. Till exempel:

Abstrakt klass Person (offentlig abstrakt sträng Namn (get; set;)) klass Klient: Person (privat strängnamn; offentlig åsidosättande sträng Namn (get (retur "Mr / Ms." + Namn;) set (namn = värde;)) ) klass Anställd: Person (offentlig åsidosättningssträng Namn (get; set;))

Klassen Person definierar egenskapen abstract Name. Det ser ut som en bilfastighet, men det är inte en bilegendom. Eftersom den här egenskapen inte behöver implementeras har den bara tomma get- och set-block. I härledda klasser kan vi åsidosätta den här egenskapen för att göra den till en fullständig egenskap (som i klientklassen), eller göra den automatisk (som i klassen Employee).

Dikning genomförandet av abstrakta medlemmar

Den härledda klassen måste implementera alla abstrakta medlemmar i basklassen. Vi kan dock välja bort implementeringen, men i det här fallet måste den härledda klassen också definieras som abstrakt:

Abstrakt klass Person (offentlig abstrakt sträng Namn (get; set;)) abstrakt klass Manager: Person ()

Abstrakt klassexempel

Ett läroboksexempel är systemet med geometriska former. I verkligheten finns det ingen geometrisk figur som sådan. Det finns en cirkel, en rektangel, en kvadrat, men det finns helt enkelt ingen figur. Men både cirkeln och rektangeln har något gemensamt och är former:

// abstrakt klass av figuren abstrakt klass Figur (// abstrakt metod för att få omkretsen offentlig abstrakt flyta Perimeter (); // abstrakt metod för att få arean offentlig abstrakt flyta Area ();) // härledd klass av rektangelklassen Rektangel: Figur (public float Width (get; set;) public float Height (get; set;) public rektangel (float width, float height) (this.Width = width; this.Height = height;) // åsidosätta få perimeter public override float Perimeter () (retur Width * 2 + Height * 2;) // override få området public override float Area () (retur Width * Höjd;))

Bilaga till arbetsprogrammet för disciplinen "Strukturer och algoritmer för databehandling i en dator"

Den abstrakta datatypen "List".

Lista- en sekvens av element av en viss typ a1 , a2 , ..., a n, var n https://pandia.ru/text/78/308/images/image001_307.gif "width =" 13 "height =" 16 "> 1, sedan a1

Kallas det första elementet och ett- det sista elementet i listan. Listobjekt är linjärt ordnade enligt deras position i listan. Ai element föregått element ai+1 för i = 1,2, n-1 och ai skall per ai-1 för i = 2,3, n. Varje objekt i listan ai Det har placera i, i=1,2, n. Det finns en position i listan , betecknar slutet på listan - noll. Den följer den sista punkten i listan.

Operatörer av ADT "List":

1. INFOGA ( x, R,L). Denna sats infogar ett objekt NS i position R i listan L, flytta element från position p och vidare till nästa högre position. Så om listan L består av element a1 , a2 , ..., an a1, a2, ..., ap-1, x, ap, ..., an.... Om p tar värdet noll, då har vi a1 , a2 , ..., an , NS... Om i listan L ingen position R, då är resultatet av detta uttalande odefinierat.

2. LOKALISERA(x , L ). Denna funktion returnerar objektets position NS i listan L. Om objektet finns i listan x inträffar flera gånger, sedan returneras positionen för det första objektet från början av listan NS. Om objektet NS inte på listan L sedan kommer den tillbaka noll.

3. HÄMTA(sid , L ). Denna funktion returnerar elementet i position R i listan L. Resultatet är odefinierat if p = noll eller i listan L ingen position R.

4. RADERA(sid , L ). Denna operatör tar bort elementet i position R lista L. Så om listan L består av element a1 , a2 , ..., an, sedan efter att ha kört den här operatorn kommer det att se ut a1, a2, ...,, ap- i , ap+ i, ..., a n. Resultatet är odefinierat om listan innehåller L ingen position R eller R = noll.

5. NÄSTA ( p, L ) och FÖREGÅENDE (sid, L ). Dessa funktioner returnerar nästa respektive föregående position från positionen R i listan L. Om R - sista positionen i listan L, sedan nästa (sid, L) = noll... NEXT-funktionen är odefinierad när p =noll... Funktionen FÖREGÅENDE är odefinierad om p = 1. Båda funktionerna är odefinierade om listan L ingen position R.

6. MAKENULL( L ) ... Denna funktion skapar en lista L tom och återställer positionen noll.

7. FÖRST(L ). Denna funktion returnerar den första positionen i listan L. Om listan är tom returneras positionen noll.

8. UTSKRIFTSLISTA(L ). Skriver ut listobjekt L i den ordning de visas i listan.

Listvy med en array:

Listvy med hjälp av enkel länkad lista:

Legend:

- en pekare till början av listan,

· sista - pekare till det sista objektet i listan ,

· maxlängd - den maximala längden (antal element) i listan.

Att representera en lista med en dubbellänkad lista:

Övningar:

1. Skriv program för att infoga, ta bort och söka i element i en sorterad lista, använd för att implementera listan

§ array,

§ pekare.

2. Skriv ett program att slå samman

§ två sorterade länkade listor,

§ n sorterade länkade listor,

3. Givet ett polynom av formen

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

Ett sådant polynom kan representeras som en länkad lista, där varje element har tre fält: ett för koefficienten medi den andra är för exponenten ei den tredje är för en pekare till nästa element. För den beskrivna representationen av polynom, skriv ett program för addition och multiplikation av polynom med hjälp av denna representation.

4. Implementera LIST ADT för alla datatyper och dess INSERT, LOCATE, HETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST-satser:

§ listan ges som en array,

§ listan anges som en enskild länkad lista,

§ listan anges som en dubbellänkad lista.

Arbetsprogram avsnitt 2.1.2

Den abstrakta datatypen "Stack".

Stack - det är en speciell typ av lista där alla infogningar och raderingar görs i endast en ände som anropas apex , (topp). Tillbehöret används för stapeln LIFO(sist-in-först-ut - sist in - först ut).

Operatörer av ATD "Stack":

1. MAKENULL(S). Töm S-stacken.

2. TOPP(S). Returnerar objektet från toppen av stacken S. Vanligtvis identifieras toppen av stacken av position 1, då TOP (S) kan skrivas i termer av vanliga listoperatorer som HEMTA (FIRST (S), S).

3. POP(S). Tar bort ett objekt från toppen av stapeln (popper från stapeln), när det gäller listsatser kan detta uttalande skrivas som DELETE (FIRST (S), S).

4. SKJUTA PÅ(x, S ). Infogar ett element NS till toppen av högen S (skjuter föremålet på högen). Objektet som tidigare stod överst i stapeln blir objektet bredvid toppen osv. När det gäller allmänna listoperatorer kan detta uttalande skrivas som INSERT (; c, FIRST (S), S).

5. TÖMMA(S) ... Denna funktion returnerar sant om stacken S tom och falsk annars.

array:

Stackvy med hjälp av enkel länkad lista:

Övningar:

Implementera STACK ADT för alla datatyper och dess MAKENULL, TOP, POP, PUSH, EMPTY operatorer.

§ stacken är specificerad som en array,

Stacken är inställd som en enkellänkad lista.

Arbetsprogram avsnitt 2.1.2

Den abstrakta datatypen "Queue".

Kö (kö) är en speciell typ av lista där objekt infogas från ena änden som anropas hind (bak) och tas bort från den andra, främre (främre). Köer kallas även "FIFO-listor" (FIFO står för först-in-först-ut: först in, först ut). Operatörer som utförs på köer liknar stackoperatorer. Den väsentliga skillnaden mellan dem är att nya element infogas slutet av listan snarare än i början, som i stackar.

Operatörer av ADT "Queue":

1. MAKENULL(F) rensar kö Q , gör det tomt.

2. FRÄMRE(F) - en funktion som returnerar det första elementet i kön F. Du kan implementera den här funktionen med hjälp av listoperatorer som HÄMTA (FIRST (Q), Q ).

3. KÖ(a, Q) infogar ett element NS i slutet av kön Q.

Med listoperatorer kan denna operator exekveras så här: INSERT (x, END (Q), Q ).

4. AVKÖA(F) tar bort det första elementet i kön Q . Kan även implementeras med listsatser som DELETE (FIRST (Q), Q).

5. TÖMMA(F) returnerar sant om och endast om Q är en tom kö.

cyklisk array:

Legend:

F-kö,

F. främre- pekare till början av kön,

F. bak-- en pekare till slutet av kön.

Kö representation med enkel länkad lista:

Övningar:

Implementera QUEUE ADT för alla datatyper och dess MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY-satser.

Kön är specificerad som en cirkulär array,

Kön anges som en dubbellänkad lista.

Abstrakt datatyp "Träd".

Trä är en samling element som kallas knutar (varav en definieras som rot ), och relationer ("förälder") som bildar en hierarkisk struktur av noder. Noder, precis som listelement, kan vara element av vilken typ som helst. Formellt kan ett träd definieras rekursivt enligt följande.

1. En nod är ett träd. Samma nod är också roten till detta träd.

2. Låt NS - detta är en nod, en T1 , T2, ...,Tk- träd med rötter n1 . n2 , ..., nk respektive. Du kan bygga ett nytt träd genom att göra NS förälder till noder n1 . n2 , ..., nk... I det här trädet NS kommer att vara roten, en T1 , T2, ...,Tk - underträd denna rot. Knutpunkter n1 . n2 , ..., nk kallas söner Knut NS.

Denna definition inkluderar ofta begreppet nollträd , det vill säga ett "träd" utan noder, ett sådant träd betecknas med ordet noll .

Exempel: Om kapitel i boken kan schematiskt representeras av ett träd. Förälder-son-relationen visas som en rad. Träd ritas vanligtvis uppifrån och ner med föräldrarna ovanför "barnen".

DIV_ADBLOCK135 ">

Nodhöjd ett träd är längden på den längsta vägen från denna nod till ett löv. I exemplet, nodens höjd Kapitel 1är lika med 1, nod Kapitel 2 - 2, och noden Ch. Z - 0. Trädets höjd sammanfaller med rotens höjd. Noddjup definieras som längden på vägen (den är den enda) från roten till denna nod.

Sons av en nod är vanligtvis ordnade från vänster till höger. Därför är de två träden i figuren olika, eftersom ordningen på nodens söner a annorlunda. Om sönernas ordning ignoreras, kallas ett sådant träd oordnad , annars kallas trädet ordnad .

Operatörer av ATD "Tree":

1. FÖRÄLDER(n, T). Denna funktion returnerar föräldern till noden NS i trädet T. Om NSär en rot som inte har någon förälder, då returnerar den i det här fallet noll... Här noll indikerar att ett out-of-bounds-träd har inträffat.

2. LÄNGST ÅT VÄNSTER__ BARN(n , T). Denna funktion returnerar nodens underordnade längst till vänster. n i trädet T. Om när ett löv (och därför inte har en son), så kommer det tillbaka noll.

3. HÖGER_ SYSKON(n , T). Denna funktion returnerar nodens högra syskon NS i trädet T eller värde noll,.om det inte finns. Detta är vad föräldern är till för R Knut NS och alla knutens söner R, då är bland dessa söner noden omedelbart till höger om. Knut NS.

4. MÄRKA(n , T ). Returnerar nodens etikett n... trä T. Denna funktion kräver att etiketter definieras på trädnoderna.

5. SKAPA(v , T 1 , T 2 , ..., Ti ,) är en familj av funktioner som skapar en ny rot för varje i = 0, 1, 2, ... r med etikett v och sedan för denna rot skapar i söner, som blir underträdens rötter T1 , T2, ....Ti;. Dessa funktioner returnerar ett rotat träd r... Observera att om i = 0, returneras en nod r, som är både en rot och ett blad.

6. ROT(T ) returnerar noden som är trädets rot T, Om T- Tomt träd kommer sedan tillbaka noll.

7. MAKENULL(T ). Denna operatör gör trädet T tomt träd.

Att representera ett träd med hjälp av en rad föräldrar:

Trädvy med länkade listor:

Representerar trädet med hjälp av vänster söner och högra bröder.

Beteckningar i figuren:

nodutrymme – en rad trädnoder,

märka – nodetikett, rubrik – indexet för den vänstra sonen i listan över söner,

cellspas – en rad listor över söner av noder,

nod – en pekare till en nod i en arraynodutrymme , Nästa – index över rätt son i sönslistan.

Övningar:

1. Givet ett träd:

DIV_ADBLOCK137 ">

§ trädet ges som en array av nodposter som innehåller index för sonen längst till vänster, index för höger syskon och en etikett,

Ett anslutet binärt träd specificeras med hjälp av pekare till vänster och höger son.

4. Skriv funktioner för att korsa ett binärt träd i framåt-, bakåt- och symmetrisk ordning.

Arbetsprogram avsnitt 2.1.3

Den abstrakta datatypen "Set".

Mycket av avbildas vanligtvis som en sekvens av dess element, inneslutna i krulliga klammerparenteser, till exempel betecknar (1, 4) en uppsättning som består av två element - siffrorna 1 och 4. Ordningen i vilken elementen i uppsättningen skrivs är inte väsentlig, så du kan skriva (4, 1) på samma sätt som (1, 4), när du skriver samma uppsättning. Uppsättningen är inte en lista (åtminstone på grund av den godtyckliga ordningen av element). Det finns inga dubbletter av element i uppsättningen ((1, 4, 1) är inte en uppsättning).

Det grundläggande begreppet för mängdlära är begreppet relationen tillhör uppsättningen betecknas med symbolen. Alltså inträdet NS NS hör inte till uppsättningen A", dvs. NS inte medlem i uppsättningen A... Det finns en speciell uppsättning betecknad med en symbol som kallas tomma, många , och som inte har några element. Ställ in DIV_ADBLOCK138 ">

De säger att mängden A innehåller i uppsättningen V(eller sätter på i en mängd V), skriven A V eller V A om någon del av uppsättningen Aär också en del av uppsättningen V. När A V säger också att uppsättningen Aär en en delmängd av uppsättningen V.

Till exempel, (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif "width =" 15 "height =" 15 src = "> V och AB, då kallas mängden A eget, sant eller strikt delmängd mängder V.

De huvudsakliga operationerna som utförs på uppsättningar är union, korsning och skillnad. Konsolidering set A och V(betecknad med A V) kallas en mängd som består av element som tillhör minst en av mängderna A och V.

Korsning set A och V(betecknad med A V) kallas en mängd som endast består av de element som hör till mängden A, och uppsättningen V. Skillnad set A och V(betecknad med A\ B) kallas en mängd som endast består av de elementen i mängden A som inte hör till uppsättningen V.

Till exempel, om A = (a, b, c) och B = (b, a), då A B = (a, b, c, d), A B = (b) och A \ B = (a, c ) .

Operatörer av ADT "Set":

1. UNION(A, FÖRE KRISTUS) A och V MED, likvärdig A V.

2. GENOMSKÄRNING(A, FÖRE KRISTUS) har "input"-argument inställda A och V, och som ett resultat - uppsättningen "utgång". MED, likvärdig A V..

3. SKILLNAD(A, FÖRE KRISTUS) har "input"-argument inställda A och V, och som ett resultat - uppsättningen "utgång". MED, likvärdig A \B.

4. SAMMANFOGA( A , FÖRE KRISTUS) operatören utför fusion (sammanfoga), eller förening av osammanhängande uppsättningar . Denna operatör skiljer sig inte från operatören. UNION, men här antas att operanden sätter skär inte varandra (dvs de har inga gemensamma element). Operatören tilldelar till setet MED menande A V, men resultatet kommer att vara odefinierat om A B, d.v.s. i fallet när uppsättningarna A och V har gemensamma element.

5. medlem(x, A ) har argument satta A och objekt NS av samma typ som elementen i uppsättningen A, och returnerar ett booleskt värde Sann(sant) om NS a "," b "," c ")) = "a". Operatören MAX.

11.LIKVÄRDIG(A , V ) returnerar värdet Sann om och bara om uppsättningarna A och V består av samma element.

12. HITTA(x ) fungerar i en miljö där det finns en uppsättning disjunkta uppsättningar. Den returnerar namnet (singular) på den mängd som har ett element NS.

Ställ in representation:

Uppsättningen kan specificeras med hjälp av en array eller en länkad lista.

Övningar:

1. Två uppsättningar A = (1, 2, 3) och B = (3, 4, 5) ges. Vad blir resultatet av att utföra följande påståenden?

UNION (A.B. C),

KORSNING (A, B, C),

SKILLNAD (A.B.C),

MEDLEM (l. A),

INFOGA (1, A),

DELETE (1, A),

2. Implementera Set ADT för alla datatyper och dess MAKENULL, UNION, INTERSECTION, MEMBER, MIN operatorer.

Uppsättningen specificeras med hjälp av en array med fast längd och en pekare till den senast upptagna positionen i arrayen,

Uppsättningen specificeras med hjälp av en osorterad länkad lista,

Uppsättningen specificeras med hjälp av en sorterad länkad lista,

Arbetsprogram avsnitt 2.1.3

Speciella typer av set

Binärt sökträd Abstrakt datatyp

Binärt sökträd - en datastruktur för att representera mängder, vars element är ordnade efter någon linjär ordningsrelation. Binära sökträd kan implementera setoperatorer FÖRA IN, RADERA, MEDLEM och MIN, och deras exekveringstid är i genomsnitt i storleksordningen O (log n) för uppsättningar som består av NS element.

En egenskap hos ett binärt sökträd är att dess noder är märkta med set-element (trädnoder innehåller set-element). Dessutom är alla element lagrade i noderna i det vänstra underträdet av någon nod NS, mindre än elementet i noden NS, och alla element lagrade i noderna i nodens högra underträd NS, mer än elementet som ingår i noden NS.

Exempel på binära träd:

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

AVL-trädvyn är densamma som den binära sökträdvyn.

En annan typ av balanserat sökträd är 2-3 trä. Strukturen för ett 2-3-träd skiljer sig från strukturen för ett binärt sökträd. För 2-3 träd är det karakteristiskt att alla noder har 2 eller 3 söner, alla vägar från rot till blad är av samma längd, och alla delar av uppsättningen finns i bladen. Noderna 2-3 i trädet är uppdelade i interna och terminala (löv). Interna noder används endast för att dirigera trädsökningar. Varje intern nod innehåller nycklarna för de minsta elementen i den andra och tredje sonen (om det finns en tredje son) och pekare till sönernas noder.

Binär sökning kopplad trädvy:

Representation av ett balanserat anslutet 2-3-träd:

Övningar:

1. Rita alla möjliga binära sökträd för de fyra elementen 1, 2, 3 och 4.

2. Infoga heltalen 7, 2, 9, 0, 5, 6, 8, 1 i ett tomt binärt sökträd.

3. Visa resultatet av att ta bort siffran 7 och sedan siffran 2 från trädet som erhölls i föregående övning.

4. Rita ett 2-3-träd, som kommer att bli resultatet av att infoga element 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 i den tomma uppsättningen (representeras som 2-3-trädet).

5. Visa resultatet av att ta bort element 3 från 2-3 i trädet som erhölls i föregående övning.

3. Implementera sökträdet ADT för alla datatyper och dess INSERT-, DELETE-, MEMBER- och MIN-satser.

Trädet ges som ett anslutet binärt träd

Träd anges som 2-3 träd

Arbetsprogram avsnitt 2.1.3

Abstrakt datatyp "Ordbok".

Ordbok - en uppsättning avsedd för att lagra "aktuella" objekt med periodisk infogning eller radering av några av dem. Då och då blir det också nödvändigt att ta reda på om ett visst element finns i en given uppsättning. Ordboken implementeras med hjälp av Dictionary ADT med operatörer FÖRA IN,RADERA och MEDLEM... Ordboksoperatoruppsättningen inkluderar också operatorn MAKENULL för att initiera ADT-datastrukturer.

En ordbok kan representeras med hjälp av en hashtabell. Tabellen är uppbyggd utifrån följande idé: en potentiell uppsättning element (eventuellt oändlig) delas in i ett ändligt antal klasser. För V klasser numrerade från 0 till I 1, under konstruktion hash-funktion h så att för alla element NS originalset funktion h (x) tar ett heltalsvärde från intervallet 0, ..., V - 1, vilket motsvarar den klass elementet tillhör NS. Element NS ringer ofta nyckel, h ( x) - hash-värde x, och "klasser" - segment ... Hur man löser hashingkollisioner (två element i en uppsättning har samma värde h (x)), både offentlig och privat hashing tillämpas.

öppet hashbord

En array som kallas segmenttabell och indexeras segmentnummer 0, 1, ..., B - 1 , innehåller rubriker för V länkade listor. Element i-th list är ett element i originaluppsättningen för vilken h(.x :) =i.

Ordboksrepresentation med privat hashbord

Segmenttabellen lagrar direkt elementen i ordförrådet. Därför kan endast ett ordbokselement lagras i varje segment. Med privat hashning används tekniken omhasha ... När du försöker placera ett element x till segment numrerat h ( x ) , som redan är upptaget av ett annat element, väljs en sekvens av segmentnummer h 1 ( x ) ,h 2 ( x ) , … där elementet kan placeras. Beläggningen av vart och ett av dessa segment kontrolleras sekventiellt tills ett ledigt segment hittas. Elementet placeras i den x ... Olika kollisionsupplösningsmetoder används för att ställa in segmentnummer vid omhasning. Till exempel linjär hash-metod, mid-square-metod, slumpmässig hash-metod

Övningar:

1. Anta att du använder hashfunktionen h (i) = i% 7 för att hasha heltal till en 7-segments hashtabell.

· Ge den resulterande hashtabellen om de exakta kuberna 1, 8, 27,64,125, 216,343 infogas i den;

· Upprepa föregående punkt för en stängd hashtabell med en linjär kollisionsupplösningsteknik.

2. Antag att det finns en privat hashtabell med 5 segment, en hashfunktion h (i) = i% 5 och en linjär kollisionsupplösningsteknik. Visa resultatet av att infoga sekvensen av nummer 23, 48, 35, 4, 10 i den initialt tomma hashtabellen.

3. Implementera Dictionary ADT för textsträngar och dess INSERT-satser , DELETE, MEMBER och MAKENULL

Ordboken specificeras med en öppen hashtabell,

Ordboken specificeras med en sluten hashtabell med linjär kollisionsupplösningsteknik,

Arbetsprogram avsnitt 2.1.3

Den abstrakta datatypen "Display".

Visa - detta är en uppsättning, på vars element funktionen att visa element av samma typ är definierad ( definitionsområden ) till element av en annan typ ( värdeintervall ) av en annan typ. Visa M matchar ett element d av typ domäntyp från scope till element r av typ rangetype från range: M(d) = r.Tom display innehåller inga element

Operatörer av ADT "Display":

1. MAKENULL(M ). Gör display M tömma.

2. TILLDELA (M d, r). gör det M(d) likvärdig r spelar ingen roll hur M(d) definierades tidigare.

3. BERÄKNA ( M, d, r). Returnerar sant och tilldelar ett värde till r M(d), om det senare är definierat, och returnerar falskt annars.

Visa vy: mappningen kan implementeras effektivt med hjälp av hashtabeller. Här x anger värdet från visningsdefinitionsomfånget och tabellelementet med numret h ( x ) - ett element från sortimentet.

Arbetsprogram avsnitt 2.1.3

Prioritetskö Abstrakt datatyp

Prioriterad kö är en uppsättning för de element för vilka prioritetsfunktionen är inställd, det vill säga för varje element x set, kan du beräkna funktionen R( x )- elementprioritet x , som vanligtvis tar värden från en uppsättning reella tal, eller, mer generellt, från någon linjärt ordnad uppsättning.

ADT "Priority queue" baserat på ADT "Set" med operatörer FÖRA IN och DELETEMIN och även med operatören MAKENULL för att initiera datastrukturen. Operatör FÖRA IN för en prioriterad kö förstås i vanlig mening, medan DELETEMINär en funktion som returnerar elementet med lägst prioritet och som en bieffekt tar det bort från uppsättningen.

Kö representation med en ordnad dubbellänkad lista.

Kö representation med delvis beställt anslutet träd:

Huvudtanken bakom denna implementering är att organisera elementen i kön i ett binärt träd. På den nedre nivån, där några löv kan saknas, kan alla saknade blad befinna sig endast till höger om de nuvarande lägre nivåerna. Det är viktigare att trädet delvis beställd . Detta innebär att nodens prioritet v inte högre än prioritet för någon son till noden v, där nodprioritet är prioritetsvärdet för objektet som är lagrat i denna nod. Det kan ses av figuren att små prioritetsvärden inte kan visas på en högre nivå, där det finns stora prioritetsvärden.

Funktionen DELETEMIN returnerar objektet med lägst prioritet som måste vara roten i trädet. För att inte förstöra trädet och för att bevara den partiella ordningen av prioritetsvärdena på trädet efter att roten har raderats, utförs följande åtgärder: noden längst till höger är placerad på den lägsta nivån och tillfälligt placerad vid roten av trädet. Detta element går sedan ner för trädets grenar (till lägre nivåer), och byter plats med söner med lägre prioritet längs vägen, tills detta element blir ett löv eller kommer i en position där dess söner kommer att ha åtminstone inte mindre prioritet.

Representation av en kö med en array som innehåller noderna i ett delvis ordnat träd:

I en uppsättning A den första n positioner motsvarar n trädnoder. Element A innehåller trädets rot. Vänster son till en trädnod A[ i], om det finns, finns i cellen A, och rätt son, om han finns, är i cellen A. Omvänt, om sonen sitter i cellen A[ i], då är dess förälder i cellen A[ i%2] ... Trädnoder fyller celler A, A, … A[ n] sekventiellt nivå för nivå, med början från roten och inuti nivån - från vänster till höger. Trädet som visas ovan kommer att representeras i arrayen av följande sekvens av dess noder: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Övningar:

1. Rita ett delvis ordnat träd genom att infoga heltalen 5, 6, 4, 9, 3, 1 och 7 i ett tomt träd. Vad skulle bli resultatet av att successivt tillämpa tre DELETEMIN-satser på detta träd?

2. Implementera Priority Queue ADT för alla datatyper och dess INSERT-, DELETEMIN- och MAKENULL-satser

§ ett delvis ordnat träd implementeras med hjälp av pekare,

§ Ett delvis ordnat träd implementeras med hjälp av en array.

Arbetsprogram avsnitt 2.1.3

Den abstrakta datatypen "Union of Sets".

ADT är en förening av objekt, som vart och ett är en uppsättning. Huvudåtgärderna som utförs på en sådan uppsättning är att kombinera uppsättningarna i en viss ordning, samt att kontrollera om ett visst objekt tillhör en viss uppsättning. Dessa uppgifter löses med hjälp av operatörer SAMMANFOGA(Töm) och HITTA(Hitta). MERGE-operatör ( A, FÖRE KRISTUS) gör uppsättningen MED lika med föreningen av uppsättningar A och V om dessa uppsättningar inte skär varandra (det vill säga inte har gemensamma element); denna operatör är odefinierad om uppsättningarna A och V korsas. FIND-funktion ( x) returnerar den uppsättning som elementet tillhör NS; i fallet när NS tillhör flera uppsättningar eller inte tillhör någon, är värdet för denna funktion odefinierat.

Operatörer av ADT "Union of Sets":

1. SAMMANFOGA(A , V) kombinerar komponenter A och ... V, resultatet tilldelas antingen A eller V.

2. HITTA(x ) - en funktion som returnerar namnet på den komponent som den tillhör NS.

3. FÖRSTA(A , NS ) skapar en komponent med namnet A som endast innehåller elementet NS.

Representation av förening av uppsättningar med hjälp av arrayer:

Uppsättningens namn är detsamma som arrayindexvärdet setheaders ( namn 0 )

Legend:

setheaders - rad uppsättningsrubriker:

§ med count - antalet element i uppsättningen,

§ första elementet - array indexnamnmed det första elementet i uppsättningen,

namn – array av listor med element i uppsättningar:

Ange namn - namnet på den uppsättning som elementet tillhör, nästa element - indexet för nästa element i listan för den givna uppsättningen (indexvärde 0 används som slutet av listan).

Arbetsprogram avsnitt 2.1.3

Abstrakt datatyp “ Riktad graf"

Grundläggande definitioner:

Riktad graf (digrafera ) G = (V, E) består av många hörn V och många bågar E. Vertices kallas också knutar , och bågar - orienterade revben . Bågen kan representeras som ett ordnat par av hörn ( u, w), var är toppen och kallad början , a w - slutet bågar.

De säger också att bågen och -> w leder från toppen till toppen w, och toppen w intilliggande med topp v.

Diagramexempel 1:

Digrafhörn kan användas för att representera objekt, och bågar kan användas för att representera relationer mellan objekt.

Förbi i en digraf menar vi en sekvens av hörn v1 , v2 , … , vn , , för vilka det finns bågar v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Denna väg börjar på toppen v1 och passerar genom topparna v2 , v3 , ..., vn-1 slutar överst vn. Stiglängd - antalet bågar som utgör banan, i det här fallet är banlängden NS - 1 ... Som ett specialfall av en bana, betrakta en vertex v som en väg med längden 0 från spetsen vTill samma topp v... I figuren bildar sekvensen av hörn 1, 2, 4 en väg med längd 2 från vertex 1 till vertex 4.

Stigen kallas enkel , om alla hörn på den, möjligen med undantag för den första och den sista, är olika. Cykel - det är en enkel bana med längden minst 1 som börjar och slutar vid samma vertex. I figuren bildar hörnen 3, 2, 4, 3 en cykel med längd 3.

I många applikationer är det bekvämt att bifoga viss information till hörnen och bågarna i en digraf. För dessa ändamål används den taggade digraph , det vill säga en digraf där varje båge och/eller varje vertex har motsvarande etiketter. Etiketten kan vara ett namn, vikt eller värde (bågar), eller ett datavärde av någon given typ.

Exempel 2 av en märkt digraf:

DIV_ADBLOCK149 ">

3. Transitiv stängningsalgoritm (Warshalls algoritm):

För grafen G = (V, E) Algoritmen beräknar transitivitetsmatrisen T, varje element av vilket T[i, j] = 1 bara när det finns en stig från toppen i till toppen j och T[ i, j] = 0 annat.

4. Algoritm för att hitta mitten av en digraf:

Låt vara och - godtycklig vertex av en digraf G = (VE). Excentricitet (max borttagning) blast och definierad som

max (minsta väglängd från toppen w till toppen v }

w V

Digraph mitt G vertexet med minsta excentricitet kallas. Med andra ord är mitten av digrafen den vertex för vilken det maximala avståndet (väglängden) till andra hörn är minimalt.

Exempel: Mitten av digrafen är vertexet d

		Excentr-t

5. Algoritm för att korsa digrafen på djupet (djup-första sökning):

När man löser många problem relaterade till riktade grafer krävs en effektiv metod för systematisk korsning av hörn och bågar av digrafer. Denna metod är den så kallade djup-första sökning - generalisering av metoden för förbeställningsträdgenomgång. Djupsökning börjar med att välja startpunkten v räkna G, denna vertex är markerad med en etikett besökt (besökt). Sedan för varje vertex som gränsar till vertexet v och som inte har besökts tidigare tillämpas djup-först-sökning rekursivt. När alla toppar som kan nås från toppen v, kommer att "hedras" med ett besök, avslutas sökandet. Om några hörn inte har besökts, väljs en av dem och sökningen upprepas. Denna process fortsätter tills alla hörn i digrafen korsas G.

6. Algoritm för att konstruera ett djupt spännande träd i en graf:

När du korsar en graf med hjälp av djup-först-sökning leder bara vissa bågar till obesökta hörn. Sådana bågar som leder till nya hörn kallas trädbågar och form för grafen djup-först spännande skog – djupt spännande skog ... När man bygger en skog särskiljs också tre typer av bågar: omvända, direkta och tvärgående. Omvända bågar - sådana bågar som går från ättlingar till förfäder i den spännande skogen. Raka bågar bågar kallas som går från förfäder till sanna ättlingar, men som inte är trädbågar.

Bågar som förbinder hörn som varken är förfäder eller ättlingar till varandra kallas tvärgående bågar ... Om, när man konstruerar ett spännande träd, sönerna i en vertex är placerade från vänster till höger i ordningen för deras besök, och om nya träd också läggs till i skogen från vänster till höger, så går alla tvärgående bågar från höger till vänster .

Till exempel bågar D-> C och G-> D- tvärgående, båge C-> A- bakåt, det finns inga raka bågar.

När man korsar ett träd djupt är det ofta bekvämt att numrera topparna i den ordning som de besöks. Sådana nummer kallas djupnummer.

Digrafrepresentation:

§ Representation av en digraf med hjälp av en närliggande matris:

Adjacency-matris för digraf G - detta är en matris A storleken n n med booleska värden, där A[ i, j] = Sann om och bara om det finns en båge från vertexet i till vertex j. Ofta i närliggande matriser, värdet Sann ersätts med 1 och värdet falsk- till 0.

En generalisering av representationen av en digraf med hjälp av en närliggande matris kan betraktas som en representation av en märkt digraf som också använder en närliggande matris, men för vilken elementet A[ i, j] lika med bågetikett jag ->j. Om bågar från toppen i till toppen j inte finns, då värdet A [ i, j] kan inte vara värdet av någon giltig etikett, men kan betraktas som en "tom" cell.

Adjacency-matris för en märkt digraf (exempel 2):

§ Representation av en digraf med hjälp av närliggande listor:

Vertex adjacency list i kallas listan över alla hörn som gränsar till vertexet i, dessutom beställd på ett visst sätt. Digraph G kan representeras med hjälp av en array HUVUD(Titel) vars element HUVUD[i] är en pekare till vertexadjacency-listan i.

Operatörer av ATD "Orgraph":

De vanligaste operatorerna som utförs på riktade grafer inkluderar läsning av vertex- och bågetikett, vertex- och båginsättning och -radering och bågsekvensövergång.

För att se en uppsättning intilliggande hörn krävs följande tre operatorer.

1. FÖRSTA ( v) returnerar indexet för den första vertex som gränsar till vertex v. Om toppen v har inga angränsande hörn, då returneras en "noll" vertex noll.

2. NÄSTA ( v, i) returnerar indexet för vertexet som gränsar till vertexet v, efter indexet i. Om jag - detta är indexet för den sista vertex som gränsar till vertex v, sedan kommer den tillbaka noll.

3. VERTEX ( v,i) returnerar toppen med index i från uppsättningen av hörn som gränsar till v.

Övningar:

Givet en riktad graf (digraf):

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

Ett exempel på en frånkopplad graf:

Cykel (enkel) är en väg med (enkel) längd på minst 3 från valfri vertex till sig själv. Grafen kallas cyklisk , om den har minst en cykel. En sammankopplad acyklisk graf, som är ett "träd utan rot", kallas gratis träd . Den andra figuren ovan visar en graf som består av två sammankopplade komponenter, som var och en är ett fritt träd. Ett fritt träd kan göras till ett "vanligt" träd om någon vertex betecknas som en rot, och alla kanter är orienterade i riktningen från denna rot.

Lösa träd har två viktiga egenskaper:

1. Varje ledigt träd med antalet hörn n, n > 1 , har exakt n - 1 revben.

2. Lägger du till en ny kant på ett ledigt träd får du definitivt en cykel.

Låt vara G = (V, E) - kopplad graf där varje kant ( r, w) markerade med ett nummer med(v, w), som kallas revben kostnad . Spanning Tree räkna G kallas ett fritt träd som innehåller alla hörn V Greve G. Pris spännträdet beräknas som summan av kostnaderna för alla kanter som ingår i detta träd

Grundläggande algoritmer för bearbetning av oriktade grafer:

1. Minsta kostnad som omfattar trädkonstruktion (Prims algoritm):

Många toppar byggs U från vilket det spännande trädet "växer". Låt vara V = (1, 2, ...,n}. I början U = (1). Vid varje steg i algoritmen hittas en lägsta kostnadskant ( u, v) Så att u U och v V \ U sedan topp v förs över från uppsättningen V \ U i en mängd U... Denna process fortsätter tills uppsättningen U kommer inte att vara lika med uppsättningen V.

Den spännande trädkonstruktionssekvensen ges nedan.

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

3. DFS-genomgång av oriktade grafer:

Djup-först-sökning används för att systematiskt gå igenom alla hörn i grafen. Sökalgoritmen för djupet-först liknar algoritmen för att korsa hörnen på en digraf. Den senare används också för oriktade grafer, eftersom den oriktade kanten (v, w) kan representeras som ett par orienterade bågar v -> w och w -> v.

Djuppassering kan användas för att konstruera ett spännträd.

Grafen och det spännande trädet som erhålls genom att korsa dess hörn med hjälp av sökmetoden djup-först visas nedan:

4. Bredth First Search på oriktade grafer

En annan metod för att systematiskt korsa en grafs hörn kallas Utöka första sökningen . Det fick sitt namn på grund av det faktum att när man når under korsningen av någon vertex v vidare betraktar vi alla hörn som gränsar till vertexet v, det vill säga hörnen skannas "i bredd". Denna teknik kan också tillämpas på riktade grafer.

Precis som med djup-först-sökning skapar bredd-först-sökning en spännande skog när man korsar en graf. Om efter att ha nått toppen NS när man tittar på revbenet (x, y) vertex på inte har besökts tidigare, så anses denna kant vara trädkanten. Om toppen på har redan besökts, revbenet (x, y) kommer att vara en tvärkant, eftersom den förbinder hörn som inte är relaterade till varandra genom arv.

Breadth First Spanning Tree visas nedan.

Representation av en oriktad graf med hjälp av en närliggande matris:

För att representera oriktade grafer kan du använda samma metoder som för att representera riktade grafer, om den oriktade kanten mellan hörnen v och w ses som två orienterade bågar från vertexet v till toppen w och från toppen w till toppen v.

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

Representerar en oriktad graf med hjälp av närliggande listor:

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

1. Bygg:

lägsta kostnad som spänner över trädet med hjälp av Prims algoritm;

lägsta kostnad som spänner över trädet med Kruskals algoritm;

spännande träd efter djup-första sökning, med början från hörnen a och d;

spännande träd efter bredd-första sökning, med början från hörnen a och d.

2. Implementera Prim och Kruskals algoritmer.

3. Genomför att bygga ett spännträd med hjälp av djup-först-sökning

§ för en oriktad graf representerad av en närliggande matris,

§ för oriktad graf representerad av angränsande listor.

4. Implementera spännträdskonstruktion med Breadth First Search

§ för en oriktad graf representerad av en närliggande matris,

§ för oriktad graf representerad av angränsande listor.

Ministeriet för utbildning och vetenskap i Ryska federationen

Federal State Budgetary Education Institute

högre yrkesutbildning

NATIONELLT FORSKNING NUCLEAR UNIVERSITY "MEPHI"

Dimitrovgrad Engineering Technological Institute

Avdelning Informationsteknologi

Att erkänna skydd "" 2012

Huvud stol Rakova O.A.

Kursarbete

genom disciplin"Objektorienterad programmering"

Tema:"Abstrakta datatyper. Listor"

Genomförd: student gr. VT-31

Shayakov A.F.

Ledare: Art. lektor vid IT-avdelningen

Alenin V.A.

Normregulator: Art. lektor vid IT-avdelningen

Alenin V.A.

Kvalitet:

Skyddsdatum:

Dimitrovgrad, 2012

Ministeriet för utbildning och vetenskap i Ryska federationen

Federal State Budgetary Education Institute

högre yrkesutbildning

NATIONELLT FORSKNING NUCLEAR UNIVERSITY "MEPHI"

Dimitrovgrad Engineering Technological Institute

för terminsuppsats

Disciplin: Objektorienterad programmering

Ämne: Abstrakta datatyper. Listor

Artist: Shayakov A.F.

Chef: V.A. Alenin

1. Teoretisk del:

Abstrakta datatyper. Objektorienterat programmeringskoncept. Linjära enkellänkade listor.

2.Praktisk del:

I C ++, skriv ett program med en objektorienterad struktur för att implementera linjära enkellänkade listor.

Villkor för slutförande av arbete enligt schema:

Teoretisk del - 15% av vecka 5

Praktisk del - 80 % senast vecka 7

Experimentdel - ____% med ____ vecka

Skydd - 100 % senast vecka 10

Krav för registrering:

Terminsuppsatsens avräkning och förklarande anteckning ska lämnas till elektroniska och papperskopior;

Rapportens volym måste vara minst 20 maskinskrivna sidor exklusive bilagor

RPZ är undertecknat av den person som ansvarar för tillsynskontrollen

Arbetsledare _________________

Entreprenör ____________________

Utgivningsdatum "_____" ___________ 2012

A.F. SHAYAKOV TEMA: ABSTRAKTA DATATYPER. LISTOR, Coursework / DITI, nr 230105.65-Dimitrovgrad, 2012. - 29 sidor, fig. 11, bibl. namn 10, bilaga 1.

Nyckelord: linjära enkellänkade listor, C++, objektorienterad programmering.

Forskningsobjektet är linjära enkelkopplade listor.

Syftet med arbetet är att studera linjära enkellänkade listor och skriva ett program i C++ med en objektorienterad struktur för deras implementering.

Slutsatser: i detta arbete har vi till fullo studerat linjära enkellänkade listor, såväl som metoderna för deras representation i minnet. Programmet skrivet på C++-språket överensstämmer helt med den objektorienterade strukturen, uppfyller sin huvuduppgift korrekt och effektivt - det implementerar linjära enkellänkade listor.

Inledning 6

1 Teoretisk del 7

1.1 Abstrakta datatyper. Linjära listor 7

1.2 Koncept för objektorienterad programmering 8

2 Praktisk del 15

3 Testning 23

Slutsats 25

Referenser 26

Bilaga A 27

Introduktion

Ofta, i processen att arbeta med data, är det omöjligt att avgöra hur mycket minne som krävs för att lagra dem; minne bör tilldelas under exekveringen av programmet efter behov i separata block. Block är länkade till varandra med hjälp av pekare. Det här sättet att organisera data kallas en dynamisk datastruktur eftersom den finns i en hög och ändrar storlek under programkörning.

Linjära listor används i detta arbete från dynamiska strukturer. En dynamisk struktur, till skillnad från en array eller post, kan uppta icke-angränsande områden av RAM.

Dynamiska strukturer används också i stor utsträckning för effektivare arbete med data, vars storlek är känd, speciellt för att lösa sorteringsproblem.

Ett element i en dynamisk struktur består av två delar: informativt, för lagringens skull strukturen skapas, och pekare som säkerställer kopplingen av element med varandra.

1. Teoretisk del

1.1 Abstrakta datatyper. Linjära listor

Abstrakta datatyper är nyckelbegrepp inom programmering. Abstraktion innebär separation och oberoende övervägande av gränssnitt och implementering.

Dataabstraktion innebär definition och övervägande av abstrakta datatyper (ADT) eller, vilket är samma sak, nya datatyper som matas in av användaren.

En abstrakt datatyp är en samling data tillsammans med många operationer som kan utföras på dessa data.

Linjära listor

I en linjär lista är varje post relaterad till nästa och möjligen den föregående. I det första fallet kallas listan helt enkelt ansluten, i det andra - dubbelt ansluten. Om det sista elementet är länkat med en pekare till det första, blir resultatet en cirkulär lista.

Varje objekt i listan innehåller en nyckel som identifierar objektet. Nyckeln är vanligtvis antingen ett heltal eller en sträng och är en del av datafältet. Olika delar av datafältet kan fungera som nyckel i arbetet med listan. Nycklarna för olika delar av listan kan vara desamma.

Du kan utföra följande operationer på listor:

initial bildning av listan (skapande av det första elementet);

lägga till ett objekt i slutet av listan;

läsa ett element med en given nyckel;

infoga ett element på en given plats i listan (före eller efter ett element med en given nyckel);

ta bort ett element med en given nyckel;

beställa listan med nyckel.

För att arbeta med en lista i ett program måste du definiera en pekare till dess början. Du kan också föra pekaren till slutet av listan för att göra det lättare att lägga till nya objekt i slutet av listan.

1.2 Begreppet objektorienterad programmering

Enligt Grady Booch, en auktoritet på objektorienterade programmeringsmetoder, "är objektorienterad programmering (OOP) en programmeringsmetodik som bygger på att representera ett program som en samling objekt, som vart och ett är en implementering av en viss klass ( typ av speciell typ), och klasser bildar en hierarki baserad på principerna för arv."

Objektorienterad metodik, liksom strukturell metodik, skapades med syftet att disciplinera processen att utveckla stora mjukvarupaket och därigenom minska deras komplexitet och kostnad.

En objektorienterad metodik eftersträvar samma mål som en strukturerad metodik, men den adresserar dem från en annan utgångspunkt och låter dig i de flesta fall hantera mer komplexa projekt än en strukturerad metodik.

Som ni vet är en av principerna för projektkomplexitetshantering nedbrytning. Grady Booch särskiljer två typer av nedbrytning: algoritmisk (som han kallar nedbrytning som stöds av strukturella metoder) och objektorienterad, vars skillnad, enligt hans åsikt, är följande: särskild betydelse för faktorer, som antingen orsakar handlingar eller är objekten. tillämpningen av dessa åtgärder”.

Med andra ord tar algoritmisk nedbrytning mer hänsyn till strukturen av relationer mellan delar av ett komplext problem, medan objektorienterad nedbrytning fokuserar mer på relationernas karaktär.

I praktiken rekommenderas det att använda båda typerna av nedbrytning: när du skapar stora projekt är det tillrådligt att först tillämpa ett objektorienterat tillvägagångssätt för att skapa en allmän hierarki av objekt som återspeglar kärnan i den programmerade uppgiften, och sedan använda algoritmisk nedbrytning till moduler för att förenkla utvecklingen och underhållet av mjukvarupaketet.

OO-programmering är utan tvekan ett av de mest intressanta områdena för professionell mjukvaruutveckling.

Objekt och klasser

De grundläggande byggstenarna i ett objektorienterat program är objekt och klasser. I sak kan ett objekt representeras som något känt eller föreställt och har ett väldefinierat beteende. Alltså kan ett föremål antingen ses eller röras, eller åtminstone veta att det till exempel representeras som information lagrad i datorns minne. Låt oss ge definitionen av ett objekt, i enlighet med GradiBuchs åsikt: "Ett objekt är en påtaglig enhet som tydligt manifesterar sitt beteende."

Ett objekt är en del av den verklighet som omger oss, det vill säga det existerar i tid och rum (för första gången introducerades begreppet objekt i programmering i Simula-språket). Formellt är objektet svårt att definiera. Detta kan göras genom vissa egenskaper, nämligen: ett objekt har tillstånd, beteende och kan identifieras unikt (med andra ord har ett unikt namn).

En klass är en uppsättning objekt som har en gemensam struktur och gemensamt beteende. En klass är en beskrivning (abstraktion) som visar hur man konstruerar en variabel av denna klass som finns i tid och rum, som kallas ett objekt. Innebörden av meningarna "beskrivning av klassvariabler" och "beskrivning av klassobjekt" är densamma.

Objektet har ett tillstånd, beteende och pass (medel för dess unika identifiering); objektens struktur och beteende beskrivs i de klasser där de är variabler.

Låt oss nu definiera begreppen tillstånd, beteende och identifiering av ett objekt.

Ett objekts tillstånd kombinerar alla dess datafält (statisk komponent, d.v.s. oföränderlig) och de aktuella värdena för vart och ett av dessa fält (dynamisk komponent, d.v.s. förändras vanligtvis).

Beteende uttrycker dynamiken i förändringar i ett objekts tillstånd och dess reaktion på inkommande meddelanden, d.v.s. hur ett objekt ändrar dess tillstånd och interagerar med andra objekt.

Identifiering (igenkänning) av ett objekt är en egenskap som gör att du kan skilja ett objekt från andra objekt av samma eller olika klasser. Identifiering utförs med hjälp av ett unikt namn (pass), som tilldelas objektet i programmet, precis som alla andra variabler.

Det har redan sagts ovan att det procedurmässiga (såväl som modulära) tillvägagångssättet tillåter en att bygga program som består av en uppsättning procedurer (subrutiner) som implementerar de givna algoritmerna. Å andra sidan representerar det objektorienterade tillvägagångssättet program som en samling objekt som interagerar med varandra. Interaktionen mellan objekt utförs genom meddelanden. Låt oss anta att vårt objekt är en cirkel. Då kan meddelandet som skickas till detta objekt vara: "rita dig själv." När vi säger att ett meddelande skickas till ett objekt, då anropar vi i själva verket någon funktion hos detta objekt (komponent-funktion). Så i exemplet ovan kommer vi att anropa en funktion som kommer att rita en cirkel på skärmen.

Inkapsling

Inkapsling är en av de grundläggande principerna för objektorienterad programmering, vars idé är att alla egenskaper och metoder kombineras i ett objekt.

Själva namnet på termen "inkapsling" kommer från det engelska ordet encapsulate, som ordagrant betyder "att försegla i en kapsel" eller "att täcka med ett skal". Ett objekt (kapsel) innehåller alltså metoder och egenskaper (innehåll).

Inkapsling kan ses i en vidare mening, långt bortom objektorienterad programmering i allmänhet. Om vi ​​talar om inkapsling på högsta möjliga abstraktionsnivå, så kan inkapsling ses som ett objekts förmåga att innehålla en mängd andra objekt. Så i förhållande till ett datorprogram kan vi säga att det kapslar in flera moduler, som var och en i sin tur kapslar in några objekt som kapslar in metoder och egenskaper, som för övrigt också kan vara objekt osv.

Baserat på allt ovan, kan en annan representation av inkapsling vara vilken trädstruktur som helst där vilken nod som helst i trädet inkapslar alla sina närmaste barn, som antingen kan vara löv (primitiver som inte kan kapsla in något i sig själva) eller andra noder.

Och ändå, om vi talar om objektorienterad programmering, så är inkapsling föreningen av data och metoder inom ett objekt.

Ibland talar man om inkapsling i objektorienterad programmering, begreppet inkapsling likställs med begreppet "black box" eller datadöljande, men de är inte samma sak. Ja, i vissa objektorienterade programmeringsspråk, med hjälp av inkapsling, kan utvecklaren göra sitt objekt till en svart låda, men detta implementeras med hjälp av åtkomstmodifierare, som inte är tillgängliga i alla objektorienterade programmeringsspråk. Själva begreppet inkapsling är mycket bredare. Och ännu mer än så kan vi göra alla egenskaper och metoder tillgängliga utifrån, det vill säga att det inte kan vara fråga om någon svart låda, men inkapsling kommer fortfarande att finnas i vilket föremål som helst. Att dölja data med hjälp av åtkomstmodifierare är därför en konsekvens av inkapsling, men är inte på något sätt identiskt lika begrepp.

För det första, tack vare inkapsling, är objekt inte längre bara användardefinierade datastrukturer, vars huvudsakliga syfte helt enkelt är att vara logiskt att kombinera flera separata datatyper inom ramen för en ny sammansatt datatyp. Tack vare inkapsling kan varje objekt nu innehålla data som beskriver objektets tillstånd och dess beteende beskrivet i form av metoder. Med andra ord har ett objekt i objektorienterad programmering upphört att vara en primitiv passiv datatyp, vars kontroll är helt beroende av den yttre miljön, men började ha sitt eget beteende, man kan till och med säga att någon vilja och sinne, förmågan att aktivt reagera på yttre påverkan och ändra dess tillstånd, och enligt sina egna lagar och regler.

För det andra ger inkapsling oss möjligheten att kontrollera tillgången till objektdata. Synlighetsbegränsning kan också ses som en manifestation av objektets egen vilja - objektet själv bestämmer vad av sitt beteende eller egenskaper som ska göras tillgängligt för alla, vad som ska göras tillgängligt endast för ett visst antal objekt och vad som ska göras helt intimt, som den inte känner till något annat föremål om. Varför, men för att bara objektet självt vet exakt hur man arbetar med det och hur inte. Du kan till och med säga om en ny programmeringsfilosofi, där objekt är mer på objekt över vilka vissa handlingar utförs, och, om jag får säga det, en ny form av abstrakt syntetiskt sinne, som interagerar med vilket du kan uppnå det önskade resultatet.

Och jag upprepar än en gång att det är tack vare inkapsling som ett objekt kan förses med någon vilja, förnuft, förmågan att reagera på yttre påverkan, och inte vara ett passivt datalager.

Arv

Arv är en av de fyra viktigaste mekanismerna för objektorienterad programmering (tillsammans med inkapsling, polymorfism och abstraktion), som låter dig beskriva en ny klass baserat på en befintlig (förälder) klass, samtidigt som moderklassens egenskaper och funktionalitet är lånade av den nya klassen.

Med andra ord implementerar den ärvda klassen specifikationen av en redan existerande klass (basklass). Detta gör att du kan behandla objekt av den ärvda klassen på samma sätt som med objekt i basklassen.

Arvstyper

Enkelt arv

Klassen som arvet härstammar från kallas bas eller överordnad (engelsk basklass). Klasser som härstammar från basen kallas ättlingar, ättlingar eller härledda klasser.

Vissa språk använder abstrakta klasser. En abstrakt klass är en klass som innehåller minst en abstrakt metod, den beskrivs i programmet, har fält, metoder och kan inte användas för att direkt skapa ett objekt. Det vill säga, du kan bara ärva från en abstrakt klass. Objekt skapas endast på basis av härledda klasser som ärvts från abstraktet.

Till exempel kan en abstrakt klass vara en basklass "universitetsanställd", från vilken klasserna "doktorand", "professor" etc. ärvs. Eftersom härledda klasser har gemensamma fält och funktioner (till exempel fältet "år). av födelse"), kan dessa klassmedlemmar beskrivas i basklassen. Programmet skapar objekt baserat på klasserna "graduate student", "professor", men det är ingen idé att skapa ett objekt baserat på klassen "universitetsanställd".

Multipelt arv

Med multipelt arv kan en klass ha mer än en förfader. I det här fallet ärver klassen alla förfäders metoder. Fördelen med detta tillvägagångssätt är större flexibilitet. Multipelarv är implementerat i C++. Andra språk som tillhandahåller denna förmåga inkluderar Python och Eiffel. Multipelt arv stöds i UML.

Multipelt arv är en potentiell källa till fel som kan uppstå på grund av förekomsten av samma metodnamn i förfäder. I språk som är positionerade som arvtagare av C ++ (Java, C #, etc.), beslutades det att överge multipelt arv till förmån för gränssnitt. Du kan nästan alltid klara dig utan att använda denna mekanism. Men om ett sådant behov ändå uppstår, för att lösa konflikter med att använda ärvda metoder med samma namn, är det till exempel möjligt att tillämpa synlighetsförlängningsoperationen - "::" - att anropa en specifik metod för en specifik förälder.

Ett försök att lösa problemet med förekomsten av samma metodnamn i förfäder gjordes på Eiffelspråket, där det, när man beskriver en ny klass, är nödvändigt att uttryckligen ange de importerade medlemmarna i var och en av de ärvda klasserna och deras namngivning i barnklassen.

De flesta moderna objektorienterade programmeringsspråk (C #, C ++, Java, Delphi, etc.) stöder möjligheten att samtidigt ärva från en förfaderklass och implementera metoder för flera gränssnitt med samma klass. Denna mekanism låter dig till stor del ersätta flera arv - gränssnittsmetoder måste åsidosättas explicit, vilket eliminerar fel när man ärver funktionaliteten för samma metoder från olika förfaderklasser.

1. Praktisk del

För att lösa detta problem används en objektorienterad programstruktur. Programmet representeras av två klasser och en huvud-cpp-fil som innehåller ett användargränssnitt för att underlätta arbetet med listor.

Klassen cList är en linjär, enkellänkad lista över objekt i klassen cElement.

Klassen cElement har följande struktur:

cElement * nästa;

~ cElement (tomt);

void setdata (int);

void setref (cElement *);

cElement * getref ();

Datafältet av typen int innehåller det numeriska värdet för listelementet, nästa fält av typen cElement * innehåller en länk till nästa element i listan. Metoderna setdata och getdata används för att komma åt klassens privata datafält för att få och följaktligen ställa in värdet på detta fält. Setref-metoden används för att sätta en länk från det aktuella till nästa objekt i listan, och getref används för att navigera till nästa objekt.

void cElement :: setdata (int sd)

int cElement :: getdata ()

returnthis-> data;

void cElement :: setref (cElement * rf)

cElement * cElement :: getref ()

returnthis-> nästa;

Implementeringen av dessa metoder är extremt enkel, vilket framgår av deras programkoder som presenteras ovan.

Låt oss nu titta på strukturen för klassen cList

#inkludera "cElement.h"

cElement * huvud;

void Lägg till (int);

void Insert (int, int);

void Ta bort (int);

void RemoveAll ();

Denna klass innehåller en länk till huvudelementet i listan - head, av typen cElement *. Lagring av denna länk är nödvändigt för korrekt utförande av operationer för att lägga till, radera data och skriva ut listan. Faktum är att, när du utför någon av ovanstående operationer, räknas listobjekten upp för att nå den önskade, eftersom listan inte har slumpmässig tillgång till elementen, därför är det mer rationellt att starta uppräkningen från " huvudet på listan. Förutom länken till början av listan kommer varje objekt i denna klass att ha ett elcount-fält som innehåller antalet element i listan.

Låt oss fortsätta vår undersökning av den här klassen genom att undersöka metoderna som implementeras i den för att arbeta med listor.

Lägg till metod - lägg till data i slutet av listan.

Som en parameter accepterar denna metod ett numeriskt värde (variabel xd), som måste lagras i det tillagda listobjektet.

void cList :: Lägg till (int xd)

Så här skapas ett nytt element och värdet på dess numeriska fält ställs in:

cElement * temp = newcElement;

temp-> setdata (xd);

Därefter kontrolleras antalet element i listan, om listan är tom skapas huvudelementet, annars den "vanliga" komponenten i listan:

if (elcount == 0)

temp-> setref (NULL);

temp-> setref (NULL);

p-> setref (temp);

Du kan märka att ovanstående konstruktion använder setref-metoden för klassen cElement, vilket är nödvändigt för att ställa in en länk till nästa element i listan, annars kommer listan att vara obunden, vilket är fyllt med dataförlust och felaktig programdrift.

Vid den första starten av programmet används metoden som beskrivs ovan för att sekventiellt lägga till objekt till listan, som du sedan kan arbeta med; för att stoppa inmatning på kommandoraden måste du ange kommandot "stopp" istället för det numeriska värdet av föremålet (se figur 1).

Figur 1 - Processen att lägga till objekt i listan

Efter att ha angett kommandot "stopp" skrivs listan ut och programmet går in i kommandovänteläge (se figur 2).

Figur 2 - Utskriven lista

Utskriftsmetod - skriver ut listan.

För utskrift är det viktigt att känna till början av listan för att sekventiellt skriva ut värdena för alla element i listan, så en länk till listans "huvud" ställs in i tempvariabeln, varefter faktumet att listan finns kontrolleras och motsvarande meddelande visas, om det inte bekräftas, om listan inte är tom, visas det:

void cList :: Skriv ut ()

cElement * temp = huvud;

om (temp == NULL) cout medan (temp! = NULL)

temp = temp-> getref ();

Del-metod - tar bort startelementet i listan.

För att ta bort det initiala elementet måste du först flytta länken till nästa komponent i listan, göra den till den första på detta sätt, och sedan ta bort det nödvändiga elementet:

voidcList :: Del ()

cElement * temp = huvud;

huvud = huvud-> getref ();

RemoveAll-metoden - tar bort hela listan.

Denna metod är baserad på ovanstående och består av att successivt radera de initiala elementen i listan tills hela listan raderas.

void cList :: RemoveAll ()

medan (elcount! = 0)

För att köra den här metoden anger du kommandot "dellist" i menyn för att arbeta med listan (se figur 3).

Figur 3 - Ange kommandot för att rensa listan

Och om användaren verkligen är säker på sina handlingar är det nödvändigt att acceptera programmets erbjudande, varefter hela listan kommer att raderas (se figur 4).

Figur 4 - Tom lista

Ta bort metod – tar bort ett specifikt objekt från listan.

Mindre radikal metod än den tidigare. Endast ett listobjekt som anges som en parameter tas bort. Detta sker enligt följande: programmet kontrollerar först korrektheten av den angivna parametern, om numret på det borttagna elementet är mindre än ett eller fler än det totala antalet element i listan, visar det ett felmeddelande, men om programmet har inga klagomål på den angivna parametern, överförs de nödvändiga länkarna för elementen som finns i närheten med den raderade, så att listan förblir länkad, varefter det nödvändiga elementet raderas.

void cList :: Ta bort (int del)

cElement * cur = huvud, * de;

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

huvud = huvud-> getref ();

medan (j! = del-1)

cur = cur-> getref ();

de = cur-> getref ();

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

coutsystem ("paus");

För att köra den här metoden anger du kommandot "radera" i menyn för att arbeta med listan. Ange sedan numret på elementet som ska raderas eller kommandot "back" för att avbryta borttagningen (se figur 5).

Figur 5 - Processen att ta bort ett listobjekt

Listan efter att ha tagit bort det fjärde elementet kommer att se ut så här (se figur 6).

Figur 6 - Lista efter borttagning av ett element

Infoga metod - infoga ett nytt objekt på en angiven plats i listan.

Denna metod tar som parametrar: positionen för det tillagda elementet och dess numeriska värde. Det nya elementet kommer att stå exakt på den angivna platsen, sålunda kommer elementen till höger om det nuvarande att flyttas med en position. När du lägger till ett nytt element i början av listan behöver du bara överföra länken från detta element till nästa, och därigenom länka listan och tillhandahålla en länk till det initiala elementet. En något annorlunda situation uppstår när du lägger till ett nytt element mellan två redan befintliga, för detta, med hjälp av en slinga, gå till elementets insättningspunkt och associera sedan komponenterna till höger och vänster om det med det nya elementet. När allt kommer omkring, vad måste till exempel göras om det är nödvändigt att förlänga kedjan: du måste öppna den, fäst sedan en ny länk på den första delen av kedjan, fäst den andra på samma länk, något liknande implementeras i denna metod. Det är värt att notera att om du anger en felaktig position för att lägga till, som är mindre än ett eller fler än det totala antalet element, kommer programmet att visa ett lämpligt felmeddelande.

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

cElement * cur = huvud;

cElement * temp = nytt cElement;

temp-> setdata (val);

om ((pos> = 1) && (pos

temp-> setref (huvud);

medan (j! = pos-1)

cur = cur-> getref ();

p = cur-> getref ();

cur-> setref (temp);

temp-> setref (p);

coutsystem ("paus");

För att köra den här metoden anger du kommandot "infoga" i menyn för att arbeta med listan. Ange sedan positionen och det numeriska värdet för det tillagda elementet eller kommandot "tillbaka" för att avbryta borttagningen (se figur 7).

Figur 7 - Processen att infoga ett element

Efter att ha lagt till ett element med värdet 111 till den tredje positionen kommer listan att se ut så här (se figur 8).

Figur 8 - Lista efter att ha lagt till ett element

Under beskrivningen nämndes menyn för att arbeta med listan mer än en gång, det återstår att notera att denna meny avsevärt underlättar arbetet med listan. Algoritmen för dess arbete består i ett cykliskt anrop av samma metoder, att skriva ut en lista, till exempel, tills ett visst kommando anges. Listan över tillgängliga kommandon kan ses genom att skriva "hjälp" i konsolen (se figur 9)

Figur 9 - Tillgängliga kommandon

Den fullständiga menykoden visas i bilaga A.

1. Testning

Ofta under arbetets gång uppstår situationer i samband med felaktig datainmatning, vilket kan göra att programmet misslyckas. Naturligtvis måste varje program implementera skyddsalgoritmer från en oerfaren användare, vilket förhindrar att programmet kraschar. Låt oss överväga hur sådana algoritmer fungerar i det skapade programmet.

Den första inmatningen av listan görs med följande kod:

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

Innan du anropar add-metoden för att lägga till ett nytt objekt i listan, kontrolleras inmatningssträngen. Atoi-funktionen konverterar en sträng till ett numeriskt värde och returnerar NULL om inmatningssträngen inte är ett tal. Sålunda, när du matar in, kommer alla rader som inte är siffror att ignoreras, förutom raden med kommandot att stoppa inmatning (se figur 10).

Figur 10 - Ange felaktiga uppgifter

Efter att ha angett sådan data kommer listan att se ut så här (se figur 11).

Figur 11 - Mottagen lista

Programmet fortsätter att fungera korrekt efter, även efter att ha angett felaktiga data. Liknande metoder för att hantera felaktiga data används för resten av inmatningsoperationerna i programmet.

Slutsats

I detta arbete erhölls koncept om abstrakta datatyper, om principerna för deras representation i moderna programmeringsspråk, i C++ i synnerhet. I de flesta moderna imperativspråk är huvudkonceptet som används för att beskriva abstraktioner i programkod det objektorienterade tillvägagångssättet. Objektorienterad programmering (OOP), liksom det ADT-baserade förhållningssättet till programmering, är till viss del en utveckling av idéer om modulär programmering. Moduler är programkomponenter som har två viktiga egenskaper:

Moduler döljer implementeringsdetaljer.

Moduler kan återanvändas i olika delar av programmet.

David Parnas, i sitt arbete från 1972, presenterade moduler som abstrakta maskiner som lagrar tillstånd inom sig själva och låter detta tillstånd ändras genom en specifik uppsättning operationer. Detta koncept är grundläggande, både för konceptet abstrakta datatyper och för objektorienterad programmering. Genom att dra paralleller mellan Parnas arbete och moderna OOP-koncept är det lätt att se sambandet mellan begreppen klass och modul.

I detta arbete representeras linjära enkellänkade listor, som är en abstrakt datatyp, av de utvecklade modulerna, för att komma åt tillstånden för vilka specialoperationer också är implementerade, kallade metoder i objektorienterad programmering.

Bibliografi

1. Ian Graham Objektorienterade metoder. Principer och praktik = Objektorienterade metoder: Principer och praktik. - 3:e uppl. - M .: "Williams", 2004. - S. 880.

2. Anthony Sintes Mästare objektorienterad programmering på 21 dagar = Sams Lär dig själv objektorienterad programmering på 21 dagar. - M .: "Williams", 2002. - S. 672.

3. Bertrand Meyer Objektorienterad design av mjukvarusystem + CD. Internet University of Information Technologies - INTUIT.ru, rysk upplaga, 2005

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

5. "Nya programmeringsspråk och tendenser för deras utveckling", V. Ushkova, 2005

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

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

8. Bjarne Stroustrup "Programmeringsprinciper och praxis för att använda C++". "ID Williams", 2011, ISBN 978-5-8459-1621-1 (ryska)

9. Grady Booch et al. "Object Oriented Analysis and Design with Sample Applications" 2:a eller 3:e upplagan. Binom, Nevskij-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 "Att använda C ++ effektivt. 50 bästa metoder för att förbättra dina program och projekt" DMK, Peter, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1

Bilaga A

Menyprogramkod

#include "cList.h"

#inkludera "string.h"

använder namnutrymme std;

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

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

system ("cls");

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

coutmylist.Print ();

if (strstr (com, "hjälp")! = NULL) com_ind = 1;

if (strstr (com, "lägg till")! = NULL) com_ind = 2;

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

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

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

switch (com_ind)

system ("cls");

system ("cls");

coutcoutcoutcoutcoutcoutcoutcoutcom_ind = 0;

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

if (atoi (ss)! = NULL)

mylist.Add (atoi (ss));

system ("cls");

// infoga element

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

if (atoi (ss)! = NULL)

system ("cls");

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

if (atoi (ss)! = NULL)

mylist.Infoga (pos, atoi (ss));

system ("cls");

// ta bort element

if (strstr (ss, "tillbaka") == NULL) definieras av en uppsättning värden given och en uppsättning operationer ... sammankopplade strukturer data – listor... Strukturera dataÄr en samling av element data, mellan vilka ... i datorns minne kallas abstrakt eller logiskt. Oftare...

Flera olika sorts data... Uppsättningarna

Föreläsning >> Datavetenskap, programmering

... sorts liknar enkel typer data... Flertal typer beskrivs i avsnitt typer... WU kan beskrivas. Abstrakt beräkningsstrukturer som beskriver input ... andra fall typer alla komponenter lista måste matcha typ filkomponenter. ...

Objektorienterade databaser data arbetar i distribuerade nätverk

Sammanfattning >> Informatik

Utveckla områden av programmeringsspråk med abstrakt typer data och objektorienterade programmeringsspråk. ... typer data- lista och array. Varje bokstavlig identifieras unikt av ett index i arrayen och en ordinal in listan ...

Abstrakt informationssäkerhetsmodeller

Sammanfattning >> Informatik

Informationsskydd ……………………………………………… ..17 Abstrakt informationssäkerhetsmodeller ... styr interaktioner med båda typer data(Certifieringsregler): Alla ... olika varianter och tillägg till befintliga listan... Säkerhetsnivåer - vissa ...

Abstrakt datatyp

Abstrakt datatyp (ATD)är en datatyp som tillhandahåller en viss uppsättning funktioner för att arbeta med element av denna typ, samt möjligheten att skapa element av denna typ med hjälp av specialfunktioner. Hela den interna strukturen av denna typ är dold för mjukvaruutvecklaren - det här är abstraktionens kärna. En abstrakt datatyp definierar en uppsättning implementeringsoberoende funktioner av typen som fungerar på dess värden. De specifika implementeringarna av ADT kallas datastrukturer.

I programmering är abstrakta datatyper vanligtvis representerade som gränssnitt som döljer motsvarande typimplementationer. Programmerare arbetar med abstrakta datatyper uteslutande genom sina gränssnitt, eftersom implementeringen kan förändras i framtiden. Detta tillvägagångssätt är förenligt med principen om inkapsling i objektorienterad programmering. Den starka punkten med denna teknik är implementeringsdöljande. När endast gränssnittet är publicerat utanför, kommer alla program som arbetar med den givna strukturen för den abstrakta datatypen att fortsätta att fungera så länge som datastrukturen stöder detta gränssnitt. Utvecklarna av datastrukturer försöker, utan att ändra det externa gränssnittet och semantiken för funktioner, att gradvis förfina implementeringarna, förbättra algoritmerna när det gäller hastighet, tillförlitlighet och använt minne.

Skillnaden mellan abstrakta datatyper och datastrukturer som implementerar abstrakta typer kan illustreras av följande exempel. Den abstrakta datatyplistan kan implementeras med användning av en array eller en linjär lista med användning av olika dynamiska minnesallokeringsmetoder. Varje implementering definierar dock samma uppsättning funktioner som ska prestera samma (i prestanda, inte hastighet) för alla implementeringar.

Abstrakta datatyper låter dig uppnå modularitet av mjukvaruprodukter och har flera alternativa utbytbara implementeringar av en separat modul.

Exempel på ADT

se även

Länkar

• Lapshin V.A. Abstrakta datatyper i programmering

Wikimedia Foundation. 2010.

Se vad "Abstrakt datatyp" är i andra ordböcker:

abstrakt datatyp- En datatyp (abstrakt klass) definierad genom att räkna upp dess metoder och egenskaper, utan att skapa deras konkreta implementering. Informationsteknikämnen i allmänhet SV Abstrakt Data TypeADT ... Teknisk översättarguide

I programmeringsteori, vilken typ som helst vars värden är värden av någon annan typ, "lindad" av konstruktörer av en algebraisk typ. Med andra ord, en algebraisk datatyp har en uppsättning typkonstruktorer, som var och en ... ... Wikipedia

Heltal, heltalsdatatyp (eng. Integer), inom datavetenskap, en av de enklaste och vanligaste datatyperna inom programmeringsspråk. Tjänar till att representera heltal. Många siffror av denna typ representerar ... ... Wikipedia

Denna term har andra betydelser, se uppsättning (betydelser). En uppsättning, en typ och datastruktur inom datavetenskap, är en implementering av en matematisk objektuppsättning. Datatypuppsättning låter dig lagra ett begränsat antal värden ... ... Wikipedia

Vissa programmeringsspråk tillhandahåller en speciell datatyp för komplexa tal. Den inbyggda typen gör det enkelt att lagra och beräkna komplexa värden. Innehåll 1 Aritmetik över komplex 2 Stöd på språk ... Wikipedia

Denna term har andra betydelser, se Index. Pekardiagram En pekare (pekare) är en variabel vars värdeområde består av minnesadresser och ett speciellt värde på nolladressen. ... ... Wikipedia

En av typerna av algebraiska datatyper, som kännetecknas av det faktum att dess konstruktörer kan returnera värden som inte är av deras egen typ. Detta koncept är implementerat i flera programmeringsspråk, särskilt i ML- och Haskell-språken, och i ... ... Wikipedia

En egenskap är en abstrakt typ som används inom datavetenskap som "en enkel konceptuell modell för att strukturera objektorienterade program." Egenskaper liknar mixins, men kan innefatta definitioner av klassmetoder ... ... Wikipedia

Binärt träd, ett enkelt exempel på en förgrenad ansluten datastruktur. Datastruktur är en programenhet som tillåter lagring av ... Wikipedia

- (topptyp) i typteorin, ofta betecknad som bara en topp eller en "fast" symbol (⊤), en universell typ, det vill säga en typ som innehåller alla möjliga objekt i det önskade typsystemet. Den högsta typen kallas ibland ... ... Wikipedia