[说明] 假设设A和B均为顺序表，A’和B’分别为A和B中除去最大共同前缀后的子表(例如，A=(x，y，y，z，x，z)，B=(x，y，y，z，y，x，x，z)，则两者中最大的共同前缀为(x，y，y，z)，在两表中除去最大共同前缀后的子表分别为A’=(x，z)和B’=(y，x，x，z)。若A’=B’=空表，则A=B；若A’=空表，而 B’!=空表，或者两者均不为空表，且A’的首先小于B’的首元，则A＜B；否则A＞B。 下面程序实现了比较A、B大小的算法。 [C程序] #include＜stdio.h＞ #include＜stdlib.h＞ typedef struct linknode { int data; struct linknode *next; }node: node *creatlist ( ) /*建立单链表*/{ node*head, *r, *s; int x; head= (node *) malloc (sizeof (node)); /建立单链表的头结点head*/ r=head; printf ("输入系列整数，以O标志结束\n"); scanf ("%d", &x); while (x!=O) /*x==O则退出while循环*/ { s=(node*) malloc (sizeof (node)); s-＞data=x; r-＞next=s; s-＞next=NULL; r=s; scanf ("%d", &x); } r-＞next=NULL; s=head; (1); Free (s); return head;}void subs ( ){ node*p, *p1, *p2, *q, *heada, *headb; heada=creatlist ( ) ; headb=creatlist ( ) ; p=heada; p1=p; /*p1指向p所指结点的前一个结点，开始时均缀向头结点*/ while (p!=NULL ) { q=headb; while (q!=NULL&&q-＞data!=p-＞data) q=q-＞next; if ( (2) ) { if (p==heada) { (3) ; p1=heada; }else if (p-＞next==NULL) p1-＞next=NULL; /*该结点为最后一结点，删除*/ else p1-＞next=p-＞next; p2=p-＞next;(4) ; free (p);(5) ; } else /*p所指结点的元素不在B中，则直接下移p*/ { p1=p;(6) ; }}p=heada; /*显示删除后的结果*/if (p==NULL) printf ("两集合机减的结果为空\n");else printf ("两集合相减的结果\n");while (p!=NULL){ printf ("%d", p-＞data); p=p-＞next;}}void main ( ){ subs ( ) ;}
