C 语言 【单链表】
单链表是一种基本的数据结构，由一系列节点组成，每个节点包含数据域和指针域。数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。单链表的特点包括动态存储、非连续存储、易于插入和删除。
节点可以定义成一个结构体，每个节点中包含一个数据和下一个节点的地址。
//构造节点
typedef int SLDataType;
struct SLNode
{
SLDataType data;
struct SLNode* next;
};
typedef struct SLNode SLNode;上面的结构体定义了一个节点，节点中存放的数据类型被定义成了SLDataType类型，节点的名称叫做SLNode。
1、单链表的顺序访问
这里给出单链表的逻辑结构：首先有一个节点指针pList指向开始的节点，节点中的next存放的是下一个节点的地址。可以通过next访问下一个节点。最后一个节点的next中存放的是空指针NULL；
这里写一个打印单链表的函数，以示范单链表的访问功能；
void SLPrint(SLNode* phead);这里需要说明的是，打印函数在访问链表的过程中不涉及更改链表，所以在设计函数时参数部分用节点的指针就可以。进一步来说，打印函数需要将每一个节点的data打印出来，这个时候可以按照如下的方式进行访问节点；
当cur为NULL时打印NULL即可，那么函数的实现可以写成如下的形式；（由于链表为空时能进行打印功能，所以不能在函数体最开始进行断言操作）
void SLPrint(SLNode* phead)
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}2、单链表的末尾插入
链表的末尾插入首先需要创建新的节点，这里可以创建一个新的节点指针，并对里面的内容分进行初始化，由于后面还会涉及到节点的创建，所以在这里选择将其封装成一个函数； 在创建完成时，返回新节点的指针用于后续的拼接。
SLNode* SLBuyNode(SLDataType val)
{
SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));
if (newNode == NULL)
{
perror("PushBack malloc faile");
return;
}
newNode->data = val;
newNode->next = NULL;
return newNode;
}在末尾插入节点时会有两种情况：1、链表本身为空 2、链表不为空
当链表本身为空时，我们需要将新创建的节点与pList进行拼接，此时的操作就会改变pList的值，在写函数时我们要改变的是一级节点指针的内容，所以在函数传参时应该传入二级节点指针才能达到目的效果。
当链表pList为空时,将新创建的节点的地址newNode赋值给pList.然而在函数调用过程中形参的改变不影响实参的变化。所以在这里选择使用*pphead = newNode ，这样就可以达到修改实参的目的。
当链表不为空时，需要找到链表的最后一个节点的地址tail，修改最后一个节点的next 使其指向创建的新节点newNode。
这里需要注意的是，我们需要改变的是最后一个节点中nest的值，那么就需要最后一个节点的地址tail ，当tail->next非空时 将tail->next赋值给tail即可找到最后一个节点的地址。最后将newNode赋值给tail->next即可。这样尾插节点就实现了，下面是代码实现：
void SLPushBack(SLNode** pphead,SLDataType val)
{
//1、创建新的节点指针
SLNode* newNode = SLBuyNode(val);
//进行拼接
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
//找最后一个节点的结构体指针
SLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newNode;
}
}3、单链表的末尾删除
需要考虑的是当链表为空时就不能进行删除操作，所以需要在函数体开始进行断言操作。第二点：目标链表的节点数为1时，删除完节点之后要修改pList的值，使它的值为NULL;这里就需要更改pList的值，所以在函数传参时就需要传入节点的二级指针。函数声明如下：
void SLPopBack(SLNode** pphead);当链表只有一个节点时：直接释放pList 再将其置空
当链表中的节点个数大于1时，先找到倒数第二个节点的地址，用于将倒数第二个节点中的next置为空，也需要找到倒数第一个结点的地址，直接释放再将其置为空。
那么单链表的末尾删除就可以写成如下的形式：
void SLPopBack(SLNode** pphead)
{
assert(*pphead);
if ((*pphead)->next != NULL)
{
//链表节点大于1个
SLNode* prev = NULL;
SLNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
else
{
free(*pphead);
*pphead = NULL;
}
}4、单链表的头部插入
链表为空时可以进行插入操作，所以不能进行断言操作。当链表为空时，创建新节点之后需要将新节点的地址赋值给pList，在这个操作中需要修改pList的值，所以在函数传参时需要传入节点的二级指针。单链表的头部插入函数声明如下：
void SLPushFront(SLNode** pphead, SLDataType val);在头部插入时，均需要修改pList的值。然后将新节点中next的值修改为原来pList的值
可以看到，上述的两种情况可以合并为一种情况来写，所以单链表的头部插入函数可以写成如下的形式：
void SLPushFront(SLNode** pphead, SLDataType val)
{
SLNode* newNode = SLBuyNode(val);
newNode->next = *pphead;
*pphead = newNode;
}5、单链表的头部删除
链表为空时不能进行删除操作，所以在函数体内要进行断言操作。每次删除一个节点之后，要将第二个节点的地址赋值给pList，在这里也需要修改pList的值，所以在函数传参时，也需要传入节点的二级指针。函数的声明如下：
void SLPopFront(SLNode** pphead);
按照上面的逻辑就可以定义函数为：
void SLPopFront(SLNode** pphead)
{
assert(*pphead != NULL);
SLNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}单链表的测试：
void Test1()
{
SLNode* pList;
pList = NULL;
SLPushBack(&pList,1);
SLPushBack(&pList,2);
SLPushBack(&pList,3);
SLPushBack(&pList,4);
SLPrint(pList);
SLPopBack(&pList);
SLPopBack(&pList);
SLPopBack(&pList);
SLPopBack(&pList);
SLPrint(pList);
}
void Test2()
{
SLNode* pList;
pList = NULL;
SLPushBack(&pList, 1);
SLPushBack(&pList, 2);
SLPushBack(&pList, 3);
SLPushBack(&pList, 4);
SLPrint(pList);
SLPushFront(&pList,1);
SLPushFront(&pList,2);
SLPushFront(&pList,3);
SLPushFront(&pList,4);
SLPrint(pList);
}
void Test3()
{
SLNode* pList;
pList = NULL;
SLPushFront(&pList, 1);
SLPushFront(&pList, 2);
SLPushFront(&pList, 3);
SLPushFront(&pList, 4);
SLPrint(pList);
SLPopFront(&pList);
SLPrint(pList);
SLPopFront(&pList);
SLPrint(pList);
SLPopFront(&pList);
SLPrint(pList);
SLPopFront(&pList);
SLPrint(pList);
}
int main()
{
Test1();
Test2();
Test3();
return 0;
}下附运行结果，可以观察到，上述功能均已实现。
原文地址：https://blog.csdn.net/qq_70199082/article/details/143803955
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！