Features
Features:

Product Tour >

Edraw AI >

Paid Plans:

Individuals >

Business >

Eduaction >
Resources
Blog

History

How-tos & Tips

Discovery

Biography

Business Analysis

Examples

AI concept Map

Free AI Mind Map Generator

Onenote Mind Map

Bcg Matrix Examples

Nike Marketing Strategy

Unilever SWOT Analysis

Make Mind Maps in Google Docs

Guide

FAQs

What's New

Resource Center
Templates
All Templates

Brain Storming Templates

Strategy and Planning Templates

Project Management Templates

Product Management Templates

Human Resources Templates

Agile Workflow Templates

Marketing Templates

Education Templates

Fun and Games Templates

User Gallery
Download
Pricing
Enterprise

MindMap Gallery Data structure mind map

Data structure mind map

This is a mind map about data structure. Physical symbols stored on a certain medium that can be recognized are carriers of information. These symbols can be numbers, symbols, etc. or others,

Edited at 2023-12-02 14:20:48

PlotWizard

Recent works View more works>>

Data structure mind map

PlotWizard

Recent works View more works>>

Recommended to you
Outline

data structure

introduction

data

definition

Physical symbols stored on a certain medium that can be recognized are the carriers of information. These symbols can be numbers, symbols, or other

constitute:

data

data element

data item

The smallest unit that makes up data

basic unit of data

logical structure

Relationships between data elements

Set structure

Belong to the same collection

linear structure

One to one

Linear list, heap, stack

tree structure

one to many

graph structure

many to many

storage structure

sequential storage structure

chain storage structure

Index storage structure

Hash storage structure

algorithm

definition

A description of specific steps to solve a particular problem, a finite sequence of instructions

five basic properties

Finiteness

Must end after executing a limited number of steps

certainty

feasibility

Any computational step can be broken down into basic executable operational steps, each step can be completed within a limited time

enter

An algorithm can have 0 or more inputs

output

An algorithm has 1 or more outputs

General rules of design

correctness

readability

Robustness

Respond appropriately to incorrect input

High efficiency and low storage volume

the complexity

linear structure

linear table

time complexity

Sequence table search by value

n 1/2

Sequence table insertion

O(n)

delete

O(n)

stack

last in first out

definition

top of stack

Operation terminal

bottom of stack

Fixed end

sequence stack

top=-1 is an empty stack

top=MAXSIZE-1 means full stack

stack chain storage

Similar to singly linked list

queue

first in first out

definition

tail of the queue

Allow insertion

Team leader

Allow deletion

sequential queue

circular queue

Leave a space unused

The sentence is full

(rear 1)%MAXQUEUE==front

front==rear

Call it short

linked list

Single linked list without head node

Operations involving the head node require special handling

Singly linked list with head node

Head pointer is not null

Circular singly linked list

The pointer field of the last node stores the address of the first node, forming a ring.

The abort operation in the operation determines whether it is the head pointer

Doubly linked list

There are predecessors and successors

array

Calculation of storage address

Base address (i 1)*n (j-1)

Find method

sequential search

Traverse

Average search length=n 1/2

Index lookup

Create index entry

Keyword items

Block

pointer item

Average search length = (n/s s)/2 1

n is the table length, evenly divided into b blocks, each block contains s records

Hash lookup

Hash function construction method

direct hash function

Take the keyword itself or a linear function of the keyword as the address

Address set size == keyword set size

Numerical Analysis Hash Function

Find the center of the square

folding method

shift fold

border collapse

Except for the remainder

H=key mod p

Take prime number

random number method

Hash lookup performance analysis

factor

Hash function

Basically don’t consider it

Conflict handling methods

open address law

Linear probing and then hashing

1, 2, 3,. . postpone

(1 1/1-α )/2

Second detection and then hashing

Positive and negative number squared lag

ln(1-α)/α

Pseudo-random probing and then hashing

pseudorandom sequence

ln(1-α)/α

rehash

ln(1-α)/α

chain address method

Conflicting records are stored in the same linear linked list

1 α/2

public overflow area

Let another vector be the overflow table

Hash table fill factor

α=number of records filled in the table/hash table length

The average search length of a hash table is a function of α, not a function of n

Prerequisite: data is loaded evenly

sort

stable sorting

The relative position of keyword data remains unchanged before and after sorting

insert directly

Divided into two parts, the left side is ordered and the right side is unordered. The first element on the right side enters the appropriate position on the left side.

O (square)

Stablize

Hill sort

According to a fixed interval, d is divided into the same group, and insertion or binary sorting is used within the same group.

Completed for the first time, reduce the interval to group, and then sort

until the interval is 1

unstable

Bubble Sort

Compare n-i 1 items in sequence from left to right

Stablize

square/2

Simple choice

Take the maximum value from the unordered sequence and add it to the end of the ordered sequence

square

Stablize

Radix sort

Multiple keyword sorting

Multiple keyword ordering

high priority

Little endian

Quick sort

Divide the sequence into two parts (required to ensure relative size relationship)

Recurse into two subsequences for quick sorting

No need to merge, because the array is completely ordered at this time

nlogn

But when the sequence itself is ordered, it degenerates into square

merge sort

Divide the sequence to be sorted into several subsequences, and each subsequence is an ordered sequence. Then merge the ordered subsequences into the overall ordered sequence

A tree is a finite set of n (n>=0) nodes. When n=0, it is called an empty tree. In any non-empty tree, there is only one specific node called the root. When n>1, the remaining nodes can be divided into m (m>0) disjoint finite sets, each of which is itself a tree and is called the subtree of the root (SubTree).

Trees have the following properties:

1. The subtrees are disjoint.

2. Except for the root node, each node has only one parent node.

3. A tree with N nodes has N-1 edges.

The degree of a tree refers to the maximum degree among all nodes in the tree, and the leaf node refers to the node with degree 0. The depth of a tree refers to the largest level among all nodes in the tree. There are at most 2^(i-1) nodes (i≥1) on the i-th level of the binary tree, and the binary tree with depth k has at most 2^k-1 nodes (k≥1).

Recursion and divide and conquer

recursion

definition

Call itself directly or indirectly

scenes to be used

The definition is recursive

Factorial of n, Fibonacci sequence

Data structures are recursive

linked list

divide and conquer

scenes to be used

Small scale, easy to solve

The problem can be decomposed into sub-problems of the same type, with optimal substructure

The solution to the original problem can be obtained by merging sub-problems

sub-problems are independent

Algorithm time complexity

Iterative method

Expand directly

recursive tree method

main method

Tree

Binary tree

concept

Spend

The number of subtrees owned by the node

leaf

node with degree 0

child

The root of the node subtree

parents

The upper node of the child node

ancestor

All nodes on the branches from the root node to this node

Node level

Starting from the root node, the root is the first level

degree of binary tree

Maximum node degree

Binary tree depth

The maximum number of layers of nodes

special

full binary tree

All branch nodes have left subtree and right subtree

All leaves and all leaf nodes are on the same layer

complete binary tree

A binary tree in which every level except the last level is completely filled. The nodes of the last layer are continuously concentrated on the left.

A full binary tree must be a complete binary tree, and a complete binary tree may not be a full binary tree.

nature

1. In a non-empty binary tree, the total number of nodes at level i does not exceed i>=1.

2. A binary tree with depth h has at most 2^h - 1 nodes (h>=1) and at least h nodes.

3. For any binary tree, if the number of leaf nodes is N0 and the total number of nodes with degree 2 is N2, then N0=N2 1.

4. The depth of a complete binary tree with n nodes is logn 1

Traverse

Binary tree traversal refers to visiting each node of the binary tree according to certain rules, so that each node is visited and only visited once. There are three main ways to traverse a binary tree: pre-order traversal, in-order traversal and post-order traversal.

1. Preorder Traversal:

* Access the root node

* Preorder traversal of the left subtree

* Preorder traverse the right subtree

2. Inorder Traversal:

* In-order traversal of the left subtree

* Access the root node

* In-order traverse the right subtree

3. Postorder Traversal:

* Post-order traversal of the left subtree

* Post-order traversal of the right subtree

* Access the root node

Traverse the application

Build a binary tree from pre-order traversal and in-order traversal sequences

Preorder and postorder cannot build a binary tree

Find the depth of a binary tree

The following is a pseudocode example that uses recursion to find the depth of a binary tree:

```

function treeDepth(root):

if root is null:

return 0

else:

leftDepth = treeDepth(root.left)

rightDepth = treeDepth(root.right)

return max(leftDepth, rightDepth) 1

```

In this pseudocode, `root` represents the root node of the binary tree. If the root node is empty, the returned depth is 0; otherwise, the depth of the left subtree and the right subtree is recursively calculated, the larger of the two plus 1 is taken as the depth of the current subtree, and the maximum depth is returned as the result.

Binary sorting tree

insert

balanced binary tree

The difference in depth between the left and right subtrees of each node does not exceed 1

Convert binary sorted tree to balanced binary tree

Left single rotation RR

Insert a node into the right subtree of the node's right child

Right single rotation LL

Insert a node into the left subtree of the node's left child

Rotate LR in both directions, first left and then right

Insert a node into the right subtree of the node's left child

Rotate RL in both directions, first right and then left

Insert a node into the left subtree of the node's right child

Optimal binary tree (Huffman tree)

Binary tree with the shortest weighted path length

Huffman tree construction

Select the smallest combination of weights from the root node to generate a new root.

Huffman coding

Left 0 Right 1

tree to binary tree conversion

Add line

Brother nodes are connected by lines

Go online

Keep the connection between the parents and the leftmost child, and remove the others

heap

1. Max heap: A heap in which each node is greater than or equal to its child nodes is called a max heap.

2. Minimum heap: A heap in which each node is less than or equal to its child nodes is called a minimum heap.

Heap insertion

picture

complete graph

For a directed graph with n vertices

Number of edges n(n-1)

Directed complete graph

Number of edges n(n-1)/2

undirected complete graph

basic concept

Spend

degree

out degree

Number of sides == sum of degrees/2

path

simple path

Pass any vertex no more than once

The length of a path is the number of edges it contains

ring (loop)

connected graph

Strongly connected graph

There is a path between any two vertices in a directed graph

Strongly connected component

sequential storage structure

adjacency matrix

correlation matrix

chain storage structure

adjacency list

inverse adjacency list

cross linked list

tialvex

Headvex

Hlink

Tlink

adjacency multiple list

Undirected graph

Ivertex

Ilink

Jvertex

Jlink

Traverse

depth first

breadth first

spanning tree

Features

A complete graph with n vertices has n (n-2) different spanning trees.

minimum spanning tree

Prim's algorithm

Choose a side

Choose the smallest new edge for the known connected components

Kruskal's algorithm

Select edges based on edge weights

If a certain edge forms a loop, discard it

greedy algorithm

weighted shortest path

Dijkstra's algorithm

Divided into two point sets

The shortest path has been found

Undetermined

topological sort

There must be no loop

Critical Path

The earliest start time of the point on the path == the latest start time

dynamic programming