#include<stdio.h>
#include<stdlib.h>
#include<cstring>

typedef int SLDataType;

typedef struct SeqList
{
    SLDataType* _data;/*需要动态开辟的数组*/
    size_t _size;/*有效元素个数*/
    size_t _capacity;/*容量,当前可以存放的最大元素个数*/
} seqList;

//初始化
void initSeqList(seqList* sl){
    sl->_data = NULL;
    sl->_size = sl->_capacity = 0;
}

//检查容量
void checkCapacity(seqList* sl){
    //检查是否为空指针
    if (sl == NULL)
        return;
    //如果元素个数和容量相同,说明空间满了,需要扩容
    if (sl->_size == sl->_capacity){
        int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
        //开一个更大的空间,拷贝原数据,释放原空间
        SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
        //内存拷贝
        memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
        //释放原来空间
        free(sl->_data);
        //更新
        sl->_data = tmp;
        sl->_capacity = newCapacity;
    }
}

//在任意位置插入一个数据
void insert(seqList* sl, int pos, SLDataType val){
    if (sl == NULL)
        return;
    //检查pos插入的位置是否是有效位置
    if (pos >= 0 && pos <= sl->_size){
        //检查容量
        checkCapacity(sl);
        //移动元素:[pos,size)
        int end = sl->_size;
        while (end > pos){
            sl->_data[end] = sl->_data[end - 1];
            --end;
        }
        //插入数据
        sl->_data[pos] = val;
        //更新
        sl->_size++;
    }
}

//删除任意位置的一个数据
void erase(seqList* sl, int pos){
    if (sl == NULL || sl->_size == 0)
        return;
    //检查pos插入的位置是否是有效位置
    if (pos >= 0 && pos <= sl->_size){
        /*1.移动元素:[pos,size)
            从pos+1开始,从前向后依次移动元素*/
        int start = pos + 1;
        while (start < sl->_size){
            sl->_data[start - 1] = sl->_data[start];
            ++start;
        }
        --sl->_size;
    }
}

//尾插(用的比较多,效率高)
void pushBack(seqList* sl, SLDataType val){
    insert(sl, sl->_size, val);
}

//尾删(用的比较多,效率高)
void popBack(seqList* sl){
    /*if (sl == NULL)
        return;
    if (sl->_size > 0)
        sl->_size--;*/
    erase(sl, sl->_size);
}
//头插
void pushFront(seqList* sl, SLDataType val){
    insert(sl, 0, val);
}

//头删
void popFront(seqList* sl){
    erase(sl, 0);
}

//查找某一个元素
int findIdx(seqList* sl, SLDataType val){
    int i = 0;
    for (; i < sl->_size; ++i){
        if (sl->_data[i] == val)
            return i;
    }
    return -1;
}

 //读取某一个位置的元素
SLDataType getIdx(seqList* sl, int pos){
    return sl->_data[pos];
}

//打印出顺序表
void printSeqList(seqList* sl)
{
    for (int i = 0; i < sl->_size; ++i){
        printf("%d ", sl->_data[i]);
    }
    printf("\n");
}

 //销毁顺序表
void destorySeqList(seqList* sl){
    if (sl){
        //释放堆上申请的空间
        if (sl->_data); {
            sl->_data = NULL; 
        }
    }
}

void test(){
    seqList sl;
    initSeqList(&sl);
    insert(&sl, sl._size, 1);
    insert(&sl, sl._size, 2); 
    insert(&sl, sl._size, 3);
    insert(&sl, sl._size, 4);
    insert(&sl, sl._size, 5);
    printSeqList(&sl);
    erase(&sl, sl._size);
    printSeqList(&sl);
    erase(&sl, sl._size);
    printSeqList(&sl);
    erase(&sl, sl._size);
    printSeqList(&sl);
    erase(&sl, sl._size);
    printSeqList(&sl);
    erase(&sl, sl._size);
    printSeqList(&sl);
    insert(&sl, sl._size, 6);
    printSeqList(&sl);
    insert(&sl, 0, 0);
    insert(&sl, 0, -1);
    insert(&sl, 0, -2);
    insert(&sl, 0, -3);
    printSeqList(&sl);
    insert(&sl, 3, 8);/*在第四个位置插入8*/
    printSeqList(&sl);
    erase(&sl, 2);/*删除第三个位置的数字*/
    printSeqList(&sl);
    erase(&sl, 0);
    printSeqList(&sl);
    erase(&sl, 0);
    printSeqList(&sl);
    erase(&sl, 0);
    printSeqList(&sl);
    erase(&sl, 0);
    printSeqList(&sl);
}

int main(){
    test();
    system("pause");
    return 0;
}