1.定义

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10     // 顺序表最大长度
#define InitSize 100   // 初始表长
typedef int ElemType;  // 假设存储int类型数据

1.1 静态顺序表定义

由于数字大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

typedef struct
{
    ElemType data[MaxSize];    //用静态的“数组”存放数据元素
    int length;                // 链表当前长度
}SqList;

1.2动态顺序表定义

存储数组的空间在程序执行过程中通过动态存储分配语句分配，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的。

typedef struct 
{
    ElemType* data;     // 指针
    int maxSize;        // 顺序表最大长度
    int length;         // 顺序表当前长度
}SeqList;

2.初始化

2.2静态顺序表

// 初始化静态顺序表
void initSqList(SqList& L) 
{
    for(int i = 0; i < MaxSize; i++)
        L.data[i] = 0;    // 初始化为默认值0
    L.length = 0;            // 长度为0
}

动态顺序表

void initSqList(SeqList& L)
{
    // malloc 函数申请一片连续空间
    L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

// 增加动态数组长度, len: 动态增量
void increaseSqListSize(SeqList& L, int len)
{
    ElemType* p = L.data;
    L.data = (ElemType*)malloc((L.maxSize+ len) * sizeof(ElemType));
    for(int i = 0; i < L.length; i++)
        L.data[i] = p[i];         // 将数据赋值到新区域, 时间开销较大
    L.maxSize= L.maxSize+ len;    // 链表最大长度增加 len
    free(p);
}

3.插入

若表满，则可以返回插入失败或增加表扩容

// 注意，i表示位序，从1开始，数组下标从0开始
bool increaseSqListSize(SqList& L, int i, ElemType e)
{
    if(i < 1 || i > L.length + 1)    // 判断i的范围是否有效
        return false;
    if(L.length >= MaxSize)         // 当存储空间已满，不能插入
        return false;
    for(int j = L.length; j >= i; j--)  // 元素后移
        L.data[j] = L.data[j - 1];    // **********
    L.data[i-1] = e;
    L.length++;
    return true;
}

平均次数定义

在长度为n的线性表中，插入一个元素时所需要移动的次数的期望值，即为插入时移动元素的平均次数。

事件概率问题，

数据为n个，“在第i个位置插入需要移动元素的次数”为事件P(i)，则每个事件的概率表示如下：

地址	0	1	2	...	i-1	...	n-1	n
事件	P(1)	P(2)	P(3)	...	P(i)	...	P(n)	P(n+1)
概率	p1	p2	p3	...	pi	...	pn	pn+1
次数	n	n-1	n-2	...	n-i+1	...	1	0

移动平均次数：(p1*n+p2*(n-1)+p3*(n-2)+...+pi*(n-i+1)+...+pn*1+p{n+1}*0)/(n+1)

假设每个位置发生插入操作的概率相同，pi=1/(n+1)，则：

移动平均次数 = 1/(n+1)*(n+....+1)=1/(n+1)*[n(n+1)/2]=n/2

4.删除

// 注意，i表示位序，从1开始，数组下标从0开始
bool deleteElemSqList(SqList& L, int i, ElemType& e)
{
    if(i < 1 || i > L.length)      // 判断i的范围是否有效
        return false;
    e = L.data[i-1];
    for(int j = i; j < L.length; j++)  // 元素前移
    {
        L.data[j-1] = L.data[j];    
    }
    L.length--;
    return true;    
}

5. 删除最小元素

从顺序表中删除最小元素，空出的位置由最后一个元素填补

bool deleteMinElemSqList(SqList& L)
{
    int minElem = L.data[0];
    int minElemIdx = 0;
    for (int idx = 1; idx < L.length; idx++)
    {
        if (L.data[idx] < minElem)
        {
            minElem = L.data[idx];
            minElemIdx = idx;
        }
    }
    L.data[minElemIdx] = L.data[L.length - 1];
    L.length--;
    return true;
}

6.过滤法

在无序表中删除值在s和t之间的所有元素。

分析

访问一个，然后通过后面元素往前移来执行删除，这样时间复杂度太高；
开创一个临时空间，将满足要求的元素放入，不满足要求的过滤，这样空间复杂度太高；
过滤后的元素集合是原元素集合的子集，即过滤后的元素集合不会占用未访问元素的集合，不会发生数据覆盖，从而可以在原有空间山进行过滤操作。

代码

bool deleteFilterElem(SqList& L, int minValue, int maxValue)
{
    int curLength = 0;
    for (int i = 0; i < L.length; i++)
    {
        // [s, t]范围外的元素操作
        if (L.data[i] < minValue || L.data[i] > maxValue)
        {
            L.data[curLength++] = L.data[i];
        }
    }
    L.length = curLength;
    return true;
}

7.偏移法

在非递减顺序表中删除值在区间[s, t]的所有元素

递增：前驱永远小于后继
非递减：前驱永远小于等于后继
递减：前驱永远大于后继
非递增：前驱永远大于等于后继

分析

可以从头到尾扫描表中元素，访问元素时进行过滤。
s和t索引之间的元素没有必要去访问，这些元素必然大于等于s且小于等于t。
t索引后序的元素要依次往前移动 $idx=idx_t-idx_s+1$ 个存储单元来实现删除操作。

总结： 在一个表中，不能明确那几个位置要删除，则使用过滤法；如果能明确删除位置，则使用偏移法。

代码

bool deleteOffsetElem(SqList& L, int s, int t)
{
    int sIdx = -1;  // s索引
    int tIdx = -1;  // t索引
    // 从前往后找第一个大于等于s的元素位置
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] >= s && L.data[i] <= t)
        {
            sIdx = i;   // 删除位置
            break;
        }
    }
    // 从后往前找第一个小于等于t的元素位置
    for (int i = L.length - 1; i >= 0; i--)
    {
        if (L.data[i] <= t && L.data[i] >= s)
        {
            tIdx = i;
            break;
        }
    }
    // 移动覆盖实现删除操作，偏移长度：t - s + 1
    if (sIdx == -1 || tIdx == -1)
        return false;
    int delta = tIdx - sIdx + 1;
    for (int i = t + 1; i < L.length; i++)
    {
        L.data[i - delta] = L.data[i];
    }
    // 更新表长
    L.length = L.length - delta;
    return true;
}

8.删除重复元素

删除非递减顺序表L中的重复元素。

分析

使用过滤法，然后删除；
过滤条件：只要当前访问元素与信标末尾的元素不同，就可说明当前元素是非重复的，可以在新表尾追加。

算法思想

从前往后依次访问顺序表L中的每个元素，
如果当前访问元素与新表表尾元素不同，则将其追加到新表表尾；
重复上述步骤。

代码

void deleteRepeatElem(SqList& L)
{
    int curLength = 0;
    for (int i = 0; i < L.length; i++)
    {
        // curLength 指向待插入的空白单元
        // 比较时需要前移
        if (curLength == 0 || L.data[i] != L.data[curLength - 1])
        {
            L.data[curLength] = L.data[i];
            curLength++;
        } 
    }
    L.length = curLength;
}