线性表 - 数组

与教材略有出入

/*
    ADT Linear_list{
        InitList();         //初始化
        ListLength(L);      //获取长度
        GetData(L,i);       //获取对应数字
        InsList(L,i,b);     //插入
        DelList(L,i);       //删除
        UpdateList(L,i,e);  //更改
    }ADT Linear_list
*/
#define MAXSIZE 10010   //单个线性表最大长度
#define OPT_SUCCESS 1   //操作成功
#define OPT_ERROR 0     //操作失败
typedef int ElemType;   //整型作为数据类型
typedef struct 
{
    ElemType elem[MAXSIZE];     //一个储存数据的数组
    int last;                   //一个储存最后元素位置的指针
}SeqList;
SeqList L;                      //全局变量
SeqList *pL = &L;
void InitList(){
    L.last = -1;                //-1为空
}
int ListLength(){
    return L.last;              //直接返回长度
}
ElemType GetData(SeqList *L, int i){
    // O(1)
    return L->elem[i];          //直接获取角标
}
int Locate(SeqList *L, ElemType e){
    int i = 0;
    for(i = 0;i < L->last;i++){
        if(e == L->elem[i])     //搜索算法
        return i;
    }
    // O(n)
    return -1;
}
int InsList(SeqList *L, int i, ElemType e){
    if(i < 0 || i> L->last+1){
        return OPT_ERROR;       //不在范围内
    }
    if(L->last>=MAXSIZE-1){
        return OPT_ERROR;       //表满
    }
    int k = 0;
    for(k = L->last; k >= i; k--){
        L->elem[k+1] = L->elem[k];      //所有元素后移
    }
    L->elem[i] = e;                     //插入
    L->last++;                          //指针加一
    return OPT_SUCCESS;
}
int DelList(SeqList *L, int i){
    if(i < 0 || i> L->last+1){
        return OPT_ERROR;           //不在范围内
    }
    int k;
    for(k = i; k < L->last; k++){
        L->elem[k] = L->elem[k+1];  //直接前移
    }
    L->last--;                      //指针减一
    return OPT_SUCCESS;
}
int UpdateList(SeqList *L,int i,ElemType e){
        if(i < 0 || i> L->last+1){
        return OPT_ERROR;           //不在范围内
    }
    L->elem[i] = e;
    return OPT_SUCCESS;
}