单链表的插入与删除.doc

《单链表的插入与删除.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、单链表的插入a已知P指针所指向的结点后插入一个元素x：b指针P所指向的结点前插入一个元素x：c线性表中值为y的元素前插入一个值为x的数据元素：1、大致步骤:插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。（1）找到ai-1存储位置p（2）生成一个数据域为x的新结点*s（3）令结点*p的指针域指向新结点（4）新结点的指针域指向结点ai2、算法描述a.已知P指针所指向的结点后插入一个元素xs=newNodeType;s->data=x;s->next=p->next;p->next=s;b指针p所指向的结点前插入一个元

2、素x：q=head;while(q->next!=p)//从头结点搜索一直到找到P所指的结点前一个结点q=q->next;s=newNodeType;s->data=x;s->next=p;q->next=s;c线性表中值为y的元素前插入一个值为x的数据元素：q=head;p=q->next;while(q->next!=NULL&&p->data!=y)q=p;p=p->next;s=newNodeType;s->data=x;Ss->next=pS;q->next=s;3、时间复杂度：O（n）二、单链表的删除1、具体步骤：  　（1）找到ai-1的存

3、储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）  　（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）  　（3）释放结点ai的空间，将其归还给"存储池"。2、算法描述①删除p所指向结点的后继结点（假设存在）Q=p->next;p->next=q->next;deleteq;②删除p所指向的结点。Q=head;While(q->next!=p)Q=q->next;q->next=p->next;deletep;③删除线性表中值为x的数据元素Q=head;P=q->next;While(q->nex

4、t!=NULL&&p->data!=x)Q=p;P=p->next;q->next=p->next;deletep;3、复杂度：O（n）链表上实现的插入和删除运算，无须移动结点，仅需修改指针。