/* bo2-9.c 單鏈表線性表(存儲結構由c2-2.h定義)的擴展操作(11個) */
 void InsertAscend(LinkList L,ElemType e)
 { /* 初始條件：按非降序排列的線性表L已存在。操作結果：在L中按非降序插入新的數據元素e */
   LinkList q=L,p=L->next;
   while(p&&e>p->data)
   {
     q=p;
     p=p->next;
   }
   q->next=(LinkList)malloc(sizeof(struct LNode)); /* 插在q后 */
   q->next->data=e;
   q->next->next=p;
 }

 void InsertDescend(LinkList L,ElemType e)
 { /* 初始條件：按非升序排列的線性表L已存在。操作結果：在L中按非升序插入新的數據元素e */
   LinkList q=L,p=L->next;
   while(p&&e<p->data)
   {
     q=p;
     p=p->next;
   }
   q->next=(LinkList)malloc(sizeof(struct LNode)); /* 插在q后 */
   q->next->data=e;
   q->next->next=p;
 }

 Status HeadInsert(LinkList L,ElemType e)
 { /* 初始條件：線性表L已存在。操作結果：在L的頭部插入新的數據元素e,作為鏈表的第一個元素 */
   LinkList s;
   s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */
   s->data=e; /* 給結點賦值 */
   s->next=L->next; /* 插在表頭 */
   L->next=s;
   return OK;
 }

 Status EndInsert(LinkList L,ElemType e)
 { /* 初始條件：線性表L已存在。操作結果：在L的尾部插入新的數據元素e,作為鏈表的最后一個元素 */
   LinkList p=L;
   while(p->next) /* 使p指向表尾元素 */
     p=p->next;
   p->next=(LinkList)malloc(sizeof(struct LNode)); /* 在表尾生成新結點 */
   p->next->data=e; /* 給新結點賦值 */
   p->next->next=NULL; /* 表尾 */
   return OK;
 }

 Status DeleteFirst(LinkList L,ElemType *e)
 { /* 初始條件：線性表L已存在，且有不少于1個元素 */
   /* 操作結果：刪除L的第一個數據元素，并由e返回其值 */
   LinkList p=L->next;
   if(p)
   {
     *e=p->data;
     L->next=p->next;
     free(p);
     return OK;
   }
   else
     return ERROR;
 }

 Status DeleteTail(LinkList L,ElemType *e)
 { /* 初始條件：線性表L已存在，且有不少于1個元素 */
   /* 操作結果：刪除L的最后一個數據元素，并用e返回其值 */
   LinkList p=L,q;
   if(!p->next) /* 鏈表為空 */
     return ERROR;
   while(p->next)
   {
     q=p;
     p=p->next;
   }
   q->next=NULL; /* 新尾結點的next域設為NULL */
   *e=p->data;
   free(p);
   return OK;
 }

 Status DeleteElem(LinkList L,ElemType e)
 { /* 刪除表中值為e的元素，并返回TRUE；如無此元素，則返回FALSE */
   LinkList p=L,q;
   while(p)
   {
     q=p->next;
     if(q&&q->data==e)
     {
       p->next=q->next;
       free(q);
       return TRUE;
     }
     p=q;
   }
   return FALSE;
 }

 Status ReplaceElem(LinkList L,int i,ElemType e)
 { /* 用e取代表L中第i個元素的值 */
   LinkList p=L;
   int j=0;
   while(p->next&&j<i)
   {
     j++;
     p=p->next;
   }
   if(j==i)
   {
     p->data=e;
     return OK;
   }
   else /* 表中不存在第i個元素 */
     return ERROR;
 }

 Status CreatAscend(LinkList *L,int n)
 { /* 按非降序建立n個元素的線性表 */
   int j;
   LinkList p,q,s;
   if(n<=0)
     return ERROR;
   InitList(L);
   printf("請輸入%d個元素:\n",n);
   s=(LinkList)malloc(sizeof(struct LNode)); /* 第一個結點 */
   scanf("%d",&s->data);
   s->next=NULL;
   (*L)->next=s;
   for(j=1;j<n;j++)
   {
     s=(LinkList)malloc(sizeof(struct LNode)); /* 其余結點 */
     scanf("%d",&s->data);
     q=*L;
     p=(*L)->next;
     while(p&&p->data<s->data) /* p沒到表尾，且所指元素值小于新值 */
     {
       q=p;
       p=p->next; /* 指針后移 */
     }
     s->next=q->next; /* 元素插在q的后面 */
     q->next=s;
   }
   return OK;
 }

 Status CreatDescend(LinkList *L,int n)
 { /* 按非升序建立n個元素的線性表 */
   int j;
   LinkList p,q,s;
   if(n<=0)
     return ERROR;
   InitList(L);
   printf("請輸入%d個元素:\n",n);
   s=(LinkList)malloc(sizeof(struct LNode)); /* 第一個結點 */
   scanf("%d",&s->data);
   s->next=NULL;
   (*L)->next=s;
   for(j=1;j<n;j++)
   {
     s=(LinkList)malloc(sizeof(struct LNode)); /* 其余結點 */
     scanf("%d",&s->data);
     q=*L;
     p=(*L)->next;
     while(p&&p->data>s->data) /* p沒到表尾，且所指元素值大于新值 */
     {
       q=p;
       p=p->next; /* 指針后移 */
     }
     s->next=q->next; /* 元素插在q的后面 */
     q->next=s;
   }
   return OK;
 }

 Status GetFirstElem(LinkList L,ElemType *e)
 { /* 返回表頭元素的值 */
   LinkList p=L->next;
   if(!p) /* 空表 */
     return ERROR;
   else /* 非空表 */
     *e=p->data;
   return OK;
 }