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

链表前言

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

链表的实现

1.头文件

#pragma once
#include <stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int sldatatype;//因为不知道要保存什么类型的数据
//定义节点的结构体
typedef struct slistnode {sldatatype data;//保存的数据struct slistnode* next;//指向下一个结构体的指针
}slnode;
void slprint(slnode* phead);
//打印链表(这里要传链表头的地址，以确保能找到链表)
//phead的作用就和火车头差不多
slnode* slbuynode(sldatatype);//申请新节点
void slpushback(slnode** pphead, sldatatype x);
//尾插（因为要通过函数改变数据所以就要传‘址’调用，不能‘传值’）
//所以这里是‘二级’指针！
void slpushfornt(slnode** pphead, sldatatype x);//头插
void slpopback(slnode** pphead);//尾删
void slpopfornt(slnode** pphead);//头删
//查找
slnode* slfind(slnode* phead, sldatatype x);
//在指定位置之前插入数据
void slinsert(slnode** pphead, slnode* pos, sldatatype x);
//删除pos结点
void slerase(slnode** pphead, slnode* pos);
//在指定位置之后插入数据
void slinsertAfter(slnode* pos, sldatatype x);
//删除pos之后的结点
void sleraseAfter(slnode* pos);
//销毁链表
void sldestroy(slnode** pphead);

2.源文件

#include"slist.h"
//断言pphead的目的是不能对空地址进行解引用！
void slprint(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;return newnode;
}
void slpushback(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;		}	
}
void slpushfornt(slnode** pphead, sldatatype x)//头插
{//既然要插入数据那么就要开辟新空间（新节点）slnode* newnode = slbuynode(x);assert(pphead);newnode->next = *pphead;//为了把新结点和原来的链表连起来*pphead = newnode;	
}
void slpopback(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;}
}
void slpopfornt(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){return node;}node = node->next;}return NULL;
}
//在指定位置之前插入数据（要改变的指针有pos的前驱节点和pos）
void slinsert(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）
void slinsertAfter(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指针）
void slerase(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）
void sleraseAfter(slnode* pos)
{assert(pos);slnode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}
//销毁链表
void sldestroy(slnode** pphead)
{assert(pphead&&*pphead);//不能销毁空链表slnode* purc = *pphead;while (purc){slnode* next =purc->next ;free(purc);purc = next;	}//头节点还没销毁*pphead = NULL;
}

详解都在注释中哦！