C++静态链表的实现（包括各操作的成员函数）

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
#define MAXSIZE 1000

#ifndef LIST_H
#define LIST_H
class node{//创建结点结构，包括数据和游标，游标记录下一个元素所对应的下标
public:
    int cur;
    int data;
};

class List{
public:
    List();//无参数的构造函数
    bool CreateList(int size);//初始链表
    int new_sl();//模仿普通链表的new分配内存空间
    void delete_sl(int i);//模仿普通链表的delete释放内存空间，这个形参i代表链表中将要释放的元素的下标
    void ClearList();//清空链表
    bool ListEmpty();//链表判空
    int ListLength();//获取链表长度
    bool GetElem(int i,int &e);//获取指定元素
    int LocateElem(int e);//寻找第一个等于e的数据元素的位序
    bool ChangeElem(int i,int e);//更改指定的元素
    void ListTraverse();//遍历链表
    bool ListInsert(int i,int Elem);//插入元素
    bool ListDelete(int i,int &Elem);//删除元素
private:
    node space[MAXSIZE];//静态链表是由数组的下标实现指针的功能
    int length=0;
};
#endif // !LIST_H

List::List(){
    length=0;
}
bool List::CreateList(int size){
    srand((unsigned int)time(NULL));//随机种子，为链表数据的创建提供随机值
    if(size<=0)//如果所要构建的链表长度小于等于0，返回false代表构建失败
        return false;
    for(int i=1;i<MAXSIZE-1;i++){//创建链表（包括备用链表和创建的链表），数组的下标0处储存备用链表（即尚未被使用的空间）的首个下标，故正式的元素从下标1开始
        space[i].cur=i+1;//每个元素都存储对应的游标，即下一个元素的下标，在初始化时就直接使用下一个元素的下标进行初始化
    }
    for(int i=1;i<=size;i++){
        space[i].data=rand()%100+1;//给创建的链表内的每个元素分配随机值
    }
    space[MAXSIZE-1].cur=1;//首个元素的游标由数组的最后一个元素存储
    length=size;
    return true;
}
int List::new_sl(){
    int i=space[0].cur;//获取备用链表的首个下标
    if(space[0].cur)
        space[0].cur=space[i].cur;//备用链表的原首下标被i拿去使用，现在需要创建新的首下标，原首下标对应的游标就是新的首下标
    return i;
}
void List::delete_sl(int i){
    space[i].cur=space[0].cur;/*将当前备用链表的首下标赋给将要释放的元素的游标，因为这个被释放的元素将成为备用链表的首个元素，那么当前备用链表的首下标就将成为这个元素的下一个元素的下标*/
    space[0].cur=i;//将被释放的元素下标的作为备用链表的首个下标
}
void List::ClearList(){
    int temp1=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    for(int i=0;i<length;i++){//因为要清空整个链表，因此遍历
        int temp2=space[temp1].cur;//再创建一个变量来暂时存储将要释放的元素的游标，因为将要释放的元素一但释放，会丢失游标信息，导致遍历无法继续
        delete_sl(temp1);//释放元素
        temp1=temp2;//将游标信息赋回temp1，保证遍历继续进行
    }
}
bool List::ListEmpty(){
    return length==0;
}
int List::ListLength(){
    return length;
}
bool List::GetElem(int i,int &e){
    if(i<0||i>length)//如果元素位置小于1或超过链表长度，返回false代表获取失败
        return false;
    int temp=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    for(int k=1;k<i;k++){//循环次数为元素位置减一，循环结束后temp变量是要获取的元素的上一个元素的游标，即我们要获取的元素的下标
        temp=space[temp].cur;//链表遍历的本质是游标的逐一传递，反复往后访问
    }
    e=space[temp].data;//将获取的元素的数据通过引用传递给e
    return true;
}
int List::LocateElem(int e){
    int i;
    int temp=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    bool flag=false;//判断是否找到了想要的元素
    for(i=0;i<length;i++){//遍历链表，逐一寻找
        temp=space[temp].cur;//链表遍历的本质是游标的逐一传递，反复往后访问
        if(e==space[temp].data){//如果找到了想要的元素，跳出循环并将flag设为true代表找到了
            flag=true;
            break;
        }
    }
    if(!flag)
        return -1;//返回位置为-1代表没找到
    else 
    return i;//返回想要的元素在链表中的次序位置，即是链表中的第几个元素（还有一种是返回temp，是返回相应的下标）
}
bool List::ChangeElem(int i,int e){
    if(i<0||i>length)//位置小于0或大于链表长度，返回false代表更改失败
        return false;
    int temp=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    for(int k=1;k<i;k++){//循环链表，游标达到指定位置为止
        temp=space[temp].cur;//链表遍历的本质是游标的逐一传递，反复往后访问
    }
    space[temp].data=e;//改变目标元素的值
    return true;
}
void List::ListTraverse(){
    int temp=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    for(int i=0;i<length;i++){//标准遍历，没什么好说的
        cout<<space[temp].data<<" ";
        temp=space[temp].cur;
    }
    cout<<endl;
}
bool List::ListInsert(int i,int Elem){
    if(i<0||i>length+1)//如果插入的位置小于0或大于链表长度，返回false代表插入失败
        return false;
    int pnew=new_sl();//创建新元素，分配内存（模拟）
    if(i==1){//头插，此时若按正常情况处理循环无法正常进行，因此特殊化处理，具体原理其实和普通的插一样
        space[pnew].cur=space[MAXSIZE-1].cur;
        space[MAXSIZE-1].cur=pnew;
        space[pnew].data=Elem;
        length++;
        return true;
    }
    int temp=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    for(int k=1;k<i-1;k++){//循环次数为将插入的位置减2，此时temp为插入位置的前二个元素的游标（也就是插入位置的前一个元素的下标）
        temp=space[temp].cur;
    }
    space[pnew].cur=space[temp].cur;//将插入位置的游标赋给新元素的游标，此时新元素向后的接口完成
    space[temp].cur=pnew;//将新元素的下标赋给插入位置的游标，此时新元素向前的接口完成
    space[pnew].data=Elem;//将数据赋给插入的元素
    length++;//长度增加
    return true;
}
bool List::ListDelete(int i,int &Elem){
    if(length==0||i<0||i>length)//如果删除的位置小于0或大于链表长度或链表为空，返回false代表删除失败
        return false;
    if(i==1){//头删，特殊化处理，原理和正常的删除一样
        int pde=space[MAXSIZE-1].cur;
        space[MAXSIZE-1].cur=space[pde].cur;
        Elem=space[pde].data;
        delete_sl(pde);
        length--;
        return true;
    }
    int temp=space[MAXSIZE-1].cur;//创建一个变量作为游标参与循环，首个元素的游标存在于数组的末尾，故将其赋给此变量
    for(int k=1;k<i-1;k++){//循环次数为将删除的位置减2，此时temp为删除位置的前二个元素的游标（也就是删除位置前一个元素的下标）
        temp=space[temp].cur;
    }
    int pde=space[temp].cur;//将删除位置的下标赋给一个整型变量
    space[temp].cur=space[pde].cur;//将删除位置的游标赋给前一个元素的游标，此时完成了跨过删除位置的元素链接，可以释放删除元素了
    Elem=space[pde].data;//将马上要被删除的元素赋给elem，避免数据彻底遗失
    delete_sl(pde);//释放删除元素
    length--;//长度减少
    return true;
}

int main(){//测试用主函数
    List a;
    a.CreateList(10);
    cout<<"All elem:";
    a.ListTraverse();
    cout<<"Length:"<<a.ListLength()<<endl;
    int e;
    a.GetElem(5,e);
    cout<<"Get elem:"<<e<<endl;
    cout<<a.LocateElem(e)<<endl;
    a.ChangeElem(5,6);
    cout<<"Change elem:";
    a.ListTraverse();
    a.ListInsert(1,6);
    cout<<"All elem:";
    a.ListTraverse();
    a.ListDelete(1,e);
    cout<<"All elem:";
    a.ListTraverse();
    return 0;
}