当前位置:   article > 正文

单链表的插入和删除_单链表插入与删除

单链表插入与删除

一、插入操作

按位序插入(带头结点):

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

  1. typedef struct LNode{
  2. ElemType data;
  3. struct LNode *next;
  4. }LNode,*LinkList;
  5. //在第i 个位置插插入元素e (带头结点)
  6. bool ListInsert(LinkList &L, int i,ElemType e){
  7. if( i<1)
  8. return false;
  9. LNode *p; //指针p指向当前扫描到的结点
  10. int j=0; //当前p指向的是第几个结点
  11. p = L; //L指向头结点,头结点是第0个结点(不存数据)
  12. while (p!=NULL &&j<i-1){ //循环找到第i-1个结点
  13. p=p->next;
  14. j++;
  15. }
  16. if(p==NULL) //i值不合法
  17. return false;
  18. LNode *s = (LNode *)malloc(sizeof( LNode) ) ;
  19. s->data = e;
  20. s->next=p->next;
  21. p->next=s; //将结点s连到p之后
  22. return true; //插入成功
  23. }

注意:上述代码s->next=p->next与p->next=s不能颠倒。

按位序插入(不带头节点):

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

  1. typedef struct LNode{
  2. ElemType data;
  3. struct LNode *next;
  4. }LNode,*LinkList;
  5. //在第i 个位置插插入元素e (带头结点)
  6. bool ListInsert(LinkList &L, int i,ElemType e){
  7. if( i<1)
  8. return false;
  9. if(i==1){ //插入第一个节点的操作与其他节点操作不同
  10. LNode *s = ( LNode *)malloc(sizeof( LNode) ) ;
  11. s->data = e;
  12. s->next=L;
  13. L=s; //头指针指向新结点
  14. return true;
  15. }
  16. LNode *p; //指针p指向当前扫描到的结点
  17. int j=1; //当前p指向的是第几个结点
  18. p = L; // p指向第1个结点(注意:不是头结点)
  19. while (p!=NULL &&j<i-1){ //循环找到第i-1个结点
  20. p=p->next;
  21. j++;
  22. }
  23. if(p==NULL) //i值不合法
  24. return false;
  25. LNode *s = (LNode *)malloc(sizeof( LNode) ) ;
  26. s->data = e;
  27. s->next=p->next;
  28. p->next=s; //将结点s连到p之后
  29. return true; //插入成功
  30. }

指定节点的后插操作:

  1. typedef struct LNode{
  2. ElemType data;
  3. struct LNode *next;
  4. }LNode,*LinkList;
  5. //后插操作:在p结点之后插入元素e
  6. bool InsertNextNode ( LNode *p,ElemType e){
  7. if ( p==NULL)
  8. return false;
  9. LNode *s = ( LNode *)malloc(sizeof( LNode) ) ;
  10. if (s==NULL) //内存分配失败
  11. return false;
  12. s->data = e; //用结点s保存数据元素e
  13. s->next=p->next;
  14. p->next=s; //将结点s连到p之后
  15. return true;
  16. }

指定节点的前插操作:

  1. //前插操作:在p结点之前插入元素e
  2. bool InsertPriorNode (LNode *p,ElemType e)

无法找到他的前驱节点,可以传入头指针

  1. //前插操作:在p结点之前插入元素e
  2. bool InsertPriorNode ( LinkList L,LNode *p,ElemType e)

但如果不能传入头指针上述方法就不能使用,依然无法解决问题。

可以申请一个新的节点s作为p的后继节点,把p中的数据复制到s中再把插入的数据放到p中完成前插操作。如下图所示:

  1. //前插操作:在p结点之前插入元素e
  2. bool InsertPriorNode (LNode *p,ElemType e){
  3. if ( p==NULL)
  4. return false;
  5. LNode *s = ( LNode *)malloc(sizeof( LNode ) ) ;
  6. if ( s==NULL) //内存分配失败
  7. return false;
  8. s->next=p->next;
  9. p->next=s; //新结点s 连到p之后
  10. s->data=p->data; //将p中元素复制到s中
  11. p->data=e; // p中元素覆盖为e
  12. return true;
  13. }

二、删除操作

按位序删除(带头结点):

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。

  1. typedef struct LNode{
  2. ElemType data;
  3. struct LNode *next;
  4. }LNode,*LinkList;
  5. bool ListDelete( LinkList &L, int i,ElemType &e){
  6. if(i<1)
  7. return false;
  8. LNode *p; //指针p指向当前扫描到的结点
  9. int j=0; //当前p指向的是第几个结点
  10. p = L; //L指向头结点,头结点是第0个结点(不存数据)
  11. while (p !=NULL && j<i-1){ //循外找到第i-1个节点
  12. p=p->next;
  13. j++;
  14. }
  15. if( p==NULL) //i值不合法
  16. return false;
  17. if( p->next == NULL) //第i-1个结点之后已无其他结点
  18. return false;
  19. LNode *q=p->next; //令q指向被删除结点
  20. e = q->data; //用e返回元素的值
  21. p->next=q->next; //将*q结点从链中“断开
  22. free(q); //释放结点的存储空间
  23. return true; //删除成功
  24. }

指定节点的删除:

  1. //删除指定结点p
  2. bool DeleteNode ( LNode *p)

方法1:传入头指针,循环寻找p 的前驱结点

方法2:类似于结点前插的实现

  1. //删除指定结点p
  2. bool DeleteNode ( LNode *p){
  3. if (p==NULL)
  4. return false;
  5. LNode *q=p->next; //令q指向*p的后继结点
  6. p->data=p->next->data; //和后继结点交换数据域
  7. p->next=q->next; //将*q结点从链中“断开”
  8. free(q); //释放后继结点的存储空间
  9. return true;
  10. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小桥流水78/article/detail/762080
推荐阅读
相关标签
  

闽ICP备14008679号