【Five Minutes】001 - Introduction to Data Structures

2021年3月3日 48点热度 0人点赞 0条评论

内容目录

Learning Requirements

Concepts and Terminology

The basic concepts of data structures: data, data elements, data structures, logical structure of data, physical structure, algorithms, etc.

Basic Concepts and Terminology

【1】

Data (Data) is the carrier of information that can be recognized, stored, and processed by computers.

Data Element (Data Element) is the basic unit of data, sometimes referred to as elements, nodes, vertices, or records.

Data Structure (Data Structure) refers to the relationships among data, i.e., the organizational form of data. Data structures generally include the following three aspects:

The data structure generally includes the following three aspects: the logical structure of data, the storage structure of data, and data operations.

① Logical Structure of Data (Logical Structure) indicates the logical relationships between data elements. The logical structure of data describes the data from a logical relationship and is independent of the storage, hence is independent of the computer.

② Storage Structure of Data (Storage Structure) refers to how data elements and their relationships are stored in the computer memory. The storage structure of data is the realization of the logical structure using computer languages and depends on the programming language used.

③ Data Operations, which are operations applied to data (such as retrieving, inserting, deleting, updating, sorting, etc.).

The logical structure of data is often referred to simply as the data structure.

【2】

Data Type (Data Type) is a concept provided by high-level programming languages. A data type is a collection of values together with a set of operations defined on these values. For example, the int type in C language and the range of maximum and minimum values it represents, along with operations like addition, subtraction, multiplication, and division.

There are two types of data types: Atomic Types and Structured Types. Atomic types are indivisible, such as float and double for floating-point types, int and long for integer types found in most languages. Structured types can be broken down into several components, such as C language's numerical and structure types.

【3】

Abstract Data Type (Abstract Data Type, ADT) refers to the organization of abstract data and the operations associated with it. It can be seen as the data in logical structure along with its defined operations. Abstract data types can be viewed as models describing problems, independent of specific implementations. Its advantage lies in encapsulating the data and operations together, allowing user programs to access the data only through certain operations defined in the ADT, thus achieving information hiding.

ADT describes problems at the conceptual/abstract level, while in object-oriented languages, it corresponds to interfaces and abstract classes. A class describes problems at the implementation level and is an implementation of the ADT.

The main significance of ADT is to encapsulate data and operations, allowing user programs to access the data only through certain operations defined within the ADT, thus achieving information hiding.

Regarding properties in C#, both C# and Java have the concept of properties. For example, a property in C# can be defined as: public int a { get; set; }. In C#, the data is actually stored in fields, and properties are a design for accessing these fields. Thus, in a class, fields belong to data while properties can be viewed as operations on the data.

【4】

In data structures, various structural forms have emerged to represent data storage. Regardless of the storage structure, it is composed of multiple elements, and the logical relationships between these elements can be represented using unified terminology.

A - B - C

The first node that starts in a data structure is called the starting node, while the last one is referred to as the terminal node. For any node A in the data structure, if A precedes B and they are adjacent, A is called the Immediate Predecessor of B; if there is a node C that is adjacent to B and C follows B, then C is termed the Immediate Successor of B. A starting node does not have a direct predecessor, and a terminal node does not have a direct successor.

【5】

The Logical Structure of data falls into two major categories:

(1) Linear Structure

If the structure is a non-empty set (i.e., it has elements), it possesses the following characteristics:

① There must be exactly one starting node in the set.

② There must be exactly one terminal node in the set.

③ Except for the last element, all other data elements must have exactly one immediate successor.

④ Except for the first element, all other data must have exactly one immediate predecessor.

(2) Non-Linear Structure

In a non-linear structure, each node may have multiple immediate predecessors and immediate successors.

Note that the logical structure of data can be categorized into two major types: linear structure and non-linear structure; while the logical structure of data can be classified into four types:

1. Set Structure: There are no logical relationships between data elements.

2. Linear Structure: A data structure that has a "one-to-one" linear relationship between the data elements. 1:1.

3. Tree Structure: Data elements define a hierarchical relationship. 1:N.

4. Graph Structure (Mesh Structure): Data elements define a network relationship. M:N.

【6】

The Storage Structure of data has four basic methods:

Sequential storage method, linked storage method, indexed storage method, and hashed storage method.

(1) Sequential Storage Method:

Logic adjacent nodes are stored in physically adjacent storage units, and the logical relationships between nodes are manifested through the adjacency of storage units. This is usually described using arrays in programming languages, with storage utilizing a contiguous block of space.

(2) Linked Storage Method:

This method does not require logically adjacent nodes to be physically adjacent; the logical relationships between nodes are represented by additional pointer fields, usually described using pointer types in programming languages.

(3) Indexed Storage Method:

This method typically builds an additional index table while storing node information. The index table consists of several index items. If each node has an index item in the index table, it is termed a Dense Index, where the addresses of the index items indicate the storage locations of the nodes.

If a group of nodes corresponds to only one index item in the index table, it is termed a Sparse Index, where the addresses of the index items indicate the starting storage location of a group of nodes. The general form of an index item is: (Key, Address).

The key uniquely identifies a node among the data items.

Dense Index_Sparse Index

Image Source: https://blog.csdn.net/weixin_43507410/article/details/112463344

(4) Hashed Storage Method:

The basic idea of this method is to directly calculate the storage address of the node based on its key. Hashing is also known as Hash.

Test

Note: Currently unlearned content; articles in the later part of the topic will continue to cover this. Readers do not need to fuss over the questions.

Among the following options, the one that belongs to logical structure is

A. Linear List

B. Linked List

C. Sequential Stack

D. Circular Queue

Logical structures: set, linear (e.g., linear list), graph, tree;

Storage structures: sequential, linked (e.g., linked list), indexed, hashed;

Stack and linked are both storage structures; the circular queue is a type of sequential storage structure.

Logical structures include linear structures (linear lists) and non-linear structures.

Data structures are divided into logical structures and storage structures. Among the following data structures, the one that does not belong to storage structures is

A. Linear Linked List

B. Binary Linked List

C. Stack and Queue

D. Circular Queue

The linear linked list is a chain storage structure of a linear list; the binary linked list is a chain storage structure of a binary tree; stacks and queues are special linear lists; the circular queue is a type of sequential storage structure. Therefore, the linear linked list, binary linked list, and circular queue all belong to storage structures, whereas stack and queue belong to logical structures.