北京网站建设 合一,什么是搜索引擎,网站,公众号开发用什么工具数据结构 | 带头双向循环链表专题
前言 前面我们学了单链表#xff0c;我们这次来看一个专题带头的双向循环链表~~ 文章目录 数据结构 | 带头双向循环链表专题前言带头双向循环链表的结构实现双向链表头文件的定义创建节点哨兵位初始化尾插尾删头插头删打印查找指定位置前插入…数据结构 | 带头双向循环链表专题
前言 前面我们学了单链表我们这次来看一个专题带头的双向循环链表~~ 文章目录 数据结构 | 带头双向循环链表专题前言带头双向循环链表的结构实现双向链表头文件的定义创建节点哨兵位初始化尾插尾删头插头删打印查找指定位置前插入删除指定位置销毁链表List.hList.c 带头双向循环链表的结构 注意这里的“带头”跟前面我们说的“头节点”是两个概念实际前面的在单链表阶段称呼不严 谨但是为了同学们更好的理解就直接称为单链表的头节点。带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这里“放哨 的”
哨兵位存在的意义
遍历循环链表避免死循环。 每个节点有三部分内容 保存数据的val保存下一个节点的地址next指针保存前一个节点的地址prev指针
实现双向链表
我们需要实现以下功能
头文件的定义
List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h// 带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _val;struct ListNode* _next;struct ListNode* _prev;
}ListNode;//哨兵位初始化
ListNode* ListInit();// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType* x);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);创建节点
malloc一个节点然后让新节点的next和prev赋值为空将值给了val最后返回空间
ListNode* ListCreate(LTDataType* x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail!\n);exit(-1);}newnode-_val x;newnode-_next NULL;newnode-_prev NULL;return newnode;
}哨兵位初始化
这里我们初始化成-1代表是哨兵位然后让前驱指针和next指针指向自己
ListNode* ListInit()
{ListNode* pHead ListCreate(-1);pHead-_next pHead;pHead-_prev pHead;return pHead;
}尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* tail pHead-_prev;ListNode* newnode ListCreate(x);// phead tail newnodetail-_next newnode;newnode-_prev tail;newnode-_next pHead;pHead-_prev newnode;
}尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead-_next ! pHead);ListNode* tail pHead-_prev;ListNode* tailprev tail-_prev;free(tail);tailprev-_next pHead;pHead-_prev tailprev;
}头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-_next;ListNode* newnode ListCreate(x);pHead-_next newnode;newnode-_prev pHead;newnode-_next cur;cur-_prev newnode;
}头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead-_next ! pHead);ListNode* first pHead-_next;ListNode* second first-_next;pHead-_next second;second-_prev pHead;free(first);first NULL;
}打印
void ListPrint(ListNode* pHead)
{ListNode* tail pHead-_next;printf(哨兵位-);while (tail ! pHead){printf(%d-, tail-_val);tail tail-_next;}printf(NULL\n);
}查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){if (cur-_val x){return cur;}cur cur-_next;}return NULL;
}指定位置前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode ListCreate(x);ListNode* prev pos-_prev;prev-_next newnode;newnode-_prev prev;pos-_prev newnode;newnode-_next pos;
}删除指定位置
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev pos-_prev;ListNode* next pos-_next;prev-_next next;next-_prev prev;free(pos);pos NULL;
}销毁链表
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-_next;while (cur ! pHead){ListNode* next cur-_next;free(cur);cur next;}free(pHead);pHead NULL;
}List.h
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int LTDataType;typedef struct ListNode {LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化哨兵位
LTNode* LTInit();
//创建节点
LTNode* LTcreate(LTDataType x);
//销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判断是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//指定位置插入
void LTInsert(LTNode* pos, LTDataType x);
//指定位置删除
LTNode* LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);List.c
#define _CRT_SECURE_NO_WARNINGS 1#includeList.h//初始化哨兵位
LTNode* LTInit()
{LTNode* phead LTcreate(-1);phead-next phead;phead-prev phead;return phead;
}
//创建节点
LTNode* LTcreate(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail!\n);exit(-1);}newnode-next NULL;newnode-prev NULL;newnode-val x;return newnode;
} //销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead)
{assert(phead);printf(哨兵位-);LTNode* cur phead-next;while (cur ! phead){printf(%d-, cur-val);cur cur-next;}printf(\n);
}
//判断是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-val 0;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTcreate(x);LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail phead-prev;LTNode* tailprev tail-prev;free(tail);tail NULL;tailprev-next phead;phead-prev tailprev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTcreate(x);LTNode* cur phead-next;phead-next newnode;newnode-prev phead;cur-prev newnode;newnode-next cur;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* first phead-next;LTNode* second first-next;free(first);phead-next second;second-prev phead;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-val x){return cur;}cur cur-next;}return NULL;
}//指定位置的前面插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTcreate(x);LTNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;}
//指定位置删除
LTNode* LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;free(pos);posprev-next posnext;posprev posprev;
}顺序表和双向链表的分析
不同点顺序表链表单链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁 好了双向链表就到这里结束了有用的话点个赞吧~~
