#include<stdio.h>

/**
 * 数组实现顺序表
 */
typedef int Status; //为数据类型声明别名，要加分号;
typedef int ElemType;
#define OK 1 //宏定义，不加分号;
#define ERROR 0
#define MAXSIZE 10
#define INCREMENT 10

typedef struct ArrayList   //顺序表三要素：元素基址、元素个数、表长
{
    ElemType *data; //数据元素基址
    int length; //顺序表当前元素个数
    int size; //顺序表表长
} ArrayList, *ArrayListPtr;

/**
 * 初始化构造一个空顺序表
 */
Status init(ArrayListPtr arrayListPtr)   //参数类型为指针变量
{
    arrayListPtr->data = (ElemType*)malloc(MAXSIZE*sizeof(ElemType)); //指针变量结构体引用成员变量使用->运算符;malloc函数申请的内存返回值要强转成对应存储格式的指针类型
    if(!arrayListPtr->data)
    {
        return ERROR;
    }
    arrayListPtr->length=0;
    arrayListPtr->size=MAXSIZE;
    return OK;
}

/**
 * 重置为空表；初始条件：顺序表存在
 */
Status clear(ArrayListPtr arrayListPtr)
{
    if(!arrayListPtr->data)
    {
        return ERROR;
    }
    arrayListPtr->length = 0;
    return OK;
}

/**
 * 销毁顺序表，回收内存空间；初始条件：顺序表存在
 */
Status destory(ArrayListPtr arrayListPtr)
{
    if(arrayListPtr->data)
    {
        free(arrayListPtr->data);
        arrayListPtr=NULL;
        return OK;
    }
    return ERROR;
}

/**
 * 根据位序返回元素
 * 思考：为什么要将返回结果作为参数传递进去而不是直接利用函数返回值传递？
 * 答：为了使函数更具有通用性，适应性更高，因为执行函数的结果有可能是正常返回指定的元素值，有可能查询失败而返回失败信息，此时如果用返回值类型做为函数返回值那么可能需要借助一些特殊值来区分失败的情况
 */
Status getElem(ArrayListPtr arrayListPtr, int pos, ElemType* e)
{
    if(pos < 1 || pos > arrayListPtr->length)
    {
        return ERROR;
    }
    *e = arrayListPtr->data[pos-1];
    return OK;
}

/**
 * 查找某个元素是否存在
 */
Status isLocate(ArrayListPtr arrayListPtr, ElemType e)
{
    int i = 0;
    if(!arrayListPtr->data)
    {
        return ERROR;
    }
    while(i < arrayListPtr->length)
    {
        if(arrayListPtr->data[i] == e)
        {
            return OK;
        }
        i++;
    }
    return ERROR;
}

/**
 * 判空
 */
Status isEmpty(ArrayListPtr arrayListPtr)
{
    return arrayListPtr->length == 0 ? 1 : 0;
}

/**
 * 插入元素到指定位置
 */
Status insert(ArrayListPtr arrayListPtr, int pos, ElemType e)
{
    ElemType* newBase;
    int i = 0;
    if(pos < 1 || pos > arrayListPtr->length+1)   //只能插入第一个位置到当前元素个数+1这之间的位置
    {
        printf("下标不合法，插入失败\n");
        return ERROR;
    }
    if(arrayListPtr->length == arrayListPtr->size)   //如果当前元素个数等于表长，则需要扩容
    {
        /*
        1）如果当前内存段后面有需要的内存空间，则直接扩展这段内存空间，realloc()将返回原指针。
        2）如果当前内存段后面的空闲字节不够，那么就使用堆中的第一个能够满足这一要求的内存块，将目前的数据复制到新的位置，并将原来的数据块释放掉，返回新的内存块位置。
        3）如果申请失败，将返回NULL，此时，原来的指针仍然有效。
        */
        newBase = (ElemType*)realloc(arrayListPtr->data, (arrayListPtr->size + INCREMENT)*sizeof(ElemType));
        arrayListPtr->data = newBase; //要将新首地址赋值给arrayList->data
        arrayListPtr->size += INCREMENT; //表长增加
    }
    for(i = arrayListPtr->length - 1; i >= pos-1; i--)
    {
        arrayListPtr->data[i+1] = arrayListPtr->data[i]; //后移操作
    }
    arrayListPtr->data[pos-1] = e; //插入操作
    arrayListPtr->length++;
    return OK;
}

/**
 * 删除指定位置元素，并用e返回
 */
Status deleteElem(ArrayListPtr arrayListPtr, int pos, ElemType* e)
//Status getElem(ArrayListPtr arrayListPtr, int pos, ElemType* e)
{
    int i;
    if(pos < 1 || pos > arrayListPtr->length)
    {
        return ERROR;
    }
    *e = arrayListPtr->data[pos-1];
    for(i = pos-1; i < arrayListPtr->length; i++)
    {
        arrayListPtr->data[i] = arrayListPtr->data[i+1];//前移操作
    }
    arrayListPtr->length--;
    return OK;
}

/**
 * 遍历顺序表
 */
void print(ArrayListPtr arrayListPtr)
{
    int i = 0;
    printf("\n顺序表表长 = %d, 元素个数 = %d,其元素分别为：",arrayListPtr->size, arrayListPtr->length);
    while(i<arrayListPtr->length)
    {
        printf("%d\t",arrayListPtr->data[i]);
        i++;
    }
    printf("\n");
}

void test1()
{
    ArrayList arrayList;
    ElemType e;
    ElemType* e1;
    //1.初始化
    init(&arrayList);
    printf("初始化顺序表：size = %d, length = %d\n",arrayList.size, arrayList.length);
    print(&arrayList);
    printf("\n是否为空表？%d\n", isEmpty(&arrayList));
    int i = 0;
    //2.插入元素
    while(i < 20)
    {
        insert(&arrayList, i+1, i);
        i++;
    }
    print(&arrayList);
    //3.根据位置返回元素

    getElem(&arrayList, 6, &e);
    printf("\n第6个元素是: %d\n", e);

    //4.查找某个元素是否存在
    printf("\n6是否存在于表中？ %d\n", isLocate(&arrayList, 6));
    printf("\n21是否存在于表中？ %d\n", isLocate(&arrayList, 21));
    printf("\n是否为空表？ %d\n", isEmpty(&arrayList));

    //5.删除元素
    deleteElem(&arrayList, 11, &e);
    printf("\n被删除的元素是：%d\n", e);
    printf("删除之后的元素序列为：");
    print(&arrayList);

    deleteElem(&arrayList, 11, &e);
    printf("\n被删除的元素是：%d\n", e);
    printf("删除之后的元素序列为：");
    print(&arrayList);
    //6.清空顺序表
    printf("执行清空之后:");
    clear(&arrayList);
    // insert(&arrayList, 1, 1); //执行清空之后仍可插入
    print(&arrayList);

    //7.销毁顺序表
    printf("执行销毁之后：");

    destory(&arrayList); //销毁只是回收了分配给线性表的空间，而arrayList变量依然存在，仍然可以访问arrayList.size等成员变量
    i = 0;
    while(i < 1)
    {
        insert(&arrayList, i+1, i);
        i++;
    }
    insert(&arrayList, 1, 6); //销毁之后再插入可能出现异常，因为地址已经被标记为可以被其他程序使用，当使用已经被占用的内存地址就会发生错误
    print(&arrayList);



}