文章目录
一.双向循环链表的结构
1.1 双向循环链表的定义
双向循环链表每一个结点有两个指针域,一个指向前驱结点,另一个指向后继结点,并且头结点的前驱指针指向尾结点,尾结点的next指针指向头结点,实际使用时会使用带头双向链表
1.2 双向循环链表的实现思路
- 通过模板类定义DualCircleList,并且继承双向链表DualLinkList类
- 在DualCircleList使用Linux内核链表实现,Linux内核链表在上一篇文章获取
- 使用struct list_head定义进行DualCircleList的头结点定义
- 在循环遍历的时候忽略头结点
1.3 双向循环链表实现要点
- 通过list_head定位目标结点
- 通过list_entry将list_head目标结点指针转换为目标结点
- 通过list_for_each来实现int find(const T&e)
- 遍历函数中的next和pre要跳过头结点
二.双向循环链表的接口实现
2.1 双向循环链表的结构
struct Node
{
list_head head;
T value;
};
list_head m_header;//定义头结点
list_head* m_current;//定义头指针
2.2 双向循环链表的初始化
在构造函数中实现
DualCircleList()
{
this->m_length = 0;
this->m_step = 1;
m_current = NULL;
INIT_LIST_HEAD(&m_header);
}
2.3 双向循环链表结点定位
和单链表遍历结点位置方法是一样的,找到插入结点的前一个结点,需要注意在const修饰的成员函数不应该修改对象的任何成员变量,这个时候要想获取到头结点需要进行类型转换,即const属性的成员函数调用非const属性的成员函数时,使用const_cast<>运算符去掉const属性
//1.实现定位函数
list_head* postion(int i)const
{
//在const修饰的成员函数中不可以直接使用成员变量的地址,需要进行类型转换
list_head* ret = const_cast<list_head*>(&m_header);
for (int p = 0; p < i; p++)
{
ret = ret->next;
}
return ret;
}
2.4 根据指定位置插入结点
- 先找到插入的位置
- 注意先不要断开原来的链表,新结点要与前驱结点和后继结点分别建立两次关系
bool insert(int i, const T& e)
{
bool ret = true;
Node* node = new Node();
i = i % (this->m_length + 1);//确定i的值
if (node != NULL)
{
node->value = e;
list_add_tail(&node->head, postion(i)->next);
this->m_length++;
}
else
{
cout << "new Node failed\n<<endl;
}
return ret;
}
//4.尾部插入
bool insert(const T& e)
{
return insert(this->m_length, e);
}
2.5 删除指定位置的结点
伪代码实现:
static void __list_del(struct list_head* prev, struct list_head* next)
{
next->prev = prev;
prev->next = next;
}
static void list_del(struct list_head* entry)
{
__list_del(toDel->prev, toDel->next);
toDel->next = NULL;
toDel->prev = NULL;
}
cpp中实现为:
先判断删除的位置是否合法,找到被删除结点,判断当前删除的结点是否为游标指向的位置,如果是的话将游标移动到下一个位置,并调用Linux内核链表的删除函数,同时将长度减1,释放删除结点的内存
bool remove(int i)
{
bool ret = true;
i = mod(i);//判断删除的位置是否合法
ret = ((i >= 0) && (i < this->m_length));
if (ret)
{
//找到被删除的结点
list_head* toDel = postion(i)->next;
//判断当前删除的结点是否为游标指向的位置
//如果是的话将游标移动一个位置
if (m_current == toDel)
{
m_current = toDel->next;
}
list_del(toDel);
this->m_length--;
delete list_entry(toDel, Node, head);
}
return ret;
}
2.6 修改某个结点的值
- 先判断设置的位置是否合法
- 进行指针转换
bool set(int i, const T& e)
{
bool ret = true;
i = mod(i);
if (ret)
{
list_entry(postion(i)->next, Node, head)->value = e;
}
return ret;
}
2.7 获取某一个结点的值
T get(int i) const
{
bool ret;
i = mod(i);
ret = ((i >= 0) && (i < this->m_length));
if (ret)
{
return list_entry(postion(i)->next, Node, head)->value;
}
return ret;
}
2.8 通过结点值找到下标
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(postion(i)->next, Node, head)->value == e)
{
ret = i;
break;
}
i++;
}
return ret;
}
2.9 获取双向链表的长度
int length()const
{
return this->m_length;
}
2.10 清空链表
void clear()
{
while (this->m_length > 0)
{
remove(0);
}
}
2.11 析构函数实现
~DualCircleList()
{
clear();
}
三.完整代码
代码可以不继承双向链表,但是需要加一些变量
#ifndef DUALCIRCLELIST_H
#define DUALCIRCLELIST_H
#include "DualLinkList.h"
#include "LinuxList.h"
template<class T>
class DualCircleList : public DualLinkList<T>
{
protected:
struct Node
{
list_head head;
T value;
};
list_head m_header;//定义头结点
list_head* m_current;//定义头指针
//1.实现定位函数
list_head* postion(int i)const
{
//在const修饰的成员函数中不可以直接使用成员变量的地址,需要进行类型转换
list_head* ret = const_cast<list_head*>(&m_header);
for (int p = 0; p < i; p++)
{
ret = ret->next;
}
return ret;
}
//2.
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);
}
//3.
bool insert(int i, const T& e)
{
bool ret = true;
Node* node = new Node();
i = i % (this->m_length + 1);//确定i的值
if (node != NULL)
{
node->value = e;
list_add_tail(&node->head, postion(i)->next);
this->m_length++;
}
else
{
cout << "new Node failed"<<endl;
}
return ret;
}
//4.尾部插入
bool insert(const T& e)
{
return insert(this->m_length, e);
}
//5.删除结点
bool remove(int i)
{
bool ret = true;
i = mod(i);//判断删除的位置是否合法
ret = ((i >= 0) && (i < this->m_length));
if (ret)
{
//找到被删除的结点
list_head* toDel = postion(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 = ((i >= 0) && (i < this->m_length));
if (ret)
{
list_entry(postion(i)->next, Node, head)->value = e;
}
return ret;
}
T get(int i) const
{
bool ret;
i = mod(i);
ret = ((i >= 0) && (i < this->m_length));
if (ret)
{
return list_entry(postion(i)->next, Node, head)->value;
}
return ret;
}
virtual 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(postion(i)->next, 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 && ((i >= 0) && (i < this->m_length));
if (ret)
{
m_current = postion(i)->next;
this->m_step = step;
}
return ret;
}
bool end()
{
return ((m_current == NULL) || (this->m_length == 0));
}
virtual T current()
{
if (!end())
{
return list_entry(m_current, Node, head)->value;
}
else
{
cout << "list is empty" << endl;
return NULL;
}
}
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->prev;
//计数
i++;
}
else
{
//直接跳过头结点
m_current = m_current->prev;
}
}
//如果等于头结点
if (m_current == &m_header)
{
m_current = m_current->prev;
}
return (i == this->m_step);
}
~DualCircleList()
{
clear();
}
};
#endif
四.测试代码
插入10个元素,并删除元素值为5的元素
#include "DualCircleList.h"
#include <iostream>
int main()
{
DualCircleList<int> dl;
int j = 5;
for (int i = 0; i < 5; i++)
{
dl.insert(0, i);
dl.insert(0, j);
}
for (int i = 0; i < dl.length(); i++)
{
cout << dl.get(i) << endl;
}
//定位到最后一个元素
dl.move(dl.length() - 1);
cout << " delete begin()" << endl;
//查找5这个元素是否在链表里面,如果在,则删除
while (dl.find(5)!= -1)
{
if (dl.current() == 5)
{
cout << dl.current() << endl;
dl.remove(dl.find(dl.current()));
}
else
{
dl.pre(); //定位到前驱结点
}
}
cout << "delete end()" << endl;
cout << "for_each begin" << endl;
for (int i = 0; i < dl.length(); i++)
{
cout << dl.get(i) << endl;
}
return 0;
}
结果:
5
4
5
3
5
2
5
1
5
0
delete begin()
5
5
5
5
5
delete end()
for_each begin
4
3
2
1
0