做视频网站带宽要,9免费建网站,深圳公司地址变更,wordpress制作前言
线性表中有着许多的结构#xff0c;如顺序表和链表。而单链表则是链表的最基础的一种形式#xff0c;下面就让我们对其做一个了解。
概念
概念#xff1a;链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次…前言
线性表中有着许多的结构如顺序表和链表。而单链表则是链表的最基础的一种形式下面就让我们对其做一个了解。
概念
概念链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
结构
我们可以将单链表的结构想象成火车的车厢 淡季时⻋次的⻋厢会相应减少旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/ 加上不会影响其他⻋厢每节⻋厢都是独⽴存在的。 在链表⾥每节“⻋厢”是什么样的呢
如图
结点
与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“结点”。
结点的组成主要有两个部分当前结点要保存的数据和保存下⼀个结点的地址指针变量。
中指针变量plist保存的是第⼀个结点的地址我们称plist此时“指向”第⼀个结点如果我们希望 plist“指向”第⼆个结点时只需要修改plist保存的内容为0x0012FFA0。
链表中每个结点都是独⽴申请的即需要插⼊数据时才去申请⼀块结点的空间我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。
性质
1、链式结构在逻辑上是连续的在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续
结合C语言中结构体的相关知识我们能得到链表的每个结点对应的结构体代码 假设当前保存的结点为整型
struct SListNode
{int data; //结点数据struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};
当我们想要保存⼀个整型数据时实际是向操作系统申请了⼀块内存这个内存不仅要保存整型数 据也需要保存下⼀个结点的地址当下⼀个结点为空时保存的地址为空。
当我们想要从第⼀个结点⾛到最后⼀个结点时只需要在当前结点拿上下⼀个结点的地址就可以了。
链表的打印
给定的链表结构中我们该如何实现结点从头到尾的打印呢
我们用一张图来解释 实现单链表
下面我先给出实现单链表所必须的头文件SList.h
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);具体的实现我将在下一期进行详细说明敬请期待
