Calculations and operations on data objects

The control structure of the algorithm (the order of execution between operations)

scale of problem

The status of the data to be processed

The space occupied by the algorithm program

The storage space occupied by the input initial data

Additional space required during each process of algorithm execution

Reflect the logical relationship between data elements

The storage form of the logical structure of data in computer storage space

sequential storage

Index storage

Hash storage

chain storage

data

data element

data object

logical structure of data

The stack is a special linear table. Insertion and deletion operations are performed on a section of the linear table, first in, last out, last in, first out.

Top of stack: a section that allows insertion and deletion

Bottom of the stack: the other end of the stack

Empty stack: a stack with no elements in the stack

The top element of the stack is the first element to be inserted and the last element to be deleted.

The stack has a memory function

Under the sequential storage structure, insertion and deletion operations on the stack do not require moving other data elements in the table.

The top pointer on the stack dynamically reflects the changes in the elements in the stack

Sequential storage and operations

Tail of the queue: the end that allows insertion

Heading: the end that allows deletion

Enqueue operation

Exit operation

Store data element value

Store pointers (pointers are used to point to migrations or afterware)

Nonlinear structure, limited node set

Can be empty. An empty binary tree has no nodes. A non-empty binary tree has one and only one root node.

Each node can have up to two subtrees, a left subtree and a right subtree.

In the traversal of a binary tree, whether it is pre-order traversal, in-order traversal or post-order traversal, the leaf nodes of the binary tree take priority.

There are at most 2k-1 nodes on the kth level of the binary tree

A binary tree of depth m has at most 2m-1 nodes.

For any binary tree, there is always one more node (leaf node) with degree 0 than node with degree 2.

A complete binary tree with n nodes has a depth of at least [log2n] (integer part) 1

full binary tree

complete binary tree

Preorder traversal

inorder traversal

Postorder traversal

A linear list is an unordered list

Linked stored ordered list

The worst case number of comparisons is n(n-1)/2 times

Average execution time o(n2)

o(nlog2n)

Take any element in the sequence to be sorted as the basis

Divided into two subsequences, left and right

The sorting code of the left subsequence is ≤ the sorting code of the reference element

The sorting code of the right subsequence is ≥ the sorting code of the base element

Then sort until the entire sequence is in order