I understand it

Read a lot about the data structure of the explanation, still in the fog; After studying for a period of time, I probably have some understanding of my own

There are some basic data types in every computer language, such as the front end: String, Number, Boolen… And data structures include arrays, stacks, linked lists, hash tables, trees, graphs, etc.

We can see that the components of these data structures are actually primitive data types; Therefore, it can be understood as follows: data structure is the combination structure of basic data types. The purpose of data structure is to abstract the information in the real world and establish an appropriate structure according to its characteristics, which is convenient for computer processing and calculation.

For example: for one-to-one relationship, we take linear model, a bunch of many, many-to-many relationship respectively take tree model, graph model. And then according to the specific characteristics of the information further divided.

Data structure – Logical structure, storage structure

Logical structure

Logical structure is divided into four types: set structure, linear structure, tree structure, graph structure

  1. Collection structure: Data elements belong to the same collection. There is no relationship between individual data elements.

  1. Linear structure: There is a one-to-one relationship between data elements in a linear structure.

  1. Tree structure: Elements in a tree have a one-to-many relationship.

  1. Graphic structure: Elements in a graphic structure are many-to-many relationships.

Storage structure (physical structure)

Common storage structure is divided into: sequential storage structure, chain storage structure, hash storage structure, index storage structure

  • Sequential structures and link structures apply to memory structures.
  • Index structure and hash structure are suitable for external memory and memory interaction structure.

  1. Sequential storage structure: In a computer, the sequential storage structure of a linear table is used to store the data elements of a linear table in sequence by a set of storage cells with contiguous addresses.

    • A contiguous memory space.
    • Advantages: Random access to table elements
    • Disadvantages: Insert and delete operations need to move elements, insert and delete inefficient, fixed size

  2. Chained storage: In a computer, the data elements of a linear table are stored in an arbitrary set of storage cells (the group of storage cells may be continuous or discontinuous). It does not require that logically adjacent elements also be physically adjacent. Therefore, it does not have the weakness of sequential storage structure, but it also loses the advantage of random access of sequential table.

    • The storage density is smaller than that of sequential storage structure (each node is composed of data field and pointer field, so sequential storage is more than chain storage if the same space is assumed to be full).
    • Nodes that are logically adjacent need not be physically adjacent.
    • Flexible insertion and deletion (no need to move the node, just change the pointer in the node), high insertion and deletion efficiency.
    • Chain storage is slower than sequential storage for finding nodes.
    • Each node is composed of a data field and a pointer field.

  3. Hash storage structure: map the storage location of data to the key code, so as to improve the speed of data search.

    • Multiple data elements may be stored in the same location, causing address conflicts
    • Advantages: Search based on the data itself can be found, high search efficiency, high access efficiency.
    • Disadvantages: access random, not easy to order search.

  4. Index storage structure: in addition to building storage node information, also build additional index table to identify the address of the node. An index table consists of several index items.

    • The index storage structure uses the index number of nodes to determine the storage address of nodes. Its advantage is fast retrieval, but its disadvantage is that additional index tables are added, which will occupy more storage space.
    • For easy lookup, the whole is unordered, but the index blocks are ordered, and extra space is needed to store the index table.
    • Advantages: An improvement of the sequential search, high search efficiency
    • Disadvantages: Extra space for index storage

Storage structure reference: www.cnblogs.com/fengty90/p/…