/** 線性表的順序存儲(chǔ)結(jié)構(gòu)：指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表內(nèi)的數(shù)據(jù)元素
 *
 *  數(shù)據(jù)長(zhǎng)度    -> 存放線性表的存儲(chǔ)空間的長(zhǎng)度，不可變
 *  線性表的長(zhǎng)度 -> 線性表中數(shù)據(jù)元素的個(gè)數(shù)，隨著線性表的插入和刪除操作，可變
 *
 *  優(yōu)點(diǎn)：1.無須為元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
 *       2.可以快速的讀取表中任一位置的元素
 *
 *  缺點(diǎn)：1.插入和刪除操作需要移動(dòng)大量元素
 *       2.當(dāng)線性表長(zhǎng)度變化較大時(shí)， 難以確定存儲(chǔ)空間的k容量
 *       3.造成存儲(chǔ)空間的‘碎片’，浪費(fèi)了內(nèi)存
 */

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

#define MAXSIZE 20
typedef int  ElemType;

typedef struct {
    ElemType *data;
    int length;
    int maxSize;
} SqlList;


#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;

/** 初始化*/
int InitList(SqlList *L) {
    L->data = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    if (L->data == NULL) {
        return -1;
    }
    L->length = 0;
    L->maxSize = MAXSIZE;
    return 0;
}


/** 指定位置插入*/
Status ListInsert(SqlList *L, int i, ElemType e) {
    int k;
    if (L->length >= L->maxSize) {
        return ERROR;
    }
    if (i <1 || i > L->length+1) {
        return ERROR;
    }
    if (i <= L->length) {
        for (k = L->length-1; k>=i-1; k--) {
            L->data[k+1] = L->data[k];
        }
    }
    L->data[i-1] = e;
    L->length++;
    return OK;
}

/** 尾插法*/
void insert_last_list(SqlList *list, ElemType e) {
    if (list->length >= list->maxSize) {
        return;
    }
    list->data[list->length] = e;
    list->length++;
}


/** 頭插法*/
Status insert_header(SqlList *list, ElemType e) {
    if (list->length >= list->maxSize) {
        printf("溢出了");
        return ERROR;
    }
    for (int i = (list->length); i >=0 ; i--) {
        list->data[i+1] = list->data[i];
    }
    list->data[0] = e;
    list->length++;
    return OK;
}

/** 刪除指定元素，并且返回被刪除的元素*/
Status List_Delete(SqlList *L,int i, ElemType *e) {
    int k;
    if (L->length == 0) {
        return ERROR;
    }
    
    if (i < 1 || i > L->length) {
        return ERROR;
    }
    *e = L->data[i-1];
    for (k = i-1; k < L->length; k++) {
            L->data[k] = L->data[k+1];
    }
    L->length--;
    return OK;
}

/** 當(dāng)內(nèi)存空間不夠時(shí)，再次開辟空間*/
void again_malloc(SqlList *list) {
    ElemType *p = realloc(list->data, 2 * list->maxSize);
    if (!p) {
        printf("存儲(chǔ)空間用完");
        return;
    }
    list->data = p;
}

/** 遍歷輸出當(dāng)前順序表*/
void iteratorData(SqlList *list) {
    for (int i =0; i < list->length; i++) {
        printf("current %d is %d",i,list->data[i]);
    }
}

/** 清空*/
void clear_list(SqlList *list) {
    if (list->data > 0) {
        list->length = 0;
    }
}

void destropy_list(SqlList *list) {
    
    if (list->data != NULL) {
        free(list->data);
        list->length = 0;
    }
}

#pragma mark - 調(diào)用
void k_printfData(void) {
    
    int a[10] = {2,4,6,8,10,12,14,16,18,20};
    SqlList q1;
    InitList(&q1);
    
    //順序插入數(shù)據(jù)
    for (int i = 0; i < sizeof(a)/sizeof(int); i++) {
        insert_last_list(&q1, a[i]);
    }
    //遍歷數(shù)據(jù)
    iteratorData(&q1);
    
    //在指定位置插入數(shù)據(jù)
    int result = ListInsert(&q1, 3, 9);
    if (result == OK) {
        printf("插入成功了\n");
    } else {
        printf("插入失敗\n");
    }
    iteratorData(&q1);
    
    //在頭部插入數(shù)據(jù)
    insert_header(&q1, 25);
    
    //刪除指定元素
    ElemType deleteEle;
    List_Delete(&q1, 5, &deleteEle);
    printf("被刪除的元素是 %d\n",deleteEle);
    
    iteratorData(&q1);
}