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

顺序表：一片连续存储的区域

结构定义：

size：代表当前顺序表大小

length：当前一共存储了多少个元素

data_type：存储的元素类型

结构操作：

插入：

删除：

1、数据结构的定义：

typedef struct Vector{
    int *data;
    int size,length;

}Vector;

将struct结构类型重新定义成vector数据类型

int * data:指针是地址。 数据一片连续的存储区域,

2、初始化存储n个元素的顺序表

Vector *init(int n){

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

数据类型Vector*，也就是前面的结构体

函数名init

参数int n

函数内定义了一个vec顺序表，并为顺序表初始化了一段内存空间

然后为顺序表中连续存储的数据data也初始化了一段空间

元素个数size初始化为n，也就是传入的参数

已有元素length初始话为0

最后返回顺序表vec

3、顺序表的销毁操作：

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

定义了一个没有返回值的函数，传入的参数是顺序表

if顺序表为空直接返回

不为空释放数据存储空间地址

释放顺序表。

4、顺序表插入操作：

int insert(Vector *vec, int ind, int val){
    if (vec == NULL ) return 0;
    if (vec->length == vec->size) return 0;
    if (ind <0 || ind>vec->length ) return 0;

    for (int i = vec->length;i>ind;i--){
        vec->data[i] = vec->data[i-1];
    }
    vec->data[ind] = val;
    vec->length +=1;
    return 1;

}

定义一个插入函数，int类型，插入成功返回1.失败为0

传入的参数分别为vec顺序表   ind位置  和val要传入的值

有几种非法的情况

1、当表为空

2、表已经满了

3、插入的位置超过上下限

以上都是非法的不能插入，直接返回0.

插入操作，我们插入的时候需要把插入位置及后面的数据依次往后移动

移动完成后再在插入位置写入我们要插入的数据

定义了一个for循环，初始化i为顺序表的已经存储的个数，因为是从0开始的所以不需要加1

循环结束条件是循环到我们要插入的位置ind

当循环结束

再插入位置插入我们的值

长度加1

返回1插入成功

5、删除顺序表元素

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

具体的和插入类似。不详细解释了

6、依次输出顺序表中元素的函数

输出格式类似于这个[1,2,2,3,6]

void output(Vector *vec){
    printf("Vector(%d) = [",vec->length);
    for (int i = 0;i<vec->length ; i++){
        printf("%d",vec->data[i]);
    }
    printf("]\n");
    return;
}

一个没有返回值的函数

传入元素是顺序表

输出vector（%d），表中有多少元素，类似vector（10），是个元素

用for循环遍历顺序表

6、主函数测试顺序表

随机位置随机插入删除值。

引入随机种子

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()%2;
        ind = rand()%(vec->length +1);
        val = rand()%100;
        switch(op){
            case 0:{
            printf("insert %d at %d to vector \n",val,ind);
            insert(vec,ind,val);

        }break;
            case 1:{
            printf("erase item at %d from vector \n",ind);
            erase(vec,ind);

        }break;

        }
        output(vec);
    }


return 0;
}

引入头文件

#include <time.h>

定义一个20常量

初始化顺序表

定义插入删除，位置，值的变量

op是0和1

0插入

1删除

定义一个for循环

循环条件0-20

%2随机出来0和1

%（vec->length+1）从已有元素的大小中随机

%100 随机到100数插入

用switch判断是插入还是删除

并输出

完整代码如下

#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;
    return vec;
}

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

int insert(Vector *vec, int ind, int val){
    if (vec == NULL ) return 0;
    if (vec->length == vec->size) return 0;
    if (ind <0 || ind>vec->length ) return 0;

    for (int i = vec->length;i>ind;i--){
        vec->data[i] = vec->data[i-1];
    }
    vec->data[ind] = val;
    vec->length +=1;
    return 1;

}

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

void output(Vector *vec){
    printf("Vector(%d) = [",vec->length);
    for (int i = 0;i<vec->length ; i++){
        if (i!=0) printf(",");
        printf("%d",vec->data[i]);
    }
    printf("]\n");
    return;
}

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()%2;
        ind = rand()%(vec->length +1);
        val = rand()%100;
        switch(op){
            case 0:{
            printf("insert %d at %d to vector \n",val,ind);
            insert(vec,ind,val);

        }break;
            case 1:{
            printf("erase item at %d from vector \n",ind);
            erase(vec,ind);

        }break;

        }
        output(vec);
    }


return 0;
}

以上的代码是有瑕疵的

对于插入的非法检查，几乎随机出来的每个操作都还是合法的

所有的插入操作都是合法的，测试就是不够充分的，必须要测出插入非法的会不会出问题。

插入非法的位置

对插入的位置+3就会随机生成超过原有大小的位置

ind = rand()%(vec->length +3)

然后我们设计一个百分之75是插入

百分之25是删除的改动

改动代码如下

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()%4;
        ind = rand()%(vec->length +3);
        val = rand()%100;
        switch(op){
            case 2:
            case 3:
            case 0:{
            printf("insert %d at %d to vector = %d\n",
                   val,ind , insert(vec,ind,val));
            insert(vec,ind,val);

        }break;
            case 1:{
            printf("erase item at %d from vector= %d \n",
                   ind,erase(vec,ind));
            erase(vec,ind);

        }break;

        }
        output(vec);
    }


return 0;
}

然我们继续更改，当前设计的顺序表的大小是固定的，但是我们想让他随机，可以自己扩容

加一个扩容操作。

int expand(Vector *vec)
{
    vec ->size *=2;
    vec ->data = (int *)rralloc(vec->data,sizeof(int)*vec->size);
    return 1;
}
int insert(Vector *vec, int ind, int val){
    if (vec == NULL ) return 0;
    if (vec->length == vec->size) {
        if (!expand(vec))
        return 0;}
    if (ind <0 || ind>vec->length ) return 0;

    for (int i = vec->length;i>ind;i--){
        vec->data[i] = vec->data[i-1];
    }
    vec->data[ind] = val;
    vec->length +=1;
    return 1;

}

扩容函数传入的顺序表

扩容为当前顺序表大小的一倍

用ralloc来扩容

怎么写扩容

malloc用来申请空间

free释放空间

realloc重新分配

重新分配声明一下对哪片空间重新分配

分配多大，

realloc分配成

realloc到底怎么工作的

他是如何扩容的，原有是p

realloc会试着在p后面申请空间，如果能成功申请的话，realloc他返回的值还是原来的数组首地址

如果申请失败，realloc就会调用malloc重新去分配一块空间

功会销毁之前的空间

当他申请到一片新的空间的时候，他会把原来空间的数据拷贝到新空间。拷贝过来后他在返回新申请空间的地址。

原来的空间还没有free，realloc当他成功申请一块新的空间后，会把之前的拷贝过来，并且会释放原来空间

如果申请第二段空间也失效，realloc不会释放掉原来的空间，realloc会返回一个空地址，代表重新分配空间失败，但是你原来的空间我没动。

申请失败，返回的空地址把vec->data的地址覆盖，原来的地址找不到了造成地址泄露。

最终代码

#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;
    return vec;
}

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

int expand(Vector *vec)
{
    int new_size = vec->size*2;
    int *p = (int *)realloc(vec->data,sizeof(int)*new_size);
    if (p==NULL) return 0;
    vec ->size *=new_size;
    vec ->data =p;
    return 1;
}
int insert(Vector *vec, int ind, int val){
    if (vec == NULL ) return 0;
    if (vec->length == vec->size) {
        if (!expand(vec))
        return 0;
    printf("expand vector size to %d success \n",vec->size);}
    if (ind <0 || ind>vec->length ) return 0;

    for (int i = vec->length;i>ind;i--){
        vec->data[i] = vec->data[i-1];
    }
    vec->data[ind] = val;
    vec->length +=1;
    return 1;

}

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

void output(Vector *vec){
    printf("Vector(%d) = [",vec->length);
    for (int i = 0;i<vec->length ; i++){
        if (i!=0) printf(",");
        printf("%d",vec->data[i]);
    }
    printf("]\n");
    printf("\n");
    return;
}

int main()
{
    srand(time(0));
    #define MAX_OP 20
    Vector *vec = init(1);
    int op ,ind ,val;
    for(int i=0 ;i<MAX_OP;i++){
        op = rand()%4;
        ind = rand()%(vec->length +3);
        val = rand()%100;
        switch(op){
            case 2:
            case 3:
            case 0:{
            printf("insert %d at %d to vector = %d\n",
                   val,ind , insert(vec,ind,val));
            insert(vec,ind,val);

        }break;
            case 1:{
            printf("erase item at %d from vector= %d \n",
                   ind,erase(vec,ind));
            erase(vec,ind);

        }break;

        }
        output(vec);
    }


return 0;
}