#ifndef StaticList_h
#define StaticList_h
const int maxSize = 100; // 靜態(tài)鏈表大小
template <class T>
struct SLinkNode {
 T data; // 結(jié)點(diǎn)數(shù)據(jù)
 int link; // 結(jié)點(diǎn)鏈接指針
};
 
template <class T>
class StaticList {
public:
 void InitList(); // 初始化
 int Length(); // 計(jì)算靜態(tài)鏈表的長(zhǎng)度
 int Search(T x); // 在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)
 int Locate(int i); // 在靜態(tài)鏈表中查找第i個(gè)結(jié)點(diǎn)
 bool Append(T x); // 在靜態(tài)鏈表的表尾追加一個(gè)新結(jié)點(diǎn)
 bool Insert(int i, T x); // 在靜態(tài)鏈表第i個(gè)結(jié)點(diǎn)后插入新結(jié)點(diǎn)
 bool Remove(int i); // 在靜態(tài)鏈表中釋放第i個(gè)結(jié)點(diǎn)
 bool isEmpty(); // 判鏈表空否？
private:
 SLinkNode<T> elem[maxSize];
 int avil; // 當(dāng)前可分配空間首地址
};
 
template <class T>
void StaticList<T>::InitList() {
 // 初始化
 elem[0].link = -1;
 avil = 1;
 // 當(dāng)前可分配空間從1開(kāi)始建立帶表頭結(jié)點(diǎn)的空鏈表
 for(int i = 1; i < maxSize - 1; i++)
 elem[i].link = i + 1; // 構(gòu)成空閑鏈接表
 elem[maxSize-1].link = -1;
}
 
template <class T>
int StaticList<T>::Length() {
 // 計(jì)算靜態(tài)鏈表的長(zhǎng)度
 int p = elem[0].link;
 int i = 0;
 
 while(p != -1) {
 p = elem[p].link;
 i++;
 }
 return i;
}
 
template <class T>
int StaticList<T>::Search(T x) {
 // 在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)
 int p = elem[0].link; // 指針p指向鏈表第一個(gè)結(jié)點(diǎn)
 
 while(p != -1) { // 逐個(gè)結(jié)點(diǎn)檢測(cè)查找給定的值
 if(elem[p].data == x)
 break;
 else
 p = elem[p].link;
 }
 return p;
}
 
template <class T>
int StaticList<T>::Locate(int i) {
 // 在靜態(tài)鏈表中查找第i個(gè)結(jié)點(diǎn)
 if(i < 0) // 參數(shù)不合理
 return -1;
 if(i == 0)
 return 0;
 int j = 1, p = elem[0].link;
 while(p != -1 && j < i) { // 循鏈查找第i號(hào)結(jié)點(diǎn)
 p = elem[p].link;
 j++;
 }
 return p;
}
 
template <class T>
bool StaticList<T>::Append(T x) {
 // 在靜態(tài)鏈表的表尾追加一個(gè)新結(jié)點(diǎn)
 if(avil == -1) // 沒(méi)有分配到存儲(chǔ)空間
 return false;
 int q = avil; // 分配結(jié)點(diǎn)
 avil = elem[avil].link; // 指向下一個(gè)可分配的結(jié)點(diǎn)
 elem[q].data = x;
 elem[q].link = -1;
 int p = 0;
 // 查找表尾
 while(elem[p].link != -1)
 p = elem[p].link;
 elem[p].link = q; // 追加
 return true;
}
 
template <class T>
bool StaticList<T>::Insert(int i, T x) {
 // 在靜態(tài)鏈表第i個(gè)結(jié)點(diǎn)后插入新結(jié)點(diǎn)
 int p = Locate(i);
 
 if(p == -1) // 找不到結(jié)點(diǎn)
 return false;
 int q = avil; // 分配結(jié)點(diǎn)
 avil = elem[avil].link;
 elem[q].data = x;
 elem[q].link = elem[p].link; // 鏈入
 elem[p].link = q;
 return true;
}
 
template <class T>
bool StaticList<T>::Remove(int i) {
 // 在靜態(tài)鏈表中釋放第i個(gè)結(jié)點(diǎn)
 int p = Locate(i-1);
 
 if(p == -1) // 找不到結(jié)點(diǎn)
 return false;
 int q = elem[p].link; // 第i號(hào)結(jié)點(diǎn)
 elem[p].link = elem[q].link;
 elem[q].link = avil; // 釋放,讓q的link指向原可分配的結(jié)點(diǎn)
 avil = q; // avil指向q
 return true;
}
 
template <class T>
bool StaticList<T>::isEmpty() {
 // 判鏈表空否？
 if(elem[0].link == -1)
 return true;
 return false;
}
 
#endif /* StaticList_h */