# data structure

## Introduction

A brief history of the future: Dataism

Problem solving: What Why How a feasible method based on the finite point of view

Turing machine calculation model

## Algorithm and computational complexity

Computable problem: the difficulty of the algorithm

Non computable problem: boundary or limit

Breaking the limit: SETI@home , photon computing and smart crowdsourcing research projects

Algorithm analysis: computing resource consumption, what is computing resource? Storage space or memory, execution time.

## Algorithm time metrics

The size of the problem affects the execution time of the algorithm

Large O representation of order of magnitude function O(n)

Example: T(n) = 5n^2 + 27n +1005 O(n^2)

Other factors: best worst average

Common large order function O(1) log(n) O(n) n*log(n) n^2 n^3 2^n

### The problem of "modified words"

abcd dcba

- Compare o one by one (n ^ 2)
- Sort comparison O(nlogn)
- Violence is exhausted....
- Count comparison count the number of times each letter appears, and finally compare O(n) space and time

## Performance of Python data types

Make the most commonly used operation performance the best

It's better not to pop(0). It has to move all the data back one bit. The time complexity is very high

## Linear structure

Linear structure is a set of ordered data items, in which each data item must have a unique precursor and successor.

Different ways of increasing or decreasing data items constitute different data structures

### Stack stack

An ordered collection of data items. In the stack, the addition and removal of data items only occur at the same end. This end is called the top of the stack and the other end is called the base of the stack.

Stack characteristics: reverse order

operation

# ADT.py """ We should master our thoughts Stack and queue """ # Stack: first in and last out data structure, stack top and stack tail. Randomly select one end of the list to set the top or bottom of the stack. Here, the last element is selected as the top of the stack. This performance will be better. # Implementation with list: we define that the starting position of the list is the bottom of the stack and the end is the top of the stack. # Stack() creates an empty stack. It does not require parameters and returns an empty stack. # push() class Stack(object): def __init__(self): self.items = [] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): """Returns the top item from the stack, but does not delete it. No parameters are required and the stack is not modified.""" return len(self.items) - 1 def isEmpty(self): return self.items == [] def size(self): return len(self.items) if __name__ == '__main__': stack = Stack() stack.push(1) stack.push(2) stack.push(3) print('Stack top element subscript',stack.peek()) print(stack.isEmpty()) print(f'Number of elements{stack.size()}')

Application of stack: simple bracket matching

Brackets must match correctly,

Each open bracket "(" must correspond to a closed bracket ")";

Nest correctly.

# Import stack package from ADT import Stack def is_kuohao(s): # Create an empty stack stack = Stack() for i in s: if i == '(': # If it is an open bracket, put it on the stack stack.push(i) else: # If it is a right parenthesis, an left parenthesis will be displayed on the stack, and they will be a pair if stack.isEmpty(): # If the stack is empty at this time, it will directly return False because it can no longer match return False # The stack is not empty stack.pop() return stack.isEmpty() s = input() print(is_kuohao(s))

Application of stack: mixed bracket matching

""" Mixed presence of parentheses """ # Import stack package from ADT import Stack def match(a, b): opens = '{[(' closes = '}])' return opens.index(a)==closes.index(b) def par_check(s): # Create an empty stack stack = Stack() for i in s: if i in '({[': # If it is an open bracket, put it on the stack stack.push(i) else: # If it is a right parenthesis, a left parenthesis will be displayed on the stack, and whether they are a pair will be detected if stack.isEmpty(): # If the stack is empty at this time, it will directly return False because it can no longer match return False # Stack only when it is not empty if not match(stack.pop(), i): return False return stack.isEmpty() s = input() print(par_check(s))

Application of stack: binary conversion

""" Given a decimal number, convert it into k Base system except k Remainder method """ from ADT import Stack def digit(base, k): arr = '0123456789ABCDEF' res = '' stack = Stack() while base != 0: stack.push(arr[base % k]) base = base // k while not stack.isEmpty(): res += stack.pop() return int(res) print(digit(100, 16)) # 64 print(int('64', 16)) # 100

Application of stack: expression

Infix expression: the operator is in the middle, such as A+B. If there are other operators, the priority should be considered. The priority is artificially specified.

For example, in order to make the expression of a + B stronger, you only need to add parentheses to make the expression of a + B stronger.

For example, (A + (B*C)), that is, full parenthesis expression.

Prefix expression: in order to facilitate the representation of priority, put the operator in front of the operand.

Suffix expression: in order to facilitate the representation of priority, put the operator after the operand.

Infix expression | Prefix expression | Postfix Expression |
---|---|---|

A+B*C | +A*BC | ABC*+ |

Prefixes and suffixes can omit parentheses. The first operation closest to the operator. Suffix expressions are usually used in computers.

Infix expression converts bit prefix expression or suffix expression

(A+(B*C))

Look at the right parenthesis of the subexpression (B*C). Replace the operator with a right parenthesis, and then delete the left parenthesis to get the suffix expression.