一、静态单链表
在不支持动态空间分配的环境中,要使用链表存储数据,那么可采用静态链表的方法:即在一块预分配的存贮空间中,用下标作为指针链来构成链式结构。
//既然是静态链表,那么可以使用一维数组实现存储,java没有指针,那么就用这来使用链表结构
//在不支持动态空间分配的环境中,要使用链式结构技术,可采用静态链表的方法:即在一块预分配的存贮空间中,用下标作为指针。
//存储结构:在数组中增加一个“指针”域,存放下一元素在数组中的下标。且0为代表空指针
//设s为slinklist型变量,若第i个分量表示链表的第k个结点,则s[i].cur指示第k+1个结点的位置。i=s[i].cur相当于指针后移p=p->next
//头结点数据域空,游标(指示器,指针的意思)是1,代表指向第一个结点,头结点本身下标为0
因为静态分配不会和动态那样,可以手动释放内存,那么如何知道数组里哪些分量没有被使用?
//办法:把所有没有被使用的和被删除的分量用 cur 连接为一个新表叫备用表,插入时,从备用表里取得第一个结点,作为插入结点,删除时把删除的结点链接到备用表
存储结构:
在数组中给每一个元素增加一个“指针”域,(一个数据域,一个“指针”域)存放下一元素在数组中的下标。不改变元素的物理位置!通过增加的指针域的重新链接,改变数组元素的逻辑顺序,且存储空间在运行期间不会动态的改变,也就是是静态链表的实现。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
实现
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
二、循环链表
所谓循环,就是到尾结点,没有空指针,尾结点反而指向了头结点,成环,说白了,就是尼玛头尾张一起了。那么从环中的任意一个结点都能达到表里其他结点,可以循环单恋,也可以多重链起来,俗话说的好,掌握好了单链表的思想和存储,那么一切都是变化罢了,思想没有变。操作大概一样。
差别:
1、循环条件变了,没有空指针,那么循环遍历的终止条件就是看尾指针指向头结点的时候
2、对于循环单链表,又有演化:
如果是头指针表示的循环单链,那么找最后一个元素时间复杂度是 o(n),不过,如果是尾指针表示的,那么找第一个元素是 p->next->next,找最后一个元素是 p 就行了,时间复杂度才是0(1)。
比如:要求合并两个循环单链表a 和 a,该怎么做?
因为是循环的,链表,那么只需要操作两个指针就行,时间复杂度为 o(1)
//此图时间复杂度不是1,应该在这里体现尾指针的方便,需要让两个表的头指针分别变味尾指针,才是操作两个指针(假设是尾指针)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
这样是不是非常方便。
三、双链表和循环
单链表的结点,有指示后继的指针域→,找后继结点方便;查找某结点的后继结点的执行时间为o(1)。 没有指示前驱的指针域→,找前驱结点难,从表头出发查找。 即:查找某结点的前驱结点的执行时间为o(n)。这时候双链表应运而生!
双向链表:在单链表的每个结点里再增加一个指向其直接前驱的指针prior ,这样链表中就形成了有两个方向不同的链,故称为双向链表。
双向链表也可以有循环,让头结点的前驱指针指向链表的最后一个结点,让最后一个结点的后继指针指向头结点。 这里需要注意一下空的双向循环链表的表示:
俗话就是自己干自己的情形,说明是空表,只有一个孤单的头结点
双向链表还要一个特点:对称性,比如结点 p,那么存在如下语句
双向链表,有些操作 (如:listlength、getelem等) ,仅涉及一个方向的指针,算法与线性链表的相同。但插入、删除,则需同时修改两个方向上的指针。这是双向链表的一个难点。
还是用循环双向链表举例:c 99新特性 bool 类型,需要使用#include <stdbool.h>,还有随用虽定义的变量,很爽了,和 c++兼容性越来越强!
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
最重要的就是插入和删除算法!插入和删除两者的操作关键前提步骤就是获得操作对象的前驱的那一步,而表长为 n 的话,那么时间复杂度均为 o(n)。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
打印:
建循环双向链表
循环双向链表初始化之后是空表么?
表是空的
循环双向链表的表长?
插入一些结点
循环双向链表插入之后是空表么?
表不空
5
遍历(正向)循环双向链表
0 1 2 3 4
删除第二个结点,1
1
0 2 3 4
销毁循环双向链表
program ended with exit code: 0
小结:关键字:顺序、链式,静态、动态
1、顺序存储特点:
逻辑顺序与物理顺序一致,本质上是用数组存储线性表的各个元素(即随机存取);存储密度大,存储空间利用率高,可以任意访问任意结点。但是插入删除不方便,需要移动大量元素。是时间换取空间。
2、链式存储特点:
元素之间关系采用元素所在的节点的”指针”信息表示(插、删不需要移动节点)。结点空间可以动态申请和释放,数据元素的逻辑次序靠结点的指针来指示,插入和删除时不需要移动数据元素。链式存储结构的缺点:每个结点的指针域需额外占用存储空间。当数据域所字节不多时,指针域所占存储空间的比重显得很大。链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结点,这增加了算法的复杂度。不便于在表尾插入元素:需遍历整个表才能找到位置。 链表插入、删除运算的快捷是以空间代价来换取时间。
3、静态存储特点:
在程序运行的过程中不用考虑追加内存的分配问题。
4、动态存储特点:
可动态分配内存,有效利用内存资源,使程序具有可扩展性。
线性表逻辑结构特点:只有一个首结点和尾结点;除首尾结点外其他结点只有一个直接前驱和一个直接后继。线性结构的逻辑关系是一对一(1:1)的。
辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4064120.html