第二章算法设计3

题目描述

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

代码实现

#pragma once
#include <iostream>
#include<string>
#define MAXSIZE 100

using namespace std;


//单链表的存储结构
typedef struct Lnode
{
	int data;//数据域
	struct Lnode* next;//指针域
}Lnode, * LinkList;


//单链表的初始化
void InitList(LinkList& L)
{
	L = new Lnode;
	L->next = NULL;
}

//头插法创建单链表

void CreateList_H(LinkList& L, int n)
{
	//创建带头结点的单链表 并初始化
	L = new Lnode;
	L->next = NULL;

	//创建新的结点
	Lnode* p;
	for (int i = n - 1; i >= 0; i--)
	{
		p = new Lnode;
		cout << "请输入第" << i + 1 << "个数据" << endl;
		cin >> p->data;
		p->next = L->next;
		L->next = p;
	}

}

//打印
void show(LinkList L)
{
	//创建一个结点 并指向L的首元结点
	Lnode* p;
	p = L->next;
	//首元结点不为空
	while (p)
	{
		cout << p->data << " ";
		//指向下一个结点
		p = p->next;
	}
	cout << endl;

}

//求交集
void get_list_jiaoji(LinkList& LA, LinkList& LB, LinkList& LC)
{
	//创建结点
	Lnode* pa;
	Lnode* pb;
	Lnode* pc;
	//用于删除剩余的结点
	Lnode* q;
	//指向LA的首元结点
	pa = LA->next;
	//指向LB的首元结点
	pb = LB->next;
	//将LA作为LC的头结点，pc指向LC的头结点，之后的操作由pc完成
	LC = LA;
	pc = LC;

	while (pa && pb)
	{
		if (pa->data== pb->data)
		{
			pc->next = pa;//将pa所指结点链接到pc所指结点之后
			pc = pa;//pc指向pa
			pa = pa->next;//pa指向下一节点
			pb = pb->next;//pb指向下一节点
			
		}
		
		else if (pa->data < pb->data)
		{
			//pa指向下一节点
			pa=pa->next;
		}
		else
		{
			//pb指向下一节点
			pb=pb->next;
			
		}
		
	}
	//如果pa中还有剩余未比较的元素则删除
	while (pa)
	{
		q = pa;
		pa = pa->next;
		delete q;
	}
	pc->next = NULL; //尾节点置为空，不然会出错
	

}



int main()
{

	//创建三个链表
	LinkList LA;
	LinkList LB;
	LinkList LC;
	//初始化需要合并的链表
	InitList(LA);
	InitList(LB);
	//创建链表
	cout << "前插法逆序输入" << endl;
	cout << "请输入A的元素：" << endl;
	CreateList_H(LA, 4);

	cout << "请输入B的元素：" << endl;
	CreateList_H(LB, 7);

	cout << string(30, '*') << endl;
	cout << "表LA的元素为：" << endl;
	show(LA);

	cout << string(30, '*') << endl;
	cout << "表LB的元素为：" << endl;
	show(LB);

	cout << string(30, '*') << endl;

	get_list_jiaoji(LA, LB,LC);
	cout << "二者的交集为：" << endl;
	show(LA);


	system("pause");
	return 0;
}

运行结果