Opgaver
Arrays og Pointere

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.

I denne opgave vil vi repræsentere et polynomium p af grad n som et array af koeficienter a₀, ..., a_n, hver af typen double,

   p(x) = a₀ + a₁ x + a₂ x² + ... + a_n xⁿ

hvor a_n 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

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.

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:

1. En pointer til det array der skal sorteres
2. Antallet af elementer i arrayet
3. Byte-størrelsen af hvert element
4. En sammenligningsfunktion (med int returværditype og to generiske pointere som input 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)

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.

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.

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.

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.

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.

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.