/* algo2-8.c 實(shí)現(xiàn)算法2.17的程序 */
 #include"c1.h"
 #define N 2
 typedef char ElemType;
 #include"c2-3.h"
 #include"bo2-3.c"
 #include"bo2-32.c"

 void difference(SLinkList space,int *S) /* 算法2.17 */
 { /* 依次輸入集合A和B的元素，在一維數(shù)組space中建立表示集合(A-B)∪(B-A) */
   /* 的靜態(tài)鏈表，S為其頭指針。假設(shè)備用空間足夠大，space[0].cur為備用空間的頭指針 */
   int r,p,m,n,i,j,k;
   ElemType b;
   InitSpace(space); /* 初始化備用空間 */
   *S=Malloc(space); /* 生成S的頭結(jié)點(diǎn) */
   r=*S; /* r指向S的當(dāng)前最后結(jié)點(diǎn) */
   printf("請(qǐng)輸入集合A和B的元素個(gè)數(shù)m,n:");
   scanf("%d,%d%*c",&m,&n); /* %*c吃掉回車符 */
   printf("請(qǐng)輸入集合A的元素（共%d個(gè)）:",m);
   for(j=1;j<=m;j++) /* 建立集合A的鏈表 */
   {
     i=Malloc(space); /* 分配結(jié)點(diǎn) */
     scanf("%c",&space[i].data); /* 輸入A的元素值 */
     space[r].cur=i; /* 插入到表尾 */
     r=i;
   }
   scanf("%*c"); /* %*c吃掉回車符 */
   space[r].cur=0; /* 尾結(jié)點(diǎn)的指針為空 */
   printf("請(qǐng)輸入集合B的元素（共%d個(gè)）:",n);
   for(j=1;j<=n;j++)
   { /* 依次輸入B的元素,若不在當(dāng)前表中,則插入,否則刪除 */
     scanf("%c",&b);
     p=*S;
     k=space[*S].cur; /* k指向集合A中的第一個(gè)結(jié)點(diǎn) */
     while(k!=space[r].cur&&space[k].data!=b)
     { /* 在當(dāng)前表中查找 */
       p=k;
       k=space[k].cur;
     }
     if(k==space[r].cur)
     { /* 當(dāng)前表中不存在該元素，插入在r所指結(jié)點(diǎn)之后，且r的位置不變 */
       i=Malloc(space);
       space[i].data=b;
       space[i].cur=space[r].cur;
       space[r].cur=i;
     }
     else /* 該元素已在表中，刪除之 */
     {
       space[p].cur=space[k].cur;
       Free(space,k);
       if(r==k)
         r=p; /* 若刪除的是尾元素，則需修改尾指針 */
     }
   }
 }

 void visit(ElemType c)
 {
   printf("%c ",c);
 }

 void main()
 {
   int k;
   SLinkList s;
   difference(s,&k);
   ListTraverse(s,k,visit);
 }