aboutsummaryrefslogtreecommitdiff
path: root/data_structures/chapter_3
diff options
context:
space:
mode:
Diffstat (limited to 'data_structures/chapter_3')
-rw-r--r--data_structures/chapter_3/.polynomial_in_list.c.swpbin12288 -> 0 bytes
-rwxr-xr-xdata_structures/chapter_3/a.outbin8480 -> 0 bytes
-rw-r--r--data_structures/chapter_3/linked_list.c138
-rw-r--r--data_structures/chapter_3/linked_list.h23
-rw-r--r--data_structures/chapter_3/polynomial.c103
-rw-r--r--data_structures/chapter_3/polynomial_in_list.c36
-rw-r--r--data_structures/chapter_3/stack.c120
-rw-r--r--data_structures/chapter_3/stack.h16
-rw-r--r--data_structures/chapter_3/stack.h.gchbin1569200 -> 0 bytes
-rw-r--r--data_structures/chapter_3/stack_array.c90
-rw-r--r--data_structures/chapter_3/stack_array.h16
11 files changed, 0 insertions, 542 deletions
diff --git a/data_structures/chapter_3/.polynomial_in_list.c.swp b/data_structures/chapter_3/.polynomial_in_list.c.swp
deleted file mode 100644
index 5906611..0000000
--- a/data_structures/chapter_3/.polynomial_in_list.c.swp
+++ /dev/null
Binary files differ
diff --git a/data_structures/chapter_3/a.out b/data_structures/chapter_3/a.out
deleted file mode 100755
index 185b597..0000000
--- a/data_structures/chapter_3/a.out
+++ /dev/null
Binary files differ
diff --git a/data_structures/chapter_3/linked_list.c b/data_structures/chapter_3/linked_list.c
deleted file mode 100644
index 920be0d..0000000
--- a/data_structures/chapter_3/linked_list.c
+++ /dev/null
@@ -1,138 +0,0 @@
-#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/data_structures/chapter_3/linked_list.h b/data_structures/chapter_3/linked_list.h
deleted file mode 100644
index ecd9040..0000000
--- a/data_structures/chapter_3/linked_list.h
+++ /dev/null
@@ -1,23 +0,0 @@
-#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/data_structures/chapter_3/polynomial.c b/data_structures/chapter_3/polynomial.c
deleted file mode 100644
index 9028758..0000000
--- a/data_structures/chapter_3/polynomial.c
+++ /dev/null
@@ -1,103 +0,0 @@
-#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/data_structures/chapter_3/polynomial_in_list.c b/data_structures/chapter_3/polynomial_in_list.c
deleted file mode 100644
index 0ecdf33..0000000
--- a/data_structures/chapter_3/polynomial_in_list.c
+++ /dev/null
@@ -1,36 +0,0 @@
-#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/data_structures/chapter_3/stack.c b/data_structures/chapter_3/stack.c
deleted file mode 100644
index a27869f..0000000
--- a/data_structures/chapter_3/stack.c
+++ /dev/null
@@ -1,120 +0,0 @@
-#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/data_structures/chapter_3/stack.h b/data_structures/chapter_3/stack.h
deleted file mode 100644
index f93c467..0000000
--- a/data_structures/chapter_3/stack.h
+++ /dev/null
@@ -1,16 +0,0 @@
-#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/data_structures/chapter_3/stack.h.gch b/data_structures/chapter_3/stack.h.gch
deleted file mode 100644
index 4083944..0000000
--- a/data_structures/chapter_3/stack.h.gch
+++ /dev/null
Binary files differ
diff --git a/data_structures/chapter_3/stack_array.c b/data_structures/chapter_3/stack_array.c
deleted file mode 100644
index 4c23334..0000000
--- a/data_structures/chapter_3/stack_array.c
+++ /dev/null
@@ -1,90 +0,0 @@
-#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/data_structures/chapter_3/stack_array.h b/data_structures/chapter_3/stack_array.h
deleted file mode 100644
index 088b0cc..0000000
--- a/data_structures/chapter_3/stack_array.h
+++ /dev/null
@@ -1,16 +0,0 @@
-#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
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-21 05:31:24 +0000