——-更高级的数组

功能：用于存放任意类型的数据；每个位置存储的数据的数据类型相同。
逻辑关系：用一组地址连续的存储单元依次存储线性表的数据元素，每个数据元素的存储位置都和线性表的起始位置相差一个偏移量；
特点：
- 线性表中第一个数据元素的存储位置，通常称为线性表的起始位置或基地址；
- 只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以顺序表是一种可以随机存取的存储结构。
- 访问每个元素所花时间相等；
- 逻辑结构与存储结构一致。
优点：
- 存储密度大；
- 可随机存取表中任一元素；
缺点：
- 在插入、删除某元素时，需要移动大量元素；
- 浪费存储空间；
- 属于静态存储形式，数据元素的个数不能自由扩充

顺序表的类型定义

#define MAXSIZE 100 //最大长度
typedef struct { //数据结构的存储结构类型定义通过typedef描述
  ElemType *elem;  //指向数据元素的基地址
  int lenth;       //线性表的当前长度
}SqList;

初始化顺序表L

顺序表的结构

size表示顺序表的空间容量
length表示当前已知元素的长度或个数
data用于存放数据的首地址

结构操作
- 插入元素
插入元素6

先把位置2及之后的元素向后移动，再插入。

删除元素

代码实现 ```c
include
include
include

define COLOR(a, b) “\033[“ #b “m” a “\033[0m”

define GREEN(a) COLOR(a, 32)

//顺序表的结构定义 typedef struct Vector { int *data; //存放数据的内存空间的首地址 int size, length;//size：顺序表的空间大小（可以存储的元素数量）；length：已存入元素的个数 } Vector;

//顺序表的初始化 Vector init(int n) { Vector v = (Vector )malloc(sizeof(Vector));//在内存创建一片空间存放一个顺序表 v->data = (int )malloc(sizeof(int) * n);//在内存中开辟一片空间存放顺序表要存储的数据 v->size = n; v->length = 0; return v; }

//顺序表的扩容 int expand(Vector v) { int extr_size = v->size;//要扩大的大小 int p; //用来接收扩大后空间的首地址 while (extr_size) { p = (int )realloc(v->data, sizeof(int) (v->size + extr_size));//定位到要扩大的空间的位置，实质上是另外开辟了一段空间，并把原来的数据存入，返回新的空间的地址 if (p != NULL) break;//判断扩容是否成功 extr_size >>= 1; //如果扩容失败，可能是内存不够，所以减少扩大的量 } if (p == NULL) return 0; v->data = p; //把扩大后空间的首地址传给顺序表 v->size += extr_size; return 1; }

//数据插入操作 int insert(Vector *v, int ind, int val) { if (v == NULL) return 0; if (v->length == v->size) { //如果存入的数据已满，无法再插入，需要扩容 if (!expand(v)) return 0; printf(GREEN(“success to expand! the size = %d\n”), v->size); } if (ind < 0 || ind > v->length) return 0; //插入的位置不在给定范围内，无法插入；元素下标从0开始，第length位此时为空 for (int i = v->length; i > ind; i—) {//把顺序表中要插入位置及后面的元素向后挪动一位，让新元素插入 v->data[i] = v->data[i - 1]; } v->data[ind] = val; v->length += 1; return 1; }

//数据清除操作 int erase(Vector *v, int ind) { if (v == NULL) return 0; if (ind < 0 || ind >= v->length) return 0;//删除的位置不在给定范围内，无法删除 for (int i = ind + 1; i < v->length; i++) { //把顺序表中要删除的元素的后面的元素向前挪动一位 v->data[i - 1] = v->data[i]; } v->length -= 1; return 1; }

//顺序表输出 void output(Vector *v) { if (v == NULL) return ; printf(“Vector : [“); for (int i = 0; i < v->length; i++) { i && printf(“ “); printf(“%d”, v->data[i]); } printf(“]\n”); return ; }

//顺序表的清空 void clear(Vector *v) { if (v == NULL) return ; free(v->data); free(v); return ; }

int main() { srand(time(0));

#define MAX_OP 20
Vector *v = init(1);
for (int i = 0; i < MAX_OP; i++) {
    int op = rand() % 4;
    int val = rand() % 100;
    int ind = rand() % (v->length + 3) - 1;
    switch (op) {
        case 0:
        case 1:
        case 2: {
            printf("insert %d at %d to Vector = %d\n", val, ind, insert(v, ind, val));
        } break;
        case 3: {
            printf("erase a item at %d from Vector = %d\n", ind, erase(v, ind));
        } break;
    }
    output(v), printf("\n");
}
#undef MAX_OP
clear(v);
return 0;

} ```

malloc 申请空间；
calloc 申请空间并初始化；
realloc 重新分配空间，会主动释放原来空间里的内容；开辟失败时会返回空地址，原来的空间不会被清空；
```
              都返回开辟空间的首地址
```

编程基础

B.2顺序表

include

include

include

define COLOR(a, b) “\033[“ #b “m” a “\033[0m”

define GREEN(a) COLOR(a, 32)