外观
04.线性表的链式存储结构、单链表的具体实现、单链表的遍历与优化、典型问题分析（Bugfix）
二十一、线性表的链式存储结构
1、线性表的链式存储结构
顺序存储结构线性表的最大问题是：插入和删除需要移动大量的元素！如何解决？
2、链式存储的定义
为了表示每个数据元素与其直接后继元素之间的逻辑关系；
数据元素除了存储本身的信息外，还需要存储其直接后继的信息。
3、链式存储逻辑结构
基于链式存储结构的线性表中，每个结点都包含数据域和指针域
数据域：存储数据元素本身
指针域：存储相邻结点的地址
4、专业术语的统一
- 顺序表
- 基于顺序存储结构的线性表
- 链表
- 基于链式存储机构的线性表
- 单链表：每个结点只包含直接后继的地址信息
- 循环链表：单链表中的最后一个结点的直接后继为第一个结点
- 双向链表：单链表中的结点包含直接前驱和后继的地址信息
5、链表中的基本概念
- 头结点
- 链表中的辅助结点，包含指向第一个数据元素的指针
- 数据结点
- 链表中代表数据元素的结点，表现形式为：（数据元素，地址）
- 尾结点
- 链表中的最后一个数据结点，包含的地址信息为空
6、单链表中的结点定义
7、单链表中的内部结构
头结点在单链表中的意义是：辅助数据元素的定位，方便插入和删除操作；因此，头结点不存储实际的数据元素
8、在目标位置处插入数据元素
从头结点开始，通过current指针定位到目标位置
从堆空间申请新的Node结点
执行操作：
9、在目标位置处删除数据元素
从头结点开始，通过current指针定位到目标位置
使用toDel指针指向需要删除的结点
执行操作：
10、编程实验：图解插入与删除
11、小结
- 链表中的数据元素在物理内存中无相邻关系
- 链表中的结点都包含数据域和指针域
- 头结点用于辅助数据元素的定位，方便插入和删除操作
- 插入和删除操作需要保证链表的完整性
二十二、单链表的具体实现
1、课程目标
完成链式存储结构线性表的实现
2、LinkList设计要点
- 类模板，通过头结点访问后继结点
- 定义内部结点类型Node，用于描述数据域和指针域
- 实现线性表的关键操作（增，删，查，等）
3、LinkList的定义
4、编程实验：链表的实现
LinkList.h
5、问题
头结点是否存在隐患？实现代码是否需要优化？
6、头结点的隐患
7、代码优化
insert , remove , get , set 等操作都涉及元素定位。
8、编程实验：链表的优化
LinkList.h
#ifndef LINKLIST_H_
#define LINKLIST_H_
/***
* Include _Files *
***/
#include "List.h"
#include "Exception.h"
/***
* Type Definition *
***/
namespace DTLib
{
template < typename T >
class LinkList : public List<T>
{
protected:
struct Node : public Object // 结点类
{
Node* next; // 指针域
T value; // 数据域
};
mutable struct : public Object // mutable 突破const的限制而设置,永远处于可变的状态,即使在一个const函数中
{
Node* next; // 指向0元素
char reserved[sizeof(T)]; // 为了与Node内存对齐，以便后续使用强制类型转换，继承于Object同理。
} 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/18 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/18 1.0 Create
**/
virtual Node* create()
{
return new Node();
}
/**
* Function: destroy()
* Description: 销毁结点(堆空间)
* Input: pn 待销毁的结点
* Output:
* Return:
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**/
virtual void destroy(Node* pn) // 释放结点
{
delete pn;
}
public:
/**
* Function: LinkList()
* Description: 构造函数 - 初始化参数
* Input:
* Output:
* Return:
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**/
LinkList()
{
m_header.next = 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/18 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->value = e; // 新节点的数据域(value)赋值
node->next = current->next; // 新节点的指针域(next) 指向下一个结点
current->next = node; // 上一个结点的指针域(next) 指向新结点
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/18 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; // 临时保存 待删除结点的地址
if( m_current == toDel ) // 判断游标是否指向 待删除结点的地址
{
m_current = toDel->next; // 指向 待删除结点的下一个结点的地址
}
current->next = toDel->next; // 待删除结点的下一个结点的地址，赋值给待删除结点的前一个结点的next
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/18 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/18 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/18 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/18 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/18 1.0 Create
**/
void clear()
{
while( m_header.next ) // 0元素的地址是否为 NULL
{
Node* toDel = m_header.next; // 暂存0结点的地址
m_header.next = toDel->next; // 新0号元素地址赋值给头结点
m_length--; // 当前线性表的长度 -1 为了防止元素为类时，析构函数抛出异常，无法保证链表的安全性
destroy(toDel); // 销毁结点
}
m_current = NULL;
}
/*
遍历所有元素 推荐使用方法
移动到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
**/
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/18 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/18 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/18 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: ~LinkList()
* Description: 析构函数 - 清空线性表
* Input:
* Output:
* Return:
* Others: O(n)
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**/
~LinkList()
{
clear();
}
};
}
#endif // LINKLIST_H_9、小结
- 通过类模板实现链表，包含头结点成员和长度成员
- 定义结点类型，并通过堆中的结点对象构成链式存储
- 为了避免构造错误的隐患，头结点类型需要重定义（内存布局必须一致，都要继承object）
- 代码优化是编码完成后必不可少的环节
二十三、顺序表和单链表的对比分析
1、问题
如何判断某个数据元素是否存在于线性表中？
2、遗失的操作 - find
- 可以为线性表（List）增加一个查找操作
- int find(const T& e) const;
- 参数：
- 待查找的数据元素
- 返回值：
- >= 0：数据元素在线性表中第一次出现的位置
- -1：数据元素不存在
3、数据元素查找示例
4、编程实验：查找操作
List.h
① 实际开发时，建议每个自定义类都继承object父类，避免编译错误。
② find函数需要比对两个元素是否相同，当比对元素为类时，需要重载==和!=操作符。
5、时间复杂度对比分析
6、有趣的问题
顺序表的整体时间复杂度比单链表要低，
那么单链表还有使用价值吗？
7、效率的深度分析
实际工程开发中，时间复杂度只是效率的一个参考指标
对于内置基础类型，顺序表和单链表的效率不相上下
对于自定义类类型，顺序表在效率上低于单链表
插入和删除
顺序表：涉及大量数据对象的复制操作
单链表：只涉及指针操作，效率与数据对象无关
数据访问
顺序表：随机访问，可直接定位数据对象
单链表：顺序访问，必须从头访问数据对象，无法直接定位
8、工程开发中的选择
- 顺序表
- 数据元素的类型相对简单，不涉及深拷贝
- 数据元素相对稳定，访问操作远多于插入和删除操作
- 单链表
- 数据元素的类型相对复杂，复制操作相对耗时
- 数据元素不稳定，需要经常插入和删除，访问操作较少
9、小结
- 线性表中元素的查找依赖于相等比较操作符（ == ）
- 顺序表适用于访问需求量较大的场合（随机访问）
- 单链表适用于数据元素频繁插入删除的场合（顺序访问）
- 当数据类型相对简单时，顺序表和单链表的效率不相上下
二十四、单链表的遍历与优化
1、问题
如何遍历单链表中的每一个数据元素？
2、当前单链表的遍历方法
- O(n) O(n^2)
- 遗憾的事实
- 不能以线性的时间复杂度完成单链表的遍历
- 新的需求
- 为单链表提供新的方法，在线性时间内完成遍历
3、设计思路（游标）
- 在单链表的内部定义一个游标(Node* m_current)
- 遍历开始前将游标指向位置为0的数据元素
- 获取游标指向的数据元素
- 通过结点中的next 指针移动游标
4、设计思路（游标）
提供一组遍历相关的函数，以线性的时间复杂度遍历链表。
5、遍历函数原型设计
- bool move(int i, int step = 1); 目标位置 每次移动几个结点
- bool end();
- T current();
- bool next();
6、编程实验：单链表的遍历
LinkList.h
7、单链表内部的一次封装
8、编程实验：内部的封装
LinkList.h
9、问题
封装create 和destroy 函数的意义是什么?
封装结点的申请和删除操作更有利于增强扩展性。
10、小结
- 单链表的遍历需要在线性时间内完成
- 在单链表内部定义游标变量，通过游标变量提高效率
- 遍历相关的成员函数是相互依赖，相互配合的关系
- 封装结点的申请和删除操作更有利于增强扩展性
二十五、静态单链表的实现
1、讨论中。。。
2、单链表的一个缺陷
触发条件
长时间使用单链表对象频繁增加和删除数据元素
可能的结果
堆空间产生大量的内存碎片，导致系统运行缓慢
3、新的线性表
设计思路：
在“单链表”的内部增加一片预留的空间，所有的Node对象都在这片空间中动态创建和动态销毁。
4、静态单链表的继承层次结构
5、静态单链表的实现思路
- 通过模板定义静态单链表类(StaticLinkList)
- 在类中定义固定大小的空间(unsigned char [])
- 重写create和destroy函数，改变内存的分配和归还方式
- 在Node类中重载operator new，用于在指定内存上创建对象
6、编程实验：静态单链表的实现
StaticLinkList.h
#ifndef STATICLINKLIST_H_
#define STATICLINKLIST_H_
/***
* Include _Files *
***/
#include "LinkList.h"
/***
* Type Definition *
***/
namespace DTLib
{
template< typename T, int N >
class StaticLinkList : public LinkList<T>
{
protected:
typedef typename LinkList<T>::Node Node; // 使用typename的原因：编译器无法辨识标识符究竟是什么（是一个类型还是一个成员名称(静态数据成员或者静态函数)）
struct SNode : public Node // 结点的定义
{
void* operator new(unsigned int size, void* loc) // 重载new操作符
{
(void)size; // 消除 size没有使用的警告
return loc;
}
/*
placement new 是重载operator new 的一个标准、全局的版本，它不能够被自定义的版本代替
placement new的执行忽略了size_t参数，只返还第二个参数。其结果是允许用户把一个对象放到一个特定的地方，达到调用构造函数的效果。
括 号里的参数ptr是一个指针，它指向一个内存缓冲器，placement new将在这个缓冲器上分配一个对象。Placement new的返回值是这 个被构造对象的地址(比如括号中的传递参数)。
placement new主要适用于：在对时间要求非常高的应用程序中，因为这些程序分配的时间是确定 的；长时间运行而不被打断的程序；以及执行一个垃圾收集器 (garbage collector)。
*/
};
unsigned char m_space[sizeof(SNode) * N]; // N个空间单元
int m_used[N]; // 标记空间单元使用情况
/**
* Function: create()
* Description: 在指定内存中创建新结点
* Input:
* Output:
* Return: Node 返回新结点的地址
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**/
Node* create()
{
SNode* ret = NULL;
for(int i=0; i<N; i++) // 遍历各个空间
{
if( !m_used[i] ) // 如果没有被使用
{
ret = reinterpret_cast<SNode*>(m_space) + i; // 获取到对应的内存单元
ret = new(ret)SNode() ; // 调用SNode类的构造函数
m_used[i] = 1; // 标记当前的内存单元已使用
break;
}
}
return ret;
}
/**
* Function: destroy()
* Description: 在指定内存中删除结点
* Input: pn 欲删除结点的地址
* Output:
* Return:
* Others:
* Modify Date Version Author Modification
* ------------------------------------------------------------
* 2022/03/18 1.0 Create
**/
void destroy(Node* pn)
{
SNode* space = reinterpret_cast<SNode*>(m_space);
SNode* psn = dynamic_cast<SNode*>(pn);
for(int i=0; i<N; i++)
{
if( psn == (space + i) )
{
m_used[i] = 0; // 该空间单元使用情况为 可用
psn->~SNode(); // 调用析构函数，这里需要使用的是子类的析构函数，故需要对pn进行一个强制类型转换成子类对象
break;
}
}
}
public:
// 构造函数
StaticLinkList()
{
for(int i=0; i<N; i++)
{
m_used[i] = 0;
}
}
// 获取空间单元个数
int capacity()
{
return N;
}
// 析构函数
~StaticLinkList()
{
this->m_header.next = NULL; // 头结点标记为 空
}
};
}
#endif // STATICLINKLIST_H_7、Q&A
LinkList中封装create和destroy函数的意义是什么？
为静态单链表( StaticLinkList )的实现做准备。
StaticLinkList 与 LinkList的不同仅在于链表结点内存分配上的不同；
因此，将仅有的不同封装于父类和子类的虚函数中。
8、小结
- 顺序表与单链表相结合后衍生出静态单链表
- 静态单链表是LinkList的子类，拥有单链表的所有操作
- 静态单链表在预留的空间中创建结点对象
- 静态单链表适合于频繁增删数据元素的场合（最大元素个数固定）
二十六、典型问题分析（Bugfix）
1、ISSUE 1
- 创建异常对象时的空指针问题
- 需要判断_message是否为空(strdup默认入参不为空)
2、ISSUE2
- LinkList 中的数据元素删除
- List.remove在释放类内存时，析构函数抛出异常后，链表依然长度为3。
- 为了防止元素为类时，析构函数抛出异常，无法保证链表的安全性。
- 在释放内存之前，即调用析构函数之前，调整链表长度。
3、ISSUE 3
- LinkList 中遍历操作与删除操作的混合使用
- 当删除某个结点之前，需判断游标是否也指向该结点。若是，则将游标指向下一个结点。
4、ISSUE 4
- StaticLinkList中数据元素删除时的效率问题
5、ISSUE 5
- StaticLinkList是否需要提供析构函数？
- 问题描述：StaticLinkList继承于LinkList，在未定义析构函数时，会依次调用 子类析构函数、父类析构函数，在父类析构函数中会调用clear函数，
clear函数中调用了destroy函数，destroy函数调用了delete函数释放内存，而StaticLinkList使用的不是堆空间，所以会导致问题。
- 解决方案：在StaticLinkList创建析构函数直接调用父类的clear函数，此时由于构造函数和析构函数，不支持多态，所以会调用子类中的destroy函数。
6、ISSUE 6
- DTLib是否有必要增加多维数组类？
- 多维数组的本质：数组的数组！
7、实践经验
是软件就有bug，因此需要不停的迭代升级，解决问题。库是一种特殊的软件产品，也会存在各种bug，也需要迭代升级，解决问题。