25_静态单链表的实现

关键词： 单链表的一个缺点、静态单链表设计思路、静态单链表的继承层次结构、静态单链表的实现思路、静态单链表的实现

1. 单链表的一个缺点

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

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

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

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

4. 静态单链表的实现思路

• 通过模板定义静态单链表类（StaticLinkLisk）
• 在类中定义固定大小的空间（unsigned char[]）
• 重写create和destroy函数，改变内存的分配和归还方式
• 在Node类中重载operator new，用于在指定内存上创建对象

5. 静态单链表的实现

StaticLinkList.h

#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