/* bo2-2.c 單鏈表線性表(存儲結構由c2-2.h定義)的基本操作(12個) */
 Status InitList(LinkList *L)
 { /* 操作結果：構造一個空的線性表L */
   *L=(LinkList)malloc(sizeof(struct LNode)); /* 產生頭結點,并使L指向此頭結點 */
   if(!*L) /* 存儲分配失敗 */
     exit(OVERFLOW);
   (*L)->next=NULL; /* 指針域為空 */
   return OK;
 }

 Status DestroyList(LinkList *L)
 { /* 初始條件：線性表L已存在。操作結果：銷毀線性表L */
   LinkList q;
   while(*L)
   {
     q=(*L)->next;
     free(*L);
     *L=q;
   }
   return OK;
 }

 Status ClearList(LinkList L) /* 不改變L */
 { /* 初始條件：線性表L已存在。操作結果：將L重置為空表 */
   LinkList p,q;
   p=L->next; /* p指向第一個結點 */
   while(p) /* 沒到表尾 */
   {
     q=p->next;
     free(p);
     p=q;
   }
   L->next=NULL; /* 頭結點指針域為空 */
   return OK;
 }

 Status ListEmpty(LinkList L)
 { /* 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */
   if(L->next) /* 非空 */
     return FALSE;
   else
     return TRUE;
 }

 int ListLength(LinkList L)
 { /* 初始條件：線性表L已存在。操作結果：返回L中數據元素個數 */
   int i=0;
   LinkList p=L->next; /* p指向第一個結點 */
   while(p) /* 沒到表尾 */
   {
     i++;
     p=p->next;
   }
   return i;
 }

 Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
 { /* L為帶頭結點的單鏈表的頭指針。當第i個元素存在時,其值賦給e并返回OK,否則返回ERROR */
   int j=1; /* j為計數器 */
   LinkList p=L->next; /* p指向第一個結點 */
   while(p&&j<i) /* 順指針向后查找,直到p指向第i個元素或p為空 */
   {
     p=p->next;
     j++;
   }
   if(!p||j>i) /* 第i個元素不存在 */
     return ERROR;
   *e=p->data; /* 取第i個元素 */
   return OK;
 }

 int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { /* 初始條件: 線性表L已存在,compare()是數據元素判定函數(滿足為1,否則為0) */
   /* 操作結果: 返回L中第1個與e滿足關系compare()的數據元素的位序。 */
   /*           若這樣的數據元素不存在,則返回值為0 */
   int i=0;
   LinkList p=L->next;
   while(p)
   {
     i++;
     if(compare(p->data,e)) /* 找到這樣的數據元素 */
       return i;
     p=p->next;
   }
   return 0;
 }

 Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
 { /* 初始條件: 線性表L已存在 */
   /* 操作結果: 若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅, */
   /*           返回OK;否則操作失敗,pre_e無定義,返回INFEASIBLE */
   LinkList q,p=L->next; /* p指向第一個結點 */
   while(p->next) /* p所指結點有后繼 */
   {
     q=p->next; /* q為p的后繼 */
     if(q->data==cur_e)
     {
       *pre_e=p->data;
       return OK;
     }
     p=q; /* p向后移 */
   }
   return INFEASIBLE;
 }

 Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
 { /* 初始條件：線性表L已存在 */
   /* 操作結果：若cur_e是L的數據元素，且不是最后一個，則用next_e返回它的后繼， */
   /*           返回OK;否則操作失敗，next_e無定義，返回INFEASIBLE */
   LinkList p=L->next; /* p指向第一個結點 */
   while(p->next) /* p所指結點有后繼 */
   {
     if(p->data==cur_e)
     {
       *next_e=p->next->data;
       return OK;
     }
     p=p->next;
   }
   return INFEASIBLE;
 }

 Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改變L */
 { /* 在帶頭結點的單鏈線性表L中第i個位置之前插入元素e */
   int j=0;
   LinkList p=L,s;
   while(p&&j<i-1) /* 尋找第i-1個結點 */
   {
     p=p->next;
     j++;
   }
   if(!p||j>i-1) /* i小于1或者大于表長 */
     return ERROR;
   s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */
   s->data=e; /* 插入L中 */
   s->next=p->next;
   p->next=s;
   return OK;
 }

 Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改變L */
 { /* 在帶頭結點的單鏈線性表L中，刪除第i個元素,并由e返回其值 */
   int j=0;
   LinkList p=L,q;
   while(p->next&&j<i-1) /* 尋找第i個結點,并令p指向其前趨 */
   {
     p=p->next;
     j++;
   }
   if(!p->next||j>i-1) /* 刪除位置不合理 */
     return ERROR;
   q=p->next; /* 刪除并釋放結點 */
   p->next=q->next;
   *e=q->data;
   free(q);
   return OK;
 }

 Status ListTraverse(LinkList L,void(*vi)(ElemType))
 /* vi的形參類型為ElemType，與bo2-1.c中相應函數的形參類型ElemType&不同 */
 { /* 初始條件：線性表L已存在 */
   /* 操作結果:依次對L的每個數據元素調用函數vi()。一旦vi()失敗,則操作失敗 */
   LinkList p=L->next;
   while(p)
   {
     vi(p->data);
     p=p->next;
   }
   printf("\n");
   return OK;
 }