/* c2-2.h 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) */ struct LNode {  ElemType data;  struct LNode *next; }; typedef struct LNode *LinkList; /* 另一種定義LinkList的方法 */

/* bo2-2.c 單鏈表線性表(存儲(chǔ)結(jié)構(gòu)由c2-2.h定義)的基本操作(12個(gè)) */ Status InitList(LinkList *L) { /* 操作結(jié)果：構(gòu)造一個(gè)空的線性表L */  *L=(LinkList)malloc(sizeof(struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) */  if(!*L) /* 存儲(chǔ)分配失敗 */   exit(OVERFLOW);  (*L)->next=NULL; /* 指針域?yàn)榭?*/  return OK; } Status DestroyList(LinkList *L) { /* 初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L */  LinkList q;  while(*L)  {   q=(*L)->next;   free(*L);   *L=q;  }  return OK; } Status ClearList(LinkList L) /* 不改變L */ { /* 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表 */  LinkList p,q;  p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */  while(p) /* 沒(méi)到表尾 */  {   q=p->next;   free(p);   p=q;  }  L->next=NULL; /* 頭結(jié)點(diǎn)指針域?yàn)榭?*/  return OK; } Status ListEmpty(LinkList L) { /* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */  if(L->next) /* 非空 */   return FALSE;  else   return TRUE; } int ListLength(LinkList L) { /* 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */  int i=0;  LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */  while(p) /* 沒(méi)到表尾 */  {   i++;   p=p->next;  }  return i; } Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */ { /* L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí),其值賦給e并返回OK,否則返回ERROR */  int j=1; /* j為計(jì)數(shù)器 */  LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */  while(p&&j<i) /* 順指針向后查找,直到p指向第i個(gè)元素或p為空 */  {   p=p->next;   j++;  }  if(!p||j>i) /* 第i個(gè)元素不存在 */   return ERROR;  *e=p->data; /* 取第i個(gè)元素 */  return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始條件: 線性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) */  /* 操作結(jié)果: 返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 */  /*      若這樣的數(shù)據(jù)元素不存在,則返回值為0 */  int i=0;  LinkList p=L->next;  while(p)  {   i++;   if(compare(p->data,e)) /* 找到這樣的數(shù)據(jù)元素 */    return i;   p=p->next;  }  return 0; } Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { /* 初始條件: 線性表L已存在 */  /* 操作結(jié)果: 若cur_e是L的數(shù)據(jù)元素,且不是第一個(gè),則用pre_e返回它的前驅(qū), */  /*      返回OK;否則操作失敗,pre_e無(wú)定義,返回INFEASIBLE */  LinkList q,p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */  while(p->next) /* p所指結(jié)點(diǎn)有后繼 */  {   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已存在 */  /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼， */  /*      返回OK;否則操作失敗，next_e無(wú)定義，返回INFEASIBLE */  LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */  while(p->next) /* p所指結(jié)點(diǎn)有后繼 */  {   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 */ { /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中第i個(gè)位置之前插入元素e */  int j=0;  LinkList p=L,s;  while(p&&j<i-1) /* 尋找第i-1個(gè)結(jié)點(diǎn) */  {   p=p->next;   j++;  }  if(!p||j>i-1) /* i小于1或者大于表長(zhǎng) */   return ERROR;  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */  s->data=e; /* 插入L中 */  s->next=p->next;  p->next=s;  return OK; } Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改變L */ { /* 在帶頭結(jié)點(diǎn)的單鏈線性表L中，刪除第i個(gè)元素,并由e返回其值 */  int j=0;  LinkList p=L,q;  while(p->next&&j<i-1) /* 尋找第i個(gè)結(jié)點(diǎn),并令p指向其前趨 */  {   p=p->next;   j++;  }  if(!p->next||j>i-1) /* 刪除位置不合理 */   return ERROR;  q=p->next; /* 刪除并釋放結(jié)點(diǎn) */  p->next=q->next;  *e=q->data;  free(q);  return OK; } Status ListTraverse(LinkList L,void(*vi)(ElemType)) /* vi的形參類型為ElemType，與bo2-1.c中相應(yīng)函數(shù)的形參類型ElemType&不同 */ { /* 初始條件：線性表L已存在 */  /* 操作結(jié)果:依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗,則操作失敗 */  LinkList p=L->next;  while(p)  {   vi(p->data);   p=p->next;  }  printf("/n");  return OK; }

/* algo2-5.c 主程序 */ #include"c1.h" typedef int ElemType; #include"c2-2.h" #include"bo2-2.c" void CreateList(LinkList *L,int n) /* 算法2.11 */ { /* 逆位序(插在表頭)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表L */  int i;  LinkList p;  *L=(LinkList)malloc(sizeof(struct LNode));  (*L)->next=NULL; /* 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */  printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)/n",n);  for(i=n;i>0;--i)  {   p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */   scanf("%d",&p->data); /* 輸入元素值 */   p->next=(*L)->next; /* 插入到表頭 */   (*L)->next=p;  } } void CreateList2(LinkList *L,int n) { /* 正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 */  int i;  LinkList p,q;  *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成頭結(jié)點(diǎn) */  (*L)->next=NULL;  q=*L;  printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)/n",n);  for(i=1;i<=n;i++)  {   p=(LinkList)malloc(sizeof(struct LNode));   scanf("%d",&p->data);   q->next=p;   q=q->next;  }  p->next=NULL; } void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法2.12 */ { /* 已知單鏈線性表La和Lb的元素按值非遞減排列。 */  /* 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列 */  LinkList pa=La->next,pb=(*Lb)->next,pc;  *Lc=pc=La; /* 用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) */  while(pa&&pb)   if(pa->data<=pb->data)   {    pc->next=pa;    pc=pa;    pa=pa->next;   }   else   {    pc->next=pb;    pc=pb;    pb=pb->next;   }  pc->next=pa?pa:pb; /* 插入剩余段 */  free(*Lb); /* 釋放Lb的頭結(jié)點(diǎn) */  Lb=NULL; } void visit(ElemType c) /* ListTraverse()調(diào)用的函數(shù)(類型要一致) */ {  printf("%d ",c); } void main() {  int n=5;  LinkList La,Lb,Lc;  printf("按非遞減順序, ");  CreateList2(&La,n); /* 正位序輸入n個(gè)元素的值 */  printf("La="); /* 輸出鏈表La的內(nèi)容 */  ListTraverse(La,visit);  printf("按非遞增順序, ");  CreateList(&Lb,n); /* 逆位序輸入n個(gè)元素的值 */  printf("Lb="); /* 輸出鏈表Lb的內(nèi)容 */  ListTraverse(Lb,visit);  MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并La和Lb,得到新表Lc */  printf("Lc="); /* 輸出鏈表Lc的內(nèi)容 */  ListTraverse(Lc,visit); }