问答题
假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。
【正确答案】(1)数据结构
同上题,采用不带有头结点的循环链表。
(2)思路
设置一个指针p,从s开始遍历整个表,停在s的前驱结点的前驱结点的位置,以便于删除s的前驱结点。
(3)算法
void deleteAheadElement(PNode s){
PNodeP,q;
p=s;
while(p->link->link!=s)p=p->link;
q=p->link;
p->link=s;
free(q);
}
(4)代价分析
该算法访问循环链表中每个结点最多一次,时间代价为O(n)。
【答案解析】