在链表的第i个节点的后面插入一个新节点的基本算法如下：
（1）定位第i个节点。让指针q指向第i个节点，指针p指向需要插入的节点。
（2）链接后面指针。p-link = q->link。
（3）链接前面指针。q->link=p。
第一步：查找结点值（这里存在两种方法）
1：按序号查找结点值
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
按序号查找结点值的算法如下：
/*
参数：
LinkList L 头节点
int i 节点序号
*/
LNode GetElem(LinkList L,int i)
{
//本算法取出单链表L（带头结点）中第i个位置的结点指针
int j=1; //计数，初始为1
LNode *p = L->next; //头结点指针赋给p
（此时，P就是第一个节点了）
if(i==0)
return L; //若i等于0，则返回头结点
if(i<1)
return NULL; //若 i 无效，则返回 NULL
//
//从第1个结点开始找，查找第i个结点， 但i=1的时候，直接跳过while，返回p， 此时的p其实就是第一个节点；
return p; //返回第i个结点的指针，如果i大于表长，p=NULL，直接返回p即可
2：按值查找表结点
从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针。若整个单链表中没有这样的结点，则返回NULL。按值查找结点的算法如下：
LNode *LocateElem (LinkList L, ElemType e)
{
//本算法查找单链表 L （带头结点）中数据域值等于e的结点指针，否则返回NULL
LNode *p=L->next;
while( p!=NULL && p->data!=e) //从第1个结点开始查找data域为e的结点
p=p->next;
return p; //找到后返回该结点指针，否则返回NULL
}
按值查找操作的时间复杂度为O(n)。
第二步：插入结点
插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
算法首先调用上面的按序号查找算法GetElem(L, i-1)，查找第i-1个结点。假设返回的第i-1个结点为*p，然后令新结，点*s的指针域指向*p的后继结点，再令结点*p的指针域指向新插入的结点*s。其操作过程如图所示。
![]()
单链表的插入操作
实现插入结点的代码片段如下：
p=GetElem(L, i-1) ; // 语句①，查找插入位置的前驱结点
s->next=p->next; // 语句②，图中辑作步骤 1
p->next=s; // 语句③，图中操作步骤2
算法中，语句②③的顺序不能颠倒，否则，当先执行p->next=s后，指向其原后继的指针就不存在了，再执行s->next = p->next时，相当于执行了 s->next=s,显然是错误的。本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若是在给定的结点后面插入新结点，则时间复杂度仅为O(1)。
阅读(5270) | 评论(0) | 转发(0) |
