文章目錄

• • 1 靜態單鏈表的出現原因
  • 2 靜態單鏈表的實現思路
  • 3 繼承關系圖
  • 4 代碼實現
  • 5 StaticLinkList需要增加析構函數嗎

1 靜態單鏈表的出現原因

如果需要頻繁的刪除元素，并且數據元素的最大個數固定，我們該怎么選擇線性表呢？

很明顯，當需要頻繁的刪除元素時，使用單鏈表是明智的選擇。但是目前的單鏈表卻有如下的缺陷：當我們長時間使用單鏈表對象頻繁增加和刪除元素時，可能會導致堆空間產生大量的內存碎片，導致系統運行緩慢。

由于數據元素的最大個數固定，我們可以設計一種新的線性表：
在單鏈表內部增加一片預留的空間，所有的Node對象都在這片空間中動態創建和動態銷毀。

---

2 靜態單鏈表的實現思路

通過模板定義靜態單鏈表類（StaticLinkList）。

在類中定義固定大小的空間（unsigned char []）。

重寫create和destroy函數，改變內存的分配和歸還方式。

在Node類中重載operator new，用于在指定的內存上創建對象。

---

3 繼承關系圖

---

4 代碼實現

StaticLinkList

#ifndef STATICLINKLIST_H #define STATICLINKLIST_H#include "Linklist.h"namespace LemonLib { template < typename T, int N > class StaticLinkList : public LinkList<T> { protected:/* 由于模板的二階段編譯，所以這里我們必須采用這種方式使用父類中的類型 */typedef typename LinkList<T>::Node Node;unsigned char m_space[sizeof(Node)*N];int m_used[N];/* 為了能夠在指定的內存空間上調用構造函數，所以我們需要重載Node的new操作符 */struct SNode : public Node{/** 雖然new操作符返回的為void*類型，但編譯器會自動處理類型問題* 需要注意的是，當new操作符返回null時，編譯器就不會自動調用構造函數*/void* operator new(unsigned int size, void* loc){(void)size; // 避免編譯器發出警告return loc;}};Node* create(){Node* ret = NULL;for (int i=0; i<N; i++){if (m_used[i] == 0){ret = reinterpret_cast<Node*>(m_space) + i;ret = new(ret) SNode(); // 調用構造函數m_used[i] = 1;break;}}return ret;}void destroy(Node* pn){SNode* spn = dynamic_cast<SNode*>(pn); // static_cast用于有繼承關系的對象指針之間的轉換SNode* addr = reinterpret_cast<SNode*>(m_space);for (int i=0; i<N; i++){if (spn == (addr + i)){m_used[i] = 0;spn->~SNode(); // 調用析構函數break;}}}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 "Object.h" #include "Exception.h" #include "List.h" #include "Seqlist.h" #include "Staticlist.h" #include "Dynamiclist.h" #include "Staticarray.h" #include "DynamicArray.h" #include "Linklist.h" #include "Staticlinklist.h"using namespace std; using namespace LemonLib;int main() {StaticLinkList<int, 5> list;for (int i=0; i<5; i++){list.insert(0, i);}for (list.move(0); !list.end(); list.next()){cout << list.current() << endl;}return 0; }

---

5 StaticLinkList需要增加析構函數嗎

當前實現版本的StaticLinkList類并無析構函數，對于如下代碼：

構造比較簡單，不用多說。對于析構來說，會自動調用父類的析構函數。而父類的析構函數直接調用了clear函數，在clear中調用destroy函數釋放申請的空間。那么，思考如下問題：clear函數調用的真的是子類的destroy函數嗎？

構造函數和析構函數中不會發生多態，不管是直接調用還是間接調用，所調用的都是當前類中實現的版本。 所以對于以上分析的問題，會調用父類的destroy函數，這將導致delete釋放的有可能不是堆空間，會造成程序的不穩定。在實際工程開發中，這個問題必須避免。那么，我們有必要為StaticLinkList增加析構函數：

~StaticLinkList(){this->clear();}

在子類析構函數中完成空間的釋放，那么在父類的析構函數中就不會再重復釋放空間，如上問題也就完美的解決了。

總結

以上是生活随笔為你收集整理的StaticLinkList的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。