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 ;
}