jquery效果网站,产品网络推广深圳,网站建设算软件还是硬件,怎么看网站是哪个系统做的目录 前言一、定义与结构二、特点与优势三、基本操作四、应用场景五、实现复杂度六、动态图解七、代码模版#xff08;c#xff09;八、经典例题九、总结结语 前言
这一期我们学习双向循环链表。双向循环链表不同于单链表#xff0c;双向循环链表是一种特殊的数据结构… 目录 前言一、定义与结构二、特点与优势三、基本操作四、应用场景五、实现复杂度六、动态图解七、代码模版c八、经典例题九、总结结语 前言
这一期我们学习双向循环链表。双向循环链表不同于单链表双向循环链表是一种特殊的数据结构它结合了双向链表和循环链表的特点。 一、定义与结构
双向循环链表中的每个节点都包含三个部分数据域存储数据、前驱指针指向前一个节点和后继指针指向下一个节点。此外链表的头节点和尾节点通过指针相互连接形成一个闭环。这种结构使得链表可以从任意一个节点开始遍历整个链表。
二、特点与优势
双向访问双向链表允许从任意节点向前或向后遍历这使得在需要频繁访问链表前后节点的场景中双向链表比单向链表更加高效。 循环特性双向循环链表的头尾相连形成一个环这使得在处理需要循环访问所有节点的任务时双向循环链表比单向循环链表更加方便。 灵活性由于节点之间通过指针相互连接双向循环链表在插入和删除节点时具有较高的灵活性。
三、基本操作
创建链表首先需要初始化头节点并设置其前驱指针和后继指针都指向自己以形成闭环。然后根据用户输入或其他数据源依次插入节点。 遍历链表可以从头节点或任意节点开始遍历整个链表。由于链表是循环的因此遍历过程会一直进行直到再次回到起始节点。 插入节点在指定位置插入新节点时需要调整新节点及其相邻节点的前驱和后继指针。 删除节点删除指定节点时需要调整其相邻节点的前驱和后继指针并释放被删除节点的内存空间。 查询节点根据节点位置或数据值查询节点时需要从头节点开始遍历链表直到找到目标节点或遍历完整个链表。
四、应用场景
双向循环链表在需要频繁访问链表前后节点的场景中非常有用。例如在任务调度、缓存管理、图形界面元素管理等场景中双向循环链表可以提供高效的数据访问和操作。
五、实现复杂度
虽然双向循环链表提供了更多的灵活性和功能但其实现复杂度也相对较高。在插入和删除节点时需要处理更多的指针操作这可能会增加代码复杂性和出错风险。因此在实现双向循环链表时需要特别注意指针的正确性和内存管理。
六、动态图解 七、代码模版c
#includeiostream
using namespace std;templatetypename T
struct Node {T data;Node* next;Node* prev;Node(const T value):data(value),next(NULL),prev(NULL){}
};templateclass T
class doubleLinkedNode {
private:NodeT* m_dummyHead;int m_size;
public:doubleLinkedNode();~doubleLinkedNode();void push_front(const T value);void push_back(const T value);void insert_after(NodeT* node, const T value);void delete_node(NodeT* node);void modify(NodeT* node, const T value);NodeT* find(const T value) const;void print()const;int size()const;bool empty()const;
};templateclass T
doubleLinkedNodeT::doubleLinkedNode():m_size(0){m_dummyHead new NodeT(T()); //初始化虚拟头结点自己指向自己m_dummyHead-next m_dummyHead; m_dummyHead-prev m_dummyHead;
}templateclass T
doubleLinkedNodeT::~doubleLinkedNode(){while (m_size 0) {delete_node(m_dummyHead-next);}delete m_dummyHead;m_dummyHead NULL;
}// m_dummyHead m_dummyHead -next
// m_dummyHead newNode m_dummyHead - next
templateclass T
void doubleLinkedNodeT::push_front(const T value){NodeT* newNode new NodeT(value);newNode-prev m_dummyHead;newNode-next m_dummyHead-next; //要好好理解一下这里为什么不直接是 m_dummyHead-nextnewNodem_dummyHead-next-prev newNode;m_dummyHead-next newNode;m_size;
}// m_dummyHead m_dummyHead -next
// m_dummyHead - prev newNode m_dummyHead
templateclass T
void doubleLinkedNodeT::push_back(const T value){NodeT* newNode new NodeT(value);newNode-prev m_dummyHead-prev;newNode-next m_dummyHead; //一定要注意要改变的是newNode和m_dummyHead的前驱和后继节点它们本身不变m_dummyHead-prev-next newNode;m_dummyHead-prev newNode;m_size;
}//插入前node node-next
//插入后node newNode node-next
templateclass T
void doubleLinkedNodeT::insert_after(NodeT* node,const T value){if (!node || node m_dummyHead)return;NodeT* newNode new NodeT(value); //这里有四个箭头代表四个方向我们加入节点就是要处理好这四个箭头newNode-prev node; //这里处理的是newNode的 -newNode-next node-next; // newNode -node-next-prev newNode; //node-next -node-next newNode; //node -m_size;
}//插入前node - prev node node-next
//插入后node - prev node-next
templateclass T
void doubleLinkedNodeT::delete_node(NodeT* node){if (!node || node m_dummyHead)return;node-prev-next node-next;node-next-prev node-prev;delete node;m_size--;
}templateclass T
void doubleLinkedNodeT::modify(NodeT* node, const T value){if (!node || node m_dummyHead)return;node-data value;
}templateclass T
NodeT* doubleLinkedNodeT::find(const T value) const{NodeT* curr m_dummyHead-next;while (curr ! m_dummyHead) {if (curr-data value)return curr;curr curr-next;}return NULL;
}templateclass T
void doubleLinkedNodeT::print() const{NodeT* curr m_dummyHead-next;while (curr ! m_dummyHead) {cout curr-data ;curr curr-next;}cout endl;
}templateclass T
int doubleLinkedNodeT::size() const{return m_size;
}templateclass T
bool doubleLinkedNodeT::empty() const {return m_size 0;
}int main() {doubleLinkedNodeint dll;for (int i 1; i 10; i) {dll.push_back(i);}int M;cin M;while (M--) {int x;cin x;Nodeint* fn dll.find(x);dll.delete_node(fn);dll.push_front(x);dll.print();}return 0;
}
八、经典例题
1. 小王子双链表
#includeiostream
using namespace std;templatetypename T
struct Node {T data;Node* next;Node* prev;Node(const T value):data(value),next(NULL),prev(NULL){}
};templateclass T
class doubleLinkedNode {
private:NodeT* m_dummyHead;int m_size;
public:doubleLinkedNode();~doubleLinkedNode();void push_front(const T value);void push_back(const T value);void insert_after(NodeT* node, const T value);void delete_node(NodeT* node);void modify(NodeT* node, const T value);NodeT* find(const T value) const;void print()const;int size()const;bool empty()const;
};templateclass T
doubleLinkedNodeT::doubleLinkedNode():m_size(0){m_dummyHead new NodeT(T()); //初始化虚拟头结点自己指向自己m_dummyHead-next m_dummyHead; m_dummyHead-prev m_dummyHead;
}templateclass T
doubleLinkedNodeT::~doubleLinkedNode(){while (m_size 0) {delete_node(m_dummyHead-next);}delete m_dummyHead;m_dummyHead NULL;
}// m_dummyHead m_dummyHead -next
// m_dummyHead newNode m_dummyHead - next
templateclass T
void doubleLinkedNodeT::push_front(const T value){NodeT* newNode new NodeT(value);newNode-prev m_dummyHead;newNode-next m_dummyHead-next; //要好好理解一下这里为什么不直接是 m_dummyHead-nextnewNodem_dummyHead-next-prev newNode;m_dummyHead-next newNode;m_size;
}// m_dummyHead m_dummyHead -next
// m_dummyHead - prev newNode m_dummyHead
templateclass T
void doubleLinkedNodeT::push_back(const T value){NodeT* newNode new NodeT(value);newNode-prev m_dummyHead-prev;newNode-next m_dummyHead; //一定要注意要改变的是newNode和m_dummyHead的前驱和后继节点它们本身不变m_dummyHead-prev-next newNode;m_dummyHead-prev newNode;m_size;
}//插入前node node-next
//插入后node newNode node-next
templateclass T
void doubleLinkedNodeT::insert_after(NodeT* node,const T value){if (!node || node m_dummyHead)return;NodeT* newNode new NodeT(value); //这里有四个箭头代表四个方向我们加入节点就是要处理好这四个箭头newNode-prev node; //这里处理的是newNode的 -newNode-next node-next; // newNode -node-next-prev newNode; //node-next -node-next newNode; //node -m_size;
}//插入前node - prev node node-next
//插入后node - prev node-next
templateclass T
void doubleLinkedNodeT::delete_node(NodeT* node){if (!node || node m_dummyHead)return;node-prev-next node-next;node-next-prev node-prev;delete node;m_size--;
}templateclass T
void doubleLinkedNodeT::modify(NodeT* node, const T value){if (!node || node m_dummyHead)return;node-data value;
}templateclass T
NodeT* doubleLinkedNodeT::find(const T value) const{NodeT* curr m_dummyHead-next;while (curr ! m_dummyHead) {if (curr-data value)return curr;curr curr-next;}return NULL;
}templateclass T
void doubleLinkedNodeT::print() const{NodeT* curr m_dummyHead-next;while (curr ! m_dummyHead) {cout curr-data ;curr curr-next;}cout endl;
}templateclass T
int doubleLinkedNodeT::size() const{return m_size;
}templateclass T
bool doubleLinkedNodeT::empty() const {return m_size 0;
}int main() {doubleLinkedNodeint dll;for (int i 1; i 10; i) {dll.push_back(i);}int M;cin M;while (M--) {int x;cin x;Nodeint* fn dll.find(x);dll.delete_node(fn);dll.push_front(x);dll.print();}return 0;
}
九、总结
综上所述双向循环链表是一种功能强大且灵活的数据结构适用于需要频繁访问链表前后节点的场景。然而其实现复杂度也相对较高需要开发者具备扎实的编程基础和内存管理能力。
结语
当前进阶的数据结构比之前学的初级数据结构要复杂了希望大家一定要动手敲一遍代码敲完之后提交到例题里检查一下是否正确出现bug不用慌张耐心差错这样你的水平才能提升。
希望大家可以一键三连后续我们一起学习谢谢大家
