Kurt Nørmark
Institut for Datalogi, Aalborg Universitet
Sammendrag Forrige lektion Næste lektion Stikord Referencer Indhold | I denne lektion studerer vi pointere og arrays. Vi ser først på pointere. Dernæst ser vi på arrays som pointere. Efter dette kommer vi til arrays af flere dimensioner. Vi slutter af med sondringen mellem statisk og dynamisk lagerallokering. |
Introduktion til arrays |
Arrays i C - Motivation og Introduktion Slide Indhold Stikord Referencer |
|
Program: Motivation for arrays - et stort antal simple variable. |
|
Program: Introduktion af arrays. |
|
Program: Eksplicit array initialisering - kun i erklæringer. |
|
Program: En variant af eksplicit array initialisering. |
|
Generelle egenskaber af arrays Slide Indhold Stikord Referencer |
|
Figur. Et array med 11 elementer indiceret fra 0 til 10 |
|
|
Arrays i C - begrænsninger Slide Indhold Stikord Referencer |
|
|
Program: Illustration af at arrays ikke kan assignes til hinanden - compilerer ikke. |
|
Program: Illustration af at et array ikke kopieres ved parameteroverførsel - compilerer og kører. |
|
Program: Program output. |
|
Program: Et array der overføres som input parameter - compilerer ikke. |
|
Program: Illustration af at arrays ikke umiddelbart kan returneres fra en funktion - compiler warnings. |
|
Program: Program output. |
|
Program: Illustration af at arrays kan returneres fra en funktion - med et lille trick - compilerer og kører korrekt. |
|
Program: Program output. |
|
Mere om Pointers |
Pointer variable Slide Indhold Stikord Referencer |
|
Program: Erklæring og initialisering af et antal variable, hvoraf nogle er pointer variable. |
|
Figur. Situationen før de to assignments |
Program: Erklæring og initialisering af et antal variable, hvoraf nogle er pointer variable. |
|
Figur. Grafisk illustration af variablene i, j, c og deres tilsvarende pointervariable. Læg mærke til værdien af ptr_i, som er sat til at pege på samme værdi som ptr_j, altså variablen j. |
Program: Hele programmet inklusive udskrivning af variablenes værdier. |
|
Program: Output fra programmet. |
|
Addresse og dereferencing operatorerne Slide Indhold Stikord Referencer |
|
|
Program: Fremhævelse af adresse og dereferencing udtryk programmet fra forrige side. |
|
|
Pointer eksempler - en opgave Slide Indhold Stikord Referencer |
Program: The variables i, j, p, q, r, and x. |
|
Tabel. |
|
|
Opgave 9.2. En pointer øvelse | På den tilknyttede slide finder du nogle erklæringer af double og int variable, herunder pointere til sådanne. Du finder også en tabel med udtryk, både med og uden parenteser som afklarer operator-prioriteringerne. Beregn værdierne af alle de udtryk, som giver mening. Check dine resultater ved at indføre udtrykkene i et lille C program. |
Pointer typer i C og generiske pointere Slide Indhold Stikord Referencer |
|
Program: Illustration af pointervariable af forskellige typer - giver compileringsfejl. |
|
Program: Et lignende program - kan oversættes og køres. |
|
Program: Program output. |
|
|
|
Call by reference parametre |
Call by reference parametre Slide Indhold Stikord Referencer |
|
Program: Et forsøg på ombytning af to variables værdi uden pointere - virker ikke. |
|
Program: Program output. |
|
Program: En funktion der ombytter værdierne af to int variable. |
|
Program: Funktionen swap og et hovedprogram, som kalder swap på to variable. |
|
Program: Program output. |
|
|
Pointers og arrays |
Pointers og arrays (1) Slide Indhold Stikord Referencer |
|
Figur. Et array med fem elementer og en pointer til første element |
Program: Illustration af pointertilgang til arrays. |
|
Billedserie: Forskellige opdateringer af table ved brug af pointere | Forskellige opdateringer af table ved brug af pointere |
Billed nr. 1. ptr_table peger på elementet med index 0 i table |
Billed nr. 2. *ptr_table refererer til indholdet i table[0]. Denne celles indehold ændres til 7.0. |
Billed nr. 3. ptr_table flyttes én plads til højre. Indholdet af denne celle bliver indholdet af cellen table[0] * 5. |
Billed nr. 4. ptr_table flyttes tre positioner længere til højre. Indholdet af den pågældende celle tælles én op. |
Billed nr. 5. Indekset af den sidste celle (4) og indexet af table[0] (0) trækkes fra hinanden og tallet skrives ud. |
Program: Et komplet C program, som illustrerer opdateringerne af table. |
|
Program: Program output. |
|
Pointers og arrays (2) Slide Indhold Stikord Referencer |
|
Program: Et simpelt program med arrays - fra starten af lektionen - med subscripting. |
|
Program: Et tilsvarende program - med pointer tilgang til elementerne. |
|
Program: Output fra programmerne. |
|
|
Pointers og arrays (3) Slide Indhold Stikord Referencer |
|
Program: Illustration af pointertilgang til arrays. |
|
|
Program: Illustration af de ækvivalente array udtryksformer - både i L-værdier og R-værdier. |
|
Program: Output fra programmerne. |
|
Pointer aritmetik Slide Indhold Stikord Referencer |
Program: Erklæring af to pointere p og q samt en int i. |
|
|
Program: En funktion som tæller antallet af tegn i en streng. |
|
Program: Hele programmet. |
|
Program: Output fra programmet. |
|
Index out of bounds Slide Indhold Stikord Referencer |
|
Program: Et eksempel på indicering uden for indeksgrænserne i et array. |
|
Program: Hele programmet. |
|
Program: Muligt program output. |
|
|
Eksempel: Bubble sort Slide Indhold Stikord Referencer |
|
Program: Function bubble_sort som laver 'bubble sort' på arrayet a som har n heltalselementer. |
|
Program: Hele 'bubble sort' programmet - med løbende udskrift af arrayet. |
|
Program: Output fra bubble sort programmet. |
|
Billedserie: Illustration af de forskellige faser i boblesorteringen | Illustration af de forskellige faser i boblesorteringen |
Billed nr. 1. Det usorterede array |
Billed nr. 2. Tallet -77 er, som det 'letteste' tal, boblet op foroven gennem en række ombytninger |
Billed nr. 3. Tallet -5 er, som det 'letteste' resterende tal, boblet op foroven gennem en række ombytninger |
Billed nr. 4. Tallet 7 er, som det 'letteste' tal, boblet op. Bemærk at de øverste tre tal - de røde - nu er sorteret. |
Billed nr. 5. Mønstret fortsætter, nu med 3 som bobleren. Nu er de øverste fire tal røde og sorteret. |
Billed nr. 6. Det næste 3 tal bringes på plads. Bemærk at vi reelt er færdige på dette tidspunkt. |
Billed nr. 7. Den yderste forløkke fortsætter, men den indre foretager ikke flere ombytninger. |
Billed nr. 8. Stadig samme situation. |
Billed nr. 9. Slutbilledet. De røde tal er sorteret, og det sorte tal er større end dem alle. |
|
Brug af qsort fra standard biblioteket Slide Indhold Stikord Referencer |
|
Program: Anvendelse af qsort til sortering af et heltals array. |
|
Program: En variant af anvendelse af qsort - med int_compare funktion. |
|
Program: Output af programmerne. |
|
|
Array input og output parametre Slide Indhold Stikord Referencer |
|
|
|
Opgave 9.3. Polynomier | I denne opgave vil vi repræsentere et polynomium p af grad n som et array af koeficienter a0, ..., an, hver af typen double, p(x) = a0 + a1 x + a2 x2 + ... + an xn hvor an er forskellig fra nul. Skriv et C program som indlæser et polynomium af grad højst 8, og som kan beregne polynomiets værdi for forskellige x værdier. Opdel din problemløsning i delproblemer, get_polynomium, som indlæser et polynomium i et array, og eval_polynomium, som beregner polynomiets værdi for en given x værdi: void get_polynomium(double coeff[], int* degreep); double eval_polynomium(const double coeff[], int degree, double x); Denne opgave svarer til opgave 14 side 464 i 6. udgave af lærebogen |
Arrays af flere dimensioner |
Arrays af to dimensioner Slide Indhold Stikord Referencer |
|
Figur. Illustrationer af et to dimensionelt array. Øverst til venstre illustreres forståelse af de to dimensioner, med to rækker og tre søjler. Vi kunne naturligvis lige så godt have byttet om på rækker og søjler. Nederst til venstre ses en forståelse der understreger at a er et array med to elementer, som begge er arrays af tre elementer. Længst til højre ses den maskinnære forståelse, 'row major' ordningen. |
|
Gennemløb af arrays med to dimensioner Slide Indhold Stikord Referencer |
|
Program: Erklæring, initialisering og to identiske gennemløb af et to dimensionelt array. |
|
Program: De viste gennemløb i et helt C program. |
|
Program: Program output. |
|
Program: En variation der afslører rækkenfølgen hvorefter elementerne besøges. |
|
Program: Program output. |
|
Program: Endnu en variation. |
|
Program: Program output. |
|
|
Arrays af to dimensioner overført som parametre Slide Indhold Stikord Referencer |
|
Program: Et to-dimensiolt array der overføres som parameter til en funktion - OK. |
|
Program: Et to-dimensiolt array der overføres som parameter til en funktion - også OK. |
|
Program: Et to-dimensiolt array der overføres som parameter til en funktion - forkert. |
|
|
Statisk og dynamisk lagerallokering |
Statisk lagerallokering Slide Indhold Stikord Referencer |
Begrebet statisk lagerallokering: Med statisk lagerallokering afsættes lagerplads implicit når den omkringliggende blok aktiveres. Lagerplads frigives implicit når blokken forlades. |
Program: Illustration af statisk lagerallokering i C. |
|
|
Dynamisk lagerallokering (1) Slide Indhold Stikord Referencer |
|
Begrebet dynamisk lagerallokering: Med dynamisk lagerallokering afsættes lagerplads eksplicit, når programmet har behov for det. |
Program: Et kreativt forsøg på dynamisk allokering - ikke ANSI C. |
|
Program: ANSI C Oversættelse af programmet. |
|
Program: Et program der foretager dynamisk allokering af et array - calloc. |
|
Program: Et program der foretager dynamisk allokering af et array - malloc. |
|
Program: Et program der dynamisk allokerer et to-dimensionelt array. |
|
Program: Output fra programmet. |
|
|
Dynamisk lagerallokering (2) Slide Indhold Stikord Referencer |
|
|
Dynamisk allokering af PPM billeder Slide Indhold Stikord Referencer |
|
Figur. The organization of the memory allocated for a PPM image |
Program: Funktionen der allokerer plads til et PPM billede. |
|
Program: Eksempel på en funktion der tilgår pixels i et PPM billede. |
|
|
Flere Opgaver Slide Indhold Stikord Referencer |
Opgave 9.11. Reduktion af et array | Vi har tidligere i undervisningsmaterialet set hvordan vi kan reducere/kombinere en række tal med en 'binær funktion' (en funktion fra to doubles til én double). I denne opgave skal I skrive en funktion double combine_right (double a[], int n, double (*combiner)(double, double)) som kombinerer alle n elementer i a, på samme måde som combine gør det for fire faste tal. Antag at n >= 2. Skriv først en version, combine_right, der kombinerer elementerne fra højre mod venstre. Skriv også gerne en version, combine_left, som kombinerer i den modsatte retning. Afprøv dit program på tilsvarende måde, som vi gjorde da vi første gange mødte combine funktionen. |
Opgave 9.11. bsort | Omskriv bubblesort funktionen så den ligner qsort så meget som muligt. Du skal ikke lave om på algoritmen bag bubblesort - det handler parametrene til funktionen. Kald den nye variant af bubblesort for bsort. Dette indebærer at bsort skal have fire parametre:
Start gerne med at generalisere den eksisterende version af bubblesort med en sammenligningsfunktion. Når dette er på plads bedes du overveje hvordan du vil håndtere ombytningen af elementer. (Hint: Overvej at bruge memcpy fra string.h når du skal kopiere array elementer). Du kan bruge følgende prototype af funktionen: void bsort(void *base, size_t n, size_t size, int(*compar)(const void *, const void *)) hvor size_t er en passende unsigned integer type (som altid findes i C) |
Opgave 9.11. Dynamisk allokering og qsort | Brug malloc til at allokere plads til 100 doubles. Check at allokeringen blev gennemført, og dealloker dit lager når du er færdig med at bruge det. Opfat det allokerede lager som et array af 100 doubles, og indskriv 100 tilfældige tal i dit array. Udskriv dem på skærmen. Brug nu qsort til at sortere dine tal. Udskriv dem igen, så du kan se at dit array rent faktisk er blevet sorteret. |
Opgave 9.11. Barcode scanning | Dette er opgave 5 side 469 i PSPD (8ed). Opgaven er taget med for at have et naturligt sted at organisere løsningen på opgaven. |
Opgave 9.11. Iterativ løsning af 'uger, dage, timer, minutter og sekunder' opgaven | Denne opgave hører logisk til i lektionen om iterative kontrolstrukturer. Men da det viser sig at arrays er helt essentielle for at kunne håndterer udfordringen, har vi valgt at placere den her. Når man ser på en typiske løsning af opgaven, der omregner et sekundtal til normaliserede uger, dage, timer, minutter og sekunder, kan man tydeligt se at division og restuddragen gentages fire gange på en given rest. I denne opgave vil vi forsøge at programmere dette med en iterativ kontrolstruktur. Omskriv altså løsningen på den oprindelige opgave til et program, der gentager divisionen og restuddragning, i en passende løkke. For at kunne arbejde med tidsdelene (og enhedsnavnene) på en realistisk måde, er det attraktivt at benyttes arrays. Som altid, er det godt at formulere løsningen på problemet i en funktion. Her en funktion med én input-parameter (sekundtallet), og én output parameter (et array med de beregnede tidsdele). Notér og bemærk hvilke udfordringer det gav at skrive programmet om på den ønskede måde. Vurder også om det er umangen værd at lave denne ændring af programmet. |
Opgave 9.11. Multiple terningekast. | På siden om tilfældige tal, har vi set en simpel funktion, der simulerer et kast med en terning. I nogle sammenhænge er der behov for kast med n terninger, hvor n > 1. I det simple tilfælde kan vi naturligvis blot kaste én terning n gange (i en løkke). I andre tilfælde har vi behov for at have adgang til udfaldene af de n terninger samtidigt, i et array, for at kunne vurdere de n kast under ét. Vi vil senere på kurset få brug for netop denne mulighed. Skriv derfor en funktion roll_multiple_dies, med en heltals parameter n, der kaster n terninger, og som afleverer et array af de n terningekast. Afleveringen af de n kast kan ske på to måder: gennem en parameter af pointer type eller via funktionens returværdi. Allokering af arrayet kan også varieres: enten allokerer roll_multiple_dies plads, eller også er der allerede allokeret plads, når roll_multiple_dies kaldes. Hvis roll_multiple_dies allokerer plads med dynamisk lagerallokering, i hvert kald, udestår der et efterfølgende arbejde med passende kald af free. Skriv, ud fra denne analyse, din foretrukning variant af funktionen roll_multiple_dies. Programmer endvidere, i main, 10 kald af af roll_multiple_dies. Giv indledningsvis brugeren mulighed for at indlæse størrelsen n (antallet af terninger). Udskriv, for hvert kald af roll_multiple_dies, udfaldet af de n terningekast. |
Opgave 9.11. Associative arrays. | Et array i C indiceres altid med et heltal, hvilket sikrer simpel og effektiv tilgang til elementer i arrayet. Men i mange sammenhænge er det fristende og nyttigt at indicere et array med værdier af andre typer, så som en tekststreng. Lad os eksempelvis antage at vi ønsker at holde styr på alderen af navngivne personer ved brug af et array, alder_af_person. For "Peter" kan vi dermed tilgå alderen med alder_af_person["Peter"] . alder_af_person kan ikke være et array i C, men konceptuelt kan vi opfatte alder_af_person som et associativt array: Et sådant array associerer navnet på en person med personen alder. Generelt giver det god mening, på denne måde, at associere en vilkårlig værdi/objekt s af typen S til en værdi t i typen T via et associativt array a. Vi slår T-værdien op med a[s], givet s i typen S. Spørgsmålet er nu hvordan vi kan bruge arrays i C til at arbejde med associative arrays. Ideen er simpel nok. Lad os illustrere den med S som en teksstreng, og T som int, og a som alder_af_person. Personens navn skal først, med en funktionen h, konverteres til et lovligt indeks i et C-array. h("Peter") skal returnere et ikke-negativt heltal, nemlig det heltal hvor alderen af "Peter" skal findes. Hermed kan vi fra pesonens navn, "Peter", tilgå Peter's navn med alder[h("Peter")] hvor alder er et C array:_ int alder[MAX_PESON_INDEX]; Hvis vi først antager at vi har et lille univers af mulige tekststrenge, kan vi ret let skrive en h-funktion , som eksplicit afbilder et navn (en streng) til et indeks (et heltal). Denne h-funktion sikrer at hver tekststreng tildeles hvert sit indeks. Skriv en sådan h -funktion for navnene på dine medstuderende i din projektgruppe, således at du kan indsætte og slå alderen af en studerende op i et associativt array (undgå danske bogstaver i navnene). Hvis vi derimod antager at vi har et meget stort univers af mulige teksstrenge, så som hele Danmarks befolkning, bliver det meget besværligt at skrive funktionen h . Hvis vi forsøger vil det sikkert også bliver meget dyrt at kalde den, fordi funktionen muligvis vil lave et arbejde proportionalt med befolkningens størrelse. Men vi kan forsøge at beregne et passende heltal ud fra tegnene i personens navn, og normalisere tallet til et indeks i det ønskede interval. (Funktionen kan eksempelvis tage alle, eller udvalgte, tegn i navnet, addere dem som de små heltal de jo er, og normalisere summet med modulo operatoren). Problemet er nu, at to forskelle navne kan afbildes til det samme indeks. Vi siger at der sker en kollision. Skriv, som en øvelse, en h-funktion efter denne ide, og prøv den af på navnene i jeres projektgruppe. Oplever I kollisionsproblemet i denne øvelse? Vi har med dette introduceret ideen om hashtabeller og hashfunktioner , som er vigtige i mange praktiske sammenhænge, hvor vi også skal udtænke strategier til håndtering af kollision. |
Opgave 9.11. Fletning af to sorterede arrays | Dette er opgave 11 side 471-472 i Problem Solving and Program Design in C, eighth global edition. Denne opgave er taget med her for at have en pladsholder til en løsning. |
Samlede referencer Indhold Stikord |
|
Kapitel 9: Arrays og Pointere
Kursets hjemmeside Forfatteren's hjemmeside Om frembringelsen af disse sider Forrige lektion (top) Næste lektion (top) Forrige lektion (bund) Næste lektion (bund)
Genereret: 9. maj 2022, 13:59:48