单链表详解

一.概念

该篇链表博客是按照工程项目的格式来记录的，与平常的算法链表有些许不同，注意区分。

二.一些类型的创建

三.尾插

因为需要凭空插入一个数，所以我们肯定需要新开辟一个节点（newnode）来存放需要插入的数。之后我们需要找到原链表的尾部再将其插入就可以了。

这里尤其需要注意的一个点是：我们增加操作如果链表为空时需要改变头节点（phead）,因为phead是一级指针，所以我们传参需要二级指针。

Test.c

SList.h

SList.c

四.头插

因为头插必定会改变头节点所以同样需要使用二级指针。同时让插入的节点变为头节点。

Test.c

SLIst.h

SList.c

五.头删尾删

SList.h

SList.c

尾删

头删

六.打印链表

SList.h

SList.c

七.单链表查找,任意位置插入，任意位置删除

SList.h

SLiist.c

查找

在pos位置前面插入

将pos位置删除

八.源代码

test.c

#include"SList.h"void TestList()
{SListNode* phead = NULL;//测试部分}int main()
{TestList();return 0;
}

SList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>#define SLTDataType inttypedef struct {SLTDataType data;//这里将int类型替换成链表类型以符合工程书写习惯struct SListNode* next;
}SListNode;void SLPushBack(SListNode** phead,SLTDataType x);//尾插void SLPushFront(SListNode** phead, SLTDataType x);//头插void SLPopBack(SListNode** phead);//尾删void SLPopFront(SListNode** phead);//头删void SLPrint(SListNode* phead);//打印//查找
SListNode* SListFind(SListNode* phead, SLTDataType x);
void SListInsert(SListNode**pphead,SListNode* pos, SLTDataType x);//在pos位置前位置插入(注意pos是节点的指针)
void SListErase(SListNode**pphead,SListNode* pos);//删除pos位置

SList.c

#include"SList.h"void SLPushBack(SListNode** pphead, SLTDataType x)//尾插
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//开辟新节点来存放插入的数if (newnode == NULL)//如果开辟失败则返回错误{perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;//初始化新节点if (*pphead == NULL)//注意*pphead就是phead{*pphead = newnode;}//如果链表里没有数直接插入数else{SListNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//找到原链表尾部tail->next = newnode;//插入新节点}}void SLPushFront(SListNode** pphead, SLTDataType x)//头插
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//开辟一个新节点if (newnode == NULL)//判断是否开辟成功{perror("malloc fail");}newnode->data = x;newnode->next = *pphead;//让新的节点指向原本的头节点*pphead = newnode;//让新节点成为头节点
}void SLPopBack(SListNode** pphead)//尾删
{assert(*pphead!=NULL);//断言链表不能为空//找尾if ((*pphead)->next == NULL)//如果链表只有一个数{free(*pphead);//直接释放头节点*pphead = NULL;}else{SListNode* tail = *pphead;SListNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);//直接删掉tail节点tail = NULL;prev->next = NULL;}}void SLPopFront(SListNode** pphead)//头删
{assert(*pphead != NULL);//链表不能为空SListNode* first = *pphead;*pphead = first->next;//直接让头节点变为第二个数free(first);first = NULL;
}void SLPrint(SListNode* phead)//打印
{SListNode* start = phead;while (start != NULL){printf("%d ", start->data);start = start->next;}printf("NULL");
}SListNode* SListFind(SListNode* phead, SLTDataType x)//查找
{SListNode* cur = phead;while (cur->data != x&&cur!=NULL){cur = cur->next;}return cur;
}void SListInsert(SListNode**pphead,SListNode* pos, SLTDataType x)//任意位置插入
{if (pos == *pphead){SLPushFront(pphead,x);//头插}else{SListNode* pre = *pphead;while (pre->next != pos)//找到pos前面的位置{pre = pre->next;}SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//开辟新节点newnode->data = x;newnode->next = pos;//初始化新节点pre->next = newnode;//将pos前一个位置连接到新节点上}
}void SListErase(SListNode** pphead, SListNode* pos)//任意位置删除
{if (pos == *pphead){SLPopFront(pphead);//头删 }else{SListNode* pre = *pphead;while (pre->next != pos)//找到pos前面的位置{pre = pre->next;}pre->next = pos->next;//删除free(pos);}
}