• 例1-6：在单链表中实现线性表的插入运
算INSERT (L,x,i)
算法思想：
(1)先求出第i-1个结点
(2)然后在第i-1个结点之后插入结点x 。
1
• 按序号查找
设单链表的长度为n，要查找表中第i个
结点，算法思想如下：
从头结点开始顺链扫描，用指针p指向当
前扫描到的结点，用j作统计已扫描结点
数的计数器，当p扫描下一个结点时，j
自动加1。
P的初值指向头结点，j的初值为0。
当j=i时，指针p所指的结点就是第i个结
点。
2
• 按序号查找算法描述
JD *GET(head,i)
JD *head;
int i;
{int j;
JD *p;
p=head;j=0;
while((p->next!=null&&(j
{p=p->next;j++;}
if (i=j) return p; /*找到第i个结点*/
else return null; /*找不到，收返回null*/
}/*end*/
3
• 例1-6的实现：
INSERT (L,x,i)
JD *L;
datatype x;
int i;
{JD *p;
int j;
j=i-1;
p=GET(L ，j )；/*找到第i-1个结点*p*/
if (p==null) printf(“找不到插入点\n“ )
else INSERA(p,x);
}/*end*/
4
(4)删除运算
(删除单链表中*p的后继)
• 规格(结点类型)说明见单链表描述。
• 算法描述：
DeleteA(p) /*删除*p的后继结点*r,设*r存在*/
JD *p;
{JD *r;
if(p->next!=null)
r=p->next; p r
p->next=r->next; 存储池
free(r);
}
}/*enddelete*/
5
• 思考：
(1)如何删除单链表中p结点本身？
(2 )如何删除单链表中p结点的前趋结
点？
例1-7：在单链表上实现线性表的删除运
算Delete(L,i) 。
思想：先找到被删结点(第i个)的前趋
结点，即第i-1个结点*p,然后删除*p的后
继( 需引用函数GET (L,i) ) 。
6
• 例1-7的实现：
DELETE(L,i)
JD *L;
int i;
{JD *p;
int j;
j=i-1;
p=GET(L ，j) ；/*找到第i-1个结点*p*/
if ((p!=null)&&(P->next!=null))
DeleteA(P);
else printf(“error
