From 9891f38ddcca971fa21ab61e7a70832c8c877b0a Mon Sep 17 00:00:00 2001 From: Michael Hunteman Date: Sat, 23 Sep 2023 12:53:46 -0500 Subject: Initial commit --- .editorconfig | 15 +++++ .gitignore | 2 + complexity.md | 14 +++++ doublylinkedlist.c | 161 +++++++++++++++++++++++++++++++++++++++++++++++++ maze/data_structures.h | 16 +++++ maze/point.c | 29 +++++++++ maze/solver.c | 88 +++++++++++++++++++++++++++ min_heap.c | 113 ++++++++++++++++++++++++++++++++++ queue.c | 68 +++++++++++++++++++++ recursion.md | 8 +++ search.c | 61 +++++++++++++++++++ sort.c | 60 ++++++++++++++++++ stack.c | 63 +++++++++++++++++++ tree/data_structures.h | 14 +++++ tree/node.c | 29 +++++++++ tree/tree.c | 54 +++++++++++++++++ 16 files changed, 795 insertions(+) create mode 100644 .editorconfig create mode 100644 .gitignore create mode 100644 complexity.md create mode 100644 doublylinkedlist.c create mode 100644 maze/data_structures.h create mode 100644 maze/point.c create mode 100644 maze/solver.c create mode 100644 min_heap.c create mode 100644 queue.c create mode 100644 recursion.md create mode 100644 search.c create mode 100644 sort.c create mode 100644 stack.c create mode 100644 tree/data_structures.h create mode 100644 tree/node.c create mode 100644 tree/tree.c diff --git a/.editorconfig b/.editorconfig new file mode 100644 index 0000000..e2f0bbd --- /dev/null +++ b/.editorconfig @@ -0,0 +1,15 @@ +root = true + +[*.{c,h}] +end_of_line = lf +insert_final_newline = true +charset = utf-8 +trim_trailing_whitespace = true +indent_style = tab +indent_size = 8 +max_line_length = 80 + +[*.md] +indent_style = space +indent_size = 4 +trim_trailing_whitespace = false diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..f17e314 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +a.out +*.gch diff --git a/complexity.md b/complexity.md new file mode 100644 index 0000000..9327bb4 --- /dev/null +++ b/complexity.md @@ -0,0 +1,14 @@ +# Time Complexity + +## Big O + +Big O is a way to categorize an algorithm's time or memory requirements based on +input. It is not meant to be an exact measurement. It will not tell you how many +CPU cycles it takes, instead it is meant to generalize the growth of the +algorithm as the input grows. + +- Look for loops +- Constants are dropped (Big O describes the upper bound or growth of the + algorithm where the constant eventually becomes irrelevant) +- We often only consider worst case (e.g., searching through a list where the + element you want is the last one) diff --git a/doublylinkedlist.c b/doublylinkedlist.c new file mode 100644 index 0000000..e98217a --- /dev/null +++ b/doublylinkedlist.c @@ -0,0 +1,161 @@ +#include +#include + +struct node { + int val; + struct node *prev; + struct node *next; +}; + +struct node *head; +struct node *tail; +int len = 0; + +void +prepend(int val) +{ + struct node *tmp = malloc(sizeof(struct node)); + tmp->val = val; + if (head == NULL) { + head = tail = tmp; + return; + } + tmp->val = val; + tmp->next = head; + head->prev = tmp; + head = tmp; + ++len; +} + +void +append(int val) +{ + struct node *tmp = malloc(sizeof(struct node)); + tmp->val = val; + if (!tail) { + head = tail = tmp; + return; + } + tmp->prev = tail; + tail->next = tmp; + tail = tmp; + ++len; +} + +struct node +*get_at(int i) +{ + struct node *cur = head; + for (int j = 0; cur && j < i; ++j) { + cur = cur->next; + } + return cur; +} + +void +insert_at(int val, int i) +{ + if (i > len) { + printf("index is greater than the list length\n"); + } else if (i == len) { + append(val); + return; + } else if (i == 0) { + prepend(val); + return; + } + struct node *cur = get_at(i); + struct node *tmp = malloc(sizeof(struct node)); + tmp->next = cur; + tmp->prev = cur->prev; + cur->prev = tmp; + + if (tmp->prev) { + tmp->prev->next = tmp; + } + ++len; +} + +int +remove_node(struct node *tmp) +{ + --len; + if (len == 0) { + head = tail = NULL; + return -1; + } + + if (tmp->prev) { + tmp->prev->next = tmp->next; + } + if (tmp->next) { + tmp->next->prev = tmp->prev; + } + + if (tmp == head) { + head = tmp->next; + } + if (tmp == tail) { + tail = tmp->prev; + } + + int val = tmp->val; + free(tmp); + return val; +} + +int +remove_val(int val) +{ + struct node *cur = head; + for (int i = 0; cur && cur->val != val && i < len; ++i) { + cur = cur->next; + } + if (!cur) { + return -1; + } + return remove_node(cur); +} + +int +remove_at(int i) +{ + struct node *tmp = get_at(i); + if (!tmp) { + return -1; + } + return remove_node(tmp); +} + +int +get(int i) +{ + get_at(i)->val; +} + +void +print() +{ + struct node *cur = head; + while (cur != NULL) { + printf("%d ", cur->val); + cur = cur->next; + } + printf("\n"); +} + +int +main() +{ + int val, n = 0; + printf("How many integers?\n"); + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + printf("Enter an integer \n"); + scanf("%d", &val); + prepend(val); + print(); + } + + return 0; +} diff --git a/maze/data_structures.h b/maze/data_structures.h new file mode 100644 index 0000000..e856aaa --- /dev/null +++ b/maze/data_structures.h @@ -0,0 +1,16 @@ +#ifndef DATA_STRUCTURES_H +#define DATA_STRUCTURES_H + +struct point { + char c; + int x; + int y; + struct point *next; +}; + +extern struct point *head; + +void push(int x, int y, char c); +char pop(); + +#endif diff --git a/maze/point.c b/maze/point.c new file mode 100644 index 0000000..c83c80d --- /dev/null +++ b/maze/point.c @@ -0,0 +1,29 @@ +#include +#include +#include "data_structures.h" + +struct point *head; + +void +push(int x, int y, char c) +{ + struct point *tmp = malloc(sizeof(struct point)); + tmp->c = c; + tmp->x = x; + tmp->y = y; + tmp->next = head; + head = tmp; +} + +char +pop() +{ + if (head == NULL) { + return -1; + } + struct point *tmp = head; + char c = tmp->c; + head = head->next; + free(tmp); + return c; +} diff --git a/maze/solver.c b/maze/solver.c new file mode 100644 index 0000000..3617f73 --- /dev/null +++ b/maze/solver.c @@ -0,0 +1,88 @@ +#include +#include +#include "data_structures.h" + +int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; + +int +walk(struct point maze[7][7], char wall, struct point cur, int vis[7][7], + struct point end) +{ + printf("%d %d ", cur.x, cur.y); + if (maze[cur.y][cur.x].c == wall) { + printf("wall\n"); + return 0; + } + if (vis[cur.y][cur.x]) { + printf("vis\n"); + return 0; + } + if (cur.x == end.x && cur.y == end.y) { + push(end.c, end.x, end.y); + return 1; + } + + printf("\n"); + vis[cur.y][cur.x] = 1; + push(cur.x, cur.y, cur.c); + + for (int i = 0; i < 4; ++i) { + int y = cur.y + dir[i][0]; + int x = cur.x + dir[i][1]; + if (x >= 0 && x < 7 && y >= 0 && y < 7) { + if (walk(maze, wall, maze[y][x], vis, end)) { + return 1; + } + } + } + + pop(cur.c); + + return 0; +} + +void +solve(struct point maze[7][7], char wall, struct point start, struct point end) +{ + int vis[7][7]; + for (int y = 0; y < 7; ++y) { + for (int x = 0; x < 7; ++x) { + vis[y][x] = 0; + } + } + walk(maze, wall, start, vis, end); +} + +int +main() +{ + struct point maze[7][7]; + for (int y = 0; y < 7; ++y) { + for (int x = 0; x < 7; ++x) { + if (x == 0 & y == 0) { + maze[y][x].c = 'S'; + } else if (x == 6 && y == 6) { + maze[y][x].c = 'E'; + } else if (y == 1 && x < 6 + || y == 3 && x > 0 + || y == 5 && x < 6) { + maze[y][x].c = '#'; + } else { + maze[y][x].c = ' '; + } + maze[y][x].x = x; + maze[y][x].y = y; + printf("%c", maze[y][x].c); + } + printf("\n"); + } + solve(maze, '#', maze[0][0], maze[6][6]); + + printf("\n\nreverse solution\n\n"); + struct point *cur = head; + while (cur->next != NULL) { + printf("%d %d\n", cur->x, cur->y); + cur = cur->next; + } + return 0; +} diff --git a/min_heap.c b/min_heap.c new file mode 100644 index 0000000..feeaf68 --- /dev/null +++ b/min_heap.c @@ -0,0 +1,113 @@ +#include +#include + +int *arr; +size_t len = 0; + +int +get_parent(int i) +{ + return (i - 1) / 2; +} + +int +get_left_child(int i) +{ + return i * 2 + 1; +} + +int +get_right_child(int i) +{ + return i * 2 + 2; +} + +void +heapify_down(int i) +{ + int l = get_left_child(i); + int r = get_right_child(i); + + if (i >= len || l >= len) { + return; + } + + int left_val = arr[l]; + int right_val = arr[r]; + int val = arr[i]; + + if (right_val > left_val && val > left_val) { + arr[i] = left_val; + arr[l] = val; + heapify_down(l); + } else if (left_val > right_val && val > right_val) { + arr[i] = right_val; + arr[r] = val; + heapify_down(r); + } +} + +void +heapify_up(int i) +{ + if (i == 0) { + return; + } + + int p = get_parent(i); + int parent_val = arr[p]; + int child_val = arr[i]; + + if (parent_val > child_val) { + arr[i] = parent_val; + arr[p] = child_val; + heapify_up(p); + } +} + +void +insert(int val) +{ + arr = realloc(arr, ++len * sizeof(int)); + arr[len - 1] = val; + heapify_up(len - 1); +} + +int +delete() +{ + if (len == 0) { + return -1; + } + int val = arr[0]; + if (len == 1) { + free(arr); + return val; + } + + arr[0] = arr[--len]; + heapify_down(0); + arr = realloc(arr, len * sizeof(int)); + return val; + +} + +int +main() +{ + arr = calloc(len, sizeof(int)); + insert(5); + insert(3); + insert(9); + insert(7); + for (int i = 0; i < len; ++i) { + printf("%d ", arr[i]); + } + printf("\n"); + delete(); + for (int i = 0; i < len; ++i) { + printf("%d ", arr[i]); + } + printf("\n"); + return 0; +} diff --git a/queue.c b/queue.c new file mode 100644 index 0000000..e0923ec --- /dev/null +++ b/queue.c @@ -0,0 +1,68 @@ +#include +#include + +struct node { + int val; + struct node *next; +}; + +struct node *head; +struct node *tail; + +void +enqueue(int val) +{ + struct node *tmp = malloc(sizeof(struct node)); + tmp->val = val; + if (head == NULL) { + tail = head = tmp; + return; + } + tail->next = tmp; + tail = tmp; +} + +int +deque() +{ + if (head == NULL) { + return -1; + } + struct node *tmp = head; + int val = tmp->val; + head = head->next; + free(tmp); + return val; +} + +int +peek() +{ + return head == NULL ? -1 : head->val; +} + +void +print() +{ + struct node *cur = head; + while (cur != NULL) { + printf("%d ", cur->val); + cur = cur->next; + } + printf("\n"); +} + +int +main() +{ + int val, n = 0; + printf("How many integers?\n"); + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + printf("Enter an integer \n"); + scanf("%d", &val); + enqueue(val); + print(); + } + return 0; +} diff --git a/recursion.md b/recursion.md new file mode 100644 index 0000000..a79729c --- /dev/null +++ b/recursion.md @@ -0,0 +1,8 @@ +# Recursion + +1. Base case +2. Function call with consecution + +- Pre +- Recurse +- Post diff --git a/search.c b/search.c new file mode 100644 index 0000000..33218b0 --- /dev/null +++ b/search.c @@ -0,0 +1,61 @@ +#include +#include + +int +linear(int *haystack, int len, int needle) +{ + for (int i = 0; i < len; ++i) { + if (haystack[i] == needle) { + return 1; + } + } + return 0; +} + +int +binary(int *haystack, int low, int high, int needle) +{ + if (low > high) { + return 0; + } + + int mid = low + (high - low) / 2; + if (haystack[mid] == needle) { + return 1; + } else if (haystack[mid] > needle) { + binary(haystack, low, mid - 1, needle); + } else { + binary(haystack, mid + 1, high, needle); + } +} + +int +square(int *breaks, int len, int needle) +{ + int jmp = floor(sqrt(len)); + int i = jmp; + for (; i < len; i += jmp){ + if (breaks[i]) { + break; + } + } + i -= jmp; + for (int j = 0; j <= jmp && i < len; ++i, ++j) { + if (breaks[i]) { + return i; + } + } + return 0; +} + +int +main() +{ + int haystack[5] = {0, 1, 2, 3, 4}; + int breaks[5] = {0, 0, 1, 0, 0}; + int len = sizeof(haystack) / sizeof(int); + printf("%d\n", linear(haystack, len, 3)); + printf("%d\n", binary(haystack, 0, len, 3)); + printf("%d\n", square(breaks, len, 3)); + return 0; +} diff --git a/sort.c b/sort.c new file mode 100644 index 0000000..2044d57 --- /dev/null +++ b/sort.c @@ -0,0 +1,60 @@ +#include + +int +partition(int *nums, int low, int high) +{ + int pivot = nums[high]; + int i = low - 1; + for (int j = low; j < high; ++j) { + if (nums[j] <= pivot) { + int tmp = nums[j]; + nums[j] = nums[++i]; + nums[i] = tmp; + } + } + + nums[high] = nums[++i]; + nums[i] = pivot; + return i; +} + +int +*quick(int *nums, int low, int high) +{ + if (low >= high) { + return nums; + } + + int i = partition(nums, low, high); + nums = quick(nums, low, i - 1); + nums = quick(nums, i + 1, high); + return nums; +} + +int +*bubble(int *nums, int len) +{ + for (int i = 0; i < len; ++i) { + for (int j = i; j < len - 1 - i; ++j) { + if (nums[j] > nums[j + 1]) { + int tmp = nums[j]; + nums[j] = nums[j + 1]; + nums[j + 1] = tmp; + } + } + } + return nums; +} + +int +main() +{ + int nums[5] = {0, 4, 2, 1, 3}; + int len = sizeof(nums) / sizeof(int); + /* int *res = bubble(nums, len); */ + int *res = quick(nums, 0, 4); + for (int i = 0; i < len; ++i) { + printf("%d\n", res[i]); + } + return 0; +} diff --git a/stack.c b/stack.c new file mode 100644 index 0000000..a460629 --- /dev/null +++ b/stack.c @@ -0,0 +1,63 @@ +#include +#include + +struct node { + int val; + struct node *prev; +}; + +struct node *head; + +void +push(int val) +{ + struct node *tmp = malloc(sizeof(struct node)); + tmp->val = val; + tmp->prev = head; + head = tmp; +} + +int +pop() +{ + if (head == NULL) { + return -1; + } + struct node *tmp = head; + int val = tmp->val; + head = head->prev; + free(tmp); + return val; +} + +int +peek() +{ + return head == NULL ? -1 : head->val; +} + +void +print() +{ + struct node *cur = head; + while (cur != NULL) { + printf("%d ", cur->val); + cur = cur->prev; + } + printf("\n"); +} + +int +main() +{ + int val, n = 0; + printf("How many integers?\n"); + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + printf("Enter an integer \n"); + scanf("%d", &val); + push(val); + print(); + } + return 0; +} diff --git a/tree/data_structures.h b/tree/data_structures.h new file mode 100644 index 0000000..dbc7bdc --- /dev/null +++ b/tree/data_structures.h @@ -0,0 +1,14 @@ +#ifndef DATA_STRUCTURES_H +#define DATA_STRUCTURES_H + +struct node { + int val; + struct node *left; + struct node *right; +}; + +extern struct node *root; + +struct node *insert(struct node* cur, int val); + +#endif diff --git a/tree/node.c b/tree/node.c new file mode 100644 index 0000000..c0d7738 --- /dev/null +++ b/tree/node.c @@ -0,0 +1,29 @@ +#include +#include +#include "data_structures.h" + +struct node *root = NULL; + +struct node +*create(int val) +{ + struct node *tmp = malloc(sizeof(struct node)); + tmp->val = val; + tmp->left = NULL; + tmp->right = NULL; + return tmp; +} + +struct node +*insert(struct node *cur, int val) +{ + if (cur == NULL) { + return create(val); + } + if (val < cur->val) { + cur->left = insert(cur->left, val); + } else if (val > cur->val) { + cur->right = insert(cur->right, val); + } + return cur; +} diff --git a/tree/tree.c b/tree/tree.c new file mode 100644 index 0000000..82b4544 --- /dev/null +++ b/tree/tree.c @@ -0,0 +1,54 @@ +#include +#include +#include "data_structures.h" + +void +pre_order(struct node *cur) +{ + if (cur == NULL) { + return; + } + printf("%d ", cur->val); + pre_order(cur->left); + pre_order(cur->right); +} + +void +in_order(struct node *cur) +{ + if (cur == NULL) { + return; + } + in_order(cur->left); + printf("%d ", cur->val); + in_order(cur->right); +} + +void +post_order(struct node *cur) +{ + if (cur == NULL) { + return; + } + post_order(cur->left); + post_order(cur->right); + printf("%d ", cur->val); +} + +int +main() +{ + struct node *root = NULL; + root = insert(root, 10); + int val, n = 0; + printf("How many integers do you want to add to root with val 10?\n"); + scanf("%d", &n); + for (int i = 0; i < n; ++i) { + printf("Enter a number \n"); + scanf("%d", &val); + insert(root, val); + in_order(root); + printf("\n"); + } + return 0; +} -- cgit v1.2.3