Projects I made in Data Structure. I use visual studio for my projects.
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers .
The terms of the polynomial will be stored in a singly linked list in decreasing order of the exponent values.
Implement polynomial functions using linked list.
Each term (except may be the first term) starts with a sign char (+ or -). Following the sign, the coefficient is specified followed by the ‘x’ and ‘ˆ’ chars. Finally comes the exponent. Notice that if the coefficient is 1, then it may be omitted as in the expression “xˆ3”. Similarly, if the exponent is 1, then it may be omitted as in the expression “2x”. Finally, if the exponent is 0, ‘x’ and ’ˆ’ chars are omitted altogether, e.g., “44”.
You may assume that the polynomial expressions will be well-formed, that is, they will not contain any errors. But there may be one or more spaces between the terms, i.e., before or after the sign symbols ‘+’ and ‘-’. To parse a given expression string, we suggest that you create a new expression string by removing all space chars. Then parse the new string one term at a time. Notice that each term of the polynomial is separated by a sign symbol.
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.
I use stack to solve arithmetic calculations.
-
When an operand is encountered, output it
-
When ’(’ is encountered, push it
-
When ’)’ is encountered, pop all symbols off the stack until ’(’ is encountered
-
When an operator, +, -, *, /, is encountered, pop symbols off the stack until you encounter a symbol that has lower priority
-
Push the encountered operator to the stack
“20+23+(28+5)*4”
“20 2 3 * + 2 8 * 5 + 4 * +” Postfix
A queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.
We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end. The element which is first pushed into the order, the operation is first performed on that. Position of the entry in a queue ready to be served, that is, the first entry that will be removed from the queue, is called the front (or the head) of the queue, similarly the position of the last entry in the queue, that is, the one most recently added, is called the rear (or the tail) of the queue.
I use a doubly-linked list to implement the Deque. All operations run in O(1).
Operations are addFront, addRear, removeFront, removeRear, front, rear, ısEmpty, size.
A Threaded BST is a BST where a the normally NULL left/right child pointers of a BST node point to the in-order predecessor/in-order successor node in the BST respectively. This allows us to walk over the threaded BST in forward or backward direction iteratively in O(n) time, where “n” is the number of keys in the tree.
Pay special attention to node that have 0 or 1 child. In a BST, the pointers pointing to a non-existent child would be set to NULL. But in the threaded BST, the right child pointer that would normally be NULL points to the in-order successor node. Similarly, a left child pointer that would normally be NULL points to the in-order predecessor node. If the in-order predecessor/successor does not exist, then and only then is the corresponding pointer set to NULL.
Operations are add, remove, getRoot, find, min, max, previous, next.
Previous returns max node on its left subtree.
Next returns min node on its right subtree.
AVL Tree can be defined as height balanced binary search tree in which each node is associated with a balance factor which is calculated by subtracting the height of its right sub-tree from that of its left sub-tree.
Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be unbalanced and need to be balanced.
If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right sub-tree.
If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal height.
If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right sub-tree.
An algorithm that returns a list of the most frequent "k" words in the given text file, in order of frequency. Words with the same frequency are displayed sequentially.
When processing the file: • The file is read line by line, each line is parsed according to its own words, and each word is appended to a map containing <word, frequency> pairs. All words are converted to lowercase letters and then stored on the map. Words shorter than 3 characters are ignored. This means “a”, “to”, “in” etc. means the words will be ignored. • All non-letter characters are ignored. That is, words will only contain letters from the 'a'-'z' alphabet. Other characters will be used to delimit words.
text file example: A text file is a file that only contains text and has no special formatting such as bold text, italic text, images, etc. bold, and, file, that, and.
When this file is processed, I will get the following <word, frequency> pairs:
Then I will return the most frequent “k” words. For example, if we want to return the most frequent 7 words from this list, then the result would be given in the following order:
Notice that the list is ordered with respect to the frequencies of the words. Also notice that the words that have the same frequency are given in sorted order. That is, “and” comes before “file” in the returned list. Similarly, “bold” comes before “that” both of which have a frequency of 2.
Algorithm take O(nlogn + k) time and O(n) space, where “n” is the number of words in the file.
-
Implement the map ADT using a BST as the underlying data structure. The map will store <word, frequency> pairs. The first time a word is added to the ADT map, its frequency is set to 1. The next time the same word is added, its frequency is only increased. Thus, when all words are added to the ADT map, the <word, frequency> pairs are available and all words can be accessed in a sequential manner. All insertions take at most O(logN) time. Therefore, adding the word "N" will take O(NlogN) time.
-
After processing all the words in the file and adding them to the map, it's time to take the most used "k" word and return it to the user in the required order. To implement this efficiently, an array with slots "t+1" is allocated where "t" is the frequency of the most frequently used word. In the example this is 4. Each slot of the array stores words with that frequency. That is, words with frequency "i", where 1<=i<=t, will be stored in the list in slot "i". For this purpose, the C++ vector is used. After adding all the words in the ADT map to this list array, it looks like this:
vector<vector> words(t+1) Here “t” is the highest frequency, which is 4 in the example.
- Once you have this word list, start from the last blank containing the words with the highest frequency and walk backwards by filling in the result. After copying the "k" word to the result, pause and return the result. If there are fewer words than the "k" word, then all the words are returned. Words with the same frequency are returned in sequential order. That is, the words "thick", "only", "it", each of which has 2 frequencies, are returned sequentially.