|
|
知识路径： > 计算机科学基础 > 常用数据结构 > 线性表及链表 > 线性表 >
|
被考次数：2次
被考频率：低频率
总体答错率：41%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：5个
|
|
|
|
|
带头节点的单链表和不带头节点的单链表的区别主要体现在其结构上和算法操作上。
|
|
|
|
在结构上，带头节点的单链表不管链表是否为空，均含有一个头节点；而不带头节点的单链表不含头节点。
|
|
|
|
在操作上，带头节点的单链表的初始化为申请一个头节点，且在任何节点位置进行的操作算法一致；而不带头节点的单链表让头指针为空，同时其他操作要特别注意空表和第一个节点的处理。下面列举带头节点的单链表插入操作和不带头节点的插入操作的区别。
|
|
|
|
|
|
|
|
1）带头节点的单链表插入函数insert（Slink *head, int i, ElemType x）
|
|
|
|
带头节点的单链表插入函数的设计思想是：创建一个data域值为x的新节点*p，然后插入到head所指向的单链表的第i个节点之前。为保证插入正确有效，必须查找到指向第i个节点的前一个节点的指针，主要的时间耗费在查找上，因而在长度为n的线性单链表中进行插入操作的时间复杂度为O（n）。
|
|
|
|
2）不带头节点的单链表插入函数insert（inti, ElemTypex）
|
|
|
|
不带头节点的单链表插入函数的设计思想是：创建一个data域值为x的新节点*p，然后插入到单链表的第i个节点之前。由于不带头节点，当插入位值i=1时，其算法与i>1时有很大差别，必须单独处理。为保证插入正确有效，必须查找到指向第i个节点的前一个节点的指针，主要的时间耗费在查找上，因而在长度为n的线性单链表中进行插入操作的时间复杂度为O（n）。
|
|
|
|
可见，带头节点的单链表插入操作和不带头节点的插入操作在算法实现上有很大的区别，主要体现在初始化、能否插入成功的判别及插入时的操作上，在带头节点的单链表上插入在任何位置上都是相同的，而在不带头节点单链表的第一个节点和其他节点前插入操作是不同的。
|
|
|
|
对于带头节点的单链表和不带头节点的单链表在其他操作上的区别可类似得到。
|
|
|
