Data Structures

Basic data structures and algorithms in python Searching algorithms in python Linear search 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i # Return the index if target is found return -1 # Return -1 if the target is not found def main(): arr = [3, 10, 23, 5, 2, 6] target = 5 # Calling the linear_search function result = linear_search(arr, target) # Output the result if result != -1: print(f"Element {target} found at index {result}.") else: print(f"Element {target} not found in the list.") # Calling main to run the program if __name__ == "__main__": main() Time Complexity ...

A complete guide ds Termwork 1 - Infix evaluation Algorithm Create an empty stack (operandStack) to store operands and an empty stack (operatorStack) to store operators. Initialize a variable (result) to store the final output Iterate through each character of the infix expression. If the current character is an operand, add it to the operandStack. If the current character is an operator, pop operators from operatorStack and add them to operandStack until an operator with lower precedence is found. Then push the current operator onto operatorStack. If the current character is an opening parenthesis, push it onto operatorStack If the current character is a closing parenthesis, pop operators from operatorStack and add them to operandStack until an opening parenthesis is found. Repeat steps 3-7 for all characters of the infix expression. Once all characters have been processed, pop any remaining operators from operatorStack and add them to operandStack. Evaluate the final expression in operandStack and return the result. IO 1 2 3 4 5 6 7 8 9 10 11 12 * ➜ programs git:(ds) ✗ gcc tw1.c -lm && ./a.out * Output 1 * Enter the infix expression to evaluate: 5+7-4+3 * 11 * * Output 2 * Enter the infix expression to evaluate: 6+6 * 12 * * Output 3 * Enter the infix expression to evaluate: 4*6^2 * 256 Applications Expression Evaluation: Stacks are commonly used in the evaluation of mathematical expressions, such as infix and postfix expressions. By using a stack, one can easily convert an infix expression to postfix and then evaluate the postfix expression. This is because stacks provide a last-in-first-out (LIFO) data structure, which is well suited for this type of evaluation. Undo/Redo functionality: Stacks can be used to implement undo and redo functionality in applications, such as text editors and image editors. By maintaining a stack of previous states, the application can easily undo and redo actions, by popping and pushing states from the stack. Syntax Checking: Stacks can be used in parsing and syntax checking of programming languages. For example, in a compiler or interpreter, a stack can be used to keep track of the current state of the program being parsed, such as keeping track of matching brackets or keeping track of function calls. This allows for efficient and accurate checking of the syntax of the program, and aids in error handling. Termwork 2 - infix to postfix Algorithm Create an empty stack. Initialize an empty string (result) to store the postfix expression. Iterate through each character of the prefix expression, starting from the rightmost character. If the current character is an operand, append it to the result string. If the current character is an operator, pop the top two elements from the stack and append them to the result string, separated by the current operator. Then, push the current operator onto the stack. Repeat steps 3-5 for all characters of the prefix expression. Once all characters have been processed, pop any remaining operators from the stack and append them to the result string. Reverse the result string and return it as the postfix expression. IO 1 2 3 4 5 6 7 8 9 10 11 12 * ➜ programs git:(ds) ✗ gcc tw2.c && ./a.out * Output 1 * Enter the exp: 4-6+7*7 * 46-77* * * Output 2 * Enter the exp: 7-4+3^5 * 74-35^ * * Output 3 * Enter the exp: 3+5+4 * 35+4+ Applications Same as termwork 1 ...