“This is the 12th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge 2021”.

This paper introduces the basic concepts of data structure, and the general classification of data structure, and finally introduces the relationship between data structure and algorithm.

The generalized data structure is a subject that studies the operation objects in the programming problems of non-numerical computation, and the related problems such as their relations and operation.

In the narrow sense, a data structure is a collection of data elements that have one or more specific relationships with each other.

1 Basic concepts and terms

1.1 data

Data is a symbol describing objective things, an object that can be operated by the computer, and a symbol set that can be recognized by the computer and input to the computer for processing.

Data not only includes numeric types such as integer and real, but also includes characters and non-numeric types such as sound, image and video. For numeric types, numerical calculation can be carried out. Non-numeric types are handled by encoding them into numeric data.

1.2 Data Elements

A data element is a meaningful unit of data that is usually processed as a whole in a computer and is also known as a record. People, cows, dogs, pigs.

1.3 data item

A data item is the smallest independent, indivisible basic unit that constitutes a data element. A data element can consist of several data items.

Such data elements as the person, can have eye, ear, nose, mouth, hand, foot these data items, can also have the name, age, gender, birth address, contact phone number and other data items, specific what data items, to decide according to the system you do.

1.4 Data Objects

A data object is a collection of data elements of the same nature, and is a subset of data. For example, people all have the same data items such as name, date of birth and gender. People belong to data.

In practice, the data elements we deal with usually have the same properties, and without confusion, we refer to data objects simply as data.

The diagram of the above concepts is as follows:

2 Data Structure

Data structure is the way that computer stores and organizes data. It refers to the collection of data elements with one or more specific relationships among them. Including according to the different viewpoint, can be divided into logical structure and physical structure.

2.1 Logical Structure

Logical structures represent abstract associations between data elements. Logical structure is for specific problems, is to solve a problem, on the basis of understanding the problem, choose a suitable data structure to represent the logical relationship between data elements.

There are three basic types of common logical structures: linear structure, tree structure and graph structure, which can also be uniformly divided into linear structure and nonlinear structure.

Linear structure:

There is a one-to-one relationship between data elements in a linear structure, as shown below:

Tree structure:

There is a one-to-many relationship between data elements in the tree structure, as shown in the following figure:

Graphic structure:

There is a many-to-many relationship between data elements in the graph structure, as shown below:

2.2 Physical Structure

Physical structure is the specific storage form of the logical structure of the data in the computer, also known as the storage structure. There are roughly two kinds: sequential storage structure and chain storage structure.

Sequential storage structure:

Data elements are stored in storage units with contiguous addresses, and the logical and physical relationships between data are consistent. For example, array storage, is the use of sequential storage structure, array storage units are continuous.

Chain storage structure

Data elements are stored in any set of storage units, which can be continuous or discontinuous. Data elements are logically related by Pointers. For example, a common implementation of linked lists is the chain storage structure.

Logical structure is problem oriented, while physical structure is computer oriented, and its basic goal is to store data and its logical relations in the memory of the computer.

3 Abstract Data Types (ADT)

3.1 Data Types

Is the collective name for a set of values and a set of operations defined on the set of values.

3.2 the abstract

Extract the general nature and characteristics of things, ignoring the specific nature and characteristics.

3.3 Abstract Data Type (ADT)

A mathematical model of a particular class of data structures with similar behavior and a set of operations defined on that model. It’s a tool of theory.

The purpose of abstract data types is to enable people to understand the characteristics of data structures independently of the implementation details of the program. The definition of an abstract data type depends on its logical nature and has nothing to do with how it is represented inside the computer.

For example, the abstract stack (stack) is a first-in, last-out queue, and is defined by three operations: push, pop, and peek at the top of the stack. Different languages implement stacks differently, but their abstract data types are the same.

Every data structure has its abstract data type, and to learn a data structure you must understand its abstract data type. For example, many data structure and algorithm books are implemented in C language, but if we understand the abstract data type of data structure, we can use the Java language to implement.

4 Relationship between data structure and algorithm

Data structure operation object is a data element, that is, they have the same properties, the existence of the relationship between them can make a difference in structure, the relationship between the data element + operation constitutes the data types, the existing of abstract data type is constitute the abstract data type (ADT), is the model encapsulates the value and operation.

A set of code that manipulates data is called an algorithm, and we can use the corresponding algorithm to write a piece of code that forms the corresponding data structure. To put it simply, a specific implementation of a data structure is implemented through the corresponding code (algorithm), and then the code to perform certain operations on the data in the data structure, such as lookup, also uses the algorithm.

Data structures serve algorithms, and algorithms have to operate on specific data structures to make sense.

For a group of data, we want to achieve a certain purpose, first to consider what kind of data structure to store these data, and then what kind of algorithm to operate these data, and in the construction process of the data structure is also used in the corresponding algorithm. For example, we need to sort the data, so we can use red-black tree or heap data structure to store, and then see how we implement the algorithm.

Linear tables, stacks, strings, trees, and graphs are common data structures defined by abstract data types, and lookup and sorting are common algorithms.

For an introduction to algorithms, see this article: Introduction to Algorithms and Time complexity Derivation.

If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!