【初阶数据结构】双向链表
文章目录
双向链表
链表分类 8种 (带头/不带头 单向/双向 循环/循环)
最常用两种 单链表(不带头单向不循环链表) 双向链表(带头双向循环链表)
双链表有 头节点(哨兵位) 后继指针(next) 前驱指针(prev)
双向链表为空时,为一个哨兵位
同样采用多文件操作
1.申请节点
//申请节点LTNode* LTBuyNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL)//申请不成功{perror(\"malloc fail\");exit(1);//给非0值}node->data = x;node->next = node->prev = node;return node;}
2.链表初始化
void LTInit(LTNode** pphead){//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);//随便赋一个值}
3.尾插
以上图为例 尾插时 head->prev指向的就是d3
void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;//也就是newnode->prev指向d3newnode->next = phead;phead->prev->next = newnode;//d3的next指针指向新节点phead->prev = newnode;}
4.打印链表
让pcur指向phead的next指针,然后遍历链表,直到pcur=phead
void LTPrint(LTNode* phead){LTNode* pcur = phead->next;while (pcur != phead){printf(\"%d->\", pcur->data);pcur = pcur->next;}printf(\"\\n\");}
5.头插
头插是插到头结点与d1之间,插在头结点前边跟尾插一样(因为链表是双向循环的)
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;}
6.尾删
void LTPopBack(LTNode* phead){//链表必须有效且链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->prev; del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;}
7.头删
void LTPopFront(LTNode* phead){assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;}
8.查找
LTNode* LTFind(LTNode* phead, LTDataType x){LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;}
9.指定位置插入
10.删除pos节点
void LTErase(LTNode* pos)//这里传一级指针是为了保持接口的一致性 其他函数传的都是一级指针{//pos理论上来说不能为phead,但是参数没有phead,所以无法增加校验pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;}
11.链表的销毁
void LTDesTroy(LTNode* phead){assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;//如果不置为空 plist(保存的地址空间被释放掉了) 若后续不再使用plist则没问题(野指针)}
12.程序源码
List.h
#pragma once#include#include#includetypedef int LTDataType;//定义双向链表节点的结构typedef struct ListNode{LTDataType data;struct ListNode* next;struct ListNode* prev;}LTNode;//声明双向链表种提供的方法//初始化void LTInit(LTNode** pphead);void LTPrint(LTNode* phead);//插入数据之前,链表必须初始化到只有一个头结点的情况// 不改变哨兵位的地址,所以传一级指针即可//尾插void LTPushBack(LTNode* phead,LTDataType x);//头插void LTPushFront(LTNode* phead, LTDataType x);void LTPopBack(LTNode* phead);void LTPopFront(LTNode* phead);//在pos位置之后插入数据void LTInsert(LTNode* pos, LTDataType x);void LTErase(LTNode* pos);//查找LTNode* LTFind(LTNode* phead, LTDataType x);void LTDesTroy(LTNode* phead);
List.c
#include\"List.h\";void LTPrint(LTNode* phead){LTNode* pcur = phead->next;while (pcur != phead){printf(\"%d->\", pcur->data);pcur = pcur->next;}printf(\"\\n\");}//申请节点LTNode* LTBuyNode(LTDataType x){LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror(\"malloc fail\");exit(1);//给非0值}node->data = x;node->next = node->prev = node;return node;}void LTInit(LTNode** pphead){//给双向链表创建一个哨兵位*pphead = LTBuyNode(-1);}//尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;//不能交换位置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;}//尾删void LTPopBack(LTNode* phead){//链表必须有效且链表不能为空assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;}//头删void LTPopFront(LTNode* phead){assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;}//查找LTNode* LTFind(LTNode* phead, LTDataType x){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;}//删除pos节点void LTErase(LTNode* pos)//这里传一级指针是为了保持接口的一致性 其他函数传的都是一级指针{//pos理论上来说不能为phead,但是参数没有phead,所以无法增加校验pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;}//链表销毁void LTDesTroy(LTNode* phead){assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;//如果不置为空 plist(保存的地址空间被释放掉了) 若后续不再使用plist则没问题(野指针)}//LTErase和LTDestroy参数理论上要传二级,因为我们需要让形参的改变影响到实参,但是为了接口的一致性才穿的一级//传一级存在的问题是,当形参phead置为NULL后,实参plist不会被修改为NULL,因此解决方法是 调用完方法后手动将实参置为NULL
test.c
#define _CRT_SECURE_NO_WARNINGS#include\"List.h\";void ListTest01(){LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopFront(plist);LTPushFront(plist, 3);LTPrint(plist);LTNode* find = LTFind(plist, 3);{if (find == NULL){printf(\"找不到\\n\");}else{printf(\"找到了\\n\");}}LTInsert(find, 66);LTPrint(plist);LTErase(find);LTPrint(plist);}int main(){ListTest01();return 0;}