C++数据结构第25课、静态单链表的实现

单链表的一个缺陷 — 触发条件 长时间使用单链表对象频繁增加和删除数据元素 — 可能的结果 堆空间产生大量的内存碎片，导致系统运行缓慢新的线性表 静态单链表的继承层次 静态单链表的实现思路 — 通过模板定义静态单链表类（StaticLinkList） — 在类中定义固定大小的空间（unsigned char[]） — 重写 create 和 destroy 函数，改变内存的分配和归还方式 — 在 Node 类中重载 operator new ，用于指定内存上创建对象

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; unsigned char m_space[sizeof(typename LinkList<T>::Node) * N]; int m_used[N]; struct SNode : public Node { void* operator new(unsigned int size, void* loc) { (void)size; return loc; } }; SNode* creat() { 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) { SNode* space = reinterpret_cast<SNode*>(m_space); SNode* pst = dynamic_cast<SNode*>(pn); for(int i = 0; i < N; i++) { if(pst == (space + i)) { m_used[i] = 0; pst->~SNode(); } } } public: StaticLinkList() { for(int i = 0; i < N;i++) { m_used[i] = 0; } } int capacity() { return N; } }; } #endif // STATICLINKLIST_H

main.cpp

#include <iostream> #include "StaticLinkList.h" using namespace std; using namespace XiebsLib; int main() { StaticLinkList<int, 5> list; for(int i = 0; i < 5; i++) { list.insert(0, i); } for(list.move(0, 1); !list.end(); list.next()) { cout << list.current() << endl; } try { list.insert(1); } catch (const Exception& obj) { cout << obj.message() << endl; cout << obj.location() << endl; } return 0; }

静态单链表的原理：

其实它的原理等同于我们前面在C++课程里面学的 重写 new 操作符（69课自定义内存管理），使得它可以在栈上，静态存储空间等等里面申请内存空间。当我们使用关键字 new 在堆上动态创建一个对象时，它实际上做了三件事：1、获得一块内存空间、2、调用构造函数、3、返回正确的指针。 从代码的1-15行都是基本操作，不用过多解释。在重写 create() 函数时，下面两条语句是我思考的最久的两条语句。

ret = reinterpret_cast<SNode*>(m_space) + i; ret = new(ret)SNode;

第一句其实就是获得一段内存空间，但是它只涉及指针的移动，并不能去调用构造函数，如果它无法调用构造函数，那么 Node 这个节点结构体的成员变量就无法正确的初始化，这就是为什么我们要重新定义一个 SNode 的节点结构体继承于Node，重写 new 操作符，在重载函数里只返回地址不进行内存操作，使得 ret = new(ret)SNode; 这条语句的意思是在ret 这个地址上调用构造函数，最终返回ret的值。SNode 调用了构造函数，那么它的父类 Node 也会调用构造函数，使得Node 结构体内部的成员变量会被正确的初始化。

小结 — 顺序表和单链表结合后衍生出静态单链表 — 静态单链表是 LinkList 的子类，拥有单链表的所有操作 — 静态单链表在预留的空间中创建节点对象 — 静态单链表适合于频繁增删数据元素的场合（最大元素个数固定）