网站建设明细报价表,淘宝的网络营销模式,佛山网站建设有限公司,wordpress博客5001、引言 本文主要是对动态链表和静态链表的区别进行原理上的讲解分析#xff0c;先通过对顺序表和动态链表概念和特点的原理性介绍#xff0c;进而引申出静态链表的作用#xff0c;以及其概念。通过这些原理性的概述#xff0c;最后总结归纳出动态链表和静态链表的区别。本…1、引言 本文主要是对动态链表和静态链表的区别进行原理上的讲解分析先通过对顺序表和动态链表概念和特点的原理性介绍进而引申出静态链表的作用以及其概念。通过这些原理性的概述最后总结归纳出动态链表和静态链表的区别。本文不对代码进行额外的讲解只对原理进行分析以加深基础的认识相关概念的代码应用读者可以另行在网上进行搜索详细学习。 2、顺序表和动态链表的特点 首先需要明白的是顺序表和链表都是线性表即线性存储结构。使用线性表存储数据的方式可以这样理解即“把所有数据用一根线串起来再存储到物理空间中”。 如下图左边将数据依次存储在连续的整块物理空间中这种存储结构称为顺序存储结构简称顺序表下图右边数据分散的存储在物理空间中通过一根线保存着它们之间的逻辑关系这种存储结构称为链式存储结构简称链表。可以看出每一个数据按照“一对一”的关系按照次序逐个排列。 2.1 顺序表存储结构 顺序表对数据的物理存储结构有要求需预先申请一整块足够大的存储空间然后将数据依次存储起来数据之间紧密贴合不留一丝空隙。如下图所示顺序表数据的 一对一 逻辑关系就是数据按照次序连续存储到一整块物理空间上一个数据存储在一个位置之后紧接着就是下一个数据存储在下一个连续的位置。其数据存储方式和数组非常相似。 使用顺序表存储数据之前除了要申请足够大小的物理空间之外为了方便后期使用表中的数据顺序表还需要实时记录以下 2 项数据1顺序表申请的存储容量即总的空间大小类似于数组的总大小2顺序表的长度也就是当前表中存储数据元素的个数。正常状态下顺序表申请的存储容量要大于顺序表的长度。顺序表的结构表示如下
typedef struct Table
{int * head;//声明了一个名为head的长度不确定的数组也叫“动态数组”int length;//记录当前顺序表的长度int size;//记录顺序表分配的存储容量
}table;
2.2 链表存储结构 链表的存储方式与顺序表截然相反链表不限制数据的物理存储状态换句话说使用链表存储的数据元素其物理存储位置不是连续的而是随机的。什么时候存储数据才在什么时候申请存储空间。链表数据的 一对一 逻辑关系就是数之间通过指针来维持一个数据存储在一个位置之后通过指针指向下一个数据存储在下一个位置。这样的链表也称之为动态链表。 链表中每个数据的存储都由两部分组成1数据元素本身其所在的区域称为数据域2指向直接后继元素的指针所在的区域称为指针域。这两个部分组成了链表中的一个数据节点链表实际存储的是一个一个的节点链表数据节点的结构表示如下
typedef struct Link
{char elem; //代表数据域struct Link * next; //代表指针域指向直接后继元素
}link; //link为节点名每个节点都是一个 link 结构体2.3 顺序表和动态链表的比较 根据以上介绍的顺序表和动态链表的存储结构特点可以比较出两者在以下几个方面的区别
1开辟空间的方式 顺序表存储数据实行的是 一次开辟永久使用即存储数据之前先开辟好足够的存储空间空间一旦开辟后期无法改变大小使用动态数组malloc的情况除外。
而动态链表则不同动态链表存储数据时一次只开辟存储一个节点的物理空间如果后期需要还可以再申请。 因此若只从开辟空间方式的角度去考虑当存储数据的个数无法提前确定又或是物理空间使用紧张以致无法一次性申请到足够大小的空间时使用动态链表更有助于问题的解决。
2空间利用率 顺序表的空间利用率高而动态链表的空间利用率低。 顺序表用一段连续的存储单元依次存储线性表的数据元素物理空间上是连续的动态链表用一组任意的存储单元存放线性表的元素逻辑上连续通过指针维持但物理空间上不一定连续。 动态链表在物理空间上不一定连续是由于每次只申请一个节点的空间且空间的位置是随机的。这种申请存储空间的方式会产生很多空间碎片一定程度上造成了空间浪费。不仅如此由于动态链表中每个数据元素都必须携带至少一个指针因此动态链表对所申请空间的利用率没有顺序表高。
3插入元素的容量 顺序表中空间不够时需要扩容扩容会有一定的消耗扩容后可能存在一定的空间浪费动态链表没有容量的概念按需申请空间。
4存储密度 顺序表中其存储密度均为1因为数组空间只用来存数据元素。而在动态链表中每个节点除了存储数据元素自身外还会至少存储直接后继的存储位置信息。相对于顺序表动态链表的存储密度要低得多。
5时间复杂度
针对随机访问性能来说 顺序表随机访问一个元素可以用下标的方式直接访问无需遍历整个表时间复杂度为O(1)动态链表随机访问一个元素需要从头到尾遍历直到寻找到该元素时间复杂度为O(N)。
针对任意位置插入或者删除元素来说 顺序表可能需要按顺序搬移大量元素后进行元素的插入或删除效率较低时间复杂度为O(N)动态链表中数据元素之间的逻辑关系靠的是节点之间的指针因此在动态链表中插入或删除元素只需修改指针的指向不需搬移大量元素时间复杂度为O(1)。 因此涉及访问元素的操作而元素的插入、删除和移动操作极少的场景时适合用顺序表涉及元素的插入、删除和移动而访问元素的需求很少的场景时适合用动态链表。 3、为什么会有静态链表 单站在时间复杂度的角度上来看是否能够有一种数据结构既能够像顺序表一样快速的访问数据元素又可以像动态链表一样可以方便的插入、删除和移动数据元素 静态链表就是这样一种数据结构其属于一种线性存储结构分配一整片连续的内存空间各个节点集中安置逻辑结构上相邻的数据元素存储在指定的一块内存空间中数据元素只允许在这块内存空间中随机存放。数据全部存储在数组中和顺序表一样但存储位置是随机的数据之间一对一的逻辑关系通过一个整型变量称为游标和指针功能类似维持和链表类似。在将数据存放到数组中时给各个数据元素配备一个整形变量此变量用于指明各个元素的直接后继元素所在数组中的位置下标。 如图中a[0]~a[6]为数组下标分配的内存空间中绿色数字为数组的数据元素红色数字就为数组的游标变量表示当前节点的下一个节点的数组下标。因此下标为x的数组中存放当前的数组数据元素和后继元素所在数组中的位置下标。因此可以看出静态链表是用数组来实现链式存储结构静态链表实际上就是一个结构体数组。 如上图a[1]中存放的数据元素值为2通过a[1]中存放的游标变量4可找到后继元素所在的数组a[4]a[4]中存放的数据元素值为5通过a[4]中存放的游标变量3可找到后继元素所在的数组a[3]a[3]中存放的数据元素值为7通过a[3]中存放的游标变量6可找到后继元素所在的数组a[6]。以此类推直到某元素的游标变量为0即可停止注意a[0]为头结点其不存储数据元素。 但是从上图中可以看出数组中间有未使用过的空间即没有数据元素的数组成员这样岂不是浪费了存储空间为了使我们创建的空间能够得到充分的利用我们还需要一条连接各个空闲位置的链表方便我们的随取随用这条链表也被称为备用链表。 备用链表的作用是回收数组中未使用或之前使用过目前未使用的存储空间留待后期使用。也就是说静态链表使用数组申请的物理空间中存有两个链表实现不同的功能一个用来连接数据另一个用来连接数组中的空闲空间。 为了适应这个会存在一个“潜规则”默认备用链表的表头位于数组下标为0(a[0])的位置而数据链表的表头位于数据下标为1(a[1])的位置。备用链表的数组成员中仅存放游标。如上图所示备用链表的连接顺序依次是a[0]、a[2]、a[5]数据链表的连接顺序依次是a[1]、a[3]、a[4]、a[6]。 静态链表中设置备用链表的好处是可以清楚地知道数组中是否有空闲位置以便数据链表添加新数据时使用。在静态链表的插入和删除操作中都会与备用链表有着联系当进行插入时则是用备用链表上面取得一个节点作为待插入的新节点反之当在删除时则将从链表上删除下来的节点链接到备用链表上面。整个过程中我们需要做的工作就是更新游标的值。 可见静态链表由数据链表的数据链表的各个节点和的备用链表的各个节点组成静态链表节点的结构表示如下
typedef struct List
{int data;//数据域int cur;//游标
}list; 4、动态链表和静态链表的区别 通过以上对动态链表和静态链表原理概念和各自特点的介绍我们可以对两者的区别有一个更深的认知。
1链表中数据“一对一”的关系 动态链表是靠指针来维持。 静态链表是靠游标来维持。
2内存空间申请 使用动态链表存储数据不需要预先申请内存空间而是在需要的时候才向内存申请。也就是说动态链表存储数据元素的个数是不限的想存多少就存多少。 使用静态链表存储数据需要预先申请足够大的一整块内存空间也就是说静态链表存储数据元素的个数从其创建的那一刻就已经确定后期无法更改。
3物理地址 动态链表malloc 或 free 函数动态申请或释放内存在长度上没有限制。因为是动态申请内存的所以每个节点的物理地址不连续 静态链表类是似于数组方法实现的在物理地址上是连续的而且需要预先分配地址空间大小所以静态链表的初始长度一般是固定的。
4操作方式 使用动态链表只需操控一条存储数据的链表。当表中添加或删除数据元素时只需要通过 malloc 或 free 函数来申请或释放空间。 静态链表是在固定大小的存储空间内随机存储各个数据元素使用静态链表存储数据需要操控两条链表一条是存储数据的数据链表另一条是记录空闲空间位置的备用链表便于随时分配给新添加元素使用。当表中添加或删除数据元素时需要更新数据链表和备用链表的对应节点的值。
5元素的访问 动态链表随机访问一个元素需要从头到尾遍历直到寻找到该元素时间复杂度为O(N)。 静态链表随机访问一个元素可以类似像数组通过下标的方式通过游标来访问时间复杂度为O(1)。
6元素的插入和删除 动态链表插入或删除元素时不用做元素的移动修改指针域即可。 静态链表插入或删除元素时不用做元素的移动可以通过修改游标的值来达到。 ↓↓↓更多技术内容和书籍资料获取入群技术交流敬请关注“明解嵌入式”↓↓↓
