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)
  • Linked Storage Structure
    • Single linked list
    • Static linked list
    • Circular linked list
    • Bidirectional circular linked list
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

Sequential table lookup

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
    

Binary sort tree

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

Multiple lookup tree (B-tree)

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:
	1.direct addressing 
	2.Digital analysis
	3.Square middle method
	4.Folding method
	5.Division method 
	6.Random number method

How to handle hash conflicts:
	1.Open addressing 
		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
	3.Chain address 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

Efficiency comparison of sorting methods

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.

Tags: data structure linked list

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