/* 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; 
}