代做课件的网站,广州机械网站建设外包,搜索引擎营销的特点包括,wordpress 分类目录 首页目录 一.链表
1#xff09;链表的概念
2#xff09;链表的结构
二.单链表的实现 三.链表的分类
1#xff09;单向或者双向
2#xff09;带头或不带头
3#xff09;循环或非循环 一.链表
1#xff09;链表的概念 链表#xff08;Linked List#xff09;是一种…目录 一.链表
1链表的概念
2链表的结构
二.单链表的实现 三.链表的分类
1单向或者双向
2带头或不带头
3循环或非循环 一.链表
1链表的概念 链表Linked List是一种物理存储结构上非连续非顺序的储存结构数据元素的逻辑顺序是通过链表中指针链接次序实现的。要注意链表也是线性表-----但链表在物理结构上不是线性的。
2链表的结构 举个栗子让我们更好的理解链表的结构想象一辆火车有一节一节的车厢每个车厢都是独立存在的旺季的时候多添加几节车厢淡季的时候减少几节车厢假如我们只能带一把钥匙从车头走到车尾我们能想到的最简单的方法就是在每节车厢都放上下一节车厢的钥匙。
在链表里是什么形式呢 与顺序表的不同每一个都是单独申请的空间即需要要插入数据时才去申请一块节点的空间这每个空间我们称之为节点。节点的组成我们直观的从图中就能看出来要保存的数据和保存下一个节点的地址我们需要通过指针变量来保存下一节点位置才能从当前节点找到下一节点这样就可以使我们的链表真正链接起来。 图中指针变量qList保存的是第一个节点的地址此时qList指向第一个节点如果我们想让其指向第二个节点时我们只需要把其保存的指针变量修改成0x0012FFA0即可让qList直接指向第二节点。
假设是整型我们给出当前的结构体代码
struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
}; 当我们想要保存下一个整型数据的时候实际上我们向系统申请了一块内存这个内存不仅要保存整型数据也需要保存下一个节点的地址当下一个节点为空时保存地址为空。我们想从第一个节点走到最后一个节点的时候只需要在前一个节点拿上下一个节点的地址就可以了。
void SLTPrint(SLTNode* phead){SLTNode *phead phead;while(pcur){printf(%d,pcur-data);pcur pcur-next;}printf(\n);
}
如何实现从头到尾的打印? ps.:
在逻辑上是连续的在物理结构上不一定连续节点一般是从堆上申请的从堆上申请的空间是按照一定策略分配出来的每次申请的空间可能连续也可能不连续
二.单链表的实现
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; //节点数据struct SListNode* next; //指针保存下⼀个节点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead); 三.链表的分类
链表结构非常多样有一大堆组合 1单向或者双向 2带头或不带头 3循环或非循环 虽然链表结构这么多但我们最常用的还是两种链表一种最简单一种最复杂。
1.无头单向非循环列表也就是单链表结构比较简单一般不会单独用来存储数据。现实中更多是作为其他数据结构的子结构如哈希桶之类的。
2.带头双向循环链表结构最复杂一般用于单独储存数据。实际使用的链表数据结构大部分都是这种链表。这种链表虽然麻烦一点但这个结构往往具有很多优势实现起来反而简单许多。 后面会详细讲这些实现是如何操作的~~~ 完结撒花
