From b70153e861af2b1c51d07926b7829ba0a3264a6b Mon Sep 17 00:00:00 2001 From: Steve Lee Date: Sun, 10 Dec 2017 09:07:59 +0800 Subject: chap4 for data structure --- .../data_structures/chapter_3/#polynomial.c# | 103 +++++++++++++++++++++ .../data_structures/chapter_3/stack.h.gch | Bin 1569200 -> 0 bytes .../data_structures/chapter_3/stack_array | Bin 0 -> 8768 bytes .../data_structures/chapter_3/stack_array.c | 23 +++-- .../data_structures/chapter_3/stack_array.h | 1 + 5 files changed, 121 insertions(+), 6 deletions(-) create mode 100644 Computer_Science/data_structures/chapter_3/#polynomial.c# delete mode 100644 Computer_Science/data_structures/chapter_3/stack.h.gch create mode 100755 Computer_Science/data_structures/chapter_3/stack_array (limited to 'Computer_Science/data_structures/chapter_3') diff --git a/Computer_Science/data_structures/chapter_3/#polynomial.c# b/Computer_Science/data_structures/chapter_3/#polynomial.c# new file mode 100644 index 0000000..9028758 --- /dev/null +++ b/Computer_Science/data_structures/chapter_3/#polynomial.c# @@ -0,0 +1,103 @@ +#include +#include + +#define MAX_DEGREE 100 + +typedef struct Polynomial* polynomial; +struct Polynomial +{ + int coeff_array[MAX_DEGREE + 1]; + int high_power; +}; + +int max(int x, int y) +{ + return x > y ? x : y; +} + +void zero_polynomial(polynomial poly) +{ + int i; + + for(i = 0; i <= MAX_DEGREE; i++) + poly->coeff_array[i] = 0; + poly->high_power == 0; +} + +void add_polynomial(const polynomial poly1, const polynomial poly2, + polynomial poly_sum) +{ + int i; + + poly_sum->high_power = max(poly1->high_power, poly2->high_power); + + for(i = 0; i <= poly_sum->high_power; i++) { + poly_sum->coeff_array[i] = poly1->coeff_array[i] + + poly2->coeff_array[i]; + } +} + +void mult_polynomial(const polynomial poly1, const polynomial poly2, + polynomial poly_prod) +{ + int i, j; + + poly_prod->high_power = poly1->high_power + poly2->high_power; + + for(i = 0; i <= poly1->high_power; i++) { + for(j = 0; j<= poly2->high_power; j++) + /* += used here */ + poly_prod->coeff_array[i + j] += poly1->coeff_array[i] + * poly2->coeff_array[j]; + } +} + +void print_poly(const polynomial poly) +{ + int i; + + for(i = 0; i <= poly->high_power; i++) + if(poly->coeff_array[i] != 0) + printf("%dx^%d + ", poly->coeff_array[i], i); + + printf("\n"); +} + +void test() +{ + int i; + + polynomial poly1, poly2, poly_sum, poly_prod; + poly1 = malloc(sizeof(struct Polynomial)); + poly2 = malloc(sizeof(struct Polynomial)); + poly_sum = malloc(sizeof(struct Polynomial)); + poly_prod = malloc(sizeof(struct Polynomial)); + + for(i = 0; i <= 20; i++) { + if(i % 2 == 0) { + poly1->coeff_array[i] = i; + poly1->high_power = i; + } else { + poly2->coeff_array[i] = i; + poly2->high_power = i; + } + } + + print_poly(poly1); + print_poly(poly2); + + /* test sum */ + add_polynomial(poly1, poly2, poly_sum); + print_poly(poly_sum); + + /* test mult foo */ + mult_polynomial(poly1, poly2, poly_prod); + print_poly(poly_prod); +} + +int main() +{ + test(); + + return 0; +} diff --git a/Computer_Science/data_structures/chapter_3/stack.h.gch b/Computer_Science/data_structures/chapter_3/stack.h.gch deleted file mode 100644 index 4083944..0000000 Binary files a/Computer_Science/data_structures/chapter_3/stack.h.gch and /dev/null differ diff --git a/Computer_Science/data_structures/chapter_3/stack_array b/Computer_Science/data_structures/chapter_3/stack_array new file mode 100755 index 0000000..a453ea7 Binary files /dev/null and b/Computer_Science/data_structures/chapter_3/stack_array differ diff --git a/Computer_Science/data_structures/chapter_3/stack_array.c b/Computer_Science/data_structures/chapter_3/stack_array.c index 4c23334..57a7fad 100644 --- a/Computer_Science/data_structures/chapter_3/stack_array.c +++ b/Computer_Science/data_structures/chapter_3/stack_array.c @@ -3,15 +3,15 @@ #include "stack_array.h" -#define EMPTY_TOS (-1); -#define MIN_STACK_SIZE (5); +#define EMPTY_TOS (-1) +#define MIN_STACK_SIZE (5) struct stack_record { int capacity; int top_of_stack; elem *array; -} +}; stack create_stack(int max_elements) { @@ -55,11 +55,11 @@ void make_empty(stack s) void push(elem x, stack s) { - if(s->top_of_stack >= capacity) + if(s->top_of_stack >= s->capacity) printf("full stack"); - else + else s->array[++s->top_of_stack] = x; - + } elem top(stack s) @@ -88,3 +88,14 @@ elem top_and_pop(stack s) printf("empty stack"); return 0; } + +int main() +{ + stack s = create_stack(100); + push(1, s); + push(2, s); + push(3, s); + printf("%d\n", top_and_pop(s)); + printf("%d\n", top_and_pop(s)); + return 0; +} diff --git a/Computer_Science/data_structures/chapter_3/stack_array.h b/Computer_Science/data_structures/chapter_3/stack_array.h index 088b0cc..d296a49 100644 --- a/Computer_Science/data_structures/chapter_3/stack_array.h +++ b/Computer_Science/data_structures/chapter_3/stack_array.h @@ -4,6 +4,7 @@ struct stack_record; typedef struct stack_record *stack; typedef int elem; +void make_empty(stack s); int is_empty(stack s); int is_full(stack s); stack create_stack(int max_elements); -- cgit v1.2.3