From 0887d8f96950a060a122e14ed2981182ff1eb37d Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 28 Dec 2019 21:16:58 +0700 Subject: [usth/ICT2.1] Algorithm and Data Structures --- usth/ICT2.1/labwork/3/Ex1.c | 38 ++++++++++++++++++++++++ usth/ICT2.1/labwork/3/Ex2.c | 61 ++++++++++++++++++++++++++++++++++++++ usth/ICT2.1/labwork/3/Ex3.c | 46 ++++++++++++++++++++++++++++ usth/ICT2.1/labwork/3/README.md | 42 ++++++++++++++++++++++++++ usth/ICT2.1/labwork/3/TT3.pdf | Bin 0 -> 379634 bytes usth/ICT2.1/labwork/3/construct.c | 26 ++++++++++++++++ usth/ICT2.1/labwork/3/construct.h | 14 +++++++++ usth/ICT2.1/labwork/3/stack.c | 39 ++++++++++++++++++++++++ usth/ICT2.1/labwork/3/stack.h | 16 ++++++++++ 9 files changed, 282 insertions(+) create mode 100644 usth/ICT2.1/labwork/3/Ex1.c create mode 100644 usth/ICT2.1/labwork/3/Ex2.c create mode 100644 usth/ICT2.1/labwork/3/Ex3.c create mode 100644 usth/ICT2.1/labwork/3/README.md create mode 100644 usth/ICT2.1/labwork/3/TT3.pdf create mode 100644 usth/ICT2.1/labwork/3/construct.c create mode 100644 usth/ICT2.1/labwork/3/construct.h create mode 100644 usth/ICT2.1/labwork/3/stack.c create mode 100644 usth/ICT2.1/labwork/3/stack.h (limited to 'usth/ICT2.1/labwork/3') diff --git a/usth/ICT2.1/labwork/3/Ex1.c b/usth/ICT2.1/labwork/3/Ex1.c new file mode 100644 index 0000000..90b3ca5 --- /dev/null +++ b/usth/ICT2.1/labwork/3/Ex1.c @@ -0,0 +1,38 @@ +/* + * Reverse name from stdin. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include +#include + +#include "stack.h" + +int main() +{ + stack *s = mkstack(); + char c, *p; + + while ((c = getchar()) != EOF) { + p = malloc(sizeof(char *)); + *p = isspace(c) ? 32 : c; + stack_push(s, p); + } + + while (!stack_empty(s) && *(char *) stack_top(s) == 32) { + p = stack_pop(s); + free(p); + } + + c = 32; + while (!stack_empty(s)) { + p = stack_pop(s); + putchar(c == 32 ? toupper(c = *p) : tolower(c = *p)); + free(p); + } + + putchar(10); + + return 0; +} diff --git a/usth/ICT2.1/labwork/3/Ex2.c b/usth/ICT2.1/labwork/3/Ex2.c new file mode 100644 index 0000000..49be21b --- /dev/null +++ b/usth/ICT2.1/labwork/3/Ex2.c @@ -0,0 +1,61 @@ +/* + * Add hard-coded names to a queue a print them to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include + +#include "construct.h" + +typedef struct { + construct *front; + construct *rear; +} queue; + +queue *mkq() +{ + queue *q = malloc(sizeof(queue)); + q->front = q->rear = NULL; +} + +int qempty(queue *q) +{ + return q->front == NULL; +} + +void qpush(queue *q, void *item) +{ + if (qempty(q)) + q->front = q->rear = cons(item, NULL); + else + q->rear = q->rear->cdr = cons(item, NULL); +} + +void *qpop(queue *q) +{ + if (qempty(q)) + return NULL; + void *first = car(q->front); + construct *rest = cdr(q->front); + free(q->front); + q->front = rest; + return first; +} + +int main() +{ + queue *q = mkq(); + qpush(q, "Mahathir Mohamad"); + qpush(q, "Elizabeth II"); + qpush(q, "Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah"); + qpush(q, "Paul Biya"); + qpush(q, "Michel Aoun"); + qpush(q, "Mahmoud Abbas"); + qpush(q, "Francis"); + + while (!qempty(q)) + puts(qpop(q)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/3/Ex3.c b/usth/ICT2.1/labwork/3/Ex3.c new file mode 100644 index 0000000..b934ec0 --- /dev/null +++ b/usth/ICT2.1/labwork/3/Ex3.c @@ -0,0 +1,46 @@ +/* + * Interactive guessing game. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include +#include + +#include "stack.h" + +char *random10(char *c) +{ + char *p = malloc(sizeof(char)); + *p = rand() % 10; + while (c != NULL && *p == *c) { + free(p); + p = malloc(sizeof(char)); + *p = rand() % 10; + } + return p; +} + +int main() +{ + stack *s = mkstack(); + char guess, lost = 0; + srand(time(NULL)); + stack_push(s, random10(NULL)); +STEP2: + stack_push(s, random10(stack_top(s))); + char *p = stack_pop(s); + puts(lost ? "Make another guess between 0 and 9" + : "Make a guess between 0 and 9"); + scanf("%hhd", &guess); + if ((guess - *p) * (guess - *(char *) stack_top(s)) < 0) { + puts("YOU WIN!"); + return 0; + } else if (lost) { + puts("YOU LOSE!"); + return 0; + } + + lost = 1; + goto STEP2; +} diff --git a/usth/ICT2.1/labwork/3/README.md b/usth/ICT2.1/labwork/3/README.md new file mode 100644 index 0000000..a38ee6e --- /dev/null +++ b/usth/ICT2.1/labwork/3/README.md @@ -0,0 +1,42 @@ +# Algorithms and Data Structures: Tutorial 3 + +This package contains the following files: + +* `construct.h`, `construct.c`: Lisp construct (with `cons`, `car` and `cdr`) +* `stack.h`, `stack.c`: initialization, check for empty, push, top and pop +* `Ex1.c`: read from stdin and reverse the name +* `Ex2.c`: add hard-coded names to a queue a print them to stdout +* `Ex3.c`: interactive guessing game + +Compilation can be done as follows + + cc construct.c stack.c Ex1.c -o Ex1 + cc construct.c Ex2.c -o Ex2 + cc construct.c stack.c Ex3.c -o Ex3 + +All source files are as licensed under the Unlicense which states + +> This is free and unencumbered software released into the public domain. +> +> Anyone is free to copy, modify, publish, use, compile, sell, or +> distribute this software, either in source code form or as a compiled +> binary, for any purpose, commercial or non-commercial, and by any +> means. +> +> In jurisdictions that recognize copyright laws, the author or authors +> of this software dedicate any and all copyright interest in the +> software to the public domain. We make this dedication for the benefit +> of the public at large and to the detriment of our heirs and +> successors. We intend this dedication to be an overt act of +> relinquishment in perpetuity of all present and future rights to this +> software under copyright law. +> +> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +> EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +> MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +> IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +> OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +> ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +> OTHER DEALINGS IN THE SOFTWARE. +> +> For more information, please refer to diff --git a/usth/ICT2.1/labwork/3/TT3.pdf b/usth/ICT2.1/labwork/3/TT3.pdf new file mode 100644 index 0000000..708d20a Binary files /dev/null and b/usth/ICT2.1/labwork/3/TT3.pdf differ diff --git a/usth/ICT2.1/labwork/3/construct.c b/usth/ICT2.1/labwork/3/construct.c new file mode 100644 index 0000000..887b6d8 --- /dev/null +++ b/usth/ICT2.1/labwork/3/construct.c @@ -0,0 +1,26 @@ +/* + * Lisp construct implementation. + * This is free and unencumbered software released into the public domain. + */ + +#include + +#include "construct.h" + +construct *cons(void *first, construct *rest) +{ + construct *list = malloc(sizeof(construct)); + list->car = first; + list->cdr = rest; + return list; +} + +void *car(construct *list) +{ + return list->car; +} + +construct *cdr(construct *list) +{ + return list->cdr; +} diff --git a/usth/ICT2.1/labwork/3/construct.h b/usth/ICT2.1/labwork/3/construct.h new file mode 100644 index 0000000..35d2448 --- /dev/null +++ b/usth/ICT2.1/labwork/3/construct.h @@ -0,0 +1,14 @@ +/* + * Lisp construct header. + * This is free and unencumbered software released into the public domain. + */ + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +construct *cons(void *, construct *); +void *car(construct *); +construct *cdr(construct *); diff --git a/usth/ICT2.1/labwork/3/stack.c b/usth/ICT2.1/labwork/3/stack.c new file mode 100644 index 0000000..708fb59 --- /dev/null +++ b/usth/ICT2.1/labwork/3/stack.c @@ -0,0 +1,39 @@ +/* + * Stack implemented using linked list. + * This is free and unencumbered software released into the public domain. + */ + +#include + +#include "stack.h" + +stack *mkstack() +{ + stack *s = malloc(sizeof(stack)); + s->stack = NULL; + return s; +} + +int stack_empty(stack *s) +{ + return s->stack == NULL; +} + +void stack_push(stack *s, void *item) +{ + s->stack = cons(item, s->stack); +} + +void *stack_top(stack *s) +{ + return car(s->stack); +} + +void *stack_pop(stack *s) +{ + void *first = car(s->stack); + construct *rest = cdr(s->stack); + free(s->stack); + s->stack = rest; + return first; +} diff --git a/usth/ICT2.1/labwork/3/stack.h b/usth/ICT2.1/labwork/3/stack.h new file mode 100644 index 0000000..2ed8851 --- /dev/null +++ b/usth/ICT2.1/labwork/3/stack.h @@ -0,0 +1,16 @@ +/* + * Stack header. + * This is free and unencumbered software released into the public domain. + */ + +#include "construct.h" + +typedef struct { + construct *stack; +} stack; + +stack *mkstack(); +int stack_empty(stack *); +void stack_push(stack *, void *); +void *stack_top(stack *); +void *stack_pop(stack *); -- cgit 1.4.1