Lesson03 - 链表C语言实现（没有伪代码）
文章目录
数据结构与算法前言1 什么是链表
1.1 基本概念1.2 链表的类型 二、无头单链表的实现（纯C语言）
2.1 创建单个结点2.2 打印2.3 尾插2.4 尾删2.5 头插2.6 头删2.7 按值查找2.8 在pos位置之后插入 x2.9 在pos位置之前插入x2.10 删除pos位置之后的元素 3 带头双向循环链表的实现（纯C语言）
3.1 创建单个结点3.2 初始化链表，并返回一个头结点的指针3.3 打印链表3.4 尾插3.5 头插3.6 尾删3.7 头删3.8 按值查找 - 返回结点的位置3.9 在pos位置之前插入x3.10 删除pos位置的元素 //后记
前言
Lesson03 主要讲解数据结构中的 - 链表，以及链表的C语言实现。
本篇文章没有伪代码，帮助大家在理解顺序表的前提下，自己动手用C语言实现链表
1 什么是链表 1.1 基本概念 线性表的链式存储又称为链表
它是指通过一组任意的存储单元来存储线性表的数据结构
由于是任意结点，还得符合线性表的逻辑结构特点，因此每一个节点除了放自身的数据元素，还必须放一个指向其后继的指针
类似于下图：
1.2 链表的类型 虽然在内存中它们是不连续的，但在逻辑上是相连的
相比较与顺序表，链表的类型就丰富多彩了
一个结点可以存很多信息，除了指向后继的指针，我们可以添加一个指向前驱的指针，于是可分成单向和双向
如果我们添加一个哨兵位的头结点，可以将插入和删除等操作变得容易一点，以此可分为带头结点和不带头结点
如果将尾结点的 next 指针指向头结点，这样就形成了一个循环结构，能够很好地找到头尾，因此可分为循环和非循环
通过排列组合，可以组合出8中不同的链表，它们各有优缺点，本篇文章重点介绍单链表和带头双向循环链表
单链表
typedef int SListDataType;
typedef struct SListNode
{
//存储结点数据
SListDataType val;
//指向下个结点的指针
struct SListNode* next;
}ListNode;
带头双向循环链表
typedef int SListDataType;
typedef struct SListNode
{
SListDataType val;
struct SListNode* next;
struct SListNode* prev;
}ListNode;
二、无头单链表的实现（纯C语言）
2.1 创建单个结点
此接口为了方便增加新数据元素时，需要不断动态申请空间的问题
//创建单个结点
ListNode* BuyListNode(SListDataType x)
{
ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
if (tmp == NULL)
{
perror("BuyListNode::malloc");
}
tmp->next = NULL;
tmp->val = x;
}
2.2 打印
遍历整个链表
void ListPrint(ListNode* pl)
{
ListNode* i = pl;
//遍历整个链表，直到遇到NULL
while (i)
{
printf("%d ", pl->val);
i = i->next;
}
printf("n");
}
2.3 尾插
先找到链表的最后一个结点，然后将新建的结点放在他的后面
//尾插
void ListPushBack(ListNode** ppl, SListDataType x)
{
ListNode* tmp = BuyListNode(x);
//如果传过来的是NULL指针，说明是第一个结点
if ((*ppl) == NULL)
{
(*ppl) = tmp;
return;
}
ListNode* tail= (*ppl);
//寻找尾结点
while (tail->next)
{
tail= tail->next;
}
tail->next = tmp;
}
2.4 尾删
找到最后一个结点，将其 free 掉
但是不能直接 free ，因为我们要将倒数第二个结点的 next 置成 NULL，因此我们需要多加一个结点，用来保存尾结点的前一个结点
void ListPopBack(ListNode** ppl)
{
//如果是NULL指针，不必删除
if ((*ppl) == NULL)
{
return;
}
//如果只有一个结点，直接free
if ((*ppl)->next == NULL)
{
free((*ppl));
(*ppl) = NULL;
return;
}
//定义一个prev记录前一个结点
ListNode* prev = NULL;
ListNode* tail = *ppl;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
2.5 头插
创建一个新结点，连在原来链表的前面即可
//从头部插入一个节点
void ListPushFront(SListNode** pplist, SListDateType x)
{
//即使传的NULL指针也没关系
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
//修改指针，使其指向新的第一个结点
(*pplist) = newnode;
newnode = NULL;
}
2.6 头删
free 第一个结点，修改指针
处理一个NULL指针情况即可
//从头部删除一个节点
void SListPopFront(SListNode** pplist)
{
if (*pplist == NULL) return;
//修改第一个结点的指针
SListNode* tmp = *pplist;
(*pplist) = tmp->next;
free(tmp);
tmp = NULL;
}
2.7 按值查找
遍历整个链表，找到返回结点指针，没有找到返回 NULL
//按值查找,返回找到后的地址
SListNode* SListFind(SListNode* plist, SListDateType x)
{
while (plist)
{
if (plist->date == x)
{
return plist;
}
plist = plist->next;
}
return NULL;
}
2.8 在pos位置之后插入 x
一定要先修改 newnode 的指针，如果先修改 pos 的指针，那么整个链表就会断开
//在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SListDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
//先修改newnode的指针
newnode->next = pos->next;
pos->next = newnode;
}
2.9 在pos位置之前插入x
void SListInsert(SListNode** pplist, SListNode* pos, SListDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
//如果是第一个结点，相当于头插
if ((*pplist) == pos)
{
newnode->next = *pplist;
*pplist = newnode;
}
else
{
//先找到pos位置的前一个结点
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
//找到后修改指针
newnode->next = pos;
prev->next = newnode;
}
2.10 删除pos位置之后的元素
注意讨论 pos 为NULL，和 pos 为唯一结点的情况
void SListEraseAfter(SListNode* pos)
{
if (pos == NULL && pos->next == NULL)
{
return;
}
else
{
//记录后一个结点
SListNode* tmp = pos->next;
//让pos结点指向后一个结点的后一个结点
pos->next = pos->next->next;
free(tmp);
tmp = NULL;
}
}
3 带头双向循环链表的实现（纯C语言）
3.1 创建单个结点
此接口为了方便增加新数据元素时，需要不断动态申请空间的问题
//创建一个新结点
ListNode* BuyListNode(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("BuyListNode::malloc");
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
3.2 初始化链表，并返回一个头结点的指针
创建一个头结点
ListNode* ListInit()
{
ListNode* head = BuyListNode(0);
//由于是循环链表，当只有头结点时，prev和next都指向自己
head->next = head;
head->prev = head;
return head;
}
3.3 打印链表
遍历整个链表
void ListPrint(ListNode* phead)
{
ListNode* cur = phead->next;
//循环链表判断结尾的标志是最后一个结点的next指向head
while (cur != phead)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}
3.4 尾插
找到最后一个结点，然后插入新结点
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
//不必遍历整个链表去找尾结点，头结点的prev即使尾结点
ListNode* tail = phead->prev;
//修改指针，使其还是一个循环链表
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
3.5 头插
创建一个新结点，连在原来链表的前面即可
//从头部插入一个结点x
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyListNode(x);
//相当于在头结点和第二个结点之间插入新结点
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
3.6 尾删
head 的 prev 即是尾
//从尾部删除一个结点
void ListPopBack(ListNode* phead)
{
assert(phead);
//如果只有头结点，不必删除
if (phead->next == phead) return;
//记录尾结点以及尾结点的前驱
ListNode* tail = phead->prev;
ListNode* p_tail = tail->prev;
free(tail);
tail = NULL;
//修改指针使其还是循环链表
phead->prev = p_tail;
p_tail->next = phead;
}
3.7 头删
记录第一个结点，以及第二个结点，方便修改指针
void ListPopFront(ListNode* phead)
{
assert(phead);
if (phead->next == phead) return;
//记录第一个结点，以及第二个结点，方便修改指针
ListNode* first = phead->next;
ListNode* n_first = first->next;
free(first);
first = NULL;
phead->next = n_first;
n_first->prev = phead；
}
3.8 按值查找 - 返回结点的位置
遍历链表，寻找 x
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
//注意尾结点的条件
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
3.9 在pos位置之前插入x
注意修改指针的顺序
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
3.10 删除pos位置的元素
删除结点一定要注意不能让链表断开
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
}
综上就是关于链表最核心的知识，对您有帮助的老铁，还望关注、点赞、收藏一键三连哦~~~
//后记 以后每周会更新一到两篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。
