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/2/Ex1.c | 100 ++++++++++++++++++++++++++++++++++++ usth/ICT2.1/labwork/2/Ex2.c | 104 ++++++++++++++++++++++++++++++++++++++ usth/ICT2.1/labwork/2/README.md | 49 ++++++++++++++++++ usth/ICT2.1/labwork/2/TT2.pdf | Bin 0 -> 384633 bytes usth/ICT2.1/labwork/2/construct.c | 57 +++++++++++++++++++++ usth/ICT2.1/labwork/2/construct.h | 17 +++++++ 6 files changed, 327 insertions(+) create mode 100644 usth/ICT2.1/labwork/2/Ex1.c create mode 100644 usth/ICT2.1/labwork/2/Ex2.c create mode 100644 usth/ICT2.1/labwork/2/README.md create mode 100644 usth/ICT2.1/labwork/2/TT2.pdf create mode 100644 usth/ICT2.1/labwork/2/construct.c create mode 100644 usth/ICT2.1/labwork/2/construct.h (limited to 'usth/ICT2.1/labwork/2') diff --git a/usth/ICT2.1/labwork/2/Ex1.c b/usth/ICT2.1/labwork/2/Ex1.c new file mode 100644 index 0000000..b4d5836 --- /dev/null +++ b/usth/ICT2.1/labwork/2/Ex1.c @@ -0,0 +1,100 @@ +/* + * Train represented using linked list by lisp-like constructs. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include +#include + +#include "construct.h" + +#define N 7 +#define LEN_MAX 42 +#define PSNGR_MAX 5 /* this raises the chance of empty vehicle */ + +struct vehicle { + int passengers; + char *name; +}; + +void free_vehicle(struct vehicle *v) +{ + free(v->name); + free(v); +} + +struct vehicle *mkvehicle(int passengers, char *name) +{ + struct vehicle *v = malloc(sizeof(struct vehicle)); + v->passengers = passengers; + v->name = name; + return v; +} + +struct vehicle *rand_vehicle() +{ + int len = rand() % LEN_MAX + 2; /* avoid empty name */ + char *name = malloc(len--); + for (int j = 0; j < len; ++j) + name[j] = 'a' + rand() % 26; + name[len] = 0; + return mkvehicle(rand() % PSNGR_MAX, name); +} + +void print_vehicle(struct vehicle *v) +{ + printf("%s (%d passengers)\n", v->name, v->passengers); +} + +void print_train(construct *train) +{ + if (train == NULL) + return; + print_vehicle(car(train)); + print_train(cdr(train)); +} + +/* Remove empty vehicles */ +construct *optimize_train(construct *train) +{ + if (train == NULL) + return NULL; + struct vehicle *first = car(train); + construct *rest = cdr(train); + free(train); + + if (first->passengers) + return cons(first, optimize_train(rest)); + free_vehicle(first); + return optimize_train(rest); +} + +int main() +{ + construct *train = NULL; + + srand(time(NULL)); + for (int i = 0; i < N; ++i) + train = cons(rand_vehicle(), train); + puts("Initial train:"); + print_train(train); + putchar(10); + + train = optimize_train(train); + puts("Optimized train:"); + print_train(train); + putchar(10); + + int index = rand() % length(train); + struct vehicle *v = rand_vehicle(); + while (!v->passengers) { + free(v); + v = rand_vehicle(); + } + train = insert(v, train, index); + printf("Train after inserting a new one at index %d:\n", index); + print_train(train); + + return 0; +} diff --git a/usth/ICT2.1/labwork/2/Ex2.c b/usth/ICT2.1/labwork/2/Ex2.c new file mode 100644 index 0000000..8f32134 --- /dev/null +++ b/usth/ICT2.1/labwork/2/Ex2.c @@ -0,0 +1,104 @@ +/* + * Polynomial represented using linked list, with free coefficient at last. + * This is free and unencumbered software released into the public domain. + */ + +#include +#include +#include +#include + +#include "construct.h" + +#define COEFF_MOD 42 + +/* + * Add addition to the coefficient of power n of poly if it already exists. + * Return the mutated polynomial on success and NULL otherwise. + */ +construct *add_term(construct *poly, double addition, size_t n) +{ + double *term = nth(poly, length(poly) - n - 1); + if (term == NULL) + return NULL; + *term += addition; + return poly; +} + +/* Remove the nth term and return the mutated polynomial. */ +construct *remove_term(construct *poly, size_t n) +{ + if (poly == NULL) + return NULL; + size_t len = length(poly); + if (++n == len) { + construct *rest = cdr(poly); + free(car(poly)); + free(poly); + return rest; + } + + double *term = nth(poly, len - n); + if (term == NULL) + return poly; + *term = 0; + return poly; +} + +/* Evaluate the polynomial poly of the length len at the specified value. */ +double polyval(construct *poly, double value, size_t len) +{ + if (!len--) + return 0; + double coeff = *(double *) car(poly); + return pow(value, len) * coeff + polyval(cdr(poly), value, len); +} + +/* Print the polynomial poly of the length len using the specified varname. */ +void polyprint(construct *poly, char *varname, size_t len) +{ + if (len--) { + printf(len ? "%g%s^%zu + " : "%g", + *(double *) car(poly), varname, len); + polyprint(cdr(poly), varname, len); + } else { + putchar(10); + } +} + +int main() +{ + construct *polynomial = NULL; + srand(time(NULL)); + int len = rand() % 4 + 3; + + for (int i = 0; i < len; ++i) { + double *coeff = malloc(sizeof(double)); + *coeff = rand() % COEFF_MOD; + polynomial = cons(coeff, polynomial); + } + + puts("Initial polynomial:"); + polyprint(polynomial, "x", len); + + double x = rand() % COEFF_MOD; + int n = rand() % len; + polynomial = add_term(polynomial, x, n); + printf("The polynomial after adding %g to the number %d term:\n", x, n); + polyprint(polynomial, "x", len); + + polynomial = remove_term(polynomial, --len); + printf("The polynomial after removing the number %d term:\n", len); + polyprint(polynomial, "x", len); + + n = rand() % (len - 1); + polynomial = remove_term(polynomial, n); + printf("The polynomial after removing the number %d term:\n", n); + polyprint(polynomial, "x", len); + + puts("Evaluation of the polynomial using x from stdin:"); + scanf("%lf", &x); + printf("%g\n", polyval(polynomial, x, len)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/2/README.md b/usth/ICT2.1/labwork/2/README.md new file mode 100644 index 0000000..25b43c4 --- /dev/null +++ b/usth/ICT2.1/labwork/2/README.md @@ -0,0 +1,49 @@ +# Algorithms and Data Structures: Tutorial 2 + +This package contains the following files: + +* construct.h +* construct.c +* Ex1.c +* Ex2.c + +Where construct is an minimal implementation of Lisp construct with +`cons`, `car`, `cdr`, `length`, `nth` and `insert`. It eases and simplifies +the implementation of linked lists (and trees and and graphs if we study them +later on). 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 + +The solution of the second exercise uses the math library and thus +it needs to by linked during compilation. Both uses the `construct` library: + + cc construct.c Ex1.c -o Ex1 + cc construct.c Ex2.c -lm -o Ex2 + +Additionally, `Ex2` requires a value of `x` to be entered from stdin: + + ./Ex1 + echo 7 | ./Ex2 diff --git a/usth/ICT2.1/labwork/2/TT2.pdf b/usth/ICT2.1/labwork/2/TT2.pdf new file mode 100644 index 0000000..c373df5 Binary files /dev/null and b/usth/ICT2.1/labwork/2/TT2.pdf differ diff --git a/usth/ICT2.1/labwork/2/construct.c b/usth/ICT2.1/labwork/2/construct.c new file mode 100644 index 0000000..db32d8a --- /dev/null +++ b/usth/ICT2.1/labwork/2/construct.c @@ -0,0 +1,57 @@ +/* + * 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; +} + +size_t length(construct *list) +{ + if (list == NULL) + return 0; + return length(cdr(list)) + 1; +} + +void *nth(construct *list, size_t n) +{ + if (list == NULL) + return NULL; + return n ? nth(cdr(list), n - 1) : car(list); +} + +/* + * Try to insert x before item of index i and return the new construct. + * Return NULL on invalid index. + */ +construct *insert(void *x, construct *list, size_t i) +{ + if (!i) + return cons(x, list); + if (list == NULL) + return NULL; + + void *first = car(list); + construct *rest = cdr(list); + free(list); + return cons(first, insert(x, rest, i - 1)); +} diff --git a/usth/ICT2.1/labwork/2/construct.h b/usth/ICT2.1/labwork/2/construct.h new file mode 100644 index 0000000..2d1c840 --- /dev/null +++ b/usth/ICT2.1/labwork/2/construct.h @@ -0,0 +1,17 @@ +/* + * 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 *); +size_t length(construct *); +void *nth(construct *, size_t); +construct *insert(void *, construct *, size_t); -- cgit 1.4.1