【数据结构篇】~单链表（附源码）

链表前言

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
1、链式机构在逻辑上是连续的，在物理结构上不一定连续​
2、结点一般是从堆上申请的​
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续​当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个结点的地址（当下一个结点为空时保存的地址为空）。
当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。
如图：
既然链表是有一个个节点组成的那我们就可以把它看成一个小火车！

链表的实现

1.头文件

#pragmaonce#include#include#includetypedefintsldatatype;//因为不知道要保存什么类型的数据//定义节点的结构体typedefstructslistnode{ sldatatype data;//保存的数据structslistnode*next;//指向下一个结构体的指针}slnode;voidslprint(slnode*phead);//打印链表(这里要传链表头的地址，以确保能找到链表)//phead的作用就和火车头差不多slnode*slbuynode(sldatatype);//申请新节点voidslpushback(slnode**pphead,sldatatype x);//尾插（因为要通过函数改变数据所以就要传‘址’调用，不能‘传值’）//所以这里是‘二级’指针！voidslpushfornt(slnode**pphead,sldatatype x);//头插voidslpopback(slnode**pphead);//尾删voidslpopfornt(slnode**pphead);//头删//查找slnode*slfind(slnode*phead,sldatatype x);//在指定位置之前插入数据voidslinsert(slnode**pphead,slnode*pos,sldatatype x);//删除pos结点voidslerase(slnode**pphead,slnode*pos);//在指定位置之后插入数据voidslinsertAfter(slnode*pos,sldatatype x);//删除pos之后的结点voidsleraseAfter(slnode*pos);//销毁链表voidsldestroy(slnode**pphead);

2.源文件

#include"slist.h"//断言pphead的目的是不能对空地址进行解引用！voidslprint(slnode*phead)//打印链表{ slnode*pcur =phead;while(pcur){ printf("%d->",pcur->data);//打印数据pcur =pcur->next;//改变purc的指向，让它指向下一个节点}printf("NULL\n");}slnode*slbuynode(sldatatype x)//申请新节点{ slnode*newnode =(slnode*)malloc(sizeof(slnode));//一开辟空间就要检查是否开辟成功if(newnode==NULL){ perror("malloc fail");}newnode->data =x;newnode->next =NULL;returnnewnode;}voidslpushback(slnode**pphead,sldatatype x)//尾插(pphead==&plist){ slnode*pcur =*pphead;//既然要插入数据那么就要开辟新空间（新节点）slnode*newnode =slbuynode(x);assert(pphead);if(*pphead==NULL)//如果是空链表（plist==null）{ *pphead =newnode;newnode->data =x;}else//不是空链表{ while(pcur->next){ pcur =pcur->next;}newnode->data =x;pcur->next =newnode;}}voidslpushfornt(slnode**pphead,sldatatype x)//头插{ //既然要插入数据那么就要开辟新空间（新节点）slnode*newnode =slbuynode(x);assert(pphead);newnode->next =*pphead;//为了把新结点和原来的链表连起来*pphead =newnode;}voidslpopback(slnode**pphead)//尾删{ //删除时，pphead（不能对null进行解引用）和头节点（不然没意义了）都不能为空assert(pphead&&*pphead);if((*pphead)->next==NULL)//只有一个节点{ free(*pphead);(*pphead)->next =NULL;}else{ slnode*ptail =*pphead;slnode*prev =NULL;while(ptail->next)//跳出循环时ptail就是最后一个节点{ prev =ptail;ptail =ptail->next;}prev->next =NULL;free(ptail);ptail =NULL;}}voidslpopfornt(slnode**pphead)//头删{ //删除时，pphead（不能对null进行解引用）和头节点（不然没意义了）都不能为空assert(pphead &&*pphead);slnode*node =(*pphead)->next;//(->)的优先级大于（*（解引用））所以要用（）free(*pphead);*pphead =NULL;*pphead =node;}//查找//因为查找数据不需要改变链表内容所以这里传一级指针slnode*slfind(slnode*phead,sldatatype x){ assert(phead);//不能在空链表中查找数据slnode*node =phead;while(node){ if(x ==node->data){ returnnode;}node =node->next;}returnNULL;}//在指定位置之前插入数据（要改变的指针有pos的前驱节点和pos）voidslinsert(slnode**pphead,slnode*pos,sldatatype x){ assert(pphead);assert(pos);slnode*newnode =slbuynode(x);if(pos ==*pphead)//pos是头节点就调用’头插‘{ slpushfornt(pphead,x);}else//pos不是头节点{ slnode*prev =*pphead;//定义pos的前一个节点以便连接while(prev->next!=pos){ prev =prev->next;}//出循环就代表pos的前驱节点已找到！newnode->next =pos;prev->next =newnode;}}//在指定位置之后插入数据//在pos后插入数据要改变的指针有（pos、pos->next）voidslinsertAfter(slnode*pos,sldatatype x){ assert(pos);slnode*newnode =slbuynode(x);slnode*next =pos->next;newnode->next =pos->next;pos->next =newnode;}//删除pos结点//删除pos后改变的指针有（pos的前驱节点和pos的next指针）voidslerase(slnode**pphead,slnode*pos){ assert(pphead &&pos);//不能删除空节点if(pos ==*pphead)//如果pos是头节点就进行头删{ slpopfornt(pphead);}else//不是头节点{ slnode*prev =*pphead;slnode*next =pos->next;while(prev->next!=pos){ prev =prev->next;}//出循环后找到了pos的前驱节点prev->next =next;free(pos);pos =NULL;}}//删除pos之后的结点//删除pos之后的结点要改变的指针有（pos和pos->next）voidsleraseAfter(slnode*pos){ assert(pos);slnode*del =pos->next;pos->next =pos->next->next;free(del);del =NULL;}//销毁链表voidsldestroy(slnode**pphead){ assert(pphead&&*pphead);//不能销毁空链表slnode*purc =*pphead;while(purc){ slnode*next =purc->next ;free(purc);purc =next;}//头节点还没销毁*pphead =NULL;}

详解都在注释中哦！