线性表的实现

先上代码：

/*************************************************************************
	> File Name: 1.vector.cpp
	> Author:Gin.TaMa 
	> Mail:1137554811@qq.com 
	> Created Time: 2019年04月09日 星期二 19时03分27秒
 ************************************************************************/
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

typedef struct Vector{
    int *data;// void* 来代表任意类型
    int size,length;
}Vector;

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

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

// calloc 申请并赋值为０
// malloc 仅申请
// realloc 重新分配
// 字节大小
int expand(Vector *v){
    // 注意内存泄露
    int extra_size = v->size;
    int*p;
    // 申请内存多次逐步减少
    while(extra_size){
        p = (int* )realloc(v->data,sizeof(int) * (v->size + extra_size));
        if(p)break;
        extra_size /= 2;
    }
    if(extra_size == 0)return 0;
    v->data = p;
    v->size += extra_size;
    return 1;
}

// 先判断错误
int insert(Vector *v, int ind,int val){
    if(ind < 0 || ind > v->length)return 0;
    if(v->length == v->size){
        if(!expand(v)){
            return 0;
        }
    }
    for(int i = v->length - 1;i >= ind;i--){
       v->data[i+1] = v->data[i]; 
    }
    v->data[ind] = val;
    v->length += 1;
    return 1;
}

int erase(Vector *v,int ind){
    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 --;
    return 1;
}

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

int main(){
    #define MAX_OP 20
    int op,ind,val;
    Vector *v;
    v = init(MAX_OP);
    for(int i = 0;i < MAX_OP;i ++){
        op = rand() % 4;
        ind = rand() % (v->length + 3) - 1;
        val = rand() % 100;
        switch(op){
            case 0:
            case 1:
            case 2:{
                printf("insert %d to vector at %d = %d\n"
                       ,val,ind,insert(v,ind,val));
                output(v);
            }break;
            case 3:{
                printf("erase element at %d from vector = %d\n",ind,erase(v,ind));
                output(v);
            }break;
            default: fprintf(stderr,"wrong op %d\n",op);break;
        }
    }
    clear(v);

    return 0;
}

在这里有些需要注意的

注意每次进行完操作都要去更改数据的基本信息
关于realloc 的使用

realloc 会先尝试扩展原来的空间，扩展失败就会去执行malloc 去申请一个新的空间

如果申请成功，接下来会进行内存的拷贝，并使用free来释放原来的空间

这里注意哈，free 和 delete 不能混用。。new 申请的由delete 删除, free malloc realloc 啥的不要和new delete 混用。

如果失败就会返回null ,注意这个地方是有可能造成内存泄露的。。

比如
```
v->data = realloc(v->data,100)
```
失败的情况下会　１．v->data 变成了空　２．原来的空间没有释放，而且找不到了。。
关于扩容操作是尝试申请到最大的能申请的空间。从原来的ｓｉｚｅ一点点的变小，能申请多少申请多少。
如何优化一下查找呢，实现更快的查找。

并行查找。。多开几个线程呗。

[数据结构 回顾]线性表的实现

线性表的实现

[数据结构　回顾]线性表的实现