//implementation of linear list, sequential representation, dynamic
#include<iostream>

using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 
#define OVERFLOW -2

//Status: status code of functions
typedef int Status;

#define INITSIZE 20
#define INCREASEMENT 10
typedef struct
{ 
    //dynamic allocation, point array
    int *elem; 

    //current length of linear_list
    int length;

    //storage space allocated for linear_list
    int listsize; 
}SqList;

Status InitList(SqList &L){
    //new and delete can do the same thing, but, no realloc
    L.elem = (int*)malloc(sizeof(int) * INITSIZE); 

    //fail to allocate storage
    if(!L.elem)
        return OVERFLOW;

    L.length = 0;
    L.listsize = INITSIZE;
    return OK;
}  

Status ListInsert(SqList &L, int pos, int e){
    //insert e in position pos(th)
    //pos legal area 1<= pos <= ListLength+1
    if(pos < 1 || pos > L.length + 1 ) 
        return ERROR; 
    
    //linear_list's storage capacity is full, allocate
    if(L.length >= L.listsize){
        int* newbase = (int*)realloc(L.elem, (L.listsize + sizeof(int)*INCREASEMENT));
        
        //fail to allocate storage
        if(!newbase)
              exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += INCREASEMENT;
    }

    //e's address
    int* curpos = &(L.elem[pos - 1]);
    int* iterpos;

    //elements at and after pos: move to the right
    for(iterpos = &(L.elem[L.length-1]); iterpos >= curpos; iterpos--)
        *(iterpos+1) = *iterpos;

    //insert e
    *curpos = e;
    ++L.length ;

    return OK;
}

Status ListDelete(SqList &L, int pos, int &e){
    //delete the element in position pos(th) 
    // set e = element to be deleted

    // pos illegal
    if(pos < 1 || pos > L.length)
        return ERROR;

    //e's address
    int* curpos = &(L.elem[pos-1]);
    e = *curpos;
    int* iterpos;
    int* endpos = L.elem + L.length - 1;
    for(iterpos = curpos; iterpos < endpos; iterpos++)
        *iterpos = *(iterpos + 1);
    L.length -= 1;

    return OK;
}

int LocateElem(SqList L, int e, Status (* compare)(int,int)){
    //find the order of the first element satisfys compare() with e
    //yes: return order; else: reutrn 0
    int order = 1;
    int* p = L.elem;
    while(order <= L.length && !(*compare)(*p++, e)) 
        order++;
    if(order <= L.length)
        return order;
    else 
        return 0;
}

void MergeList(SqList La, SqList Lb, SqList &Lc){
    //La, Lb is ordered linear list
    //merge La, Lb -> Lc
    int* pa = La.elem;
    int* pb = Lb.elem;
    Lc.listsize = Lc.length = La.length + Lb.length;
    int* pc = Lc.elem = (int*) malloc(Lc.listsize*sizeof(int));
    if(!Lc.elem)
        exit(OVERFLOW);
    int* pa_last = La.elem + La.length - 1;
    int* pb_last = Lb.elem + Lb.length - 1;
    
    //merge
    while(pa <= pa_last && pb <= pb_last)
        if(*pa <= *pb)
            *pc++ = *pa++;
        else    
            *pc++ = *pb++;
    
    //insert rest element of La
    while(*pa <= *pa_last)
        *pc++ = *pa++;

    //insert rest element of Lb
    while(*pb <= *pb_last)
        *pc++ = *pb++;
}

Status PrintList(SqList L){
    int* curp = L.elem;
    int iter;
    for(iter = 0; iter < L.length; iter++)
        printf("%d ",*curp++);
    printf("\n");
    return OK;
}

Status DestroyList(SqList &L){
    free(L.elem);
}



int main(){
    SqList L;
    InitList(L);
    ListInsert(L, 1, 1);
    ListInsert(L, 1, 2);
    PrintList(L);
    int elemToDelete = 0;
    ListDelete(L, 1, elemToDelete);
    PrintList(L);
    DestroyList(L);
    return 0;
}

//implementation of linear list, linked list, dynamic
#include<iostream>

using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 
#define OVERFLOW -2

//Status: status code of functions
typedef int Status;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

Status GetElem_L(LinkList L, int i, int &e){
    //L is the head pointer of the linked list
    //if i-th element exists, assign it to e and return OK, ERROR otherwise

    //the first node
    LNode* curnode = L->next; 
    
    //a counter
    int cnt = 1; 
    while(curnode && cnt < i){
        curnode = curnode->next;
        ++cnt;
    }

    // i-th element not exists
    if(!curnode || cnt > i)
        return ERROR; 
    e = curnode->data;
    return OK;
}

Status ListInsert_L(LinkList &L, int i, int e){
    //insert e into the i-th place of the linked list with header pointer
    LNode* curnode = L;
    int cnt = 0;

    //find the (i-1)-th node
    while(curnode && cnt < i-1){ 
        curnode = curnode->next;
        ++cnt;
    }

    //i greater than len(list)+1 or less than 1, return error
    if(!curnode || cnt > i-1)
        return ERROR;

    //genetate new node
    LNode* newnode = (LNode*) malloc(sizeof(LNode));
    //fail to allocate storage
    if(!newnode)
        return OVERFLOW;

    //insert new node into L
    newnode->data = e;
    newnode->next = curnode->next;
    curnode->next = newnode;

    return OK;
}

Status ListDelete_L(LinkList &L, int i, int &e){
    //delete i-th element and assign its value to e
    LNode* curnode = L;
    int cnt = 0;

    //find the (i-1)-th element
    while(curnode && cnt < i-1){
        curnode = curnode->next;
        cnt++;
    }

    //i is illegal
    if(!curnode || cnt > i-1)
        return ERROR;
    
    //assign i-th value to e
    LNode* toDelete = curnode->next;
    e = toDelete->data;

    //delete i-th value
    curnode->next = toDelete->next;
    free(toDelete);

    return OK;
}

Status CreateList_L(LinkList &L, int n){
    //input values of elements in reverted sequence, build linked list with header pointer
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    for(int iter=n; iter>0; iter--){
        //generate new node
        LNode* newnode = (LinkList)malloc(sizeof(LNode));
        //fail to allocate storage
        if(!newnode)
            return OVERFLOW;

        //input value of element
        printf("Please input element:\n");
        scanf("%d", &newnode->data);

        //insert new node into the front of the linked list
        newnode->next = L->next;
        L->next = newnode;
    }
}

Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
    //La, Lb is non-decreasing linked list
    //merge La, Lb into Lc

    LNode* cura = La->next;
    LNode* curb = Lb->next;

    //let La to be the header pointer of Lc
    LNode* curc = Lc = La;

    while (cura && curb)
    {
        if(cura->data <= curb->data){
            curc->next = cura;
            curc = cura;
            cura = cura->next;
        }
        else{
            curc->next = curb;
            curc = curb;
            curb = curb->next;
        }
    }

    //insert the rest of La or Lb
    curc->next = cura ? cura : curb;

    //free Lb's header pointer
    free(Lb);
    
    return OK;
}

Status Print_L(LinkList L){
    LNode* curr = L->next;
    while(curr){
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
    return OK;
}

Status Destory_L(LinkList &L){
    while(L){
        LNode* toDelete = L;
        L = L->next;
        free(toDelete);
    }

    return OK;
}

int main(){
    LinkList L;
    CreateList_L(L, 2);
    Print_L(L);

    ListInsert_L(L, 1, 10);
    Print_L(L);
    
    int toDelete;
    ListDelete_L(L, 1, toDelete);
    Print_L(L);
    
    Destory_L(L);
    return 0;
}

//implementation of linear list, linked list, dynamic
#include<iostream>

using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 
#define OVERFLOW -2

//Status: status code of functions
typedef int Status;

//maximum length of static linked list
#define MAXSIZE 1000

typedef struct{
    int data;

    //cursor of static linked list, index of the next element, last element's cur is 0
    int cur;
}component, SLinkList[MAXSIZE];

int LocateElem_SL(SLinkList S, int e){
    //find the first element whose value is e
    //exists, return its order, 0 otherwise
    
    //find the first node's index
    int curnode = S[0].cur;

    while(curnode && S[curnode].data != e)
        curnode = S[curnode].cur;
    return curnode;
}

Status InitSpace_SL(SLinkList &space){
    //make the one-dimensional array be spare list
    //space[0].cur correspond to the header pointer
    //cur = 0 represent null

    for(int iter=0; iter<MAXSIZE-1; iter++)
        space[iter].cur = iter+1;
    space[MAXSIZE-1].cur = 0;

    return OK;
}

int Malloc_SL(SLinkList &space){
    //if the standby list is not null, return the cur of the node that can be allocated
    //else, return 0

    int index = space[0].cur;

    // can allocate, then pace[0].cur point to the next available node
    if(space[0].cur)
        space[0].cur = space[index].cur;
    return index;
}

Status Free_SL(SLinkList &space, int k){
    //recycle the node(index of k) to the standby list
    space[k].cur = space[0].cur;
    space[0].cur = k;

    return OK;
}

Status Print_SL(SLinkList &space, int headptr){
    int curr = space[headptr].cur;
    while(curr != 0){
        printf("%d ", space[curr].data);
        curr = space[curr].cur;
    }
    printf("\n");
    return OK;
}

Status Difference(SLinkList &space, int &headptr){
    //input elements of set A and set B, 
    //build static linked list present set(A-B)U(B-A) in one-dimensional array space[]
    //assume the standby space is big enough, space[0].cur is the header pointer

    //initialize standby space
    InitSpace_SL(space);

    headptr = Malloc_SL(space);
    
    //endptr points to the last node 
    int endptr = headptr;
    
    //input the number of elements of A and B
    int numA, numB;
    printf("Please input \"numA numB\"! \n");
    scanf("%d %d", &numA, &numB);

    //build list represent A first
    for(int iter = 1; iter <= numA; iter++){
        int newnode = Malloc_SL(space);
        printf("Please input element in A\n");
        scanf("%d", &space[newnode].data);

        //insert new node in the end of the list
        space[endptr].cur = newnode;
        endptr = newnode;
    }

    space[endptr].cur = 0;

    for(int iter = 1; iter <= numB; iter++){
        //input value of element in B
        //if it in current list already, delete it.
        //else, insert it

        int elemValue;
        printf("Please input element in B\n");
        scanf("%d", &elemValue);

        int pre = headptr;
        int curr = space[headptr].cur;
        while(curr != space[endptr].cur && space[curr].data != elemValue){
            pre = curr;
            curr = space[curr].cur;
        }

        //element not in current list, insert it in the position after endptr
        if(curr == space[endptr].cur){
            int newnode = Malloc_SL(space);
            space[newnode].data = elemValue;
            space[newnode].cur = space[endptr].cur;
            
            //put new node after endptr
            //no change endptr, endptr is set A's end
            space[endptr].cur = newnode;
        }
        //element in current list, delete it
        else{
            space[pre].cur = space[curr].cur;
            Free_SL(space, curr);
            //if the element is endptr, modify endptr
            if(curr == endptr)
                endptr = pre;
        }
    }
    return OK;
}

int main(){
    SLinkList sl;
    int headptr;

    //test: 
    //A: 3 2 5 7 6 4
    //B: 1 2 14 6
    Difference(sl,headptr);
    Print_SL(sl, headptr);
    return 0;
}