大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
✅作者简介:嵌入式入坑者,与大家一起加油,希望文章能够帮助各位!!!!
📃个人主页:@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的节点并返回节点的指针
//查找值为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指针指向的结点的前一个位置插入一个结点
//在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的结点,返回指向节点的指针
//查找节点值为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前面插入一个结点//在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;
}
删除pos指针指向的结点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元起,快前往官网查看详情吧