Tilføjede en masse

4 files changed, 200 insertions, 1 deletions

diff --git a/sem1/algo/mm10/bfs.c b/sem1/algo/mm10/bfs.c
new file mode 100644
index 0000000..982ecef
--- /dev/null
+++ b/sem1/algo/mm10/bfs.c
@@ -0,0 +1,163 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#define COL_WHITE 0
+#define COL_GRAY  1
+#define COL_BLACK 2
+
+typedef struct list_node_t_struct {
+	struct list_node_t_struct *next;
+	void *val;
+} list_node_t;
+
+typedef struct vertex_struct {
+	char ref;
+	int color;
+	int dist;
+	struct vertex_struct *p;
+	list_node_t *adj;
+} vertex_t;
+
+vertex_t *create_vertex(char ref) {
+	// Get some space TODO check for null
+	vertex_t *v = malloc(sizeof(vertex_t));
+
+	// Set values
+	v->ref = ref;
+	v->color = COL_WHITE;
+	v->dist = -1;
+	v->p = NULL;
+	v->adj = NULL;
+}
+
+vertex_t *add_adj(vertex_t *v, vertex_t *add) {
+	list_node_t *oldN = v->adj;
+
+	// Create new list node
+	list_node_t *n = malloc(sizeof(list_node_t));
+	n->val = add;
+	n->next = oldN;
+
+	v->adj = n;
+
+	return add;
+}
+
+void print_adj(vertex_t *v) {
+	list_node_t *n = v->adj;
+	printf("[ ");
+	while(n) {
+		printf("%c ", *((char *)n->val));
+		n = n->next;
+	}
+	printf("]\n");
+}
+
+vertex_t *vertexes[128];
+
+void add_edge(char a, char b) {
+	// Does a exists
+	if( vertexes[a] == NULL ) {
+		vertexes[a] = create_vertex(a);
+	}
+	// What about b
+	if( vertexes[b] == NULL ) {
+		vertexes[b] = create_vertex(b);
+	}
+
+	// Add edge
+	add_adj(vertexes[a], vertexes[b]);
+}
+
+typedef struct {
+	unsigned int len;
+	list_node_t *in;
+	list_node_t *out;
+} queue_t;
+
+void enqueue(queue_t *q, vertex_t *v) {
+	list_node_t *n = malloc(sizeof(list_node_t));
+	n->val = v;
+
+	// Add at end
+	list_node_t *old = q->in;
+	q->in = n;
+	if( old ) {
+		old->next = n;
+	}
+
+	// Make sure we have an out
+	if( q->out == NULL ) {
+		q->out = n;
+	}
+
+	q->len++;
+}
+
+vertex_t *dequeue(queue_t *q) {
+	list_node_t *n = q->out;
+	if( n == NULL ) {
+		return NULL;
+	}
+	vertex_t *v = (vertex_t *)n->val;
+
+	// Move out forward
+	q->out = n->next;
+	q->len--;
+
+	// Free node and return
+	free(n);
+	return v;
+}
+
+void bfs(vertex_t *s) {
+	queue_t q = {0, NULL, NULL };
+	enqueue(&q, s);
+	s->dist = 0;
+	
+	while( q.len ) {
+		vertex_t *u = dequeue(&q);
+		list_node_t *n = u->adj;
+		while( n ) {
+			vertex_t *v = (vertex_t *)n->val;
+			if( v->color == COL_WHITE ) {
+				v->color = COL_GRAY;
+				v->dist = u->dist + 1;
+				v->p = u;
+				enqueue(&q, v);
+			}
+			n = n->next;
+		}
+		u->color = COL_BLACK;
+	}
+	
+}
+
+int main() {
+	add_edge('s', 'd'); // S
+	add_edge('s', 'c');
+	add_edge('s', 'a');
+	add_edge('d', 'e'); // D
+	add_edge('d', 'c');
+	add_edge('e', 'g'); // E
+	add_edge('e', 'f');
+	add_edge('c', 's'); // C
+	add_edge('c', 'g');
+	add_edge('g', 'f'); // G
+
+	//print_adj(vertexes['d']);
+	bfs(vertexes['s']);
+
+	char c;
+	while( (c = getchar()) != EOF) {
+		if( vertexes[c] != NULL ) {
+			print_adj(vertexes[c]);
+			printf("%d\n", vertexes[c]->dist);
+		} else if (c == 10) {
+		} else {
+			printf("Not found\n");
+		}
+	}
+
+
+}
diff --git a/sem1/osc/mm11/opgaver.md b/sem1/osc/mm11/opgaver.md
new file mode 100644
index 0000000..09edad0
--- /dev/null
+++ b/sem1/osc/mm11/opgaver.md
@@ -0,0 +1,25 @@
+# Opgave 1
+
+Mange af dem er okay.
+
+```
+<program> ::= 'program''(' <ident> ')' <statementlist> 'end'.
+<statementlist> ::= <statement> <statementlist> | e
+<statement> ::= <ident> '=' <exp>;
+
+<exp> ::= <term> <expB>
+<expB> ::= <termopr> <term> <expB> | e
+
+<term> ::= <factor> <termB>
+<termB> ::= <factoropr> <factor> <termB> | e
+<termopr> ::= '+' | '-'
+
+<factor> ::= '(' <exp> ')' | <ident>
+<factoropr> ::= '*' | '/'
+```
+
+# Opgave 2
+
+Denne laver jeg måske senere.
+
+# Opgave 3
diff --git a/sem1/osc/mm9/opgaver.md b/sem1/osc/mm9/opgaver.md
index a16f069..fe2ec99 100644
--- a/sem1/osc/mm9/opgaver.md
+++ b/sem1/osc/mm9/opgaver.md
@@ -111,7 +111,7 @@ digit -> *0* | ... | *9*
 symbol -> letter | digit
 symList -> symbol symList | e
 exp -> term expB
-exp -> termopr term expB | e
+expB -> termopr term expB | e
 termOpr -> *+* | *-*
 term -> factor termB
 termB -> factorOpr factor termB | e
diff --git a/sem1/osc/noter.md b/sem1/osc/noter.md
new file mode 100644
index 0000000..92f875a
--- /dev/null
+++ b/sem1/osc/noter.md
@@ -0,0 +1,11 @@
+# HUsk
+
+Ikke Deterministisk: Et stadie i kan føre til flere andre states.
+
+Undersøg **kontekst fri**
+
+Leksikal analysen: bruger regulær
+
+Parsing: ikke regulær.
+
+Shift-reduce parser.