#include "list.h"
#include <stdlib.h>
#include "fatal.h"

//定义节点
struct Node
{
    ElementType Element;   //数据区
    Position Next;   //指针区
};

//创建一个空表或清空一个表
List MakeEmpty( List L)
{
    if(L != NULL)
        DeleteList(L);    //L非空删除L
    L=malloc(sizeof(struct Node));
    if( L == NULL)
        FatalError("Out of memory!");
    L->Next = NULL;
    return L;
}

//判断是否空表
int IsEmpty( List L)
{
    L-Next == NULL;
}

//判断是否为最后一个元素
int IsLast(Position P, List L)
{
    return P->Next == NULL;
}

//查找指定元素的位置
Position Find( ElementType X, List L)
{
    Position P;

    P = L->Next;
    while( P!=NULL && P->Element != X)
        p = P->Next;
    return P;
}

//删除指定元素
void Delete ( ElementType X, List L )
{
    Position P;

    P= FindPrevious( X, L）); //找到X，则if执行；找不到，if不不执行
    if( !IsLast( P, L ) )  /* Assumption of header use */
    {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free( TmpCell );
        //TmpCell的作用：保留要删除的节点地址，准备后续free
        //故不能用P->Next=P->Next->Next代替上述代码
    }
}

//找到X元素的前继，找不到返回NULL
Position FindPrevious( ElementType X, List L )
{
    Position P;
    P = L;

    while( P->Next != NULL && P->Next->Element != X )
        P = P->Next;

    return P;
}

//在指定位置插入元素X，后插
void Insert( ElementType X, List L, Position P )
{
    Position TmpCell;

    TmpCell = malloc( sizeof( struct Node ) );
    if( TmpCell == NULL )
        FatalError( "Out of space!!!" );

    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}


//删除整个链表
void DeleteList( List L )
{
    Position P, Tmp;

    P = L->Next;
    L->Next = NULL;
    while( P != NULL )
    {
        Tmp = P->Next;
        free( P );
        P = Tmp;
    }
}

//返回头结点地址
Position Header( List L )
{
    return L;
}

//取出第一个元素
Position First( List L )
{
    return L->Next;
}

//取出下一个元素
Position Advance( Position P )
{
    return P->Next;
}

//取出元素
ElementType Retrieve( Position P )
{
    return P->Element;
}