//linear list described by linear 
//线性表：由同类型数据元素构成有序序列的线性结构
//表头、表尾、无元素称空表、元素个数称表的长度。
//----------------------------------------------------------------------------------------------------------------------------第一部分-introduction

//a struct for polynomial 
typedef struct PolyNode *Polynomial;
struct PolyNode{   
    int coef; //the coeffcient
    int expon; // the exponential
    Polynomial link;
};

//----------------------------------------------------------------------------------------------------------------------------
//for linear list, we have the following operations.

//  List MakeEmpty()  初始化一个空线性表L；
//  ElementType FindKth(int K, List L)  根据位序K，返回相应元素；
//  int Find(ElementType X, List L)   在线性表L中查找X的第一次出现位置
//  viod Insert(ElementType X, int i, List L)  在位序i前插入一个新元素X；
//  viod Delete(int i, List L)  删除指定位序i的元素；
//  int Length(List L)  返回线性表L的长度n;

// now let's realize it !
//-----------------------------------------------------------------------------------------------------------------------------
//-----------------------------------------------------------------------------------------------------------------------------第二部分-使用数组
//利用数组的连续存储空间顺序存放线性表的各元素
#define MAXSIZE 100

typedef struct Node *List;;
struct LNode{
    ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;
List PtrL;
// initialize the orlder table----------------------------------------------------------------------------------------------
List MakeEmpty()
{
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode)); //malloc a memory space 
    Ptrl->Last = -1; //let the last value initialize to -1, means no elememt
    return PtrL;     // if the last value = 0, means have a element at the first site
}
//search the element   -----------------------------------------------------------------------------------------------------
int Find(ElementType X, List PtrL)
{
    int i= 0；
    while(i <= PtrL->Last && PtrL->Data[i]!= X) i++; 
    if(i > PtrL->Last) return -1;
    else return i;//if not find, goto the next untill retune -1, or return i
}

//insert the element   -----------------------------------------------------------------------------------------------------
void Insert(ElementType X, int i, List PtrL)
{
    int i;
    if(PtrL->Last == MAXSIZE-1){ //cheak whether the list is full
        printf("full");
        return;
    }
    if(i<1||i>PtrL->Last+2){  //the element must have a valid position number
        printf("illegal position");
        return;
    }
    for(j = PtrL->Last;j >= i-1;j--) //translate from the back to front  
    {
        PtrL->Data[j+1] = PtrL->Data[j];
    }
    PtrL->Data[i-1] = x; //insert it at x-1
    PtrL->Last++;       // last point the last value 
    return;
}
//delete the element   ------------------------------------------------------------------------------------------------------------
void Delete(int i, List PtrL)
{
    int j;
    if(i<1||i>PtrL->Last+1){ //validity cheach
        printf("%dth element inexitence",i);
        return;
    }
    for(j=i;j<=PtrL->last;j++)
        PtrL->Data[j-1] = PtrL->Data[j]; //translate the elements
    PtrL->Last--;
    return; 
}


//---------------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------------第三部分-使用链表
//linked list 通过链表存储
//不要求逻辑上相邻的两个元素物理上也相邻。
//插入与删除不需要移动数据元素，只需要修改链

typedef struct Node *List;;
struct LNode{
    ElementType Data;
    list Next;
};
struct LNode L;
List PtrL;

//the length of list  -----------------------------------------------------------------------------------------------------------
int Length(List PtrL)
{
    List p = PtrL; //p point the first node of this list
    int j = 0;
    while(p){
        p = p->Next;
        j++     //current p point the j th node
    }
    return j;
}

//find by value     ----------------------------------------------------------------------------------------------------------

List Find(ElementType X, List PtrL)
{
    List p = PtrL;
    while(p!=NULL && p->Data!=X) p = p->Next;
    return p;
}

//find by the serial number  --------------------------------------------------------------------------------------------------

List FindKth(int L, List PtrL)
{
    List p = PtrL;
    int i = 1;
    while(p != NULL && i<K){ // i = K, mean we find it, or p is null
        p = p->Next;
        i++
    }
    if(i == K) return p; //find K th
    else return NULL;  // or don't find it
}

//insert        -------------------------------------------------------------------------------------------------------------
List Insert(ElementType X, int i, List PtrL)
{
    List p, s;
    if(i == 1){       //the new node insert into the list head
        s = (List)malloc(sizeof(struct LNode)); //malloc a space for this new
        s->Data = X;
        s->Next = PtrL;
        return s;
    }
    p = FindKth(i-1, PtrL); //find the i-1 th node
    if(p == NULL){
        printf("parameter i invalid");
        return NULL;
    }
    else{
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = p->Next;  //let new i th point to i+1
        p->Next = s;  //let i-1 th  point new i th
        return PtrL;  // the above operations cannot converse! or, s->Next point s!
    }
}


//delete     -------------------------------------------------------------------------------------------------------------

List Delete(int i, List PtrL){
    List p, s;
    if(i==1){    //if the first node will be delete, easy!
        s= PtrL;
        if(PtrL != NULL) PtrL = PtrL->Next;        
    }
    p = FindKth(i-1, PtrL);   //find the i-1 the node
    if(p == NULL){    //if i-1 is null 
        printf("%d th node inexistence",i-1);
        return NULL;
    } 
    else if (p->Next == NULL){  //if i is null
        printf("%d th node inexistence",i);
        return NULL;
    }
    else{     // if valid, let the i-1 th node point the i+1
        s = p->Next; // in order to free it convenience! or, we can't find it!
        p->Next = s->Next; 
        free(s);
        return PtrL;
    }
}

//---------------------------------------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------------------------------------//第四部分-广义表与多重链表
//广义表， 是线性表的推广   


typedef struct GNode *Glist;
struct GNode{
    int Tag; //标识域Tag， 0表示结点为单元素和1表示结点为广义表
    union{     //子表指针域Sublist与单元素数据域Data复用
        ElementType Data;
        GList SubList;
    }URegion;
    GList Next; //指向后继结点
};

//多重链表
//标识域Tag， 区分头结点（Head）和非0元素结点(Term)