Tölvunarfræði 2 - Vor 2012


Verkefni 3 - Strengir, I/O, fallbendar - Sýnislausn


Dæmi 1 (2 stig)


Skrifið forrit sem les línur af aðalinntaki og skrifar þær í öfugri röð á aðalúttak. Forritið á að nota hlaða, sem fylgir með beinagrindinni, til að víxla röðinni. Forritið má gera ráð fyrir að hámarkslengd línu sé 8192 bæti með núll-bætinu.

Lausn


#include <stdio.h>
#include "stack.h"

int main(void)
{
	char buf[8192];
	struct stack s;

	stack_init(&s);

	while (1)
	{
		if (fgets(buf, sizeof(buf), stdin) == NULL)
			break;

		stack_push(&s, buf);
	}

	while (!stack_empty(&s))
	{
		printf("%s", stack_pop(&s));
	}
}

Beinagrind


Beinagrind í ZIP skrá: reverse.zip

Lesefni


fgets(3)

Dæmi 2 (4 stig)


Klárið útfærslu á walktree fallinu í beinagrindinni. Fallið tekur inn fallbendi og bendi á streng sem inniheldur slóð í skráarkerfinu. Fallið gengur yfir allar skrár og möppur sem liggja undir slóðinni og fyrir hverja skrá/möppu þá er kallað á fallbendinn með viðföngum sem lýsa þeirri tilteknu skrá/möppu.

Forritið á að nota hlaða, sem fylgir með beinagrindinni, til að halda utan um möppur sem á eftir að heimsækja. Í upphafi þá er uppgefin slóð sett á hlaðann, en síðan í hvert skipti sem fallið rekst á möppu í göngunni þá er hún sett á hlaðann. Fallið lýkur keyrslu þegar hlaðinn er tómur.

Lausn


#include <stdio.h>
#include <dirent.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include "stack.h"

#include <errno.h>
#include <string.h>

int walktree(char *root, void (*fn)(char type, char *path, char *fn, struct stat *st))
{
	DIR *dir;
	struct dirent *entry;
	struct stat st;
	char buf[8192];
	struct stack s;

	stack_init(&s);
	stack_push(&s, root);

	while (!stack_empty(&s))
	{
		char *dp = stack_pop(&s);

		dir = opendir(dp);

		if (dir == NULL)
		{
			free(dp);
			continue;
		}

		while ((entry = readdir(dir)))
		{
			if (entry->d_name[0] == '.')
				continue;

			snprintf(buf, sizeof(buf), "%s/%s", dp, entry->d_name);

			if (lstat(buf, &st) < 0)
				continue;

			if (S_ISDIR(st.st_mode))
			{
				fn('D', buf, entry->d_name, &st);
				stack_push(&s, buf);
			}
			else if (S_ISREG(st.st_mode))
			{
				fn('F', buf, entry->d_name, &st);
			}
		}

		closedir(dir);
		free(dp);
	}
}

void printfile(char type, char *path, char *fn, struct stat *st)
{
	if (type == 'D')
		printf("%c %s\n", type, path);
	else
		printf("%c %s (%ld bytes)\n", type, path, st->st_size);
}

int main(int argc, char *argv[])
{
	if (argc < 2)
	{
		fprintf(stderr, "usage: walker <path>\n");
		return 1;
	}

	walktree(argv[1], printfile);

	return 0;
}

Ef forritið virkar rétt þá ætti að vera hægt að keyra það með einu viðfangi (slóð á möppu) og fá út lista eins og hér fyrir neðan.


Dæmi um notkun


hhg@hhg:~/t2/V3/walker$ ./walker /home/hhg/t2/V3
D /home/hhg/t2/V3/walker
F /home/hhg/t2/V3/sort.c (973 bytes)
F /home/hhg/t2/V3/dirprint.c (592 bytes)
F /home/hhg/t2/V3/count.c (1038 bytes)
F /home/hhg/t2/V3/sort (7509 bytes)
F /home/hhg/t2/V3/count (7433 bytes)
D /home/hhg/t2/V3/reverse
F /home/hhg/t2/V3/reverse/Makefile (190 bytes)
F /home/hhg/t2/V3/reverse/reverse.c (274 bytes)
F /home/hhg/t2/V3/reverse/reverse.o (1228 bytes)
F /home/hhg/t2/V3/reverse/stack.h (365 bytes)
F /home/hhg/t2/V3/reverse/stack.c (583 bytes)
F /home/hhg/t2/V3/reverse/stack.o (1096 bytes)
F /home/hhg/t2/V3/reverse/reverse (7525 bytes)
F /home/hhg/t2/V3/walker/Makefile (210 bytes)
F /home/hhg/t2/V3/walker/walker.o (51596 bytes)
F /home/hhg/t2/V3/walker/stack.h (365 bytes)
F /home/hhg/t2/V3/walker/walker.c (1226 bytes)
F /home/hhg/t2/V3/walker/stack.c (582 bytes)
F /home/hhg/t2/V3/walker/walker (80677 bytes)
F /home/hhg/t2/V3/walker/stack.o (27436 bytes)
hhg@hhg:~/t2/V3/walker$ 

Beinagrind


Beinagrind í ZIP skrá: walker.zip

Lesefni


opendir(3)   readdir(3)   snprintf(3)   lstat(2)

Sýnidæmi


Forrit úr fyrirlestri 25. jan

Dæmi 3 (2 stig)


Skrifið forrit sem les línur af aðalinntaki og skrifar þær í vaxandi stafrófsröð á aðalúttak.

Notið beinagrindina hér fyrir neðan og klárið útfærsluna.


Lausn


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

char *readline(FILE *fp)
{
	size_t size = 0;
	size_t len = 0;
	size_t last = 0;
	char *buf = NULL;

	while (!feof(fp))
	{
		size += BUFSIZ;
		buf = realloc(buf, size);

		if (fgets(buf+last, size-last, fp) == NULL)
			break;

		len = strlen(buf);
		last = len - 1;

		if (buf[last] == '\n')
			break;
	}

	if (len == 0)
	{
		free(buf);
		return NULL;
	}

	return buf;
}

int cmp(const void *va, const void *vb)
{
	const char *a = *(char * const *)va;
	const char *b = *(char * const *)vb;

	return strcmp(a, b);
}

int main(void)
{
	char **lines;
	size_t size = 1024;
	int n = 0;
	int i;

	lines = malloc(sizeof(char *) * size);

	while (1)
	{
		if (n >= size)
		{
			size *= 2;
			lines = realloc(lines, sizeof(char *) * size);
		}

		char *line = readline(stdin);

		if (line == NULL)
			break;

		lines[n++] = line;
	}

	qsort(lines, n, sizeof(char *), cmp);

	for (i = 0; i < n; i++)
		printf("%s", lines[i]);
}

Lesefni


qsort(3)   malloc(3)   realloc(3)  

Sýnidæmi


Forrit úr fyrirlestri 25. jan

Dæmi 4 (2 stig)


Skrifið forrit sem les orð af aðalinntaki og prentar út á aðalúttak hversu oft hvert orð kemur fyrir í inntakinu.

Notið beinagrindina hér fyrir neðan og klárið útfærsluna.

(Athugið að þetta forrit notar mjög hægvirka línulega leit, það er leitað í öllu fylkinu í hverri uppflettingu, en seinna í námskeiðinu munið þið læra betri aðferðir.)


Lausn


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

struct word
{
	char *word;
	int count;
};

struct state
{
	struct word **words;
	size_t alloc;
	size_t len;
};

void state_init(struct state *s)
{
	s->alloc = 8192;
	s->len = 0;
	s->words = malloc(sizeof(struct word *) * s->alloc);
}

struct word *state_get(struct state *s, char *word)
{
	int i;
	struct word *h;

	for (i = 0; i < s->len; i++)
	{
		if (!strcmp(s->words[i]->word, word))
			return s->words[i];
	}

	if (s->len >= s->alloc)
	{
		s->alloc *= 2;
		s->words = realloc(s->words, sizeof(struct word *) * s->alloc);
	}

	h = malloc(sizeof(struct word));
	h->word = strdup(word);
	h->count = 0;

	s->words[s->len] = h;
	s->len++;

	return h;
}

int main(void)
{
	char buf[8192];
	struct state state;
	int i;

	state_init(&state);

	while (1)
	{
		if (scanf("%8191s", buf) != 1)
			break;

		struct word *w = state_get(&state, buf);
		w->count++;
	}

	for (i = 0; i < state.len; i++)
	{
		struct word *w = state.words[i];
		printf("%s: %d\n", w->word, w->count);
	}
}

Lesefni


scanf(3)   strcmp(3)   malloc(3)   realloc(3)