苏州哪里做网站好,赣州百度,建设银行网站短信错误6次,seo优化网站快速排名目录 前言 一、链表的分类详细 二、双向链表 三、双向链表的实现 四、List.c文件的完整代码 五、使用演示 总结 前言 接着上一篇单链表来详细说说链表中什么是带头和不带头#xff0c;“哨兵位”是什么#xff0c;什么是单向什么是双向#xff0c;什么是循环和不循环。然后实… 目录 前言 一、链表的分类详细 二、双向链表 三、双向链表的实现 四、List.c文件的完整代码 五、使用演示 总结 前言 接着上一篇单链表来详细说说链表中什么是带头和不带头“哨兵位”是什么什么是单向什么是双向什么是循环和不循环。然后实现完整的双向链表代码。 ❤️感谢支持点赞关注不迷路❤️ 一、链表的分类详细 上一篇已经说过链表总共分为8中结构常用的就是单链表和双链表 这里的单链表全称不带头单向不循环链表。双链表全称带头双向循环链表
以下是上一篇中提到的8中结构 注意因为常用的只有单链表和双链表将这两种链表结构掌握之后就能够自行实现其他结构的链表。 1.带头和不带 带头与不带头的区别就是带头的链表有一个头结点head也叫哨兵位。 哨兵位带头链表的头结点不存储任何有效元素仅用于占位代表链表的头部功能类似于“放哨”因此叫哨兵位。
注意上一篇中的单链表是不带头的因此不存在头结点的说法所以上一篇中说的头结点仅仅是为了方便称呼第一个节点的一种不规范叫法只有带头链表才有头结点的说法。尤其是在链表的分类中。 2.单向和双向 区别
结构上单向链表只有一个指向下一个节点的指针。双向链表有一个指向前一个节点的指针和一个指向后一个节点的指针。功能上单向链表只能单向访问下一个节点。双向链表可以既可以访问下一个节点也可以访问上一个节点。 3.循环和不循环 区别不循环链表的尾结点next指针会指向空指针。循环链表的尾结点next指针不为空可以无限循环的访问下一个节点。 注意循环链表的尾结点的next指针可以指向链表的第一个节点或者中间的任一节点甚至尾结点。这都叫循环链表。 二、双向链表
双向链表全称带头双向循环链表。
结构图如下 双向链表的结构声明如下 typedef int LTDataType; //定义双链表结构 typedef struct ListNode { LTDataType data;//存储数据 struct ListNode* next;//指向下一个节点 struct ListNode* prev;//指向上一个节点 }LTNode; 同样双向链表的实现也分为三个文件
List.h双向链表的头文件包含各种库函数头文件、链表结构、函数的声明。List.c用于实现各种接口函数。test.c用于测试。 三、双向链表的实现
1.List.h文件
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef int LTDataType;
//定义双链表结构
typedef struct ListNode
{LTDataType data;//存储数据struct ListNode* next;//指向下一个节点struct ListNode* prev;//指向上一个节点
}LTNode;//初始化
//第一种传二级指针
//void LTInit(LTNode** pphead);
//第二种不传参
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//判空
bool LTEmpty(LTNode* phead);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除指定位置的节点
void LTErase(LTNode* pos);//销毁
//第一种传二级指针
//void LTDesTroy(LTNode** pphead);
//第二种传一级指针缺点是需手动将哨兵位置空
void LTDesTroy(LTNode* phead); 2.List.c文件
1.LTBuyNode函数
//申请新节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;//前后指针全部指向自己自循环newnode-next newnode-prev newnode;return newnode;
}
解析
功能用于申请新节点。参数新节点的需数据x使用malloc函数申请一个节点空间判空后将其数据域赋值x。注意新节点的两个指针都需要指向自己这样才是一个双向循环链表。因为该函数只为其他函数服务因此可以只在 List.c 文件中定义无需在 List.h 中声明。 2.LTInit函数
//初始化
//第一种传二级指针
//void LTInit(LTNode** pphead)
//{
// assert(pphead);
//
// //创建一个头结点哨兵位
// *pphead LTBuyNode(-1);
//}//第二种不传参
LTNode* LTInit()
{return LTBuyNode(-1);
}
解析
该函数有两个版本第二种为优化后的版本为的是保持接口的一致性因为双向链表的其它功能函数都只是传一级指针。为了避免混淆优化为不传参版本。功能初始化为哨兵位头结点。第一种需要传参版本传二级指针因为只有二级指针才能修改一级指针的指向。因此这里使用二级指针进行初始化赋值。-1可以改为任何值因为哨兵位存储的数据为无效数据。第二种不传参版本直接创建并返回哨兵位的地址。使用上的区别第一种需要自己定义一个双向链表类型的空指针然后使用调用该函数进行传参初始化注意传参时需。第二种自己创建一个双向链表类型的空指针并调用该函数进行赋值。 3.LTPrint函数
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}
解析
功能打印链表的所有节点数据。参数链表的头结点哨兵位。首先断言头结点不能为空创建一个 pcur 指针指向第一个有效节点然后进行循环遍历时因为该链表是循环链表因此循环一遍的判定是 pcur 指向的节点不是头结点。循环体里就是打印数据然后让pcur走向下一个节点。打印完后换行即可。 4.LTPushBack函数
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//首先修改新节点的指针指向newnode-next phead;//next指针指向哨兵位newnode-prev phead-prev;//prev指针指向尾节点//再修改旧尾节点和哨兵位phead-prev-next newnode;//旧尾节点的next指针指向新尾节点phead-prev newnode;//哨兵位后指针指向新尾节点
}
解析
功能在链表的尾部插入一个节点参数头结点哨兵位和需要插入的节点数据首先断言头结点不为空申请新节点然后就需要改变新节点和受影响节点的指针指向。这里需要注意修改的前后顺序先修改新节点的指针指向新节点的 next 指针应该指向头结点因为是循环链表原尾结点可以通过头结点找到即 phead-prev 指向的就是原来的尾结点将新节点的 prev 指针指向原尾结点。修改完新节点就需要修改头结点和原尾结点的指针指向原尾结点依旧可以通过头结点的 prev 指针找到将其 next 指针指向新节点。最后就是头结点的 prev 指针需要指向新节点。 5.LTPushFront函数
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//首先还是先修改新节点的指向newnode-next phead-next;newnode-prev phead;//然后修改旧头结点和哨兵位phead-next-prev newnode;phead-next newnode;
}
解析
功能在第一个有效节点之前插入数据也就是头结点哨兵位之后参数头结点哨兵位和需插入的节点数据、首先头插为什么不是在头结点前面插入数据很简单头结点的 prev 指针就是指向尾结点的所以如果在头结点之前插入数据其实就是尾插。实现过程开头还是断言和申请新节点然后先修改新节点的前后指针指向原第一个有效节点可以通过头结点的 next 指针找到。修改完新节点后就修改原第一节点的prve指针使其指向新节点最后修改头结点的 next 指针也指向新节点。 6.LTEmpty函数
//判空
//只有哨兵位节点说明链表为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}
解析
功能判断链表是不是空链表也就是判断链表是不是只有头结点哨兵位参数头结点哨兵位该函数主要为后续删除链表节点时判断链表是否为空链表实现简单断言头结点后直接判断头结点的下一个节点是不是还是头结点即可。 7.LTPopBack函数
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//先保存尾结点和倒数第二个节点LTNode* del phead-prev;LTNode* prev del-prev;//再修改倒数第二节点和哨兵位节点指向prev-next phead;phead-prev prev;//释放尾结点free(del);del NULL;
}
解析
功能删除尾结点参数头结点哨兵位首先断言判断头结点是否为空指针以及链表是否为空链表然后创建 del 指针保存尾结点创建 prev 指针保存倒数第二个节点避免修改完受影响节点的前后指针指向后找不到尾结点然后修改倒数第二个节点的 next 指针指向头结点以及头结点的 prev 指针指向倒数第二个节点。最后释放尾结点del最后释放尾结点 del 即可。 8.LTPopFront函数
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//还是先保存第一个有效节点LTNode* del phead-next;del-next-prev phead;//修改第二个有效节点指向phead-next del-next;//修该哨兵位指向//释放free(del);del NULL;
}
解析
功能删除第一个有效节点也就是头结点哨兵位的下一个节点参数头结点哨兵位还是先断言判断头结点和链表是否为空创建 del 指针保存第一个有效节点然后先通过 del指针找到并修改第二个有效节点的 prev 指针使其指向头结点再修改头结点的 next 指针指向第二个节点。最后就可以直接释放第一个节点 del 即可。 9.LTFind函数
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;//循环遍历while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
解析
功能根据指定数据查找对应的节点然后返回该节点的地址主要是配合后面两个函数使用有了上面函数实现的经验查找函数实现简单循环遍历循环链表循环一遍的标志是下一节点为头结点找到就返回节点的地址找不到返回空指针。 10.LTInsert函数
//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//先修改新节点朝向newnode-next pos-next;newnode-prev pos;//在修改受影响的两个节点朝向注意顺序pos-next-prev newnode;pos-next newnode;
}
解析
功能在指定位置之后插入数据这个指定位置需要通过 LTFind 函数指定。双向链表插入数据其实都差不多先修改新节点的前后指针再修改受影响节点的指针。这里不再赘述。 11.LTErase函数
//删除指定位置的节点
void LTErase(LTNode* pos)
{assert(pos);//先修改pos的前后节点pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}
解析
功能删除指定位置的节点这个实现更加简单通过 pos 指针先修改前后节点的指针指向然后就可以直接释放掉自己。 11.LTDesTroy函数
//销毁
//第一种传二级指针
//void LTDesTroy(LTNode** pphead)
//{
// assert(pphead *pphead);
//
// LTNode* pcur (*pphead)-next;
// while (pcur ! *pphead)
// {
// LTNode* Next pcur-next;
// free(pcur);
// pcur Next;
// }
//
// free(*pphead);
// *pphead NULL;
// pcur NULL;
//}//第二种传一级指针缺点是需手动将哨兵位置空
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* Next pcur-next;free(pcur);pcur Next;}free(phead);phead pcur NULL;
}
解析
销毁函数有两种第二种为优化后的版本同样也是为了接口的一致性避免使用时混淆因此传一级指针合适但是带来的缺点就是需要手动将哨兵位置空。两个版本的函数实现方式大致相同循环遍历在释放当前节点之前要先使用 Next 指针保存下一节点的地址。第一个版本缺点是需要传二级指针但是不需要手动将哨兵位置空函数内部就可以实现置空第二版本优点就是同其他接口一样只需要传一级指针缺点就是在调用完该函数后需要手动将哨兵位置空。 四、List.c文件的完整代码
#include List.h//申请新节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;//前后指针全部指向自己自循环newnode-next newnode-prev newnode;return newnode;
}//初始化
//第一种传二级指针
//void LTInit(LTNode** pphead)
//{
// assert(pphead);
//
// //创建一个头结点哨兵位
// *pphead LTBuyNode(-1);
//}//第二种不传参
LTNode* LTInit()
{return LTBuyNode(-1);
}//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//首先修改新节点的指针指向newnode-next phead;//next指针指向哨兵位newnode-prev phead-prev;//prev指针指向尾节点//再修改旧尾节点和哨兵位phead-prev-next newnode;//旧尾节点的next指针指向新尾节点phead-prev newnode;//哨兵位后指针指向新尾节点
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//首先还是先修改新节点的指向newnode-next phead-next;newnode-prev phead;//然后修改旧头结点和哨兵位phead-next-prev newnode;phead-next newnode;
}//判空
//只有哨兵位节点说明链表为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//先保存尾结点和倒数第二个节点LTNode* del phead-prev;LTNode* prev del-prev;//再修改倒数第二节点和哨兵位节点指向prev-next phead;phead-prev prev;//释放尾结点free(del);del NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//还是先保存第一个有效节点LTNode* del phead-next;del-next-prev phead;//修改第二个有效节点指向phead-next del-next;//修该哨兵位指向//释放free(del);del NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;//循环遍历while (pcur ! phead){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//先修改新节点朝向newnode-next pos-next;newnode-prev pos;//在修改受影响的两个节点朝向注意顺序pos-next-prev newnode;pos-next newnode;
}//删除指定位置的节点
void LTErase(LTNode* pos)
{assert(pos);//先修改pos的前后节点pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}//销毁
//第一种传二级指针
//void LTDesTroy(LTNode** pphead)
//{
// assert(pphead *pphead);
//
// LTNode* pcur (*pphead)-next;
// while (pcur ! *pphead)
// {
// LTNode* Next pcur-next;
// free(pcur);
// pcur Next;
// }
//
// free(*pphead);
// *pphead NULL;
// pcur NULL;
//}//第二种传一级指针缺点是需手动将哨兵位置空
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* Next pcur-next;free(pcur);pcur Next;}free(phead);phead pcur NULL;
} 五、使用演示
使用测试文件 test.c 进行演示
#include List.hvoid ListTest1()
{//创建哨兵位头结点LTNode* plist LTInit();//尾插4个节点LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);printf(尾插);LTPrint(plist);//头插4个节点LTPushFront(plist, 11);LTPushFront(plist, 12);LTPushFront(plist, 13);LTPushFront(plist, 14);printf(头插);LTPrint(plist);//在1后面插入一个数据LTInsert(LTFind(plist, 1), 66);printf(在1后面插入66);LTPrint(plist);//尾删LTPopBack(plist);printf(尾删);LTPrint(plist);//头删LTPopFront(plist);printf(头删);LTPrint(plist);//删除11LTErase(LTFind(plist, 11));printf(删除11);LTPrint(plist);//销毁LTDesTroy(plist);plist NULL;//需要手动置空printf(链表已销毁\n);}int main()
{ListTest1();return 0;
}
运行结果 总结 以上就是本文的全部内容感谢支持。
