数据结构实践——“求两集合交集”的一个错解分析

　　本文点评一位学生对基于线性表存储集合，然后对集合进行求并运算的错解，供学习者参考。

【项目 - 求集合并集】
　　假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即线性表中的数据元素即为集合中的成员。设计算法，用函数unionList(List LA, List LB, List &LC )函数实现该算法，求一个新的集合C=A∪B，即将两个集合的并集放在线性表LC中。

提示：
（1）除了实现unnionList函数外，还需要在main函数中设计代码，调用unionList进行测试和演示；
（2）可以充分利用前面建好的算法库[点击…]，在程序头部直接加 #include<list.h>即可（工程中最普遍的方法，建议采纳）；
（3）也可以将实现算法中需要的线性表的基本运算对应的函数，与自己设计的所有程序放在同一个文件中。

【点这儿…】可以看课程中提供参考解答。

【错解】

#include <stdio.h>
#include "list.h"

void unionList(SqList *LA, SqList *LB, SqList *&LC)
{
    int e;
    int lena=LA->length;
    LC = LA;
    for (int i = 0; i <LA->length; i++)
    {
        if (LA->data[i] != LB->data[i])
        {
            ListInsert(LC, lena++, LB->data[i]);
        }
    }
    DispList(LC);
}

int main()
{
    SqList *la, *lb, *lc;
    ElemType x[2] = {1,2};
    ElemType y[2] = {1,4,3}; //原文中只有{1,4}，为更好地反映问题，我增加1个元素3
    ElemType z[4];
    CreateList(la, x, 2);
    CreateList(lb, y, 3);
    CreateList(lc, z, 4);
    unionList(la, lb, lc);
    return 0;
}

【我的点评】
　　阅读代码知道，第8行LC=LA，意即从此LC指向的也就是LA指向的线性表了。对照题目要求，合并后的LC应该是一个新的线性表，此处处理不合要求。
　　若不考虑这一要求，LC=LA后，合并的结果就保存在LA（也是LC）中了。在内存访问的机制中，这是合法的。（这儿和内存管理中的什么堆区、栈区之类的没有关系。内存管理机制对于计算机类的学生很重要，但一般入门级阶段并不讲。）合法仅是在合乎语法要求的层面，事实上，LC原先指向的空间从此没有由任何变量指向，也没有被释放，成了“游离”的垃圾。　　
　　接下来的讨论，我们就以合并后的结果保存到LA中为起点。
　　第9-15行的处理，可以看出学生在算法设计时没有理清头绪。LA（LC）中已经是并集中的第一部分元素了，接下来，应该是“将LB中有，但LA没有的元素，加到LC中”（严格讲，“LB中的元素”指LB指针指向的线性表代表的集合中的元素，LA、LC同），代码没有体现出这层意思。为了完成这一任务，要考察LB中的每个元素，最外层的循环，应该针对的是LB，而不是LA。
　　故算法框架应该是：

    for (i = 0; i <LB->length; i++)
    {
        //若LB集合中的第i个元素不在原LA集合中，则将LB中的第i个元素加入到LC中
    }

　　如何知道“LB集合中的第i个元素不在原LA集合中”？这需要和LA集合中的元素逐个比较的！于是这里需要针对“原LA集合”构造一个循环，以便逐个比较。显然，11-14行的一个分支结构，仅完成“LA和LB相同序号的元素是否相等”，是不足以考察LA中的每一个元素的。于是上面是算法框架拓展为：

    for (i = 0; i <LB->length; i++)
    {
        for (j = 0; j <lena; j++)  
            //若LB->data[i] == LA->data[j]退出循环
        //循环中未出现相等的情形，则说明LB->data[i]未在LA中出现过，要将LB->data[i]加入

    }

　　于是，尽可能在原错误程序基础上修改，且合并后的结果LC实际就是LA的情况下，得到的完整代码为：

#include <stdio.h>
#include "list.h"

void unionList(SqList *LA, SqList *LB, SqList *&LC)
{
    int i,j;
    int lena,lenc;
    lena=lenc=LA->length;　//lena是原LA长度，lenc代表合并后的长度
    LC = LA;  //LC和LA将指同一个集合
    for (i = 0; i < LB->length; i++)
    {
        for (j = 0; j <lena; j++)
            if(LB->data[i] == LA->data[j])
                break;
        if(j>=lena)  //退出前面的循环是因为全找过了找不着，即在原LA中不存在
        {
            ListInsert(LC, ++lenc, LB->data[i]);
        }
    }
}

int main()
{
    SqList *la, *lb, *lc;
    ElemType x[2] = {1,2};
    ElemType y[3] = {1,4,3}; //原文中只有{1,4}，为更好地反映问题，我增加1个元素3
    //ElemType z[4];
    CreateList(la, x, 2);
    CreateList(lb, y, 3);
    //CreateList(lc, z, 4);
    unionList(la, lb, lc);
    DispList(lc);
    return 0;
}

　　需要强调的是，for (j = 0; j <lena; j++)中的lena是“原LA”的长度，不能用LA->length代替，因为在LA、LC混用的情况下，LA->length随着插入，是动态变化着的。
　　在原参考解答中，“插入LB中每一个元素”只用了一重循环，但要知道，实现if (!LocateElem(LA,e))的内部，“藏”对LA指向的每一个元素的扫描，是内含一层循环的，到算法库[点击…]中考察基本操作的实现可以验证这一说法。这种写法看起来更简单，也道出了我们应该用基本运算为单位进行思考的必要性。这是在学习数据结构中，应该养成的习惯。这是工程中用到的思维，代码写得出，还要写得好。
　　在上面的解答中，我将DispList(LC);放到main函数中了。unionList只管合并，不管别的任何事情。这是软件工程中“高内聚”的要求——一个模块尽可能只完成单一的工作。“显示结果”是“求并”以后做的工作，两者是“平级”的，不要将显示作为合并的一部分。
　　还有，新代码中的27和30（在原代码中也有）没有必要，这样创建了线性表，却在合并时直接将LC和LA共用空间了，何必呢，反倒使一块空间彻底成了垃圾。
　　在初学者的学习中，一定要争取自己写出来。可以参考一切可以用到的资料启发自己，给出自己的解答。写出这样的错解，也是好的成果，中间的思考、尝试过程是我们真正要的东西。这个过程价值连城。当自己已经经过一定的思考之后，再看一些相对规范的解法（例如本文中的参考解答），也是很必要的。观摩、阅读是学习方法。如果能在观摩中品到其味道，再去仿制一份，也便极好。