C++ 实现静态单链表的实例_C/C++

C++ 实现静态单链表的实例

利用数组实现的静态单链表，与严蔚敏书实现略有不同，不另设回收空间。有任何BUG或错误，希望各位朋友多多反馈~~感激不尽

				?

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

									}