1 顺序表
1 顺序表
核心公式：
程序 = 算法 + 数据结构
程序设计 = 算法 + 数据结构 + 编程范式
数据结构 = 结构定义 + 结构操作
1定义
顺序表是一种线性表数据结构，即线性结构；它用一段连续的内存空间 来存储一组具有相同类型 的数据。
-
线性表（Linear List）：顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其中，顺序表、链表、队列、栈等都是线性表结构。
-
非线性表：是与线性表相对的概念，如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
2 性质
1. 高效的随机访问
-
由于顺序表具有连续的内存空间和相同类型数据，故支持“随机访问”；
-
由于顺序表具有连续的内存空间，故其下标从“0”开始；寻址公式: data[i] = base_address + i * sizeof(data_type), base_address 为存储空间的首地址。
-
注：随机访问 != 查找O(1) ，因为二分查找的复杂度为O(logn)；但是，按照数组索引方式访问数据，其复杂度为O(1) ；
-
由于要保证物理内存的连续性，所以对于顺序表的“插入”和“删除”操作效率非常低，因为需要移动大量的数据元素。
2. 低效的插入与删除
-
假设顺序表的长度为 n，现在，如果我们需要将一个数据插入到顺序表中的第 k 个位置。为了 把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一 位；
-
如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1) ；
-
但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n) ；
-
因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 (1+2+ …n)/n=O(n) ；
-
跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要将k~n这部分的元素都顺序的前移一位；
-
优化方法：建议“插入”和“删除”操作顺序表中的最后一位元素；
1. 插入操作
2. 删除操作
3. 动态扩容(realloc)
-
因为顺序表本身在定义时，需要预先指定空间大小，因为需要分配连续的内存空间；当顺序表的预定义的存储空间使用完毕后，此时再“插入”元素时，就需要申请一块更大的存储空间，一般建议是预定义空间大小的2倍；
-
注：因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以， 如果事先能确定需要存储的数据大小，最好在创建 顺序表 的时候事先指定数据大小；
3代码演示
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define GREEN(a) COLOR(a, 32)
#define RED(a) COLOR(a, 31)
typedef struct Vector {
int *data; // 指向一片连续的存储空间
int size, length; // size：顺序表的最大容量，length：当前顺序表中数据元素的个数
} Vec;
Vec *init(int); // 初始化，生成一片连续的存储空间
int insert(Vec *, int, int); // 插入，成功：1，失败：0
int erase(Vec *, int); // 删除，成功：1，失败：0
void clear(Vec *); // 清空
void output(Vec *); // 遍历
int main() {
#define MAX_N 20
Vec * v = init(1);
srand(time(0));
for (int i = 0; i < MAX_N; i++) {
int op = rand() % 4;
int ind = rand() % (v->length + 3) - 1; // ind 的取值范围：[-1, v->length + 1]
int val = rand() % 100;
switch (op) {
case 0:
case 1:
case 2: {
printf("insert %d at %d to the Vector = %d\n", val, ind, insert(v, ind, val));
} break;
case 3: {
printf("erase an item at %d from the Vector = %d\n", ind, erase(v, ind));
} break;
}
output(v), printf("\n");
}
#undef MAX_N
clear(v);
return 0;
}
Vec *init(int n) {
Vec *v = (Vec *)malloc(sizeof(Vec));
v->data = (int *)malloc(sizeof(int) * n);
v->size = n;
v->length = 0;
return v;
}
// 动态申请空间的方式：malloc、calloc、realloc
// calloc 相对于 malloc 而言，所申请的空间清零
// realloc 重新申请空间 void *realloc(void *ptr, size_t new_size);
// 1 扩张ptr所指向的已存在内存
// 2 分配一个大小为 new_size 字节的新内存块，并将ptr指向的数据拷贝到新内存中，然后释放ptr指向的数据
// 3 分配失败（没有足够的内存），返回NULL，但ptr指向的内存并未释放
int expand(Vec *v) {
// 顺序表的动态扩容，一般扩容为原空间的2倍
int extr_size = v->size;
int *p;
// 通过动态的减小extr_size值，来提高扩容的可能性
while (extr_size) {
p = (int *)realloc(v->data, sizeof(int) * (extr_size + v->size));
if (p != NULL) break;
extr_size >>= 1;
}
// 扩容失败（没有足够的内存）
if (p == NULL) return 0;
v->size += extr_size;
v->data = p;
return 1;
}
int insert(Vec *v, int ind, int val) {
// 判断顺序表是否存在
if (v == NULL) return 0;
// 1 位置合法性判断，顺序表必须在[0, v->length]的范围内插入元素
if (ind < 0 || ind > v->length) return 0;
// 2 当前顺序表中数据元素是否达到容量上限（size），以此来判断是否需要扩容处理
if (v->length == v->size) {
if (!expand(v)) {
printf(RED("fail to expand!\n"));
}
printf(GREEN("success to expand! the size = %d\n"), v->size);
}
// 3 将ind后的每一个元素后移（包括ind位置的元素）
for (int i = v->length; i > ind; i--) {
v->data[i] = v->data[i - 1];
}
// 4 在指定位置插入元素，同时顺序表中的数据元素个数加一
v->data[ind] = val;
v->length += 1;
return 1;
}
int erase(Vec *v, int ind) {
if (v == NULL) return 0;
// 1 位置合法性判断，此处必须有等号，因为元素下标是从0开始的
// 2 此处，隐式包含了顺序表的判空操作
if (ind < 0 || ind >= v->length) return 0;
// 3 将ind后的每个元素依次向前移动
for (int i = ind + 1; i < v->length; i++) {
v->data[i - 1] = v->data[i];
}
// 4 数据元素的个数减一
v->length -= 1;
return 1;
}
void clear(Vec *v) {
if (v == NULL) return ;
free(v->data);
free(v);
return ;
}
void output(Vec *v) {
if (v == NULL) return ;
printf("[");
for (int i = 0; i < v->length; i++) {
i && printf(", ");
printf("%d", v->data[i]);
}
printf("]\n");
return ;
}
