1. 线性表_顺序表

1. 定义顺序表

通过分配内存的方式，可以分为两种顺序表

(1)静态分配

//静态分配，顺序表大小固定
#define maxSize 50

typedef struct
{
    ElemType data[maxSize];
    int length;
}SqList;

(2)动态分配

typedef struct
{
    ElemType *data;
    int length;
}SqList2;

//初始化顺序表
l.data = (ElemType *) malloc(sizeof(ElemType) * initSize);

//增加顺序表长度
p = realloc(l.data,n * sizeof(ElemType));

if (p == NULL)
    exit(1);
else
{
    l.data = p;
}

2. 增加，删除，按值查找操作

增加：从最后一个元素开始，每个元素往后移动一位覆盖原有的元素，直到第 i 个位置（需要插入元素的位置）的元素往后移动了一位。然后向第i个位置插入新增元素。

bool ListInsert(SqList &L, int i, ElemType e)
{
     //表已满
    if(L.length >= maxSize)
        return false;

     //i不在顺序表范围之内
     if(i < 1 || i > L.length+1)
        return false;

    //开始移动元素
    //最开始， j 指向顺序表最后一个元素后面的空位
    //直到将第 i 个元素移动到 i+1 的位置
    for(int j = L.length; j >= i; j--)
    {
        a[j] = a[j - 1];
    }

    //由于是下标从 0 开始算，所以第 i 个位置下标是 i - 1
    L.data[i - 1] = e;
    L.length++;
    return true;
}

删除：找到第 i 位置后，从 i + 1位置的元素开始，每个元素往前移动一个位置，覆盖前一个元素，直到顺序表最后一个元素。

bool ListDelete(SqList &L, int i, int &e)
{
    if(i < 1 || i > L.length)
        return false;

    e = L.data[i - 1];

    //最开始 j 指向第 i + 1 个位置
    //每个元素往前移动一位，直到 j 指向顺序表尾
    for(int j = i; j < L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

按值查找：其实就是遍历过程中判断元素是否所找值，如果是，停止遍历，返回元素下标。

int LocateElem(SqList &L, ElemType e)
{
    int i;
    for(i = 0; i < L.length; i++)
    {
        if(L.data[i] == e)
            return i + 1;
    }
    return -1;
}

</br>

总结：

1. 顺序表本身性质：存在两个最基本变量
   （1）元素数组
   （2）顺序表长度</br>
   元素数组分为两种，一种为静态分配顺序表的数组，是为普通数组以data[i]的方式可以找到元素。
   另外一种，由于需要动态分布，因而由一个指针作为表头。找到元素方式为*(a + i)，切忌与链表混淆。顺序表与链表的本质区别在于，顺序表的内存空间是连续分配的，因而可以通过元素序号直接找到元素，时间复杂度为O(1)。

2. 操作
   增加：从最后一位元素开始往后移一位，直到要插入位置空出，然后插入新元素。
   时间复杂度：最好O(1),最坏O(n),平均O(n)</br>
   删除：从要删除元素的后一个元素开始往前移一位，直到最后一个元素移动完毕。
   时间复杂度：最好O(1),最坏O(n),平均O(n)</br>
   查找：遍历。
   时间复杂度：最好O(1),最坏O(n),平均O(n)