链表的基本操作增删查改C语言实现 [复制链接]

本节讲解链表的基本操作，包括向链表中添加数据、删除链表中的数据、查找和更改链表中的数据。

首先，创建一个带头结点的链表，链表中存储着{1,2,,4}：

//链表中节点的结构typedefstructlink{intelem;structlink*next;}Link;Link*initLink(){inti;//1、创建头指针Link*p=NULL;//2、创建头结点Link*temp=(Link*)malloc(sizeof(Link));temp-elem=0;temp-next=NULL;//头指针指向头结点p=temp;//、每创建一个结点，都令其直接前驱结点的指针指向它for(i=1;i5;i++){//创建一个结点Link*a=(Link*)malloc(sizeof(Link));a-elem=i;a-next=NULL;//每次temp指向的结点就是a的直接前驱结点temp-next=a;//temp指向下一个结点（也就是a),为下次添加结点做准备temp=temp-next;}returnp;}

提示：想系统学习数据结构的小伙伴，我原创了一整套数据结构和算法教程（C语言版）：

同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下种情况：

插入到链表的头部，作为首元节点；

插入到链表中间的某个位置；

插入到链表的最末端，作为链表中最后一个结点；

对于有头结点的链表，种插入元素的实现思想是相同的，具体步骤是：

将新结点的next指针指向插入位置后的结点；

将插入位置前结点的next指针指向插入结点；

例如，在链表{1,2,,4}的基础上分别实现在头部、中间、尾部插入新元素5，其实现过程如图1所示：

图1带头结点链表插入元素的种情况

从图中可以看出，虽然新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤1，再执行步骤2。实现代码如下：

voidinsertElem(Link*p,intelem,intadd){inti;Link*c=NULL;Link*temp=p;//创建临时结点temp//首先找到要插入位置的上一个结点for(i=1;iadd;i++){temp=temp-next;if(temp==NULL){printf("插入位置无效\n");return;}}//创建插入结点cc=(Link*)malloc(sizeof(Link));c-elem=elem;//①将新结点的next指针指向插入位置后的结点c-next=temp-next;//②将插入位置前结点的next指针指向插入结点；temp-next=c;}

注意：链表插入元素的操作必须是先步骤1，再步骤2；反之，若先执行步骤2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤1。

对于没有头结点的链表，在头部插入结点比较特殊，需要单独实现。

图2不带头结点链表插入元素的种情况

和2)、)种情况相比，由于链表没有头结点，在头部插入新结点，此结点之前没有任何结点，实现的步骤如下：

将新结点的指针指向首元结点；

将头指针指向新结点。

实现代码如下：

Link*insertElem(Link*p,intelem,intadd){if(add==1){//创建插入结点cLink*c=(Link*)malloc(sizeof(Link));c-elem=elem;c-next=p;p=c;returnp;}else{inti;Link*c=NULL;Link*temp=p;//创建临时结点temp//首先找到要插入位置的上一个结点for(i=1;iadd-1;i++){temp=temp-next;if(temp==NULL){printf("插入位置无效\n");returnp;}}//创建插入结点cc=(Link*)malloc(sizeof(Link));c-elem=elem;//向链表中插入结点c-next=temp-next;temp-next=c;returnp;}}

注意当add==1成立时，形参指针p的值会发生变化，因此需要它的新值作为函数的返回值返回。

从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除。对于有头结点的链表来说，无论删除头部（首元结点）、中部、尾部的结点，实现方式都一样，执行以下三步操作：

找到目标元素所在结点的直接前驱结点；

将目标结点从链表中摘下来;

手动释放结点占用的内存空间；

从链表上摘除目标节点，只需找到该节点的直接前驱节点temp，执行如下操作：

temp-next=temp-next-next;

例如，从存有{1,2,,4}的链表中删除存储元素的结点，则此代码的执行效果如图所示：

图带头结点链表删除元素

实现代码如下：

//p为原链表，elem为要删除的目标元素intdelElem(Link*p,intelem){Link*del=NULL,*temp=p;intfind=0;//1、找到目标元素的直接前驱结点while(temp-next){if(temp-next-elem==elem){find=1;break;}temp=temp-next;}if(find==0){return-1;//删除失败}else{//标记要删除的结点del=temp-next;//2、将目标结点从链表上摘除temp-next=temp-next-next;//、释放目标结点free(del);return1;}}

对于不带头结点的链表，需要单独考虑删除首元结点的情况，删除其它结点的方式和图完全相同，如下图所示：

实现代码如下：

//p为原链表，elem为要删除的目标元素intdelElem(Link**p,intelem){Link*del=NULL,*temp=*p;//删除首元结点需要单独考虑if(temp-elem==elem){(*p)=(*p)-next;free(temp);return1;}else{intfind=0;//1、找到目标元素的直接前驱结点while(temp-next){if(temp-next-elem==elem){find=1;break;}temp=temp-next;}if(find==0){return-1;//删除失败}else{//标记要删除的结点del=temp-next;//2、将目标结点从链表上摘除temp-next=temp-next-next;//、释放目标结点free(del);return1;}}}

函数返回1时，表示删除成功；返回-1，表示删除失败。注意，该函数的形参p为二级指针，调用时需要传递链表头指针的地址。

在链表中查找指定数据元素，最常用的方法是：从首元结点开始依次遍历所有节点，直至找到存储目标元素的结点。如果遍历至最后一个结点仍未找到，表明链表中没有存储该元素。因此，链表中查找特定数据元素的C语言实现代码为：

//p为原链表，elem表示被查找元素intselectElem(Link*p,intelem){inti=1;//带头结点，p指向首元结点p=p-next;while(p){if(p-elem==elem){returni;}p=p-next;i++;}return-1;//返回-1，表示未找到}

注意第5行代码，对于有结点的链表，需要先将p指针指向首元结点；反之，对于不带头结点的链表，注释掉第5行代码即可。

更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。直接给出链表中更新数据元素的C语言实现代码：

//p为有头结点的链表，oldElem为旧元素，newElem为新元素intamendElem(Link*p,intoldElem,intnewElem){p=p-next;while(p){if(p-elem==oldElem){p-elem=newElem;return1;}p=p-next;}return-1;}

函数返回1，表示更改成功；返回数字-1，表示更改失败。如果是没有头结点的链表，直接删除第行代码即可。

以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程及C语言代码，最后给大家一段完整的代码，实现对有头结点链表的“增删查改”：

#includestdio.h#includestdlib.h//链表中节点的结构typedefstructlink{intelem;structlink*next;}Link;Link*initLink(){inti;//1、创建头指针Link*p=NULL;//2、创建头结点Link*temp=(Link*)malloc(sizeof(Link));temp-elem=0;temp-next=NULL;//头指针指向头结点p=temp;//、每创建一个结点，都令其直接前驱结点的指针指向它for(i=1;i5;i++){//创建一个结点Link*a=(Link*)malloc(sizeof(Link));a-elem=i;a-next=NULL;//每次temp指向的结点就是a的直接前驱结点temp-next=a;//temp指向下一个结点（也就是a),为下次添加结点做准备temp=temp-next;}returnp;}//p为链表，elem为目标元素，add为要插入的位置voidinsertElem(Link*p,intelem,intadd){inti;Link*c=NULL;Link*temp=p;//创建临时结点temp//首先找到要插入位置的上一个结点for(i=1;iadd;i++){temp=temp-next;if(temp==NULL){printf("插入位置无效\n");return;}}//创建插入结点cc=(Link*)malloc(sizeof(Link));c-elem=elem;//①将新结点的next指针指向插入位置后的结点c-next=temp-next;//②将插入位置前结点的next指针指向插入结点；temp-next=c;}//p为原链表，elem为要删除的目标元素intdelElem(Link*p,intelem){Link*del=NULL,*temp=p;intfind=0;//1、找到目标元素的直接前驱结点while(temp-next){if(temp-next-elem==elem){find=1;break;}temp=temp-next;}if(find==0){return-1;//删除失败}else{//标记要删除的结点del=temp-next;//2、将目标结点从链表上摘除temp-next=temp-next-next;//、释放目标结点free(del);return1;}}//p为原链表，elem表示被查找元素intselectElem(Link*p,intelem){inti=1;//带头结点，p指向首元结点p=p-next;while(p){if(p-elem==elem){returni;}p=p-next;i++;}return-1;//返回-1，表示未找到}//p为有头结点的链表，oldElem为旧元素，newElem为新元素intamendElem(Link*p,intoldElem,intnewElem){p=p-next;while(p){if(p-elem==oldElem){p-elem=newElem;return1;}p=p-next;}return-1;}//输出链表中各个结点的元素voiddisplay(Link*p){p=p-next;while(p){printf("%d",p-elem);p=p-next;}printf("\n");}//释放链表voidLink_free(Link*p){Link*fr=NULL;while(p-next){fr=p-next;p-next=p-next-next;free(fr);}free(p);}intmain(){Link*p=initLink();printf("初始化链表为：\n");display(p);printf("在第的位置上添加元素6：\n");insertElem(p,6,);display(p);printf("删除元素4：\n");delElem(p,4);display(p);printf("查找元素2：\n");printf("元素2的位置为：%d\n",selectElem(p,2));printf("更改元素1的值为6：\n");amendElem(p,1,6);display(p);Link_free(p);return0;}

执行结果为：

初始化链表为：在第的位置上添加元素6：删除元素4：查找元素2：元素2的位置为：2更改元素1的值为6：