设有两个顺序表A和B,且都递增有序。试写一算法,从A中删除与B中相同的那些元素(也就是计算A—B)。
本题算法思想是:扫描整个B表,顺序取表中每个元素,然后与表A中从某下标开始的元素进行比较(因为两表都是有序的,不必每次从头开始,用一个变量k标识上一次比较结束的位置),当B中的某元素值大于或等于A的某个元素时,比较结束。记住A表的当前下标值k,之后再比较两元素值是否相等,若相等,则从表A中删除该元素,而后继续B中的下一个元 素与A中从第k个元素开始向后比较;否则,继续,……,直到B中所有元素比较完为止。具体算法如下: void SubList(SeqList*A,SeqList B) { int i,j,k; k=1; //记住A表的下标位置 for(i=1;i<=B.length;i++){ for(j=k;j<=A一>length;j++) if(B.data[i]=A一>data[j]){ //因为表是有序的,不必比较到最后 k=j;break; //用k记住A表的当前位置,以便下一次比较从k开始 } else continue; if(B.data[i-]==A—>data[k]) //相等表示有重复的 DeleteList(A,k); //调用删除函数,删除A中第k个元素 } }