Sort, Queen, Tree

hoan.phamphu · hoan.phamphu · commit dcada03e0ce8 · 2021-12-09T01:00:30.000+07:00
diff --git a/01.LinkedLists/_main.c b/01.LinkedLists/_main.c
diff --git a/02.DoublyLinkedLists/_main.c b/02.DoublyLinkedLists/_main.c
diff --git a/03.CircularLinkedLists/_main.c b/03.CircularLinkedLists/_main.c
diff --git a/BackTracking/Queen.c b/BackTracking/Queen.c
@@ -0,0 +1,45 @@
+//
+//  Queen.c
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 23/10/2021.
+//
+
+#include <math.h>
+#include "Queen.h"
+
+int a[20], count = 0;
+
+void print_result(int n) {
+    count++;
+    char c = '0';
+    char x = '1';
+    printf("%d.\n", count);
+    for (int i = 1; i <= n; i++) {
+        for (int t = 1; t < a[i]; t++) printf(" %c ", c);
+        printf(" %c ", x);
+        for (int t = a[i] + 1; t <= n; t++) printf(" %c ", c);
+        printf("\n");
+    }
+    printf("\n");
+}
+
+int is_candidate(int x, int y) {
+    for (int i = 1; i < x; i++) {
+        if ((y == a[i]) || (fabs(y-a[i]) == x-i)) {
+            return 0;
+        }
+    }
+    return 1;
+}
+
+void queen(int i, int n) {  // Quân Hậu ở hàng i, cột j
+    for (int j = 1; j <= n; j++) {
+        if (is_candidate(i, j)) {
+            a[i] = j;
+            if (i == n) print_result(n);
+            else queen(i+1, n);
+        }
+    }
+}
+
diff --git a/BackTracking/Queen.h b/BackTracking/Queen.h
@@ -0,0 +1,15 @@
+//
+//  Queen.h
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 23/10/2021.
+//
+
+#ifndef Queen_h
+#define Queen_h
+
+#include <stdio.h>
+
+void queen(int i, int n);
+
+#endif /* Queen_h */
diff --git a/BinarySearch/BinarySearch.c b/BinarySearch/BinarySearch.c
@@ -0,0 +1,27 @@
+//
+//  BinarySearch.c
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 17/10/2021.
+//
+
+#include "BinarySearch.h"
+
+
+int binary_search(int *a, int start, int finish, int x) {
+    int middle = (start + finish)/2;
+    if (start == finish) {
+        if (a[middle] == x) {
+            return middle;
+        } else {
+            return -1;
+        }
+    }
+    if (a[middle] == x) {
+        return middle;
+    } else if (a[middle] > x) {
+        return binary_search(a, start, middle-1, x);
+    } else {
+        return binary_search(a, middle+1, finish, x);
+    }
+}
diff --git a/BinarySearch/BinarySearch.h b/BinarySearch/BinarySearch.h
@@ -0,0 +1,15 @@
+//
+//  BinarySearch.h
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 17/10/2021.
+//
+
+#ifndef BinarySearch_h
+#define BinarySearch_h
+
+#include <stdio.h>
+
+int binary_search(int *a, int start, int finish, int x);
+
+#endif /* BinarySearch_h */
diff --git a/DataStructure-Algorithm/main.c b/DataStructure-Algorithm/main.c
@@ -0,0 +1,67 @@
+//
+//  main.c
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 10/10/2021.
+//
+
+#include <stdio.h>
+#include "../SortAlgorithm/BubbleSort.h"
+#include "../BinarySearch/BinarySearch.h"
+#include "../SortAlgorithm/MergeSort.h"
+#include "../BackTracking/Queen.h"
+#include "../Tree/LeftMostChild_RightSibling.h"
+
+
+int main(int argc, const char * argv[]) {
+//    int n = 10;
+//    int input[10] = {3, 5, 2, 7, 1, 0, 4, 8, 9, 6};
+//
+//    bubble_sort(input, n);
+//
+//    printf("kết quả: ");
+//    for (int i = 0; i < n; i++){
+//        printf("%d ", input[i]);
+//    }
+    
+//    int a[10] = {0, 1, 3, 5, 7, 9, 10, 11, 15, 17};
+//    int index = binary_search(a, 0, 9, 10);
+//    printf("Index: %d\n", index);
+    
+//    int n;
+//    printf("Input n = "); scanf("%d", &n);
+//    queen(1, n);
+    
+    treeNode * root = make_treeNode(0);
+    treeNode * b = make_treeNode(1);
+    treeNode * c = make_treeNode(2);
+    treeNode * d = make_treeNode(3);
+    treeNode * e = make_treeNode(4);
+    treeNode * f = make_treeNode(5);
+    treeNode * g = make_treeNode(6);
+    treeNode * h = make_treeNode(7);
+    treeNode * i = make_treeNode(8);
+    treeNode * j = make_treeNode(9);
+    treeNode * k = make_treeNode(10);
+
+    root->leftmost_child = b;
+    b->right_sibling = c;
+    b->leftmost_child = e;
+    e->right_sibling = f;
+    c->leftmost_child = g;
+    c->right_sibling = d;
+    g->leftmost_child = h;
+    h->right_sibling = i;
+    i->right_sibling = j;
+    j->right_sibling = k;
+    
+    
+    printf("Pre Order\n");
+    preOrder(root);
+    printf("In Order\n");
+    inOrder(root);
+    printf("Post Order\n");
+    postOrder(root);
+    
+    return 0;
+}
diff --git a/SortAlgorithm/BubbleSort.c b/SortAlgorithm/BubbleSort.c
@@ -0,0 +1,30 @@
+//
+//  BubbleSort.c
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 10/10/2021.
+//
+
+#include "BubbleSort.h"
+
+void print_array(int arr[], int n);
+
+void bubble_sort(int arr[], int n){
+    for (int i = n-1; i > 0; i--){
+        for (int j = 1; j <= i; j++){
+            if (arr[j-1] > arr[j]) {
+                int t = arr[j-1];
+                arr[j-1] = arr[j];
+                arr[j] = t;
+            }
+        }
+        print_array(arr, n);
+    }
+}
+
+void print_array(int arr[], int n) {
+    for (int i = 0; i < n; i++){
+        printf("%d ", arr[i]);
+    }
+    printf("\n");
+}
diff --git a/SortAlgorithm/BubbleSort.h b/SortAlgorithm/BubbleSort.h
@@ -0,0 +1,15 @@
+//
+//  BubbleSort.h
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 10/10/2021.
+//
+
+#ifndef BubbleSort_h
+#define BubbleSort_h
+
+#include <stdio.h>
+
+void bubble_sort(int arr[], int n);
+
+#endif /* BubbleSort_h */
diff --git a/SortAlgorithm/MergeSort.c b/SortAlgorithm/MergeSort.c
@@ -0,0 +1,23 @@
+//
+//  MergeSort.c
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 23/10/2021.
+//
+
+#include "MergeSort.h"
+
+void merge(int arr[], int p, int q, int r) {
+    int i = p;
+    int j = q+1;
+}
+
+
+void merge_sort(int arr[], int p, int r) {
+    if (p < r) {
+        int q = (p+r)/2;
+        merge_sort(arr, p, q);
+        merge_sort(arr, q+1, r);
+        merge(arr, p, q, r);
+    }
+}
diff --git a/SortAlgorithm/MergeSort.h b/SortAlgorithm/MergeSort.h
@@ -0,0 +1,15 @@
+//
+//  MergeSort.h
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 23/10/2021.
+//
+
+#ifndef MergeSort_h
+#define MergeSort_h
+
+#include <stdio.h>
+
+void merge_sort(int arr[], int p, int r);
+
+#endif /* MergeSort_h */
diff --git a/Tree/LeftMostChild_RightSibling.c b/Tree/LeftMostChild_RightSibling.c
@@ -0,0 +1,56 @@
+//
+//  LeftMostChild_RightSibling.c
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 09/12/2021.
+//
+
+#include <stdlib.h>
+#include "LeftMostChild_RightSibling.h"
+
+treeNode * make_treeNode(int d){
+    treeNode * newNode = NULL;
+    newNode = (treeNode*) malloc(sizeof(treeNode));
+    newNode->data = d;
+    newNode->leftmost_child = NULL;
+    newNode->right_sibling = NULL;
+    return newNode;
+}
+
+void preOrder(treeNode * nodeR){
+    printf("%d\n", nodeR->data);
+    if (nodeR->leftmost_child != NULL) {
+        preOrder(nodeR->leftmost_child);
+        treeNode * temp = nodeR->leftmost_child->right_sibling;
+        while (temp != NULL){
+            preOrder(temp);
+            temp = temp->right_sibling;
+        }
+    }
+}
+
+void inOrder(treeNode * nodeR){
+    if (nodeR->leftmost_child == NULL) {
+        printf("%d\n", nodeR->data);
+    } else {
+        inOrder(nodeR->leftmost_child);
+        printf("%d\n", nodeR->data);
+        treeNode * temp = nodeR->leftmost_child->right_sibling;
+        while (temp != NULL){
+            inOrder(temp);
+            temp = temp->right_sibling;
+        }
+    }
+}
+
+void postOrder(treeNode * nodeR){
+    if (nodeR->leftmost_child != NULL) {
+        postOrder(nodeR->leftmost_child);
+        treeNode * temp = nodeR->leftmost_child->right_sibling;
+        while (temp != NULL){
+            postOrder(temp);
+            temp = temp->right_sibling;
+        }
+    }
+    printf("%d\n", nodeR->data);
+}
diff --git a/Tree/LeftMostChild_RightSibling.h b/Tree/LeftMostChild_RightSibling.h
@@ -0,0 +1,26 @@
+//
+//  LeftMostChild_RightSibling.h
+//  DataStructure-Algorithm
+//
+//  Created by Pham Hoan on 09/12/2021.
+//
+
+#ifndef LeftMostChild_RightSibling_h
+#define LeftMostChild_RightSibling_h
+
+#include <stdio.h>
+
+struct Node
+{
+    int data;
+    struct Node * leftmost_child;
+    struct Node * right_sibling;
+};
+typedef struct Node treeNode;
+
+treeNode * make_treeNode(int);
+void preOrder(treeNode *);
+void inOrder(treeNode *);
+void postOrder(treeNode *);
+
+#endif /* LeftMostChild_RightSibling_h */
