和我一起学编程呀，大家一起努力！
这篇文章耗时比较久，所以大家多多支持啦
链表的结构及结构
概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。
理解：可以把链表理解为火车，每一节火车车厢都有下一节车厢的钥匙
如下图
与顺序表不同的是：链表里面的‘车厢’都是独立申请下来的空间，我们称为节点
如上图就可以理解为一个节点
当前节点主要有两个部分组成：要保存的数据和保存下一个节点的地址（指针变量）
为什么需要指针变量保存下一个节点的位置？
因为链表里面的每一个节点都是独立申请的，需要保存下一个节点的位置才能找到下一个节点
假设保存的节点为整型，则代码如图：
struct SListNode { int data; //节点数据 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 };
给定的链表结构中，如何实现链表的从头到尾的打印？
void SLTPrint(SLTNode*phead) { SLTNode*pcur=phead; while(pcur) { printf("%d ",pcur->date); pcur=pcur->next; } printf("\n"); }
解析：
1.pcur指针变量保存第一个节点的地址
2.对pcur解引用拿到next指针变量的地址一个节点的地址
3.赋值给pcur，此时的pcur保存的地址就指向了下一个节点
补充：
1、链式机构在逻辑上是连续的，在物理结构上不一定连续
2、节点一般是从堆上申请的
3、从堆上申请的空间，是按照一定策略分配的，每一次申请的空间可能连续
单链表的存储结构
先写出结构体改名比较简单的名字为SLTNode
typedef int SLTDataType;//便于后期修改 typedef struct SListNode { SLTDataType data; //节点数据 struct SListNode* next; //指针保存下⼀个节点的地址 }SLTNode;
单链表的头插
1、断言，pphead不能为空
2、给新节点申请空间
3、让新节点的next指向原本的头
4、新节点设为新的头
void SLTPushFront(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead; *pphead = newnode; }
单链表的尾插
1.分为链表为空和不为空
2.链表为空：头节点直接为新的节点，即newnode
3.链表不为空，找到尾节点，尾节点的next指向新节点newnode
注意：这里使用了二级指针，因为你需要传的是地址
//尾插 void SLTPushBack(SLTNode** pphead, SLTDateType x) { assert(pphead); SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->date = x; newnode->next = NULL; //链表为空 if (*pphead == NULL) { *pphead = newnode; return; } //链表不为空 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; } void SListTest02()//尾插 { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPrint(plist); }
单链表的头部删除
1、pphead,*pphead不能为空
2、保存第二个节点
3、释放旧的头也就是*pphead
4、把保存的第二个节点设为头结点
void SLTPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); //第二个节点成为新的头结点，释放旧的头结点 SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
单链表的尾部删除
1、分为两种情况，一个是链表只有一个节点的情况，另一个是不止有一个节点的情况，当然这都是在pphead *phead不为空的情况
2、只有一个节点的情况就是释放（free）
3、不只有一个节点：就是找到尾节点前面一个节点，让这个节点（prev）指向NULL找到尾节点，使用while循坏，把头结点保存在ptail中，当ptail->next为NULL就终止循坏，找到了prev prev->next指向空指针，然后释放掉之前的尾节点
void SLTPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } SLTNode* ptail = *pphead; SLTNode* prev = NULL; while (ptail->next) { prev = ptail; ptail = ptail->next; } prev->next = NULL; //销毁 free(ptail); ptail = NULL; }
单链表的查找
1、断言pphead
2、遍历链表，采用循坏就可以，找到了就返回x
SLTNode* SLTFind(SLTNode** pphead, SLTDateType x) { assert(pphead); //遍历链表 SLTNode* pcur = *pphead; while (pcur) { if (pcur->date == x) return x; pcur = pcur->next; } return NULL; }
在指定位置之前插入数据
1、pphead *pphead pos不能为空
2、分为两种情况，pos是头结点，采用头插
3、pos不是头结点，采用while循坏，找到pos前面的一个节点（prev），prev->next指向新节点，新节点->next指向pos
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x) { assert(pphead); assert(pos); assert(*pphead); //Pos是头结点 if (pos == *pphead) { SLTPushFront(pphead, x); return; } //不是头结点情况 SLTNode* newnode = SLTBuyNode(x); SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; }
在指定位置之后插入数据
1、直接申请新节点空间
2、新节点的->next指向pos的后面一个节点
3、pos—>next指向新节点
void SLTInsertAfter(SLTNode* pos, SLTDateType x) { assert(pos); SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; }
删除pos节点
1、pos是头结点，采用头删
2、pos不是头节点，找到pos节点的前面一个节点（prev）,让prev->next指向pos->next，然后释放pos节点
void SLTErase(SLTNode** pphead, SLTNode*pos) { assert(pphead); assert(*pphead); assert(pos); //posg刚好是头结点 if (*pphead == pos) { SLTPopFront(pphead); return; } SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; }
销毁链表
采用循坏，依次把每一个节点释放掉
void SListDesTroy(SLTNode** pphead) { assert(pphead); assert(*pphead);; SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }
希望大家多多支持！谢谢大家可以阅读到这里^ ^
