线性表的顺序结构
定义
用一段地址连续的存储单元一次存储线性表的数据元素
在内存中找了块地,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。
描述顺序存储结构需要三个属性
- 存储空间的起始位置
- 线性表的最大存储容量
- 线性表的当前长度
数据的长度是存放线性表的存储空间的长度,线性表长度是线性表中数据元素的个数
地址计算方法
数数是从1开始,可下标是从0开始,元素的序号和存放它的数组下表之间存在对应关系
存储器中的每个存储单元都有自己的编号,这个编号称为地址。(LOC表示获得存储位置的函数)
第i个数据元素的存储位置
LOC(ai)=LOC(a1)+(i-1)*C
可以随时算出线性表中任意位置的地址,存取时间性能为O(1),把具有这一特点的存储结构称为随机存取结构
顺序存储结构的插入与删除
获得元素
只要i
的数值在数组下标范围内,就是把数组第i-1
下标的值返回
插入操作
- 如果插入位置不合理,抛出异常
- 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量
- 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置
- 将要插入元素填入位置i处
- 表长加1
删除操作
- 如果删除位置不合理,抛出异常
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
- 表长减1
在存、读数据时,不管是哪个位置,时间复杂度都是O(1);而插入或删除时,时间复杂度都是O(n)
优缺点
优点
- 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时,难以确定存储空间的容量
- 造成存储空间的“碎片”
线性表的链式存储结构
线性表链式存储定义
特点:用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置。
现在链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。
为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像,称为节点。
n个节点链结成一个链表,即为线性表的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表。
头指针
-
链表中的第一个节点的存储位置叫做头指针
-
头指针具有标识作用,所以常用头指针冠以链表的名字
-
无论链表是否为空,头指针均不为空。头指针是链表的必要元素
头结点
- 在单链表的第一个结点前附设一个结点,称为头节点。头节点的数据域可以不存储任何信息
- 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
- 头结点不一定是链表必须要素
单链表的读取
- 声明一个结点P指向链表第一个结点,初始化j从1开始
- 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
- 若链表末尾p为空,则说明第i个元素不存在
- 否则查找成功,返回结点p的数据
最坏时间复杂度O(n),主要核心思想“工作指针后移”
单链表的插入
- 声明一结点P指向链表第一个结点,初始化j从1开始
- 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
- 若链表末尾p为空,则说明第i个元素不存在
- 否则查找成功,在系统中生成一个空结点s
- 将数据元素e赋值给s->data
- 单链表的插入标准语句:s->next=p-next; p->next-s;
- 返回成功
单链表的删除
- 声明一结点p指向链表第一个结点,初始化j从1开始
- 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
- 若链表末尾p为空,则说明第i个元素不存在
- 否则查找成功,将欲删除的结点p->next赋值给q
- 单链表的删除标准语句p->next=q->next
- 将q结点中的数据赋值给e,作为返回
- 释放q结点
单链表插入和删除算法,第一部分是遍历查找第i个元素,第二部分是插入和删除元素。时间复杂度都是O(n)。在不知道第i个元素指针的位置,单链表数据结构在插入和删除操作上,与线性表的顺序存储结构没有太大优势,但对于插入或删除数据越频繁的操作,单链表的优势就越明显
单链表的整表创建
对于每个链表来说,它所占用空间的大小和位置都不需要预先分配,根据系统的情况和实际的需求即时生成。
创建单链表的过程就是一个动态生成链表的过程,即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表
单链表结构与顺序存储结构优缺点
存储分配方式
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
时间性能
- 查找
- 顺序存储结构O(1)
- 单链表O(n)
- 插入和删除
- 顺序存储结构需要平均移动表长一半的元素,时间为O(n)
- 单链表在找出某位置的指针后,插入和删除时间仅为O(1)
- 空间性能
- 顺序存储结构需要预分配存储空间,分大了,浪费,分小了,易发生上溢
- 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点,就使得整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表
循环链表解决了一个很麻烦的问题,如何从当中一个结点出发,访问到链表的全部结点。
为了使空链表与非空链表处理一致,通常设一个头结点。
可以用O(1)的时间访问第一个结点,但对于要访问到最后一个结点,却需要O(n)时间。使用尾指针来表示循环链表,此时查找开始结点和终端结点都很方便了。
终端结点用尾指针rear指示,则查找终端结点是O(1),而开始结点,其实就是rear->next->next,其时间复杂也为O(1)
双向链表
在单链表的每个结点中,再设置一个指向其前驱结点的指针域
插入
先搞定s的前驱和后继,再搞定后结点的前驱,最后解决前结点的后继
删除
- 把p->next 赋值给p->prior的后继
- 把p->prior赋值给p->next的前驱
双向链表相对于单链表来说,要更复杂一些,毕竟它多了prior指针,对于插入和删除时,需要格外小心。另外由于每个结点都需要记录两份指针,所以在空间上时要占用略多一些的。不过,由于它的良好对称性,使得对某个结点的前后结点操作,带来了方便,用空间换了时间