• 欢迎访问速搜资源吧，如果在网站上找不到你需要的资源，可以在留言板上留言，管理员会尽量满足你！

# 【速搜问答】线性表结构是什么

1年前 (2021-04-11) 212次浏览

Chinese-English Translation:

The most common data structure is linear table. The specific meaning of each data element is different in different situations. It can be a number or a symbol, a page of book, or even more complex information. In a slightly complex linear table, a data element can be composed of several data items.

Linear table structure is the most common and simplest data structure. In short, a linear table is a finite sequence of N data elements. As for the specific meaning of each data element, it is different in different cases. It can be a number or a symbol, a page of book, or even other more complex information. In a slightly complex linear table, a data element can be composed of several data items. In this case, data elements are often called records, and linear tables with a large number of records are also called files.

brief introduction

Linear table structure is a kind of linear structure, which is a finite sequence of N data elements. The characteristics of linear structure are: in the nonempty finite set of data elements, (1) there is a unique data element called “the first”; (2) there is a unique data element called “the last”; (3) except for the first, each data element in the set has only one precursor; (4) except for the last, each data element in the set has only one precursor Follow up. The common linear list structures are sequential list and linked list.

Sequence table

The order table is a linear table in the form of array in the computer memory. It is a linear structure in which data elements are stored successively in a group of storage units with continuous addresses.

Linked list

Linked list is a common basic data structure. It is a linear list, but it does not store data in linear order. Instead, it stores the pointer to the next node in each node. Because it doesn’t have to be stored in order, the complexity of linked list can reach o (1) when it is inserted, which is much faster than another linear sequential list. However, it takes O (n) time to find a node or access a node with a specific number, and the corresponding time complexity of sequential list is O (logn) and O (1).

Using linked list structure can overcome the disadvantage that array linked list needs to know the size of data in advance. Linked list structure can make full use of computer memory space and realize flexible dynamic memory management. However, the linked list loses the advantage of random array reading, and the space cost of the linked list is relatively large because it increases the pointer field of the node.

In computer science, linked list as a basic data structure can be used to generate other types of data structure. A linked list usually consists of a series of nodes, each of which contains arbitrary data fields and one or two links to the location of the previous and / or next node. The most obvious advantage of linked list is that the way in which the conventional array arranges the associated items may be different from the order of these data items in memory or disk, and the data access often needs to be converted in different order. A linked list is a self indicating data type because it contains a pointer (link) to another data of the same type. Linked list allows inserting and removing nodes at any position on the list, but does not allow random access. There are many different types of linked lists: one-way linked list, two-way linked list and circular linked list.

Two way linked list

Also known as double linked list, is a kind of linked list, it has two pointers in each data node, which point to direct successor and direct precursor respectively. Therefore, starting from any node in the two-way linked list, you can easily access its precursor node and successor node. Generally, we construct a bidirectional circular list.

Circular linked list

Circular linked list is a kind of chain storage structure, its last node points to the head node, forming a ring. Therefore, starting from any node in the circular list, you can find any other node. The operation of circular linked list is basically the same as that of single linked list. The only difference is that the circular conditions in the algorithm are different.

One way linked list

The simplest kind of linked list is one-way linked list, which contains two fields, an information field and a pointer field. This link points to the next node in the list, and the last node points to a null value.

The nodes of a one-way list are divided into two parts. The first part stores or displays information about the node, and the second part stores the address of the next node. One way linked list can only traverse in one direction.

The most basic structure of linked list is to save data and address to the next node in each node, a special end tag in the last node, and a pointer to the first node in a fixed position. Sometimes, the pointer to the last node will also be stored at the same time. Generally, when searching for a node, you need to start from the first node and visit the next node every time until you reach the desired location. But you can also save the location of a node in advance and access it directly. Of course, if you just access the data is not necessary, it is better to store the pointer to the actual data on the linked list. This is generally to access the next or previous node in the linked list (you need to store the reverse pointer, see the bidirectional linked list below).

Compared with the following two-way linked list, this common linked list with only one pointer per node is also called one-way linked list or single linked list. It is usually used when only the linked list is traversed in order each time (for example, the adjacency list of a graph is usually accessed in a fixed order).

Structural features

1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

1. Uniformity: Although the data elements of different data tables can be various, the data elements of the same linear table must have the same data type and length.

2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。

2. Order: the position of each data element in the linear table only depends on its serial number, and the relative position before the data element is linear, that is, there are only “the first” and “the last” data elements. Except for the first and the last, there is only one data element (direct precursor) in front of other elements and only one data element (direct successor) behind them ）。

[361009623@qq.com]

• 版权声明

本站的文章和资源来自互联网或者站长
的原创，按照 CC BY -NC -SA 3.0 CN
协议发布和共享，转载或引用本站文章
应遵循相同协议。如果有侵犯版权的资
源请尽快联系站长，我们会在24h内删
除有争议的资源。
• 网站驱动

• 友情链接

• 支持主题