/* bo2-6.c 具有實(shí)用意義的線性鏈表(存儲(chǔ)結(jié)構(gòu)由c2-5.h定義)的24個(gè)基本操作 */
 Status MakeNode(Link *p,ElemType e)
 { /* 分配由p指向的值為e的結(jié)點(diǎn)，并返回OK；若分配失敗。則返回ERROR */
   *p=(Link)malloc(sizeof(LNode));
   if(!*p)
     return ERROR;
   (*p)->data=e;
   return OK;
 }

 void FreeNode(Link *p)
 { /* 釋放p所指結(jié)點(diǎn) */
   free(*p);
   *p=NULL;
 }

 Status InitList(LinkList *L)
 { /* 構(gòu)造一個(gè)空的線性鏈表 */
   Link p;
   p=(Link)malloc(sizeof(LNode)); /* 生成頭結(jié)點(diǎn) */
   if(p)
   {
     p->next=NULL;
     (*L).head=(*L).tail=p;
     (*L).len=0;
     return OK;
   }
   else
     return ERROR;
 }

 Status ClearList(LinkList *L)
 { /* 將線性鏈表L重置為空表，并釋放原鏈表的結(jié)點(diǎn)空間 */
   Link p,q;
   if((*L).head!=(*L).tail)/* 不是空表 */
   {
     p=q=(*L).head->next;
     (*L).head->next=NULL;
     while(p!=(*L).tail)
     {
       p=q->next;
       free(q);
       q=p;
     }
     free(q);
     (*L).tail=(*L).head;
     (*L).len=0;
   }
   return OK;
 }

 Status DestroyList(LinkList *L)
 { /* 銷毀線性鏈表L，L不再存在 */
   ClearList(L); /* 清空鏈表 */
   FreeNode(&(*L).head);
   (*L).tail=NULL;
   (*L).len=0;
   return OK;
 }

 Status InsFirst(LinkList *L,Link h,Link s) /* 形參增加L,因?yàn)樾栊薷腖 */
 { /* h指向L的一個(gè)結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前 */
   s->next=h->next;
   h->next=s;
   if(h==(*L).tail) /* h指向尾結(jié)點(diǎn) */
     (*L).tail=h->next; /* 修改尾指針 */
   (*L).len++;
   return OK;
 }

 Status DelFirst(LinkList *L,Link h,Link *q) /* 形參增加L,因?yàn)樾栊薷腖 */
 { /* h指向L的一個(gè)結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，刪除鏈表中的第一個(gè)結(jié)點(diǎn)并以q返回。 */
   /* 若鏈表為空(h指向尾結(jié)點(diǎn))，q=NULL，返回FALSE */
   *q=h->next;
   if(*q) /* 鏈表非空 */
   {
     h->next=(*q)->next;
     if(!h->next) /* 刪除尾結(jié)點(diǎn) */
       (*L).tail=h; /* 修改尾指針 */
     (*L).len--;
     return OK;
   }
   else
     return FALSE; /* 鏈表空 */
 }

 Status Append(LinkList *L,Link s)
 { /* 將指針s(s->data為第一個(gè)數(shù)據(jù)元素)所指(彼此以指針相鏈,以NULL結(jié)尾)的 */
   /* 一串結(jié)點(diǎn)鏈接在線性鏈表L的最后一個(gè)結(jié)點(diǎn)之后,并改變鏈表L的尾指針指向新 */
   /* 的尾結(jié)點(diǎn) */
   int i=1;
   (*L).tail->next=s;
   while(s->next)
   {
     s=s->next;
     i++;
   }
   (*L).tail=s;
   (*L).len+=i;
   return OK;
 }

 Position PriorPos(LinkList L,Link p)
 { /* 已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接前驅(qū)的位置 */
   /* 若無(wú)前驅(qū)，則返回NULL */
   Link q;
   q=L.head->next;
   if(q==p) /* 無(wú)前驅(qū) */
     return NULL;
   else
   {
     while(q->next!=p) /* q不是p的直接前驅(qū) */
       q=q->next;
     return q;
   }
 }

 Status Remove(LinkList *L,Link *q)
 { /* 刪除線性鏈表L中的尾結(jié)點(diǎn)并以q返回，改變鏈表L的尾指針指向新的尾結(jié)點(diǎn) */
   Link p=(*L).head;
   if((*L).len==0) /* 空表 */
   {
     *q=NULL;
     return FALSE;
   }
   while(p->next!=(*L).tail)
     p=p->next;
   *q=(*L).tail;
   p->next=NULL;
   (*L).tail=p;
   (*L).len--;
   return OK;
 }

 Status InsBefore(LinkList *L,Link *p,Link s)
 { /* 已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在p所指結(jié)點(diǎn)之前， */
   /* 并修改指針p指向新插入的結(jié)點(diǎn) */
   Link q;
   q=PriorPos(*L,*p); /* q是p的前驅(qū) */
   if(!q) /* p無(wú)前驅(qū) */
     q=(*L).head;
   s->next=*p;
   q->next=s;
   *p=s;
   (*L).len++;
   return OK;
 }

 Status InsAfter(LinkList *L,Link *p,Link s)
 { /* 已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在p所指結(jié)點(diǎn)之后， */
   /* 并修改指針p指向新插入的結(jié)點(diǎn) */
   if(*p==(*L).tail) /* 修改尾指針 */
     (*L).tail=s;
   s->next=(*p)->next;
   (*p)->next=s;
   *p=s;
   (*L).len++;
   return OK;
 }

 Status SetCurElem(Link p,ElemType e)
 { /* 已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，用e更新p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值 */
   p->data=e;
   return OK;
 }

 ElemType GetCurElem(Link p)
 { /* 已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值 */
   return p->data;
 }

 Status ListEmpty(LinkList L)
 { /* 若線性鏈表L為空表，則返回TRUE，否則返回FALSE */
   if(L.len)
     return FALSE;
   else
     return TRUE;
 }

 int ListLength(LinkList L)
 { /* 返回線性鏈表L中元素個(gè)數(shù) */
   return L.len;
 }

 Position GetHead(LinkList L)
 { /* 返回線性鏈表L中頭結(jié)點(diǎn)的位置 */
   return L.head;
 }

 Position GetLast(LinkList L)
 { /* 返回線性鏈表L中最后一個(gè)結(jié)點(diǎn)的位置 */
   return L.tail;
 }

 Position NextPos(Link p)
 { /* 已知p指向線性鏈表L中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接后繼的位置 */
   /* 若無(wú)后繼，則返回NULL */
   return p->next;
 }

 Status LocatePos(LinkList L,int i,Link *p)
 { /* 返回p指示線性鏈表L中第i個(gè)結(jié)點(diǎn)的位置，并返回OK，i值不合法時(shí)返回ERROR */
   /* i=0為頭結(jié)點(diǎn) */
   int j;
   if(i<0||i>L.len)
     return ERROR;
   else
   {
     *p=L.head;
     for(j=1;j<=i;j++)
       *p=(*p)->next;
     return OK;
   }
 }

 Position LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType))
 { /* 返回線性鏈表L中第1個(gè)與e滿足函數(shù)compare()判定關(guān)系的元素的位置， */
   /* 若不存在這樣的元素，則返回NULL */
   Link p=L.head;
   do
     p=p->next;
   while(p&&!(compare(p->data,e))); /* 沒(méi)到表尾且沒(méi)找到滿足關(guān)系的元素 */
   return p;
 }

 Status ListTraverse(LinkList L,void(*visit)(ElemType))
 { /* 依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗 */
   Link p=L.head->next;
   int j;
   for(j=1;j<=L.len;j++)
   {
     visit(p->data);
     p=p->next;
   }
   printf("\n");
   return OK;
 }

 Status OrderInsert(LinkList *L,ElemType e,int (*comp)(ElemType,ElemType))
 { /* 已知L為有序線性鏈表，將元素e按非降序插入在L中。（用于一元多項(xiàng)式） */
   Link o,p,q;
   q=(*L).head;
   p=q->next;
   while(p!=NULL&&comp(p->data,e)<0) /* p不是表尾且元素值小于e */
   {
     q=p;
     p=p->next;
   }
   o=(Link)malloc(sizeof(LNode)); /* 生成結(jié)點(diǎn) */
   o->data=e; /* 賦值 */
   q->next=o; /* 插入 */
   o->next=p;
   (*L).len++; /* 表長(zhǎng)加1 */
   if(!p) /* 插在表尾 */
     (*L).tail=o; /* 修改尾結(jié)點(diǎn) */
   return OK;
 }

 Status LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType))
 { /* 若升序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素，則q指示L中 */
   /* 第一個(gè)值為e的結(jié)點(diǎn)的位置，并返回TRUE；否則q指示第一個(gè)與e滿足判定函數(shù) */
   /* compare()取值>0的元素的前驅(qū)的位置。并返回FALSE。（用于一元多項(xiàng)式） */
   Link p=L.head,pp;
   do
   {
     pp=p;
     p=p->next;
   }while(p&&(compare(p->data,e)<0)); /* 沒(méi)到表尾且p->data.expn<e.expn */
   if(!p||compare(p->data,e)>0) /* 到表尾或compare(p->data,e)>0 */
   {
     *q=pp;
     return FALSE;
   }
   else /* 找到 */
   {
     *q=p;
     return TRUE;
   }
 }