1. 线性表的定义

一个线性表是n个具有相应特性的数据元素有限序列，线性表是最基本最简单的一种常用数据结构。线性表种的数据元素之间的关系是一对一的。第一个元素没有前驱最后一个元素没有后继，其他元素都是首尾相接的。注：（循环链表除外）

• 存在唯一的第一个元素
• 存在唯一的最后一个元素
• 出了第一个都有前驱
• 除了最后一个都有后继

2. 线性表的顺序表现与实现

2.1 前期准备

// 定义一些辅助元素
#define MAXSize 100 // 初始大小
#define OK 1        // ok
#define ERROR       // 错误
#define TRUE 1      // true
#define FALSE 0     // false

/// 数据类型
typedef int ElemType;
/// 函数的返回类型，其值是当前函数的执行状态，类似于OK error等
typedef int Status;

//顺序表结构设计
typedef struct {
    ElemType *data; //数据
    int length;     //长度
}sqList;

2.2 初始化

注： 线性表顺序存储的初始化，以下都称之为顺序表，本文所有的位置都是从1开始而不是0。

// 线性表顺序存储的初始化
Status InitLinkList(SqList *L) {
    // 初始化一个MAXSize大小的数组空间
    L->data = malloc(sizeof(ElemType) * MAXSize);
    if (L->data == NULL) {//初始化失败
        return ERROR;
    }
    L->length = 0;
    return OK;
}

验证初始化

    Status rStatus;
    SqList L;
    // 初始化
    rStatus = InitLinkListI(&L);
    printf("线性表初始化的结果是：%d\n", rStatus);

打印结果是： 线性表初始化的结果是：1

2.3 插入元素到指定位置

思考： 插入一个新的元素，需要知道插入的顺序表、位置、元素，所以我们需要这三个参数。

一些逻辑上的判断来进行容错处理：

• 如果顺序表为NULL则说明没有初始化，不进行操作，直接报错
• 如果插入的位置非法，小于起始位置、大于最大位置、大于当前长度加一
• 表满了也不在进行插入

插入算法：

• 核心是插入时应该将插入位置的值修改为要插入的新值
• 但是插入位置小于当前的长度则需要把当前位置及以后的元素后移

代码实现：

Status InsertElemToList(SqList *L,int i,ElemType e){
    // 顺序表为NULL直接报错
    if (L==NULL) return ERROR;
    // 插入位置大约顺序表大小或者小于1报错
    if (i>MAXSize||i<1) return ERROR;
    // 表已满
    if (L->length == MAXSize) return ERROR;
    // 最长不能超过队尾加1
    if (i>L->length+1) { return ERROR; }
    // 小于length，移出前面的元素，空出位置
    if (i<L->length) {
        for (int j = L->length; j>=i; j--) {
            L->data[j+1] = L->data[j];
        }
    }
    
    L->data[i] = e;
    ++L->length;
    
    return OK;
}

2.4 删除指定位置的元素

思考：删除一个元素需要知道删除的顺序表和位置，所以函数设计需要两个参数。

一些逻辑上的判断来进行容错处理：

• 如果顺序表为NULL则说明没有初始化，直接报错
• 如果没有元素（表为空）则报错
• 表删除位置不合法，小于起始值，大于长度

删除算法：

• 核心是删除要删除位置的值
• 在顺序表中只要覆盖当前位置的值即可
• 删除后（覆盖）将length-1即达到了删除的目的

代码实现：

/// 删除指定位置的元素
/// @param L 顺序表
/// @param location 位置
Status DeleteList(SqList *L, int location) {
    // 为空则报错
    if (L==NULL) { return ERROR; }
    // 无元素报错
    if (L->length<1) { return ERROR; }
    // 位置不合法报错
    if (location<1||location>L->length) {return ERROR;}
    // 把要删除位置之后的元素往前移动
    for (int i = location; i<=L->length; i++) {
        L->data[i] = L->data[i+1];
    }
    // 长度减一
    L->length--;
    
    return OK;
}

2.5 清空顺序表

• 因为是顺序表，清空就是将其长度置为0
• 清空不等于销毁（free）顺序表初始化的时候就分配了固定大小的内存，除非不在使用，否则不需要销毁。
  实现代码：

/// 清空顺序表
Status ClearList(SqList *L){
    L->length = 0;
    return OK;
}

2.6 获取指定位置的元素

获取元素可以使用返回的方式，这里使用的是修改参数来实现。

• 判断位置是否合法，大于最大位置、小于最小位置，大于当前长度都不合法
  实现代码：

/// 获取指定位置的元素
/// @param L 书序表
/// @param i 位置
/// @param e 获取到的值
Status GetElemForList(SqList L, int i, ElemType *e){
    //位置不合法
    if (i>MAXSize || i>L.length || i<1) {
        return ERROR;
    }
    *e = L.data[i];
    return OK;
}

2.7 获取指定元素的第一个位置

此处使用返回值得方法获取元素的位置，如果没有该元素则返回0
实现算法：

• 定义默认值j作为初始化的返回值
• 当遍历找到元素后记录下位置跳出循环
• 返回位置

/// 获取某个元素的第一个位置
/// @param L 书序表
/// @param e 元素
int GetLocationForList(SqList L, ElemType e) {
    int j = 0;
    if (L.length < 1) { return j; }
    // 遍历查找
    for (int i = 1; i<=L.length; i++) {
        if (L.data[i] == e) {
            j = i;
            break;
        }
    }
    return j;
}

2.8 顺序输出顺序表

/// 顺序输出顺序表
Status TraverseList(SqList L){
    // 没有值，不打印
    if (L.length<1) { return ERROR; }
    
    for (int i = 1; i<=L.length; i++) {
        printf("第%d个位置的元素是%d\n",i,L.data[i]);
    }
    return OK;
}

3. 测试代码

int main(int argc, const char * argv[]) {
    // insert code here...
//    printf("Hello, World!\n");
    
    Status rStatus;
    SqList L;
    int location,elem;
    ElemType e;
    
    rStatus = InitLinkList(&L);
    printf("顺序表初始化的结果是：%d\n", rStatus);
    
    for (int i = 1; i<=5; i++) {
        rStatus = InsertElemToList(&L, i, i);
        printf("插入的结果是：%d\n", rStatus);
    }
    
    printf("顺序表的长度是：%d\n",L.length);
    
    
//    printf("请输入要插入的位置和元素，用空格分开：");
//    scanf("%d %d",&location,&elem);
//    rStatus = InsertElemToList(&L, location, elem);
//    printf("插入的结果是：%d\n", rStatus);
//    printf("顺序表的长度是：%d\n",L.length);

//    printf("请输入要取值的位置：");
//    scanf("%d",&location);
//    rStatus = GetElemForList(L, location, &e);
//    printf("获取到的值是：%d\n",e);
    
    rStatus = TraverseList(L);
    printf("顺序输出的结果是：%d\n",rStatus);
    
//    int l = GetLocationForList(L, 3);
//    printf("该元素的位置是：%d\n", l);
    
    printf("请输入要删除的位置：");
    scanf("%d",&location);
    rStatus = DeleteList(&L, location);
    
    rStatus = TraverseList(L);
    printf("顺序输出的结果是：%d\n",rStatus);

    return 0;
}