# Introduction to Data Structures

## 1. The concept of data and data structures

​Data : It is a symbol that describes objective things, an object that can be manipulated in a computer, and a collection of symbols that can be recognized by the computer and input to the computer for processing.

​ Data includes not only numeric types such as integers and reals, but also non-numeric types such as characters, sounds, images, and videos.

​Data element : It is the basic unit that makes up data and has a certain meaning. It is usually processed as a whole in a computer, also called a record.

For example, in humans, what is a data element? Of course it’s people.

​Data item : A data element can consist of several data items.

​ In fact, it is a description of the attributes of data elements. For example, data elements such as people can have data items such as eyes, ears, nose, mouth, hands and feet, as well as name, age, gender, home address, contact number and postal service. Encoding and other data items.

A data item is the smallest unit in which data is indivisible. But when it comes to really discussing the problem, it is the data elements, not the data items.

​Data object : is a collection of data elements with the same nature, which is a subset of data.

What is the same nature? It means that the data elements have the same number and type of data items, such as people, both Chinese and foreigners are people, and have data items such as name, gender, age, etc.

data structure

​ Structure, in simple terms, is a relationship. Strictly speaking, it refers to the way in which the various components are matched and arranged with each other. In real life, different data elements are not independent, but have specific relationships, which we call structures.

​Data structure :is a collection of data elements that have one or more specific relationships with each other。

It can also be said that:A data structure is a form of storage and organization of data in a computer。

## 2. Logical structure and physical structure

### 2.1 Logical structure

​Logical structure : refers to the relationship between data elements in a data object.

#### 2.1.1 Collection structure

​ The data elements in the collection structure have no other relationship except that they belong to the same collection.

#### 2.1.2 Linear Structure

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

#### 2.1.3 Tree structure

​ The data elements in the tree structure are in a one-to-many hierarchical relationship.

#### 2.1.4 Graphical Structure

The data elements of the graph structure are in a many-to-many relationship.

### 2.2 Physical structure (storage structure)

​Physical structure : refers to the storage form of the logical structure of data in the computer.

#### 2.2.1 Sequential storage structure

​ is to store data elements in storage units with consecutive addresses, and the logical and physical relationships between the data are consistent.

​ The simplest example is an array. For example, when you want to create an array with nine integer data, the computer finds a block of free memory in memory and multiplies the size occupied by an integer by 9 to open up a continuous segment. space, then the first data is placed first, the second is placed second… so one discharge.

#### 2.2.2 Chain storage structure

If the structure involves changes, it is very inconvenient to store the structure sequentially. For example, to remove an element in the array, it is usually necessary to move the element in the array. If the array is large, it will be very troublesome. This is because the logical relationship and the physical relationship are unified. Once the logical relationship changes, the physical relationship will also change. If the logical relationship and the physical relationship are not consistent, is it necessary to change the physical relationship when changing the logical relationship? No, it still needs to be changed, it’s just easier to change the physical relationship.

​Chain storage structure : It stores data elements in any memory unit. This group of storage units can be continuous or discontinuous.

At this time, the storage relationship of the data element does not reflect its logical relationship, so a pointer needs to be used to store the address of the data element, so that the location of the relevant data element can be found through the address.

​ Obviously, chain storage is much more flexible. It doesn’t matter where the data exists at all, as long as there is a pointer that stores the corresponding address, it can be found.

## 3. Data Type

​ refers to a set of values ​​with the same properties and a general term for some operations defined on this set. .

### 3.1 Data Type Definition

​ Data types are divided according to different values. Types are used to describe the range of values ​​and operations that can be performed on variables or expressions.

Why did people in the past think about data structures?

​ Let’s take an example in life first: everyone needs a house to live in, right? According to the rich and poor, everyone lives in different houses, such as commercial houses, apartments, villas, etc. The structural design and size of the house are also different. So many types, why are there so many types of houses?to meet the needs of different groups of people。

​ In the same way, in a computer, the memory is not infinite. If you want to calculate the four arithmetic operations of an integer number such as 1+2=3, obviously you don’t need to open up a lot of space for it. You have to calculate complex operations with very large numbers, and it is obviously not enough to open up the space for the previous integer numbers. That is to say, to classify the data,In order to meet the computing needs in different scenarios。

For example, declaring variables in C language `int a, b`means that the value range of int cannot be exceeded when assigning values ​​to variables a and b, and the operation between variables a and b can only be the operation allowed by the int type.

### 3.2 Abstract Data Types

​Abstract Data Type (ADT) : A mathematical model and a set of operations defined on that model.

It is to extract the general characteristics of things, and only care about the logical characteristics, not how it is represented and implemented in the computer.

Operations between are only allowed by the int type.

### 3.2 Abstract Data Types

​Abstract Data Type (ADT) : A mathematical model and a set of operations defined on that model.

It is to extract the general characteristics of things, and only care about the logical characteristics, not how it is represented and implemented in the computer.