category

11 files changed, 542 insertions, 0 deletions

diff --git a/Computer_Science/data_structures/chapter_3/.polynomial_in_list.c.swp b/Computer_Science/data_structures/chapter_3/.polynomial_in_list.c.swp
new file mode 100644
index 0000000..5906611
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/.polynomial_in_list.c.swp
diff --git a/Computer_Science/data_structures/chapter_3/a.out b/Computer_Science/data_structures/chapter_3/a.out
new file mode 100755
index 0000000..185b597
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/a.out
diff --git a/Computer_Science/data_structures/chapter_3/linked_list.c b/Computer_Science/data_structures/chapter_3/linked_list.c
new file mode 100644
index 0000000..920be0d
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/linked_list.c
@@ -0,0 +1,138 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "linked_list.h"
+
+struct node
+{
+    elem data;
+    position next;
+};
+
+int is_empty(list header)
+{
+    return header->next == NULL;
+}
+
+int is_last(position p, list header)
+{
+    return p->next == NULL;
+}
+
+position find(elem x, list header)
+{
+    position p;
+    p = header->next;
+
+    for(; p != NULL; p = p->next) {
+        if(p->data == x) return p;
+    }
+
+    return NULL;
+}
+
+void delete(elem x, list header)
+{
+    position tmp;
+    position pre;
+
+    pre = find_previous(x, header);
+
+    if(!is_last(pre, header)) {
+        tmp = pre->next;
+        pre->next = pre->next->next;
+        free(tmp);
+    }
+
+}
+
+position find_previous(elem x, list header)
+{
+    position p;
+
+    p = header;
+    while(p->next != NULL && p->next->data != x)
+        p = p->next;
+
+    return p;
+}
+
+void insert(elem x, list header, position p)
+{
+    position tmp;
+    
+    tmp = malloc(sizeof(struct node));
+    
+    if(tmp == NULL)
+       printf("Out of space!\n"); 
+
+    tmp->data = x;
+    tmp->next = p->next;
+    p->next = tmp;
+}
+
+void delete_list(list header)
+{
+    position p, tmp;
+
+    p = header->next;
+    header->next = NULL;
+
+    while(p != NULL) {
+        tmp = p;
+        p = p->next;
+        free(tmp);
+    }
+}
+
+void print_list(list header)
+{
+    position p;
+
+    if(is_empty(header))
+       printf("empty list! \n");
+
+    p = header->next;
+    for(; p != NULL; p = p->next) 
+        printf("%d->", p->data);
+    printf("\n");
+}
+
+int test()
+{
+    position p1, p2, p3;
+    list l1, l2, l3, l4;
+    l1 = malloc(sizeof(struct node));
+    l1->next == NULL;
+
+    print_list(l1);
+
+    /* test insert foo */
+    insert(5, l1, l1);
+    insert(4, l1, l1);
+    insert(3, l1, l1);
+    insert(2, l1, l1);
+    insert(1, l1, l1);
+    print_list(l1);
+
+
+    /* test find foo */
+    p1 = find(2, l1);
+    printf("%d\n", p1->next->data);
+
+    /* test delete foo */
+    delete(3, l1);
+    delete(5, l1);
+    delete(1, l1);
+    print_list(l1);
+
+    /* test delete_list foo */
+    delete_list(l1);
+    print_list(l1);
+}
+
+int main()
+{
+    test();
+    return 0;
+}
diff --git a/Computer_Science/data_structures/chapter_3/linked_list.h b/Computer_Science/data_structures/chapter_3/linked_list.h
new file mode 100644
index 0000000..ecd9040
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/linked_list.h
@@ -0,0 +1,23 @@
+#ifndef _LIST_H
+
+struct node;
+typedef struct node *node_ptr;
+typedef node_ptr list;
+typedef node_ptr position;
+
+/* elem to int */
+typedef int elem;
+
+list make_empty(list header);
+int is_empty(list header);
+int is_last(position p, list header);
+position find(elem x, list header);
+void delete(elem x, list header);
+position find_previous(elem x, list header);
+void insert(elem x, list header, position p);
+void delete_list(list header);
+position header(list header);
+position first(list header);
+position advance(position p);
+
+#endif    /* _LIST_H */
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/polynomial_in_list.c b/Computer_Science/data_structures/chapter_3/polynomial_in_list.c
new file mode 100644
index 0000000..0ecdf33
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/polynomial_in_list.c
@@ -0,0 +1,36 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct node* ptr_to_node;
+
+struct node
+{
+    int coefficient;
+    int exponent;
+    ptr_to_node next;
+};
+
+
+typedef ptr_to_node polynomial;
+
+void add_polynomial(polynomial poly1, polynomial poly2,
+        polynomial poly_sum)
+{
+}
+
+void mult_polynomial(polynomial poly1, polynomial poly2,
+        polynomial poly_prod)
+{
+}
+
+void print_poly(polynomial poly)
+{
+    polynomial p;
+
+    p = poly->next;
+
+    for(; p != NULL; p = p->next)
+        printf("%dx^%d + ", p->coefficient, p->exponent);
+    
+    printf("\n");
+}
diff --git a/Computer_Science/data_structures/chapter_3/stack.c b/Computer_Science/data_structures/chapter_3/stack.c
new file mode 100644
index 0000000..a27869f
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/stack.c
@@ -0,0 +1,120 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "stack.h"
+
+/* Stack implementation is a linked list with a header */
+struct node
+{
+    elem data;
+    ptr_to_node next;
+};
+
+int is_empty(stack s)
+{
+    return s->next == NULL;
+}
+
+stack create_stack()
+{
+    stack s;
+
+    s = malloc(sizeof(struct node));
+    if(s == NULL)
+        printf("error");
+    make_empty(s);
+    return s;
+}
+
+void make_empty(stack s)
+{
+    if(s == NULL)
+        printf("must create a stack first");
+    else
+        while(!is_empty(s))
+            pop(s);
+}
+
+void push(elem x, stack s)
+{
+    ptr_to_node tmp;
+
+    tmp = malloc(sizeof(struct node));
+    if(tmp == NULL)
+        printf("out of space");
+    else {
+        tmp->data = x;
+        tmp->next = s->next;
+        s->next = tmp;
+    }
+}
+
+void pop(stack s)
+{
+    if(!is_empty(s)) {
+        ptr_to_node tmp = s->next;
+        s->next = s->next->next;
+        free(tmp);
+    } else
+        printf("Empty stack");
+}
+
+elem top(stack s)
+{
+//    if(is_empty(s))
+//        printf("empty stack");
+//    else
+//        return s->next->data;
+//
+//   return -1;
+//
+/* tune version */
+    if(!is_empty(s))
+        return s->next->data;
+
+    printf("empty stack");
+    return 0;
+}
+
+void print_stack(stack s)
+{
+    printf("--------\n");
+    while(!is_empty(s)) {
+        printf("   %d\n", s->next->data);
+        s = s->next;
+    }
+    printf("--------\n");
+}
+
+void test()
+{
+    stack s;
+    s = create_stack();
+    push(1, s);
+    push(2, s);
+    print_stack(s);
+
+    push(3, s);
+    push(4, s);
+    push(5, s);
+    print_stack(s);
+    printf("%d\n",top(s));
+
+    pop(s);
+    print_stack(s);
+
+    pop(s);
+    pop(s);
+    pop(s);
+    pop(s);
+    pop(s);
+    pop(s);
+
+    print_stack(s);
+}
+
+int main()
+{
+    test();
+    return 0;
+}
diff --git a/Computer_Science/data_structures/chapter_3/stack.h b/Computer_Science/data_structures/chapter_3/stack.h
new file mode 100644
index 0000000..f93c467
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/stack.h
@@ -0,0 +1,16 @@
+#ifndef _STACK_H
+
+struct node;
+typedef struct node *ptr_to_node;
+typedef ptr_to_node stack;
+typedef int elem;
+
+int is_empty(stack s);
+stack create_stack();
+void dispose_stack(stack s);
+void make_empty(stack s);
+void push(elem x, stack s);
+elem top(stack s);
+void pop(stack s);
+
+#endif
diff --git a/Computer_Science/data_structures/chapter_3/stack.h.gch b/Computer_Science/data_structures/chapter_3/stack.h.gch
new file mode 100644
index 0000000..4083944
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/stack.h.gch
diff --git a/Computer_Science/data_structures/chapter_3/stack_array.c b/Computer_Science/data_structures/chapter_3/stack_array.c
new file mode 100644
index 0000000..4c23334
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/stack_array.c
@@ -0,0 +1,90 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "stack_array.h"
+
+#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)
+{
+    stack s;
+
+    if(max_elements < MIN_STACK_SIZE)
+        printf("size too small.\n");
+
+    s = malloc(sizeof(struct stack_record));
+    if(s == NULL)
+        printf("out of space");
+
+    s->array = malloc(sizeof(elem) * max_elements);
+
+    if(s->array == NULL)
+        printf("out of space");
+
+    s->capacity = max_elements;
+    make_empty(s);
+
+    return s;
+}
+
+void dispose_stack(stack s)
+{
+    if(s != NULL) {
+        free(s->array);
+        free(s);
+    }
+}
+
+int is_empty(stack s)
+{
+    return s->top_of_stack == EMPTY_TOS;
+}
+
+void make_empty(stack s)
+{
+    s->top_of_stack = EMPTY_TOS;
+}
+
+void push(elem x, stack s)
+{
+    if(s->top_of_stack >= capacity)
+        printf("full stack");
+    else 
+        s->array[++s->top_of_stack] = x;
+    
+}
+
+elem top(stack s)
+{
+    if(!is_empty(s))
+        return s->array[s->top_of_stack];
+
+    printf("empty stack");
+    return 0;
+}
+
+void pop(stack s)
+{
+    if(!is_empty(s))
+        s->top_of_stack--;
+
+    printf("empty stack");
+}
+
+elem top_and_pop(stack s)
+{
+    if(!is_empty(s))
+        /* take care of this, before return, s->top_of_stack is already dec. */
+        return s->array[s->top_of_stack--];
+
+    printf("empty stack");
+    return 0;
+}
diff --git a/Computer_Science/data_structures/chapter_3/stack_array.h b/Computer_Science/data_structures/chapter_3/stack_array.h
new file mode 100644
index 0000000..088b0cc
--- /dev/null
+++ b/Computer_Science/data_structures/chapter_3/stack_array.h
@@ -0,0 +1,16 @@
+#ifndef _STACK_H
+
+struct stack_record;
+typedef struct stack_record *stack;
+typedef int elem;
+
+int is_empty(stack s);
+int is_full(stack s);
+stack create_stack(int max_elements);
+void dispose_stack(stack s);
+void push(elem x, stack s);
+elem top(stack s);
+void pop(stack s);
+elem top_and_pop(stack s);
+
+#endif