/* c2-2.h 線性表的單鏈表存儲結構 */ struct LNode {  ElemType data;  struct LNode *next; }; typedef struct LNode *LinkList; /* 另一種定義LinkList的方法 */

/* bo2-4.c 設立尾指針的單循環鏈表(存儲結構由c2-2.h定義)的12個基本操作 */ Status InitList_CL(LinkList *L) { /* 操作結果：構造一個空的線性表L */  *L=(LinkList)malloc(sizeof(struct LNode)); /* 產生頭結點,并使L指向此頭結點 */  if(!*L) /* 存儲分配失敗 */   exit(OVERFLOW);  (*L)->next=*L; /* 指針域指向頭結點 */  return OK; } Status DestroyList_CL(LinkList *L) { /* 操作結果：銷毀線性表L */  LinkList q,p=(*L)->next; /* p指向頭結點 */  while(p!=*L) /* 沒到表尾 */  {   q=p->next;   free(p);   p=q;  }  free(*L);  *L=NULL;  return OK; } Status ClearList_CL(LinkList *L) /* 改變L */ { /* 初始條件：線性表L已存在。操作結果：將L重置為空表 */  LinkList p,q;  *L=(*L)->next; /* L指向頭結點 */  p=(*L)->next; /* p指向第一個結點 */  while(p!=*L) /* 沒到表尾 */  {   q=p->next;   free(p);   p=q;  }  (*L)->next=*L; /* 頭結點指針域指向自身 */  return OK; } Status ListEmpty_CL(LinkList L) { /* 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */  if(L->next==L) /* 空 */   return TRUE;  else   return FALSE; } int ListLength_CL(LinkList L) { /* 初始條件：L已存在。操作結果：返回L中數據元素個數 */  int i=0;  LinkList p=L->next; /* p指向頭結點 */  while(p!=L) /* 沒到表尾 */  {   i++;   p=p->next;  }  return i; } Status GetElem_CL(LinkList L,int i,ElemType *e) { /* 當第i個元素存在時,其值賦給e并返回OK,否則返回ERROR */  int j=1; /* 初始化,j為計數器 */  LinkList p=L->next->next; /* p指向第一個結點 */  if(i<=0||i>ListLength_CL(L)) /* 第i個元素不存在 */   return ERROR;  while(j<i)  { /* 順指針向后查找,直到p指向第i個元素 */   p=p->next;   j++;  }  *e=p->data; /* 取第i個元素 */  return OK; } int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始條件：線性表L已存在，compare()是數據元素判定函數 */  /* 操作結果：返回L中第1個與e滿足關系compare()的數據元素的位序。 */  /*      若這樣的數據元素不存在，則返回值為0 */  int i=0;  LinkList p=L->next->next; /* p指向第一個結點 */  while(p!=L->next)  {   i++;   if(compare(p->data,e)) /* 滿足關系 */    return i;   p=p->next;  }  return 0; } Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e) { /* 初始條件：線性表L已存在 */  /* 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅， */  /*      否則操作失敗，pre_e無定義 */  LinkList q,p=L->next->next; /* p指向第一個結點 */  q=p->next;  while(q!=L->next) /* p沒到表尾 */  {   if(q->data==cur_e)   {    *pre_e=p->data;    return TRUE;   }   p=q;   q=q->next;  }  return FALSE; } Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e) { /* 初始條件：線性表L已存在 */  /* 操作結果：若cur_e是L的數據元素,且不是最后一個,則用next_e返回它的后繼， */  /*      否則操作失敗，next_e無定義 */  LinkList p=L->next->next; /* p指向第一個結點 */  while(p!=L) /* p沒到表尾 */  {   if(p->data==cur_e)   {    *next_e=p->next->data;    return TRUE;   }   p=p->next;  }  return FALSE; } Status ListInsert_CL(LinkList *L,int i,ElemType e) /* 改變L */ { /* 在L的第i個位置之前插入元素e */  LinkList p=(*L)->next,s; /* p指向頭結點 */  int j=0;  if(i<=0||i>ListLength_CL(*L)+1) /* 無法在第i個元素之前插入 */   return ERROR;  while(j<i-1) /* 尋找第i-1個結點 */  {   p=p->next;   j++;  }  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */  s->data=e; /* 插入L中 */  s->next=p->next;  p->next=s;  if(p==*L) /* 改變尾結點 */   *L=s;  return OK; } Status ListDelete_CL(LinkList *L,int i,ElemType *e) /* 改變L */ { /* 刪除L的第i個元素,并由e返回其值 */  LinkList p=(*L)->next,q; /* p指向頭結點 */  int j=0;  if(i<=0||i>ListLength_CL(*L)) /* 第i個元素不存在 */   return ERROR;  while(j<i-1) /* 尋找第i-1個結點 */  {   p=p->next;   j++;  }  q=p->next; /* q指向待刪除結點 */  p->next=q->next;  *e=q->data;  if(*L==q) /* 刪除的是表尾元素 */   *L=p;  free(q); /* 釋放待刪除結點 */  return OK; } Status ListTraverse_CL(LinkList L,void(*vi)(ElemType)) { /* 初始條件:L已存在。操作結果:依次對L的每個數據元素調用函數vi()。一旦vi()失敗,則操作失敗 */  LinkList p=L->next->next;  while(p!=L->next)  {   vi(p->data);   p=p->next;  }  printf("/n");  return OK; }

/* main2-4.c 單循環鏈表,檢驗bo2-4.c的主程序 */ #include"c1.h" typedef int ElemType; #include"c2-2.h" #include"bo2-4.c" Status compare(ElemType c1,ElemType c2) {  if(c1==c2)   return TRUE;  else   return FALSE; } void visit(ElemType c) {  printf("%d ",c); } void main() {  LinkList L;  ElemType e;  int j;  Status i;  i=InitList_CL(&L); /* 初始化單循環鏈表L */  printf("初始化單循環鏈表L i=%d (1:初始化成功)/n",i);  i=ListEmpty_CL(L);  printf("L是否空 i=%d(1:空 0:否)/n",i);  ListInsert_CL(&L,1,3); /* 在L中依次插入3,5 */  ListInsert_CL(&L,2,5);  i=GetElem_CL(L,1,&e);  j=ListLength_CL(L);  printf("L中數據元素個數=%d,第1個元素的值為%d。/n",j,e);  printf("L中的數據元素依次為：");  ListTraverse_CL(L,visit);  PriorElem_CL(L,5,&e); /* 求元素5的前驅 */  printf("5前面的元素的值為%d。/n",e);  NextElem_CL(L,3,&e); /* 求元素3的后繼 */  printf("3后面的元素的值為%d。/n",e);  printf("L是否空 %d(1:空 0:否)/n",ListEmpty_CL(L));  j=LocateElem_CL(L,5,compare);  if(j)   printf("L的第%d個元素為5。/n",j);  else   printf("不存在值為5的元素/n");  i=ListDelete_CL(&L,2,&e);  printf("刪除L的第2個元素：/n");  if(i)  {   printf("刪除的元素值為%d,現在L中的數據元素依次為：",e);   ListTraverse_CL(L,visit);  }  else   printf("刪除不成功！/n");  printf("清空L：%d(1: 成功)/n",ClearList_CL(&L));  printf("清空L后，L是否空：%d(1:空 0:否)/n",ListEmpty_CL(L));  printf("銷毀L：%d(1: 成功)/n",DestroyList_CL(&L)); }