网站建设后怎么写,云主机 多 网站,公司网站建设设计公司排名,用友软件官网目录
基本概念
1#xff0c;什么是双向链表
2#xff0c;与单向链表的区别
双向链表详解
功能展示#xff1a;
1. 定义链表
2#xff0c;创建双向链表
3#xff0c;初始化链表
4,尾插
5#xff0c;头插
6#xff0c;尾删
判断链表是否被删空
尾删代码
7什么是双向链表
2与单向链表的区别
双向链表详解
功能展示
1. 定义链表
2创建双向链表
3初始化链表
4,尾插
5头插
6尾删
判断链表是否被删空
尾删代码
7头删
8,pos位置之前插入
优化后的头插
优化后的尾插
9,删除pos位置的节点
优化后的尾删
优化后的头删
10,求链表长度
11,查找链元素
12,销毁链表
成品展示
List.h
List.c
test.c 本文将以写代码思路进行讲述故中间会出现代码的优化以便梳理思路渐入佳境
本文分成三个文件
List.h//函数的声明
List.c//函数的创建
test.c //用于测试文件基本概念
1什么是双向链表
双向链表Doubly Linked List是一种常见的链表数据结构。它与普通链表的区别在于每个节点都有两个指针一个指向前一个节点一个指向后一个节点因此可以从任意一个节点开始双向遍历整个链表。
双向链表的节点通常由三部分组成数据部分存储节点的值、前驱指针指向前一个节点的指针和后继指针指向后一个节点的指针。相比于单向链表双向链表可以更方便地进行正反向遍历和节点的插入、删除操作。
双向链表的优点是在某些特定场景下可以更高效地操作链表缺点是相比于单向链表需要额外的空间来存储每个节点的前驱指针。
继续遍历一下双向链表的特点和操作 特点 双向链表每个节点有两个指针可以向前或向后遍历。可以从任意节点开始向前或向后遍历整个链表。插入和删除节点的操作相对容易只需要调整节点的前驱和后继指针即可。对于双向链表可以更轻松地实现双向循环链表即首尾节点相连。 常见操作 遍历链表可以从头节点开始按照后继指针依次访问每个节点。或者从尾节点开始按照前驱指针依次访问每个节点。插入节点在给定位置之前或之后插入一个新节点只需要调整前后节点的指针即可。删除节点删除给定位置上的节点同样通过调整前后节点的指针来实现。查找节点可以通过遍历链表来查找特定值或者特定位置上的节点。
注意在使用双向链表时需要注意指针的正确性和更新以避免出现指针丢失和内存泄漏等问题。
2与单向链表的区别
双向链表与单向链表的主要区别在于节点中指针的个数和指向方式1. 指针个数双向链表每个节点有两个指针分别指向前一个节点和后一个节点而单向链表每个节点只有一个指针指向下一个节点。
2. 遍历方式双向链表可以从任意节点开始向前或向后遍历整个链表而单向链表只能从头节点开始顺序遍历。
3. 插入和删除操作双向链表的插入和删除操作相对方便因为可以直接调整前驱和后继节点的指针而单向链表在进行插入和删除时需要更多的操作来调整节点之间的链接关系。
4. 空间占用双向链表相较于单向链表需要额外的空间来存储每个节点的前驱指针。这在一些特定场景下可能会带来一定的开销。
5. 双向性双向链表可以在节点内部通过前驱指针和后继指针来实现双向的遍历和操作。这使得在某些场景下双向链表更加方便和高效例如需要反向遍历链表或者需要在给定节点处进行插入和删除操作。
6. 双向循环性双向链表可以通过连接首尾节点的前驱和后继指针来形成一个双向循环链表。这使得链表在某些场景下更具灵活性例如需要循环遍历链表或者实现循环队列等。
7. 内存占用相对于单向链表每个节点额外存储一个前驱指针和一个后继指针使得双向链表在存储上需要更多的内存空间。这是一个需要考虑的因素尤其是在链表节点数量较大或内存有限的情况下。
8. 双向链表的前向遍历与后向遍历由于双向链表具有前驱和后继指针可以方便地进行正向和反向的遍历操作。而单向链表只能从头节点开始进行顺序遍历无法直接进行反向遍历。
9. 删除操作的效率相对于单向链表在双向链表中删除给定节点的效率更高。由于双向链表可以直接通过前驱和后继指针找到目标节点的前后节点所以删除操作只需要修改前后节点的指针即可而单向链表需要遍历找到目标节点的前一个节点才能进行删除操作。
10. 双向链表支持双向迭代器由于双向链表具有双向性可以轻松地实现双向迭代器。这使得在某些情况下可以更加方便地进行双向迭代操作如双向搜索算法或需要反向遍历的数据结构。
总之双向链表相较于单向链表具有更强的遍历和操作能力但在存储上需要额外的空间开销。根据具体需求和场景的不同选择适合的链表类型是根据实际情况进行权衡和取舍。概述 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 单向链表(无头)详细讲解# 数据结构线性表之-单向链表(无头)
双向链表详解
功能展示
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* BuyListNode(LTDataType x);//void ListInit(LTNode** pphead);
LTNode* ListInit();//打印
void ListPrint(LTNode* phead);//尾插
void ListPushBack(LTNode* phead, LTDataType x);//头插
void ListPushFront(LTNode* phead, LTDataType x);//尾删
void ListPopBack(LTNode* phead);//头删
void ListPopFront(LTNode* phead);//判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead);//pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);//删除pos位置的节点
void ListErase(LTNode* pos);//求链表长度
int ListSize(LTNode* phead);//销毁链表
void ListDestory(LTNode* phead);1. 定义链表
typedef struct ListNode
{struct ListNode* next;//下一节点struct ListNode* prev;//上一个节点LTDataType data;
}LTNode;2创建双向链表
LTNode* BuyListNode(LTDataType x)
{//计算连自定义链表大小LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){//判断是否创建成功perror(malloc fail);exit(-1);}//对前节点进行赋值node-data x;node-next NULL;node-prev NULL;return node;
}3初始化链表
初始化链表使用哨兵位(头节点)前后指针存储的位置为phead本身。
LTNode* ListInit()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;
}当然用无返回值的函数用二级指针进行初始化及后续的增删查改 这样会更麻烦本文全程采用一级指针
void ListInit(LTNode** pphead)
{*pphead BuyListNode(-1);(*pphead)-next *pphead;(*pphead)-prev *pphead;
}改变结构体要用结构体指针。 要改变结构体指针要用结构体指针的指针。 4,尾插
先让我们回顾下双向链表的结构 与单链表的不同是单链表要尾插时要从头一次向后访问找到为节点再进行插入 而双向链表要尾插在head前插入节点即为尾节点。
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* tail phead-prev;//前一个节点指向新节点tail-next newnode;//新节点的prev指向上一个节点newnode-prev tail;//新节点存放的下一节点为头节点newnode-next phead;//头节点的prev存放新节点方便尾插phead-prev newnode;
}5头插
头部插入为head前一个节点
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyListNode(x);LTNode* next phead-next;
//尾部标号对应图中步骤next-prev newnode; //1newnode-next next; //2newnode-prev phead; //3phead-next newnode; //4
//另一种写法//phead-next newnode;//newnode-prev phead;//newnode-next next;//next-prev newnode;
}6尾删
尾删即为删除head的前一个节点 切记不可先将head指向尾删节点NULL否则有可能造成野指针。 还有一种情况若链表已经被删空则会出现错误则应该对删空时进行提醒并终止程序
判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead)
{assert(phead);/*链表返回只剩头节点(链表已经被删空)为真否则为假*/return phead-next phead;
}尾删代码
void ListPopBack(LTNode* phead)
{assert(phead);//判断链表是否被删空为真即为假为假即为真assert(!ListEmptyLTNode(phead));//assert(phead-next ! phead);//head的前一个即为尾巴LTNode* tail phead-prev;//head前一个节点LTNode* tailPrev tail-prev;//tail的前一个节点free(tail);//删除节点//重新链接新尾节点tailPrev-next phead;phead-prev tailPrev;
}7头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListEmptyLTNode(phead));LTNode* next phead-next;LTNode* nnext next-next;free(next);//删除节点phead-next nnext;nnext-prev phead;
}8,pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev pos-prev;LTNode* newnode BuyListNode(x);//prev newnode posprev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}此时既然已经做到了可以任意位置插入 那就可以对头插尾插进行复用简化代码
优化后的头插
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}优化后的尾插
void ListPopBack(LTNode* phead)
{assert(phead);//判断链表是否被删空为真即为假为假即为真assert(!ListEmptyLTNode(phead));//assert(phead-next ! phead);ListErase(phead-prev);
}9,删除pos位置的节点
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;prev-next next;next-prev prev;free(pos);
}此时既然已经做到了可以任意位置插入 那就可以对头插尾插进行复用简化代码
优化后的尾删
void ListPopBack(LTNode* phead)
{assert(phead);//判断链表是否被删空为真即为假为假即为真assert(!ListEmptyLTNode(phead));//assert(phead-next ! phead);ListErase(phead-prev);
}优化后的头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListEmptyLTNode(phead));ListErase(phead-next);
}10,求链表长度
int ListSize(LTNode* phead)
{assert(phead);//跳过哨兵位LTNode* cur phead-next;//求长度int size 0;while (cur!phead){size;cur cur-next;}//返回链表长度return size;
/*不要用头节点存储来计算长度int符合但其他类型例如chardouble 都会出现错误
*/
}test.c中的调用方法 printf(存储的元素个数为%d\n, ListSize(plist));//plist为主函数中创建的结构体11,查找链元素
/*phead为原双链表x表示被查找元素*/
int ListFind(LTNode* phead, LTDataType x)
{assert(phead);/*新建一个指针t初始化为头指针 head*/LTNode* temp phead-next;int i 1;while (temp!phead){if (temp-data x){return i;}i;temp temp-next;}/*程序执行至此处表示查找失败*/return 0;
}test.c中的调用方法 int lf ListFind(plist, 5);if (lf1)printf(找到了%d\n,lf);elseprintf(没找到\n);12,销毁链表
void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;int size 0;while (cur ! phead){LTNode* next cur-next;ListErase(cur);cur next;}free(phead);//只是将指向plist的指针置空要置空plist要在Test.c中完成phead NULL;
}test.c中的使用方法 //销毁的为结构体并不是指向结构体的指针所以需要对指针置空ListDestory(plist);plist NULL;if (plist NULL)printf(销毁成功);成品展示
List.h
#pragma once#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int LTDataType;//定义链表
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;//创建双向链表
LTNode* BuyListNode(LTDataType x);//链表初始化
//void ListInit(LTNode** pphead);
LTNode* ListInit();//打印
void ListPrint(LTNode* phead);//尾插
void ListPushBack(LTNode* phead, LTDataType x);//头插
void ListPushFront(LTNode* phead, LTDataType x);//尾删
void ListPopBack(LTNode* phead);//头删
void ListPopFront(LTNode* phead);//判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead);//pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x);//删除pos位置的节点
void ListErase(LTNode* pos);//求链表长度
int ListSize(LTNode* phead);//查找链元素
int ListFind(LTNode* phead, LTDataType x);//销毁链表
void ListDestory(LTNode* phead);List.c
#include List.h//创建双向链表
LTNode* BuyListNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail);exit(-1);}node-data x;node-next NULL;node-prev NULL;return node;
} /*改变结构体要用结构体指针。要改变结构体指针要用结构体指针的指针。
*/
//初始化链表
//void ListInit(LTNode** pphead)
//{
// *pphead BuyListNode(-1);
// (*pphead)-next *pphead;
// (*pphead)-prev *pphead;
//}
LTNode* ListInit()
{LTNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;
}//打印
void ListPrint(LTNode* phead)
{assert(phead);//创建指针进行依次访问LTNode* cur phead-next;//当cur循环到头节点时代表已经循环一圈停止循环while (cur!phead){printf(%d , cur-data);cur cur-next;}printf(\n);
}//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);//head前一个位置插入即为尾插ListInsert(phead, x);//pos前一个位置插入
}
//void ListPushBack(LTNode* phead, LTDataType x)
//{
// assert(phead);
//
// LTNode* newnode BuyListNode(x);
// LTNode* tail phead-prev;
// //前一个节点指向新节点
// tail-next newnode;
// //新节点的prev指向上一个节点
// newnode-prev tail;
// //新节点存放的下一节点为头节点
// newnode-next phead;
// //头节点的prev存放新节点方便尾插
// phead-prev newnode;
//}//头插
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}
//void ListPushFront(LTNode* phead, LTDataType x)
//{
// assert(phead);
//
// LTNode* newnode BuyListNode(x);
// LTNode* next phead-next;
//
// next-prev newnode; //1
// newnode-next next; //2
// newnode-prev phead; //3
// phead-next newnode; //4
//
// //phead-next newnode;
// //newnode-prev phead;
// //newnode-next next;
// //next-prev newnode;
//
//}//判断链表是否被删空
bool ListEmptyLTNode(LTNode* phead)
{assert(phead);/*链表返回只剩头节点(链表已经被删空)为真否则为假*/return phead-next phead;
}//尾删
void ListPopBack(LTNode* phead)
{assert(phead);//判断链表是否被删空为真即为假为假即为真assert(!ListEmptyLTNode(phead));//assert(phead-next ! phead);ListErase(phead-prev);
}
//void ListPopBack(LTNode* phead)
//{
// assert(phead);
// //判断链表是否被删空为真即为假为假即为真
// assert(!ListEmptyLTNode(phead));//assert(phead-next ! phead);
//
// //head的前一个即为尾巴
// LTNode* tail phead-prev;//head前一个节点
// LTNode* tailPrev tail-prev;//tail的前一个节点
//
// free(tail);//删除节点
//
// //重新链接新尾节点
// tailPrev-next phead;
// phead-prev tailPrev;
//}//头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListEmptyLTNode(phead));ListErase(phead-next);
}
//void ListPopFront(LTNode* phead)
//{
// assert(phead);
// assert(!ListEmptyLTNode(phead));
//
// LTNode* next phead-next;
// LTNode* nnext next-next;
//
// free(next);//删除节点
//
// phead-next nnext;
// nnext-prev phead;
//}//pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev pos-prev;LTNode* newnode BuyListNode(x);//prev newnode posprev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;//此时既然已经做到了可以任意位置插入//那就可以对头插尾插进行复用简化代码
}//删除pos位置的节点
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;prev-next next;next-prev prev;free(pos);//此时既然已经做到了可以任意位置插入//那就可以对头删尾插进行复用简化代码
}//求链表长度
int ListSize(LTNode* phead)
{assert(phead);//跳过哨兵位LTNode* cur phead-next;//求长度int size 0;while (cur!phead){size;cur cur-next;}//返回链表长度return size;/*不要用头节点存储来计算长度int符合但其他类型例如chardouble 都会出现错误
*/
}/*phead为原双链表x表示被查找元素*/
int ListFind(LTNode* phead, LTDataType x)
{assert(phead);/*新建一个指针t初始化为头指针 head*/LTNode* temp phead-next;int i 1;while (temp!phead){if (temp-data x){return i;}i;temp temp-next;}/*程序执行至此处表示查找失败*/return 0;
}//销毁链表
void ListDestory(LTNode* phead)
{assert(phead);LTNode* cur phead-next;int size 0;while (cur ! phead){LTNode* next cur-next;ListErase(cur);cur next;}free(phead);//只是将指向plist的指针置空要置空plist要在Test.c中完成phead NULL;
}test.c
test.c只是用于测试代码菜单的写法本文将不进行讲解。 但test.c中含有对查找and销毁and存储链元素个数的使用方法进行了示例可以当参考。
#include List.hvoid Test1()
{//LTNode* plist NULL;//ListInit(plist);LTNode* plist ListInit();ListPushBack(plist, 0);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPushFront(plist, 10);ListPrint(plist);
}void Test2()
{//LTNode* plist NULL;//ListInit(plist);LTNode* plist ListInit();ListPushFront(plist, 0);ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPushBack(plist, 5);ListPrint(plist);ListPopBack(plist);ListPrint(plist);ListPopFront(plist);ListPrint(plist);int lf ListFind(plist, 5);if (lf1)printf(找到了%d\n,lf);elseprintf(没找到\n);printf(存储的元素个数为%d\n, ListSize(plist));ListDestory(plist);plist NULL;if (plist NULL)printf(销毁成功);
}int main()
{Test2();return 0;
}本文到这就结束啦本文为万字解读创作不易若喜欢请留下免费的赞吧 感谢阅读
