数据结构之单链表基本运算的实现[9]

if (!p)

{ printf(参数 i 错);

return (); /*第i个结点不存在不能删除*/

}

q=p>next; /*q指向第i个结点*/

p>next=q>next; /*从链表中删除*/

free(q); /*释放*s */

return ();

}

该算法同插入算法一样时间主要消耗在查找第i个元素结点上故其时间复杂度为O(n)

另外在上面插入和删除的算法中第一个元素结点的处理和其它结点是相同的因为在第一个元素结点之前有一个头结点(可以看作是第 个结点)所以我们在查找第i个元素结点时只要i值合法总能找到第i个结点的指针处理起来非常方便;如果采用不带头结点的单链表则需要对插入位置具体考虑在第一个元素结点之前插入时它没即可有直接前驱结点需修改头指针;而在其它结点之前插入时只要找到前驱结点地址(指针)进行正常插入即可在不带头结点的链表中删除结点时删除第一个结点和其它结点的处理也是不同的删除第一个结点要修改头指针变量其它结点删除只要修改其直接前驱的指针域即可有兴趣的读者可以考虑用不带头结点的单链表实现插入删除操作比较一下它们的区别以便进一步理解单链表的插入和删除操作的实现总之在通常情况下无表头结点的单链表在处理时往往比有表头结点的单链表更为复杂

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []