directory

  • Knowledge framework

  • Exam outline content

  • Basic concepts of data structures

  • Three elements of a data structure

【 Knowledge framework 】

【考 题 目 】

  • Data structure-related concepts and terminology
  • Data structure has three elements: logical structure, physical structure and data operation
  • Analysis of time complexity and space complexity of algorithm

1. Basic concepts of data structure

1.1 Basic Concepts and terminology

  • data

    Data is the carrier of information. It is the set of numbers, characters and symbols that can be input into the computer and recognized and processed by the computer program to describe the attributes of objective things. Data is the raw material of computer programs.

  • The data element

    A data element is a basic unit of data and is usually considered and processed as a whole. A data element can be composed of several data items, which are the smallest indivisible units of data elements.

  • The data object

    A data object is a collection of data elements with the same properties, and is a subset of data. For example, integer data objects are sets N={0, ±1, ±2… }.

  • The data type

    A data type is an umbrella term for a set of values and a set of operations defined on that set.

    (1) Atomic type

    A data type whose value is non-divisible.

    Set of values + operations (int,char,doubleExamples:intSet of type values and set of operations:- 2147483648.~2147483647Operations: +, -, *, /, %, etcCopy the code

    (2) Structure type

    Its value can be further decomposed into a number of component (component) data types.

    Set of structures + operations (list, set, etc.)Copy the code

    (3) Abstract Data Type (ADT)

    Abstract data organization and operations associated with it.

    Data objects + data relationships + operationsCopy the code

  • The data structure

    A data structure is a collection of data elements that have one or more specific relationships with each other. In any problem, data elements do not exist in isolation, but there is a certain relationship between them, which is called a Structure. Data structure includes three aspects: logical structure, storage structure and data operation. The logical structure and storage structure of data are two inseparable aspects. The design of an algorithm depends on the selected logical structure, and the timing of the algorithm depends on the storage structure adopted.

Two, data structure three elements

1. Logical structure of data

Logical structure is the logical relationship between data elements, that is, to describe data from the logical relationship. It has nothing to do with data storage and is independent of the computer. The logical structure of data can be divided into linear structure and nonlinear structure. The linear table is a typical linear structure. Sets, trees and graphs are typical nonlinear structures. The logical structure classification of data is shown in the figure below:

Collection. There is no relationship between data elements in a structure except that they belong to the same set

Linear structure. There is only a one-to-one relationship between data elements in a structure

Tree structure. Only one-to-many relationships exist between data elements in a structure

Graph structure or network structure. There is a many-to-many relationship between data elements in a structure

2. Data storage structure

A storage structure is a computer representation (also known as an image) of data results, also known as a physical structure. It contains representations of data elements and representations of relationships. The storage structure of data is a logical structure implemented by computer language, which depends on computer language.

The storage structure of data mainly includes sequential storage, chain storage, index storage and hash storage.

  • Sequential storage

    The logical relationship between elements is represented by a pointer indicating where the elements are stored without requiring the elements to be physically adjacent.

    Advantages: Random access, minimum storage space per element. Disadvantages: Only one contiguous storage unit can be used, which may cause more external fragmentation.

  • Chain store

    The logical relationship between elements is represented by a pointer indicating where the elements are stored without requiring the elements to be physically adjacent.

    Advantages: No fragmentation phenomenon, can make full use of all storage units

    Disadvantages: Each element takes up extra storage space by storing Pointers, and can only be stored sequentially

  • Indexes are stored

    As information is stored, additional index tables are created. Each item in an index table is called an index item, and the general form of an index item is (keyword, address).

    Advantages: Fast retrieval speed.

    Disadvantages: Additional index tables take up extra storage space. In addition, index tables are modified as data is added and deleted, which takes more time.

  • Hash storage (hash storage)

    Calculates the storage address of the element directly based on its keyword.

    Advantages: Retrieving, adding, and deleting nodes are fast.

    Disadvantages: If the hash function is not good, conflicts of element storage units can occur, and resolving conflicts can add time and space overhead.

3. Operation of data

Operations imposed on data include the definition and implementation of operations. The definition of operation is for logical structure, pointing out the function of operation, operation is for storage structure, pointing out the specific operation steps of operation.