chap4 for data structure

5 files changed, 121 insertions, 6 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;
+}
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
--- a/Computer_Science/data_structures/chapter_3/stack.h.gch
+++ /dev/null
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
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/stack_array
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);