commit 2256c601daad12b258162db70e3f53d5348d4c3d
parent b18d2dc2ca5824cac06486b12ed3318d106cfe70
Author: TranLili <tranlili96@gmail.com>
Date: Thu, 30 Nov 2023 14:41:15 +0100
Merge branch 'master' of https://github.com/LindholmLabs/DSA-Assignments
Diffstat:
| M | Problem2/Problem2.cpp | | | 78 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- |
| M | Problem3/Problem3.cpp | | | 189 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------------- |
2 files changed, 210 insertions(+), 57 deletions(-)
diff --git a/Problem2/Problem2.cpp b/Problem2/Problem2.cpp
@@ -1,15 +1,79 @@
-
+// Problem 2: Social Network
+// Description:
+// Course: IT405G - Datastructures and Algorithms
+// Authors: William Lindholm, Lili Tran, Victor Adamson
+// Date: 29-11-2023
+//
#include <iostream>
#include <queue>
+#include <vector>
+#include <list>
using namespace std;
-int main()
-{
- queue<int> network;
+class Graph {
+private:
+ int V;
+ vector<int>* adj;
+public:
+ Graph(int V);
+ void addEdge(int v, int w);
+ bool isEdge(int v, int w);
+ int getNumNodes();
+ void printGraph();
+};
+
+Graph::Graph(int V) {
+ this->V = V;
+ adj = new vector <int>[V];
+}
+
+void Graph::addEdge(int v, int w) {
+ adj[v].push_back(w);
+}
- while (!network.empty()) {
- cout << ' ' << network.front();
- network.pop();
+bool Graph::isEdge(int v, int w) {
+ vector<int>::iterator i;
+ for (i = adj[v].begin(); i != adj[v].end(); i++) {
+ if (w == *i) {
+ return(true);
+ }
+ return(false);
}
+}
+
+int Graph::getNumNodes() {
+ return V;
+}
+
+void Graph::printGraph() {
+ for (int v = 0; v < V; ++v) {
+ cout << "\nAdjacency list of node " << v << "\n head ";
+ vector<int>::iterator i;
+ for (i = adj[v].begin();
+ i != adj[v].end(); ++i) {
+ cout << "-> " << *i << " ";
+ }
+ }
+}
+
+int main(){
+ Graph network(4);
+ network.addEdge(0, 1); //A dislikes B
+ network.addEdge(1, 2); //B dislikes C
+ network.addEdge(1, 3); //B dislikes D
+ network.addEdge(2, 3); //C dislikes D
+ network.addEdge(2, 1); //C dislikes B
+ network.printGraph();
+ queue<int> queue;
+ const int i = network.getNumNodes();
+ list<int> nodes[4];
+ cout << "\n" << "Number of nodes: " << i << "\n";
+ vector<bool> visited[4];
+
+}
+
+bool isAdversary(Graph network, vector<bool> visited[4]) {
+
+ return true;
}
\ No newline at end of file
diff --git a/Problem3/Problem3.cpp b/Problem3/Problem3.cpp
@@ -12,83 +12,172 @@
using namespace std;
-
-struct node
+class Tree
{
- char data;
- int freq = 0;
- node* left = NULL;
- node* right = NULL;
-};
+public:
+ /*
+ * Constructor for leaf node
+ * @param w: the weight of the node
+ * @param c: the character of the node
+ */
+ Tree(int w, char c)
+ {
+ this->weight = w;
+ this->c = c;
+ }
+ /*
+ * Constructor for internal node
+ * @param w: the weight of the node
+ * @param t1: the left subtree
+ * @param t2: the right subtree
+ */
+ Tree(int w, Tree* t1, Tree* t2)
+ {
+ this->weight = w;
+ this->left = t1;
+ this->right = t2;
+ }
-class nodeComparator
-{
- public:
- bool operator() (const node& leftNode, const node& rightNode) const
- {
- return leftNode.freq > rightNode.freq;
- }
+ /*
+ * Destructor
+ */
+ ~Tree()
+ {
+ delete(left);
+ delete(right);
+ }
+
+ /*
+ * Get the weight of the node
+ * @return: the weight of the node
+ */
+ int getWeight() const
+ {
+ return this->weight;
+ }
+
+ /*
+ * Print the tree
+ * Example of output:
+ * 0 : a
+ * 1 0 : c
+ * 1 1 : b
+ * @param bitString: the bitstring of the node
+ */
+ void printTree(vector<char>& bitString) const
+ {
+
+ }
+
+private:
+ Tree* left;
+ Tree* right;
+ int weight;
+ char c;
};
+struct TreeWrapper
+{
+ TreeWrapper()
+ {
+ tree = NULL;
+ }
+
+ TreeWrapper(Tree* t)
+ {
+ tree = t;
+ }
+
+ bool operator<(const TreeWrapper& tw) const
+ {
+ return tree->getWeight() > tw.tree->getWeight();
+ }
+
+ Tree* tree;
+};
/*
- * Class: HuffmanTree
- * Description: A Huffman tree
- */
-class huffmanTree
+* Function: calculateWeight
+* Calculate the weight of a string
+* @param plainText: the string to calculate the weight of
+* @param targetLetter: the letter to calculate the weight of
+*/
+int calculateWeight(string plainText, char targetLetter)
{
- private:
- priority_queue<node, vector<node>, nodeComparator> nodes;
+ int weight = 0;
+ for (int i = 0; i < (int)plainText.size(); i++)
+ {
+ if (plainText[i] == targetLetter)
+ {
+ weight++;
+ }
+ }
+ return weight;
+}
+class HuffmanTree
+{
public:
/*
- * Function: Constructor
- * Description: Create a Huffman tree from a string
- * @param plainText: the string to create the tree
+ * Constructor
+ * @param plainText: the string to encode
*/
- huffmanTree(string plainText)
+ HuffmanTree(string plainText)
{
- // create nodes
- for (int i = 0; i < (int) plainText.length(); i++)
- {
- node n;
- n.data = plainText[i];
- n.freq += 1;
- nodes.push(n);
- }
+ this->plainText = plainText;
}
-
+
/*
- * Function: getTree
- * Description: Get the Huffman tree
- * @return: reference of īthe Huffman tree
+ * Encode the string
+ * @return: the encoded string
*/
- priority_queue<node, vector<node>, nodeComparator> getTree() const
+ string encode()
{
- return nodes;
+ auto subTrees = buildSubTrees();
+ auto root = buildTree(subTrees);
+
+ return "";
}
- /*
- * Function: printTree
- * Description: Print the Huffman tree
- */
- void print() const
+ private:
+ string plainText;
+
+ priority_queue<TreeWrapper> buildSubTrees()
{
- priority_queue<node, vector<node>, nodeComparator> temp = nodes;
+ priority_queue<TreeWrapper> q;
- while (!temp.empty())
+ for (int i = 0; i < (int)plainText.size(); i++)
{
- cout << temp.top().data << " " << temp.top().freq << endl;
- temp.pop();
+ int weight = calculateWeight(plainText, plainText[i]);
+ q.push(TreeWrapper(new Tree(weight, plainText[i])));
}
+
+ return q;
+ }
+
+ priority_queue<TreeWrapper> buildTree(priority_queue<TreeWrapper> q)
+ {
+ if (q.size() == 1)
+ {
+ return q;
+ }
+
+ TreeWrapper t1 = q.top();
+ q.pop();
+ TreeWrapper t2 = q.top();
+ q.pop();
+ q.push(TreeWrapper(new Tree(t1.tree->getWeight() + t2.tree->getWeight(), t1.tree, t2.tree)));
+
+ return buildTree(q);
}
};
int main()
{
- huffmanTree T = huffmanTree("Hello World");
-
- T.print();
+ HuffmanTree huffmanTree("abacabad");
+ string encoded = huffmanTree.encode();
+
+ cout << "The string was encoded to: " << encoded << endl;
};
