月华透云上枝头稚雏也学雀南飞。此朝花间挑芙蓉莺莺燕燕娇欲滴。岂敢良景乏乏眼正是华灯初上时。可将此生留其中往是你去也是你。1. 链表的分类1.1单双向单向链表以单链表为例子双向链表以双链表为例1.2带头或不带头不带头头节点直接存储有效数据带头头节点不存储有效数据而是存储第一个有效节点的地址可视为占位子或者哨兵位1.3循环和不循环不循环存在尾结点也可以说某个节点的next指针指向NULL循环所有结点中的next指针没有指向NULL综上所述可以列举出八种不同的链表类型日常主要是应用两种链表Ⅰ无头单向非循环链表即单链表结构简单一般不会用于单独存储数据实际应用于作为其他数据结构的子结构如哈希桶图的邻接表等Ⅱ带头双向循环链表结构复杂一般用于单独存储数据一个节点由三个部分组成前驱指针后驱指针保存数据2.双链表的接头实现C语言2.1对双链表类型的成员定义包含的重命名typedef int LTDataType; typedef struct ListNode { LTDataType data;//要存储的有效数据 struct ListNode* next;//保存下一个节点地址的指针 struct ListNode* prev;//保存上一个节点地址的指针 }LTNode;2.2双链表初始化以下代码存在一些问题pphead可能不为空指针但*pphead可能为空指针因为情况一此时链表中不存在节点此处初始化的节点是第一个节点运行程序时可能会出现问题void LTInit(LTNode** pphead) { assert(pphead);//判断是否为NULL防止对空指针解引用 (*pphead)-data -1;//将存储的有效数据初始化为-1 (*pphead)-prev (*pphead)-next *pphead;//前驱指针和后驱指针全部指向自身 }2.0初始化版本void LTInit(LTNode** pphead) { assert(pphead); LTBuyNode(-1);//后面的函数调用作用是申请一个节点的空间并将有效数据保存其中 }2.3双链表创建节点空间LTNode* LTBuyNode(LTDataType x) { LTNode* newnode (LTNode*)malloc(sizeof(LTNode)); //申请一个节点的空间并且保存这个空间的地址给newnode if (newnode NULL) { perror(malloc fail!); exit(1); }//判断是否申请空间成功 newnode-data x;//将数据保存到新申请的节点中 newnode-prev newnode-next newnode;//将前驱指针和后驱指针全部指向自身 return newnode;//返回新节点的地址 }2.4双链表的打印void LTPrint(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; } printf(\n); }2.5双链表的尾插头节点不需要改变则传一级指针否则传二级指针观察上方两幅图示可知仅需改变原链表d3的next指向newnodehead的prev指向newnode新节点prev指向d3next指向headvoid LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); //优先改变对原链表无影响的部分即新插入的节点 newnode-prev phead-prev; newnode-next phead; //再修改原链表 phead-prev-next newnode;//尾节点修改 phead-prev newnode;//头节点修改 }2.6判断链表是否为空仅有一个头节点的情况下双链表为空bool LTEmpty(LTNode* phead) { assert(phead); return phead-next phead; }2.7双链表的尾删注意链表不可为空主要修改对象是头节点和倒数第二个节点修改对象倒数第二个节点的next指向头节点head-prev指向倒数第二个节点void LTPopBack(LTNode* phead) { assert(!LTEmpty(phead)); LTNode* del phead-prev; del-prev-next phead; phead-prev del-prev; free(del); del NULL; }2.8双链表的头插在第一个有效节点前插入注意不能先使head-next指向new-prev这样会使原链表的第一个节点地址丢失故先使d1-prev指向newnode再使head-next指向newnodevoid LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); newnode-next phead-next;//新节点的next指向原链表的第一个节点 newnode-prev phead;//新节点的prev指向头节点 phead-next-prev newnode;//原链表的第一个节点的prev指向新节点 phead-next newnode;//头节点的next指向新节点 }2.9双链表的头删修改对象d2的prev指向headhead的next指向d2void LTPopFront(LTNode* phead) { assert(!LTEmpty(phead)); LTNode* del phead-next;//del指向第一个有效节点 del-next-prev phead;//原链表的第二个节点的prev指向头节点 phead-next del-next;//头节点的next指向原链表的第二个节点 free(del); del NULL; }2.10双链表的查找LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur phead-next;//pcur初始化指向第一个有效节点 while (pcur ! phead) { if (pcur-data x) { return pcur; } pcur pcur-next;//pcur指针不断向后移动直到指向头节点退出 } return NULL; }2.11删除双链表中指定位置pos的节点void LTErase(LTNode* pos) { assert(pos); pos-next-prev pos-prev;//pos的下一个节点的prev指向pos的前一个节点 pos-prev-next pos-next;//pos的前一个节点的next指向pos的下一个节点 free(pos); pos NULL; }2.12在指定位置pos之后插入数据处理对象Ⅰ先对原链表无影响的newnode进行处理newnode的next指向pos的nextnewnode的prev指向posⅡ不可以通过原链表进行改动读者大可一试小编try过几次还是觉得通过新节点间接改动原链表更有效且正确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; }2.13销毁链表void LTDestroy(LTNode** pphead) { LTNode* pcur (*pphead)-next; while (pcur ! *pphead) { LTNode* next pcur-next; free(pcur); pcur next; } free(*pphead); *pphead NULL; }双链表的销毁需要一个一个节点单独销毁小编给出的销毁实现函数是传入二级指针有违背接口的一致性各位读者也可以改为一级指针之后在调用完函数之后手动置空
还在被双链表绕晕？这篇保姆级教程带你彻底吃透（含完整C实现）
月华透云上枝头稚雏也学雀南飞。此朝花间挑芙蓉莺莺燕燕娇欲滴。岂敢良景乏乏眼正是华灯初上时。可将此生留其中往是你去也是你。1. 链表的分类1.1单双向单向链表以单链表为例子双向链表以双链表为例1.2带头或不带头不带头头节点直接存储有效数据带头头节点不存储有效数据而是存储第一个有效节点的地址可视为占位子或者哨兵位1.3循环和不循环不循环存在尾结点也可以说某个节点的next指针指向NULL循环所有结点中的next指针没有指向NULL综上所述可以列举出八种不同的链表类型日常主要是应用两种链表Ⅰ无头单向非循环链表即单链表结构简单一般不会用于单独存储数据实际应用于作为其他数据结构的子结构如哈希桶图的邻接表等Ⅱ带头双向循环链表结构复杂一般用于单独存储数据一个节点由三个部分组成前驱指针后驱指针保存数据2.双链表的接头实现C语言2.1对双链表类型的成员定义包含的重命名typedef int LTDataType; typedef struct ListNode { LTDataType data;//要存储的有效数据 struct ListNode* next;//保存下一个节点地址的指针 struct ListNode* prev;//保存上一个节点地址的指针 }LTNode;2.2双链表初始化以下代码存在一些问题pphead可能不为空指针但*pphead可能为空指针因为情况一此时链表中不存在节点此处初始化的节点是第一个节点运行程序时可能会出现问题void LTInit(LTNode** pphead) { assert(pphead);//判断是否为NULL防止对空指针解引用 (*pphead)-data -1;//将存储的有效数据初始化为-1 (*pphead)-prev (*pphead)-next *pphead;//前驱指针和后驱指针全部指向自身 }2.0初始化版本void LTInit(LTNode** pphead) { assert(pphead); LTBuyNode(-1);//后面的函数调用作用是申请一个节点的空间并将有效数据保存其中 }2.3双链表创建节点空间LTNode* LTBuyNode(LTDataType x) { LTNode* newnode (LTNode*)malloc(sizeof(LTNode)); //申请一个节点的空间并且保存这个空间的地址给newnode if (newnode NULL) { perror(malloc fail!); exit(1); }//判断是否申请空间成功 newnode-data x;//将数据保存到新申请的节点中 newnode-prev newnode-next newnode;//将前驱指针和后驱指针全部指向自身 return newnode;//返回新节点的地址 }2.4双链表的打印void LTPrint(LTNode* phead) { LTNode* pcur phead-next; while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; } printf(\n); }2.5双链表的尾插头节点不需要改变则传一级指针否则传二级指针观察上方两幅图示可知仅需改变原链表d3的next指向newnodehead的prev指向newnode新节点prev指向d3next指向headvoid LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); //优先改变对原链表无影响的部分即新插入的节点 newnode-prev phead-prev; newnode-next phead; //再修改原链表 phead-prev-next newnode;//尾节点修改 phead-prev newnode;//头节点修改 }2.6判断链表是否为空仅有一个头节点的情况下双链表为空bool LTEmpty(LTNode* phead) { assert(phead); return phead-next phead; }2.7双链表的尾删注意链表不可为空主要修改对象是头节点和倒数第二个节点修改对象倒数第二个节点的next指向头节点head-prev指向倒数第二个节点void LTPopBack(LTNode* phead) { assert(!LTEmpty(phead)); LTNode* del phead-prev; del-prev-next phead; phead-prev del-prev; free(del); del NULL; }2.8双链表的头插在第一个有效节点前插入注意不能先使head-next指向new-prev这样会使原链表的第一个节点地址丢失故先使d1-prev指向newnode再使head-next指向newnodevoid LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode LTBuyNode(x); newnode-next phead-next;//新节点的next指向原链表的第一个节点 newnode-prev phead;//新节点的prev指向头节点 phead-next-prev newnode;//原链表的第一个节点的prev指向新节点 phead-next newnode;//头节点的next指向新节点 }2.9双链表的头删修改对象d2的prev指向headhead的next指向d2void LTPopFront(LTNode* phead) { assert(!LTEmpty(phead)); LTNode* del phead-next;//del指向第一个有效节点 del-next-prev phead;//原链表的第二个节点的prev指向头节点 phead-next del-next;//头节点的next指向原链表的第二个节点 free(del); del NULL; }2.10双链表的查找LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur phead-next;//pcur初始化指向第一个有效节点 while (pcur ! phead) { if (pcur-data x) { return pcur; } pcur pcur-next;//pcur指针不断向后移动直到指向头节点退出 } return NULL; }2.11删除双链表中指定位置pos的节点void LTErase(LTNode* pos) { assert(pos); pos-next-prev pos-prev;//pos的下一个节点的prev指向pos的前一个节点 pos-prev-next pos-next;//pos的前一个节点的next指向pos的下一个节点 free(pos); pos NULL; }2.12在指定位置pos之后插入数据处理对象Ⅰ先对原链表无影响的newnode进行处理newnode的next指向pos的nextnewnode的prev指向posⅡ不可以通过原链表进行改动读者大可一试小编try过几次还是觉得通过新节点间接改动原链表更有效且正确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; }2.13销毁链表void LTDestroy(LTNode** pphead) { LTNode* pcur (*pphead)-next; while (pcur ! *pphead) { LTNode* next pcur-next; free(pcur); pcur next; } free(*pphead); *pphead NULL; }双链表的销毁需要一个一个节点单独销毁小编给出的销毁实现函数是传入二级指针有违背接口的一致性各位读者也可以改为一级指针之后在调用完函数之后手动置空
