Laboration i C

Syftet med den här laborationen är att lära sig programmeringspråket C. Labben är tänkt att vara klar på tre veckor med all felsökning man kan tänkas behöva göra. Labbtillfällena är hjälp och redovisningstillfällen, det mesta arbetet ska göras utanför labbtid. Förutom labbtillfällena finns det allmänhandledningen där en ensam hjälphandledare handleder studenter på flera kurser.

För att få tillgång till C-kompilatorn och övriga verktyg behöver du addera modulen gcc och gnu. Om du gjort course join tilpro09 module list.

Läs om pekare

Läs på Ted Jensens tutorial om pekare i C. Länken finns på hemsidan under länkar. A. Svara på följande frågor.

Vad menas i kapitel två med den här raden? ptr = &my_array[0];
Vad är skillnaden mellan de två variablerna?

Vad betyder 3[a]?

Vad är skillnaden mellan *(*(multi + row) + col) och multi[row][col]?

Innan du programmerar

Parallellt med att läsa Ted Jensens pekartutorial ska du göra följande för att lära dig mer om C och dess verktyg.

In och utmatning

Skriv in följande enkla program i en textfil med namnet mitt_program.c

#include <stdio.h>

int main() {
    printf("Hej vad heter du? ");
    char str [5];
    scanf("%s", str);
    long a;
    printf("Hur gammal är du? ");
    scanf("%d", a);
    printf("Hej %s du har endast 65 - %d år kvar till pensionen\n", str, a);
}

Kompilera programmet med

gcc -o mitt_program mitt_program.c

Programmet funderar inte särskilt bra. Ändra argumentet till det andra scanf så att man matar in åldern till variabeln a's adress.

Prova att köra programmet några gånger. Vad händer om du skriver in ett namn som är mycket längre än vektorn str?

Skriva över stacken

Alla lokala variabler lagras på stacken. Du ska nu prova att skriva ett program som skriver en annan variabel. Först ska du ta reda på var dina variabler lagras.

Spara undan ditt nuvarande program i en annan fil. Skriv ett nytt huvudprogram i filen mitt_program.csom allokerar fem heltal av olika storlekar. Skriv ut dess adresser och rita en bild av hur stacken ser ut med adresser och initialvärden.

Deklarera tre teckenvektorer enligt nedan. Rita upp hur stacken ser ut.

    char str1 [10] = "str1";
    char str2 [11];
    char str3 [12] = "str3";

Låt användaren mata in ett svar till str2. B. Hur ska man svara för att påverka andra variabler?

Hårdkodning

Vektorns str längd är hårdkodad. Det kan man åtgärda på två sätt. Det gamla sättet (ANSI C) definierar man ett makro, t.ex. #define STR_LENGTH 5. I nya c-standarden kan man deklarera en konstant istället const int max_storlek = 30. Nackdelen med den #define är att den är potentiellt farlig eftersom preprocessorn inte tar hänsyn till C-syntax.

Ändra på hårdkodningen. I fortsättningen ska du se till att ingen hårdkodning förekommer i dina program.

Preprocessor

#define är ett preprocessorkommando. Ett annat är #include som vi använde för att få tillgång till standard I/O (input/output) funktionalitet. C. På vilket sätt ändrar preprocessorn din källkod innan den körs av kompilatorn?

Statiska variabler

Deklarera två statiska variabler. En statisk variabel i C är filglobal. Man kan jämföra dem med instansvariabler i en klass (om filen är klassen) eller med klassvariabler i en klass.

Skriv ut variablernas värden och adress.

Externa moduler och variabler

Skriv en fil som heter modul1.c med följande rad:

    const int MAXLENGD = 13;

Kompilera filen till maskinkod genom att skriva

gcc -c modul1.c

Det enda denna maskinkod gör är att allokera heltalet MAXLENGD. Använd detta tal i ditt föregående program mitt_program.c. Skriv raden

    extern const int MAXLENGD;

i mitt_program.c. Ändra i main så att värdet och adressen till MAXLENGD skrivs ut. För att kompilera mitt_program.c måste du länka in objektfilen modul1.o. Det kan du göra genom att t.ex. lägga till modulen när du kör gcc.

gcc -o mitt_program mitt_program.c modul1.o

D. Vad händer om tar bort ordet extern?

Makefile

För att bygga större projekt med flera delprogram använder man programmet make. TAB-tangenten har en speciell betydelse i makefiler, vilken?

Prova att skriva en Makefile med följande rader.

mitt_program: modulen mitt_program.c
	gcc -o mitt_program mitt_program.c modul1.o

modulen: modul1.c
	gcc -c modul1.c

Kör make flera gånger, E. vad händer??

Programmet make kommer att kontrollera om filstämpeln för mitt_program är äldre än källkoden men tyvärr är den här makefilen korkat skriven. Ändra den sista regeln, döp om modulen till modul1.o på två ställen i Makefile. Om modul1.c är nyare ska båda filerna kompilera men om enbart mitt_program.c är nyare ska modul1.c inte behöva kompilera om. Prova flera gånger, använd touch för att förnya filstämpeln (t.ex. touch modul1.c)

Den sistnämnda egenskapen är väldigt viktig. Om man ändrar i enbart en fil vill man inte att hela projektet ska kompileras. Stora projekt kan ta ett par timmar att kompilera.

Manualsidor

På alla unix system finns manualsidor om C. Vissa kommandon finns både i C och i operativsystemet. Då måste man förutom kommandot också ange vilket avsnitt i manualen man vill titta i. Prova läsa mansidorna för scanf, printf, gcc genom att i terminalfönstret skriva:

man M 3 scanf
man M 3 printf
man gcc

Dessa man-sidor finns även på nätet. Prova googla efter dem. Läs om flaggor som man kan ge till kompilatorn gcc. F. Vad betyder flaggorna -g och -Wall?

Det är inte bara c-kommandon man kan läsa man-filer om. Det går även att läsa om flera unix-kommandon. Prova man touch. Läs även om olika sätt att kopiera strängar.

Var allokerar malloc

Utöka ditt program med två strängar som allokeras på heapen.

    char * p1 = malloc(sizeof(char[13]));
    char * p2 = malloc(sizeof(char[13]));

Ge dem era tilltalsnamn som värden. Skriv ut värdena och adresserna. Prova om du kan skriva över den ena strängen genom att kopiera till den andra.

Funktionspekare

Skriv en funktion

void foo() {
    printf("Nu körs foo\n");
}

Deklarera en funktionspekare

    void (*funktionspekare)() = foo;

och skriv ut dess adress. Prova skriv ut adressen till main också.

Debugger

Det finns en debugger gdb som man kan använda för att stega igenom sin kod. Du kan läsa om den på nätet (google gdb tutorial) eller man-sidorna. Du måste kompilera med flaggan -g för att kunna debugga ditt program. Prova stega igenom ditt program med debuggern. Det finns olika sätt att stega, dels stega över funktionsanrop (gå till nästa rad) och dels stega in i funktioner.

Jämför om adresserna blir likadana om du kompilerar med -g eller inte. Somliga kompilatorer stoppar om sina variabler ("padding") med lite extra utrymme när man kompilerar med debugflaggan på.

Jämför om det blir skillnad om du kompilerar med optimering påslaget. Gör nya regler i Makefile: mitt_program_debug och mitt_program_optimerad.

Ett alternativ för att felsöka utan debugger är att använda spårutskrifter.

Formaterad utskrift

Du har redan läst manualsidan om printf. Ibland är det lurigt.

    long long s = 11;
    printf("Variabel\t\t Värde\t\t Adress\n");
    printf("s \t\t\t %d \t\t %d\n", s, &s);

G. Varför blir värdet och adressen konstig?

Gör om dina utskriftssatser så att programmet skriver ut en snyggt formaterad tabell sorterad på minnesadresserna. Alla dina variabler inklusive funktionspekarna ska vara med (bör vara minst ett dussin). Programmet ska i princip bara innehålla flera printf-satser

Variabel          Adress            Värde
=========================================================
...

H. Åt vilket håll växer stacken? Deklarera en array (int vek[] = {1, 2, 3, 5, 7}. Skriv ut adresser och värden på enskilda element i en array I. Åt vilket håll växer en array på stacken?

Dags att programmera

Nu är det dags att programmera. Vi ska börja med att göra en länkad lista i C precis som vi tidigare gjort i Python.

Sammansatta datatyper

För att göra den länkade listan behövs en struct. Den motsvarar klasser i Python men man kan inte lägga in metoder utan bara medlemsvariabler i den. Den struktur som behövs för den länkade listan skulle kunna se ut så här:

struct post {
    char name[30];
    int tel;
    struct post * next;
};

För att göra typen lite enklare att skriva kan man använda typedef struct post Post. Då kommer Post att vara identiskt med struct post

Dynamisk minnesallokering

Fördelen med den länkade listan är att man inte behöver specificera en maxlängd vilket vi var tvungna att göra med vektorn. Varje gång vi lägger in ett nytt element allokerar vi en ny Post på heapen med malloc

Post * p = (Post *) malloc(sizeof(Post));

...

p -> next = (Post *) malloc(sizeof(Post));

Eftersom det inte finns någon automatisk skräphanterare i C så måste vi manuellt frigöra minnet med free om vi skulle vilja ta bort posten under programmets gång.

Strukturering .h och .c filer

Gör två filer, lista.h och lista.c. Låt första raden i implementationsfilen (c-filen) inkludera headerfilen (h-filen) men se till att använda en include guard

Deklarera struct post och två funktioner i header-filen. Den ena funktionen ska ta en Post som parameter och sätta in i listan. Den andra ska ta bort en Post ur listan och frigöra minnet. Repetera hur du skulle ha skrivit i python för stack eller kö. Implementera funktionerna i c-filen.

Skapa en ny fil som test_lista.c som inkluderar lista.h. Skriv en main-metod som skriver ut en enkel meny där användaren kan välja mellan att 1) sätta in namn och telefon i listan, 2) ta bort ett namn från listan, 3) söka efter namn, 4) skriva ut hela listan, 5) avsluta. Använd en slinga som i princip ser ut så här:

    printf("Hej och välkommen till testlistaren\n");
    int menyval = 1;
    while (menyval > 0 && menyval <= 5) {
        skrivMeny();                     // skriver ut menyn på skärmen
        scanf("%d", &menyval);
        ...

Observera att när man läser in ett heltal från tangentbordet måste man skicka adressen till heltalet som argument till scanf! Vad händer annars?

Kompilera programmet med gcc -o testlista testlista.c lista.c

Makefile

Skriv en makefile för ditt projekt. Om man enbart ändrar i testlista.c ska inte lista.c behöva kompileras om.

Programmera en hashtabell

Nu är det dags att göra hashtabellen. Som hashfunktion ska en korkad algoritm implementeras. Givet en sträng så returneras siffersumman av de olika bokstävernas ASCII-värden modulo hashvektorns storlek.

För den intresserade finns betydligt bättre hashfunktioner som Robert Jenkins har skrivit men de kan vara svårtydda innan man har lärt sig C.

Skriv hashtabellsimplementationen i två filer hash.h, hash.c och skriv sedan ett nytt huvudprogram i en ny fil. Hashtabellsimplementationen ska använda sig av den länkade listan som krocklista. Utöka din Makefile så att allting kan byggas, även testprogrammet till listan.

Låt testprogrammet läsa flera namn och telefonnummer från en fil när programmet startar. Använd fopen för att öppna filen för läsning och fscanf för att läsa in från filen. Programmet behöver inte kunna spara till filen.

Programmet ska ha en meny där man kan lägga in och plocka ut folk ur hashtabellen precis som för listan. Så här ska det kunna se ut:

Hej och välkommen till kom-ihåg, vad vill du göra?
1) Lägga in ny kontakt
2) Ta bort kontakt
3) Leta upp kontakt
4) Avsluta
>1
Vad heter din nya kompis?  Kalle
Ange telefonnummer?        123131

Kalle är lagrad

Hej och välkommen till kom-ihåg, vad vill du göra?
1) Lägga in ny kontakt
2) Ta bort kontakt
3) Leta upp kontakt
4) Avsluta
...

Innan du redovisar

Repetera dina kunskaper och tänk efter om du kan svara ja på följande:

Jag har svar på de förberedande frågorna
Du kan rita en minnesbild som visar var stacken och heapen ligger
Jag vet hur man söker information på man-sidor.
Jag vet vad en include-guard är och hur preprocessorn fungerar.
Jag vet hur pekare fungerar
Jag vet hur man hanterar dynamiskt minne i C
Mitt program läcker inget minne
Mitt program är uppdelat med deklarationer i .h och implementationer .c filer
Det slutliga hashtabells-projektet består av minst sju filer. Två filer för listan, två filer för hashtabellen, två testprogram, ett för listan och ett för hashtabellen, samt en Makefile
Olika delar av mitt program byggs med make
Jag vet hur make fungerar

Se så superbt ............................................ skålar .............................. den .................

Extrauppgift

För de som tycker labben var för lätt kan ni skissa på följande användning av en länkad lista. Deklarera ett stort utrymme. Dela upp minnet i många lika stora delar. Låt början på varje del vara en pekare till nästa del. Då har ni en länkad lista med ett maximalt antal element och en fix storlek på innehållet. Skriv funktionerna put, get och isFull för din länkade lista.

Ovanstående lista kan användas för att allokera små objekt. Större objekt kan använda malloc. Det är en beprövad teknik om man har ett program som har många små objekt med kort livslängd.