关键词： 单链表的一个缺点、静态单链表设计思路、静态单链表的继承层次结构、静态单链表的实现思路、静态单链表的实现
1. 单链表的一个缺点
长时间使用单链表对象频繁增加和删除数据元素，可能会导致堆空间产生大量的内存碎片，导致系统运行缓慢。
2. 静态单链表设计思路：
在“单链表”的内部增加一片预留的空间，所有的Node对象都在这片空间中动态创建和动态销毁。
3. 静态单链表的继承层次结构
4. 静态单链表的实现思路
- 通过模板定义静态单链表类（
StaticLinkLisk） - 在类中定义固定大小的空间（
unsigned char[]） - 重写
create和destroy函数，改变内存的分配和归还方式 - 在
Node类中重载operator new，用于在指定内存上创建对象
5. 静态单链表的实现
#ifndef STATICLINKLIST_H
#define STATICLINKLIST_H
#include "LinkList.h"
namespace DTLib
{
template<typename T, int N>
class StaticLinkList : public LinkList<T>
{
protected:
typedef typename LinkList<T>::Node Node; // 重命名
struct SNode : public Node // new操作符重载
{
void* operator new(unsigned int size, void* loc)
{
(void)size;
return loc;
}
};
unsigned char m_space[sizeof(SNode) * N]; // 预留空间大小
int m_used[N]; // 标记数组
Node* create() // 重写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();
m_used[i] = 1;
break;
}
}
return ret;
}
void destroy(Node* pn) //重写destroy()
{
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();
}
}
}
public:
StaticLinkList()
{
for(int i=0; i<N; i++)
{
m_used[i] = 0;
}
}
int capacity()
{
return N;
}
};
}
#endif // STATICLINKLIST_H
6. LinkList中封装create和destroy的函数的意义是什么？
是为了静态单链表（StaticLinkList）的实现做准备。StaticLinkList与LinkList不同仅仅在于链表结点内存分配上的不同。因此，将仅有的不同封装于父类和子类的虚函数中。
7. 小结
- 顺序表与单链表相结合后衍生出静态单链表
- 静态单链表是
LinkList的子类，拥有单链表的所有操作 - 静态单链表在预留的空间中创建结点对象
- 静态单链表适合于频繁增删数据元素的场合（最大元素个数一定要固定）
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
