Innledning
Dette er det siste settet med ukeoppgaver som er hovedsaklig ment for de som ikke har følgt INF1060. Vi synes at de vil hjelpe med gjennomføringen av obliger og hjemmeeksamer. Dere som har følgt INF1060 vil ikke ha spesiell bruk for disse oppgavene.
Fra neste uke vil ukeoppgavene besto hovedsaklig av oppgaver som ligner oppgaver i den skriftlige slutteksamen. Mens dere holder på med praktiske i obliger og hjemmeeksamer er det altså nyttig også å følge med på ukeoppgavene som forberedelse for slutteksamen.
Målet med disse oppgavene er å gå gjennom en del konstruksjoner i språket C som stiller programmerere som ikke er vant språket foran en del problemer. Det er hovedsaklig pekere, arrays, strings, og bit-operasjoner. I disse konstruksjonene viser det seg tydelig at C ikke er et høynivåssprak. Man må tenke hardwarenær for å sjønne hvorfor ting virker som de gjør. For oss i INF3190/INF4190 er det viktig, fordi vi må ha full kontroll over hver eneste bit og byte som vi ønsker å overføre på data link, network eller transportlag.
Oppgaver
Programmeringsoppgaven skal løses på en maskin av type unix; enten linux eller solaris.
1. Bitoperasjoner
Bitoperasjoner forekommer hyppig i alle protokoller nedenfor applikasjonslaget. I noen tilfeller er det bare gjort for å spåre båndbredde, men hovedsaklig er protokoller spesifisert på bit-nivå fordi protokoller gjør samtaler mulig mellom maskiner som er så forskjellige at det eneste som de har i felles er sin forståelse om hva en bit er og hvilken rekkefølge de har sendt og mottatt bittene i.
Derfor skal dere lese fra en fil og komprimere den etter metoden runlength encoding. Tanken med dette er at i steden for å skrive mange etterfølgende like tegn i en fil har man med en teller i tillegg som sier hvor mange like tegn som følger det tegnet vi akkurat har lest.
Filen skal inneholde bare tegnene a, b, c, d, e, f, g, h, i, j. Det gjør det mulig å komprimere bokstavene entydig med 4 bit per bokstav (a=0001, b=0010, c=0011, ..., j=1010). I tillegg til å komprimere bokstavene skal dere telle hvor mange like bokstaver det er som følger etter hverandre. Er det bare en bokstav, så skal dere bare skrive den komprimerte bokstaven. Er det flere like bostaver, skal dere bruke de to bitene 11 for å vise at det er følger flere like bokstaver, fire bits for å kodiere antallet gjentakelser binært, følgt av den komprimerte bokstaven. Hvis den komprimerte strengen ikker slutter på en byte-grense, skal den fylles opp med bitparer 00.
Det skal kunne både komprimere og dekomprimere strenger.
2. Arrays and pointers (a)
C er et språk med få og korte ord og enkle symboler. En-bokstavs-symboler er hyppig brukt, og forkortelser er en del av syntaksen. Her er et eksempel for korrekt kode:
void function( char* buf )
{
...
}
void otherfunction( )
{
char buffer[200];
...
function( buffer ); /* <- abbreviation */
...
}
Forklar hva det er som foregår.
3. Arrays and pointers (b)
Du har følgende kode:
void function( int a, int* b, char c, char* d, char e[] )
{
a = 2;
*b = 3;
b = &a;
c = 'x';
*d = 'y';
d = &c;
e[2] = 'z';
}
int main( )
{
int k,l;
int* m;
char n,o;
char* p;
char q[5];
k = 100;
l = 101;
m = &l;
n = 'n';
o = 'o';
p = &o;
q[0] = 'h';
q[1] = 'e';
q[2] = 'r';
q[3] = 'e';
q[4] = '\0';
function( k,m,n,p,q );
printf( "k=%d l=%d *m=%d\n", k, l, *m );
printf( "n=%c o=%c *p=%c\n", n, o, *p );
printf( "q=%s\n", q );
}
Hva skreves ut på skjermen? Hvorfor skreves ut akkurat dette?
4. Strenger i C (a)
Strenger i C er ikke noe annet en bokstavarrayer. Det er blant annet ikke mulig å utføre veldig nyttige operasjoner på C strenger som de allerfleste andre språk har. For eksempel kan man ikke bruke plus operatoren for å konkatinere to C strenger. Mange misliker det.
Den store fordelen med C strenger er at man har full kontroll over det som skjer. Man hvet nøyaktig hvor i minne dataene til en C streng ligger, hvor mye plass den bruker, og hva man må sende over nettet for at mottakersiden også kan bruke den som en streng. Det klarer man ikke med strengene i de andre språkene. Og man kan f.eks. trekke ut eller erstatte enkelte bokstaver, regne med bokstaver som om de var tall eller på en enkel måte avbryte strenger. Men det krever litt trening.
Du har følgende kode:
void funA( char buf[10] )
{
int i;
for( i=0; i<10; i++ )
{
buf[i] = 'a' + i;
}
}
void funB( char* buf )
{
int i;
for( i=0; i<10; i++ )
{
buf[i] = 'b' + i;
}
}
void funC( char* buf )
{
int i;
for( i=0; i<10; i++ )
{
*buf = 'c' + i;
buf = buf + 1;
}
}
int main( )
{
char buf[11];
memset( buf, 0, 11 );
funA( buf );
printf( "%s\n", buf );
funB( buf );
printf( "%s\n", buf );
funC( buf );
printf( "%s\n", buf );
}
Hva skreves ut på skjermen? Hvorfor skreves ut akkurat dette?
5. Strenger i C (b)
Du har den følgende variablen:
char* apple = " a\n"
" ppl\n"
" eappl\n"
" eapple\n"
" apple\n"
" appl\n"
" eappleappleappleappl\n"
" eappleappleappleappleapple\n"
" appleappleappleappleappleapple\n"
" appleappleappleappleappleappleappl\n"
" eappleappleappleappleappleappleapple\n"
"appleappleappleappleappleappleappleapp\n"
"leappleappleappleappleappleappleapplea\n"
"ppleappleappleappleappleappleappleappl\n"
"eappleappleappleappleappleappleappleap\n"
"pleappleappleappleappleappleappleapple\n"
"appleappleappleappleappleappleappleapp\n"
"leappleappleappleappwormpleappleapplea\n"
" ppleappleappleappleappleappleappleap\n"
" pleappleappleappleappleappleapplea\n"
" ppleappleappleappleappleappleapp\n"
" leappleappleappleappleappleap\n"
" pleappleappleappleappleapp\n"
" leappleappleappleapple\n"
" appleappleappleapp\n";
Dette er en lovlig C streng. Spørsmålene er: Hvor langt er strengen? Hvor mange bytes må du allokkere med malloc hvis du ønsker å lage en kopi?
5. Strenger i C (c)
Finn ormen i eplen. Forsøk følgende muligheter:
- Bruk ikke noen C funksjoner i det hele tatt, bare enkle språkoperasjoner som if/else, for, while, do osv.
- Bruk søkefunksjonen strchr(). Husk å inkludere string.h.
- Bruk erstatningsfunksjonen strstr().
Klipp ormen ut av eplen, med å overskrive bokstavene med " ".
6. Strenger i C (d)
Hvor dypt i eplen var ormen (Hva er index verdien for den første bokstaven 'w' av ordet worm). Brukt funksjonen strstr() for å finne svaret.