<> What is data structure ?
Data structure is computer storage , How data is organized . Data structure refers to the collection of data elements with one or more specific relationships .
<> Basic concepts and terms
<>✍ data （Data）
Data is about objective things Symbol express .
In computer science, it means all kinds of energy input To the computer and Can be processed by computer programs The general name of the symbol of .
<>✍ data elements （Data Element）
Data element is the basic unit of data , In computer programs, it is usually considered and dealt with as a whole . Also known as records .
A data element can be composed of several data items （data item） form . data item The data is indivisible Minimum unit .
<>✍ data object （Data Object）
A data object is a collection of data elements of the same nature , A subset of data .
Treat students in a class as data objects , Every student is a data element , Student's name , The data items of this data element are gender .
Student list
Student number name gender course number
17120708 Linghu Chong male A
17120709 Let me go C
17120710 Asia the invincible B
Class Schedule Card
Course number course name
A Dugu Jiujian
B Sunflower treasure
C The method of absorbing work
Student list , Class Schedule Card , These are the two tables data .
A single table is called a data object , That is, the student table is a data object , The curriculum is also a data object .
Each row in each table is called data elements .
And the student number , full name , Gender , Course number , The course is called data item .
<>✍ data structure （Data Structure）
Data structure is a collection of data elements that have one or more specific relationships with each other .
Data is an abstract concept . Data elements are not independent , There are specific relationships , These relationships are structures .
There are two types of data structures ： Logical structure and Physics （ storage ） structure .
<>1. Logical structure
It refers to the relationship between data elements in data objects .
*
Set structure
Except that the data elements belong to the same collection , There is no other relationship .
*
linear structure
Data elements are 1:1 The relationship between .
*
tree structure
Data elements are 1:N The relationship between .
*
Graphic structure
Data elements are M:N The relationship between .
So for logical structure , We passed Is it linear It can be divided into linear structure and Nonlinear structure .
linear structure ： There is usually only one start and one end node , And all nodes have at most one precursor and one successor , The relationship between nodes is one-to-one . Typical representative ： Linear table , Stack , queue , strand .
Nonlinear structure ： A node may have multiple direct precursors and direct successors , The nodes are one to many , Or many to many relationships . Typical representative ： tree , chart .
<>2. Physics （ storage ） structure
It refers to the storage form of logical structure of data in computer .
* Sequential storage structure
To store data elements in a storage unit with consecutive addresses , The logical and physical relationships between the data are consistent .
Arrays are stored in this way .
* Linked Storage Structure
Store data elements in any storage unit , This set of storage units can be continuous , It can also be discontinuous .
The physical relationship between data does not reflect its logical relationship , Therefore, in the chain storage structure , There is a pointer to the address of the data element
So that's it The associated data element location can be found through the pointer .
<>✍ Data types and abstract data types
When using high-level programming language to write programs , Every variable that appears in the program must be , Constant or expression , Specify the type of data they belong to , as ：int num, float price,
char c etc .
A data type is a collection of values of the same nature and a set of operations defined on the set .
Abstract data type (Abstract Data Type, abbreviation ADT) It refers to a mathematical model and a set of operations defined on the model .
That is, the data type and the operation on the data type are tied together , Package . The purpose of introducing abstract data types is to separate the representation of data types and the implementation of operations on data types from the references of these data types and operations in programs , Make them independent of each other .
The definition of an abstract data type depends only on its set of logical characteristics , It has nothing to do with how it is expressed and implemented inside the computer , That is, no matter how the internal structure changes , As long as its mathematical properties remain unchanged , It does not affect its external use .
Formal definition of abstract data type :
Abstract data types can be tripled (D,S,P) express , among ：
* D Representing data objects
* S representative D Relation set on
* P On behalf of the right D Basic operation set of
Concrete implementation of abstract data type ：
C Examples of language
#include "stdio.h" typedef struct rect{ int x; // Abscissa of rectangle int y; // Ordinate of rectangle float
width; // The width of the rectangle float height; // The height of the rectangle }rect; // Initialize rectangle void init_rect(rect &r,
int x, int y, int w, int h); double area(rect &r); // Calculate the area of a rectangle double perimeter(
rect&r); // Calculate the perimeter of a rectangle
nature , The knowledge of concept class may be very boring , But it is also a knowledge point that we easily ignore . You can temper your patience .
Technology