C++数据结构03--静态链式线性表的实现

头文件：

//静态链表头文件
#include "stdafx.h"

using namespace std;

#define MAXSIZE 250

typedef int ElemType;

typedef struct{
  ElemType data;
  int cur; //存在next的指针游标
} StaticLinkList[MAXSIZE];

class StaticLinuralList{

public:
  StaticLinuralList();//构造函数
  ~StaticLinuralList();
private:

  int cur_Length;

  //初始化链表
  bool InitList(StaticLinkList L);

  //是否链表已满
  //return:true:满，false:非满
  bool isFull(StaticLinkList L);

  //获得一个可以插入的节点的下标
  //@param:L:需要的链表L
  //return:空的可插入的下标
  int GetEmptyPos(StaticLinkList L);

  //得到链表的长度
  //@param[in]:L:当前链表
  // return: 链表的长度
  int getListLength(StaticLinkList L); 

  //插入数据
  //@param[in]:L:当前链表
  //@param[in]:pos:插入的位置
  //@param[in]:data:插入的数据
  // return:true:插入成功，false:插入失败
  bool InsertData(StaticLinkList L,int pos,ElemType data);
  
  //删除元素
  //@param[in]:L:当前链表
  //@param[in]:pos:删除的位置
  // return:true:删除成功，false:删除失败
  bool DeleteData(StaticLinkList L,int pos);

  //查找元素
  //@param[in]:L:当前链表
  //@param[in]:pos:位置
  // return:位置的数据
  ElemType FindDataByPos(StaticLinkList L,int pos);

};

实现cpp文件：

/* 静态链表头文件 */

#include "stdafx.h"
#include "StaticLineList.h"
using namespace std;

StaticLinuralList::StaticLinuralList(){
   cur_Length = 0;//初始化长度为0；
}

StaticLinuralList::~StaticLinuralList(){

}

//初始化链表
//其中 最后一个是cur为0 指向第一个坐标
bool  StaticLinuralList::InitList(StaticLinkList L){
   int i = 0;
   for (i = 0 ; i < MAXSIZE-1;i++)
   {
      L[i].cur = i+1;
   }
   L[MAXSIZE-1].cur = 0;  //设置最后一个为空
   return true;
}


//得到链表的长度
//@param[in]:L:当前链表
// return: 链表的长度
int StaticLinuralList::getListLength(StaticLinkList L){
   return cur_Length;
}

//插入数据
//@param[in]:L:当前链表
//@param[in]:pos:插入的位置
//@param[in]:data:插入的数据
// return:true:插入成功，false:插入失败
bool StaticLinuralList::InsertData(StaticLinkList L,int pos,ElemType data){
   
   if (isFull(L))
   {
      std::cout << " 链表已经满了"<< endl;
      return false;
   }
   if (pos < 1 || pos > cur_Length + 1)
   {
      cout << "Error to Insert!" << endl;
   }
   //获取可以插入的pos
   int k = GetEmptyPos(L);
   int j = MAXSIZE-1;
   if (k)
   {
      L[k].data = data;
      for(int i = 1; i <= pos -1; ++i){
         j = L[j].cur;
      }
      L[k].cur = L[j].cur;
      L[j].cur = k;
      ++cur_Length;
      return true;
   }
   return false;
}

//删除元素
//@param[in]:L:当前链表
//@param[in]:pos:删除的位置
// return:true:删除成功，false:删除失败
bool StaticLinuralList::DeleteData(StaticLinkList L,int pos){
   if (cur_Length == 0)//假设链表为空。不运行删除操作
   {
      return false;
   }
   if (pos<1 || pos>cur_Length )//假设删除的位置不合法，返回false
   {
      cout << "The invalid index!\n";
      return false;
   }
   int k = MAXSIZE - 1;
   int i = 1;
   for (; i <= pos- 1;++i)//找到第index-1个节点k
   {
      k = L[k].cur;
   }
   i = L[k].cur;//i为第index个节点的下标
   L[k].cur = L[i].cur;//将第index-1个节点的cur设置成第index个节点的cur，实现了把第index个节点排除在链表之外
   //data = StList[i].data;//返回第index个节点的data给e
   //DeleteSpace(i);//回收第index个节点的空间
   --cur_Length;//链表长度减一
   return true;
}

//查找元素
//@param[in]:L:当前链表
//@param[in]:pos:位置
// return:位置的数据
ElemType StaticLinuralList::FindDataByPos(StaticLinkList L,int pos){
   if (pos==1)
   {
      return L[pos-1].data;
   }
   if (L[pos-2].cur == 0)
   {
      cout << "数据为空" << endl;
      return 0;
   }
   return L[pos-1].data;
}

//判断是否已满
bool StaticLinuralList::isFull(StaticLinkList L)
{
   if (cur_Length == MAXSIZE-1)
   {
      return true;
   }
   return false;
}

//获取可插入的下标
int StaticLinuralList::GetEmptyPos(StaticLinkList L){
   //参考链接：https://blog.csdn.net/yyc1023/article/details/22230795
   int i = L[0].cur;
   if (i)//存在的话
   {
      L[0].cur = L[i].cur;
   }
   return i;
}