【数据结构】1 顺序表

行动是治愈恐惧的良药，而犹豫拖延将不断滋养恐惧。

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
上述定义是我从百度百科上直接copy过来的，我把其中重要的概念进行了加粗标记。可以看到顺序表具有的特点是：① 以数组形式存储；② 物理上和逻辑上均具有相邻关系。

在动手写代码之前，我们首先得对我们的目标有一个明确的认知，不能硬着头皮写，等到出现问题再回过头来检查，这种方法是低效的也是不对的。我们应该想清楚我们这个数据结构需要包含哪些成员；我们需要怎样设计函数；我们需要对实例进行哪些操作等等。一些更加具体的东西，我将在本次设计顺序表的过程中向大家一一展示。
首先是顺序表这个数据结构到底应该包括哪些东西。根据定义我们知道顺序表是需要借助数组实现的，因此我们得在该数据结构中包含一个数组。我们知道对于数组最重要的东西就是它的大小，有一开始就分配好内存的（静态方式），也有在使用的时候再分配内存的（动态方式），那我们究竟该选择哪一项？还是说两种方法都可以？这也是需要思考的问题。如果选择静态分配的话，我们的数据结构中就需要包含一个整型变量来记录目前表中存储了多少元素，一个确定大小的数组来存储数据。如果选择动态分配的话，我们就需要一个指针进行动态分配内存，需要一个整型变量来记录目前表中存储了多少元素，还需要一个整型变量来记录顺序表最多可以存储多少个元素。
其次是实例需要进行哪些操作。一般情况下数据结构都是需要包括：增、删、改、查、创建与销毁这几个功能的。那么对于顺序表我们还需要其它的功能吗？我想再加上一个打印最好，这样的话在每次对实例进行操作之后可以打印一下，以检查我们的操作是否正确执行。
最后是函数的设计。前面我们已经把各个模块给细分了出来，我们在实现功能的时候就需要想清楚怎么设计才能使函数能实现既定功能而又具有鲁棒性，就比如说“查”这个功能，我们是按值查找还是按位置查找？我们需要传入的是一个指针还是一个值？这都是需要进行思考的问题。总的来说我们需要考虑一个函数的输入，输出和函数体内对数据结构进行的操作。

在正式动手编写代码之前，我们最好是先写好代码框架，在代码框架中把我们需要实现的功能和需要注意的地方都用文字标注出来，这样后面自己动手写代码的时候就会很清晰。

1.导入头文件、进行宏定义
2.定义数据结构
  2.1 需要一个存储数据的数组
  2.2 需要一个变量记录数组当前的长度
3.需要对顺序表进行的操作
  3.1 增：往顺序表中插入一个元素
      - 插入元素位置判断
      - 插入之后是否需要交换元素位置
  3.2 改：修改顺序表中的一个元素
      - 给定索引是否正确
      - 是否需要返回被修改的元素
  3.3 删：从顺序表中删除指定位置的元素
      - 给定索引是否正确
      - 是否需要返回被删除的元素
  3.4 查：检查顺序表中是否存在给定值
  3.5 打印：按照一定的形式打印顺序表中的元素
  3.6 初始化设置：对新生成的顺序表进行初始化
4.在主函数中实例化对象，并调用方法以检查方法的正确性

经过上面的精心准备，相信大家对顺序表是个什么东西，它的作用是什么，需要对其进行哪些操作有了一个大概的了解。下面我们开始按照模块编写代码，这里我是按照静态分配内存的方法写的代码，按照动态分配内存的就留给大家作为训练，思路可以完全按照本篇博客来。

首先我们得导入C语言标准的输入输出库，之后定义顺序表的最大长度以及两个用来判断结果是否正确的宏，最后给数据类型起一个别名，方便后面顺序表在不同场景下的复用。

#include 
#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef int ElementType;

typedef struct SeqList {
    ElementType elem[MAXSIZE];
    int length;
} SeqList;

int InitSeqList(SeqList &L) {
    L.length = 0;
    return OK;
}

int InsertSeqList(SeqList &L, int i, ElementType data) {
    if(L.length >= MAXSIZE) {
        printf("The sequence list is full.n");
        return ERROR;
    }
    if(L.length < 0 || i > L.length + 1) {
        printf("Invalid insert location.n");
        return ERROR;
    }
    for(int j = L.length-1; j >= i-1; j--) {
        L.elem[j+1] = L.elem[j];
    }
    L.elem[i-1] = data;
    L.length += 1;
    return OK;
}

int ModifySeqList(SeqList &L, int i, ElementType data, ElementType &value) {
    if(i < 1 || i > L.length) {
        printf("Invalid modification location.n");
        return ERROR;
    }
    ElementType tmp = L.elem[i-1];
    L.elem[i-1] = data;
    value = tmp;
    return OK;
}

int DeleteSeqList(SeqList &L, int i) {
    if(i < 1 || i > L.length) {
        printf("Invalid delete location.n");
        return ERROR;
    }
    for(int j = i; j < L.length; j++) {
        L.elem[j-1] = L.elem[j];
    }
    L.length -= 1;
    return OK;
}

int LocateSeqList(SeqList &L, ElementType x) {
    int i = 0;
    while(i < L.length && L.elem[i] != x) {
        i++;
    }
    if(i >= L.length) {
        printf("Not find element in sequence listn");
        return ERROR;
    }
    return (i+1);
}

void DisplaySeqList(SeqList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d ", L.elem[i]);
    }
    printf("n");
}

int main() {
    SeqList seqList;
    InitSeqList(seqList);
    for(int i = 0; i < MAXSIZE / 2; i++) {
        InsertSeqList(seqList, 1, MAXSIZE-i);
    }
    printf("Original sequence list is:n");
    DisplaySeqList(seqList);
    printf("n");
    printf("Test delete function: ");
    printf("Try to delete 0th elementn");
    DeleteSeqList(seqList, 0);
    printf("Try to delete 5th elementn");
    DeleteSeqList(seqList, 5);
    printf("After delete 5th element: ");
    DisplaySeqList(seqList);
    printf("n");
    printf("Test insert function: ");
    printf("Try to insert 7th elementn");
    InsertSeqList(seqList, 7, 520);
    printf("After insert 7th element: ");
    DisplaySeqList(seqList);
    printf("Try to insert 13th elementn");
    InsertSeqList(seqList, 13, 520);
    DisplaySeqList(seqList);
    printf("n");
    printf("Test modify function: ");
    printf("Try to modify 8th elementn");
    ElementType data;
    ModifySeqList(seqList, 8, 521, data);
    printf("The original data of 8th is: %dn", data);
    DisplaySeqList(seqList);
    printf("n");
    printf("Test search function: ");
    int returnCode = LocateSeqList(seqList, 520);
    DisplaySeqList(seqList);
    printf("%d is the %dth elementn", 520, returnCode);
    return 0;
}

当上面的代码全部编写完成之后，我们就可以编译并运行它们了，我使用的是gnu出品的gcc(免费而且功能强大)，具体的编译指令如下.

g++ SeqList.c -o SeqList && ./SeqList

运行结果如下所示，如果大家跟我的步骤一样的话，那应该是可以得到相同的结果的，祝各位coding顺利!)