/*
简单的list双向链表结构关系
李坤昱
326087275@qq.com
从简单到复杂的学习之路
*/
#include <stdio.h>
template<typename T>
class listnode//观摩linux源码 listnode作为基类，T类 data放置在其派生类中，本例子没做其派生类
{
public:
listnode<T>* prior;//指向之前的地址
listnode<T>* next;//指向下一个地址
T data;//没做数据派生类 ，直接用节点类储存类型数据
int nrecord;//是否已经记录数据
int nend;//末端判断，用变量标志判断，主要是应对CString容器，而不判断T data
listnode()
{
nrecord = 0;
nend = 0;
}
virtual ~listnode(){}
};
template<typename T>
class alloc//简单的内存分配
{
public:
virtual ~alloc(){}
listnode<T>* mallocmemory(listnode<T>* obj,int & capacity,bool bClean = false);//第一个参数是传入的链表对象，第二个参数代表向前还是向后增加节点，第三个参数是否已经设置末端
};
template<typename T>
inline listnode<T>* alloc<T>::mallocmemory(listnode<T>* obj,int & capacity,bool bClean)
{
listnode<T> *_new_ = new listnode<T>;
_new_->next = NULL;
_new_->prior = NULL;
if (0 == capacity)//按照顺序向后增加节点
{
if (!bClean)
{
while(1 != obj->nend)
{
obj = obj->next;
}
obj->nend = 0;
}
obj->next = _new_;//alignment container
obj->next->prior = obj;
_new_->nend = 1;//末端结束标志
}
else//在第一位增加节点
{
obj->prior = _new_;
_new_->next = obj;
}
return _new_;
}
template<typename T>
class
List_Iterator//简单的迭代器
{
public:
typedef List_Iterator<T> list_Iter;
typedef listnode<T>* node;
typedef long int difference_type;
typedef T* pointer;
typedef T& reference;
explicit List_Iterator():noperjia(1)
{
}
pointer operator->()const
{
return &(m_Iternode->data);
}
reference operator*()const
{
return m_Iternode->data;
}
bool operator !=(list_Iter & obj)
{
return (noperjia != obj.noperjia);
}
int operator ++()
{
++noperjia;
m_Iternode = m_Iternode->next;
return 0;
}
int operator –()
{
–noperjia;
m_Iternode = m_Iternode->prior;
return 0;
}
node m_Iternode;
int noperjia;
};
template<typename T>
class test
{
public:
virtual ~test()
{
Clean();
}
typedef listnode<T>* node;
typedef alloc<T> malloc;
typedef List_Iterator<T> iterator;
explicit test():nbefore(0),noperjia(1),bClean(true)
{
initnode();
}
int initnode();
listnode<T>* allocmemory(int insert = 0,bool bClean = false);//insert 0为向后 ，1为向前， bClean true第一次使用不计算位置 。链表多分配一节做末端
bool push_back(const T & obj);//从当前向后插入
bool push_front(const T & obj);//在第一位向前插入
bool eArse(iterator & obj);//容器删除，迭代器也跟着删除
iterator Begin();
iterator End();
bool Insert(iterator & obj,const T & _obj);//迭代也随着增加而增加
bool Clean();
protected:
node lastnode;
node beforenode;
node nextnode;
node endnode;
malloc alloc_type;
int nbefore;
int noperjia;
iterator iter;
private:
bool bClean;//判断是否清除过数据
};
template<typename T>
inline int test<T>::initnode()
{
listnode<T>* init = new listnode<T>;
init->prior = NULL;
init->next = NULL;
lastnode = init;
beforenode = init;
endnode = init;
return 0;
}
template<typename T>
inline listnode<T>* test<T>::allocmemory(int insert,bool bClean)
{
if (!insert)
{
endnode = alloc_type.mallocmemory(beforenode,insert,bClean);
endnode->next = lastnode;
lastnode->prior = endnode;
this->bClean = false;
return endnode;
}
lastnode = alloc_type.mallocmemory(lastnode,insert);
lastnode->prior = endnode;
endnode->next = lastnode;
return lastnode;
}
template<typename T>
inline bool test<T>::push_back(const T & obj)
{
if (bClean)
{
initnode();
allocmemory(0,bClean);
bClean = false;
}
else
allocmemory(0);
if(1 >= ++nbefore)
{
beforenode->data = obj;
beforenode->nrecord = 1;
lastnode = beforenode;
nextnode = beforenode->next;
return true;
}
while(0 != beforenode->nrecord)
{
beforenode = beforenode->next;
}
beforenode->data = obj;
beforenode->nrecord = 1;
nextnode = beforenode->next;
return true;
}
template<typename T>
inline bool test<T>::push_front(const T & obj)
{
if (bClean)
{
initnode();
}
allocmemory(1);
if(1 >= ++nbefore)
{
lastnode->data = obj;
lastnode->nrecord = 1;
beforenode = lastnode;
nextnode = lastnode->next;
return true;
}
while(1 != lastnode->prior->nend)
{
lastnode = lastnode->prior;
}
lastnode->data = obj;
lastnode->nrecord = 1;
return true;
}
template<typename T>
inline List_Iterator<T> test<T>::Begin()
{
iter.m_Iternode = lastnode;
return iter;
}
template<typename T>
inline List_Iterator<T> test<T>::End()
{
iter.noperjia = (nbefore + 1);//用来判断是不是最后一节
iter.m_Iternode = beforenode;
return iter;
}
template<typename T>
inline bool test<T>::Insert(iterator & obj,const T & _obj)//添加或者删除一节，都要为之前和之后的链表建立上下链接
{
if (bClean)
{
initnode();
bClean = false;
}
if (1 == obj.noperjia)//首节点 嵌入的数据为自己new空间，不用判断空间
{
node savenode = new listnode<T>;
savenode->data = _obj;
savenode->next = lastnode;
savenode->prior = endnode;
savenode->nrecord = 1;
endnode->next = savenode;
lastnode = savenode;
obj.m_Iternode = lastnode;
return true;
}
node Addnode;
Addnode = new listnode<T>;
Addnode->data = _obj;
obj.m_Iternode->prior->next = Addnode;
Addnode->prior = obj.m_Iternode->prior;
obj.m_Iternode->prior = Addnode;
Addnode->next = obj.m_Iternode;
Addnode->next->next = obj.m_Iternode->next;
obj.m_Iternode = obj.m_Iternode->prior;
lastnode = obj.m_Iternode;
while (!lastnode->prior->nend)//返回到第一位
lastnode = lastnode->prior;
return true;
}
template<typename T>
inline bool test<T>::eArse(iterator & obj)
{
if (bClean)
{
return false;
}
node getnode,savenode,deletenode;
if (1 == obj.noperjia)
{
if (!obj.m_Iternode->nrecord)
return false;
getnode = obj.m_Iternode->next;
deletenode = obj.m_Iternode;
delete deletenode;
obj.m_Iternode = getnode;
obj.m_Iternode->prior = endnode;
obj.m_Iternode->prior->next = obj.m_Iternode;
lastnode = obj.m_Iternode;
if (obj.m_Iternode->nend || obj.m_Iternode->next->nend)
{
endnode->next = obj.m_Iternode;
obj.m_Iternode->next = endnode;
return true;
}
return true;
}
getnode = obj.m_Iternode->prior;
deletenode = obj.m_Iternode;
savenode = obj.m_Iternode->next;
delete deletenode;
obj.m_Iternode = savenode;
obj.m_Iternode->prior = getnode;
obj.m_Iternode->prior->next = obj.m_Iternode;
lastnode = obj.m_Iternode;
while(!lastnode->prior->nend)
lastnode = lastnode->prior;
return true;
}
template<typename T>
bool test<T>::Clean()//把链表都删除释放掉，所有节点置为空
{
node deletenode;
while(!lastnode->prior->nend)//向前检查删除
{
deletenode = lastnode->prior;
delete lastnode;
lastnode = deletenode;
}
while(!lastnode->nend)//1为末端标志 向后删除
{
deletenode = lastnode->next;
delete lastnode;
lastnode = deletenode;
}
delete lastnode;
lastnode = NULL;
beforenode = NULL;
nextnode = NULL;
endnode = NULL;
iter.m_Iternode = NULL;
nbefore = 0;
noperjia = 0;
bClean = true;
return true;
}
template<typename T>
class testlist : public test<T>//只是变个名称，没有实质用处
{
public:
~testlist(){}
testlist(){}
};
/*使用实例
testlist<int>test;//或者test<int>test;
for(int i = 0;i < 100;i++)
{
test.push_back(1);
test.push_front(1);
}
for(testlist<int>::iterator it = test.Begin();it != End();it++)
{
*it;//调用引用运算符，显示传入的类数据 比如it的值为1 。如果传入的是够类型是个结构体 可以输出成员数据 ，也可以使用指针运算符 it->data;
test.Insert(1);//根据当前迭代到的链接位置插入数据，比如现在是第7位链表，插入第7位链表，原来的第7位变成第8位
test.eArse(1);//删除当前的链接节点，比如删除第7位，原来的第8位变为第7位。 Insert与eArse 整个迭代循环中就可以一直使用，
避免了STL中使用earse不调用break出现崩溃的问题。
}//迭代器独立出来的好处：可以避免因为迭代器的释放而导致链表地址的丢失问题。
test.Clear();//使用完成testlist调用，释放链接内存。 也可以不用调用此方法，testlist对象销毁时会自动调用析构函数，析构函数内部放入了此方法。
*/
.迭代器
按照我个人的实现思路，迭代器作用是用来查询链表数据位置，并且更新链表数据。在例子中，通过迭代器添加或者删除链表节点，并且刷新list的链表对象，有效的防止迭代过程中删除节点导致的崩溃问题。
2.内存分配
双向链表的构建在内存分配时就已经做好了工作，并且多出一节末端用来判断数据，有效的预防了比如CString容器类不好判断的问题。
3.链表方法类
通过此类建立内存分配、迭代器、与链表类的关联，简单而且灵活。
源文件地址http://download.csdn.net/detail/a29562268/9714680
首次写博客，有许多理解不到的地方，请帮忙指出，谢谢~！