第二章算法设计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;
}