[SDP/E2] Added work from exam

2 files changed, 200 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/Exam 2/ex1.cpp b/Year 2/Structures and data algorithms/Exam 2/ex1.cpp
new file mode 100644
index 0000000..822d316
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Exam 2/ex1.cpp
@@ -0,0 +1,119 @@
+#include <iostream>
+#include <cstring>
+#include <vector> // Б подточка
+
+template <typename T>
+struct Node {
+	T data;
+	Node<T> *left, *right;
+	Node(const T& data, Node<T>* left = nullptr, Node<T>* right = nullptr) : data(data), left(left), right(right) {}
+};
+
+void freeTree(const Node<char>* tree) {
+	if (tree == nullptr) return;
+	freeTree(tree->left);
+	freeTree(tree->right);
+	delete tree;
+}
+
+/* Подточка А */
+
+bool checkWord(const Node<char>* tree, const char* start, const char* end) {
+	if (start == end)
+		return true;
+	if (start == nullptr || tree == nullptr)
+		return false;
+	if (*start != tree->data)
+		return false;
+
+	return checkWord(tree->left, start + 1, end) || checkWord(tree->right, start + 1, end);
+}
+
+bool readWord(const Node<char>* tree, const char* word) {
+	if (strlen(word) < 4)
+		throw std::runtime_error("Word length cannot be less than 4!");
+
+	const char* endWord = word;
+	while (*endWord != '\0') endWord++;
+
+	const char* separator = word + 1;
+	while (separator != endWord) {
+		if (checkWord(tree->right, word, separator) && checkWord(tree->left, separator, endWord))
+			return true;
+		separator++;
+	}
+	return false;
+}
+
+void A() {
+	const Node<char>* t =
+		new Node<char>('F',
+				new Node<char>('B',
+					new Node<char>('A'),
+					new Node<char>('D',
+						new Node<char>('C'),
+						new Node<char>('E'))),
+				new Node<char>('G',
+					nullptr,
+					new Node<char>('I',
+						new Node<char>('H'),
+						nullptr)));
+
+	std::cout << readWord(t, "GIBDC") << readWord(t, "GIBD") << readWord(t, "GIBCD") << readWord(t, "GHBD") << std::endl;
+	freeTree(t);
+}
+
+/* Подточка Б */
+
+bool risingOrder(std::vector<char>& v) {
+	for (size_t i = 0; i < v.size() - 1; i++) {
+		if (v[i] > v[i+1]) return false;
+	}
+	return true;
+}
+
+void getLevel(const Node<char>* tree, size_t level, std::vector<char>& out) {
+	if (level == 0) return;
+	if (tree->left != nullptr) getLevel(tree->left, level - 1, out);
+	if (level == 1) {
+		out.push_back(tree->data);
+		return;
+	}
+	if (tree->right != nullptr) getLevel(tree->right, level - 1, out);
+}
+
+size_t minLevel(const Node<char>* tree) {
+	std::vector<char> temp;
+	size_t i = 1;
+	getLevel(tree, i, temp);
+	while (!temp.empty()) {
+		i++;
+		temp.clear();
+		getLevel(tree, i, temp);
+		if (risingOrder(temp)) break;
+	}
+	return (temp.empty()) ? 0 : i;
+}
+
+void B() {
+	const Node<char>* t =
+		new Node<char>('F',
+				new Node<char>('Z',
+					new Node<char>('Z'),
+					new Node<char>('D',
+						new Node<char>('C'),
+						new Node<char>('E'))),
+				new Node<char>('G',
+					nullptr,
+					new Node<char>('I',
+						new Node<char>('H'),
+						nullptr)));
+
+	std::cout << minLevel(t) << std::endl;
+	freeTree(t);
+}
+
+int main() {
+	//A();
+	B();
+}
diff --git a/Year 2/Structures and data algorithms/Exam 2/ex2.cpp b/Year 2/Structures and data algorithms/Exam 2/ex2.cpp
new file mode 100644
index 0000000..cbe6a02
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Exam 2/ex2.cpp
@@ -0,0 +1,81 @@
+#include <iostream>
+
+template <typename T>
+struct DLListElem {
+	T data;
+	DLListElem<T> *next, *prev;
+	DLListElem(const T& data, DLListElem<T>* next = nullptr, DLListElem<T>* prev = nullptr) : data(data), next(next), prev(prev) {}
+};
+
+template <typename T>
+void freeList(DLListElem<T>* l) {
+	DLListElem<T>* temp;
+	while (l != nullptr) {
+		temp = l;
+		l = l->next;
+		delete temp;
+	}
+}
+
+// A <-> i <-> j <-> D
+
+template <typename T>
+void swap(DLListElem<T>* i, DLListElem<T>* j) {
+	if (i == j) return;
+	if (i->prev != nullptr) i->prev->next = j;
+	if (j->next != nullptr) j->next->prev = i;
+	DLListElem<T>* iPrev = i->prev;
+	i->next = j->next;
+	i->prev = j;
+	j->next = i;
+	j->prev = iPrev;
+}
+template <typename T>
+void swapNext(DLListElem<T>* i, DLListElem<T>* j) {
+	if (i == j) return;
+	if (i->prev != nullptr) i->prev->next = j;
+	i->next = j->next;
+	j->next = i;
+}
+
+// O(n^2) time complexity
+template <typename T>
+void sortDescending(DLListElem<T>* start, DLListElem<T>* end) {
+	for (DLListElem<T>* i = end; i != start && i != nullptr; i = i->prev) {
+		DLListElem<T>* toSwap = i;
+		for (DLListElem<T>* j = i->prev; j != start && j != nullptr; j = j->prev) {
+			if (j->data < toSwap->data) toSwap = j;
+		}
+		//swap(i, toSwap);
+		swapNext(i, toSwap);
+	}
+	// TODO: update prevs
+}
+
+int main() {
+	DLListElem<int>* l1 = new DLListElem<int>(1);
+	DLListElem<int>* l2 = new DLListElem<int>(2);
+	DLListElem<int>* l3 = new DLListElem<int>(3);
+	DLListElem<int>* l4 = new DLListElem<int>(4);
+	DLListElem<int>* l5 = new DLListElem<int>(5);
+	DLListElem<int>* l6 = new DLListElem<int>(6);
+	DLListElem<int>* l7 = new DLListElem<int>(7);
+	DLListElem<int>* l8 = new DLListElem<int>(8);
+	
+	// 8 7 2 5 6 1 4 3
+	               l8->next = l7;
+	l7->prev = l8; l7->next = l2;
+	l2->prev = l7; l2->next = l5;
+	l5->prev = l2; l5->next = l6;
+	l6->prev = l5; l6->next = l1;
+	l1->prev = l6; l1->next = l4;
+	l4->prev = l1; l4->next = l3;
+	l3->prev = l4;
+
+	sortDescending(l8, l3);
+	for (DLListElem<int>* i = l8; i != nullptr; i = i->next)
+		std::cout << i->data << ", ";
+	std::cout << std::endl;
+
+	freeList(l1);
+}