线性表-顺序表与链表-堆栈与队列你应该知道的原理
线性表
数据结构的一种排列、组织方式,它是线性的
分类
大纲我们有一个图,可以回顾一下。
根据元素存储结构来划分的,顺序存储结构和链式存储结构。
1. 顺序表
2. 链表
存储空间虽然是离散的,一块一块的,但是通过逻辑上的一个指针的联系,在逻辑上实现一个整体。
3 链表的类别(主要来看链表)
单链表
单链表最后一个节点 为null
循环链表
最后一个为指针
双链表
最后一个有两个指针,可以形成两条链,叫做双链表。
双链表 灵活性,会大于其他。
4 链表的操作
单链表的删除
我要删除 a2
方法:
把 a1 的 next(指针)域 直接指向 a3,跳过 a2,那就可以了,等于a2已经被删除了。
再去,释放 节点a2,free a2
,就完成了。
简单说就是,把前驱节点 a1
指向 后驱节点 a3
。
单链表的节点插入
把 新的节点,从要插入的位置。
把 前驱节点 要插入的 next域 指向 新加入节点,再把 新加入节点的 next域 指向 下一个节点就可以了。
但是实际上的操作,我们不能直接替换,
a2本来指针可表示为 p->next,如果我们让 p->next 直接指向 如图的 s,则他会发生变化,发生变化后,就无法把后面一截连起来了。
那么如何操作呢?
- 我们定义一个 s节点
- 把s 指向 p节点的 下一个节点, p->next
- 把 s->next 赋值为 p->next
双链表的节点删除
双链表的节点插入
此图,从左往右看,1 2 3 4步骤。 先完成,1 2,再完成 3 4
- 新节点的 前驱 指向 a1 后驱 指向 a2
- 接下来,再完成第二步赋值即可。
5. 顺序表与链表的比较
何为存储密度?
固定的(比如说内存)区域,存储的元素越多,密度越高。2K空间,一个存了200个数据,一个存了2000个数据。则2000个数据的,密度高。为什么 顺序存储好?
因为就一个空间,而链式存储还需要1.5个空间,因为还要存指针。容量分配
链式存储可以随时增减空间。 顺序存储必须 事先确定
时间性能
插入删除运算
对于链表来说:
我们只是一个节点的操作指向, 操作起来就是一个常量,所以他们时间复杂度为 O(1)
对于顺序存储来说:
你删除或者添加一个,都需要把后面的,位置也移动一遍。 虽然看起来非常容易,但是时间消耗在移动操作上。
所以明显 插入删除运算 链式存储 优于 顺序存储
- 查找运算
相同,因为他们都是 从第一个 往第二,三个查找。
特殊情况,顺序存储,123456 从小到大,我们可以使用 二分法查找,就会顺序结构比链式存储快。
- 读运算
顺序存储, 依次存储,他的偏移量 是可以 直接计算出来的。比如第一个为 000,第八个是多少?直接加上偏移量7即可,那就是007/ (从 0开始计算。) 这种存储方式称为随机存储,想存储哪一个元素 就是存储哪一个元素。
而链表就无法这样做。
必须一个一个 next,一直查找查找。
6. 栈 -先进后出
栈,不是一个实实在在存在的东西,是逻辑上概念,一种思想,一种概念。
并不像 顺序存储,链式存储那样,一种一种很有规律的。
栈是在其之上的一种逻辑单元。
我们只要给 栈 定义一个规则 先进后出就可以了
比如: 你往箱子里 塞 如 笔记本, 毛巾, 散热器, 鼠标垫。
那么你拿出来,就得是 鼠标垫,散热器,毛巾,笔记本。
这就是 先进后出。
那我们栈,能不能 1 2 3 4 进去,然后 1 2 3 4出来呢?
可以,如果你的栈是不是如上图,那就行。
7. 队列(先进先出)
排队挂号,能理解吧。。。
顺序结构队列
特殊队列(循环队列)
队列指针,转转转,转一圈,又回到了,原点。(爱的魔力转圈圈。。。。)
如图,如果队列没有记录任何元素的时候,头指针,尾指针都指向同一个 元素 . 且元素当中的值是空的。
记录一个元素之后,比如我在 0 存入一个 X, 则 队头指针不变,队尾指针会 后移一位,再存入,又后移一位。以此类推。
判断循环队列 是满还是空状态?
问题,当我在最后一个地方,存入一个 Z 的时候,我的 tail 指针就又回来了(因为是循环队列)。
以前 如果 head = tail 我们就是 空情况, 而现在 又回来了,是 队列满的情况,也相等。
也就是说我们发现了,我们不知道 如何判断 循环 队列 是空还是满队列。
解决办法: 牺牲一个空间,这个空间 我们不用来存放数据/
就是 当 tail 指针,为指向这个空间时候。就满了。
如何判断,就是 tail + 1 = head 则循环队列满了。
感谢关注
上海PHP自学中心-免费编程视频教学|Python教学|Web开发教学|全栈开发教学|加密与解密|Linux教学|Golang教学|
]
@author wangchunbo