顺序表

顺序表

• 程序 = 算法 + 数据结构

• 数据结构 = 结构定义 + 结构操作

• 顺序表是线性表

• 线性表的元素是1对1的关系

• 线性表也称为动态数组，可以动态扩容

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.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; //容量 
    int length; //  长度 
} Vec;


// 结构操作

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

int expand(Vec *v) {
    //顺序表的扩容操作
    //malloc动态申请空间不一定干净的，也就是这块空间不一定都为0； 
    //calloc动态申请空间并且清空为0值
    //realloc 重新申请空间
    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->size += extr_size;
    v->data = p;
    printf("扩容成功， v->size = %d\n", v->size);
    return 1; 
} 

//插入成功返回1，否则返回0 
int insert(Vec *v, int ind, int val) { //插入元素
    // ind 表示插入位置，vla表示插入的元素 
    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 (v->length <= ind || ind < 0) 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("[");
    for (int i = 0; i < v->length; i++) {
        i && printf(", ");
        printf("%d", 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 1
    Vec *v = init(MAX_N);
    srand(time(0));
    // 测试
    for (int i = 0; i < 20 * MAX_N; i++) {
        //生成数据
        // rand()头文件stdlib.h
        int op = rand() % 4;
        int ind = rand() % (v->length + 3) - 1; //范围[-1, v->length + 1] ,使测试数据全面
        int val = rand() % 100;
        switch (op) {
            case 2 :
            case 3 :
            case 0 : 
            case 1 : {
                printf("插入位置ind = %d, 插入元素val = %d, 插入%s, 元素个数 = %d\n", ind, val, insert(v, ind, val) ? "成功" : "失败", 1 + v->length);
            } break;
            case 4 : {
                printf("删除位置ind = %d, 删除%s\n", ind, erase(v, ind) ? "成功" : "失败");
            } break;
        }
        output(v), printf("\n");
    }
    #undef MAX_N
    clear(v);
    return 0;
}