# Big talk data structure - Summary

## Big talk data structure - Summary

Read the book "Dahua data structure" and summarize some things; The summary is rough. Some ideas can't be understood for the time being. Put them aside first, and then go back to digest these knowledge points after learning other things

### 1. Data structure

A data structure is a collection of data elements that have one or more specific relationships with each other

#### Logical structure of data

```1.Set structure
Belonging to the same set, the elements are equal
2.linear structure
Element one to one
3.Tree structure
One to many hierarchical relationship of elements
4.Graphic structure
Element many to many
```

#### Physical structure of data

```1.Sequential storage
Elements are stored in storage units with continuous addresses, and the logical relationship of data is consistent with the physical relationship
2.Chain structure
Store the data in any storage unit of the task, and the address can be even discontinuous; Find the associated data location through the pointer
```

### 2. Time algorithm complexity

#### Derivation method

```1.Replace all addition constants in time with constant 1
2.In the modified sub function, only the highest order is retained
3.If the highest order exists and is not 1, remove the constant multiplied by this term and the result is large O rank
```
• Constant order O(1)
```int sum = 0,n=100; //Execute once
sum = sum+n; //Execute once
System.out.printf(sum); //Execute once

O(1)
```
• Linear order O(n)
• Logarithmic order Ologn
• Square order O(n) ²)

### 3. Linear table

• Sequential storage structure
```Continuous storage location, slow insertion and fast search(Subscript lookup)
```
```Search is slow, insert and delete blocks; Space for time
```

### 4. Stack and queue

• Stack
```A stack is a linear table that restricts insertion and deletion operations only at the end of the queue
Function: recursion
Application: evaluation of four operation expressions(Postfix Expression )
```
• queue
```A queue is a linear table that only allows insertion at one end and deletion at the other
```

### 5. String

String is a finite sequence of 0 or more characters, also known as string

• KMP matching algorithm

### 6. Tree

• depth
```The maximum level of nodes in a tree is called the depth or height of the tree
```
• Representation method
```Parent representation, child representation, child brother representation
```
• Binary tree
```1.Each node has at most two subtrees, and there are no nodes with a degree greater than 2 in the binary tree
2.The number of left and right words is in order and cannot be reversed
3.If there is only one subtree, you should also distinguish whether it is a left subtree or a right subtree

Five basic forms
1.Empty binary tree
2.There is only one root node
3.The root node has only the left subtree
4.The root node has only the right subtree
5.The root node has both left and right subtrees
```
• Special binary tree
```1.Oblique tree
2.Full binary tree(The number of left and right nodes is exactly the same)
3.Complete binary tree(On a certain layer, the number of left and right nodes is equal)
```
• Binary tree traversal method
```1.Preamble
Starting from the root node, traverse from left to right
2.Middle order
Starting from the leftmost node, traverse the root node first, and then the right node
3.Post order
Start from the leftmost node, first traverse the right node, and finally traverse the root node
4.level traversal
Start from the root node and traverse layer by layer from left to right
```

• Application of tree

```huffman tree
Weighted path length WPL The smallest binary tree is called Huffman tree
Huffman coding-compress
```

### 7. Figure Graph

A graph is composed of a set of edges between vertices of a finite non empty set of vertices, which is usually expressed as: G(V,E), where G is a graph, V is the marriage of vertices in graph G, and E is the set of edges in graph G

#### Some definitions in the figure

• The data elements in the graph are called vertices

• No vertices are allowed in a graph structure

• There may be a relationship between any two vertices in the graph. The logical relationship between vertices is represented by edges, and the edge set can be empty

• Definition of edge

```Undirected edge
Directed edge
```

### 8. Search

#### Ordered table lookup

• Half search
• Interpolation search
• fibonacci search

#### Linear index lookup

• Dense index

```Dense index means that in linear index, each record in the data set corresponds to an index item; Example: Notepad
```
• Block index

```Disorder within blocks and order between blocks; Ways of storing books in reference libraries and Archives
```
• Inverted index

```Common structure of index entries:
Secondary key
Record number table
```

#### Balanced binary tree (AVL tree)

```Construction thought: Whenever a node is inserted, first check whether the balance of the tree is damaged due to the insertion. If so, find out the minimum unbalanced subtree. On the premise of maintaining the characteristics of binary sort tree, adjust the link relationship between the nodes of the minimum unbalanced subtree and rotate it accordingly to make it a new balanced subtree
```

#### Hash table lookup

```The most suitable solution of hash technology is to find records equal to the given value; However, the maximum value, minimum value and other results cannot be found
Construction method of hash function:
2.Digital analysis
3.Square middle method
4.Folding method
5.Division method
6.Random number method

How to handle hash conflicts:
The open addressing method for conflict resolution is called linear detection method
The situation that is not a synonym but needs to compete for the same address is called accumulation
To prevent keywords from piling up in one area. Secondary detection method is adopted/Recalculate address by random detection method
2.Hashing function method
4.Public spillover area act
```

### 9. Sort

#### Sorting and classification

```According to whether all the records to be sorted are placed in memory during sorting, sorting is divided into:Inner sort and outer sort
Inner sorting: Internal sorting is that all records to be sorted are placed in memory in the whole process of sorting.
External sorting: Because there are too many records to be sorted, they cannot be placed in memory at the same time. The whole sorting process always needs to exchange data between internal and external memory for many times
Internal sorting performance impact points:
1.Time performance
2.Auxiliary space
3.Complexity of algorithm
Internal sorting is divided into: Insert sort, swap sort, select sort and merge sort
```

#### Sort type

```Bubble sort, simple selection sort, direct insertion sort, Hill sort, heap sort, merge sort, quick sort
```
• Quick sort!!!
• Random fast scheduling
• Two way fast platoon
• Three way fast platoon

### complimentary close

• Nothing is impossible. Don't be limited by rules
• If you have a dream, defend it. When others can't do it, they want to tell you, and you can't. If you want something. Just try to fight for it.

Posted by redrabbit on Sat, 21 May 2022 01:17:44 +0300