C语言实现单链表(图解增删查改+代码)

链表(图解增删查改+代码)"/>

C语言实现单链表(图解增删查改+代码)

文章目录

• 写在前面
• 1. 链表节点的定义
• 2. 链表的创建
• 3. 插入数据
• • 3.1 头插
  • 3.2 尾插
  • 3.3 在指定位置的前面插入数据
• 4. 删除数据
• • 4.1 头删
  • 4.2 尾删
  • 4.3 删除指定位置的数据
• 5. 查找数据
• 5. 链表的销毁

写在前面

上面文章用C语言实现了顺序表的增删查改，本片文章继续用C语言来实现另一种线性存储结构——单链表。我们知道，顺序表中的数据元素在内存中是连续存储的，而单链表的数据元素在内存中是随机存储的。它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
例如：使用单链表存储 {1,2,3,4,5}，数据在内存中的存储状态的逻辑图如下所示：

总结：单链表的数据元素在内存中随机存储，数据元素之间的逻辑关系是通过指针来表示的。

1. 链表节点的定义

链表的结点分为两部分：数据域和指针域。
数据域：链表要存储的数据所在的区域。
指针域：指向下一个节点的指针所在的区域。

链表节点的定义：

typedef int SLTDatatype;typedef struct SListNode
{SLTDatatype data;//数据域struct SListNode* next;//指针域， 指向下一个节点
}SLTNode;

2. 链表的创建

创建一个新链表，通常包括一个指向链表头节点的指针，初始时指向NULL。
例如：一个存储 {1,2,3,4,5} 的链表结构下如图所示：

该链表是由头指针 plist 来维护的，通过头指针 plist 就能找到该链表。由于链表刚创建的时候，链表中没有节点，因此链表创建时，plist 为空。
创建头指针的代码如下：

SLTNode* plist = NULL;//创建头指针

3. 插入数据

向链表插入数据时，根据插入位置的不同可以分为以下三种情况：

• 在头节点前插入一个元素，即头插。
• 在链表中间位置插入元素。
• 在最后一个节点后面插入一个元素，即尾插。

3.1 头插

头插数据步骤：

• 新建一个节点。
  由于后面的插入都需要创建新的节点，因此这里把创建节点封装成一个函数。

代码如下：

//创建新节点
SLTNode* BuyNode(SLTDatatype x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("BuyNode->malloc");return;}newnode->data = x;newnode->next = NULL;return newnode;
}

• 新节点的 next 指向 plist 指向的节点。
• plist 指向新节点。
  

代码如下：

void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{assert(pphead);//检查参数的有效性//创建节点SLTNode* newnode = BuyNode(x);newnode->next = (*pphead);*pphead = newnode;
}

3.2 尾插

尾插数据分为以下两种情况：

1. 链表为空。

• 新建一个节点。
• 新节点的 next 指向 NULL。
• plist 指向新节点。
  

2. 链表不为空。

• 新建一个节点。
• 遍历链表，找到最后一个节点
• 新节点的 next 指向 NULL。
• 最后一个节点的 next 指向新节点。
  

代码如下：

void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{assert(pphead);//检查参数有效性SLTNode* newnode = BuyNode(x);//链表为空的情况if (*pphead == NULL){*pphead = newnode;}else{//链表不为空的情况SLTNode* cur = *pphead;//遍历链表，找最后一个节点while (cur->next){cur = cur->next;}cur->next = newnode;}
}

3.3 在指定位置的前面插入数据

步骤如下：

• 新建一个节点。
• 遍历链表，找到指定位置pos的前一个节点prev。
• 新节点的 next 指向pos。
• prev的 next 指向新节点。

代码如下：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{assert(pphead);//检查参数的有效性assert(pos);//检查插入位置的有效性SLTNode* newnode = BuyNode(x);//头插if (*pphead == pos){newnode->next = *pphead;*pphead = newnode;}else{//中间位置插入数据SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}

4. 删除数据

4.1 头删

头删的步骤如下：

• 判断链表是否为空，不为空在进行删除。
• 保存头节点的地址。
• 更新 plist ，使其跳过待删除节点，指向待删除节点的下一个节点。
• 释放头节点的内存。
  

代码如下：

void SLTPopFront(SLTNode** pphead)
{assert(pphead);//检查参数有效性assert(*pphead);//检查链表是否为空SLTNode* phead = *pphead;*pphead = phead->next;free(phead);
}

4.2 尾删

尾删的步骤如下：

• 判断链表是否为空，不为空在进行删除。
• 找到最后一个节点的前一个节点prev。
• 保存待删除节点的地址。
• prev 的 next 指向NULL。
• 释放头节点的内存。

代码如下：

void SLTPopBack(SLTNode** pphead)
{assert(pphead);//检查参数有效性assert(*pphead);//检查链表是否为空//只有一个元素时,相当于头删if ((*pphead)->next == NULL){SLTNode* phead = *pphead;*pphead = phead->next;free(phead);}else{SLTNode* prev = *pphead;while (prev->next->next != NULL){prev = prev->next;}SLTNode* ptail = prev->next;prev->next = NULL;free(ptail);}
}

4.3 删除指定位置的数据

• 判断链表是否为空，不为空在进行删除。
• 找到待删除节点的前一个节点。
• 更新前一个节点的指针，使其跳过待删除节点，指向待删除节点的下一个节点。
• 释放待删除节点的内存。

代码如下：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);//检查参数有效性assert(*pphead);//检查链表是否为空//头删if (*pphead == pos){SLTNode* phead = *pphead;//保存头节点的指针*pphead = phead->next;free(phead);//SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

5. 查找数据

在链表中查找指定数据的方法是：从表头开始依次遍历链表的节点，如果被查找数据与当前遍历节点的数据相同就是查找成功，如果遍历完链表都没找到，则查找失败。

• 如果找到了，就返回数据所在节点的地址
• 如果找不到，则返回 NULL。

代码如下：

SLTNode* SLTFind(SLTNode* phead, SLTDatatype x)
{SLTNode* cur = phead;//遍历链表的每一个节点while (cur){//与每个节点的数据进行比较if (cur->data == x){return cur;}}return NULL;
}

5. 链表的销毁

依次释放链表的每个节点。
代码如下：

void SLTDestroy(SLTNode** pphead)
{assert(pphead); //检查参数的有效性SLTNode* cur = *pphead;SLTNode* next = NULL;if (cur){next = cur->next;}while (cur){free(cur);cur = next;if (cur){next = cur->next;}}*pphead = NULL;
}

至此，本片文章就结束了，若本篇内容对您有所帮助，请三连点赞，关注，收藏支持下。
创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！
如果本篇博客有任何错误，请批评指教，不胜感激 ！！！