记录一下自己做的题
227交集
#include <iostream>
using namespace std;
//求有序链表的交集
typedef int Data;
struct LNode
{
Data data;
LNode* next;
};
//初始化
void InitList(LNode*& L)
{
L = new LNode;
L->next = NULL;
}
//尾插法创建链表
void CreateList_B(LNode*& L, int n)
{
LNode* p = L;
for (int i = 0; i < n; i++)
{
//创建临时节点
LNode* tmp = new LNode;
cin >> tmp->data;
//插入
p->next = tmp;
tmp->next = NULL;
//更新P
p = p->next;
}
}
//尾删销毁链表
LNode * DestoryList_B(LNode*& L)
{
if (!L)
{
return L;
}
if (L->next == NULL)
{
delete L;
L = NULL;
return L;
}
LNode* p = L;
//找到倒数第二个节点，删除倒数第一个节点
while (p->next->next != NULL)
{
p = p->next;
}
//删除
/*LNode* tmp = p->next;
delete tmp;*/
delete p->next;
p->next = NULL;
//删除尾节点
DestoryList_B(L);
}
//删除某节点
LNode* DeleteNode(LNode*& L, LNode* pnode)
{
LNode* tmp = L->next;
if (tmp == pnode)
{
L->next = pnode->next;
delete pnode;
return L->next;
}
//找到pnode的前一个结点——tmp
while (tmp->next != pnode)
{
tmp = tmp->next;
}
tmp->next = pnode->next;
delete pnode;
return tmp->next;
}
//有序链表的交集
void IntersectionList(LNode*& A, LNode*& B)
{
//与空集的交集为空
if (!(A->next) || !(B->next))
{
A->next = NULL;
return;
}
//临时变量
LNode* pa = A->next, * pb = B->next;
//循环
while (pa && pb)
{
//递增集合
//比较，取小的后移
if (pa->data > pb->data)
{
pb = pb->next;
}
else if (pa->data <pb->data)
{
LNode* p = pa;
pa=DeleteNode(A, p);
}
else//相等
{
//更新
pb = pb->next;
pa = pa->next;
}
}
//释放pa以及pa后的节点——尾删
if (!pa)
return;
else
{
//删除pa及以后元素
//LNode* p = pa;
DestoryList_B(pa->next);
DeleteNode(A,pa);
/*LNode* p = A;
while (p->next != pa)
{
p = p->next;
}*/
//delete pa;
//pa = NULL;
//p = NULL;
}
}
//打印链表
void PrintList(LNode*& L)
{
LNode* p = L->next;
while (p)
{
cout << p->data;
if (p->next != NULL)
cout<< " ";
p = p->next;
}
cout << endl;
}
//void test1()
//{
// //多组输入
// while (1)
// {
// LNode* LA, * LB;
// //初始化
// InitList(LA);
// InitList(LB);
// int n1 = 0, n2 = 0;
// cin >> n1 >> n2;
// if (n1 == 0 && n2 == 0)
// {
// break;
// }
// CreateList_B(LA, n1);
// CreateList_B(LB, n2);
// IntersectionList(LA, LB);
// //打印
// PrintList(LA);
//
// }
//
//
//}
void test1()
{
int n1 = 0, n2 = 0;
//cin >> n1 >> n2;
//多组输入
while (1)
{
LNode* LA, * LB;
//初始化
InitList(LA);
InitList(LB);
cin >> n1 >> n2;
if (n1 == 0 && n2 == 0)
{
break;
}
CreateList_B(LA, n1);
CreateList_B(LB, n2);
IntersectionList(LA, LB);
//打印
PrintList(LA);
//cin >> n1 >> n2;
}
//while (n1!=0&&n2!=0)
//{
// LNode* LA, * LB;
// //初始化
// InitList(LA);
// InitList(LB);
// if (n1 == 0 && n2 == 0)
// {
// break;
// }
// CreateList_B(LA, n1);
// CreateList_B(LB, n2);
// IntersectionList(LA, LB);
// //打印
// PrintList(LA);
// cin >> n1 >> n2;
//}
}
//测试函数
void test2()
{
LNode* LA,*LB;
//初始化
InitList(LA);
InitList(LB);
CreateList_B(LA, 4);
CreateList_B(LB, 4);
IntersectionList(LA, LB);
PrintList(LA);
}
int main()
{
//test2();
test1();
return 0;
}
228差集
#include <iostream>
using namespace std;
//求有序链表的差集
typedef int Data;
struct LNode
{
Data data;
LNode* next;
};
//初始化
void InitList(LNode*& L)
{
L = new LNode;
L->next = NULL;
}
//尾插法创建链表
void CreateList_B(LNode*& L, int n)
{
LNode* p = L;
for (int i = 0; i < n; i++)
{
//创建临时节点
LNode* tmp = new LNode;
cin >> tmp->data;
//插入
p->next = tmp;
tmp->next = NULL;
//更新P
p = p->next;
}
}
//尾删销毁链表
void DestoryList_B(LNode*& L)
{
if (!L)
{
return;
}
if (L->next == NULL)//error
{
delete L;
return;
}
LNode* p = L;
//找到倒数第二个节点，删除倒数第一个节点
while (p->next->next != NULL)
{
p = p->next;
}
//删除
/*LNode* tmp = p->next;
delete tmp;*/
delete p->next;
p->next = NULL;
//删除尾节点
DestoryList_B(L);
}
//删除某节点
LNode* DeleteNode(LNode*& L, LNode* pnode)
{
LNode* tmp = L->next;
if (tmp == pnode)
{
L->next = pnode->next;
delete pnode;
return L->next;
}
//找到pnode的前一个结点——tmp
while (tmp->next != pnode)//error——tmp=nullptr
{
tmp = tmp->next;
}
tmp->next = pnode->next;
delete pnode;
return tmp->next;
}
//有序链表的差集——未删链表B
void DifSetList(LNode*& A, LNode*& B)
{
//与空集的差集为原集合
if (!(A->next) || !(B->next))
{
return;
}
//临时变量
LNode* pa = A->next, * pb = B->next;
////要存储的链表C
//LNode* C = A;
//LNode* pc = C;//pc开始时指向A的头节点
//循环
while (pa && pb)
{
//递增集合
//比较，取小的后移
if (pa->data > pb->data)//error——pa=0xFFFFFFFFFFFFFFFF
{
pb = pb->next;
}
else if (pa->data < pb->data)
{
pa = pa->next;
}
else//相等
{
//删除A的该节点
pa=DeleteNode(A,pa);
//更新
pb = pb->next;
}
}
}
//打印链表
void PrintList(LNode*& L)
{
LNode* p = L->next;
int count = 0;
while (p)
{
count++;
cout << p->data;
if (p->next != NULL)
cout << " ";
p = p->next;
}
cout << endl;
cout << count << endl;
}
void test1()
{
int n= 0, m = 0;
while (1)
{
LNode* A, * B;
InitList(A);
InitList(B);
cin >> n >> m;
if (n==0&&m==0)
{
break;
}
CreateList_B(A, n);
CreateList_B(B, m);
DifSetList(A, B);
//打印
PrintList(A);
}
}
int main()
{
test1();
return 0;
}