189 8069 5689
✅作者简介：嵌入式入坑者，与大家一起加油，希望文章能够帮助各位！！！！
📃个人主页：@rivencode的个人主页
🔥系列专栏：玩转数据结构
💬推荐一款模拟面试、刷题神器，从基础到大厂面试题👉点击跳转刷题网站进行注册学习
线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列等，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构（存储结构）上并不一定是连续的，线性表在物理上存储时，通常以顺序表和链式结构的形式存储。
线性表的顺序存储—>顺序表
是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
线性表的链式存储
线性表中的数据结点在内存中的位置是任意的，即逻辑上相邻的数据元素在物理位置（内存存储的位置）上不一定相邻。
链式存储结构的优点：
链式存储结构的缺点：
顺序表因为只有数据域，没有指针域所以它的存储密度为大1
不过这个问题，一个结点也就多几个指针，最多8个字节，所以若是在现代计算机这点空间已经不算什么，不过如果是像单片机这种嵌入式设备内存较小，所以还是会有一点点影响的
顺序表的优点：
顺序表的缺点：
数据结点在内存中的位置是任意的，即逻辑上是线性的数据元素在物理位置（内存存储的位置）上不一定相邻。
结点为什么在内存中是随机存储的呢
因为我们产生一个结点要给他分配内存是动态分配出来的（malloc），而分配的结点的内存的地址是随机的，所以结点的地址是随机的，也就是说结点在内存中的存储是随机的。
单链表的一个结点
我们只要知道一个结构体的指针（地址），就能访问该结构体的成员（如果成员里面又包含下一个结点（结构体）指针，又可以访问下一个结点的成员）
若基础不好的先请参考：
《指针详解》
《结构体详解》
其实链表你把结构体与指针搞明白了，链表真的随便拿捏。
不带头结点单向不循序链表：
当链表为空时，头指针指向空，当链表不为空时头指针必须指向第一个结点
void SListPrint(SLTNode *phead)
{SLTNode *cur = phead;
while (cur != NULL)
{printf("%d->", cur->data);
cur=cur->next;
}
printf("NULL\n");
}
//清空单链表
void SListClear(SLTNode **pphead)
{SLTNode *cur = *pphead;
SLTNode *next = NULL;
while (cur != NULL)
{next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
如果要改变头指针的值，虽然头指针是一个指针，但是指针一样有它的地址，如果在一个函数中要改变它的值，照样要传头指针的地址，在解引用改变头指针的值，如果你只是值传递，则传过去的只是该头指针的临时拷贝，一旦出函数会自动销毁并不会影响头指针本身的值。
SLTNode* CreateSListNode(SLTDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
NewNode->data = x;
NewNode->next = NULL;
return NewNode;
}因为插入元素时都先要创建一个新结点，所以为了避免代码冗余，将创建新结点单独封装成一个函数。
尾插结点void SListPushBack(SLTNode **pphead, SLTDataType x)
{SLTNode*NewNode = CreateSListNode(x);
//当链表为空
if (*pphead == NULL)
{*pphead = NewNode;
}
else
{SLTNode* tail = *pphead;
while (tail->next != NULL)
{ tail=tail->next;
}
tail->next = NewNode;
}
}
不要写了if不写else，搞得后面又插入一个结点
//链表头部插入一个节点
void SListPushFront(SLTNode **pphead, SLTDataType x)
{SLTNode*NewNode = CreateSListNode(x);
NewNode->next = *pphead;
*pphead = NewNode;
}
void SListPopBack(SLTNode **pphead)
{//链表为空
if (*pphead == NULL)
{return;
}
//只有一个节点
else if ((*pphead)->next == NULL)
{free(*pphead);
*pphead = NULL;
}
//有多个节点
else
{SLTNode*prev = NULL;
SLTNode*tail = *pphead;
while (tail->next != NULL)
{ prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
有以下几种情况：
void SListPopFront(SLTNode **pphead)
{if (*pphead == NULL)
{return;
}
SLTNode *next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
查找值为x的节点并返回节点的指针
//查找值为x的节点并返回节点的指针
SLTNode * SListFind(SLTNode *phead, SLTDataType x)
{SLTNode *cur = phead;
while (cur != NULL)
{if (cur->data == x)
{ //找到返回该结点指针
return cur;
}
cur = cur->next;
}
//找不到返回NULL指针
return NULL;
}在pos指针指向的结点的前一个位置插入一个结点
//在pos指针前一个插入一个节点
void SListInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{//pos在第一个节点，相当与头插
if (*pphead== pos)
{SListPushFront(pphead, x);
}
else
{SLTNode *NewNode = CreateSListNode(x);
SLTNode *prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
prev->next = NewNode;
NewNode->next = pos;
}
}
如果pos的位置是第一个结点，则在第一个结点前一个插入结点则为头插，直接调用头插的接口函数即可。
pos在其他位置：
void SListErese(SLTNode **pphead, SLTNode *pos)
{if (*pphead == pos)
{SListPopFront(pphead);
}
else
{SLTNode *prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
prev->next=pos->next;
free(pos);
}
}
一样的如果pos的位置是第一个结点，则在第一个结点前一个删除结点则为头删，直接调用头删的接口函数即可。
pos在其他位置：
头指针是指向链表中第一个结点(存储该节点的地址)。如果链表中有头结点，则头指针指向头结点；若链表中没有头结点，则头指针指向链表中第一个数据结点。
不存储任何数据，若链表有头结点则头指针一直指向头指针。
链表带头结点的优点：
当链表为空表时，插入，删除结点都是在头结点后面，头结点指向了第一个带数据的结点。
当我们单链表无头结点时当我们头插，头插的时候，我们都需要移动头指针的位置指向新的第一个结点，当链表为空时又要将头结点置NULL，这些操作我们都需要去改变头指针的值，而改变头指针要传头指针的地址的，用二级指针来操作，无疑是增加了编程的难度，如果链表有头结点，而头指针一直指向头结点，不管是头删，头插，都是在头结点后面增加删除，而头指针一直指向头结点不用发生改变，只需要一级指针就搞定
注意：
循环链表中没有NULL指针，故遍历链表时，其终止条件是判断是不是等于头指针。
所以双向链表：在单链表的每一个结点再增加一个指向其直接前驱的指针域prev，这样链表中就形成了有两个方向不同的链
单向不带头不循环
单向带头不循环
单向不带头循环
单向带头循环
双向不带头不循环
prev的值也为空
双向不带头循环
双向带头不循环
prev的值也为空
双向带头循环
ListNode*CreateListNode(LTDataType x)
{ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode));
NewNode->data = x;
NewNode->next = NULL;
NewNode->prev = NULL;
return NewNode;
}一个新的结点，先将next，prev置空
链表初始化//链表初始化
ListNode *ListInit()
{ListNode*phead = CreateListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}空表
void ListDestory(ListNode**pphead)
{ListNode*cur = (*pphead)->next;
while (cur != *pphead)
{ ListNode* next = cur->next;
free(cur);
cur = next;
}
free(*pphead);
*pphead = NULL;
}
//清空链表
void ListClear(ListNode*phead)
{ListNode*cur = phead->next;
while (cur != phead)
{ListNode* next = cur->next;
free(cur);
cur = next;
}
phead->next = phead;
phead->prev = phead;
}只清空的话不需要释放头结点，不过要将头结点的两个指针域都指向自己（回到空表状态）
打印链表//打印链表
void Listprint(ListNode*phead)
{ListNode*cur = phead->next;
while (cur != phead)
{printf("%d ",cur->data);
cur = cur->next;
}
printf("NULL\n");
}
遍历是看是否遍历到了头结点才停下来。
尾插结点//尾插
void ListPushBack(ListNode*phead, LTDataType x)
{ assert(phead != NULL);
ListNode*NewNode = CreateListNode(x);
ListNode*tail = phead->prev;
tail->next = NewNode;
NewNode->prev = tail;
NewNode->next = phead;
phead->prev = NewNode;
}
可以怎么写：但是这里水太深你可能把握不住
我们只要抓住一点：把要操作的结点事先存储起来，不管我们怎么连接结点，我们都找的到要操作的结点
//头插
void ListPushFront(ListNode*phead, LTDataType x)
{ assert(phead != NULL);
ListNode*NewNode = CreateListNode(x);
ListNode*first = phead->next;
phead->next = NewNode;
NewNode->prev = phead;
NewNode->next = first;
first->prev = NewNode;
}//尾删
void ListPopBack(ListNode*phead)
{ assert(phead != NULL);
assert(phead->next != phead);
ListNode*tail = phead->prev;
ListNode*prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
//头删
void ListPopFront(ListNode*phead)
{ assert(phead != NULL);
assert(phead->next != phead);
ListNode*first = phead->next;//除掉头结点第一个结点
ListNode*second = first->next;//除掉头结点第二个结点
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
查找节点值为x的结点，返回指向节点的指针
//查找节点值为x，返回指向节点的指针
ListNode* ListFind(ListNode*phead, LTDataType x)
{ ListNode*cur = phead->next;
while (cur != phead)
{ if (cur->data == x)
{ return cur;
}
cur = cur->next;
}
return NULL;
}//在pos指针指向的节点前插入一个节点
void ListInsert(ListNode*pos, LTDataType x)
{ assert(pos != NULL);
ListNode*NewNode = CreateListNode(x);
ListNode*prev = pos->prev;
prev->next = NewNode;
NewNode->prev = prev;
NewNode->next = pos;
pos->prev = NewNode;
}
void ListErase(ListNode*pos)
{ assert(pos !=NULL);
ListNode*next = pos->next;
ListNode*prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}//链表长度
int ListLength(ListNode*phead)
{int len = 0;
ListNode*cur = phead->next;
while (cur != phead)
{len++;
cur = cur->next;
}
return len;
}只要搞懂结构体指针，明白链表的概念，直接拿捏，相信很多人学完了链表还是不知道链表会用在什么地方，因为我们平时编程基本上用不到链表，但是链表在操作系统中的使用非常广泛，所以链表是非常重要重要的数据结构，有兴趣的可以看看在实际项目中链表的应用->《FreeRTOS实时操作系统-链表的源码解析》
结束语：
最近发现一款刷题神器，如果大家想提升编程水平，玩转C语言指针，还有常见的数据结构（最重要的是链表和队列）后面嵌入式学习操作系统的时如freerots、RT-Thread等操作系统，链表与队列知识大量使用。
大家可以点击下面连接进入牛客网刷题
点击跳转进入网站(C语言方向)
点击跳转进入网站(数据结构算法方向)
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧