不得不知道的实用数据结构算法（一）

新坑说开就开，就是这么随（不）心（知）所（死）欲（活），这个系列实际上是针对数据结构中的一些低时间复杂度的常用模板or思考方式的总结，ok，今天先进行的是线性表。

线性表

定义：

# include <stdio.h>
typedef ElemType int;

struct typedef SeqList
{
    ElemType  *data;  // 按道理这里应该有很多实现方法，比如直接上一个数组，通过宏定义最大数组长度
    int size;
    int capacity;
}SeqList;

# include <stdio.h>
# define MAXSIZE 100

typedef ElemType int;

struct typedef SeqList
{
    ElemType  data[MAXSIZE];
    int length;
}SeqList;

void init(SeqList *l)
{
    l->length=0;
}

秉承着不给自己找麻烦，后边就不用动态分配空间的代码了，虽然在我初学的时候觉得动态分配真的很优雅（起码不怕爆了）

OK，然后迅速的过一下基本操作以及其操作的流程以及弊端（懒得写了）：

删除：删除一个元素，要将后边的元素都移过来，实际上也就是说复杂度是O(n)

遍历：这不必多说，自然O(n)

随机存取：这是顺序表的强项

插入：和删除其实一致，但是要求后移后面的元素

然而很多算法题会颠覆你对基本操作的认识，也就是会让你优化一种插入操作or删除操作，使一个本来暴力解时间复杂度为O(n²)的算法优化为时间复杂度为O(n)的算法

我们先举个例子：

现在有一个顺序表，其中有元素n个，现在我希望删除其中的所有偶数元素

我们从直觉上很容易写出这样一个代码：

void dele_even(SeqList *l)
{
    if (l==NULL)
    {
        printf("顺序表未初始化");
        return ;
    }
    
    for (int i = 0; i < l->length; i++)
    {
        if (l->data[i]%2==0)
        {
            delete(l,i); #时间复杂度是O(n)
        }
    }
}

简单瞅一眼，很明显可以看出这是个O(n²)的时间复杂度的算法，但是有没有一种可能，这个算法可以被优化到O(n)，这就是技巧一：有效的循环合并

技巧一：有效的循环合并

我们可以分析一下刚才删除的过程，其实有一些动作是多余的，我们其实没有必要去移动一个可能会被删除的元素：当我们找到一个偶数时，实际上后边的元素中依旧可能存在偶数，那么我们将这些偶数移动到前面就是一个多余的动作，因为以后依旧要被删除，其后边的元素仍旧面临的再一次循环的境地，因此我们是不是可以通过某种手段避免无效的遍历移动呢？

void dele_even_good(SeqList *l)
{
    if (l==NULL)
    {
        printf("顺序表未初始化");
        return ;
    }

    int m=0; //用于存储找到了多少偶数

    for (int i = 0; i < l->length; i++)
    {
         if (m!=0 && i-m>0)
        {
            l->data[i-m]=l->data[i];
        }

        if (l->data[i]%2==0)
        {
            m++;
        }
    }
    l->length=l->length-m;
}