求链表交集(线性表)

2020年1月17日 1116点热度 0人点赞 0条评论

求链表交集(线性表)

时间: 1ms        内存:128M

描述:

(线性表)已知递增有序的单链表A,B分别存储了一个集合,请编程以求出两个集合A和B 的交集(即由在A中出现且在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。

#include <stdio.h>

#include <stdlib.h> //standard library标准库头文件

typedef struct node

{

    int data;

    struct node *next;

}List;

  

List *Create(int n)  //尾插法建立链表

{

    int i;

    List *tmp, *p;

    List *head=(List *)malloc(sizeof(List)); //(分配类型 *)malloc(分配元素个数 *sizeof(分配类型))

    head->next =NULL;

    tmp=head;

      

    for(i=0;i<n;i++)

    {

        p=(List *)malloc(sizeof(List));

        scanf("%d", &p->data);

        p->next=tmp->next;

        tmp->next=p;

        tmp=p;

    }

  

    return head;

}

  

 

List *intersection(List *p1,List *p2)//两条链表取交集的函数

{

    List *p,*tmp;             //p用于指向新建立的结点, tmp指向链表尾部

    p=(List *)malloc(sizeof(List));//另开辟存储空间存放交集

    p->next=NULL;

    tmp=p;

    p1=p1->next;

    p2=p2->next;

    while(p1!=NULL)     //遍历p1链表

    {

        if(p2==NULL)    //p2与p1比较

        {

            break;

        }

        while(p2->data<p1->data&&p2->next!=NULL)

        {

            p2=p2->next;            //相当于p2++

        }

        if(p1->data==p2->data)  //当两条链表中的值相等时

        { 

/*************/

添加代码

/*************/  

        }

        p1=p1->next;           //相当于/p1++

    }

      

    tmp->next=NULL;

 //delete ;

    return p;

}

 

List *output(List *p)     //输出

{

   while(p->next)

    {

       

        printf("%d ",p->data);

        p=p->next;

    }

    printf("\n");

    return p;

}

void  destroy( List *p1)

{

  List *p;

 while(p1!=NULL)

 {

  p=p1->next;

  delete(p1);

  p1=p;

 }

}

int main()

{

    int m,n;

    List *p1,*p2,*p;

    scanf("%d", &n);

    p1=Create(n);        //第一条链表的建立

    scanf("%d", &m);

    p2=Create(m);//第二条链表的建立

    p=intersection( p1, p2);

    output(p);

    destroy(p);

    return 0;

}

输入:

一个整数m,表示A的长度m。

m个数表示A中的m个数据元素。

一个整数n,表示B的长度n。

n个数表示B中的n个数据元素。

输出:

AB的交集C

示例输入:

6
11 22 33 44 55 66
4
22 22 33 56 

示例输出:

22 33 

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论