数据结构与算法笔记 cp2-1：线性表

ADT List{
    Data:.......
    Operation:
        InitList(&L): 初始化，建立一个空的线性表L
        ClearList(&L): 清空线性表L
        GetElem(L,i,&e): 将L中第i个位置元素值返回给e
        LocateElem(L,e): 在L中查找与e相等的元素
        ListInsert(&L,i,e): 在L中第i个位置插入新元素e
        ListDelete(&L,i,&e): 删除L中第i个位置元素，并用e返回其值
        ListLength(L): 返回L长度
} ADT List

typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
}table;

#define Size 5 //对Size进行宏定义，表示顺序表申请空间的大小
table initTable(){
    table t;
    t.head=(int*)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间
    if (!t.head) //如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        exit(0);
    }
    t.length=0;//空表的长度初始化为0
    t.size=Size;//空表的初始存储空间为Size
    return t;
}

table delTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被删除元素的位置有误");
        exit(0);
    }
    //删除操作
    for (int i=add; i<t.length; i++) {
        t.head[i-1]=t.head[i];
    }
    t.length--;
    return t;
}

//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
table addTable(table t,int elem,int add)
{
    //判断插入本身是否存在问题
    if (add>t.length+1||add<1) {
        printf("插入位置有问题");
        return t;
    }
    //线性表长度等于数组长度，没有多余空间容纳新插入的元素，此时需要申请
    if (t.length==t.size) {
        t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
        if (!t.head) {
            printf("存储分配失败");
            return t;
        }
        t.size+=1;
    } 
    for (int i=t.length-1; i>=add-1; i--) {
        t.head[i+1]=t.head[i];
    }
    t.head[add-1]=elem;
    t.length++;
    return t;
}