数据结构初阶：顺序表、链表与时间空间复杂度

时间复杂度和空间复杂度

理论部分

时间复杂度和空间复杂度的计算遵循大 O 表示法，通常按最坏情况计算。

大 O 表示法规则：

1. 用常数 1 取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是 1，则去除与这个项目相乘的常数。得到的结果就是大 O 阶。

习题部分

注意循环执行次数，某些看似 n 次的循环实际未执行到 n 次。

题目：移除元素 原地移除，将不变元素移到前面。遇到不等于 val 的元素时，移到第 k 个位置即可。

int removeElement(vector<int>& nums, int val) {
    int k = 0;
    int n = nums.size();
    for(int i = 0; i < n; i++) {
        if(nums[i] != val) nums[k++] = nums[i];
    }
    return k;
}

顺序表和链表

理论部分

链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同。顺序表比链表唯一好的地方就是找下标为多少的位置好，其他都是链表好些。

顺序表跟数组非常相似，几乎可以说是一模一样。链表的话有用数组模拟的，还有用结构体去模拟的，一般来说，在竞赛方面，一般都是用数组去模拟，在工程方面的话，一般是动态去用结构体去模拟。

顺序表的动态模拟

typedef int SLDataType;
typedef struct SeqList {
    SLDataType* a;
    int size; // 有效数据个数
    int capacity; // 空间容量
} SL;

void SLInit(SL* ps) {
    assert(ps);
    ps->a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);
    if (ps->a == NULL) {
        perror("malloc fail");
        ;
    }
    ps->size = ;
    ps->capacity = INIT_CAPACITY;
}

{
    (ps);
    (ps->a);
    ps->a = ;
    ps->capacity = ps->size = ;
}

{
    (ps);
     ( i = ; i < ps->size; ++i) {
        (, ps->a[i]);
    }
    ();
}

{
    (ps);
     (ps->size == ps->capacity) {
        SLDataType* tmp = (SLDataType*)(ps->a, (SLDataType) * ps->capacity * );
         (tmp == ) {
            ();
            ;
        }
        ps->a = tmp;
        ps->capacity *= ;
    }
}

{
    (ps);
    (pos >=  && pos <= ps->size);
    (ps);
     end = ps->size - ;
     (end >= pos) {
        ps->a[end + ] = ps->a[end];
        --end;
    }
    ps->a[pos] = x;
    ps->size++;
}

{
    (ps);
    (pos >=  && pos < ps->size);
     begin = pos + ;
     (begin < ps->size) {
        ps->a[begin - ] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

{
    (ps);
    ( i = ; i < ps->size; ++i) {
         (ps->a[i] == x) {
             i;
        }
    }
     ;
}