Shulou(Shulou.com)05/31 Report--

Today Xiaobian to share with you what the basic concept of c++ related knowledge points, detailed content, clear logic, I believe that most people still know too much about this knowledge, so share this article for your reference, I hope you have some gains after reading this article, let's learn about it together.

Section 1: Overview of Data Structure

The main task of data structure is to analyze the structural characteristics of data objects, including logical structures and relationships between data objects, and then express logical structures into physical structures realized by computer classes, thus facilitating computer processing.

1.1 concept term

(1) Data is a symbol or set of symbols that can be processed by a computer. It has a wide meaning and can be understood as "raw materials." Such as characters, pictures, audio and video, etc.

(2) A data element is the basic unit of data. For example, a student statistics sheet.

(3) A data item is the smallest unit of data elements. For example, a student statistics table has data items such as number, name, gender, origin, etc.

A data object is a collection of data elements of the same nature, a subset of data. For example, positive integer N={1, 2, 3,...}.

(5) Data structure is the organization of data, a collection of data elements with one or more specific relationships between data elements.

(6) Data type is operability divided according to different data values. In C language can also be divided into atomic types and structural types. Original character types are basic types that cannot be decomposed, including integer, real type, character type, etc. Structure types are composed of several types and can be decomposed again.

1.2 logical structure of data

Logical structure refers to the relationships between data elements in data. There are different logical relationships between data elements that make up the following four structural types.

(1) Set structure: The data elements of a set have no other relationship, simply because they are packed into a box called a "set."

(2) Linear structure: The linear data element structure relationship is one-to-one and in a sequential order, like a-b-c-d-e-g····connected by a thread.

(3) Tree structure: The data element structure of the tree is one-to-many, just like the department level of the company, chairman-CEO\CTO-technical department\personnel department\marketing department...

(4) Graph structure: The data element structure relationship of the graph is many-to-many. It is our common railway map of each big city. A city has many lines connecting different cities.

1.3 Storage (physical) structure of data

Storage structure (also known as physical structure) refers to the logical structure of data stored in a computer.

The storage structure of data can generally reflect logical relationships between data elements. Divided into sequential storage structure and chain storage structure.

(1) Sequential storage structure: data elements are stored in a group of consecutive storage locations, and the logical relationship and physical relationship between data elements are consistent.

(2) Chain storage result: data elements are stored in any storage unit, this group of storage units can be continuous, can also be discontinuous, the storage relationship of data elements can not reflect its logical relationship, so it is necessary to use pointers to represent the logical relationship between data elements.

Summary:

The logical structure and physical structure of data are closely related. In the process of learning data, it will be found that the design of any algorithm depends on the selected logical structure of data, and the implementation of the algorithm depends on the storage structure adopted.

1.4 abstract data types

An abstract data type (ADT) describes a data model that has some logical relationship and performs a set of operations on the mathematical model.

Abstract data type describes a set of logical characteristics, independent of internal representation in the computer, integer data type in the computer is an abstract data type, different processors may implement different methods, but its logical characteristics are the same, that is, addition, subtraction, multiplication, division and other operations are consistent.

"Abstract" means the mathematically abstract properties of data types rather than their implementation methods.

Abstract data type embodies the characteristics of problem decomposition, abstraction and information hiding in program design. It can decompose a large problem in reality into a number of small and easy-to-handle problems, and then establish a data that can be processed by a computer. The implementation details of each functional module are regarded as an independent unit, so that the specific implementation process is hidden.

Similar to building a house, it is divided into several small tasks, such as land planning, drawing design, construction, decoration, etc. The whole process is similar to problem decomposition in abstract data types. The brick-moving person does not need to know how the drawing design is, the design drawing personnel do not need to know the specific details of the construction foundation and the wall, and the decoration workers do not need to care about the drawing and the brick-moving process. This is the information hiding in the abstract type.

The concept of abstract data types may be difficult for beginners to understand. For example, the abstract data type description data object set of a linear table: the data object set of a linear table is {a1,a2,a3,···,an}, and the type of each element is DataType. where each element except the first element a1 has one and only one immediate predecessor and each element except the last element an has one and only one immediate successor. The relationships between data elements are one-to-one.

1.5 algorithm

An algorithm is a description of the steps involved in solving a particular problem, represented in a computer as a finite sequence of operations.

After the data types are established, operations are performed on these data types to establish sets of operations, i.e., programs. The efficiency of computer program prototype is directly determined by the establishment and method of operation.

(1) Relationship between data structure and algorithm

There's a difference between the two. Connection is program = algorithm + data structure. Data structure is the basis of algorithm implementation, algorithm always depends on some data structure to achieve.

The algorithm operates on data structures. The difference is that the data structure focuses on the logical structure of the data, the storage structure and its basic operations, while the algorithm is more concerned with how to solve the actual problem on the basis of the data structure.

Algorithms are programming ideas, and data structures are the basis of those ideas.

(2) Five characteristics of the algorithm

Finitude means that the algorithm automatically ends after performing a finite number of steps rather than an infinite loop, and each step is completed within an acceptable time.

Determinism means that each step executed by the algorithm has only one execution path under certain conditions, that is, the same input can only have one unique output result.

Feasibility means that each step of the algorithm must be feasible and can be completed by a limited number of executions.

Input means that the algorithm has zero or more inputs.

Output means that the algorithm has at least one or more outputs.

1.6 time complexity

In algorithmic analysis, the number of executions T(n) of a statement is always a function of the problem size n. Furthermore, the variation of the degree T(n) with the scale n is analyzed and the order of magnitude of T(n) is determined. The time complexity of the algorithm is the time metric of the algorithm, denoted T(n) = O (f (n)). It indicates that with the increase of problem size n, the growth rate of execution time of the algorithm is the same as that of f (n), which is called the asymptotic time complexity of the algorithm, referred to as time complexity. where f (n) is some function of problem size n.

The time complexity of an algorithm is an important index to measure whether an algorithm is good or bad. In general, with the increase of size n, the algorithm whose degree T(n) increases slowly is the optimal algorithm. Common time complexity in descending order: O(1) < O(log2n) < O(n) < O(n²)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.