12 files changed, 581 insertions, 8 deletions

diff --git a/Computer_Science/SICP/ex2_17.scm b/Computer_Science/SICP/ex2_17.scm
index 37e3eb3..f559457 100644
--- a/Computer_Science/SICP/ex2_17.scm
+++ b/Computer_Science/SICP/ex2_17.scm
@@ -184,5 +184,4 @@ one-through-four
   (list 57 321 88))
 
 (cons (list 1 2) (list 3 4))
-
-
+(cons (list 1 2) (list 3 4))
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);
diff --git a/Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp b/Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp
new file mode 100644
index 0000000..b1514aa
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/.binary_search_tree.c.swp
diff --git a/Computer_Science/data_structures/chapter_4/a.out b/Computer_Science/data_structures/chapter_4/a.out
new file mode 100755
index 0000000..b1815f0
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/a.out
diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.c b/Computer_Science/data_structures/chapter_4/binary_search_tree.c
new file mode 100644
index 0000000..fb61e7b
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.c
@@ -0,0 +1,138 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "binary_search_tree.h"
+#include "print_ascii_tree.h"
+
+struct TreeNode
+{
+    elem_t elem;
+    SearchTree left;
+    SearchTree right;
+};
+
+SearchTree make_empty(SearchTree t)
+{
+    if(t != NULL) {
+        make_empty(t->left);
+        make_empty(t->right);
+        free(t);
+    }
+
+    return NULL;
+}
+
+/**
+ *  find x or return NULL.
+ */
+Position find(elem_t x, SearchTree t)
+{
+    if(t != NULL) {
+        if(t->elem == x) return t;
+        else if(t->elem > x) return find(x, t->right);
+        else return find(x, t->left);
+    }
+
+    return NULL;
+}
+
+Position find_min(SearchTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(t->left == NULL)
+        return t;
+    else
+        return find_min(t->left);
+}
+
+Position find_max(SearchTree t)
+{
+    if(t == NULL)
+        return NULL;
+    else if(t->right == NULL)
+        return t;
+    else
+        return find_max(t->right);
+}
+
+SearchTree insert(elem_t x, SearchTree t)
+{
+    if(t == NULL) {
+        t = malloc(sizeof(struct TreeNode));
+        t->elem = x;
+        t->left = NULL;
+        t->right = NULL;
+    } else if(x > t->elem)
+        t->right = insert(x, t->right);
+    else if(x < t->elem)
+        t->left = insert(x, t->left);
+    /* The t->elem = x need do nothing, already inserted */
+
+    return t;
+}
+
+SearchTree delete(elem_t x, SearchTree t)
+{
+    Position p, tmp;
+
+    p = find(x, t);
+
+    if(p == NULL) {
+        /* elem x not found */
+        printf("x not found!(do nothing)\n");
+    } else if(p->left == NULL && p->right == NULL) {
+        free(p);
+    } else if(p->left == NULL) {
+        tmp = p;
+        p = p->right;
+        free(tmp);
+    } else if(p->right == NULL) {
+        tmp = p;
+        p = p->left;
+        free(tmp);
+    } else {
+        /* replace and delete */
+        tmp = find_min(p->right);
+        p->elem = tmp->elem;
+        t->right = delete(p->elem, t->right);
+    }
+
+    return t;
+}
+
+elem_t retrieve(Position p)
+{
+
+}
+
+void print_tree_pre_order(SearchTree t)
+{
+    if(t == NULL)
+        return;
+    print_tree_pre_order(t->left);
+    printf("%d ", t->elem);
+    print_tree_pre_order(t->right);
+}
+
+void test()
+{
+    SearchTree t = NULL;
+    t = make_empty(t);
+    t = insert(1, t);
+    insert(4, t);
+    insert(3, t);
+    insert(2, t);
+    insert(10, t);
+
+    print_tree_pre_order(t);
+    printf("\n");
+    print_ascii_tree(t);
+}
+
+int main()
+{
+    test();
+    return 0;
+}
diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.h b/Computer_Science/data_structures/chapter_4/binary_search_tree.h
new file mode 100644
index 0000000..da128f8
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.h
@@ -0,0 +1,17 @@
+#ifndef _BINARY_SEARCH_TREE_H
+#define _BINARY_SEARCH_TREE_H
+
+struct TreeNode;
+typedef struct TreeNode *Position;
+typedef struct TreeNode *SearchTree;
+typedef int elem_t;
+
+SearchTree make_empty(SearchTree t);
+Position find(elem_t x, SearchTree t);
+Position find_min(SearchTree t);
+Position find_max(SearchTree t);
+SearchTree insert(elem_t x, SearchTree t);
+SearchTree delete(elem_t x, SearchTree t);
+elem_t retrieve(Position p);
+
+#endif  /* _BINARY_SEARCH_TREE_H */
diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.c b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c
new file mode 100644
index 0000000..f2e9839
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c
@@ -0,0 +1,282 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "binary_search_tree.h"
+#include "print_ascii_tree.h"
+
+struct asciinode_struct
+{
+  asciinode * left, * right;
+
+  //length of the edge from this node to its children
+  int edge_length;
+
+  int height;
+
+  int lablen;
+
+  //-1=I am left, 0=I am root, 1=right
+  int parent_dir;
+
+  //max supported unit32 in dec, 10 digits max
+  char label[11];
+};
+
+int lprofile[MAX_HEIGHT];
+int rprofile[MAX_HEIGHT];
+
+//adjust gap between left and right nodes
+int gap = 3;
+
+//used for printing next node in the same level,
+//this is the x coordinate of the next char printed
+int print_next;
+
+int MIN (int X, int Y)
+{
+  return ((X) < (Y)) ? (X) : (Y);
+}
+
+int MAX (int X, int Y)
+{
+  return ((X) > (Y)) ? (X) : (Y);
+}
+
+asciinode *build_ascii_tree_recursive(Tree t)
+{
+  asciinode *node;
+
+  if (t == NULL) return NULL;
+
+  node = malloc(sizeof(asciinode));
+  node->left = build_ascii_tree_recursive(t->left);
+  node->right = build_ascii_tree_recursive(t->right);
+
+  if (node->left != NULL)
+  {
+    node->left->parent_dir = -1;
+  }
+
+  if (node->right != NULL)
+  {
+    node->right->parent_dir = 1;
+  }
+
+  sprintf(node->label, "%d", t->elem);
+  node->lablen = strlen(node->label);
+
+  return node;
+}
+
+
+//Copy the tree into the ascii node structre
+asciinode *build_ascii_tree(Tree t)
+{
+  asciinode *node;
+  if (t == NULL) return NULL;
+  node = build_ascii_tree_recursive(t);
+  node->parent_dir = 0;
+  return node;
+}
+
+//Free all the nodes of the given tree
+void free_ascii_tree(asciinode *node)
+{
+  if (node == NULL) return;
+  free_ascii_tree(node->left);
+  free_ascii_tree(node->right);
+  free(node);
+}
+
+//The following function fills in the lprofile array for the given tree.
+//It assumes that the center of the label of the root of this tree
+//is located at a position (x,y).  It assumes that the edge_length
+//fields have been computed for this tree.
+void compute_lprofile(asciinode *node, int x, int y)
+{
+  int i, isleft;
+  if (node == NULL) return;
+  isleft = (node->parent_dir == -1);
+  lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
+  if (node->left != NULL)
+  {
+	  for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++)
+    {
+	    lprofile[y+i] = MIN(lprofile[y+i], x-i);
+    }
+  }
+  compute_lprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
+  compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
+}
+
+void compute_rprofile(asciinode *node, int x, int y)
+{
+  int i, notleft;
+  if (node == NULL) return;
+  notleft = (node->parent_dir != -1);
+  rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
+  if (node->right != NULL)
+  {
+	  for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++)
+    {
+	    rprofile[y+i] = MAX(rprofile[y+i], x+i);
+    }
+  }
+  compute_rprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
+  compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
+}
+
+//This function fills in the edge_length and
+//height fields of the specified tree
+void compute_edge_lengths(asciinode *node)
+{
+  int h, hmin, i, delta;
+  if (node == NULL) return;
+  compute_edge_lengths(node->left);
+  compute_edge_lengths(node->right);
+
+  /* first fill in the edge_length of node */
+  if (node->right == NULL && node->left == NULL)
+  {
+	  node->edge_length = 0;
+  }
+  else
+  {
+    if (node->left != NULL)
+    {
+	    for (i=0; i<node->left->height && i < MAX_HEIGHT; i++)
+      {
+		    rprofile[i] = -INFINITY;
+	    }
+	    compute_rprofile(node->left, 0, 0);
+	    hmin = node->left->height;
+    }
+    else
+    {
+	    hmin = 0;
+    }
+	  if (node->right != NULL)
+    {
+	    for (i=0; i<node->right->height && i < MAX_HEIGHT; i++)
+      {
+		    lprofile[i] = INFINITY;
+	    }
+	    compute_lprofile(node->right, 0, 0);
+	    hmin = MIN(node->right->height, hmin);
+    }
+    else
+    {
+	    hmin = 0;
+    }
+	  delta = 4;
+	  for (i=0; i<hmin; i++)
+    {
+	    delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
+    }
+
+    //If the node has two children of height 1, then we allow the
+    //two leaves to be within 1, instead of 2
+	  if (((node->left != NULL && node->left->height == 1) ||
+	      (node->right != NULL && node->right->height == 1))&&delta>4)
+    {
+      delta--;
+    }
+
+    node->edge_length = ((delta+1)/2) - 1;
+  }
+
+  //now fill in the height of node
+  h = 1;
+  if (node->left != NULL)
+  {
+	  h = MAX(node->left->height + node->edge_length + 1, h);
+  }
+  if (node->right != NULL)
+  {
+	  h = MAX(node->right->height + node->edge_length + 1, h);
+  }
+  node->height = h;
+}
+
+//This function prints the given level of the given tree, assuming
+//that the node has the given x cordinate.
+void print_level(asciinode *node, int x, int level)
+{
+  int i, isleft;
+  if (node == NULL) return;
+  isleft = (node->parent_dir == -1);
+  if (level == 0)
+  {
+	  for (i=0; i<(x-print_next-((node->lablen-isleft)/2)); i++)
+    {
+	    printf(" ");
+    }
+	  print_next += i;
+	  printf("%s", node->label);
+	  print_next += node->lablen;
+  }
+  else if (node->edge_length >= level)
+  {
+	  if (node->left != NULL)
+    {
+	    for (i=0; i<(x-print_next-(level)); i++)
+      {
+		    printf(" ");
+	    }
+	    print_next += i;
+	    printf("/");
+	    print_next++;
+    }
+	  if (node->right != NULL)
+    {
+	    for (i=0; i<(x-print_next+(level)); i++)
+      {
+		    printf(" ");
+	    }
+	    print_next += i;
+	    printf("\\");
+	    print_next++;
+    }
+  }
+  else
+  {
+	  print_level(node->left,
+                x-node->edge_length-1,
+                level-node->edge_length-1);
+	  print_level(node->right,
+                x+node->edge_length+1,
+                level-node->edge_length-1);
+  }
+}
+
+//prints ascii tree for given Tree structure
+void print_ascii_tree(Tree t)
+{
+  asciinode *proot;
+  int xmin, i;
+  if (t == NULL) return;
+  proot = build_ascii_tree(t);
+  compute_edge_lengths(proot);
+  for (i=0; i<proot->height && i < MAX_HEIGHT; i++)
+  {
+	  lprofile[i] = INFINITY;
+  }
+  compute_lprofile(proot, 0, 0);
+  xmin = 0;
+  for (i = 0; i < proot->height && i < MAX_HEIGHT; i++)
+  {
+	  xmin = MIN(xmin, lprofile[i]);
+  }
+  for (i = 0; i < proot->height; i++)
+  {
+	  print_next = 0;
+	  print_level(proot, -xmin, i);
+	  printf("\n");
+  }
+  if (proot->height >= MAX_HEIGHT)
+  {
+	  printf("(This tree is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT);
+  }
+  free_ascii_tree(proot);
+}
diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.h b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h
new file mode 100644
index 0000000..12eed6a
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h
@@ -0,0 +1,22 @@
+#ifndef _PRINT_ASCII_TREE_H
+#define _PRINT_ASCII_TREE_H
+
+struct asciinode_struct;
+typedef struct asciinode_struct asciinode;
+typedef SearchTree Tree;
+
+#define MAX_HEIGHT 1000
+#define INFINITY (1 << 20)
+
+int MIN (int X, int Y);
+int MAX (int X, int Y);
+asciinode *build_ascii_tree_recursive(Tree t);
+asciinode *build_ascii_tree(Tree t);
+void free_ascii_tree(asciinode *node);
+void compute_lprofile(asciinode *node, int x, int y);
+void compute_rprofile(asciinode *node, int x, int y);
+void compute_edge_lengths(asciinode *node);
+void print_level(asciinode *node, int x, int level);
+void print_ascii_tree(Tree t);
+
+#endif