25_静态单链表的实现

2018-01-26 10:30:27来源:https://www.jianshu.com/p/64bf03be3de6作者:jacob2359人点击

分享

关键词:


1. 单链表的一个缺点

长时间使用单链表对象频繁增加和删除数据元素,可能会导致堆空间产生大量的内存碎片,导致系统运行缓慢。


2. 静态单链表设计思路:

在“单链表”的内部增加一片预留的空间,所有的Node对象都在这片空间中动态创建和动态销毁。





3. 静态单链表的继承层次结构



4. 静态单链表的实现思路
通过模板定义静态单链表类(StaticLinkLisk
在类中定义固定大小的空间(unsigned char[]
重写createdestroy函数,改变内存的分配和归还方式
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中封装createdestroy的函数的意义是什么?

是为了静态单链表(StaticLinkList)的实现做准备。StaticLinkListLinkList不同仅仅在于链表结点内存分配上的不同。因此,将仅有的不同封装于父类和子类的虚函数中。


7. 小结
顺序表与单链表相结合后衍生出静态单链表
静态单链表是LinkList的子类,拥有单链表的所有操作
静态单链表在预留的空间中创建结点对象
静态单链表适合于频繁增删数据元素的场合(最大元素个数一定要固定)


声明:此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记,文章中包含狄泰软件资料内容,一切版权归狄泰软件所有!
实验环境:ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4






最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台