Data structure and algorithm
1. Basic knowledge
1. Relationship between data
Logical structure: it refers to the relationship between data elements, which is imagined by us and is not substantially stored in the computer.
Linear structure: there is a one-to-one relationship between data elements in a linear structure
Tree structure: there is a one to many hierarchical relationship between data elements in the tree structure
Graphic structure: the data elements of the graphic structure are many to many relationships
Physical structure: refers to the specific storage form of the logical structure of data in the computer
Sequential storage structure: open up a group of continuous space to store data, which is usually realized by array. The space in the array itself is continuous, which ensures the relationship between data
Chain storage structure: open up a group of random space to store data, which is usually realized by nodes. Nodes should not only store data, but also store the location of the next node to ensure the relationship between data
2. Algorithm overview
What is an algorithm:
It is a description of the solution steps to solve a specific problem, analyze the problem, and solve the problem. These steps are algorithms
(1. Natural language description, 2. Flow chart description, 3. Pseudo code description, 4. Code description)
The quality of the algorithm
1. Post hoc statistical method:
This method is mainly through the designed program and data, using the computer timer to wake up and compare the running time of different algorithm programs, so as to determine the efficiency of the algorithm.
Disadvantages:
The program must be written in advance. If the data processed by the program is large, it will spend a lot of time and energy. The comparison of time mainly depends on the computer hardware function and software environment. When testing the algorithm, if the amount of data is small, the difference is almost zero, and the amount of data is large, the advantages of the algorithm will be shown, but it will take time. For programming language, it is only a tool to implement the algorithm, which has no impact on the algorithm itself.
2. Prior analysis
This method mainly estimates the algorithm according to statistical methods before computer programming. The time consumed when a program written in a high-level programming language runs on the computer depends on the following factors:
The strategy and method adopted by the algorithm (the basis of easy algorithm exchange) the code quality generated by compilation (depending on the specific programming language) the input scale of the problem, the speed of machine execution instructions (hardware performance)
The running time of a program depends on the quality of the algorithm and the input scale of the problem. The so-called problem input scale refers to the amount of data input
Time complexity of the algorithm
In short, the growth rate of algorithm execution time is the same as that of f(n), which is called the progressive time complexity of the algorithm.
1. Constant order O(1)
No loop, no recursion, line by line code independent of the problem input scale N.
2. Linear order (O(n))
Related to the problem input scale, it is mainly a layer of circular code, and there may be recursion
3. Linear order (O(n+m))
Like linear order O(n), there are only two data input scales
4. Square order O(n^2)
Related to the problem input scale, it is mainly the code of two-level nested loops
5. Logarithmic order
Related to the input scale of the problem, it is mainly a layer of cyclic iterative or recursive code
Comparison of common orders
For the simple calculation method of time complexity: ignore the constant term, only retain the power height term, and ignore the coefficient of the highest term; Note: when the time complexity of an algorithm exceeds O(n^2), the algorithm is not desirable
2. Linear table of data structure
Linear table is a linear structure, which is a finite sequence composed of zero or more data elements. The characteristic of linear table is that in a sequence, except for the head and tail elements, each element has and has only one direct precursor and only one direct successor, while the sequence head element has no direct precursor and the sequence tail element has no direct successor.
Insert operation of linear table
@Override
public void add(E element) {
add(size,element);
}
@Override
public void add(int index, E element) {
if (index<0||index>size){
throw new IllegalArgumentException("add out");
}
//Judge whether the table is full
if (size==data.length){
resize(2 * data.length);
}
//Move element
for(int i=size-1;i>=index;i--){
data[i+1]=data[i];
}
//Insert the new element at the specified location
data[index]=element;
size++;
}
Delete linear table
public void remove(E element) {
int index = indexOf(element);
if (index!=-1){
remove(index);
}
}
@Override
public E remove(int index) {
if (index<0||index>=size){
throw new IllegalArgumentException("index out");
}
//Save the value to be deleted first
E ret =data[index];
//Move element
for (int i= index+1;i<size;i++){
data[i-1]=data[i];
}
size--;
//When to shrink
//1. The effective element is 1 / 4 of the capacity
//2. The current capacity shall not be less than the default capacity
if (size == data.length/4&&data.length>DEFAULT_CAPACITY){
resize(data.length/2);
}
return ret;
}
Gets the specified element of the linear table
public E get(int index) {
if (index<0||index>=size){
throw new IllegalArgumentException("get index out");
}
return data[index];
}
Modify the specified element of the linear table
public E set(int index, E element) {
if (index<0||index>=size){
throw new IllegalArgumentException("set index out");
}
E ret =data[index];
data[index]=element;
return ret;
}
Sorting of elements in linear tables (using insert sort)
public void sort(Comparator<E> c) {
if (c==null){
throw new IllegalArgumentException("COMPARATOR NULL");
}
for (int i = 1 ; i < size ; i++){
E e =data[i];
int j =0;
for( j = i ; j > 0&&c.compare(data[j-1],e)>0; j--){
data[j]=data[j-1];
}
data[j]=e;
}
}
Intercept a segment of a linear table
public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex<0||toIndex>=size||fromIndex >toIndex){
throw new IllegalArgumentException("error");
}
ArrayList<E> List =new ArrayList<>();
for(int i =fromIndex;i<=toIndex;i++){
List.add(data[i]);
}
return List;
}
3. Stack of data structure
Linear table is a linear structure, which is a finite sequence composed of zero or more data elements. The characteristic of linear table is that in a sequence, except for the head and tail elements, each element has and has only one direct precursor and only one direct successor, while the sequence head element has no direct precursor and the sequence tail element has no direct successor.
Stack method and implementation method of directly calling linear table
@Override
public int size() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E element) {
list.add(element);
}
@Override
public E pop() {
return list.remove(list.size()-1);
}
@Override
public E peek() {
return list.get(list.size()-1);
}
@Override
public void clear() {
list.clear();
}
@Override
public Iterator<E> iterator() {
return list.iterator();
}
Calculation of infix expression
Scan from left to right. If the operator priority scanned is greater than the operator priority at the top of the stack, it will be put into the stack. Otherwise, it will be out of the stack and operated.
If you encounter a right parenthesis, keep going out of the stack until you encounter an left parenthesis. And every time the operator out of the stack has to do an operation.
After scanning the whole expression, if there are still operators left in S2 stack, all of them will be out of the stack and calculated one by one.
public class InfixCalculator {
public static void main(String[] args) {
String s ="(10+20/2*3)/2+8";
System.out.println(s);
int res = evaluateString(s);
System.out.println(res);
}
private static int evaluateString(String s){
s= insertBlanks(s);
String[] tokens = s.split(" ");
ArrayStack<Character> operatorStack =new ArrayStack<>();
ArrayStack<Integer> numberStack =new ArrayStack<>();
for (String token: tokens) {
if(token.length()==0){ //Filter empty string
continue;
//Traverse to plus minus sign
}else if (token.equals("+")||token.equals("-")){
while (!operatorStack.isEmpty()&&(operatorStack.peek() == '+'|| operatorStack.peek() == '-'||operatorStack.peek() == '*'||operatorStack.peek()=='/')){
//The previous is + - * / it needs spring stack calculation
processAnOperator(numberStack,operatorStack);
}
//If the operator stack is empty or not, but the top of the stack is(
operatorStack.push((token.charAt(0)));
}else if (token.equals("*")||token.equals("/")){ //Traversal to multiplication and division
while (!operatorStack.isEmpty()&&(operatorStack.peek() == '*'||operatorStack.peek()=='/')){
processAnOperator(numberStack,operatorStack);
}
operatorStack.push((token.charAt(0)));
}else if (token.equals("(")){
operatorStack.push((token.charAt(0)));
}else if (token.equals(")")){
//As long as the top of the operator stack is not (calculated one by one)
while (operatorStack.peek()!='('){
processAnOperator(numberStack,operatorStack);
}
operatorStack.pop();
}else {
numberStack.push(new Integer(token));
}
}
while (!operatorStack.isEmpty()){
processAnOperator(numberStack,operatorStack);
}
return numberStack.pop();
}
private static void processAnOperator(ArrayStack<Integer>numStack,ArrayStack<Character>operatorStack){
char op=operatorStack.pop();
int num1 =numStack.pop();
int num2 =numStack.pop();
if (op == '-') {
numStack.push(num2-num1);
}else if (op=='+'){
numStack.push(num2+num1);
}else if (op =='*'){
numStack.push(num2*num1);
}else if(op=='/'){
numStack.push(num2/num1);
}
}
//Add spaces around all non numeric symbols
public static String insertBlanks(String S){
StringBuilder sb = new StringBuilder();
for(int i =0;i< S.length();i++){
char c = S.charAt(i);
if (c =='/'||c=='*'||c=='('||c==')'||c=='-'||c=='+'){
sb.append(' ');
sb.append(c);
sb.append(' ');
}else {
sb.append(c);
}
}
return sb.toString();
}