C语言链表难吗,链表的基本操作c语言
文章目录前言？1.什么是链表？1.1链表的分类？1单向/双向链表？2领先/不领先？3循环还是无循环？2.开始敲代码！2.1链表结构2.2打开节点2.3尾插入/头插入2.4尾删除/头删除2.5查找/更改2.6在pos位置前/后插入2.7在pos位置删除数据2.8打印链表2.9销毁链表3。测试结论？
前言？在之前的博客中，我们谈到了序列表的数据结构，和之前在C语言中学习的数组颇为相似。
我们今天要学的是链表，这是一种全新的数据结构，和之前学的不一样。
编译器：VS2019
1.什么是链表？顾名思义，链表是一个有链的表。
与序列表的扩展相比，它可以利用内存堆中的空闲空间，而不需要一个连续的长空间。从而达到提高空间利用效率的目的。
链表中每个独立打开的“元素”都称为节点链表，带有头指针phead，用来指向链表的第一个节点。在单链表中，每个节点都有一个next指针，指向下一个节点链表尾节点的next指向一个空指针，这样我们在使用它的时候，就可以用next指针访问链表中的下一个节点，直到最后一个节点的next为空。
需要注意的是，链表的各个节点之间并没有实际的箭头，画箭头只是为了方便我们理解。实际上，在内存中，链表的下一个指针起着箭头的作用。
链表的结构在逻辑上是连续的，但不一定在物理上是连续的。
实际上，在堆开放空间中，分配的内存可能是连续的，也可能不是连续的。
1.1链表的分类
1/2向链表
2/不要带头。这里的头指的是头节点。这个节点的Next指向链表的实际头，val中没有存储有效数据。
实际上，有头的head- next相当于没有头的phead指针。
3循环或非循环
这个博客解释了无头单向非循环链表，双向链表会在后面的博客里解释！
2.开始输入代码！写实际代码的时候，一定要记住：写完一个模块，一定要测试一次，不要全部测试！
2.1链表结构与顺序表相同。在使用单链表之前，我们需要创建一个“模板”，即单链表各个节点的结构。
typedef int SLTDataType//定义一个新的符号，这个符号和链表的内容有关。
typedef结构SListNode
{
SLTDataType数据；//val-存储内容
struct SListNode * next//存储下一个节点的地址
} SListNode
2.2打开节点我们在使用单链表的时候，需要先打开一个头节点，让它的下一个指针指向NULL。
slist node * node 1=(slist node *)malloc(sizeof(slist node))；
node 1-data=1；
node 1-next=NULL；我们可以封装一个函数来实现这部分！
ListNode * BuysListNode(SLT data type x)//x表示节点val的值。
{
slist node * new node=(slist node *)malloc(sizeof(slist node))；
if (newnode==NULL)
{
printf( malloc fail \ n )；
退出(-1)；
}
其他
{
new node-data=x；
new node-next=NULL；
}
返回newnode
}需要注意的是，在使用这个函数时，我们应该让另一个指针先接收返回的newnode地址。不建议直接让上一个节点的下一个接收返回值。
这将有利于我们后续的调试！
//建议的做法
slist node * new node=buys list node(x)；
tail-next=new node；
//不推荐
tail-next=buys list node(x)；
2.3 Tail Insert/Head Insert和Tail Insert:将新节点连接到现有链表的尾部。
假设我们现在有了这样一个链表，在需要插尾的时候应该怎么做？
其实我们只需要打开一个新节点，把前一个节点的next指向这个新打开节点的地址！(next=对于在末尾插入的新节点为空)
void slist push back(slist node * * PP head，SLTDataType x)
{
assert(PP head)；
slist node * new node=buys list node(x)；
if (*pphead==NULL)
{
//如果原链表为空，直接让头指针=新打开的节点地址。
* pphead=newnode
}
Else//原始链表不为空
{
SListNode * tail=* pphead
while(尾巴——下一个！=空)
{//需要先找到尾巴
tail=tail-next；
}
tail-next=new node；
}
}而且头插没有尾插麻烦！
我们只需要将新节点的下一个指向原始链表的头，然后将头指针改为新节点的地址
void SListPushFront(slist node * * PP head，SLTDataType x)
{
assert(PP head)；
slist node * new node=buys list node(x)；
new node-next=* PP head；
* pphead=newnode
}细心的你应该注意到了，这里我们都使用了二级指针pphead。
如果我们使用一级指针，直接传入头指针phead，当我们需要改变指针指向的地址时，改变只会在函数内部生效，主函数中的phead指针并没有被改变。
这是一个函数地址和值传递的经典问题。
当我们需要改变phead本身时，我们需要传入一个二级指针。
2.4尾删除/头删除和尾删除，需要先找到尾。并且需要保存尾部的前一个节点的地址。
while(尾巴——下一个！=NULL)//会找到尾节点本身，不符合要求。
//尾部删除应该找到前一个尾部节点。
while(尾-下-下！=NULL)同时，我们需要考虑特殊情况
链表为空，只有一个链表没有删除尾部。具体代码实现如下
void slist pop back(slist node * * PP head)
{
assert(PP head)；
if (*pphead==NULL)
{
返回；
}
else if((*pphead)- next==NULL)
{
免费(* PP head)；
* pphead=NULL
}
其他
{
//有多个尾部的情况
SListNode * tail=* pphead//找到尾巴
while(尾-下-下！=空)
{
tail=tail-next；
}
免费(tail-next)；
tail-next=NULL；
}
返回；
}头删除的情况还是比较简单的。
我们需要用一个变量保存头节点，然后让头指针phead指向原头节点的下一个，最后免费把节点转过来。
void SListPopFront(slist node * * PP head)
{
assert(PP head)；
if (*pphead==NULL)
{
返回；
}
其他
{
SListNode * oldhead=* pphead
* PP head=(* PP head)-next；
免费(old head)；
oldhead=NULL
}
返回；
}
2.5 Finding/change Finding函数需要我们遍历单链表，找到用户输入的X的值，返回其所在节点的地址。
lookup函数不需要改变phead指针，所以这里我们只需要传入一级指针。
slist node * slist find(slist node * phead，SLTDataType x)
{
断言(phead)；
SListNode * curt=phead//找到x的位置。
while (curt- next！=空)
{
if (curt- data==x)
{
回复curt
}
其他
{
curt=curt-next；
}
}
//找不到，返回null
返回NULL
}你可能会有一个疑问，假设我的链表中有多个X？这个函数只能返回找到的第一个X的地址。
不幸的是，我们没有任何好的办法来解决这个问题。除非用户知道自己想找的X的确切地址，否则很难搞定。
实际上，在链表的一个节点中并不只有一个整数X。我们可以通过其他参数进行多重判断。
比如在通讯录中，我们可以利用姓名和性别进行精准搜索。您也可以将所有找到的X返回给用户进行选择，但这不是本博客要讨论的内容。
在更改功能中，我们需要用户输入要更改的节点的地址，以及新的val。
如果用户不知道节点的地址需要更改，可以使用查找功能来查找。
void slist modify(slist node * phead，SListNode* pos，SLTDataType x)
{
断言(phead)；
pos-data=x；
返回；
}
2.6插入前/后pos位置除了基本的首尾增加，用户可能还需要插入特定节点的前后，方便数据管理。这时候就需要灵活改变了。
没有链表。序列表中的数据超出界限。pos位置可以通过查找功能找到。假设用户需要在pos位置后插入，我们需要暂时断开链表，插入一个新的节点，重新链接。
void SListInsertAfter(slist node * * PP head，SListNode* pos，SLTDataType x)
{
assert(PP head)；
断言(位置)；
slist node * new node=buys list node(x)；
slist node * next=pos-next；//原始位置的下一位
pos-next=new node；//新插入位置的下一位
new node-next=next；
返回；
}如果是在pos之前插入，需要遍历找到pos的前一位，用同样的方法断开、插入、重新连接。
void slist insert(slist node * * PP head，SListNode* pos，SLTDataType x)
{
assert(PP head)；
断言(位置)；
if (pos==*pphead)
{
SListPushFront(pphead，x)；
}
其他
{
SListNode * tail=* pphead//找到上一个位置
while(尾巴——下一个！=空)
{//只写这个情况，没有考虑pos是第一个的情况
if (tail- next==pos)
{
slist node * new node=buys list node(x)；
tail-next=new node；
tail-next-next=pos；
返回；
}
其他
{
tail=tail-next；
}
}
}
返回；
}这里我们都传入了二级指针，因为当pos是链表的头节点时，在pos之前插入相当于头插入，可以直接调用之前写的头插入函数。
当pos是链表的头节点时，在它后面插入相当于在末尾插入。
这个函数中没有空链表，因为函数需要传入pos。空链表中没有节点，pos为空，assert断言会报错。
我这里写的函数很简单，需要用户严格遵守使用规则，传入一个合法的pos。
2.7删除pos位置的数据。插完了再说删。
这里提供了两个函数，一个是删除pos位置的节点，另一个是删除pos旁边的节点。
这部分其实是上一步的逆向，就不细说了(懒)。
有不懂的可以在评论区提问~ ~看到会回复的！
无效滑动酯酶(滑动节点** pphead，滑动节点** pos)
{
assert(PP head)；
断言(位置)；
if (*pos==*pphead)
{//如果pos是头节点，相当于头删除。
SListPopFront(PP head)；
}
其他
{
SListNode * tail=* pphead//找到上一个位置
while(尾巴——下一个！=空)
{
if (tail- next==*pos)
{
tail-next=(* pos)-next；
免费(* pos)；//删除后主函数传递的pos位置已经空闲。
* pos=NULL//*pos为空，主函数中的pos也为空。
pos=NULL
返回；
}
其他
{
tail=tail-next；
}
}
}
返回；
}
void slisterasafter(slist node * * PP head，SListNode* pos)
{
assert(PP head)；
断言(位置)；
slist node * next=pos-next-next；
免费(pos-next)；
pos- next=下一个；
返回；
}
2.8打印链表。打印时，可以打印出-箭头，方便我们查看链表的结构。
void SListPrint(SListNode* phead)
{
SListNode * cur=phead
而(cur！=空)
{
printf(%d-，cur-data)；
cur=cur-next；
}
printf( NULL \ n )；
}
2.9销毁链表对于顺序表，销毁链表只需要释放指向顺序表中堆空间的指针。
但是对于链表，我们需要一步一步的释放，释放完后清空头指针。
如果链表有头节点，头节点也应该留空。
void slist destroy(slist node * * PP head)
{
assert(PP head)；
SListNode * curt=* pphead
while(简略)
{
slist node * next=curt-next；
免费(curt)；
curt=下一个；
}
* pphead=NULL
返回；
}
3.这次测试，我还是用多文件编程的方法来打单链表的代码。
这样做的好处是别人只需要看你的。h头文件，而且他们可以清楚的知道你的项目实现了什么功能，就像一篇文章的大纲一样。对于后续的项目实战来说，是非常重要的编程能力的积累。
测试我们的代码，可以看到所有功能都可以正常实现！
结论？学了单链表之后，开始接触一些链表的oj话题。不得不说，链表的题目比之前C语言练的还要难！有很多题目需要我们掌握之前的知识。
最重要的是通读代码和调试的能力，这样才能更好的写出算法。
如果这个博客对你有帮助，请点击它？非常感谢！
有问题可以在评论区问。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。