线性表算法设计题（四）

题目

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

算法思想

求两个集合A和B的差集是指在A中删除A和B中共有的元素，即删除链表中的数据域相等的结点。由于要删除结点，此题的关键点在于在遍历链表时，需要保存待删除结点的前驱。

完整代码

#include <iostream>
#include <stdlib.h>
using namespace std;

//已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数 

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

void ListRead(LinkList &L){
    //读取链表，即给链表添加数据 
    int length;
    LinkList  p = NULL, q;
    cout << "Input the length:";
    cin >> length;
    L = (LinkList)malloc(sizeof(struct LNode));
    L -> next = NULL;
    q = L;
    for(int i = 0; i < length; ++ i){
        p = (LinkList)malloc(sizeof(struct LNode));     //生成头结点 
        cin >> p -> data;
        q -> next = p;
        q = q -> next;
    }
    p -> next = NULL;
}

void Difference(LinkList &La, LinkList &Lb, int &n){
    //La和Lb差集的结果存储在La中，n是结果集合中元素个数，调用时为0 
    LinkList pa, pb, pre, u;
    pa = La -> next;                           //pa是链表La的工作指针，初始化为首元结点 
    pb = pb -> next;                           //pb是链表Lb的工作指针，初始化为首元结点  
    pre = La;                                  //pre为La中pa所指结点的前驱结点的指针 
    while(pa && pb){
        if(pa -> data < pb -> data){           //A链表中当前结点指针后移 
            n ++;
            pre = pa;
            pa = pa -> next;
        }
        else if(pa -> data > pb -> data){
            pb = pb -> next;                   //B链表中当前结点指针后移 
        }
        else{                                  //在La表删除La和Lb中元素相同的结点 
            pre -> next = pa -> next;
            u = pa;
            pa = pa -> next;
            delete u;                          //删除结点 
        }
    }
}

void ListPrint(LinkList L){
    //打印链表 
    LNode *p;
    p = L -> next;
    if(L -> next == NULL){
        cout << "NULL" << endl;
    }
    while(p){
        cout << p -> data << "\t";
        p = p -> next;
    }
    cout << endl; 
}

int main(){
    LinkList La, Lb;
    int n = 0;
    ListRead(La);
    ListRead(Lb);
    Difference(La, Lb, n);
    cout << "链表A和链表B的差集为：" << endl; 
    ListPrint(La); 
    return 0;
}

结果显示

5NHU19YRN(DD1KNY}AJ854R.png