怎样用Linux内核链表来实现DTLib中的双向循环链表
发布时间：2023-02-27 10:37:28 所属栏目：Linux 来源：
导读：本篇内容介绍了“如何用Linux内核链表来实现DTLib中的双向循环链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅
|
本篇内容介绍了“如何用Linux内核链表来实现DTLib中的双向循环链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！ 如何用Linux内核链表来实现DTLib中的双向循环链表 下来我们来讲讲它的设计思路：数据结点之间在逻辑上构成双向循环链表，头结点仅用于结点的定位。 如何用Linux内核链表来实现DTLib中的双向循环链表 实现思路： 1、通过模板定义 DualCircleList 类。继承自 DualLinkList 类； 2、在 DualCircleList 内部使用 Linux 内核链表进行实现； 3、使用 struct list_head 定义 DualCircleList 的头结点； 实现要点： 1、通过 list_head 进行目标结点定位（position(i)）； 2、通过 list_entry 将 list_head 指针转换为目标结点指针； 3、通过 list_for_each 实现 int find(const T& e) 函数； 下来我们来看看基于 Linux 内核链表的双向循环链表是怎样写的 DualCircleList 源码 #ifndef DUALCIRCLELIST_H #define DUALCIRCLELIST_H #include "DualLinkList.h" #include "LinuxList.h" namespace DTLib { template < typename T > class DualCircleList : public DualLinkList<T> { protected: struct Node : public Object { list_head head; T value; }; list_head m_header; list_head* m_current; list_head* position(int i) const { list_head* ret = const_cast<list_head*>(&m_header); for(int p=0; p<i; p++) { ret = ret->next; } return ret; } int mod(int i) const { return (this->m_length == 0) ? 0 : (i % this->m_length); } public: DualCircleList() { this->m_length = 0; this->m_step = 1; m_current = NULL; INIT_LIST_HEAD(&m_header); } bool insert(const T& e) { return insert(this->m_length, e); } bool insert(int i, const T& e) { bool ret = true; Node* node = new Node(); i = i % (this->m_length + 1); if(node != NULL) { node->value = e; list_add_tail(&node->head, position(i)->next); this->m_length++; } else { THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ..."); } return ret; } bool remove(int i) { bool ret = true; i = mod(i); ret = ((0 <= i) && (i < this->m_length)); if( ret ) { list_head* toDel = position(i)->next; if( m_current == toDel ) { m_current = toDel->next; } list_del(toDel); this->m_length--; delete list_entry(toDel, Node, head); } return ret; } bool set(int i, const T& e) { bool ret = true; i = mod(i); ret = ((0 <= i) && (i < this->m_length)); if( ret ) { list_entry(position(i)->next, Node, head)->value = e; } return ret; } T get(int i) const { T ret; if( get(i, ret) ) { return ret; } else { THROW_EXCEPTION(indexoutofboundsexception, "Invaild parameter i to get element ..."); } } bool get(int i, T& e) const { bool ret = true; i = mod(i); ret = ((0 <= i) && (i < this->m_length)); if( ret ) { e = list_entry(position(i)->next, Node, head)->value; } return ret; } int find(const T& e) const { int ret = -1; int i = 0; list_head* slider = NULL; list_for_each(slider, &m_header) { if( list_entry(slider, Node, head)->value == e ) { ret = i; break; } i++; } return ret; } int length() const { return this->m_length; } void clear() { while( this->m_length > 0 ) { remove(0); } } bool move(int i, int step = 1) { bool ret = (step > 0); i = mod(i); ret = ret && ((0 <= i) && (i < this->m_length)); if( ret ) { m_current = position(i)->next; this->m_step = step; } return ret; } bool end() { return (m_current == NULL) || (this->m_length == 0); } T current() { if( !end() ) { return list_entry(m_current, Node, head)->value; } else { THROW_EXCEPTION(INvalidOPerationException, "No value at current position ..."); } } bool next() { int i = 0; while( (i < this->m_step) && !end() ) { if( m_current != &m_header ) { m_current = m_current->next; i++; } else { m_current = m_current->next; } } if( m_current == &m_header ) { m_current = m_current->next; } return (i == this->m_step); } bool pre() { int i =0; while( (i < this->m_step) && !end() ) { if( m_current != &m_header ) { m_current = m_current->next; i++; } else { m_current = m_current->prev; } } if( m_current == &m_header ) { m_current = m_current->next; } return (i == this->m_step); } ~DualCircleList() { clear(); } }; } #endif // DUALCIRCLELIST_H 下来我们写点测试代码看看上面的代码有没有问题 main.cpp 源码 #include <iostream> #include "DualCircleList.h" using namespace std; using namespace DTLib; int main() { DualCircleList<int> d1; for(int i=0; i<5; i++) { d1.insert(0, i); d1.insert(0, 5); } cout << "begin" << endl; d1.move(d1.length()-1); while( d1.find(5) != -1 ) { if( d1.current() == 5 ) { cout << d1.current() << endl; d1.remove(d1.find(d1.current())); } else { d1.pre(); } } cout << "end" << endl; for(int i=0; i<d1.length(); i++) { cout << d1.get(i) << endl; } return 0; } 我们先来分析下，在插入 i 后，随后便插入 5。先打印出 5 个 5，随后删除这 5 个数，然后在打印出剩下的 4 ~ 0。看看结果是否如我们所分析的那样 “如何用Linux内核链表来实现DTLib中的双向循环链表”的内容就介绍到这里了，感谢大家的阅读。 （编辑：汽车网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |