Tölvunarfræði 2 - Vor 2012

---

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.

Lausn

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

char *mystrchr(char *s, int c)
{
    if (s == NULL)
        return NULL;

    while (*s)
    {
        if (*s == c)
            return s;

        s++;
    }

    return NULL;
}

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.

Staðan fyrir split

Staðan eftir split

Lausn

#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 i = 0;

    while (*s && i < maxargs)
    {
        while (*s && isspace(*s))
            *s++ = 0;

        if (!*s)
            break;

        argv[i++] = s;

        while (*s && !isspace(*s))
            s++;
    }

    return i;
}

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.

Lausn

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

struct link
{
    int n;
    struct link *next;
};

int count(struct link *h)
{
    int n = 0;

    while (h != NULL)
    {
        n++;
        h = h->next;
    }

    return n;
}

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).

Lausn

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

struct link
{
	int n;
	struct link *next;
};

struct link *search(struct link *h, int k)
{
	while (h != NULL)
	{
		if (h->n == k)
			return h;

		h = h->next;
	}

	return NULL;
}

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).

Lausn

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

struct link
{
    int n;
    struct link *next;
};

struct link *reverse(struct link *h)
{
    struct link *tmp;
    struct link *rh = NULL;

    // h  -> [x1|.] -> [x2|.] -> [x3|.] -> ... [xn|/]
    // rh -> /

    while (h != NULL)
    {
        // h  -> [xi|.]   -> [xi+1|.] -> [xi+2|.] -> ...    -> [xn|/]
        // rh -> [xi-1|.] -> ...      -> [x3|.]   -> [x2|.] -> [x1|/]

        tmp = h;
        h = h->next;

        // h    -> [xi+1|.] -> [xi+2|.] -> ...    -> [xn|/]
        // tmp  -> [xi|.]   -> [xi+1|.] -> [xi+2|.] -> ...    -> [xn|/]

        tmp->next = rh;
        rh = tmp;

        // h  -> [xi+1|.] -> [xi+2|.] -> ...   -> [xn|/]
        // rh -> [xi|.]   -> [xi-1|.] -> ...   -> [x3|.]   -> [x2|.] -> [x1|/]
    }

    // h  -> /
    // rh -> [xn|.] -> [xn-1|.] -> ...-> [x3|.] -> [x2|.] -> [x1|/]

    return rh;
}

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");
}