黑彩网站充值就给你做单子,北京seo排名厂家,织梦网站源码下载,重庆网站建设招聘数据结构—-链表详解
目录 文章目录 链表的定义链表的构成链表的分类双向和单向带头和不带头循环和不循环 链表的命名基本操作的实现初始化打印取值查找插入指定位置插入删除删除销毁 部分其他链表的代码实现循环链表双向链表 优点/缺点#xff08;对比顺序表#xff09;优点…数据结构—-链表详解
目录 文章目录 链表的定义链表的构成链表的分类双向和单向带头和不带头循环和不循环 链表的命名基本操作的实现初始化打印取值查找插入指定位置插入删除删除销毁 部分其他链表的代码实现循环链表双向链表 优点/缺点对比顺序表优点缺点 链表的定义
前面我们介绍的顺序表在逻辑结构和物理结构上都是线性、连续的关系那么我们在篇尾的时候也提到了是否有一种顺序表无需在物理结构上连续从而达到更好存取的目的呢今天它来了。
链表LinkList属于线性表的一种以下是百度百科关于链表的定义 总结下来我们可以看出
在结构上链表并不是像顺序表那样底层结构是数组而是包含两个区域数据域、指针域。我们可以类比成火车火车每一节车厢实际上是独立的也就好比数据域存储着各自的数据但每一节车厢之间都会由一条链连接在一起从而形成整个火车链也就好比指针域起到连接该车厢和指向下一车厢的作用。而实际上这样的存储结构也就是为什么链表的物理结构可以不连续而逻辑结构依旧是连续的。
这样的好处就是当我们需要对指定元素进行移动、替换、存取等操作的时候我们可以一步到位无需挪动数据无需扩容不会造成空间上的浪费——好比你火车更换车厢总不可能让整个火车都为你而改动吧。 所以如果要用一句话概括链表是什么我们可以说链表是一种线性数据结构由结点组成每个结点包含一个数据元素也就是数据域和指向下一个节点的指针也就是指针域。叫法结点或者节点都行 联想指针域的作用
实际上在后续的数据结构中还有很多类型的数据结构会使用到指针域这个概念或者可以说是结点的概念。结点指地是组成数据元素的存储映像往往指针就是指向结点的鉴于它不受物理空间限制的优点往往都会使用指针和结点来更高效率地实现数据结构。
链表的构成
数据域data存放实际数据
指针域next存放下一节点的首地址
结点由数据域和指针域两部分信息组成的数据元素的存储映像
链表的分类
我们平常使用的最多的就是单链表——不带头单向不循环链表
既然有不带头那么必然就有带头既然有单向那么必然就有双向既然有不循环那么必然就有循环。
接下来针对这三个方向进行介绍。
双向和单向
单向链表每个节点包含一个指向下一个节点的指针。单向链表只能从头节点开始遍历无法从尾节点向前遍历。 双向链表每个节点包含一个指向下一个节点和一个指向前一个节点的指针。双向链表可以从头节点或尾节点开始遍历可以方便地在链表中间插入或删除节点。向的描述与指针域的描述是一致的单向只有一个指针域而双向有两个
可以通俗地理解为单向为单行道只能从头走到尾双向为双行道既可退又可进。
带头和不带头
带头链表指第一个结点叫做头结点不存储有效数据只作为指引结点 不带头链表指第一个结点不叫做头结点就是第一个结点存储有效数据
注意这里指的带头就是带有头结点的意思头结点不存储任何数据它仅仅用于指向第一个结点。优点是操作链表时统一处理不需要特殊处理第一个节点代码更加简洁清晰。缺点是需要额外的头节点占用额外的空间。
循环和不循环
循环链表最后一个节点的指针指向第一个节点形成一个环状结构。循环链表可以从任意节点开始遍历但需要注意避免出现死循环的情况。 不循环链表最后一个节点的指针直接指向空仅仅作为线性结构。
虽然链表种类之多例如还有带有尾结点的链表等等但在实际应用中只有两种**单链表不带头单向不循环链表和双向链表带头双向循环链表**使用得最多因为它们两个的特性加起来即为所有特性而其他类型的链表也就不难创建了。
链表的命名
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode单链表
SLTDataType、ElemType、LinklistType等等根据自己的偏好设定以下都命名为SLTDataType数据域
SLTDataType data; //保存结点数据指针域*
struct SListNode* next;//保存下一结点地址操作
SLTPushBack//针对操作的命名一般在操作前缀添加SLT等代表其为链表的大写字母缩写基本操作的实现
有关链表的操作下方是一些举例 //链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);
//打印
void SLTPrint(SLTNode* phead);接下来针对上述操作进行详细介绍。
初始化
即构造一个空链表
void SlistTest01() {//一般不会这样去创建链表这里只是为了给大家展示链表的打印SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node4-data 4;
//当我们定义好了数据域之后指针域应该如何定义呢node1-next node2;node2-next node3;node3-next node4;node4-next NULL;
//像这样让指针域指向该节点的下一节点达到链接的目的SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL) {//如果开辟失败的情况perror(malloc fail!);exit(1);}newnode-data x;//开辟数据域newnode-next NULL;//开辟指针域return newnode;
}打印
在接下来承担显示的作用将链表的结构可视化
void SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;//使用next指针指向下一节点}printf(NULL\n);
}取值
与顺序表的取值不一样因为链表物理结构是不连续的所以在链表中进行访问的时候不能直接随机访问只能从首元素出发遍历进行访问。
Status SLTGet(LinkList L, int i, ElemType e)//获取线性表L中的耨个数据元素的内容通过变量e返回
{ p L-next; //初始化p指向首元结点j 1; //初始化j为计数器while (pj i) //向后扫描直到p指向的第i个元素或p为空{p p-next; //p指向下一个结点j;}if (!p || j i) //第i个元素不存在抛出异常return NULL; e p-data; //取第i个元素return OK;
}
查找
查找操作同顺序表类似都是哦才能够首元结点开始依次将元素与给定值进行比较。
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur) //等价于pcur ! NULL{if (pcur-data x) {return pcur;}pcur pcur-next;}//没有找到return NULL;
}插入
插入分为尾插、头插、指定位置插入而指定位置插入又分为指定位置之前和之后。
尾插
//尾插
void SLTPushBack(SLTNode** pphead/*为什么是**二级指针因为*pphead这个指针在传参时实际上还是传值而不是传地址需要传这个指针的地址也就是使用二级指针*/, SLTDataType x) {assert(pphead);SLTNode* newnode SLTBuyNode(x);//链表为空新节点作为pheadif (*pphead NULL) {*pphead newnode;return;}//链表不为空找尾节点SLTNode* ptail *pphead;while (ptail-next)//并非ptial不能为空而是ptail-next不能指向空{ptail ptail-next;}//ptail就是尾节点ptail-next newnode;
}头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode SLTBuyNode(x);//newnode *ppheadnewnode-next *pphead;*pphead newnode;
}指定位置插入
之前
//在指定位置之前插入数据
//关键找到前驱节点
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上链表不能为空如果链表都空了必然找不到前驱节点assert(*pphead);SLTNode* newnode SLTBuyNode(x);//pos刚好是头结点if (pos *pphead) {//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况如果不分情况讨论那么prev就永远找不到posSLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev - newnode - posprev-next newnode;newnode-next pos;
}之后
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode SLTBuyNode(x);//错误操作顺序错误导致pos-next不再指向下一节点//pos-nextnewnode //newnode-nextpos-next//正确操作newnode-next pos-next;pos-next newnode;
}删除
删除又分为尾删、头删、指定结点删除以及指定位置后续结点删除
尾删
//尾删
void SLTPopBack(SLTNode** pphead) {assert(pphead);//第一个节点不能为空//链表不能为空assert(*pphead);//链表不为空if ((*pphead)-next NULL)//如果只有一个节点 {free(*pphead);//直接释放*pphead NULL;//置空return;}//如果有多个节点SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next)//不能指向空{prev ptail;ptail ptail-next;}prev-next NULL;//销毁尾结点free(ptail);ptail NULL;
}头删
//头删
void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}删除
删除又分为删除指定结点、删除指定结点之后的所有结点
删除pos结点
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点没有前驱节点执行头删if (*pphead pos) {//头删SLTPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//找到了prev以及pos pos-next//先改变指向prev-next pos-next;//再释放节点free(pos);pos NULL;
}删除pos之后的结点
//删除pos之后的节点也就是pos-next-next
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos-next不能为空assert(pos-next);//pos pos-next pos-next-nextSLTNode* del pos-next;//pos-next pos-next-next;free(del);del NULL;
}销毁
//销毁链表
//注意链表的空间是不连续的所以不能一次性销毁所有元素只能使用循环一个元素一个元素销毁
void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}…
以上操作都基于单链表
部分其他链表的代码实现
循环链表
在介绍链表的分类的时候已经介绍了循环链表的基本定义也就是链表的最后一个结点的指针域指向第一个结点这样就形成了一个循环链表如果用图像来表示关系的话如下
那么针对其代码的实现实际上只需要让最后一个结点的指针域不指向空而是指向第一个结点即可。
//关键代码
pB-next-next;
B-nextA-next;
A-nextp;//指向头结点循环链表的作用以及使用场景
约瑟夫问题约瑟夫问题是一个经典的问题即有n个人围成一圈从第一个人开始报数报到m的人出列然后从出列的下一个人开始重新报数直到所有人都出列。循环链表可以很好地模拟这个问题。环形队列循环链表可以用来实现环形队列即队列的尾节点指向头节点可以很方便地实现循环入队和出队操作。循环播放列表循环链表可以用来实现循环播放音乐列表或视频列表等功能。实际上循环这个概念在生活中许多部分都有被使用到而当它需要使用代码实现的时候那么循环链表是较为容易实现的方案。
双向链表 双向链表的每个节点都包含两个指针一个指向前一个节点一个指向后一个节点。鉴于这个特点它与单向链表不同的是双向链表可以从头到尾或从尾到头遍历链表。
在双向链表中通常有一个头节点和一个尾节点它们分别指向链表的第一个节点和最后一个节点可以方便地在头部或尾部进行插入或删除操作。
双向链表的操作普遍上比单向链表简单因为它多了一个指针域所以操作的灵活性大大提高。
双向链表的作用以及使用场景
需要频繁在链表中间插入或删除节点的情况双向链表可以在O(1)的时间复杂度内完成插入或删除操作因此适合在需要频繁插入或删除节点的场景中使用。需要双向遍历链表的情况双向链表可以方便地从头到尾或从尾到头遍历链表因此适合在需要双向遍历链表的场景中使用。需要实现栈或队列的情况双向链表可以方便地在两端进行插入或删除操作因此适合用来实现栈或队列。需要实现LRU缓存淘汰算法的情况LRU缓存淘汰算法中经常需要删除最近最少使用的节点双向链表可以方便地删除尾节点因此适合用来实现LRU缓存淘汰算法。
优点/缺点对比顺序表
优点
1.存储空间充足对内存利用率高
链表无需像顺序表那样预先分配空间只要内存空间允许链表中的元素个数就没有限制那么这也可以反向说明链表对内存的利用率较高。
2.插入和删除的效率高
不像顺序表那样在进行插入和删除的时候需要移动整个表链表可以直接对单个元素进行插入和删除操作。
3.动态性和灵活性
链表的大小可以动态地调整可以根据需要动态地插入或删除元素不需要提前指定大小。
4.可以实现高级数据结构
实际上在后续更高阶的数据结构中许多结构都是基于链表的。链表可以实现栈、队列、哈希表等高级数据结构具有很高的灵活性和扩展性。
缺点
1.存储密度小单个结点有效数据占用空间小
我们发现链表中的一个结点包含数据域和指针域但是实际上真正存储了有效元素的只有数据域一部分那么这就说明了其存储密度小存储密度数据元素本身占用的存储量/结点结构占用的存储量
2.存取元素的效率低
链表不像顺序表那样是随机存取结构可以随时存取该位置上的元素它属于顺序存取结构只能通过遍历来实现存取元素操作。
3.每存一个数据都要开辟动态空间增加了内存分配的开销并可能导致内存碎片化。所以说动态化既有利也有弊。
