线性表算法设计题（三）

题目

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并存放在A链表中。

算法思想

关键点在于依次摘取两个表中相等的元素重新进行链接，删除其他不等的元素。

完整代码

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

//已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并存放在A链表中。 

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 Intersection(LinkList &La, LinkList &Lb, LinkList &Lc){
    //求两个递增的有序链表La和Lb的交集，使用头指针Lc指向 
    LinkList pa, pb, pc, u;
    pa = La -> next;                        //pa是链表La的工作指针，初始化为首元结点 
    pb = Lb -> next;                        //pb是链表Lb的工作指针，初始化为首元结点 
    Lc = pc = La;                           //用La的头结点作为Lc的头结点 
    while(pa && pb){                        //两个链表La和Lb均未达到表尾结点 
        if(pa -> data == pb -> data){       //相等，交集并入结果表中 
            pc -> next = pa;
            pc = pa;
            pa = pa -> next;                //取La中的元素，将pa链接在pc的后面，pa指针后移 
            u = pb;
            pb = pb -> next;
            delete u;                       //删除Lb中的对应的相等元素 
        }
        else if(pa -> data < pb -> data){   //删除较小者La中的元素 
            u = pa;
            pa = pa -> next;
            delete u;
        }
        else{                               //删除较小者Lb中的元素 
            u = pb;
            pb = pb -> next;
            delete u;
        }
    }
    while(pa){                              //Lb为空，删除非空表La中的所有元素 
        u = pa;
        pa = pa -> next;
        delete u;
    }
    while(pb){                             //La为空，删除非空表Lb中的所有元素 
        u = pb;
        pb = pb -> next;
        delete u;
    }
    pc -> next = NULL;                     //置链表Lc尾标记 
    delete Lb;                             //释放Lb的头结点 
} 

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, Lc;
    ListRead(La);
    ListRead(Lb);
    Intersection(La,Lb,Lc);
    cout << "两个链表的交集为：" << endl; 
    ListPrint(Lc); 
    return 0;
}

结果显示

E2ODZK7`KP)A{{F6Z1F}2WM.png