p3

  • Inlämningsdatum 31 mar 2021 av 23.59
  • Poäng 1
  • Lämnar in en filuppladdning
  • Filtyper c, h och txt

1 p3

Syftet med den här laborationen är att lära sig programmeringspråket C. Det mesta arbetet ska göras utanför labbtid. Förutom labbtillfällena finns allmänhandledningen där en ensam hjälphandledare handleder studenter på flera kurser.

1.1 Innan du programmerar

 

1.1.1 Verktyg

Vi kommer att använda kompilatorn gcc Links to an external site.. Om du sitter på linux/ubuntu eller windows med ubuntu kan du installera gcc och flera andra verktyg med apt-get

sudo apt-get install build-essential

1.1.2 Att läsa på

Läs på de tre första kapitlen i Ted Jensens tutorial om pekare i C Links to an external site. innan du börjar. Kapitel 1-5 samt 9 är viktiga för den här labben.

1.2 Ett första program

#include <stdio.h>
#include <time.h>

int getyear() {
    time_t timer;
    time(&timer);
    struct tm* tm_info = localtime(&timer);
    return tm_info->tm_year + 1900;
}

int main() {
    printf("Hej vad heter du? ");
    char str [5];
    scanf("%s", str);

    int age;
    printf("Hur gammal är du? ");
    fscanf(stdin, "%d", &age);

    int thisyear = getyear();

    printf("Hej %s, i år är det %d. ", str, thisyear);
    if (2000 + age == thisyear)
	printf("Du skulle kunna vara född på 1900-talet\n");
    else if (2000 + age > thisyear)
	printf("Du är född på 1900-talet!\n");
    else
	printf("Du är född på 2000-talet!\n");        
}

Raden #include <stdio.h> ger tillgång till scanf, fscanf och printf Prova att tillfälligt ta bort/kommentera #include-satsen kompilera och se vad som händer.

Programmet förväntar sig inmatning från terminalen via funktionen scanf/fscanf som du måste anropa med en adress till ett minne som ska fyllas. Prova kör programmet med ett kort namn (t.ex. Eva) och ett långt namn (t.ex. Alexander). Vad händer eller borde hända? Varför?

Programmet skriver ut med printf som använder sig av platshållare för att skriva ut formaterat Links to an external site.. För att skriva ut en tredjedel med tre decimaler kan du skriva:

printf("1/3 = %.3f\n", 1/3.0);

1.2.1 Överkurs - getyear

Du förväntas inte kunna redogöra för hur getyear fungerar i denna labb.

Funktionen getyear returnerar innevarande år. Först deklareras en timer av typ timet (ett slags heltal). Därefter anropas localtime som returnerar en pekare till en struct som fyllts med lokalt tidsdata (år, månad, dag, timme etc). Historiskt har tid i datorers operativsystem mätts som millisekunder sedan 1:a januari 1970 00:00 vilket kan visa sig bli problematiskt om man mäter denna tid med en int Links to an external site. därav speciella datatyper som timet.

1.2.2 länkningsfel vs kompileringsfel

Programmet har en hårdkodad 5:a ta bort hårdkodningen och deklarera en konstant global variabel maxlength (ovanför main) som du sätter till 30, kompilera och provkör.

const int maxlength = 30;

Gör en ny fil som heter konstanter.c den ska innehålla en enda rad

const int maxlength = 30;

Kompilera filen med gcc -c konstanter.c notera att maskinkodsfilen konstanter.o bildas.

Kompilera huvudprogrammet och länka till konstanter.o genom att ta filen på kommandoraden.

gcc mitt_program.c konstanter.o

Eftersom maxlength är definierad på två ställen så får du ett länkningsfel (ld returned 1 exit status). Kommentera bort maxlength i mitt_program.c och kompilera igen.


// const int maxlength = 30;

Då får du ett kompileringsfel (troligen undeclared identifier) eftersom maxlength inte är definierad.

För att använda maxlength i konstanter.c så kan du deklarera maxlength som extern i mitt_program.c

// const int maxlength = 30;
extern const int maxlength;

Prova nu att kompilera och länka till konstanter.c eller konstanter.o

gcc mitt_program.c konstanter.c
gcc mitt_program.c konstanter.o 

Om du skriver konstanter.o så kommer kompilatorn länka utan att kompilera om kontanter.c. Om du skriver konstanter.c så ber du kompilatorn kompilera om konstanter.c och sedan länka (men utan att skapa en ny konstanter.o)

Prova ännu en gång att kompilera utan att länka till konstanter.o

gcc mitt_program.c

Då får du ännu en gång ett länkningsfel (troligen undefined reference).

 

Makefile

Programmet make är ett gammalt program som används för att bygga projekt med många källkodsfiler. För att slippa kompilera om samtliga filer så indersöker makefilstämpeln. Instruktionerna till make förutsätts ligga i en fil som heter Makefile (observera att det inte ska vara någon filändelse), skapa en fil med namnet Makefile och klistra in följande innehåll. De inskjutna raderna ska innehålle ett <TAB>-tecken och inte mellanslag. 

mittprogram: mitt_program.c konstanter.o
	gcc -o mittprogram mitt_program.c konstanter.o

konstanter.o: konstanter.c
	gcc -c konstanter.c

Kompilera ditt program genom att skriva

make mittprogram

Öppna kontanter.c och lägg till en tom ny rad och spara. Kompilera två gånger med /make/x

make mittprogram
make mittprogram

Notera att första gången kompileras konstanter.o men inte andra gången eftersom tidsstämpeln för konstanter.o är nyare än den för konstanter.c

1.3 Var allokeras variabler i minnet.

Skriv in följande början på ett program i en fil minne.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

long foo(void * a) {
    long offset = 4196518;
    long adr = (long) a;
    return adr - offset;
}

int main(int argc, char * argv[]) {
    int a = 1;
    char tkn = 't';
    int v[] = {1, 3, 5};

    int * vdyn = malloc(sizeof(int) * 2);
    vdyn[0] = 7;
    vdyn[1] = 4;

    char * staticstr = "Hej";

    char * sv = malloc(sizeof(char) * 11);
    strcpy(sv, staticstr);    // kopierar sträng se frl-anteckningar

    printf("variabel        adress            värde\n");
    printf("---------------------------------------\n");
    printf("a               %p      %d\n"      , &a        , a);
}

Programmet ska skriva ut alla variabler, deras värden och minnesadresser. Gör färdigt programmet med fler print-satser så att alla variabler och dess adresser skrivs ut. Se till att tabellen blir snygg!

printf("variabel        adress            värde\n");
printf("---------------------------------------\n");
printf("a               %p      %d\n"      , &a        , a);
printf("tkn             %p      %c\n"      , &tkn      , tkn);
printf("v               %p      %d \n"     , v         , *v);
printf("v[1]            %p      %d \n"     , (v + 1)     , *(v + 1));
printf("v[2] ... gör klart programmet med alla variabler

Skriv även ut adressen till funktionen foo

printf("foo             %p      \n"        , &foo);

Adresserna skrivs ut hexadecimalt. Du kan konvertera värdena i python

python3
>>> print(0x7ffd15ee9994)
140724971411860

Om du föredrar att ditt program skriver ut decimala värden kan du typkonvertera till long. Prova

printf("variabel        adress            värde\n");
printf("---------------------------------------\n");
printf("a               %ld      %d\n"      ,(long)  &a        , a);
printf("tkn             %ld      %c\n"      ,(long)  &tkn      , tkn);
printf("v               %ld      %d \n"     ,(long)  v         , *v);
printf("v[1]            %ld      %d \n"     ,(long)  (v + 1)    , *(v + 1));
  • Kör programmet flera gånger, hamnar alltid variablerna på samma ställe?
  • Rita en bild över minnet (en stor array med index 0 längst till vänster) och rita in var variablerna hamnar.
    • Lägg märke till vilka variabler som hamnar nära varandra.
    • Var särskilt noga med att rita in var array-element hamnar och i vilken ordning de ligger.

2 Programmeringsuppgift

Du ska implementera en dubbellänkad lista som har en pekare till nästa nod (next) och en pekare till föregående nod (prev). Den lista du implementerar ska inte läcka minne. Se till att du läst Ted Jensens pekartutorial kapitel 1-5 samt kap 9 (översiktligt) innan du börjar och läs om pekartutorialen åtminstone en gång medan du programmerar. 

Det är nyttigt att rita minnesbilder när man programmerar länkade listor.
Du kan även använda http://pythontutor.com/c.html#mode=edit Links to an external site. för att visualisera en kodexekvering.

2.1 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 dubbellänkade listan ska se ut så här:

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

För att göra typen lite enklare att skriva kan man använda typedef Links to an external site.

typedef struct nod Nod;

Då kommer Nod att vara identiskt med struct nod

2.2 Dynamisk minnesallokering

En fördel med den länkade listor är att man inte behöver specificera en maxlängd vilket vi var tvungna att göra med en array. Varje gång vi lägger in ett nytt element allokerar vi en ny Nod på heapen med malloc

Nod * p =  malloc(sizeof(Nod));
//...
p -> next =  malloc(sizeof(Nod));
p -> next -> prev = p;

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 noden under programmets gång.

Skriv ett program leak.c med följande innehåll

#include <stdlib.h>

struct nod {
    char name[30];
    int tel;
    struct nod * next;
    struct nod * prev;
};
typedef struct nod Nod;

int main() {
    Nod * p =  malloc(sizeof(Nod));
    p -> next =  malloc(sizeof(Nod));
    p -> next -> prev = p;
    free(p);
}

Programmet går att kompilera och köra men läcker minne. På vilket sätt läcker programmet minne? Rita och förklara.

2.2.1 Upptäcka minnesläckor med valgrind

Verktyget valgrind Links to an external site. (/ˈvælɡrɪnd/ Links to an external site.) kontrollerar om ett program läcker minne. Om du har valgrind installerat kan du prova att kompilera med debugflaggan -g och sedan köra valgrind på ditt program.

gcc -g leak.c
valgrind ./a.out

2.2.2 Upptäcka minnesläckor med gcc flaggor -fsanitize

Man kan även prova att kompilera med kompilatorargument till gcc. Det fungerar inte på alla plattformar. När man kör programmet får man reda på var minnet som läcks är allokerat.

gcc -fsanitize=address -fno-omit-frame-pointer -g leak.c
./a.out

2.3 Uppdelning i header och implementationsfil

Gör två filer, lista.h och lista.c. Låt första raden i implementationsfilen (lista.c) inkludera headerfilen (lista.h) men se till att använda en include guard Links to an external site. i headerfilen. Se F6, Skapa C-program.

Headerfilen ska ha följande funktioner:

struct nod {
    char name[30];
    int tel;
    struct nod * next;
    struct nod * prev;
};
typedef struct nod Nod;

void insertnod(Nod ** padr, Nod * tobeadded);
void removenod(Nod ** padr, Nod * toberemoved);
void printnod(Nod * p);
void printlist(Nod * p);
Nod * search(Nod * p, int tel);
insertnod lägger till noden tobeadded i listan padr
removenod tar bort noden toberemoved ur listan padr och frigör minnet
printnod skriver ut en nod
printlist skriver ut alla noder i listan
search letar efter tel i listan p och returnerar noden

2.3.1 Randvillkor, särfall att testa

När man programmerar länkade listor bör man i allmänhet tänka på

  • Tomma listan
  • Ett element i listan
  • Sista elementet i listan

När vi lägger till ett nytt element i en tom lista så vill vi att pekaren utanför funktionen insertnod ska ändras. Det är därför vi skickar adressen till pekaren.

Nod * root = NULL;
Nod * ny = malloc(sizeof(Nod));
ny->tel = 1122;
ny->next = NULL;
//...
insertnod(&root, ny);

2.4 Testkod

Skriv ett testprogram som lägger till, söker efter och tar bort noder ur en eller två olika listor. Det kan vara till hjälp att skriva några hjälpfunktioner t.ex. en funktion som skapar en nod. Lägg testkoden och din main-funktion i en tredje fil, t.ex. p3.c, som inkluderar lista.h. Kompilera och länka med

gcc p3.c lista.c

Testa att ditt program inte läcker minne och inte kraschar. Om du inte kan installera valgrind kan du kopiera programmet till skolans datorer och testa m.hj.a valgrind på en av dessa. Du kan logga in på skolans dator hemifrån med ssh

ssh DITTKTHLOGIN@student-shell.sys.kth.se

 

1617227999 03/31/2021 11:59pm