顺序表扩容

顺序表扩容

---

程序=算法+数据结构

数据结构=结构定义+结构 *** 作

程序设计=算法+数据结构+编程范式

1.顺序表 *** 作：

注意：顺序表与数组的不同点在于顺序表支持动态扩容 *** 作

#include
#include
#include

typedef struct{
    int *data;
    int size, length;
}SqList;

//1.顺序表初始化
SqList *init(int n){
    //malloc存储空间开辟在堆区,函数外部也能访问(需要借助free手动释放空间)
    SqList *sqlst = (SqList *)malloc(sizeof(SqList));
    sqlst->data = (int *)malloc(sizeof(int) * n);
    sqlst->size = n;
    sqlst->length = 0;
    return sqlst;
}

//2.顺序表销毁 *** 作
void clear(SqList *sqlst){
    if(sqlst == NULL) return;//顺序表不存在直接return
    free(sqlst->data);//释放数据表的data域
    free(sqlst);//释放掉整个顺序表
    return;
}

//3.顺序表的插入 *** 作
int insert(SqList *sqlst, int ind, int val){
    if(sqlst == NULL) return 0;//顺序表生成失败
    if(ind < 0 || ind > sqlst->length) return 0;//只能在[0, sqlst-length]范围内进行插入
    if(sqlst->length == sqlst->size) return 0;//length==size顺序表已满直接return0
    //(1)将插入位置后的所有元素后移
    for(int i = sqlst->length; i > ind; --i){
        sqlst->data[i] = sqlst->data[i - 1];
    }
    //(2)将元素val进行插入
    sqlst->data[ind] = val;
    sqlst->length += 1;
    return 1;
}

//4.顺序表的删除 *** 作
int erase(SqList *sqlst, int ind){
    if(sqlst == NULL) return 0;
    if(ind < 0 || ind >= sqlst->length) return 0;
    //将删除位置后的所有元素前移(覆盖删除元素)
    for(int i = ind + 1; i < sqlst->length; ++i){
        sqlst->data[i - 1] = sqlst->data[i];
    }
    sqlst->length -= 1;
    return 1;
}

//5.print *** 作
void print(SqList *sqlst){
    if(sqlst == NULL) return;
    printf("[");
    for(int i = 0; i < sqlst->length; ++i){
        i && printf(", ");//若i不为0则输出", "
        printf("%d", sqlst->data[i]);
    }
    printf("]");
}

int main(){
    //1.创建一个顺序表
    #define MAX_N 20
    SqList *sqlst = init(MAX_N);
    //2.利用随机数的方式顺序表进行插入、删除 *** 作
    srand(time(0));
    for(int i = 0; i < MAX_N; ++i){
        //进行MAX_N组测试
        int op = rand() % 4;//随机 *** 作方式
        int ind = rand() % (sqlst->length + 3) - 1;//随机 *** 作下标范围为[-1, sqlst-length + 1]
        int val = rand() % 100;//随机100以内的val值
        switch(op){
            case 0:
            case 1:
            case 2: {
                printf("insert %d at %d to the Vector = %d\n", val, ind, insert(sqlst, ind, val));
            } break;
            case 3: {
                printf("erase a item at %d = %d\n", ind, erase(sqlst, ind));
            } break;
        }
        print(sqlst), printf("\n");
    }
    #undef MAX_N
    //3.销毁顺序表
    clear(sqlst);
    return 0;
}

此时顺序表并没有达到最大容量，能够正常 *** 作。

2.关于内存空间申请：

注意：只要使用malloc动态申请过内存空间，就需要使用free释放内存空间，否则将产生内存泄漏

函数	说明
malloc()	动态申请空间
calloc()	动态申请空间，并且主动清空为0
realloc(v->data, 大小(byte))	重新申请空间

realloc的工作方式：

例如，将data空间扩容至原空间的两倍，realloc的执行会出现以下3种情况：

case1：在原内存空间后直接能够找到足够的连续内存空间，则直接开辟新的内存，返回原空间首地址（最优情况）

case2：在原内存空间后直接不能够找到足够的连续内存空间，

1. 需要在内存中找到新的内存空间满足两倍容量大小并开辟，
2. 将原内存空间中的数据拷贝到新开辟的空间中，
3. 最后会释放掉原空间内存（返回新开辟空间首地址）

注意：realloc *** 作会自动释放原空间内存，无需手动释放

case3：扩容失败，返回空地址NULL

3.顺序表实现扩容：

在对顺序表进行插入 *** 作时，当sqlst->length == sqlst->size需要进行扩容 *** 作

对程序中的插入 *** 作进行修改，并添加新增扩容 *** 作expand：

//SqList扩容 *** 作
int expand(SqList *sqlst){
    sqlst->data = (int *)realloc(sqlst->data, sizeof(int) * (sqlst->size * 2));//利用realloc每次扩容两倍
    return 1;
}

//3.顺序表的插入 *** 作
int insert(SqList *sqlst, int ind, int val){
    if(sqlst == NULL) return 0;//顺序表生成失败
    if(ind < 0 || ind > sqlst->length) return 0;//只能在[0, sqlst-length]范围内进行插入
    if(sqlst->length == sqlst->size){
        //顺序表已满则需要进行扩容
        if(!expand(sqlst)){
            printf("fail to expand!\n");
        }
        printf("success to expand! the size = %d\n"), sqlst->size);
    }
    //将插入位置后的所有元素后移
    for(int i = sqlst->length; i > ind; --i){
        sqlst->data[i] = sqlst->data[i - 1];
    }
    //将元素val进行插入
    sqlst->data[ind] = val;
    sqlst->length += 1;
    return 1;
}

缺点：这种简单的扩容 *** 作可能会出现扩容失败，realloc返回null地址覆盖data数据地址索引，导致丢失数据的现象。

---

考虑到上述中可能会出现的数据丢失情况，对扩容 *** 作进行修改后的版本：

#include
#include
#include

//格式控制字符串打印颜色
#define COLOR(a, b) "3[" #b "m" a "3[0m"
#define GREEN(a) COLOR(a, 32)
#define RED(a) COLOR(a, 31)

typedef struct{
    int *data;
    int size, length;
}SqList;

//1.顺序表初始化
SqList *init(int n){
    //malloc存储空间开辟在堆区,函数外部也能访问(需要借助free手动释放空间)
    SqList *sqlst = (SqList *)malloc(sizeof(SqList));
    sqlst->data = (int *)malloc(sizeof(int) * n);
    sqlst->size = n;
    sqlst->length = 0;
    return sqlst;
}

//2.顺序表销毁 *** 作
void clear(SqList *sqlst){
    if(sqlst == NULL) return;//顺序表不存在直接return
    free(sqlst->data);//释放数据表的data域
    free(sqlst);//释放掉整个顺序表
    return;
}

//SqList扩容 *** 作
int expand(SqList *sqlst){
    int extend_size = sqlst->size;
    int *p;//临时指针p用于存放realloc返回值
    while(extend_size){
        //进行循环扩容
        p = (int *)realloc(sqlst->data, sizeof(int) * (sqlst->size + extend_size));
        if(p != NULL) break;//realloc扩容成功,返回地址!=null则直接break
        extend_size >>= 1;//realloc扩容失败则将扩容容量extend缩小,再次尝试扩容
    }
    if(p == NULL) return 0;//循环扩容失败
    sqlst->size += extend_size;
    sqlst->data = p;
    return 1;
}

//3.顺序表的插入 *** 作
int insert(SqList *sqlst, int ind, int val){
    if(sqlst == NULL) return 0;//顺序表生成失败
    if(ind < 0 || ind > sqlst->length) return 0;//只能在[0, sqlst-length]范围内进行插入
    if(sqlst->length == sqlst->size){
        //顺序表已满则需要进行扩容
        if(!expand(sqlst)){
            printf(RED("fail to expand!\n"));
        }
        printf(GREEN("success to expand! the size = %d\n"), sqlst->size);
    }
    //将插入位置后的所有元素后移
    for(int i = sqlst->length; i > ind; --i){
        sqlst->data[i] = sqlst->data[i - 1];
    }
    //将元素val进行插入
    sqlst->data[ind] = val;
    sqlst->length += 1;
    return 1;
}

//4.顺序表的删除 *** 作
int erase(SqList *sqlst, int ind){
    if(sqlst == NULL) return 0;
    if(ind < 0 || ind >= sqlst->length) return 0;
    //将删除位置后的所有元素前移(覆盖删除元素)
    for(int i = ind + 1; i < sqlst->length; ++i){
        sqlst->data[i - 1] = sqlst->data[i];
    }
    sqlst->length -= 1;
    return 1;
}

//5.print *** 作
void print(SqList *sqlst){
    if(sqlst == NULL) return;
    printf("[");
    for(int i = 0; i < sqlst->length; ++i){
        i && printf(", ");//若i不为0则输出", "
        printf("%d", sqlst->data[i]);
    }
    printf("]");
}

int main(){
    //1.创建一个顺序表
    #define MAX_N 20
    SqList *sqlst = init(1);//将顺序表容量缩小以测试扩容 *** 作
    //2.利用随机数的方式顺序表进行插入、删除 *** 作
    srand(time(0));
    for(int i = 0; i < MAX_N; ++i){
        //进行MAX_N组测试
        int op = rand() % 4;//随机 *** 作方式
        //int ind = rand() % (sqlst-length + 1);测试范围为[0, sqlst-length]
        int ind = rand() % (sqlst->length + 3) - 1;//随机 *** 作下标范围为[-1, sqlst-length + 1]
        int val = rand() % 100;//随机100以内的val值
        switch(op){
            case 0:
            case 1:
            case 2: {
                printf("insert %d at %d to the Vector = %d\n", val, ind, insert(sqlst, ind, val));
            } break;
            case 3: {
                printf("erase a item at %d = %d\n", ind, erase(sqlst, ind));
            } break;
        }
        print(sqlst), printf("\n");
    }
    #undef MAX_N
    //3.销毁顺序表
    clear(sqlst);
    return 0;
}