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.