02 数据结构与算法之顺序表(带自动扩容功能）（C语言实现）

#include 
#include 
#include 

typedef struct Vector {
    int *data;
    int size, capacity;
} Vector;

Vector *init_vec(int n) {
    Vector *vec = (Vector *)malloc(sizeof(Vector));
    vec->data = (int *)malloc(sizeof(int) * n);
    vec->size = 0;
    vec->capacity = n;
     return vec;
}

void clear_vec(Vector *vec) {
    if (vec == NULL) return ;
    free(vec->data);
    free(vec);
    return ;
}

int expand(Vector *vec) {

    return 1;
}

int insert(Vector *vec, int ind, int val) {
    if (vec == NULL) return 0;
    if (ind < 0 || ind > vec->size) return 0;
    if (vec->size == vec->capacity) {
        //if (!expand(Vector *vec)) printf("Failed to expand!n");
        return 0;
    }
    for (int i = vec->size; ind < i ; i--) {
        vec->data[i] = vec->data[i - 1];
    }
    vec->data[ind] = val;
    vec->size++;
    return 1;
}

int erase(Vector *vec, int ind) {
    if (vec == NULL) return 0;
    if (ind < 0 || ind >= vec->size) return 0;
    for (int i = ind; i <= vec->size; i++) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->size--;
    return 1;
}

void output(Vector *vec) {
    if (vec == NULL) return ;
    printf("Vector(%d): [", vec->size);
    for (int i = 0; i < vec->size; i++) {
        i && printf(",");
        printf("%d", vec->data[i]);
    }
    printf("]n");
}
int main() {
    #define MAX_N 20

    Vector *v = init_vec(MAX_N);
    srand(time(0));
    for (int i = 0; i < MAX_N; i++) {
        int op = rand() % 4;
        int ind = rand() % (v->size + 3) - 1;
        int val = rand() % 100;
        switch(op) {
            case 0:
            case 1:
            case 2: {
                printf(" insert %d at %d to Vector = %dn", val, ind, insert(v, ind, val));
            } break;
            case 3: {
                printf("erase %d from Vector = %dn", ind, erase(v, ind));
            } break;      
        }
        output(v);
    }
    clear_vec(v);

    #undef MAX_N
    return 0;
}

② 存储整型数据的顺序表(带扩容功能)

#include 
#include 
#include 

#define COLOR(a, b, c) "33[" #b ";" #c "m" a "33[0m"
//将内容a设定b字体颜色、c特效输出，0m关闭所有属性
#define GREEN(a) COLOR(a, 32, 4) 
#define RED(a) COLOR(a, 31, 4)

typedef struct Vector {
    int *data;
    int size, capacity;
} Vector;

Vector *init_vec(int n) {
    Vector *vec = (Vector *)malloc(sizeof(Vector));
    vec->data = (int *)malloc(sizeof(int) * n);
    vec->size = 0;
    vec->capacity = n;
     return vec;
}

void clear_vec(Vector *vec) {
    if (vec == NULL) return ;
    free(vec->data);
    free(vec);
    return ;
}

int expand(Vector *v){//malloc 申请的内存不一定为0，calloc会清空所申请内存为0。realloc重新申请内存(1、直接在原内存后面申请。2、重新申请一片连续的内存空间，将元数据拷贝过去并自动释放原空间。3、申请空间不足、申请失败，返回NULL),申请成功返回首地址值，申请不成功返回NULL，所以用realloc申请内存需做保护措施。
    int extr_size = v->capacity;
    int *p;
    while(extr_size){
        p = (int *)realloc(v->data, sizeof(int) * (v->capacity + extr_size));
        if(p) break;
        extr_size >>= 1;
    }
    if(p == NULL ){
        printf(RED("fail to expand!n"));
        return 0;
    }
    v->capacity += extr_size;
    v->data = p;
    //v->data = (Type *)realloc(v->data, sizeof(int) * (v->size + extr_size));
    //v->size += extr_size;
    printf(GREEN("success to expand! the new size = %dn"), v->size);
    return 1;
}

int insert(Vector *vec, int ind, int val) {
    if (vec == NULL) return 0;
    if (ind < 0 || ind > vec->size) return 0;
    if (vec->size == vec->capacity) {
        if (!expand(vec)) return 0;
    }
    for (int i = vec->size; ind < i ; i--) {
        vec->data[i] = vec->data[i - 1];
    }
    vec->data[ind] = val;
    vec->size++;
    return 1;
}

int erase(Vector *vec, int ind) {
    if (vec == NULL) return 0;
    if (ind < 0 || ind >= vec->size) return 0;
    for (int i = ind; i <= vec->size; i++) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->size--;
    return 1;
}

void output(Vector *vec) {
    if (vec == NULL) return ;
    printf("Vector(%d): [", vec->size);
    for (int i = 0; i < vec->size; i++) {
        i && printf(",");
        printf("%d", vec->data[i]);
    }
    printf("]n");
}
int main() {
    #define MAX_N 20

    Vector *v = init_vec(1);
    srand(time(0));
    for (int i = 0; i < MAX_N; i++) {
        int op = rand() % 4;
        int ind = rand() % (v->size + 3) - 1;
        int val = rand() % 100;
        switch(op) {
            case 0:
            case 1:
            case 2: {
                printf(" insert %d at %d to Vector = %dn", val, ind, insert(v, ind, val));
            } break;
            case 3: {
                printf("erase %d from Vector = %dn", ind, erase(v, ind));
            } break;      
        }
        output(v);
    }
    clear_vec(v);

    #undef MAX_N
    return 0;
}

③ 存储通用数据的顺序表(带扩容功能)

#include 
#include 
#include 

#define TYPE_STR(a) _Generic((a), 
    int : "%d",
    double : "%lf", 
    char : "%c",
    char * : "%s"
)

#define COLOR(a, b, c) "33[" #b ";" #c "m" a "33[0m"
//将内容a以设定的背景、b字体颜色、c特效输出，0m关闭所有属性
#define GREEN(a) COLOR(a, 32, 4) 
#define RED(a) COLOR(a, 31, 4)

typedef char Type;
typedef struct Vector {
    Type *data;
    int length, size;
} Vec;

Vec *init(int n) {
    Vec *v = (Vec *)malloc(sizeof(Vec));
    v->data = (Type *)malloc(sizeof(Type) * n);
    v->size = n;
    v->length = 0;
    return v;
}

int expand(Vec *v) {
    int extr_size = v->size;
    Type *p;
    while (extr_size) {
        p = (Type *)realloc(v->data, sizeof(Type) * (v->size + extr_size));
        if (p) break;//判断申请空间是否成功，不成功减半申请
        extr_size >>= 1;
    }
    if (p == NULL) {
        printf(RED("fail to expand!n"));
        return 0;
    }
    v->size += extr_size;
    v->data = p;
    printf(GREEN("success to expand! the new size = %dn"), v->size);
    return 1;
}

int insert(Vec *v, int ind, Type val) {
    if (v == NULL) return 0;
    if (ind < 0 || ind > v->length) return 0;
    if (v->length == v->size) {
        if (!expand(v)) return 0;
    }
    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(Vec *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(Vec *v) {
    if (v == NULL) return ;
    printf("Vector : [");
    for (int i = 0; i < v->length; i++) {
        i && printf(",");
        printf(TYPE_STR(v->data[i]), v->data[i]);
    }
    printf("]n");
    return ;
}

void clear(Vec *v) {
    if (v == NULL) return ;
    free(v->data);
    free(v);
    return ;
}

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 + 2) - 1;
        char val = rand() % 26 + 'a';
        switch (op) {
            case 2:
            case 1:
            case 0: {
                printf("insert %c at %d = %dn", val, ind, insert(v, ind, val));
            } break;
            case 3: {
                printf("erase a item at %d = %dn", ind, erase(v, ind));
            } break;
        }
        output(v), printf("n");
    }
    clear(v);
    #undef MAX_N
    return 0;
}