线性表的顺序存储结构及基础操作代码实现

一、 在《小白眼中的线性表（上篇）》中我们介绍了线性表的基础，及线性表的顺序存储基础知识，今天我们来看看如何用代码实现线性表的基本操作。还记得线性表的基本操作吗？

接下来，我们将一一实现。注意哦，这里的实现，是以顺序存储结构为基础进行实现的，在明天我们还会介绍线性表的链式存储结构，欢迎大家捧场。

二、代码实现

1. 线性表的初始化

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//定义状态，0表示失败，1表示成功 
typedef int Status;
#define OK 1;
#define ERROR 0; 

//线性表顺序存储结构 的代码实现 
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqList; 

//线性表的初始化操作 
Status InitList(SqList *L){
    L->length = 0;//初始化操作就是将线性表长度置为0 
    return OK; 
}

int main(int argc, char *argv[]) { 
    SqList L; 
    InitList(&L);
    printf("线性表的长度为 %d \n", L.length);
    return 0;
}

2. 线性表是否为空

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//定义状态，0表示失败，1表示成功 
typedef int Status;
#define OK 1
#define ERROR 0 
#define TRUE 1
#define FALSE 0 

//线性表顺序存储结构 的代码实现 
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqList; 

//线性表的初始化操作 
Status InitList(SqList *L){
    L->length = 0;//初始化操作就是将线性表长度置为0 
    return OK; 
}

//判断线性表是否为空
Status ListEmpty(SqList L){
    if(L.length == 0){
        return TRUE;
    }else{
        return FALSE;
    }
} 

int main(int argc, char *argv[]) { 
    SqList L; 
    InitList(&L);
    printf("线性表的长度为 %d \n", L.length);

    printf("线性表是否为空？1代表是 0代表不是 %d \n", ListEmpty(L));
    return 0;
}

在这里我想说明一下，观察以上两个操作ListEmpty(SqList L)和InitList(SqList *L)这两个方法有什么不同？看出来了吧，二者参数不同，一个是SqList这个结构体变量，一个是指向SqList的指针。为什么会出现不同的参数呢？接下来我来解释。

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct{
    int data;
    int length;
}TestStruct;

int ChangeElem(TestStruct S){
    S.data = 10;
    S.length = 666;
} 

int ChangeElem2(TestStruct *S){
    S->data = 10;
    S->length = 666;
} 

int main(int argc, char *argv[]) {
    TestStruct S;
    ChangeElem(S);
    printf("%d \n", S.data);
    printf("%d \n", S.length);

    ChangeElem2(&S);
    printf("%d \n", S.data);
    printf("%d \n", S.length);

    return 0;
}

大家知道答案了吗？以上的输出结果是什么？

由此，有没有得到启发：
用把结构体指针传到方法中，在方法中操作的其实是这个结构体本身，而把结构体变量传到方法中，在方法中操作的其实是这个结构体的复制，与这个结构体本身并没有关系。所以，总结一下，要是你想改变这个结构体本身，你就在方法中传结构体指针，如果你只是想得到这个结构体的某一项参数，你可以直接在方法中传这个结构体。
3. 在线性表指定位置插入

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//定义状态，0表示失败，1表示成功 
typedef int Status;
#define OK 1
#define ERROR 0 
#define TRUE 1
#define FALSE 0 

//线性表顺序存储结构 的代码实现 
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqList; 

//线性表的初始化操作 
Status InitList(SqList *L){
    L->length = 0;//初始化操作就是将线性表长度置为0 
    return OK; 
}

//判断线性表是否为空
Status ListEmpty(SqList L){
    if(L.length == 0){
        return TRUE;
    }else{
        return FALSE;
    }
} 

//生成线性表
Status CreateList(SqList *L){
    srand(1);
    int i;
    for(i = 0; i < 5; i++){
        L->data[i] = rand() % 100 + 1;
        L->length++;
    } 
} 

//在指定位置插入元素 
Status ListInsert(SqList *L, int i, ElemType e){
    int x;
    for(x = L->length; x >= i; x--){
        L->data[x] = L->data[x - 1];
    }
    L->data[i - 1] = e; 
    L->length++;
}

int main(int argc, char *argv[]) { 
    SqList L; 
    InitList(&L);
    printf("线性表的长度为 %d \n", L.length);

    printf("线性表是否为空？1代表是 0代表不是 %d \n", ListEmpty(L));

    CreateList(&L); 
    int i;
    printf("创建线性表的值分别为 \n");
    for(i = 0; i < L.length; i++){
        printf("%d \n", L.data[i]);
    }

    ListInsert(&L, 4, 666);
    int x;
    printf("插入值后线性表的值分别为 \n");
    for(x = 0; x < L.length; x++){
        printf("%d \n", L.data[x]);
    }

    return 0;
}

在这里，线性表的插入操作如下图

在这里，我想说明两点，第一，为什么要从后向前遍历。试想，如果从前向后遍历，前一个值要覆盖后一个值，那么后一个值就必须用一个临时变量进行存储，要不然就会造成信息丢失，而从后向前遍历则不需要定义临时变量。第二，

for(x = L->length; x >= i; x--){
        L->data[x] = L->data[x - 1];
    }

循环的边界条件为什么是这样的，拿图来说，比较容易理解。

如果我们想在线性表的第四个位置插入数据，我们必须将线性表上（注意不是数组）的4、5、6位置上的数据进行向后移位，所以我们就理解了循环变量为什么要这样写。
4. 删除指定位置的数据元素

#include <stdio.h>
#include <stdlib.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//定义状态，0表示失败，1表示成功 
typedef int Status;
#define OK 1
#define ERROR 0 
#define TRUE 1
#define FALSE 0 

//线性表顺序存储结构 的代码实现 
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int length;
}SqList; 

//线性表的初始化操作 
Status InitList(SqList *L){
    L->length = 0;//初始化操作就是将线性表长度置为0 
    return OK; 
}

//判断线性表是否为空
Status ListEmpty(SqList L){
    if(L.length == 0){
        return TRUE;
    }else{
        return FALSE;
    }
} 

//生成线性表
Status CreateList(SqList *L){
    srand(1);
    int i;
    for(i = 0; i < 5; i++){
        L->data[i] = rand() % 100 + 1;
        L->length++;
    } 
} 

//在指定位置插入元素 
Status ListInsert(SqList *L, int i, ElemType e){
    int x;
    for(x = L->length; x >= i; x--){
        L->data[x] = L->data[x - 1];
    }
    L->data[i - 1] = e; 
    L->length++;
}

//删除指定位置的元素 
Status ListDelete(SqList *L, int i, ElemType *e) {
    //为什么提前赋值，因为for循环后，这个值就被覆盖掉了 
    *e = L->data[i - 1];
    int x;
    for(x = (i + 1); x <= L->length; x++){
        L->data[x - 2] = L->data[x - 1];
    } 
    L->length--;
} 

int main(int argc, char *argv[]) { 
    SqList L; 
    InitList(&L);
    printf("线性表的长度为 %d \n", L.length);

    printf("线性表是否为空？1代表是 0代表不是 %d \n", ListEmpty(L));

    CreateList(&L); 
    int i;
    printf("创建线性表的值分别为 \n");
    for(i = 0; i < L.length; i++){
        printf("%d \n", L.data[i]);
    }

    ListInsert(&L, 4, 666);
    int x;
    printf("插入值后线性表的值分别为 \n");
    for(x = 0; x < L.length; x++){
        printf("%d \n", L.data[x]);
    }

    ElemType e; 
    ListDelete(&L, 3, &e);
    int y;
    printf("删除值后线性表的值分别为 \n");
    for(y = 0; y < L.length; y++){
        printf("%d \n", L.data[y]);
    }
    printf("删除的值为 %d \n", e);
    return 0;
}

这就是线性表的基本操作，当然只有一部分，明天我将补充其他基本操作。希望各位小白同学（包括我）都能好好坚持，学好数据结构，如有问题，欢迎加微信（18813068112）进行交流，谢谢大家批评指正