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

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

问答 admin 1个月前 (04-11) 32次浏览 已收录 0个评论

汉英对照:
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.

线性表结构是最常用且最简单的一种数据结构。简言之,一个线性表是 n 个数据元素的有限序列。至于每个数据元素的具体含义,在不同的情况下各不相同,它可以是一个数或一个符号,也可以是一页书,甚至其他更复杂的信息。在稍复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称文件。

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

线性表结构是 n 个数据元素的有限序列,是一个种线性结构。线性结构的特点是:在数据元素的非空有限集中,(1)存在唯一的一个被称做“第一个”的数据元素;(2)存在惟一的一个被称做“最后一个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中每个数据元素均只有一个后继。常见的线性表结构有顺序表、链表。

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)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到 O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间,而顺序表相应的时间复杂度分别是 O(logn)和 O(1)。

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.

在计算机科学中,链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(”links”)。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。

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 )。


速搜资源网 , 版权所有丨如未注明 , 均为原创丨转载请注明原文链接:【速搜问答】线性表结构是什么
喜欢 (0)
[361009623@qq.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址