五、删除元素操作
和插入类似，由于删除元素
改变了元素之间的关系，使 
不再是
的后继，而是 
的后继，因此需要修改
元素所在结点的指针。因此在单链表中删除元素操作的算法基本思想和插入相同，也是：首先找到第 i-1 个结点，然后修改相应指针。
算法2.17bool ListDelete ( SLink &L, int pos, ElemType &e)
{
// 若1≤pos≤LengthList(L)，则删除指针L指向头结点的单链表
// 中第 pos 个元素并以 e 带回其值，返回函数值为 TRUE，
// 否则不进行删除操作且返回函数值为 FALSE
p = L; j = 0;
while (p->next && j < i-1)
{ // 寻找第pos个结点，并令p指向其前驱
p = p->next; ++j;
}
if (!(p->next) || j > i-1)
return FALSE; // 删除位置不合理
q = p->next; p->next = q->next; // 修改指针
e = q->data; delete(q); // 释放结点空间
return TRUE;
} // ListDelete_L
算法时间复杂度为O (ListLength(L))。
|
|||
|
你是否注意到了，在删除算法中参数不合理的判断条件和插入的情况不同？为什么？
|
|||
|
算法时间复杂度的分析：
显然，和插入一样，其时间消耗在查询前驱结点上。