chap4 for data structure

1 files changed, 103 insertions, 0 deletions

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 <stdio.h>
+#include <stdlib.h>
+
+#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;
+}