採用一個節點數組以及對該數組進行索引的模擬指針 ，可以使設計更方便、 更高效。模擬指針是使用一段連續的存儲區來模擬指針的功能，可以有效的利用一段連續記憶體進行一定範圍內可變的子鍊表的空間分配。
基本介紹
- 中文名：模擬指針
- 外文名：simulated pointer
- 簡介：用一個節點數組並對數組進行索引
- 優點：使設計更方便、更高效
- 實現：設計一個過程來分配和釋放節點
- 套用學科：計算機科學、測繪科學、通信工程
簡介,實現,類定義,採用的鍊表,
簡介
假定採用一個數組node，該數組的每個元素中都包含兩個域：data和link。數組中的節點分別是：node[0]、node[l]、...、node[Number Of Nodes-l]。以下用節點i來代表node[i]。如果一個單向鍊表c由節點10，5和24按序構成，將得到c=10(指向鍊表c的第一個節點的指針是整數類型)，node[10].link=5(指向第二個節點的指針)，node[5].link=24(指向下一個節點的指針)，node[24].link=-1(表示節點24是鍊表中的最後一個節點)。在繪製鍊表時，可以把每個連結指針畫成一個箭頭（如圖1所示），與使用C++指針的時候一樣。
圖1 模擬指針的鍊表
實現
為了實現指針的模擬，需要設計一個過程來分配和釋放一個節點。當前未被使用的節點將被放入一個存儲池（storage pool）之中。開始時，存儲池中包含了所有節點node[0：Number-OfNodes-l]。Allocate從存儲池中取出節點，每次取出一個。Deallocate則將節點放入存儲池中，每次放入一個。因此，Allocate和Deallocate分別對存儲池執行插入和刪除操作，等價於C++函式delete和new。如果存儲池是一個節點鍊表（如圖2所示），這兩個函式可以高效地執行。
圖2 可用空間表
用作存儲池的鍊表被稱之為可用空間表（available space list），其中包含了當前未使用的所有節點。first是一個類型為int的變數，它指向可用空間表中的第一個節點。添加和刪除操作都是在可用空間表的前部進行的。
類定義
為了實現一個模擬指針系統，定義了SimNode類和SimSpace類，具體代碼如下所示：
template <class T>
class SimNode {
friend SimSpace<T>;
private :
T data;
int link;
};
template <class T>
class SimSpace {
public :
SimSpace (int MaxSpaceSize=100);
~SimSpace() {delete [] node;}
int Allocate(); //分配一個節點
void Deallocate (int& i) ;
//釋放節點i
private:
int NumberOfNodes, first;
SimNode<T> *node;//節點數組
} ;
SimSpace的操作
由於所有節點初始時都是自由的，因此在剛被創建的時候，可用空間表中包含NumberOfNodes個節點。用來對可用空間表進行初始化。如下兩個程式分別實現Allocate和Deallocate操作。
使用模擬指針分配一個節點
template<class T>
int SimSpace<T>::Allocate()
{// 分配一個自由節點
if (first == -1) throw NoMem();
int i = first; //分配第一個節點
first = node[i].link; //first指向下一個自由節點
return i;
}
使用模擬指針釋放一個節點
t
emplate<class T>
void SimSpace<T>::Deallocate(int& i)
{// 釋放節點i .
/ /使i 成為可用空間表的第一個節點
node[i].link = first;
first = i;
i = -1;
}
採用的鍊表
可以使用模擬空間S來定義一個鍊表類。S被說明為一個static成員，目的是使所有類型為T的模擬鍊表共享相同的模擬空間。如下程式給出了除Search和Output之外的各共享函式的代碼。這些代碼假定SimChain已經被說明為SimNode和SimSpace的友元。
模擬鍊表的類定義
template<class T>
class SimChain{
public:
SimChain(){first=-1;}
~SimChain(){Destroy();}voidDestroy();// 使表為空
int Length()const;boolFind(intk,T&x)const;
int Search(constT&x)const;
SimChain<T>&Delete(intk,T&x);
SimChain<T>&Insert(intk,constT&x);
void Output(ostream&out)const;
private:
int first;// 第一個節點的索引staticSimSpace<T>S;
};
構造函式和Length函式
template<class T>
void SimChain<T>::Destroy()
{// 釋放鍊表節點
int next;
while(first!=-1){
next=S.node[first].link;
S.Deallocate(first);
first=next;}
}
template<class T>
int SimChain<T>::Length()const
{// 返回鍊表的長度
int current=first；//鏈節點的當前位置
len=0;//元素計數
while(current!=-1){
current=S.node[current].link;len++;}
return len;
}
Find函式
template<class T>
bool SimChain<T>::Find(intk,T&x)const
{// 取第k個元素至x
//如果不存在第k個元素，函式返回false，否則返回true
if(k<1) return false;
int current=first,// 鏈節點的當前位置
index=1;//當前節點的索引
//移動current至第k個節點
while(index<k&¤t!=-1){
current=S.node[current].link;
index++;}
//驗證是否到達了第k個節點
if(current!=-1){
x=S.node[current].data;
return true;}
return false;// 不存在第k個元素
}
Delete函式
template<class T>
SimChain<T>&SimChain<T>::Delete(intk,T&x)
{//把第k個元素取至x，然後刪除第k個元素
//如果不存在第k個元素，則引發異常OutOfBounds
if(k<1||first==-1)throw OutOfBounds();// 不存在第k個元素
//p最終將指向第k個節點intp=first;
//將p移動至第k個節點，並從鍊表中刪除該節點
if(k==1)//p已經指向第k個節點
first=S.node[first].link;// 從鍊表中刪除
else{// 使用q指向第k-1個元素
int q=first;
for(intindex=1;index<k-1&&q!=-1;index++)
q=S.node[q].link;
// 驗證第k個元素的存在性
if(q==-1||S.node[q].link==-1) throw OutOfBounds();// 不存在第k個元素
//使p指向第k個元素
p=S.node[q].link;
//從鍊表中刪除第k個元素
S.node[q].link=S.node[p].link;
}
//保存第k個元素並釋放節點
px=S.node[p].data;
S.Deallocate(p);
return*this;
}
Insert函式
template<class T>
SimChain<T>&SimChain<T>::Insert(intk,constT&x)
{//在第k個元素之後插入x
//如果不存在第k個元素，則引發異常OutOfBounds
//如果沒有足夠的空間，則傳遞NoMem異常
if(k<0)throwOutOfBounds();
//定義一個指針p，p最終將指向第k個節點
int p=first;
//將p移向第k個節點
for(intindex=1;index<k&&p!=-1;index++)
p=S.node[pl.link;
// 驗證第k個節點的存在性
if(k>0&&p==-1)
throw OutOfBounds();
// 為插入操作分配一個新節點
int y=S.Allocate();
S.node[y].data=x;
//向鍊表中插入新節點
// 首先檢查新節點是否要插到鍊表的首部
if(k){//在p之後插入
S.node[y].link=S.node[p].link;S.node[p].link=y;}
else{// 作為鍊表首節點
S.node[y].link=first;first=y;}
return*this;
}
