网站运维工作内容,怎么做搜索网站,申请网站一年多少钱,做英文网站有哪些前言
接下来就开始正式进入数据结构环节了#xff0c;我们先从线性表开始。
线性表
线性表#xff08;linear list#xff09;也叫线性存储结构#xff0c;即数据元素的逻辑结构为线性的数据表#xff0c;它是数据结构中最简单和最常用的一种存储结构#xff0c;专门存…前言
接下来就开始正式进入数据结构环节了我们先从线性表开始。
线性表
线性表linear list也叫线性存储结构即数据元素的逻辑结构为线性的数据表它是数据结构中最简单和最常用的一种存储结构专门存储“一对一”逻辑关系的数据。何为“一对一”即除去第一个和最后一个数据元素其他元素均首尾相通第一个元素只有下家没有上家最后一个元素只有上家而没有下家。 此外还有一种特殊的线性表——循环链表其将尾指针指向首元素从而形成了一个闭环。存储在同一个线性表中的数据其类型必须一致即要么都是整型要么都是字符串型。如果从数据结构的逻辑层次上讲那么线性表还可以进一步细分为一般线性表和受限线性表。
一般的线性表
一般线性表可分为顺序表和链表链表又可分为单向链表、双向链表和循环链表等如下图所示。
1. 順序表
如下图所示。
顺序表Sequential List 也叫顺序存储结构即将数据依次存储在连续的物理空间中是不是发现这样的结构很熟悉是的顺序表最底层的结构即为我们常听说的数组Array而针对顺序表的任何操作包括查找、添加和删除等都是基于遍历。 一般情况下顺序表申请的存储容量应大于顺序表的长度。 2. 链表
链表Linked List也叫链式存储结构即将数据依次存储在分散的物理空间中但其逻辑关系仍是连续的如下图所示。 与顺序表不同链表的数据元素是随机存储的因此其物理存储空间比较散乱但其凭借着一条连接各个数据元素的线条使数据元素之间保持着一定的逻辑关系。 链表还可细分为单向链表、双向链表和循环链表等接下来让我们逐一进行学习。
1単向链表
单向链表也叫单链表是链表中最基础的类型通过单链表开启对于链表的学习显然是明智的。 上面我们讲到链表的物理存储空间是不连续的但逻辑关系却可以保持。这是如何实现的呢答案是指针域。单链表为每个元素配备了一个指针域next指向自己的直接后继元素。 直接后继元素即目标元素后相邻的一个元素相似的还有后继元素、前驱元素和直接前驱元素。 因此单链表的数据元素结构应该包含数据域data和指针域next它们也称为节点如下图所示。 整个单链表的结构如下图所示 然而完整的链表结构应该有头节点、头指针和首元节点如下图所示。
头指针指向链表第一个节点头节点或首元节点的指针用于指明链表的位置头节点链表第一个不包含数据的空节点不是必需的首元节点链表第一个包含数据的节点不过作用不如头节点大。 若有头节点则头指针指向头节点若无头节点则头指针指向首元节点。 单链表中的动态和静态
在单链表中又有动态和静态之分。 动态链表也叫动态单链表很多时候人们还会把它直接称作单链表这也导致很多人都会把链表的关系树混淆。不过动态链表确实就是单链表因此在后面的文章中笔者将会把动态链表称为单链表。 我们已经讲解了顺序表和单链表而静态链表可以理解为顺序表和单链表的结合体。 静态链表融合了顺序表和单链表的优点——既可快速访问元素又可快速增加和删除元素。这是怎么做到的呢 在静态链表中数据依旧存储在数组中和顺序表一样物理空间也是连续的和顺序表一样但存储位置是随机的和单链表一样元素的逻辑关系则靠“游标”指针进行维持和单链表一样。 是不是感觉有点懵别急我们继续往下看。假设我们创建了一个长度为5的静态链表它的基础结构如下图所示。 上图所示的是一个空数组。我们进一步剖析一下一个静态链表应该是由数据链表和备用链表组成的才对。为了方便理解我们进一步假设这个长度为5的静态链表存储的是数据12,3则存储状态可能如下图所示。 通常备用链表表头指向a[0]的位置而数据链表表头指向 a[1]的位置。 这里的数据链表即为存储数据的链表。该链表的每个节点除了包含所存储的数据如1、2、3之外还拥有一个整型变量这个变量称为游标变量用于标记该节点的直接后继节点的位置下标如2、4、0。而备用链表则是记录空闲位置的链表。通过备用链表我们可以清晰、便捷地知道目标链表是否还有空余位置还可以快速又准确地找到空余位置的物理地址。静态链表的完整结构如下图所示。 在这个例子里数据链表依次连接的是 a1、a2、a4而备用链表依次连接的是a0、a3。在静态链表中a0位置默认是不存储数据的若 a0位置有数据则说明该数组已满即链表已满。 让我们将数据链表和备用链表结合起来便可以得到如上图所示存储123的静态链表的完鏊结构。
当想要查找元素时便从数据链表的a1位置开始遍历毕竟我们只知道a0和 a1的地址当想要修改元素时我们依旧从数据链表的a1位置开始遍历找到目标元素后直接修改它的数据域即可游标不用修改当想要增加元素时默认插入位置为备用链表a0]的直接后继节点这样就不用移动游标时间复杂度仅为 O1当想要删除元素时我们先找到目标元素将其直接前驱节点的游标指向其直接后继节点然后删除该节点并将空余位置存放于备用链表中方便下次使用。
(2)双向链表
有单向链表则必有双向链表双向链表也叫双链表。无论是我们学过的单链表还是静态链表节点中都只包含一个指针游标用于指向直接后继节点这确实解决了最基本的“一对一”问题。 当我们编写算法需要多次查找目标节点的前驱节点时如果使用单链表的话问题就严重了——效率超低因为单链表是“一根筋的憨憨”更适合“从前往后”进行遍历。 那怎么办呢这时候双链表就诞生了。双链表的存储结构和单链表基本一致只是一个箭头变成了两个而已这里就不赘述了。双链表的节点结构如下图所示。 双链表的每个节点都有一个数据域和两个指针域prior 指针指向直接前驱节点next指针指向直接后继节点。 虽然双向链表的逻辑关系是双向的但通常情况下头指针依旧只有一个。 (3)循环链表
循环链表即环状链表只是把单链表最后一个节点的指针指向了第一个节点头节点或首元节点形成一个头尾相接的环状链表像个圆圈一样因此也被称为“环”。 循环链表之下还有单向循环链表和双向循环链表。 单向循环链表与动态单链表一样单向循环链表也经常被简单称为循环链表。为了方便大家理解画了一个循环链表的整体结构图如下图所示。 双向循环链表有了对从单链表到循环链表变形过程的认知相信双向循环链表也就不难理解了。这里就作为作业读者可尝试一下把双向循环链表的整体结构完整地画出来。
拓展
说到循环链表提到了环就必然会想到约瑟夫环。大家可以试着实现约瑟夫环以加深自己对链表的理解。
