/* 
 * 线性表顺序结构（代码块完整，可直接执行）
 * 建议使用 VS Code.配置自查，有需要我再发。
 * By: HSGO 19-08-08
*/

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 //不可行的
#define OVERFLOW -2 //溢出

typedef int Status;

//-----------------------------------------------
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int ElemType;
typedef struct 
{
    ElemType *elem;
    int length;
    int listsize;
} Linear_list;

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

/* 打印线性表 */
Status Print_SQ();
/* 算法01 线性表顺序结构初始化 */
Status InitList_SQ();
/* 算法02 在某位置插入一个元素 */
Status ListInsert_SQ();
/* 算法03 删除某位置元素，并将该值返回 */
Status ListDelete_SQ();
/* 算法04 查找某元素的位置 */
    /* 对比函数，被调用 */
Status Compare_EL(); 
Status LocateElem_SQ();
/* 算法05 计算线性表合并时间复杂度 */
Status MergeList_SQ();

//----------------------------------------------
int main(){
    
    Linear_list A;
    Linear_list B;
    Linear_list C;
    InitList_SQ(&A); //初始化
    InitList_SQ(&B);

    for (int i = 1; i < 10; i++) //插入赋值
    {
        int a = i * 2;
        int b = i * 2 + 1;
        ListInsert_SQ(&A, i, a);
        ListInsert_SQ(&B, i, b);
    }

    printf("insert test:\n"); //插入测试
    ListInsert_SQ(&A, 5, 44); 
    printf("Print A:\n");
    Print_SQ(A);

    printf("delete test:\n"); //删除测试
    int E;
    ListDelete_SQ(&A, 3, &E);
    printf("delete the 3 position Elem, it is %d \n", E);
    printf("Print A:\n");
    Print_SQ(A);

    printf("locate test:\n"); //查找测试
    int locateElem = LocateElem_SQ(&A, 44, Compare_EL);
    printf("find 44 ,position is %d \n",locateElem);

    printf("Merge test:\n"); //合并测试
    MergeList_SQ(A, B, &C);
    printf("Print C:\n");
    Print_SQ(C);

    free(A.elem);//释放
    free(B.elem);
    free(C.elem);
    return 0;
}

//--------------------------------------------
Status Print_SQ(Linear_list L){
    for (int i = 0; i < L.length; i++)
    {
        printf("%d\t",L.elem[i]);
    }
    printf("\n");
}

Status InitList_SQ(Linear_list *L){
    
    L->elem = ( ElemType * ) malloc ( LIST_INIT_SIZE * sizeof ( ElemType ) );
    if ( !( L->elem ) ) exit ( OVERFLOW );

    L->length = 0;
    L->listsize = LIST_INIT_SIZE;

    printf("Init success, size is: %d \n",sizeof ( *L ));
    return OK;
}

Status ListInsert_SQ(Linear_list *L, int i, ElemType e){
    
    if ( i<1 || i>L->length+1 ) return ERROR;
    if ( L->length >= L->listsize )
    {
        int *newbase = (ElemType *) realloc (L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType) );
        if( !newbase ) exit(OVERFLOW);
        L->elem = newbase; //重新定义大小
        L->listsize += LISTINCREMENT;
    }
    int *q = &(L->elem[i-1]);
    for( int *p = &(L->elem[L->length -1]); p >= q; --p) *(p+1) = *p; //元素后移

    *q = e;
    ++L->length;
    return OK;
}

Status ListDelete_SQ(Linear_list *L, int i, ElemType *E){//删除，并用E返回该值

    if( i < 1 || i > L->length ) return ERROR;
    int *p = &(L->elem[i-1]);
    *E = *p;
    int *q = L->elem + L->length -1;
    for ( ++p; p <= q; ++p) *(p-1) = *p; //元素前移
    --L->length;
    return OK;
}

int Compare_EL(ElemType p, ElemType e){
    if ( p == e) return 1;
    else return 0;    
}
Status LocateElem_SQ(Linear_list *L, ElemType e, Status ( *compare )(ElemType, ElemType) ){

    int i = 1;
    int *p = L->elem;
    while( i <= L->length && !compare(*p++,e) ) ++i;
    if( i <= L->length ) return i;
    else return 0;
}

Status MergeList_SQ(Linear_list La, Linear_list Lb, Linear_list *Lc){
    int *pa = La.elem;
    int *pb = Lb.elem;
    Lc->listsize = Lc->length = La.length + Lb.length;

    int *pc = Lc->elem = (ElemType *) malloc ( Lc->listsize * sizeof(ElemType) );
    if( !Lc->elem ) exit (OVERFLOW);

    int *pa_last = La.elem  + La.length-1;
    int *pb_last = Lb.elem + Lb.length-1;

    while (pa <= pa_last && pb <= pb_last)
    {
        if(*pa <= *pb) *pc++ = *pa++;
        else *pc++ = *pb++;
    }

    while(pa <= pa_last) *pc++ = *pa++;
    while(pb <= pb_last) *pc++ = *pb++;
    
}

后续更新：链式表链式结构。
数据结构这本书的所有代码陆续更新。