本篇内容介绍了“如何用Linux内核链表来实现DTLib中的双向循环链表”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
网站建设哪家好,找成都创新互联公司!专注于网页设计、网站建设、微信开发、成都微信小程序、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了木兰免费建站欢迎大家使用!
继承关系如下图所示
下来我们来讲讲它的设计思路:数据结点之间在逻辑上构成双向循环链表,头结点仅用于结点的定位。如下图所示
实现思路:
1、通过模板定义 DualCircleList 类。继承自 DualLinkList 类;
2、在 DualCircleList 内部使用 Linux 内核链表进行实现;
3、使用 struct list_head 定义 DualCircleList 的头结点;
4、特殊处理:循环遍历时忽略头结点
实现要点:
1、通过 list_head 进行目标结点定位(position(i));
2、通过 list_entry 将 list_head 指针转换为目标结点指针;
3、通过 list_for_each 实现 int find(const T& e) 函数;
4、遍历函数中的 next() 和 pre() 需要考虑跳过头结点
下来我们来看看基于 Linux 内核链表的双向循环链表是怎样写的
DualCircleList 源码
#ifndef DUALCIRCLELIST_H #define DUALCIRCLELIST_H #include "DualLinkList.h" #include "LinuxList.h" namespace DTLib { template < typename T > class DualCircleList : public DualLinkList{ 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 (&m_header); for(int p=0; pnext; } 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#include "DualCircleList.h" using namespace std; using namespace DTLib; int main() { DualCircleList 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 我们先来分析下,在插入 i 后,随后便插入 5。先打印出 5 个 5,随后删除这 5 个数,然后在打印出剩下的 4 ~ 0。看看结果是否如我们所分析的那样
“如何用Linux内核链表来实现DTLib中的双向循环链表”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
名称栏目:如何用Linux内核链表来实现DTLib中的双向循环链表
本文地址:http://bjjierui.cn/article/jdidhe.html