typedef int Position;

typedef struct LNode *List;

struct LNode {

    ElementType Data[MAXSIZE];

    Position Last;

};

/* 初始化 */

List MakeEmpty()

{

    List L;

    L = (List)malloc(sizeof(struct LNode));

    L->Last = -;

    return L;

}

/* 查找 */

#define ERROR -1

Position Find( List L, ElementType X )

{

    Position i = ;

    while( i <= L->Last && L->Data[i]!= X )

        i++;

    if ( i > L->Last )  return ERROR; /* 如果没找到，返回错误信息 */

    else  return i;  /* 找到后返回的是存储位置 */

}

/* 插入 */

/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/

bool Insert( List L, ElementType X, Position P )

{ /* 在L的指定位置P前插入一个新元素X */

    Position i;

    if ( L->Last == MAXSIZE-) {

        /* 表空间已满，不能插入 */

        printf("表满");

        return false;

    }

    if ( P< || P>L->Last+ ) { /* 检查插入位置的合法性 */

        printf("位置不合法");

        return false;

    }

    for( i=L->Last; i>=P; i-- )

        L->Data[i+] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */

    L->Data[P] = X;  /* 新元素插入 */

    L->Last++;       /* Last仍指向最后元素 */

    return true;

} 

/* 删除 */

/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/

bool Delete( List L, Position P )

{ /* 从L中删除指定位置P的元素 */

    Position i;

    if( P< || P>L->Last ) { /* 检查空表及删除位置的合法性 */

        printf("位置%d不存在元素", P );

        return false;

    }

    for( i=P+; i<=L->Last; i++ )

        L->Data[i-] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */

    L->Last--; /* Last仍指向最后元素 */

    return true;

}

typedef struct LNode *PtrToLNode;

struct LNode {

    ElementType Data;

    PtrToLNode Next;

};

typedef PtrToLNode Position;

typedef PtrToLNode List;

/* 查找 */

#define ERROR NULL

Position Find( List L, ElementType X )

{

    Position p = L; /* p指向L的第1个结点 */

    while ( p && p->Data!=X )

        p = p->Next;

    /* 下列语句可以用 return p; 替换 */

    if ( p )

        return p;

    else

        return ERROR;

}

/* 带头结点的插入 */

/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */

bool Insert( List L, ElementType X, Position P )

{ /* 这里默认L有头结点 */

    Position tmp, pre;

    /* 查找P的前一个结点 */

    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;

    if ( pre==NULL ) { /* P所指的结点不在L中 */

        printf("插入位置参数错误\n");

        return false;

    }

    else { /* 找到了P的前一个结点pre */

        /* 在P前插入新结点 */

        tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */

        tmp->Data = X;

        tmp->Next = P;

        pre->Next = tmp;

        return true;

    }

}

/* 带头结点的删除 */

/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */

bool Delete( List L, Position P )

{ /* 这里默认L有头结点 */

    Position tmp, pre;

    /* 查找P的前一个结点 */

    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;

    if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */

        printf("删除位置参数错误\n");

        return false;

    }

    else { /* 找到了P的前一个结点pre */

        /* 将P位置的结点删除 */

        pre->Next = P->Next;

        free(P);

        return true;

    }

}

 typedef int Position;

 struct SNode {

     ElementType *Data; /* 存储元素的数组 */

     Position Top;      /* 栈顶指针 */

     int MaxSize;       /* 堆栈最大容量 */

 };

 typedef struct SNode *Stack;

 Stack CreateStack( int MaxSize )

 {

     Stack S = (Stack)malloc(sizeof(struct SNode));

     S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));

     S->Top = -;

     S->MaxSize = MaxSize;

     return S;

 }

 bool IsFull( Stack S )

 {

     return (S->Top == S->MaxSize-);

 }

 bool Push( Stack S, ElementType X )

 {

     if ( IsFull(S) ) {

         printf("堆栈满");

         return false;

     }

     else {

         S->Data[++(S->Top)] = X;

         return true;

     }

 }

 bool IsEmpty( Stack S )

 {

     return (S->Top == -);

 }

 ElementType Pop( Stack S )

 {

     if ( IsEmpty(S) ) {

         printf("堆栈空");

         return ERROR; /* ERROR是ElementType的特殊值，标志错误 */

     }

     else

         return ( S->Data[(S->Top)--] );

 }

 typedef struct SNode *PtrToSNode;

 struct SNode {

     ElementType Data;

     PtrToSNode Next;

 };

 typedef PtrToSNode Stack;

 Stack CreateStack( )

 { /* 构建一个堆栈的头结点，返回该结点指针 */

     Stack S;

     S = (Stack)malloc(sizeof(struct SNode));

     S->Next = NULL;

     return S;

 }

 bool IsEmpty ( Stack S )

 { /* 判断堆栈S是否为空，若是返回true；否则返回false */

     return ( S->Next == NULL );

 }

 bool Push( Stack S, ElementType X )

 { /* 将元素X压入堆栈S */

     PtrToSNode TmpCell;

     TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));

     TmpCell->Data = X;

     TmpCell->Next = S->Next;

     S->Next = TmpCell;

     return true;

 }

 ElementType Pop( Stack S )

 { /* 删除并返回堆栈S的栈顶元素 */

     PtrToSNode FirstCell;

     ElementType TopElem;

     if( IsEmpty(S) ) {

         printf("堆栈空");

         return ERROR;

     }

     else {

         FirstCell = S->Next;

         TopElem = FirstCell->Data;

         S->Next = FirstCell->Next;

         free(FirstCell);

         return TopElem;

     }

 }

typedef int Position;

struct QNode {

    ElementType *Data;     /* 存储元素的数组 */

    Position Front, Rear;  /* 队列的头、尾指针 */

    int MaxSize;           /* 队列最大容量 */

};

typedef struct QNode *Queue;

Queue CreateQueue( int MaxSize )

{

    Queue Q = (Queue)malloc(sizeof(struct QNode));

    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));

    Q->Front = Q->Rear = ;

    Q->MaxSize = MaxSize;

    return Q;

}

bool IsFull( Queue Q )

{

    return ((Q->Rear+)%Q->MaxSize == Q->Front);

}

bool AddQ( Queue Q, ElementType X )

{

    if ( IsFull(Q) ) {

        printf("队列满");

        return false;

    }

    else {

        Q->Rear = (Q->Rear+)%Q->MaxSize;

        Q->Data[Q->Rear] = X;

        return true;

    }

}

bool IsEmpty( Queue Q )

{

    return (Q->Front == Q->Rear);

}

ElementType DeleteQ( Queue Q )

{

    if ( IsEmpty(Q) ) {

        printf("队列空");

        return ERROR;

    }

    else  {

        Q->Front =(Q->Front+)%Q->MaxSize;

        return  Q->Data[Q->Front];

    }

}

typedef struct Node *PtrToNode;

struct Node { /* 队列中的结点 */

    ElementType Data;

    PtrToNode Next;

};

typedef PtrToNode Position;

struct QNode {

    Position Front, Rear;  /* 队列的头、尾指针 */

    int MaxSize;           /* 队列最大容量 */

};

typedef struct QNode *Queue;

bool IsEmpty( Queue Q )

{

    return ( Q->Front == NULL);

}

ElementType DeleteQ( Queue Q )

{

    Position FrontCell;

    ElementType FrontElem;

    if  ( IsEmpty(Q) ) {

        printf("队列空");

        return ERROR;

    }

    else {

        FrontCell = Q->Front;

        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */

            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */

        else

            Q->Front = Q->Front->Next;

        FrontElem = FrontCell->Data;

        free( FrontCell );  /* 释放被删除结点空间  */

        return  FrontElem;

    }

}