两个有序单链表求交集（8803）

1、两个有序单链表求交集(8803)一、题目1、问题描述各依次输入递增有序若干个(最多20个)不超过100的整数，分别建立两个递增有序单链表，分别表示集合A和集合B,设计算法求出A与B的交集，并存放于A链表中。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。然后输出求交集后的单链表。2、输入输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的第一行和第二行分别为若干个(最多20个)依次非递减有序的不超过100的整数，输入-1000作为输入结束标志(-1000本身不作为输入的数据)。3、输出输出A与B的交集的单链表，每两个数据之间一个空格。4

2、、输入例410 17 22 29 31 35 43 45 46 49 51 56 74 75 99 -100011 13 17 24 38 41 45 52 53 56 69 80 82 83 87 -100012 13 15 17 18 20 26 30 31 38 51 77 83 85 94 -100011 12 16 23 32 34 36 38 45 65 72 80 82 90 98 -10001 2 3 4 5 6 -10001 2 3 4 -10001 2 3 -10001 2 3 4 5 6 -10005、输出例17 45 5612 381 2 3 41 2 3二、算法指导1

3、、数据结构根据题目要求，数据要存储于单链表，首先要确定建立的单链表的结点类型，结点类型可为：typedef struct node int data; node *next; *linklist; 这里的linklist为指针类型，其变量为指向node的结点。2、算法思路(1) 设计初始化单链表的函数int initlist_l(linklist &l)；以建立带头结点的空单链表。int initlist_l(linklist &l) / 构造一个带头结点的空单链表l，l是引用参数，是变参，其值其他函数要用。 (2) 设计建立递增有序单链表的函数void createlist_

4、l(linklist l)。可用后插法建立单链表，当输入-1000时建立结束，这里的l开始时已指向单链表的头结点，l的值已不会变，所以只要值参就可以。void createlist_l(linklist l) 输入数据d; while(d!=-1000) 产生新结点； 把d 赋值给新结点； 把新结点链接到链表l的尾部； 输入数据d; (3) 输出单链表。void print(linklist l) / 按输出格式要求输出单链表l中结点的值 (4) 设计将两个递增有序有序单链表求出其交集的函数void intersection (linklist la,linklist lb)，la和lb分别为

5、两个递增有序单链表。求交集的思想是依次扫描la表中的每个元素x，与lb表中的每个元素比较，若lb表中存在x，则保留该元素，否则删除该元素，操作过程中要注意对la表的扫描不要断链。最后la表中就是所要求的交集的单链表。void intersection (linklist la,linklist lb) p1指向la的头结点； / 作为正在生成交集单链表的尾结点，此时p1只有头结点 while(pa不空) / 扫描la表中的每个元素 pb指向lb表的第一个结点；while(pb不空而且当前pa所指结点的值不等于pb所指结点的值) / pa中当前元素与lb表中的每个元素比较 pb指向原pb 的下一个结点； if(若pb中不存在pa中当前元素) 保存pa所指结点的后一结点于q； / 为了pa不断链删除结点pa； pa取q的值； / 准备好pa表中下一个结点else / pb中存在pa所指向的元素 p1所指结点后链上pa； / pa所指结点是交集单链表中的结点 p1作为新的尾结点； / 后插法生成交集单链表 pa指向其下一个结点；对已生成的交集单链表最后一个结点(p1)置结束标志； 3、主函数main()调用initlist_l()，初始化两个单链表la,lb；调用createlist_