/* Author : Moyiii  * Mail: lc09@vip.qq.com  * 靜態鏈表實現，僅作學習之用，當然如果  * 你想拿去用，隨你好啦。 */  #include <iostream>  using namespace std;  #define MAX_LIST_SIZE 100  class Node { public:   int data;   int cur; };   class SLinkList { public:   SLinkList();   //和普通的線性鏈表區別不是很大。除了兩個分配   //和回收節點空間的函數，具體算法請參考課本或   //網絡資料   int newNode();   bool deleteNode(int pos);   bool insertElem(int pos, int elem);   bool deleteElem(int pos);   int& getElem(int pos);   int getLength();   bool isEmpty();   void print();   void clear();  private:   int head;//這個可以不要，默認等于0   int space;   int length;   Node *elems; };   SLinkList :: SLinkList() {   // 0號位置為頭幾點，不可以更改，初始指向自己   // 從1~MAXLENGTH為可分配節點，最初由space管理    elems = new Node[MAX_LIST_SIZE];   if(!elems)   {     cout << "Malloc failed!" << endl;   }    head = space = length = 0;    for(int i = 0; i < MAX_LIST_SIZE; ++i)   {     elems[i].data = i;     elems[i].cur = i + 1;   }   elems[MAX_LIST_SIZE - 1].cur = 0;   elems[0].cur = 0;   space = 1; }  //從space指向的備用節點鏈表中取下一個節點 int SLinkList :: newNode() {   if(space == 0)   {     cout << "Space is full!" << endl;     return 0;   }    int pos = space;   space = elems[space].cur;   elems[pos].cur = 0;   return pos; }  //回收節點空間 bool SLinkList :: deleteNode(int pos) {   if(pos == 0)   {     cout << "Free space Error!" << endl;     return false;   }   elems[pos].cur = space;   space = pos;   return true; }  //插入節點，思路類似，找到被刪除節點的前一個節點 //然后更改指向 bool SLinkList :: insertElem(int pos, int elem) {   if(length == MAX_LIST_SIZE)   {     cout << "Space is Full" << endl;     return false;   }    if(pos < 1 || pos > length + 1)   {     cout << "Insert Over Bound" << endl;     return false;   }    int index = head;   for(int i = 1; i <= pos - 1; ++i)   {     index = elems[index].cur;   }    int node = newNode();   if(node == 0)   {     cout << "Space malloc failed" << endl;     return false;   }   elems[node].data = elem;   elems[node].cur = elems[index].cur;   elems[index].cur = node;    length++;   return true; }  //一回事，注意把刪除的節點回收給space bool SLinkList :: deleteElem(int pos) {   if(pos < 1 || pos > length)   {     cout << "Delete Node over Bound!" << endl;     return false;   }    int index = head;    for(int i = 1; i <= pos - 1; ++i)   {     index = elems[index].cur;   }    int node = elems[index].cur;   elems[index].cur = elems[node].cur;    deleteNode(node);    length--;    return true; }  void SLinkList :: print() {   int index = elems[head].cur;   while(index != 0)   {     cout << elems[index].data << " ";     index = elems[index].cur;   }   cout << endl;   return; }  int SLinkList :: getLength() {   return length; }  bool SLinkList :: isEmpty() {   if(length == 0)   {     return true;   }   else   {     return false;   } }  int& SLinkList :: getElem(int pos) {   int index = head;   for(int i = 1; i <= pos; ++i)   {     index = elems[index].cur;   }   return elems[index].data; }  void SLinkList :: clear() {   for(int i = 0; i < MAX_LIST_SIZE; ++i)   {     elems[i].data = i;     elems[i].cur = i + 1;   }   elems[MAX_LIST_SIZE - 1].cur = 0;   elems[0].cur = 0;   space = 1; }  int main() {   //測試數據，測試插入刪除空間是否溢出   SLinkList myList;    for(int i = 1; i <= 105; ++i)   {     myList.insertElem(1,i);   }    //myList.print();    for(int i = 1; i <= 105; ++i)   {     myList.deleteElem(1);   }    //myList.print();    //普通測試    for(int i = 1; i <= 10; ++i)   {     myList.insertElem(1,i);   }    myList.print();   cout << "Length= " << myList.getLength() <<endl;    myList.deleteElem(5);    myList.print();    cout << "Length= " << myList.getLength() <<endl;    cout << myList.isEmpty() << endl;    int &elem = myList.getElem(3);     elem = 99;    myList.print();    myList.clear();    myList.print();    return 0; }