一:概念
数据元素的有限序列.
它需要是序列,有列且有序,第一个元素没有前驱,最后一个元素没有后继,除此之外每个元素都只有一个前驱一个后继.
线性表
线性表
线性表的抽象定义和基本操作
线性表的抽象定义和基本操作
对于线性表,复杂的问题也都是用上面这些基本操作组合来解决的,比如去重合并两个线性表A和B,获得B的长度,遍历,获取每一个元素,然后在A中对比,如果没有则插入到A的最后.
二:存储结构
1.顺序存储
线性表的顺序存储,前面提到过,就是申请一段地址连续的内存空间,也就是一个数组,需要预定好长度,而真实的数据长度,或者说线性表长度,只能小于等于数组长度.
-
查找
顺序存储一开始就要申请一段连续内存空间,而且长度是预定的,那么显然每个元素需要的空间是一样的,比如整形数组,不管是多大的数字,每个元素占的内存空间是一样大的.
因此,在获取某个位置的元素时,只要根据下标计算内存地址就行了,它是时间复杂度是O(1). -
插入
顺序存储结构,如果要再i处插入一个新元素, 首先要判断是否会溢出,之后要把i后面的元素都后移一位.时间复杂度是O(n). -
删除
同样的,删除i处的元素,后面的也都要向前移动,时间复杂度是O(n).
image.png
2.链式存储
链式存储把数据和指针包装在一起,叫做节点,每个节点分为两个部分,一个是数据域,一个是指针域,指针域存的是下个节点的地址;
对于头部的节点,数据域可能是空的,也可能会存储一些信息,比如长度,命名,或者其他业务场景实际需要的信息,而尾部的节点是真实的数据,指针域为空NULL.
因此链式存储的每个元素不相互挨着,由链表来映射数据结构,也就是线性表的特征.
这种每个节点存着下一个节点地址的链表叫做单链表.
image.png
-
头结点
并非是第一个节点,是一个扩展节点,放在第一节点之前,存储一些扩展信息,有了头结点,链表真正的数据节点就全部统一了,不必考虑第一个节点前面没东西.另外头结点是可选的. -
头指针
指向链表第一个节点的指针,如果有头结点,那么指向头结点,头指针创建链表就存在,即使链表是空的.
image.png
定义单链表
-
查找
单链表元素不挨着,查询需要一个个往下访问,时间复杂度是O(n) -
插入
当向i插入元素时,需要修改i-1的的指针和i的指针,并且这里还有个顺序问题.
image.png
如果先把p指向s,那么p->next直接就丢失了,所以应该先把s指向p->next,再把p指向s.
插入节点的实现
-
删除
删除单链表节点就是跳过被删除的节点,直接指向后面的节点.
image.png
删除节点的实现
显然插入和删除本身是O(1)的,耗时的还是查找,由于地址不连续,不能根据下标获取地址,因此不管是查找具体元素还是访问指定下标的元素,都得一个个查找,为O(n).
对比
三:创建和删除单链表
1.创建单链表
头插法
头插法
这种方法叫做头插法:
先创建一个指针L,创建的时候申请了一个Node的空间,也就是给了一个头结点,让头结点指向NULL,这就是一个空链表L.
然后创建一个指针P并申请一个新的Node,放上数据,把节点P指向L的第一个节点,如果没有,就是NULL,然后把L的头结点指向P;之后循环这一过程;
这样每次新元素就插入在第一的位置,叫做头插法.
尾插发-
尾插发(接上图)
尾插发的区别在于创建一个标记节点r指向头结点;
然后创建一个节点P,将r的next指向P,此时r就是头结点,r->next是P;
接着把r重新指向P,重新标记P为最后一个元素,以此类推.
r本来是ai-1,之后换成ai
2.删除单链表
image.png
因为是单链表,当然只能从头开始释放,用p作为标记,拿到要删除的那个节点,然后释放,但是如果释放了p,后面的节点就泄漏了,所以还得用q来暂存一下p之后的那个节点,然后循环往后移动,最后释放头结点.
四:静态链表
1.静态链表
静态链表是用数组来实现的,在没有指针操作的开发环境中,会用到这种方式来实现链表.
image.png
image.png
首先创建一个数组,这个数组的长度可以尽量的大;
数组的每个元素都是结构体,相当于一个节点,结构体是内存对齐的,不依赖指针,因此每个元素的内存空间是一样的;结构体有两个元素,一个是数据,相当于数据域(data),另一个是下个节点的下标,相当于指针域(cur);
数组的最后一个元素的cur存第一个元素的下标,相当于头结点;
数组的第一个元素的cur存最后一个节点的下一个下标,也就是第一个备用节点的下标;
最后一个节点的cur存0,表示后面没有节点了;
2.静态链表插入
从上面说的cur来看,插入操作就很容易想象了,就和动态链表一样,修改关键的几个节点的cur就可以了,假设要在2和3直接插入一个元素;
首先把元素放在第一个空位上,下标为x,也就是数组第一个元素的cur(前面说到存的是个下标),并且设置cur为元素3的cur;
然后修改元素2的cur为x;
和动态链表一样的两步操作.
过程表示
返回第一个空闲下标
完成插入
第一个函数中,space[0]就是数组第一个位置,它的cur存的是第一个空闲的下标i,获取之后将space[0]的cur修改成space[i]的cur,对于空闲元素来说,cur一般就是i+1,也就是他后面那个元素的下标.
第二个函数就像注释里写的那样,赋值,查找i,修改两个元素的cur.
3.静态链表删除
删除元素要分两步;
先前说到,末尾元素是头结点的作用,它的sur是第一个元素的下标,如果删除第一个,要修改头结点的sur,然后再释放节点;
第二步,被修改元素的cur修改为第一个元素的cur,第一个元素的cur修改为被删除元素的下标;这样第一个空闲被修改成了被删除元素,被删除元素的cur是原先的第一个空闲,现在是第二个了;
过程表示
删除第i个元素
接上图
优缺点
五:循环链表
当单链表访问到末尾节点的时候,无法逆向,也无法回到起点,将末尾节点的指针从NULL改成指向头结点,于是形成了循环链表.
循环链表
单链表的循环访问,当节点的指针为NULL时,遍历结束,而循环列表是当节点指针指向头结点时,遍历结束.
尾指针
不管是单链表还是循环链表,访问第一个节点是O(1),但是访问最后一节点都是O(n),因为总要从头开始往下找,那么能不能解决这个问题呢:
把头指针改成尾指针就可以了;
用尾指针rear表示一个链表时,访问第一个节点,是rear->next(到这里是头结点)->next,访问最后一个节点就是rear.这样就都是O(1).
六:双向链表
双向链表就是每个节点有两个指针,一个指向前驱节点,一个指向后继节点.
双向链表
双向循环空链表
双向循环非空链表
插入
双向链表插入时,首先设置新元素的prior和next,然后修改前驱元素,然后修改后继元素的prior,最后修改前驱元素的next.
删除
删除节点时,把前驱节点的next修改成后继节点的prior,然后把后继节点的prior修改成前驱节点的next.
线性表
网友评论