【数据结构】顺序表

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

---

一.顺序表

1.结构定义

结构定义主要包含下面3个方面：

1. 存放数据的数组
2. 顺序表的大小size
3. 当前顺序表的长度（顺序表中的元素个数）length

2.结构操作

2.1插入操作

• 先将待插入位置后的数据整体往后平移一位
• 在待插入位置处插入数据
• length++

2.2删除操作

• 直接将待删除位置后的数据整体向前平移一位
• length–

3.代码演示

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//结构定义 存取整型数据
typedef struct Vector{
    int *data;
    int size, length;
} Vector;
//顺序表初始化
Vector *init(int n){
    Vector *vec = (Vector *)malloc(sizeof(Vector));
    vec->data = (int *)malloc(sizeof(int) * n);
    vec->size = n;
    vec->length = 0;//length指向下一个要插入的位置
    return vec;
}
//插入操作
int insert(Vector *vec, int ind, int val){
    if(vec == NULL) return 0;
    if(ind < 0 || ind > vec->length) return 0;
    if(vec->length >= vec->size) return 0;
    for(int i = vec->length - 1; i >= ind; i--){
        vec->data[i + 1] = vec->data[i];
    }
    vec->data[ind] = val;
    vec->length++;
    return 1;
}
//删除操作
int erase(Vector *vec, int ind){
    if(vec == NULL) return 0;
    if(ind < 0 || ind >= vec->length) return 0;
    for(int i = ind; i < vec->length - 1; i++){
        vec->data[i] = vec->data[i + 1];
    }
    vec->length--;
    return 1;
}
//打印顺序表
void output(Vector *vec){
    printf("Vector(%d) = [", vec->length);
    for(int i = 0; i < vec->length; i++){
        i && printf(", ");
        printf("%d", vec->data[i]);
    }
    printf("]\n");
}

//释放顺序表 防止内存泄漏
void clear(Vector *vec){
    if(vec == NULL) return ;
    free(vec->data);
    free(vec);
    return ;
}

//80%插入数据，%20删除数据
int main(){
    srand(time(0));
    #define MAX_OP 20
    Vector *vec = init(MAX_OP);
    int op, ind, val;
    for(int i = 0; i < MAX_OP; i++){
        op = rand() % 5;
        ind = rand() % (vec->length + 2)- 1;
        val = rand() % 100;
        switch(op){
            case 0:
            case 1:
            case 2:
            case 3:{
                printf("insert %d at %d to Vector = %d\n", val, ind, insert(vec, ind, val));
            }break;
            case 4:{
                printf("erase item at %d from Vector = %d\n", ind, erase(vec, ind));
            }break;
        }
        output(vec);
        printf("\n");
    }
    clear(vec);
    return 0;
}

4.优化（malloc、calloc、realloc）

优化：单纯的数组也可以进行上述的操作，为了实现更多的功能，我们在上面的基础加上扩容操作，即当顺序表满了之后，可以扩大空间

引出3个地址开辟的函数：

• malloc：单纯的开辟空间
• calloc：开辟空间之后对该片地址上的数值清0
• realloc：在原有空间的基础上扩大开辟的空间

当要对 vec->data进行扩容时，我们可以选用realloc函数在原有的基础上进行扩容，下面给出一个错误的扩容操作

//错误扩容方法
int expand(Vector *vec){
    vec->size *= 2;
    vec->data = (int *)realloc(vec->data, sizeof(int) * vec->size);
    return 1;
}

乍一看，我们发现可以进行扩容，下面我们分析一下realloc的工作方式

• 当vec->data后面的空间足够时，直接在其后面开辟等大的空间，返回地址vec->data
• 当vec->data后面的空间不足时，我们现在其他空间充足的地方开辟所需的空间，地址为q，将vec->data中的数据copy到q的前半部分，最后释放掉vec->data指向的空间，并返回地址q

由上面realloc的两种工作方式我们可以看出当没有足够的空间时，我们的q == NULL，之后vec->data被时放掉，数据就丢失了，造成内存泄露！！！！！！！！！！数据丢失是很严重的问题

下面给出正确的扩容操作：

//正确扩容方法
//先用一个中间量p记录新开辟的地址空间，防止直接将NULL赋值给vec->data
int expand(Vector *vec){
    int extr_size = vec->size;
    int *p;
    while(extr_size){//如果没有足够的空间，所需开辟的空间减半，循环，直到找到一个合适extr_size
        p = (int *)realloc(vec->data, sizeof(int) * (vec->size + extr_size));
        if(p) break;
        extr_size /= 2;
    }
    if(p == NULL) return 0;//循环结束时p仍为NULL，说明一点空间没有了，开辟失败
    vec->data = p;
    vec->size += extr_size;
    return 1;
}

//插入操作需要修改部分内容
int insert(Vector *vec, int ind, int val){
    if(vec == NULL) return 0;
    if(ind < 0 || ind > vec->length) return 0;
    if(vec->length >= vec->size) {
        if(!expand(vec)) return 0;
        printf("expand successfully! size = %d\n", vec->size);
    }
    for(int i = vec->length - 1; i >= ind; i--){
        vec->data[i + 1] = vec->data[i];
    }
    vec->data[ind] = val;
    vec->length++;
    return 1;
}


//为了现实效果更好，主函数修改
Vector *vec = init(5);

运行结果：

---

明天更新链表内容，加油！！！LIfe goes on!

转载：https://blog.csdn.net/moX980/article/details/105721470