Speaking of why to pick up this book again, really very ashamed. Because in the interview, after the first interviewer has interviewed the project. The second interviewer said that we could just chat and study data structures and algorithms. I was stumped by a question: What is a hash table?

So I’m going to spend two days rereading the book and making notes that I’ll remember this time.

Chapter one introduction

At present, computer has penetrated into every field of social life, and its application is no longer limited to scientific calculation, but more for control, management and data processing and other non-numerical calculation fields. Computer is the science of information representation and processing by computer. There are two problems involved: representation of information and processing of information.

The presentation and organization of information are directly related to the efficiency of information processing procedures. With the increasing complexity of application problems, the increase of information and the widening of the scope of information, so that many system procedures and applications of large scale, the structure is quite complex. Therefore, it is necessary to analyze the characteristics of the objects in the problem to be dealt with and the relationship between them. This is the problem that the data structure course will study.

1.1 What is a data structure?

That has to be the first question.

Have you ever thought about how many steps a computer takes to solve a specific problem?

1. Abstract a mathematical model from a specific problem
2. Design an algorithm to solve this model
3. Make up the program
4. test
5. Get the answer

Here are three examples:

• Library Bibliographic Retrieval System (sorted by title or author name) : Table Structure (one to one)
• Chess games (multiple moves for each move) : tree structure (one-to-many)
• Multi-fork traffic intersection problem (each intersection affects each other) : Graph structure (many-to-many)

1.2 Basic Concepts and Terminology

• Data: Symbolic representation of an objective thing.

• Data Element: The basic unit of data.

• Data object: A collection of data elements of the same nature. It is a subset of data elements.

• Data structure: A collection of data elements that have one or more specific relationships with each other.

  • (There are usually four kinds of structure.)

    1. Set (no relation other than belonging to a set)
    2. Linear structure (one to one)
    3. Tree structure (one-to-many)
    4. Graph structure (many-to-many)

Representation of data structures in a computer

The representation of data structure in the computer is called the physical structure of data structure, also known as the storage structure.

• Bit: A bit in binary system, the smallest unit in a calculator.
• Element or node: A string of bits.
• Data field: When a data element consists of several data items, the subbit strings in the bitstring corresponding to each data item are called data fields.

Two relationships between data elements in a computer

• Sequential image, the storage structure is sequential storage structure

  Features: Logical relationships between data elements are represented by their relative positions in memory.

  For example, complex numbers: z1 = 3.0-2.3i and z2 = -0.7+4.8i. (Figure A)

• Non – sequential image, the storage structure of the chain storage structure

  Features: Use the pointer to the address of the element to represent the logical relationship between the elements.

  Z1 = 3.0-2.3i. (Figure B)

Data Type

A data type is a collection of values and the general term for an operation defined on that value. For example, the value of an integer variable in C language is an integer in a certain interval, and the operations defined on it are arithmetic operations such as addition, subtraction, multiplication and division.

Data types for high-level languages fall into two categories:

1. Atomic type: Atomic type values are indivisible. 2. Structural type: The value of a structural type consists of the values of a certain structure of several structures and is therefore resolvable, and its components can be structural or unstructural.Copy the code

Abstract data Type

An abstract data type is a mathematical model and a set of operations defined on that model.

A software module that abstracts data types usually consists of three parts: definition, representation, and implementation.

1. Definitions fall into three types:

   • Atomic data type
   • Fixed-aggregate data type: a value consisting of a certain number of components in a certain structure. A complex number consists of two real numbers in a definite order.
   • Variable-aggregate data type: The number of components that make up its value is indeterminate.

   The latter two can be collectively referred to as structural types.

   Abstract data types can be composed of the following triples:

   (D, S, P)

   Where D is the data object, S is the set of relations on D, and P is the basic operation on D.

   This book uses the following format for abstract data types:

   ADT < Abstract data type name >{

   Data objects: < Definition of data objects >

   Data relationships: < Definition of data relationships >

   Basic operations: < Definition of basic operations >

   } ADT < abstract data type name >

   • The definition of data object and data relation is described by pseudo code.

   • The basic operation is defined as:

     < Basic operation name >(< parameter list >)

     Initial conditions: < Description of initial conditions >

     Operation result: < Description >

     • Initial conditions: describes the conditions that data structures and parameters should meet before an operation is performed. If no, the operation fails and an error message is displayed.
     • Operation result: Describes how the data structure changes and what results should be returned after the operation completes normally.