diff options
| -rw-r--r-- | sem1/algo/mm10/bfs.c | 163 | ||||
| -rw-r--r-- | sem1/osc/mm11/opgaver.md | 25 | ||||
| -rw-r--r-- | sem1/osc/mm9/opgaver.md | 2 | ||||
| -rw-r--r-- | sem1/osc/noter.md | 11 |
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. |