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

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

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

/* Author : Moyiii
 * Mail: [e-mail]
 * 静态链表实现，仅作学习之用，当然如果
 * 你想拿去用，随你好啦。
*/

#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;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！