Kurt Nørmark ©
Department of Computer Science, Aalborg University, Denmark


September 2001

Abstract Previous lecture Next lecture Index References Contents

Emnet for denne lektion er arrays og lister. Vi tager udgangspunkt i de vigtige og klassiske egenskaber af disse begreber. Vi giver også oversigter over, og eksempler på de specifikke klasser i Java, som understøtter disse datastrukturer. I en senere lektion vil vi se på datasamlinger (collections) i Java, som kan betragtes som en generalisering af arrays og lister.

The concept array: Et array er en ordnet samling af dataelementer. Alle elementer har samme type. Elementerne tilgås via et indeks.

Indekset er et heltal, eller en værdi af en heltals-lignende type, som betegner en bestemt plads i samlingen.

Figure. En skitse af et array. Vi tænker på et array som en tabel. Tabellen går fra (er indiceret fra) min til max.

Karakteristik af arrays Slide Note Contents Index References

På denne side karakteriserer vi mere omhyggeligt det klassiske arraybegreb.

Vi opfatter et array som en abstrakt datatype, der repræsenterer en homogen tabel At array'et er homogent betyder at alle elementer har samme type Vigtige array-operationer: hent det i-te element gem et nyt objekt i i-te element Hent og gem operationerne er effektive, med konstant tidskompleksitet Opslag i et array sker direkte, uden nogen form for søgning eller gennemløb Et array kan have én eller flere dimensioner Et array har faste øvre og nedre grænser, og dermed en fast størrelse Underliggende lagres elementerne i et array konsekutivt Konsekutiv lagring indebærer at elementerne placeres i umiddelbar forlængelse af hinanden i maskinens arbejdslager Et array er en tabel, hvor alle elementer er af samme type. Homogenitetsegenskaben af arrays er relativ til programmeringssprogets regler for typesammenlignelighed. Homogenitetsegenskaben kan også ses som en kontrast til records, hvori felterne jo kan være af forskellige typer. Konstant tidskompleksitet af hent og gem operationerne betyder at uanset hvor stor array'et er tager det samme tid at hente eller gemme et element i tabellen, uanset hvilken plads (første, sidste, midterste osv.) i arrayet vi arbejder på Hvis man ønsker det kan man tænke på 'almindelige data' som 0-dimensionelle arrays. Éndimensionelle arrays er det mest almindelige. Flerdimensionale arrays kan opfattes som éndimensionalle arrays, hvor elementtypen er en arraytype (af dimension én mindre end den oprindelige arraytype) Kravet om fast størrelse af arrays kan forstås på flere måder: Det er statisk bestemmeligt, hvor stort et array skal være. Dvs. at inden programmet kører kan man bestemme, hvor grænserne for programmets arrays. Det er dynamisk bestemmeligt, hvor stort et array skal være. Størrelsen kan f.eks. afhænge af bruger-input. Men når et array først er allokeret, kan det ikke ændre størrelse. Det første alternativ afspejler det klassiske array begreb. Ved statisk at låse indeks intervallet af et array fast kan man generere den mest effektive kode for tilgang til array'et elementer. Det andet alternativ er mere fleksibel, idet størrelsen af et array kan gøres afhængig af andre data i programmet. Endelig er der variationer af array begrebet, som tillader at udvide indeksintervallet af et array på køretidspunktet. Ifølge vores karakteristik er en sådan datatype strengt taget ikke et array. Java's Vector begreb (som behandles nedenfor) er et eksempel på et dynamisk udvideligt 'array'. Et array kan implementeres som en konsekutiv mængde af lagerceller, hvor positionen af et element i array'et kan beregnes ud fra indekset. Det befordrer den konstante tidskompleksitet af de to fundamentale operationer: hent og gem på arrays. Med andre ord: hent og gem operationerne beregner positionen af et element i arrayet, og henter/gemmer dette element direkte, uden nogen som helst form for søgning eller gennemløb af arrayet. Det er vigtigt at slå fast, at denne garanterede effektivitet af de basale operationer på et array er et væsentlig karakteristika ved selve array ideen.

Arrays i Java Slide Note Contents Index References

Programmeringssproget Java har et iboende array begreb. Et array er et objekt, men der er særlig, sproglig understøttelse af array objekter i Java. Dette udmønter sig bl.a. i særlige syntaktiske konstruktioner, når man programmerer med Java's iboende array begreb

Program: Et typisk eksempel på erklæring af et array og umiddelbar array instantiering

ElementType[] arrayNavn = new ElementType [SIZE]

Arrays typeangives ved brug af betegnelsen ElementType[] Arrays opfører sig som objekter Arrays allokeres dynamisk ved brug af new operatoren Den øvre grænse angives med special syntaks: new ElementType[MAX_LIMIT] Det egentlige indeksinterval i et Java array går fra og med 0 til og med MAX_LIMIT-1 Der findes ingen Array klasse i JDK biblioteket Indeks intervallet af et array kan ikke ændres efter array objektet er allokeret Man kunne vælge at sige at arrays er objekter. Sandheden er nok snarere, at Java designerne forsøger at få arrays til at ligne objekter. Men et array 'objekt' er ikke en instans af en Array klasse. Og sproget omgærer arrays med tilstrækkeligt meget special syntaks til at man kan se, at arrays er specielle objekter. Hvis arrays var normale objekter, altså instanser af klassen array, ville instantieringen se således ud: Array arrayNavn = new Array(MAX_LIMIT); Vi ser, at vi ikke med denne syntaks kan angive elementtypen af array'et. Dette er naturligvis et problem! Hvad vi generelt mangler er muligheden for at typeparametrisere klassen Array med en elementtype. I nogle sprog - såsom C++ kalder man dette for templates. Nogle sprog har mulighed for en sådan typeparametrisering. Java vil givetvis blive udvidet med typeparametriserede klasser på et tidspunkt.

Java's iboende arrays kan opfattes som en effektiv, lavniveau facilitet der kan anvendes til at implementere array-lignende abstrakte datatyper på et højere niveau

Reference Vores første møde med Java arrays

Eksempler på arrays i Java Slide Note Contents Index References

Vi ser her på et antal simple eksempler på anvendelse af arrays i Java

Program: Et konkret eksempel på erklæring af et array bookShelf, som er en tabel med elementtypen Book (en klasse) og med indekstypen 0..BOOKSHELF_LIMIT-1

Book[] bookShelf = new Book [BOOKSHELF_LIMIT]

Program: Et Java program som tabellægger de første 12 tal af fakultetsfunktionen. I hovedprogrammet kan man slå op i tabellen

import cs1.*; class FakultetsDemo1{ static final int SIDSTE = 13; long[] fakultet = new long[SIDSTE]; static long[] lavFakultetsTabel(int indtil){ long[] ft = new long[SIDSTE]; ft[1] = 1; for (int i=2; i < indtil; i++) ft[i] = ft[i-1] * i; return(ft); } public static void main(String args[]){ long[] fakultet = lavFakultetsTabel(SIDSTE); int n; do { System.out.println("Opslå fakultet af (0 afslutter):"); n = Keyboard.readInt(); if (n > 0) System.out.println(fakultet[n]); } while (n != 0); } }

Program: Et sammenligneligt Pascal program til tabellægning af fakultetsfunktionen.

Program FakultetsProgram; {$Q+,R+} {overflow check, range check} uses crt; Const Sidste = 12; Type IndexType = 1 .. Sidste; HeltalsTabel = array[IndexType] of Longint; Var Fakultet: HeltalsTabel; n: integer; Procedure LavFakultetsTabel(indtil: IndexType; var FT: HeltalsTabel); var i: Integer; begin FT[1] := 1; for i := 2 to indtil do FT[i] := FT[i-1] * i end; begin LavFakultetsTabel(Sidste, Fakultet); repeat write('Opslå fakultet af (0 afslutter): '); readln(n); if n > 0 then writeln(Fakultet[n]) until n = 0 end.

Direkte notation for array objekter i Java Slide Note Contents Index References

Når vi arbejder med arrays, hvor elementtypen er primitive typer, er det ofte en fordel at benytte sig af muligheden for at initialisere et array på en mere direkte facon end ved en række assignments.

Der findes en direkte notation for array objekter i Java Denne notation kan kun anvendes i forbindelse med initialisering af et array Anvendelsesbegrænsningen indebærer, at den direkte array notation ikke kan anvendes generelt som et udtryk, der beregnes til et array objekt. Notationen kan kun forekomme i en erklæringssammenhæng, hvor en array variabel erklæres og efterfølgende initialiseres.

Program: Array erklæring hvor initialiseringen foregår med en direkte noteret array objekt

ElementType[] arrayNavn = {el1, el2, el3, ... eln}

Program: En variation af fakultetsprogrammet som benytter direkte notation for arrays.

import cs1.*; class FakultetsDemo3{ static final int SIDSTE = 13; static int fak(int n){ return n == 0 ? 1 : n * fak(n-1); } public static void main(String args[]){ long[] fakultet = {0,fak(1),fak(2),fak(3),fak(4),fak(5),fak(7), fak(8),fak(9),fak(10),fak(11),fak(12)}; int n; do { System.out.println("Opslå fakultet af (0 afslutter):"); n = Keyboard.readInt(); if (n > 0) System.out.println(fakultet[n]); } while (n != 0); } }

Flerdimensionelle arrays i Java Slide Note Contents Index References

På denne side vil vi kort se på arrays af mere end én dimension i Java.

Arrays af flere dimensioner laves ved at lade elementtypen være et array. Konsekvensen af denne fremgangsmåde er at rækkerne i et to dimensionelt array kan være af forskellig længde.

Program: Eksempel på 'ikke rektangulært' todimensionelt array. Man skal lægge mærke til erklæringen af array'et triangular, hvor vi angiver antallet af elementer i første dimension. Initialiseringen af triangular foregår i en static block, som vi studerede i en tidligere lektion. Hvert element er af typen int[], altså et array af heltal. Vi laver de enkelte 'rækker' i variablen row, og vi assigner disse rækker til triangular[0] ... triangular[9].

class MultidimArray { public static final int ROWMAX = 10; public static int[][] triangular = new int[ROWMAX][]; static int[] row; static { for(int i = 0; i < ROWMAX; i++){ row = new int[i+1]; for (int j = 0; j <= i; j++){ row[j] = i*j; } triangular[i] = row; } } public static void main(String[] args){ for(int i = 0; i < ROWMAX; i++){ for (int j = 0; j <= i; j++){ System.out.print(triangular[i][j] + " "); } System.out.println(); } } }

Program: Output fra ovenstående program.

0 0 1 0 2 4 0 3 6 9 0 4 8 12 16 0 5 10 15 20 25 0 6 12 18 24 30 36 0 7 14 21 28 35 42 49 0 8 16 24 32 40 48 56 64 0 9 18 27 36 45 54 63 72 81

Fleksible arrays i Java: Vectorer Slide Note Contents Index References

Java indeholder en klasse, som kaldes Vector. Et Vector objekt ligner et array objekt. En Vector er dog på flere måder mere fleksibel end et Array. Vi sætter fokus forskellene mellem Java's Array og Vector begreb på denne side. Bemærk at Vector klassen nu er forældet i Java. Man bør således ikke bruge den længere. Brug derimod en Collection klasse, f.eks. ArrayList, jf. den tilknyttede henvisning.

Program: Et typisk eksempel på erklæring af et en vector og umiddelbar Vector instantiering. Erklæring og instantiering af en Vector foregår præcist som for andre objekter. Bemærk at elementtypen af en vector ikke angives eksplicit. Parameteren til konstruktoren spiller samme rolle som MAX_LIMIT i array erklæringen.

Vector vectorNavn = new Vector(INITIEL_KAPACITET)

Vi karakteriserer nu Vector klassen i Java, og vi sammenligner med Java's iboende Arrays

Elementtypen af Vector er altid Object Elementtypen af Array kan være mere specialiseret Elementer i en Vector skal være objekter - værdier skal 'wrappes' Værdier kan gemmes direkte i et Array Størrelsen af en Vector kan udvides under programudførelsen Størrelsen på et array låses fast på Array instantieringstidspunktet Flere operationer i Vector klassen skubber elementer frem eller tilbage i tabellen Tilsvarende operationer i Array klassen overskriver elementer Vector understøtter operationer som søger efter et element i tabellen I et Array tilgås elementer altid ved tabelopslag via et indeks Klassen Object er roden i Java's klassehierarki. Object er således den mest generelle klasse i Java systemet. Alle klasser er Object klasser. Vi minder om, at tal, tegn, og booleans er værdier i Java. Når vi wrapper sådanne værdier bliver de indlejret i et objekt. Operationerne, som skubber elementer i en Vector er insertElementAt og removeElement. Vil man søge i et array må man programmere det fra situation til situation. Man skal være opmærksom på, at søgning i en stor Vector kan være ineffektiv i forhold til opslag i et Array. Array opslag er altid af konstant tidskompleksitet, mens søgning i en Vector må forventes at være af lineær tidskompleksitet (lineær søgning). Søgning efter data i en Vector foregår med bl.a. operationerne contains, indexOf og removeElement.

References Klassen Vector i pakken java.util Værdier i forhold til objekter Collections som erstatning af Vector

Eksempler på brug af Vector i Java Slide Note Contents Index References

Vi ser her på eksempler, hvor Java Vectorer er brugt i stedet for arrays

Program: Et program som demonstrerer brugen af klassen Vector i et Java program. En mængde af strenge opbevares i leksikografisk orden i vektoren store. Når vektoren er fyldt op forstørres den automatisk. Den starter med plads til 5 elementer, og den forstørres med 5 elementer ad gangen, jf. konstruktoren. I proceduren insert søger vi frem i vektoren. Når vi når indsættelsepunktet indsættes den nye streng med 'insertElementAt'. Dette kald skubber strengene efter indsættelsepunktet ét trin frem.

import java.util.Vector; import oopcourse.util.Console; class VectorDemo1 { static Vector store = new Vector(5,5); /** Insert element in v, such that v remains sorted */ static void insert(String element, Vector v){ int i = 0; while (i < v.size() && ((String)v.elementAt(i)).compareTo(element) < 0 ) i = i + 1; v.insertElementAt(element,i); } public static void main(String[] args){ String str; do{ str = Console.readString("Type a string to be inserted: " + "(empty string terminates): "); if (str != ""){ insert(str,store); System.out.println(store); } } while (str != ""); } }

Exercise 5.1. Opgave i forlængelse af Vector eksemplet

Denne opgave tager udgangspunkt i programmet, som viser brugen af en Vector til indsættelse af strenge i sorteret rækkefølge. Modificer programmet således at strengene i Array'et args, som altid er parameter til hovedprogrammet main, indsættes i variablen 'store' inden de af brugeren indtastede strenge bliver indsat. Se dernæst på det logiske udtryk, som styrer while løkken i proceduren insert: i < v.size() && ((String)v.elementAt(i)).compareTo(element) < 0 Studér først operator prioriteterne af '<' og '&&' og forklar hvorfor der ikke er parenteser om 'i < v.size()'. Vær dernæst sikker på at I forstår String operationen compareTo (slå den op i klassen java.lang.String). Pt. er der ingen løsning til denne opgave

Java 1.2 tilbyder en række meget fleksible Collection klasser som helt heller delvist kan afløse brugen af Vector klassen Vi ser på Collections i en senere lektion

The concept associativt array: Et associativt array er et array hvor indekserne (nøglerne) ikke blot er heltal, men vilkårlige objekter, eksempelvis strenge

Et associativt array kendetegnes ved at vi kan indicere med værdier eller objekter, som er mere generelle end ordinaltyperne integer, char mv. Som navnet antyder er et associativt array velegnet til at associere to objekter, lad os sige o1 og o2, til hinanden. Givet o1 kan man via det associative array slå det associerede objekt o1 op

Figure. En skitse af et associativt array hvor nøgleobjekterne indicerer obj objekterne

Der er ikke nødvendigvis nogen naturlig rækkefølge af elementerne i et associativt array I modsætning til et almindeligt array som altid lagres i indeks orden Det er som oftest nødvendigt at lagre nøgleobjektet sammen med det associerede objekt I modsætning til et almindeligt array hvor indekser ikke lagres i array'et Det er en udfordring at implementere effektiv tilgang til elementerne i et associativt array I modsætning til et almindeligt array hvor effektiv tilgang er let at implementere Nøgleobjektet skal lagres sammen med det associerede objekt for, under opslag i det associative array at kunne erkende, om man står ved det rigtige element

Associative arrays implementeres typisk som såkaldte hashtabeller Hashtabeller behandles på kurset Algoritmik

Exercise 5.2. Opgave om associative arrays

Denne opgave har til formål at få erfaringer med associative arrays, ala Java's HashTabel. Lav et program der på en naturlig måde associerer elementer i mængden af tekststrenge, som repræsenterer heltal, til elementer i mængden af heltal. Eksempelvis skal strengen 'en' associeres til 1, 'to' til 2, 'enogtyve' til 21, osv. Associeringen skal foretages på baggrund af indtastninger foretaget af brugeren af programmet. Brugeren af programmet angiver altså par af tekstrenge og tal, som associeres. På baggrund af de registrerede associeringer kan brugeren slå talværdien op af en given en tekstreng, som repræsenterer tallet. Programmet skal benytte et associativt array til formålet. Konkret anbefales det at benyttet en Hashtabel, java.util.HashTable i denne opgave. Pt. er der ingen løsning til denne opgave

Reference Klassen Hashtable i pakken java.util

Figure. En liste men 6 elementer. Med denne måde at tegne listen på understreger vi at den indbyrdes rækkefølge af elementer er væsentlig. Vi giver også samtidig et hint til en typisk repræsentation af lister

En liste er en abstrakt datatype som tillader os at registrere en bestemt rækkefølge af et antal homogene elementer. Vigtige liste-operationer: Indsættelse af nyt element i listen Sletning af eksisterende element fra listen Navigering til et naboelement i listen Aflæsning af et nærmere angivet element i listen Der er flere mulige repræsentationer af lister: Her vil vi koncentrere os om sammenkædede lister Vi har forsøgt at fastslå de vigtige og karakteristiske operationer på lister. Indsættelse og sletning tillader os manipulere rækkefølgen af elementer. Hvis vi sammenligner med array-typen kan vi notere os, at der er fundamentale forskelle, idet rækkefølgen af array-elementer i bund og grund er fastlagt på det tidspunkt, tabellen skabes. (At vi kan simulere ændringer af rækkefølgen af array-elementer ved at skubbe og ombytte indholdet er tabellens elementer er en anden sag). Navigering til naboelementer er også fundamentalt for lister. På dette niveau af diskussionen vil vi ikke fastlægge nøjagtigt hvilken navigering der er tale om, og ej heller hvordan resultatet af navigeringen manifesterer sig. Men i alle typer af lister vil vi kunne navigere til næste element i listen. (I mange liste typer kan vi også komme afsted med at navigere til forrige element i listen). Endelig må vi have en eller anden måde at aflæse elementer fra listen. Aflæsning hænger ofte sammen med navigering, således at vi kan aflæse det element, hvortil vi har bevæget os. I forhold til arrays ser vi følgende væsentlige forskelle: Der er ingen fast øvre grænse på antallet af elementer Der er typisk ikke effektiv og direkte tilgang til elementerne i listen Elementerne i listen lagres ikke konsekutivt (altså ikke i hinanden følgende lagerceller i maskinens arbejdslager).

Enkeltkædede lister Slide Note Contents Index References

Vi studerer her den 'klassiske' enkeltsammenkædede liste.

Figure. En enkeltsammenkædet liste. Den udefra kommende reference peger på det første element i listen.

The concept kæde-objekt: Kæde-objekterne er de objekter, som sammenknytter data-objekterne og evt. nabo kædeobjekter		Kæde-objekterne udgør den indre 'infrastruktur' af en kædet liste. Et kædeobjekt aggregerer to informationer: referencen til et dataobjekt og en reference til det efterfølgende kædeobjekt. Klienterne af en kædet liste bør ikke have kendskab eller adgang til kæde-objekterne
The concept data-objekt: Data-objekterne er de objekter, som er indsat i listen		Data-objekterne er de objekter, som programmøren håndterer, og som indsættes i listen
The concept hægte: Hægterne er pointere som udgår fra kæde-objekterne		Hægterne er referencer mellem objekterne indbyrdes. Hægterne knytter kæde-objekterne sammen indbyrdes, ligesom hægterne knytter forbindelsen mellem kæde- og data-objekterne

Program: Klassen Linkable som repræsenterer kæde-objekterne. Der er tre forskellige konstruktorer, som gør det fleksibelt at konstruere et kæde-objekt ud fra viden om både datafeltet og next feltet, kun om data feltet, eller ingen af delene. Ud over disse konstruktorer er der selektorer og mutatorer af de to felter. Datarepræsentationen er privat.

class Linkable { private Object data; private Linkable next; /** Return a Linkable object with null references in both data and next */ Linkable(){ data = null; next = null; } /** Return a Linkable object with null references in next, and the parameter as data */ Linkable(Object data){ this.data = data; this.next = null; } /** Return a Linkable object with first parameter as data and second parameter as next */ Linkable(Object data, Linkable next){ this.data = data; this.next = next; } /** Return the data of this Linkable object */ Object data(){ return (data); } /** Return the reference to the next Linkable */ Linkable next(){ return (next); } /** Set the data field of this Linkable object */ void setData(Object data){ this.data = data; } /** Set the next field of this Linkable object */ void setNext(Linkable next){ this.next = next; } } // Linkable

Indsættelse af et element i en kædet liste Slide Note Contents Index References

Vi går nu over til at studere vigtige operationer på en kædet liste. Vi starter med indsættelse i en enkeltkædet liste

I objekt-orienteret programmering ønsker vi at bort-abstrahere detaljerne om, hvordan man manipulerer hægterne under indsættelse af elementer i listen

Image series: Skridt i indsættelse af et element i en kædet liste.

Skridt i indsættelse af et element i en kædet liste.

Image no. 1. Et nyt element ønskes indsat på pilens plads

 

Image no. 2. Der er lavet et nyt kæde-objekt som skal kædes ind i listen efter den blå pil

 

Image no. 3. Vi fastholder en reference til elementet efter det nye element

 

Image no. 4. Der laves en reference til det nye element

 

Image no. 5. ... og videre fra det nye element til resten af listen, via det huskede element

 

Indsættelse af et nyt første element i listen udgør et specialtilfælde

Sletning af et element fra en kædet liste Slide Note Contents Index References

I objekt-orienteret programmering ønsker vi at bort-abstrahere detaljerne om, hvordan man manipulerer hægterne under sletning fra en kædet liste

Image series: Skridt i sletning af et element fra en kædet liste.

Skridt i sletning af et element fra en kædet liste.

Image no. 1. Data-objektet som er markeret med et kryds ønskes slettet

 

Image no. 2. Kæde-objektet markeret med den blå pil skal ændres for at udføre sletningen

 

Image no. 3. Data-objektet som er markeret med et kryds er fjernet fra den kædede liste. Kæde-objektet såvel som data-objektet kan nu fjernes af garbage collectoren

 

Image no. 4. Situationen efter at kæde- og data-objekt er fjernet af garbage collectoren

 

Sletning af det første element i listen udgør et specialtilfælde

Identitet af lister: Listen som objekt. Slide Note Contents Index References

Vi går nu over til at se på objekter, der repræsenterer listen som så

En liste er mere end samlingen og rækkefølgen af elementer: En liste har identitet i sig selv Det er fristende at identificere en liste med det første element. Dermed mener vi, at når vi refererer til listen sker det via en reference til det første element i listen. Listesprog ala Lisp fungerer på denne måde. Men dette er for simpelt. Problemerne opstår hvis vi sletter det første element, eller hvis vi indsætter et nyt første element. I tilfælde af sletning kan vi let miste referencer til listen (idet alle de steder, som refererer til det første element vil komme til at referere til det slettede element). I tilfælde af indsættelse vil allerede eksisterende referencer til liste ikke inkludere det nye første element. Dette er noget rod. Problemet skyldes ene og alene, at vores listeidentitet er for svagt

Figure. Listen repræsenteres her af ét objekt, som refererer til det første kæde-objekt. Liste objektet kan indeholder referencer til andre kæde-objekter, f.eks. det sidste (ikke vist). Endvidere kan liste objektet repræsenteres anden information om listen, f.eks. antallet af elementer i listen (antydet med 5-tallet)

Image series: Forskellige mulige situationer og illustrationer af liste identitet.

Forskellige mulige situationer og illustrationer af liste identitet.

Image no. 1. En liste hvor klienter af listen blot refererer til listens første kædeobjekt. Hermed bringes kæde-objekterne til omgivelsernes kendskab, hvilket er uheldigt. Endvidere opstår der store problemer hvis det første element slettes, eller hvis der indsættes et nyt første element

 

Image no. 2. Alle referencer til listen er via liste objektet. Uanset om listen er tom, eller om listen består af et eller flere objekter, vil objektet 'enListe' repræsentere listen. Der opstår ikke problemer hvis første element slettes, eller hvis der indsættes et nyt første element

 

Image no. 3. Et alternativt billede, hvor liste objektet omslutter kædeobjekterne og dataobjekterne. Kædeobjekterne (instanserne af Linkable) er indeholdt i Listeobjektet, svarende til at Linkable klassen er en indre klasse i Liste klassen.

 

Indsættelse og sletning af første element i en liste uden identitet Slide Note Contents Index References

Her vil vi illustrere hvor galt det kan gå når man indsætter eller sletter det første element i en liste uden identitet.

Indsættelse og sletning af første element i en liste uden identitet skaber store problemer

Image series: Problemer ved indsættelse af et nyt første element i en liste uden identitet.

Problemer ved indsættelse af et nyt første element i en liste uden identitet. Denne problemstilling er en del af motivationen for at introducere et objekt, der repræsenterer listen.

Image no. 1. Vi forestiller os at vi via reference r1 skal indsætte det nye, røde element i listen. Læg mærke til, at vi har flere andre referencer til listen

 

Image no. 2. Vi har nu indsat det nye element i listen, og r1 refererer til det. Listen ser fin ud via r1 referencen, men via r2 og r3 kan vi ikke erkende at der er indsat et nyt element

 

Image series: Problemer ved sletning af det første element uden identitet.

Problemer ved sletning af det første element uden identitet.

Image no. 1. Vi ønsker at slette det første element via referencen r1.

 

Image no. 2. Når vi tilgår listen via referencen r1 er det første element slettet. Men via r2 og r3 eksisterer elementet stadigvæk. (Alternativt peger r2 og r3 kun på det første element, som vi har ønsket slettet. Dette er tilfældet hvis vi har nulstillet pointeren fra e1 til e2)

 

Java programeksempler Slide Note Contents Index References

Lad os her se på et konkret eksempel på en meget simpel, men ikke desto mindre nyttig kædet liste programmeret til lejligheden i Java. Klasserne er ikke perfekte - endnu. Vi vil gradvis repararere uhesigtsmæssigheder i løbet af lektionen

Vi ser på en enkeltkædet liste hvor al indsættelse og sletning foregår i forenden af listen.

Program: Klassen LinkedList. Klassen afhænger af Linkable, som vi tidligere har vist. Datamæssigt holder vi styr på det første element og længden (private instansvariable). Konstruktoren laver en tom liste. Metoderne insertFirst og deleteFirst indsætter og sletter første element i listen. Metoden firstLinkable returnerer det første kædeobjekt. Som vi vil se senere er dette en problematisk beslutning, idet vi dybest set ikke ønsker at afsløre detaljer om lister's interne infrastruktur (altså sammmenkædningen).

/** A simple linked list which reveals the Linkable object in a unsatisfactory manner */ public class LinkedList { private Linkable firstLinkable; private int length; public LinkedList(){ // make empty list firstLinkable = null; length = 0; } public void insertFirst(Object element){ Linkable newFirst = new Linkable(element, firstLinkable); firstLinkable = newFirst; length = length + 1; } public void deleteFirst(){ if (length > 0){ firstLinkable = firstLinkable.next(); length = length - 1; } } public Linkable firstLinkable(){ return firstLinkable; } public int length(){ return length; } } // LinkedList

Program: Et eksempel på anvendelse af LinkedList. Vi indsætter 1, 2 og 3. Dernæst sletter vi det første element (3). Dernæst indsætter vi 4. Programmet udskriver 4, 2, 1.

class ListApplication { public static void main(String[] args){ LinkedList lst = new LinkedList(); Integer element; lst.insertFirst(new Integer(1)); lst.insertFirst(new Integer(2)); lst.insertFirst(new Integer(3)); lst.deleteFirst(); lst.insertFirst(new Integer(4)); Linkable link = lst.firstLinkable(); while (link != null){ element = (Integer)link.data(); System.out.println(element); link = link.next(); } System.out.println("Listen har nu " + lst.length() + " elementer"); } //main }

Den viste implementation af LinkedList afslører detaljer om kædeobjekterne Listesproget Lisp's listebegreb opererer ligesom LinkedList på forenden af en liste Afsløringen af detaljer om kædeobjekterne er fremhævet i de to klasser, som er vist ovenfor

Dobbeltkædede lister Slide Note Contents Index References

Der findes en del forskellige variationer af kædede lister. Her og på den følgende slide ser vi på to særligt interessante af disse, nemlig dobbeltkædede og cirkulærer lister

I en dobbeltkædet liste er det effektivt at navigere både mod venstre og højre i listen

Figure. I en dobbeltkædet liste er der referencer til begge naboelementer. Derved benyttes mere lager. Gevinsten er naturligvis, at man både kan navigere effektivt mod forlæns og baglæns

Cirkulære lister Slide Note Contents Index References

En cirkulær liste er en kædet liste med effektiv adgang til både første og sidste element

Figure. I en cirkulær liste peger vores udefra kommende reference på det sidste element i listen. Idet listens sidste element peger på det første element, er det effektivt at indsætte elementer både først og sidst i listen, uanset listens længde

Exercise 5.3. Opgave om cirkulære lister

Formålet med denne opgave er primært at få øvelse i at arbejde med 'pointere' (referencer) på relativt lavt niveau. En del af jer har aldrig prøvet det før. Dette er chancen... Øvelsen er dog også en god træning i objekt-orienteret programmering. Ud fra ideerne på sliden, som er knyttet til denne opgave, ønskes en implementation af en klasse CircularList i Java. Bemærk referencen, som kommer 'udefra' går til det sidste element i den cirkulære liste. Tænk på denne reference som kommende fra objektet af typen CircularList. Følgende udgør klient-interfacet af klassen: void insertFirst(Object el) Indsæt et nyt første-element med indhold el i den cirkulære liste. void insertLast(Object el) Indsæt et nyt sidste-element med indhold el i den cirkulære liste. void deleteFirst() Slet det første element i listen (svarende til el1 på sliden). Gør intet hvis listen er tom void deleteLast() Slet det sidste element i listen (svarende til el5 på sliden). Gør intet hvis listen er tom Object retrieveFirst() Returner det første element i listen, eller null hvis listen er tom Object retrieveLast() Returner det sidste element listen, eller null hvis listen er tom int size() Returner antallet af elementer i listen. Det er en pointe i denne opgave at lave en løsning uden at benytte andre Java liste-klasser. Ud over at lave klassen CircularList får man brug for en klasse som repræsenterer kædeobjekterne. I er velkomne til at bruge min version af klassen Linkable . Aftest klassen CircularList. Estimer køretiden af operationerne i klassen CircularList. (Datalogerne: Brug ``Store O'' notation). Hints: Det kan være en god ide at forsyne klassen CircularList med en række interne hjælpeoperationer, såsom returnering af første elements og næstsidste elements kædeobjekt. Endvidere er en operation, som tømmer listen og en operation som laver listen 'singulær' (altså bestående af netop ét element) nyttige.

Associationslister Slide Note Contents Index References

En associationsliste er en kædet liste som realiserer samme idé som et associativt array På engelsk taler vi om 'association lists'

Figure. Et samlet billede af listestrukturen af en associationsliste. Den øverste række af objekter, kædeobjekterne (farvet grå) udgør en enkeltkædet liste. Den næste række af objekter er par (farvet gule), som blot aggregerer nøgler og de associerede objekter.

Operationer på associationslister har lineær tidskompleksitet Indsættelse, sletning og ændring af en association kræver i gennemsnit et arbejde der er proportionalt med antallet af par i listen For associative arrays med få associationer er denne simple afart af 'associative arrays' ofte meget nyttig

Kæde objekterne opfattes som private i listen. Kædeobjekterne bør ikke komme til klienternes kendskab Hvordan gennemløbes en liste hvis kædeobjekterne er skjult for klienterne?

Program: Et utilfredsstillende form for gennemløb af en kædet liste. Programmet indsætter først nogle elementer i en liste. Til illustration, slettes også et enkelt element. Dernæst gennemløbes listen ved direkte brug af et Linkable objekt. Et Linkable objekt svarer til det vi har kaldt et kæde-objekt.

public static void main(String[] args){ LinkedList lst = new LinkedList(); Integer element; lst.insertFirst(new Integer(1)); lst.insertFirst(new Integer(2)); lst.insertFirst(new Integer(3)); lst.deleteFirst(); lst.insertFirst(new Integer(4)); Linkable link = lst.firstLinkable(); while (link != null){ element = (Integer)link.data(); System.out.println(element); link = link.next(); } System.out.println("Listen har nu " + lst.length() + " elementer"); } //main

The concept iterator: En iterator er et objekt som har ansvar for gennemløb af en samling af data Man kan bede en iterator om det nuværende element og om repositionering i samlingen af data

En iterator er et objekt, hvortil man kan sende beskederne 'hasMoreElements' og 'nextElement'. Førstnævnte returnerer hvorvidt der er flere elementer i et gennemløb. Sidstnævnte returnerer et element. 'nextElement' må kun kaldes hvis 'hasMoreElements' returnerer true

Program: En mere tilfredsstillende form for gennemløb af en kædet liste med en iterator. Ligesom programmet ovenfor indsættes først indsætter nogle elementer i en liste, og der slettes et enkelt element. Dernæst gennemløbes listen ved brug af en iterator. Man kan spørge iteratoren om der er flere elementer i listen, og om det næste element.

public static void main(String[] args){ LinkedList lst = new LinkedList(); Integer element; lst.insertFirst(new Integer(1)); lst.insertFirst(new Integer(2)); lst.insertFirst(new Integer(3)); lst.deleteFirst(); lst.insertFirst(new Integer(4)); java.util.Enumeration iterator = lst.elements(); while (iterator.hasMoreElements()){ element = (Integer)iterator.nextElement(); System.out.println(element); } System.out.println("Listen har nu " + lst.length() + " elementer"); } //main

Program: Klassen LinkedList som anvendes i ovenstående program. Der er kun få variationer i forhold til den version vi studerede første i denne lektion. Variationerne er fremhævet.

/** A simple linked list which use an iterator instead of revealing of the Linkable's */ public class LinkedList { Linkable firstLinkable; private int length; public LinkedList(){ firstLinkable = null; length = 0; } public void insertFirst(Object element){ Linkable newFirst = new Linkable(element, firstLinkable); firstLinkable = newFirst; length = length + 1; } public void deleteFirst(){ if (length > 0){ firstLinkable = firstLinkable.next(); length = length - 1; } } public java.util.Enumeration elements(){ return new LinkedListEnumeration(this); } public int length(){ return length; } }

Program: Klassen LinkedListEnumeration. Klassen implementerer et Interface som hedder Enumeration i pakken java.util. Vi vil i en senere lektion se meget mere på Interfaces.

class LinkedListEnumeration implements java.util.Enumeration { private LinkedList enumeratedList; private Linkable currentLinkable; public LinkedListEnumeration (LinkedList list){ enumeratedList = list; currentLinkable = list.firstLinkable; } public boolean hasMoreElements(){ return(currentLinkable != null); } public Object nextElement(){ Object result = currentLinkable.data(); currentLinkable = currentLinkable.next(); return (result); } }

References Vores første version af klassen LinkedList Klassen Linkable Interfaces

Enumerations i Java Slide Note Contents Index References

Ovenfor så vi allerede en anvendelse af en Enumeration til gennemløb af en kædet liste. Her vil vi i større detalje se på Java enumeration idéen

Figure. Objektet enIterator har ansvar for et gennemløb af den sammenkædede liste. I Java er en iterator en instans af Enumeration i pakken java.util. Enumeration er et Interface, og ikke en klasse. Hvad det betyder ser vi i næste lektion. Objektet enIterator kan sendes beskederne 'hasMoreElements' og 'nextElement'. Objektet enIterator er skabt ved at sende enListe beskeden 'elements'. På figuren har vi allerede én gang sagt nextElement() på iteratoren

Det vil ofte være naturligt og nyttigt, hvis listen kan tilgå alle listens iteratorer

Det kan ofte være nyttigt at have mere end én iterator på en liste

I Java kan man umiddelbart lave iteratorer af typen Enumeration på instanser af Vector, HashTable og i Collections Man kan også let lave iterators på egne samlinger af objekter Vi vil i næste lektion introducere teknikker, som tillader os at lave vore egne iteratorer. Dette kræver forståelse af Java's Interface begreb

Reference Klassen Enumeration i pakken java.util

Indlejring af Linkable i LinkedList Slide Note Contents Index References

Vi vil her illustrere anvendelsen af indre klasser til at begrænse kendskabet til kæde-objekterne i en linked list. Forsøget på denne side lykkes kun delvis. På næste side vil vi gøre det endnu bedre.

Kæde-objekterne i en liste struktur, som er instanser af Linkable, er knyttet til en bestemt liste Kæde-objekterne er irrelevante for klienter af klassen LinkedList Derfor bør Linkable være en indre klasse i klassen LinkedList

Program: En skitse af indlejringen af Linkable i LinkedList.

public class LinkedList { LinkedList instansvariable class Linkable { Linkable instansvariable Linkable metoder } LinkedList metoder }

Program: Klassen LinkedList med pakke-synlig Linkable som inner class. Vi har valgt at give Linkable pakke synlighed. Hvis vi lader Linkable være privat kan vi ikke oversætter liste applikationen, idet Linkable dermed ikke kan ses uden for LinkedList.

/** A simple linked list with inner Linkable class which reveals the Linkable object in a unsatisfactory manner */ public class LinkedList { private Linkable firstLinkable; private int length; class Linkable { private Object data; private Linkable next; /** Return a Linkable object with null references in both data and next */ Linkable(){ data = null; next = null; } /** Return a Linkable object with null references in next, and the parameter as data */ Linkable(Object data){ this.data = data; this.next = null; } /** Return a Linkable object with first parameter as data and second parameter as next */ Linkable(Object data, Linkable next){ this.data = data; this.next = next; } /** Return the data of this Linkable object */ Object data(){ return (data); } /** Return the reference to the next Linkable */ Linkable next(){ return (next); } /** Set the data field of this Linkable object */ void setData(Object data){ this.data = data; } /** Set the next field of this Linkable object */ void setNext(Linkable next){ this.next = next; } } // Linkable public LinkedList(){ // make empty list firstLinkable = null; length = 0; } public void insertFirst(Object element){ Linkable newFirst = new Linkable(element, firstLinkable); firstLinkable = newFirst; length = length + 1; } public void deleteFirst(){ if (length > 0){ firstLinkable = firstLinkable.next(); length = length - 1; } } public Linkable firstLinkable(){ return firstLinkable; } public int length(){ return length; } } // LinkedList

Program: Liste applikationen repræsenteret ved klassen ListApplication. Vi har fremhævet det sted hvor Linkable anvendes. Ideelt set ønsker vi ikke denne anvendelse. På næste side vil vi se, hvordan vi løser problemet.

public static void main(String[] args){ LinkedList lst = new LinkedList(); Integer element; lst.insertFirst(new Integer(1)); lst.insertFirst(new Integer(2)); lst.insertFirst(new Integer(3)); lst.deleteFirst(); lst.insertFirst(new Integer(4)); LinkedList.Linkable link = lst.firstLinkable(); while (link != null){ element = (Integer)link.data(); System.out.println(element); link = link.next(); } System.out.println("Listen har nu " + lst.length() + " elementer"); } //main

Hvis Linkable er privat i LinkedList kan vi ikke anvende Linkable fra liste applikationen På næste side vil vi gen-introducere iterator løsningen, som vi tidligere har set på. Dette giver os mulighed for at have Linkable som en private klasse.

Indlejring af Linkable mv. i LinkedList Slide Note Contents Index References

Hvis vi anvender iteratorer af typen LinkedListEnumeration kan Linkable gøres privat i LinkedList

Program: En skitse af indlejringen af Linkable og LinkedListEnumeration i LinkedList. Bemærk at Linkable er private og LinkedListEnumeration er public.

public class LinkedList { private class Linkable { ... } public class LinkedListEnumeration implements java.util.Enumeration { ... } ... }

Program: Klassen LinkedList med Linkable og LinkedListEnumeration som inner classes. Man skal specielt lægge mærke til kroppen af LinkedListEnumeration, hvor vi kan se at der er direkte adgang til det omkringliggende objekts instansvariable (endog private instansvariable). Vi ser også, at det omkringliggende objekt kan refereres med udtrykket LinkedList.this, som er specialsyntaks i Java.

/** A simple linked list which use an iterator instead of revealing of the Linkable's */ public class LinkedList { private Linkable firstLinkable; private int length; private class Linkable { private Object data; private Linkable next; /** Return a Linkable object with null references in both data and next */ Linkable(){ data = null; next = null; } /** Return a Linkable object with null references in next, and the parameter as data */ Linkable(Object data){ this.data = data; this.next = null; } /** Return a Linkable object with first parameter as data and second parameter as next */ Linkable(Object data, Linkable next){ this.data = data; this.next = next; } /** Return the data of this Linkable object */ Object data(){ return (data); } /** Return the reference to the next Linkable */ Linkable next(){ return (next); } /** Set the data field of this Linkable object */ void setData(Object data){ this.data = data; } /** Set the next field of this Linkable object */ void setNext(Linkable next){ this.next = next; } } // Linkable public class LinkedListEnumeration implements java.util.Enumeration { private LinkedList enumeratedList; private Linkable currentLinkable; public LinkedListEnumeration() { enumeratedList = LinkedList.this; currentLinkable = firstLinkable; } public boolean hasMoreElements(){ return(currentLinkable != null); } public Object nextElement(){ Object result = currentLinkable.data(); currentLinkable = currentLinkable.next(); return (result); } } // LinkedListEnumeration public LinkedList(){ firstLinkable = null; length = 0; } public void insertFirst(Object element){ Linkable newFirst = new Linkable(element, firstLinkable); firstLinkable = newFirst; length = length + 1; } public void deleteFirst(){ if (length > 0){ firstLinkable = firstLinkable.next(); length = length - 1; } } public java.util.Enumeration elements(){ return new LinkedListEnumeration(); } public int length(){ return length; } }

Program: Liste applikationen repræsenteret ved klassen ListApplication.

public static void main(String[] args){ LinkedList lst = new LinkedList(); Integer element; lst.insertFirst(new Integer(1)); lst.insertFirst(new Integer(2)); lst.insertFirst(new Integer(3)); lst.deleteFirst(); lst.insertFirst(new Integer(4)); java.util.Enumeration iterator = lst.elements(); while (iterator.hasMoreElements()){ element = (Integer)iterator.nextElement(); System.out.println(element); } System.out.println("Listen har nu " + lst.length() + " elementer"); } //main

Collected references Contents Index

Vores første møde med Java arrays Collections som erstatning af Vector Værdier i forhold til objekter Klassen Vector i pakken java.util Klassen Hashtable i pakken java.util Interfaces Klassen Linkable Vores første version af klassen LinkedList Klassen Enumeration i pakken java.util Indlejrede klasser i Java

Chapter 5: Arrays og Lister
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: March 31, 2008, 12:08:29