Data structures and algorithms

Chapter one introduction

1.2 What is a data structure

  • Structure: Entity + relationship

  • Data structure:

    • A collection of data organized according to a logical relationship
    • It’s stored in a certain way on a computer
    • A set of operations is defined on these data

Logical organization of data structures

  • Linear structure
    • Linear tables (tables, stacks, queues, strings, etc.)
  • Nonlinear structure
    • Tree (binary tree, Huffman tree, binary search tree, etc.)
    • Graph (directed graph, undirected graph, etc.)

The storage structure of data

  • Mapping of logical structures to physical storage
  • Computer main memory
    • Non-negative integer address code, set of adjacent cells
      • The basic unit is bytes
      • Access to different addresses takes roughly the same amount of time (i.e. random access)

The storage structure of data structure is mainly composed of four forms: sequence, link, index and hash.

  • Sequential: Sequential addresses of storage units (linearized)

  • Link: Address pointing relation of pointer (nonlinear)

Abstract data type ADT

  • Abstract data structure tuples

< data object D, data operation P>

  • Define the logical structure first, then define the operation
    • Logical structure: Data objects and relationships
    • Computation: Data manipulation

1.3 algorithm

Characteristics of the algorithm

  • generality
    • The parametric input is solved
    • Ensure the correctness of the calculation results
  • effectiveness
    • An algorithm is an instruction queue consisting of a finite number of instructions
    • It consists of a series of concrete steps
  • deterministic
    • The next steps to be performed in the algorithm description must be clear
  • Have a poor sexual
    • The execution of the algorithm must end in a finite number of steps
    • In other words, there are no dead loops allowed in the algorithm

1.4 Algorithm complexity analysis

Asymptotic analysis of the algorithm

  • When the data scale n gradually increases:

    F (n)

  • When n increases to a certain value, in the calculation formula, the most important is the highest power term of n – other constant terms and lower power terms can be ignored

Big O notation

  • Functions f and g have a domain of natural numbers and a range of non-negative real numbers
  • Definition: If there are positive numbers C and n0 such that f(n)< C · g(n) for any n>n0, f(n) is said to be in the set O(g(n)), and f(n) is O(g(n))
  • Big O notation: Represents the upper bound on the function’s growth rate.
    • There cannot be only one upper limit on the growth rate of a function.

Growth rate curve