线性表之循环与双向链表 - part04
线性表之循环与双向链表 - part04
循环链表
包括单链循环链表和双向循环链表。
1.定义：头尾相接的链表，最后一个结点的指针域指向头结点，整个链表形成一个环。
2.优点：从表中任一结点出发均可找到表中其他结点。
3.无空指针：
空表中，头结点的指针域指向自己。
遍历时终止条件是判断p是否等于头指针L。p!=L /p->next!=L
4.用尾指针比头指针方便，便于找a与a
5.带尾指针循环链表的合并
双向链表
为克服找前驱结点难的问题。
1.双向链表
2.双向链表结构的对称性
p->prior->next=p=p->next->prior
注意：在只已知p的情况下，改变指向不直接用p。因为一般不要改变p本身，而是改变前一个的后趋指向。
3.双向循环链表
双向链表的操作
查找与取长度等操作仅涉及一个方向的指针，从而算法与线性链表相同。但是插入与删除需要修改两个方向的指针。
1.双向链表的插入
2.双向链表的删除
所有链表的时间效率比较
顺序表和链表的比较
链式存储结构
优点：结点空间可以动态申请释放，插入和删除不需要移动数据元素。
缺点：存储密度小，每个结点的指针域占据额外空间。不是随机存取的，时间复杂度高。
存储密度=结点数据本身占用空间 / 结点占用的空间总量
线性表的应用
1.线性表的合并
La与Lb分别表示两个集合A和B，A=A∪B。
遍历Lb，循环终止条件为Lb长度。对Lb每个结点都遍历La找相同元素，找不到则插入。
可在函数内用顺序表或链表实现。
时间复杂度为O(Lb_len*La_len)。
2.有序表的合并
有序排列的La与Lb合并成有序排列的新线性表Lc。
用顺序表表示
新建表Lc，初始化Lc数组与长度值，同时建立指针pc，以及La、Lb的首指针与尾指针。
pa指示内容，数据内容小的存入表Lc（令当前pc=pa，且操作之后都+1，表示放入下一个pc位置，对比下一个pa位置内容）。
循环终止条件为pa<=pa_last&&pb<=pb_last，跳出循环则有的到达表尾，再对另一张表内元素依次添加即可。
时间复杂度为O(Lb_len+La_len)。空间复杂度为O(Lb_len+La_len)，因为新增额外的C表空间。
用链表表示
data小的结点如pa就接在pc后，然后pc右移，pa右移。循环终止条件为pa&&pb为空，最后一句把不为空的尾巴加在pc后。
时间复杂度为O(Lb_len+La_len)。空间复杂度为O(1)，结点重新连接，不占用额外空间。
案例分析与实现
1.一元多项式运算：
两个多项式相加相乘运算，一般运用顺序表。
存储一部分内容，即系数。因为指数对应下标了。
2.稀疏多项式的运算：
需要存储两部分内容，系数与指数。
一般运用链表。（因为空间分配不灵活、空间复杂度高）
链表是不需要开辟新存储空间的，只是从某个表的头结点开始，不断改变结点的指向，不需要的结点删除。顺序表则是取目标值存在新开辟的空间。
存在多项式的项相加为零的情况，项都要删去。但是注意要先保留副本，将新链表连接起来，再删除结点。
3.图书信息管理系统：
如果图书数量变化不频繁，经常查找，则用顺序表。反之则用链表。