Tölvunarfræði 2 - Vor 2012


Verkefni 3 - Strengir, I/O, fallbendar


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 31. janúar fyrir kl 16:00

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.

Beinagrind

Beinagrind í ZIP skrá: reverse.zip

Prófun

Inntak:
ABC
DEF
GHI
Úttak:
GHI
DEF
ABC

Lesefni

fgets(3)

Sýnidæmi

Dæmi um notkun fgets

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.

Dæmi um stakt kall á fallbendinn fyrir skrá:

fn('F', "/home/hhg/t2/V3/walker/walker.c", "walker.c", &st);
// þar sem st er struct stat fyrir viðkomandi skrá

Dæmi um stakt kall á fallbendinn fyrir möppu:

fn('D', "/home/hhg/t2/V3/walker", "walker", &st);
// þar sem st er struct stat fyrir viðkomandi möppu

Þið eigið ekki að breyta main eða printfile.

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

Dæmi um notkun readdir

Þetta forrit les bara eina möppu. Ykkar forrit á að lesa möppu og allar undirmöppur.

ATH. Ef það kemur upp villu um "undefined reference to lstat" þá nægir að breyta lstat yfir í stat og allt ætti að virka sem skyldi.


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.

Beinagrind

#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)
	{
		// Notið realloc til að stækka fylkið ef þess þarf
		// Lesið línu með readline (munið að athuga NULL)
		// Látið línuna í fylkið
	}

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

	// Prentið út allar línurnar
}

Lesefni

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

Sýnidæmi

Dæmi um notkun realloc

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

Beinagrind

#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++)
	{
		// Leita eftir orðinu í fylkinu
		// ....
		// (Notið strcmp)
	}

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

	h = malloc(sizeof(struct word));
	// Frumstilla og bæta h í words

	return h;
}

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

	state_init(&state);

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

		// ...
	}

	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)   strdup(3)