问答题 设计一个求两个集合A和B之差C=A—B的程序,即当且仅当e是A的一个元素,但不是B中的一个元素时,e才是c中的一个元素。集合用有序链表实现,初始时,A、B集合中的元素按递增排列,C为空;操作完成后,A、B保持不变,C中元素按递增排列。下面的函数append(1ast,e)是把值为e的新结点链接在由指针last指向的结点的后面,并返回新结点的地址;函数difference(A,B)实现集合运算A—B,并返回表示结果集合C的链表的首结点的地址。在执行A—B运算之前,用于表示结果集合的链表首先增加一个附加的表头结点,以便新结点的添加,当A—B运算执行完毕后,再删除并释放表示结果集合的链表的表头结点。【上海大学2000年】 typedef struct node( int element; struct node*link; }NODEj NODE*A,*B,*C; NODE *append (NODE *last,in七e) { last一>link=(NODE*)malloc(sizeof(NODE)); last一>link一>element=e; return (1ast一>link); } NODE*dlf ference(NOI)E*A,N0 L)E*B) { }
【正确答案】正确答案:算法的基本设计思想:对两个链表进行归并,但当A的一个元素不是B中的一个元素时,才将其加入到新链表C中。算法的代码: LNode *difference(LNode*A,LNode*B)( LNode*C,*1ast, C=1ast=(LNode*)malloc(Sizeof(LNode)), while(A!=NULL&&B!=NULL) //两表均未空时循环 { if(A->elementelement) { last=append(1ast,A一>element); A=A->1ink; } else if(A一>element==B一>element) { //两表中相等元素不作结果:元素 A=A->1ink; B=B一>1ink; } else B=B一>link; //向后移动B表指针 } whlle(A!=NULL) { 1ast=append(1ast,A一>element), A=A一>1ink; } 1ast一>1ink=NULL; //置链表尾 1ast=C; C=C一>1ink; free(1ast); return C; }//difference
【答案解析】