二十七、再论智能指针（上）
1、思考
- 使用智能指针( SmartPointer )替换单链表( LinkList )中的原生指针是否可行？
2、问题出在哪里？
- SmartPointer的设计方案
- 指针生命周期结束时主动释放堆空间
- 一片堆空间最多只能由一个指针标识
- 杜绝指针运算和指针比较
3、新的设计方案
是时候创建新的智能指针了！
4、新的设计方案
- Pointer是智能指针的抽象父类（模板）
- 纯虚析构函数virtual ~Pointer() = 0;
- 重载operator -> ()
- 重载operator * ()
5、编程实验：智能指针的新方案
Pointer.h
SmartPointer.h
6、To be continued
二十八、再论智能指针（下）
1、完成SharedPointer类的具体实现
?
2、SharedPointer设计要点
- 类模板
- 通过计数机制( ref )标识堆内存
- 堆内存被指向时：ref++
- 指针被置空时：ref--
- ref == 0 时：释放堆内存
- 通过计数机制( ref )标识堆内存
3、计数机制原理剖析
4、SharedPointer类的声明
5、智能指针的比较
由于SharedPointer支持多个对象同时指向一片堆空间；因此，必须支持比较操作！
6、编程实验：智能指针的新成员
SharedPointer.h
#ifndef SHAREDPOINTER_H_
#define SHAREDPOINTER_H_
/*******************************************************************************
* Include _Files *
*******************************************************************************/
#include <cstdlib>
#include "Pointer.h"
#include "Exception.h"
/*******************************************************************************
* Type Definition *
*******************************************************************************/
namespace DTLib
{
template < typename T >
class SharedPointer : public Pointer<T>
{
protected:
int* m_ref; // 计数机制成员指针
// 获取当前的智能指针地址、计数变量地址、计数变量 +1
void assign(const SharedPointer<T>& obj)
{
this->m_ref = obj.m_ref; // 获取共用的计数变量地址
this->m_pointer = obj.m_pointer; // 获取共用的堆空间地址
if( this->m_ref )
{
(*this->m_ref)++; // 计数变量 +1
}
}
public:
// 构造函数
SharedPointer(T* p = NULL) : m_ref(NULL)
{
if( p )
{
this->m_ref = static_cast<int*>(std::malloc(sizeof(int))); // 申请计数变量堆空间
if( this->m_ref )
{
*(this->m_ref) = 1; // 计数变量 +1
this->m_pointer = p; // 获取p对应的堆空间
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create SharedPointer object ...");
}
}
}
SharedPointer(const SharedPointer<T>& obj) : Pointer<T>(NULL)
{
assign(obj); // 获取当前的智能指针地址、计数变量地址、计数变量 +1
}
SharedPointer<T>& operator= (const SharedPointer<T>& obj)
{
if( this != &obj )
{
clear(); // 让当前的智能指针置空，计数变量 -1
assign(obj); // 获取当前的智能指针地址、计数变量地址、计数变量 +1
}
return *this;
}
// 让当前的智能指针置空，计数变量 -1
void clear()
{
T* toDel = this->m_pointer;
int* ref = this->m_ref;
this->m_pointer = NULL; // 智能指针指向的堆空间地址 置 NULL
this->m_ref = NULL; // 智能指针指向的计数变量地址 置 NULL
if( ref )
{
(*ref)--; // 计数变量 -1
if( *ref == 0 ) // 计数变量为 0
{
free(ref); // 释放共用的计数变量的堆空间
delete toDel; // 释放共用的堆空间
}
}
}
~SharedPointer()
{
clear(); // 让当前的智能指针置空，计数变量 -1
}
};
// 支持比较操作 智能指针地址 <==> 智能指针地址 <==> 类对象地址
template < typename T >
static bool operator == (const T* l, const SharedPointer<T>& r)
{
return (l == r.get());
}
template < typename T >
static bool operator != (const T* l, const SharedPointer<T>& r)
{
return (l != r.get());
}
template < typename T >
static bool operator == (const SharedPointer<T>& l, const T* r)
{
return (l.get() == r);
}
template < typename T >
static bool operator != (const SharedPointer<T>& l, const T* r)
{
return (l.get() != r);
}
template < typename T >
static bool operator == (const SharedPointer<T>& l, const SharedPointer<T>& r)
{
return (l.get() == r.get());
}
template < typename T >
static bool operator != (const SharedPointer<T>& l, const SharedPointer<T>& r)
{
return !(l == r);
}
}
#endif // SHAREDPOINTER_H_
7、智能指针的使用军规
- 只能用来指向堆空间中的单个变量（对象）
- 不同类型的智能指针对象不能混合使用
- 不要使用delete释放智能指针指向的堆空间
8、小结
- SharedPointer最大程度的模拟了原生指针的行为
- 计数机制确保多个智能指针合法的指向同一片堆空间
- 智能指针只能用于指向堆空间中的内存
- 不同类型的智能指针不要混合使用
- 堆对象的生命周期由智能指针进行管理
二十九、循环链表的实现
1、什么是循环链表？
- 概念上
- 任意数据元素都有一个前驱和一个后继
- 所有的数据元素的关系构成一个逻辑上的环
- 实现上
- 循环链表是一种特殊的单链表
- 尾结点的指针域保存了首结点的地址
2、循环链表的逻辑构成
3、循环链表的继承层次结构
4、循环链表的实现思路
- 通过模板定义CircleList类，继承自LinkList类
- 定义内部函数last_to_first()，用于将单链表首尾相连
- 特殊处理：首元素的插入操作和删除操作
- 重新实现：清空操作和遍历操作
5、循环链表的实现要点
- 插入位置为0时：
- 头结点和尾结点均指向新结点
- 新结点成为首结点插入链表
- 删除位置为0时：
- 头结点和尾结点指向位置为1的结点
- 安全销毁首结点
6、编程实验：循环链表的实现
CircleList.h
#ifndef CIRCLELIST_H_
#define CIRCLELIST_H_
/*******************************************************************************
* Include _Files *
*******************************************************************************/
#include "LinkList.h"
/*******************************************************************************
* Type Definition *
*******************************************************************************/
namespace DTLib
{
template < typename T >
class CircleList : public LinkList<T>
{
protected:
typedef typename LinkList<T>::Node Node; // 使用typename的原因：编译器无法辨识标识符究竟是什么（是一个类型还是一个成员名称(静态数据成员或者静态函数)）
int mod(int i) const // 取余
{
return (this->m_length == 0) ? 0 : (i % this->m_length);
}
Node* last() const // 尾结点的指针
{
return this->position(this->m_length-1)->next;
}
void last_to_first() const // 将链表首尾相连
{
last()->next = this->m_header.next; // 尾结点指向首结点
}
public:
/**********************************************************************
* Function: insert()
* Description: 插入新结点(函数重载)
* Input: i 在位置i插入新结点(默认插在最后)
* e 带插入结点的数据(value)
* Output:
* Return: bool 判断插入结点位置是否合法
* Others: 异常 申请内存是否成功
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool insert(const T& e)
{
return insert(this->m_length, e);
}
bool insert(int i, const T& e)
{
bool ret = true;
i = i % (this->m_length + 1); // 取余
ret = LinkList<T>::insert(i, e); // 调用父类的插入函数
if( ret && (i == 0) ) // 处理特殊情况(首结点)
{
last_to_first(); // 将链表首尾相连
}
return ret;
}
/**********************************************************************
* Function: remove()
* Description: 删除结点
* Input: i 在位置i删除结点
* Output:
* Return: bool 判断删除结点位置是否合法
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool remove(int i)
{
bool ret = true;
i = mod(i); // 取余
if( i == 0 ) // 处理特殊情况(首结点)
{
Node* toDel = this->m_header.next; // 获取首结点地址
if( toDel != NULL )
{
this->m_header.next = toDel->next; // 头结点指向 1 结点
this->m_length--; // 当前线性表长度 -1
if( this->m_length > 0 ) // 当前结点不是最后一个结点
{
last_to_first(); // 将链表首尾相连
if( this->m_current == toDel ) // 判断游标是否指向 待删除结点的地址
{
this->m_current = toDel->next; // 指向 待删除结点的下一个结点的地址
}
}
else
{
this->m_header.next = NULL; // 头结点置 NULL
this->m_current = NULL; // 当前结点置 NULL
}
this->destroy(toDel); // 为了异常安全，最后销毁结点
}
else
{
ret = false;
}
}
else
{
ret = LinkList<T>::remove(i); // 若不是特殊情况，调用父类函数实现
}
return ret;
}
/**********************************************************************
* Function: set()
* Description: 修改第i个结点的值
* Input: i 待修改结点的位置
* Output:
* Return: bool 判断修改结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool set(int i, const T& e)
{
return LinkList<T>::set(mod(i), e);
}
/**********************************************************************
* Function: get()
* Description: 获取第i个结点的值(函数重载)
* Input: i 待获取结点的位置
* Output:
* Return: bool 判断获取结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
T get(int i) const
{
return LinkList<T>::get(mod(i));
}
bool get(int i, T& e) const
{
return LinkList<T>::get(mod(i), e);
}
/**********************************************************************
* Function: find()
* Description: 查找指定元素的位置
* Input: e 待查找结点的值(value)
* Output:
* Return: int 返回结点的位置
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
int find(const T& e) const
{
int ret = -1;
Node* slider = this->m_header.next; // 获取 0 元素的地址
for(int i=0; i<this->m_length; i++)
{
if( slider->value == e ) // 判断值是否相等
{
ret = i; // 获取位置
break;
}
slider = slider->next; // 移动到下一个结点
}
return ret;
}
/**********************************************************************
* Function: clear()
* Description: 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
void clear()
{
while( this->m_length > 1 )
{
remove(1); // 为了效率 remove(0)
}
if( this->m_length == 1 ) // 处理特殊情况(只剩首结点)
{
Node* toDel = this->m_header.next;
this->m_header.next = NULL;
this->m_length = 0;
this->m_current = NULL;
this->destroy(toDel);
}
}
/**********************************************************************
* Function: move()
* Description: 将游标定位到目标位置(i)
* Input: i 移动到第i个元素
* step 步进默认为 1
* Output:
* Return: bool 判断i位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool move(int i, int step) // 遍历所有元素
{
return LinkList<T>::move(mod(i), step);
}
/**********************************************************************
* Function: end()
* Description: 游标是否到达尾部
* Input:
* Output:
* Return: bool 游标是否到达尾部
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool end()
{
return (this->m_length == 0) || (this->m_current == NULL);
}
/**********************************************************************
* Function: ~LinkList()
* Description: 析构函数 - 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
~CircleList()
{
clear();
}
};
}
#endif // CIRCLELIST_H_
7、循环链表的应用
- 约瑟夫环问题
????????
8、编程实验：约瑟夫问题
main.cpp
#include <iostream>
#include "./DTLib/CircleList.h"
using namespace std;
using namespace DTLib;
void josephus(int n, int s, int m)
{
CircleList<int> cl;
for(int i=1; i<=n; i++)
{
cl.insert(i);
}
cl.move(s-1,m-1); //游标指向0处，步长2
int i=0;
while( cl.length() > 0 )
{
cl.next();
cout << cl.current() <<endl; //当前要自杀的
int index=cl.find(cl.current());
cl.remove(index);
}
}
int main()
{
josephus(41,1,3); //41个人，从1号开始数，数到第三个人开始自杀
return 0;
}
9、小结
- 循环链表是一种特殊的单链表
- 尾结点的指针域保存了首结点的地址
- 特殊处理首元素的插入操作和删除操作
- 重新实现清空操作和遍历操作
?
三十、双向链表的实现
1、交流中
????????
2、单链表的另一个缺陷
- 单向性
- 只能从头结点开始高效访问链表中的数据元素
- 缺陷
- 如果需要逆向访问单链表中的数据元素将极其低效
????????
3、新的线性表
- 设计思路：
在“单链表”的结点中增加一个指针 pre ,用于指向当前结点的前驱结点。
????????
4、双向链表的继承层次结构
5、DualLinkList的定义
6、编程实验：双向链表的实现
DualLinkList.h
#ifndef DUALLINKLIST_H_
#define DUALLINKLIST_H_
/*******************************************************************************
* Include Files *
*******************************************************************************/
#include "List.h"
#include "Exception.h"
/*******************************************************************************
* Type Definition *
*******************************************************************************/
namespace DTLib
{
template < typename T >
class DualLinkList : public List<T>
{
protected:
struct Node : public Object
{
T value; // 数据域
Node* next; // 后继指针
Node* pre; // 前驱指针
};
mutable struct : public Object // mutable 突破const的限制而设置,永远处于可变的状态,即使在一个const函数中
{
char reserved[sizeof(T)]; // 为了与Node内存对齐，以便后续使用强制类型转换，继承于Object同理。
Node* next; // 指向首结点
Node* pre; // 内存对齐
} m_header; // 创建头结点 不直接用 Node m_header，因为T有可能是类，在类运行构造函数时，可能会抛出异常
int m_length; // 当前线性表的长度
int m_step; // 步进次数 遍历元素的时候使用 move(); end(); next(); current()
Node* m_current; // 游标 遍历元素的时候使用 move(); end(); next(); current()
/**********************************************************************
* Function: position()
* Description: 移动i次，返回第i-1个结点的地址
* Input: i 数组类地址
* m_header 头结点地址
* Output:
* Return: Node 返回第i-1个结点的地址
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
Node* position(int i) const
{
Node* ret = reinterpret_cast<Node*>(&m_header); // 头结点地址 - 强制类型转换
for(int p=0; p<i; p++) // 移动i次
{
ret = ret->next;
}
return ret;
}
/**********************************************************************
* Function: create()
* Description: 创建新结点(堆空间)
* Input:
* Output:
* Return: Node 返回新结点的地址
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual Node* create()
{
return new Node();
}
/**********************************************************************
* Function: destroy()
* Description: 销毁结点(堆空间)
* Input: pn 待销毁的结点
* Output:
* Return:
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual void destroy(Node* pn)
{
delete pn;
}
public:
/**********************************************************************
* Function: DualLinkList()
* Description: 构造函数 - 初始化参数
* Input:
* Output:
* Return:
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
DualLinkList()
{
m_header.next = NULL;
m_header.pre = NULL;
m_length = 0;
m_step = 1;
m_current = NULL;
}
/**********************************************************************
* Function: insert()
* Description: 插入新结点(函数重载)
* Input: i 在位置i插入新结点(默认插在最后)
* e 带插入结点的数据(value)
* Output:
* Return: bool 判断插入结点位置是否合法
* Others: 异常 申请内存是否成功
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool insert(const T& e)
{
return insert(m_length, e); // 新结点插在最后
}
bool insert(int i, const T& e)
{
bool ret = ((0 <= i) && (i <= m_length)); // 位置i合法性校验
if( ret )
{
Node* node = create(); // 创建新结点 - 申请内存
if( node != NULL )
{
Node* current = position(i); // 获取新结点前一个结点的地址
Node* next = current->next; // 获取新结点后一个结点的地址
node->value = e; // 新结点的数据域(value)赋值
node->next = next; // 新结点后继指针赋值
current->next = node; // 前一个结点后继指向新结点
if( current != reinterpret_cast<Node*>(&m_header) ) // 前一个结点不为头结点
{
node->pre = current; // 新结点前继指针赋值
}
else
{
node->pre = NULL; // 新结点前继指针置 0
}
if( next != NULL ) // 后一个结点存在
{
next->pre = node; // 后一个结点的前继指针赋值
}
m_length++; // 当前线性表的长度 +1
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
}
}
return ret;
}
/**********************************************************************
* Function: remove()
* Description: 删除结点
* Input: i 在位置i删除结点
* Output:
* Return: bool 判断删除结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool remove(int i)
{
bool ret = ((0 <= i) && (i < m_length)); // 位置i合法性校验
if( ret )
{
Node* current = position(i); // 获取待删除结点前一个结点的地址
Node* toDel = current->next; // 临时保存 待删除结点的地址
Node* next = toDel->next; // 获取待删除结点后一个结点的地址
if( m_current == toDel ) // 判断游标是否指向 待删除结点的地址
{
m_current = next; // 指向 待删除结点的下一个结点的地址
}
current->next = next; // 待删除结点的下一个结点的地址，赋值给待删除结点的前一个结点的next
if( next != NULL ) // 待删除结点后还有结点
{
next->pre = toDel->pre; // 待删除结点的前驱地址，赋值给下一个结点的前驱指针
}
m_length--; // 当前线性表的长度 -1 为了防止元素为类时，析构函数抛出异常，无法保证链表的安全性
destroy(toDel); // 释放该结点所占得内存
}
return ret;
}
/**********************************************************************
* Function: set()
* Description: 修改第i个结点的值
* Input: i 待修改结点的位置
* Output:
* Return: bool 判断修改结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
bool set(int i, const T& e)
{
bool ret = ((0 <= i) && (i < m_length)); // 位置i合法性校验
if( ret )
{
position(i)->next->value = e; // 待修改结点的前一个结点->next == 待修改的结点的地址
}
return ret;
}
/**********************************************************************
* Function: get()
* Description: 获取第i个结点的值(函数重载)
* Input: i 待获取结点的位置
* Output:
* Return: bool 判断获取结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual T get(int i) const
{
T ret;
if( get(i, ret) )
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
}
return ret;
}
bool get(int i, T& e) const
{
bool ret = ((0 <= i) && (i < m_length)); // 位置i合法性校验
if( ret )
{
e = position(i)->next->value; // 待获取结点的前一个结点->next == 待获取的结点的地址
}
return ret;
}
/**********************************************************************
* Function: find()
* Description: 查找指定元素的位置
* Input: e 待查找结点的值(value)
* Output:
* Return: int 返回结点的位置
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
int find(const T& e) const
{
int ret = -1;
int i = 0;
Node* node = m_header.next; // 获取 0 元素的地址
while( node )
{
if( node->value == e ) // 判断值是否相等
{
ret = i; // 获取位置
break;
}
else
{
node = node->next; // 移动到下一个结点
i++; // 位置 +1
}
}
return ret;
}
/**********************************************************************
* Function: length()
* Description: 当前线性表的长度
* Input:
* Output:
* Return: int 当前线性表的长度
* Others: O(1)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
int length() const
{
return m_length;
}
/**********************************************************************
* Function: clear()
* Description: 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
void clear()
{
while( m_length > 0 ) // 循环删除首结点
{
remove(0);
}
}
/*
遍历所有元素 推荐使用方法
移动到0号元素 判断是否到尾部 移动到下一个结点
for (list.move(0); !list.end();list.next())
{
cout << list.current() << endl;
}
移动到尾元素 判断是否到首部 移动到上一个结点
for (list.move(list.length()-1); !list.end();list.pre())
{
cout << list.current() << endl;
}
*/
/**********************************************************************
* Function: move()
* Description: 将游标定位到目标位置(i)
* Input: i 移动到第i个元素
* step 步进默认为 1
* Output:
* Return: bool 判断i位置是否合法
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual bool move(int i, int step = 1)
{
bool ret = (0 <= i) && (i < m_length) && (step > 0);
if( ret )
{
m_current = position(i)->next; // 目标位置的地址
m_step = step;
}
return ret;
}
/**********************************************************************
* Function: end()
* Description: 游标是否到达尾部
* Input:
* Output:
* Return: bool 游标是否到达尾部
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual bool end()
{
return (m_current == NULL);
}
/**********************************************************************
* Function: current()
* Description: 获取游标所指向的数据元素
* Input:
* Output:
* Return: T 游标所指向的数据元素
* Others: 异常 游标已到尾部，无法获取到值
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual T current()
{
if( !end() ) // 游标是否到达尾部
{
return m_current->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
}
}
/**********************************************************************
* Function: next()
* Description: 向后移动游标 m_step次
* Input:
* Output:
* Return: bool 是否成功移动游标 m_step次
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual bool next()
{
int i = 0;
while( (i < m_step) && !end() ) // 移动次数是否为m_step && 游标是否到达尾部
{
m_current = m_current->next; // 移动一次游标
i++;
}
return (i == m_step);
}
/**********************************************************************
* Function: pre()
* Description: 向前移动游标 m_step次
* Input:
* Output:
* Return: bool 是否成功移动游标 m_step次
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
virtual bool pre()
{
int i = 0;
while( (i < m_step) && !end() ) // 移动次数是否为m_step && 游标是否到达尾部
{
m_current = m_current->pre; // 移动一次游标
i++;
}
return (i == m_step);
}
/**********************************************************************
* Function: ~DualLinkList()
* Description: 析构函数 - 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
~DualLinkList()
{
clear();
}
};
}
#endif // DUALLINKLIST_H_
7、小结
- 双向链表是为了弥补单链表的缺陷而重新设计的
- 在概念上，双向链表不是单链表，没有继承关系
- 双向链表中的游标能够直接访问当前结点的前驱和后继
- 双向链表是线性表概念的最终实现(更贴近理论上的线性表)
8、深度思考
- 有些设计，会让两者的呈现继承关系。没有对与错。考虑的不同。
- 代码后期的维护性和软件产品的维护性。
三十一、老生常谈的两个宏（Linux）
1、Linux内核中常用的两个宏定义
2、见招拆招 - 第一式：编译器做了什么？
- offsetof用于计算TYPE结构体中MEMBER成员的偏移位置。
- 编译器清楚的知道结构体成员变量的偏移位置
- 通过结构体变量首地址与偏移量定位成员变量
3、编程实验：offsetof 原理剖析
#include <stdio.h>
#ifndef offsetof
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
#endif
struct ST
{
int i; // 0
int j; // 4
char c; // 8
};
void func(struct ST* pst)
{
int* pi = &(pst->i); // 0
int* pj = &(pst->j); // 4
char* pc = &(pst->c); // 8
printf("pst = %p\n", pst);
printf("pi = %p\n", pi);
printf("pj = %p\n", pj);
printf("pc = %p\n", pc);
}
int main()
{
struct ST s = {0};
func(&s);
func(NULL);
printf("offset i: %ld\n", offsetof(struct ST, i));
printf("offset j: %ld\n", offsetof(struct ST, j));
printf("offset c: %ld\n", offsetof(struct ST, c));
return 0;
}
4、见招拆招 - 第二式：({})是何方神圣？
- ({}) 是GNU C编译器的语法扩展
- ({}) 与逗号表达式类似，结果为最后一个语句的值
5、见招拆招 - 第三式：typeof是一个关键字吗？
- typeof是GNU C编译器的特有关键字
- typeof只在编译期生效，用于得到变量的类型
????????
6、见招拆招 - 第四式：最后的原理
当已知pc和结构成员地址偏移量，求首地址。
7、编程实验：container_of 原理剖析
#include <stdio.h>
#ifndef offsetof
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
#endif
#ifndef container_of
#define container_of(ptr, type, member) ({ \
const typeof(((type*)0)->member)* __mptr = (ptr); \
(type*)((char*)__mptr - offsetof(type, member)); })
#endif
#ifndef container_of_new
#define container_of_new(ptr, type, member) ((type*)((char*)(ptr) - offsetof(type, member)))
#endif
struct ST
{
int i; // 0
int j; // 4
char c; // 8
};
void method_1()
{
int a = 0;
int b = 0;
int r = (
a = 1,
b = 2,
a + b
);
printf("r = %d\n", r);
}
void method_2()
{
int r = ( {
int a = 1;
int b = 2;
a + b;
} );
printf("r = %d\n", r);
}
void type_of()
{
int i = 100;
typeof(i) j = i;
const typeof(j)* p = &j;
printf("sizeof(j) = %d\n", sizeof(j));
printf("j = %d\n", j);
printf("*p = %d\n", *p);
}
int main()
{
// method_1();
// method_2();
// type_of();
struct ST s = {0};
char* pc = &s.c;
int e = 0;
int* pe = &e;
struct ST* pst = container_of(pc, struct ST, c);
printf("&s = %p\n", &s);
printf("pst = %p\n", pst);
return 0;
}
8、小结
- 编译器清楚的知道结构体成员变量的偏移位置
- ({ })与逗号表达式类似（但是可以定义新的局部变量），结果为最后一个语句的值
- typeof只在编译期生效，用于得到变量的类型
- container_of使用({})进行类型安全检查（逗号表达式中不可以定义变量）
?
三十二、Linux内核链表剖析
1、目标
- 移植Linux内核链表，使其适用于非GNU编译器
- 分析Linux内核中链表的基本实现
2、Linux内核链表的位置及依赖
- 位置
- {linux-2.6.39}\\include\linux\list.h
- 依赖
- #include <linux/types.h>
- #include <linux /stddef.h>
- #include <linux/poison.h>
- #include <linux/prefetch.h>
3、移植时的注意事项
- 清除文件间的依赖
- 剥离依赖文件中与链表实现相关的代码
- 清除平台相关代码（GNU C )
- ({})
- ?typeof
- _builtin_prefetch? (提高访问效率)? -? 直接删除
- static inline（支持同时使用）-? 删除inline
4、编程实验：Linux内核源码的移植
list.h
5、Linux内核链表的实现
- 带头节点的双向循环链表，且头节点为表中成员
- 头结点的next指针指向首结点
- 头节点的prev指针指向尾结点
6、Linux内核链表的结点定义
7、使用struct list_head自定义链表结点
8、编程实验：Linux内核链表初体验
main.c
9、Linux内核链表的插入操作
- 在链表头部插入：list_add (new, head)
- 在链表尾部插入：list_add_tail (new, head)
????????
10、Linux内核链表的删除操作
????????
11、Linux内核链表的遍历
- 正向遍历：list_for_each(pos, head)
- 逆向遍历：list_for_each_prev(pos, head)
12、编程实验：Linux内核链表的使用
main.c
#include <stdio.h>
#include "LinuxList.h"
void list_demo_1()
{
struct Node
{
struct list_head head;
int value;
};
struct Node l = {0};
struct list_head* list = (struct list_head*)&l;
struct list_head* slider = NULL;
int i = 0;
INIT_LIST_HEAD(list);
printf("Insert begin ...\n");
for(i=0; i<5; i++)
{
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->value = i;
list_add_tail((struct list_head*)n, list);
}
list_for_each(slider, list)
{
printf("%d\n", ((struct Node*)slider)->value);
}
printf("Insert end ...\n");
printf("Delete begin ...\n");
list_for_each(slider, list)
{
if( ((struct Node*)slider)->value == 3 )
{
list_del(slider);
free(slider);
break;
}
}
list_for_each(slider, list)
{
printf("%d\n", ((struct Node*)slider)->value);
}
printf("Delete end ...\n");
}
void list_demo_2()
{
struct Node
{
int value;
struct list_head head;
};
struct Node l = {0};
struct list_head* list = &l.head;
struct list_head* slider = NULL;
int i = 0;
INIT_LIST_HEAD(list);
printf("Insert begin ...\n");
for(i=0; i<5; i++)
{
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->value = i;
list_add(&n->head, list);
}
list_for_each(slider, list)
{
printf("%d\n", list_entry(slider, struct Node, head)->value);
}
printf("Insert end ...\n");
printf("Delete begin ...\n");
list_for_each(slider, list)
{
struct Node* n = list_entry(slider, struct Node, head);
if( n->value == 3 )
{
list_del(slider);
free(n);
break;
}
}
list_for_each(slider, list)
{
printf("%d\n", list_entry(slider, struct Node, head)->value);
}
printf("Delete end ...\n");
}
int main()
{
// list_demo_1();
// list_demo_2();
return 0;
}
13、小结
- Linux内核链表移植时需要剔除依赖以及平台相关代码
- Linux内核链表是带头节点的双向循环链表
- 使用Linux内核链表时需要自定义链表结点
- 将struct list_head 作为结点结构体的第一个成员或最后一个成员
- struct list_head 作为最后一个成员时，需要使用list_entry宏
- list_entry的定义中使用了container_of宏
?
三十三、双向循环链表的实现
1、目标
- 使用Linux内核链表实现 DTLib中的双向循环链表
- template < typename T > class DualCircleList;
2、DTLib中双向循环链表的设计思路
数据结点之间在逻辑上构成双向循环链表，头结点仅用于结点的定位。
3、实现思路
- 通过模板定义 DualCircleList类，继承自DualLinkList类
- 在DualCircleList内部使用Linux内核链表进行实现
- 使用struct list_head定义 DualCircleList的头结点
- 特殊处理：循环遍历时忽略头结点
4、实现要点
- 通过list_head进行目标结点定位( position(i) )
- 通过list_entry将list_head指针转换为目标结点指针
- 通过list_for_each 实现int find(const T&e)函数
- 遍历函数中的next()和pre()需要考虑跳过头结点
5、编程实验：基于Linux内核链表的双向循环链表
DualCircleList.h
#ifndef DUALCIRCLELIST_H
#define DUALCIRCLELIST_H
#include "LinuxList.h"
#include "DualLinkList.h"
namespace DTLib
{
template < typename T >
class DualCircleList : public DualLinkList<T>
{
protected:
struct Node : public Object // 结点类型
{
list_head head; // Linux内核链表结点的结构体成员
T value; // 数据域
};
list_head m_header; // 头结点
list_head* m_current; // 游标 - 用于遍历
/**********************************************************************
* Function: position()
* Description: 移动i次，返回第i-1个结点的地址
* Input: i 数组类地址
* m_header 头结点地址
* Output:
* Return: Node 返回第i-1个结点的地址
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
list_head* position(int i) const
{
list_head* ret = const_cast<list_head*>(&m_header); // 头结点地址 - 强制类型转换
for(int p=0; p<i; p++) // 移动i次游标
{
ret = ret->next;
}
return ret;
}
/**********************************************************************
* Function: mod()
* Description: 取余
* Input: i 数组类地址
* m_header 头结点地址
* Output:
* Return: Node 返回第i-1个结点的地址
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
int mod(int i) const
{
return (this->m_length == 0) ? 0 : (i % this->m_length);
}
public:
/**********************************************************************
* Function: DualCircleList()
* Description: 构造函数 - 初始化参数
* Input:
* Output:
* Return:
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/04/12 1.0 Create
**********************************************************************/
DualCircleList()
{
this->m_length = 0;
this->m_step = 1;
m_current = NULL;
INIT_LIST_HEAD(&m_header); // Linux链表头结点初始化
}
/**********************************************************************
* Function: insert()
* Description: 插入新结点(函数重载)
* Input: i 在位置i插入新结点(默认插在最后)
* e 带插入结点的数据(value)
* Output:
* Return: bool 判断插入结点位置是否合法
* Others: 异常 申请内存是否成功
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
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;
}
/**********************************************************************
* Function: remove()
* Description: 删除结点
* Input: i 在位置i删除结点
* Output:
* Return: bool 判断删除结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
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;
}
/**********************************************************************
* Function: set()
* Description: 修改第i个结点的值
* Input: i 待修改结点的位置
* Output:
* Return: bool 判断修改结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
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;
}
/**********************************************************************
* Function: get()
* Description: 获取第i个结点的值(函数重载)
* Input: i 待获取结点的位置
* Output:
* Return: bool 判断获取结点位置是否合法
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
T get(int i) const
{
T ret;
if( get(i, ret) )
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element ...");
}
return ret;
}
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;
}
/**********************************************************************
* Function: find()
* Description: 查找指定元素的位置
* Input: e 待查找结点的值(value)
* Output:
* Return: int 返回结点的位置
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
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;
}
/**********************************************************************
* Function: length()
* Description: 当前线性表的长度
* Input:
* Output:
* Return: int 当前线性表的长度
* Others: O(1)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
int length() const
{
return this->m_length;
}
/**********************************************************************
* Function: clear()
* Description: 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
void clear()
{
while( this->m_length > 0 )
{
remove(0);
}
}
/*
遍历所有元素 推荐使用方法
移动到0号元素 判断是否到尾部 移动到下一个结点
for (list.move(0); !list.end();list.next())
{
cout << list.current() << endl;
}
*/
/**********************************************************************
* Function: move()
* Description: 将游标定位到目标位置(i)
* Input: i 移动到第i个元素
* step 步进默认为 1
* Output:
* Return: bool 判断i位置是否合法
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
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;
}
/**********************************************************************
* Function: end()
* Description: 游标是否到达尾部
* Input:
* Output:
* Return: bool 游标是否到达尾部
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
bool end()
{
return (m_current == NULL) || (this->m_length == 0);
}
/**********************************************************************
* Function: current()
* Description: 获取游标所指向的数据元素
* Input:
* Output:
* Return: T 游标所指向的数据元素
* Others: 异常 游标已到尾部，无法获取到值
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
T current()
{
if( !end() )
{
return list_entry(m_current, Node, head)->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No value at current position ...");
}
}
/**********************************************************************
* Function: next()
* Description: 移动游标 m_step次
* Input:
* Output:
* Return: bool 是否成功移动游标 m_step次
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**********************************************************************/
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);
}
/**********************************************************************
* Function: pre()
* Description: 向前移动游标 m_step次
* Input:
* Output:
* Return: bool 是否成功移动游标 m_step次
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
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);
}
/**********************************************************************
* Function: ~DualLinkList()
* Description: 析构函数 - 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/19 1.0 Create
**********************************************************************/
~DualCircleList()
{
clear();
}
};
}
#endif // DUALCIRCLELIST_H
6、小结
- Linux内核链表是带头结点的双向循环链表
- DualCircleList使用Linux内核链表进行内部实现
- DualCircleList在循环遍历时需要跳过头结点
- 将list_head指针转换为目标结点指针时，使用list_entry宏
7、思考题
下面代码中的pn1和pn2是否相等？为什么？
