Tölvunarfræði 2 - Vor 2012
Verkefni 2 - Bendar og eintengdir listar
Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 24. janúar fyrir kl 16:00
Dæmi 1 (2 stig)
Skrifið ykkar eigin útgáfu af strchr fallinu í C. Fallið tekur inn streng og bókstaf og skilar bendi á fyrsta staðinn í strengnum þar sem bókstafurinn kemur fyrir eða NULL ef hann kemur hvergi fyrir í strengnum.
Notið beinagrindina hér fyrir neðan og útfærið mystrchr fallið. Ekki breyta main fallinu sem prófar mystrchr.
Beinagrind
#include <stdio.h>
#include <string.h>
char *mystrchr(char *s, int c)
{
}
int main(void)
{
char s[] = "Hello world";
if (mystrchr(s, 'w') == strchr(s, 'w'))
printf("Test 1: Passed\n");
else
printf("Test 1: Failed\n");
if (mystrchr(s, 'a') == NULL)
printf("Test 2: Passed\n");
else
printf("Test 2: Failed\n");
if (mystrchr(s, 'd') == strchr(s, 'd'))
printf("Test 3: Passed\n");
else
printf("Test 3: Failed\n");
if (mystrchr(s, 'H') == strchr(s, 'H'))
printf("Test 4: Passed\n");
else
printf("Test 4: Failed\n");
}
Dæmi 2 (2 stig)
Skrifið fall í C sem brýtur upp strengi. Fallið tekur inn streng (null terminated) og fylki af bendum. Strengnum er skipt upp samkvæmt isspace þ.a. allir bókstafir c þar sem isspace(c) == 1 er skipt út fyrir núll-bæti. Bendarnir í fylkinu vísa síðan á byrjun hvers aðskilda hluta í skipta strengnum.
Notið beinagrindina hér fyrir neðan og útfærið split fallið. Ekki breyta main fallinu.
Staðan fyrir split
Staðan eftir split
Beinagrind
#include <stdio.h>
#include <string.h>
#define MAXARGS 32
// Notkun: n = split(s, argv, maxargs);
// Fyrir: argv er fylki af stærð maxargs, þ.e.
// argv[0..maxargs-1] er leyfilegt svæði
// maxargs er heiltala >= 0
// Eftir: Búið er að brjóta strenginn s upp í n margra
// strengi samkvæmt isspace. Strengirnir eru
// í argv[0..n-1]. argv[i] vísar á streng númer i
// í s, þ.e. argv[0] er fyrsti strengurinn, o.s.frv.
// Öll gildi c í upphaflega strengnum sem uppfylltu
// isspace(c) verða að null-bætum.
int split(char *s, char *argv[], int maxargs)
{
}
int main(void)
{
char s[] = "ab cd ef\t gh";
char *expected[] = {"ab", "cd", "ef", "gh", NULL};
char *argv[MAXARGS];
int argc;
int i;
argc = split(s, argv, MAXARGS);
i = 0;
while (expected[i] != NULL)
{
if (i >= argc)
{
printf("Test failed: Exceeded length\n");
return 1;
}
if (strcmp(argv[i], expected[i]))
{
printf("Test failed: Expected %s got %s\n", expected[i], argv[i]);
return 1;
}
i++;
}
printf("Test passed\n");
return 0;
}
Dæmi 3 (2 stig)
Skrifið fall í C sem tekur inn bendi á haus fyrir eintengdan lista og skilar fjölda hlekkja í listanum.
Notið beinagrindina hér fyrir neðan og útfærið count fallið. Ekki breyta main fallinu.
Beinagrind
#include <stdio.h>
#include <stdlib.h>
struct link
{
int n;
struct link *next;
};
int count(struct link *h)
{
}
int main(void)
{
struct link *h1 = malloc(sizeof(struct link));
struct link *h2 = malloc(sizeof(struct link));
struct link *h3 = malloc(sizeof(struct link));
struct link *h4 = malloc(sizeof(struct link));
h4->n = 40;
h4->next = NULL;
h3->n = 30;
h3->next = h4;
h2->n = 20;
h2->next = h3;
h1->n = 10;
h1->next = h2;
if (count(NULL) == 0)
printf("Test 1: Passed\n");
else
printf("Test 1: Failed\n");
if (count(h4) == 1)
printf("Test 2: Passed\n");
else
printf("Test 2: Failed\n");
if (count(h3) == 2)
printf("Test 3: Passed\n");
else
printf("Test 3: Failed\n");
if (count(h2) == 3)
printf("Test 4: Passed\n");
else
printf("Test 4: Failed\n");
if (count(h1) == 4)
printf("Test 5: Passed\n");
else
printf("Test 5: Failed\n");
}
Dæmi 4 (2 stig)
Skrifið fall í C sem tekur inn heiltölu og bendi á haus fyrir eintengdan lista og skilar hlekk sem inniheldur viðkomandi heiltölu (eða NULL ef ekkert finnst).
Notið beinagrindina hér fyrir neðan og útfærið search fallið. Ekki breyta main fallinu.
Beinagrind
#include <stdio.h>
#include <stdlib.h>
struct link
{
int n;
struct link *next;
};
struct link *search(struct link *h, int k)
{
}
int main(void)
{
struct link *h1 = malloc(sizeof(struct link));
struct link *h2 = malloc(sizeof(struct link));
struct link *h3 = malloc(sizeof(struct link));
struct link *h4 = malloc(sizeof(struct link));
h4->n = 40;
h4->next = NULL;
h3->n = 30;
h3->next = h4;
h2->n = 20;
h2->next = h3;
h1->n = 10;
h1->next = h2;
if (search(NULL, 10) == NULL)
printf("Test 1: Passed\n");
else
printf("Test 1: Failed\n");
if (search(h1, 10) == h1)
printf("Test 2: Passed\n");
else
printf("Test 2: Failed\n");
if (search(h1, 20) == h2)
printf("Test 3: Passed\n");
else
printf("Test 3: Failed\n");
if (search(h1, 30) == h3)
printf("Test 4: Passed\n");
else
printf("Test 4: Failed\n");
if (search(h1, 40) == h4)
printf("Test 5: Passed\n");
else
printf("Test 5: Failed\n");
if (search(h1, 50) == NULL)
printf("Test 6: Passed\n");
else
printf("Test 6: Failed\n");
}
Dæmi 5 (2 stig)
Skrifið fall í C sem tekur inn bendi á haus fyrir eintengdan lista og snýr listanum við (án þess að búa til nýjan lista).
Notið beinagrindina hér fyrir neðan og útfærið reverse fallið. Ekki breyta main fallinu.
Beinagrind
#include <stdio.h>
#include <stdlib.h>
struct link
{
int n;
struct link *next;
};
struct link *reverse(struct link *h)
{
}
void printlist(struct link *h)
{
struct link *p = h;
while (p != NULL)
{
printf("%d\n", p->n);
p = p->next;
}
}
int test(struct link *h, int f[], int n)
{
int i;
for (i = 0; i < n; i++)
{
if (h == NULL)
return 0;
if (h->n != f[i])
return 0;
h = h->next;
}
return 1;
}
int main(void)
{
struct link *p;
int f[] = {40,30,20,10};
struct link *h1 = malloc(sizeof(struct link));
struct link *h2 = malloc(sizeof(struct link));
struct link *h3 = malloc(sizeof(struct link));
struct link *h4 = malloc(sizeof(struct link));
h4->n = 40;
h4->next = NULL;
h3->n = 30;
h3->next = h4;
h2->n = 20;
h2->next = h3;
h1->n = 10;
h1->next = h2;
printf("Before:\n");
p = h1;
printlist(p);
printf("After:\n");
p = reverse(h1);
printlist(p);
if (test(p, f, 4))
printf("Test passed\n");
else
printf("Test failed\n");
}