单链表的插入和删除

Titianyeer

在单链表中，又如何实现“插入”和“删除”操作呢？
假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。
3 ^2 S& F3 ]8 X6 e) E8 ^; e为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在单链表中，根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的单链表所示。假设s为指向结点x的指针，则上述指针修改用语句描述即为
0 j) O# z' @/ i( @: E3 O5 e* [s->next=p->next；p->next=s；
8 F* p" r/ [* h- z反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为
p->next= p->next->next
: v: H5 f9 e  q% n/ ?# ~0 Y可见，在一直链表中元素插入或删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。
Status ListInsert_L(LinkList &L,inti,ElemType e){
//在带头结点的单链线性表L中第i个位置之前插入元素e
p=L；j=0；
while(p&&j<i-1){p=p->next;++j}//寻找第i-1个结点
) k/ T7 J( h; fif(!p||j>i-1)return ERROR;           //i小于1或者大于表长+1
s=(LinkList)malloc(sizeof(LNode));//生成新结点
- X* J- C  p6 k, w- |s->data=e;s->next=p->next;          //插入L中
p->next=s;
( x( ?/ v+ l3 t) r$ p6 D' A/ `return OK;
) M* M$ N3 n8 ?( x# c8 S}//ListInsert_L
void ListDelete_L(LinkList &L,inti,ElemType &e){
5 D1 |7 j9 d( {. K# ^$ P//在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
p=L;j=0;
$ T+ l" j4 X! @. c% o0 |while (p->next&&j<i-1){//寻找第i个结点，并令p指向其前驱
p=p->next;++j;
  K! |4 q9 g$ r5 t}
: M' ?2 l8 k- Fif(!(p->next||j>i-1)return ERROR;//删除位置不合理
% J, }% ^/ K/ q/ S' M7 l# X: a0 rq=p->next;p->next=q->next;  //删除并释放结点
1 J& [' K& h) V( E( P) Ce=q->data;free(q);
5 r$ H( ?& w1 ]* a. ireturn OK;
: i+ ~( _- r& o/ _5 W3 A5 f}//ListDelete_L

Gegu

谢谢O(∩_∩)O哈哈~谢谢O(∩_∩)O哈哈

sinsaina

感谢楼主分享！！！

sinsaina

支持楼主！谢谢分享！
; N. O# c3 v# A; P- {) G& ?1 N5 ]

wu68aq

学习了!3Q