From 0887d8f96950a060a122e14ed2981182ff1eb37d Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Sat, 28 Dec 2019 21:16:58 +0700
Subject: [usth/ICT2.1] Algorithm and Data Structures

---
 usth/ICT2.1/labwork/6/Ex1.c   | 123 ++++++++++++++++++++++++++++++++++++++++++
 usth/ICT2.1/labwork/6/TT6.pdf | Bin 0 -> 413253 bytes
 2 files changed, 123 insertions(+)
 create mode 100644 usth/ICT2.1/labwork/6/Ex1.c
 create mode 100644 usth/ICT2.1/labwork/6/TT6.pdf

(limited to 'usth/ICT2.1/labwork/6')

diff --git a/usth/ICT2.1/labwork/6/Ex1.c b/usth/ICT2.1/labwork/6/Ex1.c
new file mode 100644
index 0000000..12ebb02
--- /dev/null
+++ b/usth/ICT2.1/labwork/6/Ex1.c
@@ -0,0 +1,123 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#define MIN(a, b) (((a) < (b)) ? (a) : (b))
+#define MAX(a, b) (((a) > (b)) ? (a) : (b))
+
+int *rand_array(size_t nmemb)
+{
+	int *base = malloc(nmemb * sizeof(int));
+	for (size_t i = 0; i < nmemb; ++i)
+		base[i] = rand() % (1 << nmemb);
+	return base;
+}
+
+size_t bits(size_t n)
+{
+	size_t h = 0;
+	while (n) {
+		n >>= 1;
+		h++;
+	}
+	return h;
+}
+
+void *tree(int *base, size_t *nmemb)
+{
+	size_t n = 1 << bits(*nmemb - 1);
+	if ((base = realloc(base, n * sizeof(int) << 1)) == NULL)
+		return NULL;
+	memcpy(base + n, base, *nmemb * sizeof(int));
+	int max = *base;
+	for (size_t i = 1; i < *nmemb; ++i)
+		max = MAX(base[n + i], max);
+	for (size_t i = *nmemb; i < n; ++i)
+		base[n + i] = max;
+	for (size_t i = n; --i;)
+		base[i] = MIN(base[i << 1], base[(i << 1) + 1]);
+	*nmemb = n << 1;
+	return base;
+}
+
+void display(int *base, size_t nmemb, size_t node, size_t indent)
+{
+	if (node < 1 || node >= nmemb)
+		return;
+	display(base, nmemb, node << 1, indent + 1);
+	for (size_t i = 0; i++ < indent; putchar(9));
+	printf("%d", base[node]);
+	putchar(10);
+	display(base, nmemb, (node << 1) + 1, indent + 1);
+}
+
+size_t search(int value, int *base, size_t nmemb, size_t pos)
+{
+	if (pos < 1 || pos >= nmemb || base[pos] > value)
+		return 0;
+	if (base[pos] == value)
+		return pos;
+	size_t left = search(value, base, nmemb, pos << 1);
+	return left ? left : search(value, base, nmemb, (pos << 1) + 1);
+}
+
+void treeify(int *base, size_t nmemb, size_t node)
+{
+	if (node > 1 && node < nmemb && base[node >> 1] > base[node]) {
+		base[node >> 1] = base[node];
+		treeify(base, nmemb, node >> 1);
+	}
+}
+
+void insert(int value, size_t pos, int *base, size_t nmemb)
+{
+	if (pos >= nmemb >> 1 && pos < nmemb) {
+		base[pos] = value;
+		treeify(base, nmemb, pos);
+	}
+}
+
+void delete(size_t pos, int *base, size_t nmemb)
+{
+	if (pos > 1 && pos < nmemb) {
+		base[pos] = base[pos >> 1];
+		delete(pos << 1, base, nmemb);
+		delete((pos << 1) + 1, base, nmemb);
+	}
+}
+
+int main()
+{
+	size_t n;
+	puts("Array length:");
+	scanf("%zu", &n);
+
+	srand(time(NULL));
+	int *a = rand_array(n);
+	a = tree(a, &n);
+	display(a, n, 1, 0);
+
+	int x;
+	puts("Value to search for:");
+	scanf("%d", &x);
+	size_t i = search(x, a, n, 1);
+	if (i)
+		display(a, n, i, 0);
+	else
+		puts("Not found");
+
+	puts("Value to insert:");
+	scanf("%d", &x);
+	puts("Leaf index to insert to:");
+	scanf("%zu", &i);
+	insert(x, i, a, n);
+	display(a, n, 1, 0);
+
+	puts("Node to be deleted:");
+	scanf("%zu", &i);
+	delete(i, a, n);
+	display(a, n, 1, 0);
+
+	return 0;
+}
diff --git a/usth/ICT2.1/labwork/6/TT6.pdf b/usth/ICT2.1/labwork/6/TT6.pdf
new file mode 100644
index 0000000..d4d3bf5
Binary files /dev/null and b/usth/ICT2.1/labwork/6/TT6.pdf differ
-- 
cgit 1.4.1