数据结构之线性表

记录数据结构之线性表的代码实现

顺序表的定义

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

顺序表的初始化

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

顺序表的清空

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

顺序表的扩容操作

int expand(Vector* v)
{
    int extr_size = v->size;
    int* p=NULL;
    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->data = p;
    v->size += extr_size;
    return 1;
}

顺序表的插入

int insert(Vector* v, int ind, int val)
{
    if (v == NULL) return 0;
    if (v->length == v->size)
    {
        if (!expand(v)) return 0;
        printf("success to expand! the size= %d\n", v->size);
    }
    if (ind<0 || ind>v->length) 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(Vector* v, int ind)
{
    if (v == NULL) return 0;
    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 -= 1;
    return 1;
}

顺序表的打印

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