网站中有哪些标签需要优化,微信平台制作网站开发,修改wordpress登录logo网址,在门户网站建设上的讲话链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的#xff01;在上篇我们学习了单向链表#xff0c;而单向链表虽然空间利用率高#xff0c;插入和删除也只需改变指针就可以达到#xff01;但是我们在每次查找、删除、访问..…
链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的在上篇我们学习了单向链表而单向链表虽然空间利用率高插入和删除也只需改变指针就可以达到但是我们在每次查找、删除、访问.....时都受到单向链表的一个特性干扰单向不可逆只能以遍历的形式去使用这样使得需要从头到尾找到特定的节点再进行操作今天我们来学习另外一种链表结构双向链表。既然是零基础我会从小白的角度进行讲解放心食用
目录 一.链表的分类 二.带头双向循环链表 二.1链表节点设置 二.2链表新增节点 二.3链表初始化 二.4链表扩容节点 二.5链表打印 二.6在目标节点前面插入 二.7在目标节点后面插入 二.8链表头删 二.9链表尾删 二.10链表头插 二.11链表尾插 二.12删除中间目标节点 二.13释放双链表 三.总结 四.代码合并 一.链表的分类
这里就不介绍哈是链表了如果对此感到疑惑可以看我上一篇投稿咱直接进入分类
链表主要可以分为以下3大类
单向链表
单向链表是链表中最简单的一种它由一系列节点组成每个节点包含两个部分指针域与数据域。指针域用来指向下一个节点的地址数据域用来存储数据。以下是抽象草图方便巧记 双向链表 双向链表与单向链表不同它的每个节点有两个指针next跟prev跟一个数据域两个指针分别指向前一个节点和后一个节点。同样如图巧记 循环链表 循环链表是一种特殊的单链表它的最后一个节点的指针指向头节点形成一个“环”如图 在进行下面的学习之前针对链表的各种分类我们需要理清几个名词
头指针
头指针本质上是结构体类型的指针指向一个节点这个节点一般是 第一个节点 或者 头节点
头结点
简单理解为在 第一个节点 前面还有一个节点这个节点就称为头节点。头节点一般不存储数据
带头
头指针指向头节点就称为带头节点如图 不带头
头指针指向第一个节点就称为不带头节点如图 针对这几种分类带头或者不带头、单向或者双向、循环或者非循环
我们总共可以组合八种链表我们主要学习 无头双向非循环链表 带头双向循环链表 这两种
八种链表结构中其中这两种最具代表性另外六种便自然理解了上一篇我们已经学完了第一种今天我们来学习第二种
注意双链表一般需要改变四个指针的指向因此建议大家画图理解这样就可以轻松操作了
二.带头双向循环链表
理解了上面几个名词后我们就能轻易理解哈是带头双向循环链表了
带头无非就是第一个节点前还有一个头节点嘛
双向节点里面有两个指针两个指针分别指向一前一后的节点
循环尾节点的后指针指向头节点头节点的前指针指向尾节点达到封闭形成循环 二.1链表节点设置
不论怎样我们都需要先创建一个结构体作为接下来各种功能的节点基础 这个结构体里面有两个指针一个数据域。这里为了缩短结构体类型我们用 typedef 重定义以下需要注意的是typedef重定义的这个结构体里面结构体指针必须写完整因为此处还属于声明阶段后续才可以正常缩写。代码如下
typedef struct Pointdef
{struct Pointdef* next;//指向下一个节点struct Pointdef* prev;//指向上一个节点int data;//数据域
}Pointdef;
二.2链表新增节点
因为我们不管初始化还是各种增添功能都需要节点所以我们先完成开辟节点的函数让这个函数返回指向这个开辟好的节点指针然后才可以进行初始化操作代码如下
//开辟新节点
Pointdef* Newspoint(int x)
{Pointdef* news (Pointdef*)malloc(sizeof(Pointdef));if (news NULL){perror(malloc);return NULL;}//初始化新节点news-next NULL;news-prev NULL;news-data x;return news;
}
我们刚开辟好的节点还没有连接只是一个结构体大小因此它的prev跟next指针都指向NULLx就是初始化节点的数据域如下图理解 二.3链表初始化
上面我们先调用 新增节点 的函数在外面开辟一个节点作为头节点如果有问题可以先看下面的合并代码接下来对这个头节点进行初始化将它作为头节点此时头节点的next跟prev指针都应该指向自己因为是循环链表此时只有一个节点。代码如下
//链表初始化
void Initialize(Pointdef* head)
{head-next head;head-prev head;
} 二.4链表扩容节点
此时我们已经初始化了链表下面我们给它新增几个节点调用新增函数改变节点指针指向代码如下
//链表扩容节点
Pointdef* tail head;
for (int i 2; i 5; i)
{Pointdef* news Newspoint(i);//连接tail-next news;news-prev tail;news-next head;head-prev news;tail tail-next;
} 二.5链表打印
与单向链表访问区别不大只需要注意是这里的链表是循环的需要控制打印的条件不能是当前指针不能指向头节点否则就是死循环了代码如下
//链表打印
void Printf(Pointdef* head)
{Pointdef* tail head-next;while (tail ! head){printf(%d , tail-data);tail tail-next;}printf(NULL\n);
} 二.6在目标节点前面插入
我们已经写好了一条双链表那么我们只需要找到目标节点然后连接四个指针就行了代码如下
这里我们假设目标节点是 tail 新节点 news 新节点前面的节点是 prev
//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{assert(tail);Pointdef* prev tail-prev;Pointdef* news Newspoint(x);prev-next news;news-prev prev;news-next tail;tail-prev news;} 二.7在目标节点后面插入
将找到的目标节点作为参数然后在函数中改变它的前后四个指针就行如图
//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{assert(tail);//目标节点的下一个节点不能是空否则就是尾插了assert(tail-next);Pointdef* news Newspoint(x);Pointdef* next tail-next;tail-next news;news-prev tail;news-next next;next-prev news;
} 二.8链表头删
头删咱直接将头节点作为参数就行了再记录第二个节点方便释放然后用四个指针连接头节点和第二个节点最后记得释放第一个节点的空间如图
//链表头删
void Outomit(Pointdef* head,int x)
{assert(head);assert(head-next);Pointdef* tail head-next-next;Pointdef* next head-next;head-next tail;tail-prev head;free(next);next NULL;
}二.9链表尾删
这个咱就不多说了就是先记录倒数第二个节点将它作为尾节点就行了同样记得释放空间直接上代码
//链表尾删
void Tailomit(Pointdef* head, int x)
{assert(head);Pointdef* prev head-prev-prev;Pointdef* tail head-prev;prev-next head;head-prev prev;free(tail);tail NULL;
} 二.10链表头插
但凡插入节点的都具有很大的相似之处无非就是将这个节点插入某处通过记录附近节点的位置再把新增节点的左右节点与它进行连接看代码
//链表头插
void Headinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail head-next;Pointdef* news Newspoint(x);head-next news;news-prev head;news-next tail;tail-prev news;
} 二.11链表尾插
//链表尾插
void Tailinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail head-prev;Pointdef* news Newspoint(x);tail-next news;news-prev tail;head-prev news;news-next head;
} 二.12删除中间目标节点
删除节点我们肯定要先找到目标节点我们在链表中可以通过以下两种方式寻找指针域 数据域在上面的前后插入中我们选择的指针查找方式下面我们进行数据查找方式来删除
//链表中间节点删除
void Omit(Pointdef* tail)
{Pointdef* pc tail-prev;Pointdef* pt tail-next;pc-next pt;pt-prev pc;free(tail);tail NULL;
} 二.13释放双链表
咋从第一个节点释放到尾就OK了注意链表的空间不是连续的因此需要一个个销毁
//双链表销毁
void Undermine(Pointdef* head)
{assert(head);Pointdef* cur head-next;Pointdef* tail cur-next;while (cur ! head){tail cur-next;free(cur);cur tail;}free(head);headNULL;printf(释放完毕\n);
}
三.总结
针对以上实现的双链表其实针对整个链表都有以下特点
1首先我们要有设计好开辟节点的函数然后知道如何连接这些节点
2头插、尾插、中间插其实都有很大的共性只是目标地点稍微差异这点大家可以画图理解
3删除某个节点需要及时释放该空间避免空间泄漏。需要注意是先连接再释放
4针对为何单向链表很多涉及二级指针而双向链表大多是一级指针
因为单向链表有很多地方需要改变头指针单向链表将第一个节点作为头节点的指向而双向链表是固定了哨兵节点因此其它操作其实是针对结构体里面的指针操作的。该知识的原理是对形参的改变不影响实参如需改变形参需要使用二级指针
5双向链表为哈要从第一个节点开始释放
双向链表的头节点是链表结构的一部分不是数据节点应该先释放数据节点再释放链表结构
四.代码合并
流程文件可以使用打印来进行功能的测试
#define _CRT_SECURE_NO_WARNINGS 1
#includetext.hint main()
{int x 4;//链表新增节点Pointdef* headNewspoint(1);//链表初始化void Initialize(head);//链表扩容节点Pointdef* tail head;for (int i 2; i 5; i){Pointdef* news Newspoint(i);//连接tail-next news;news-prev tail;news-next head;head-prev news;tail tail-next;}//链表打印Printf_t(head);//在目标节点前面插入 tail (head-next)-next;x 6;FrontInsertion(tail, x);//在目标节点后面插入 OutInsertion(tail, x);// 测试点Printf_t(head);//链表头删x 7;Outomit(head,x);//链表尾删x 8;Tailomit(head, x);// 测试点Printf_t(head);//链表头插x 1;Headinsert(head, x);//链表尾插x 9;Tailinsert(head, x);// 测试点Printf_t(head);//链表中间节点删除x 4;tail head - next;while (tail-data ! x){tail tail-next;}Omit(tail);// 测试点Printf_t(head);//双链表销毁Undermine(head);return 0;
}
头文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#includestdlib.h
#includestdio.h
#includeassert.htypedef struct Pointdef
{struct Pointdef* next;//指向下一个节点struct Pointdef* prev;//指向上一个节点int data;//数据域
}Pointdef;//链表新增节点
Pointdef* Newspoint(int x);
//链表初始化
void Initialize(Pointdef* head);
//链表打印
void Printf_t(Pointdef* head);
//在目标节点前面插入
void FrontInsertion(Pointdef* tail, int x);
//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x);
//链表头删
void Outomit(Pointdef* head ,int x);
//链表尾删
void Tailomit(Pointdef* head, int x);
//链表头插
void Headinsert(Pointdef* head, int x);
//链表尾插
void Tailinsert(Pointdef* head, int x);
//链表中间节点删除
void Omit(Pointdef* tail);
//双链表销毁
void Undermine(Pointdef* head);
函数执行文件
#define _CRT_SECURE_NO_WARNINGS 1
#includetext.h//链表新增节点
Pointdef* Newspoint(int x)
{Pointdef* news (Pointdef*)malloc(sizeof(Pointdef));if (news NULL){perror(malloc);return NULL;}//初始化新节点news-next NULL;news-prev NULL;news-data x;return news;
}//链表初始化
void Initialize(Pointdef* head)
{head-next head;head-prev head;
}//链表打印
void Printf_t(Pointdef* head)
{Pointdef* tail head-next;while (tail ! head){printf(%d , tail-data);tail tail-next;}printf(NULL\n);
}//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{assert(tail);Pointdef* prev tail-prev;Pointdef* news Newspoint(x);prev-next news;news-prev prev;news-next tail;tail-prev news;}//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{assert(tail);//目标节点的下一个节点不能是空否则就是尾插了assert(tail-next);Pointdef* news Newspoint(x);Pointdef* next tail-next;tail-next news;news-prev tail;news-next next;next-prev news;
}//链表头删
void Outomit(Pointdef* head,int x)
{assert(head);assert(head-next);Pointdef* tail head-next-next;Pointdef* next head-next;head-next tail;tail-prev head;free(next);next NULL;
}//链表尾删
void Tailomit(Pointdef* head, int x)
{assert(head);Pointdef* prev head-prev-prev;Pointdef* tail head-prev;prev-next head;head-prev prev;free(tail);tail NULL;
}//链表头插
void Headinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail head-next;Pointdef* news Newspoint(x);head-next news;news-prev head;news-next tail;tail-prev news;
}//链表尾插
void Tailinsert(Pointdef* head, int x)
{assert(head);Pointdef* tail head-prev;Pointdef* news Newspoint(x);tail-next news;news-prev tail;head-prev news;news-next head;
}//链表中间节点删除
void Omit(Pointdef* tail)
{Pointdef* pc tail-prev;Pointdef* pt tail-next;pc-next pt;pt-prev pc;free(tail);tail NULL;
}//双链表销毁
void Undermine(Pointdef* head)
{assert(head);Pointdef* cur head-next;Pointdef* tail cur-next;while (cur ! head){tail cur-next;free(cur);cur tail;}free(head);head NULL;printf(释放完毕\n);
}
