/*求交集*/
#include <iostream>
using namespace std;
const int N = 10010;
int Intersection[N];
struct ListNode
{
double val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* create()
{
ListNode *dummy = NULL;
dummy = new ListNode;
ListNode *pre = dummy;
while (1)
{
ListNode *p = new ListNode;
cin >> p->val;
if(p->val == -1)
{
pre->next = NULL;
return dummy->next;
}
else
{
pre->next = p;
pre = pre->next;
}
}
}
void Output_Intersection(ListNode* S1, ListNode* S2)
{
int i = 0;
while(S1)
{
if(!S2) break;
ListNode* temp_S2 = S2;
while(temp_S2)
{
if(S1->val == temp_S2->val) Intersection[i++] = S1->val;
temp_S2 = temp_S2->next;
}
if(S1->next && S1->val != S1->next->val)
{
S1 = S1->next;
}
else if(S1->next && S1->val == S1->next->val)
{
S1 = S1->next->next;
}
else if(!S1->next)
{
break;
}
}
if(!Intersection[i-1])
{
cout<<"NULL"<<endl;
return;
}
for(int j = 0; j < i; j++) cout<<Intersection[j]<<" ";
}
int main()
{
ListNode* S1 = create();
ListNode* S2 = create();
Output_Intersection(S1, S2);
return 0;
}
/*原地求并集*/
#include <iostream>
using namespace std;
const int N = 10010;
struct ListNode
{
double val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* create()
{
ListNode *dummy = NULL;
dummy = new ListNode;
ListNode *pre = dummy;
while (1)
{
ListNode *p = new ListNode;
cin >> p->val;
if(p->val == -1)
{
pre->next = NULL;
return dummy->next;
}
else
{
pre->next = p;
pre = pre->next;
}
}
}
void OutPut_Merge(ListNode* S1, ListNode* S2)
{
ListNode* temp_S1 = S1;
ListNode* temp_S2 = S2;
if(S1->val > S2->val) swap(S1->val, S2->val);
while(temp_S1->next && temp_S2)
{
if(temp_S1->next->val > temp_S2->val)
{
ListNode* temp = temp_S1->next;
temp_S1->next = temp_S2;
temp_S2 = temp;
temp_S1 = temp_S1->next;
}
else if(temp_S1->next->val == temp_S2->val)
{
temp_S2 = temp_S2->next;
temp_S1 = temp_S1->next;
}
else if(temp_S1->next->val < temp_S2->val)
{
temp_S1 = temp_S1->next;
}
}
while(temp_S2)
{
temp_S1->next = temp_S2;
temp_S2 = temp_S2->next;
temp_S1 = temp_S1->next;
}
while(S1)
{
cout<<S1->val<<" ";
S1 = S1->next;
}
}
int main()
{
ListNode* S1 = create();
ListNode* S2 = create();
OutPut_Merge(S1, S2);
return 0;
}
/*多项式求加减*/
#include <iostream>
using namespace std;
const int N = 10010;
int S1[N], S2[N], n1, n2, max1, max2;
int main()
{
cout<<"请输入第一个多项式的项数:";
cin>>n1;
for(int i = 0; i < n1; i++)
{
int index, nums;
cout<<"第"<<i+1<<"项的系数和指数分别是:" ;
cin>>nums>>index;
S1[index] = nums;
max1 = max(index, max1);
}
cout<<endl;
cout<<"请输入第二个多项式的项数:";
cin>>n2;
for(int i = 0; i < n2; i++)
{
int index, nums;
cout<<"第"<<i+1<<"项的系数和指数分别是:" ;
cin>>nums>>index;
S2[index] = nums;
max2 = max(index, max2);
}
cout<<endl;
cout<<"一元多项式1:";
bool first = true;
for(int i = 0; i <= max1; i++)
{
if(S1[i] != 0)
{
if(S1[i] > 0 && first != true)
{
cout<<"+";
}
cout<<S1[i]<<"x("<<i<<") ";
if(first) first = false;
}
}
cout<<endl;
first = true;
cout<<"一元多项式2:";
for(int i = 0; i <= max2; i++)
{
if(S2[i] != 0)
{
if(S2[i] > 0 && first != true)
{
cout<<"+";
}
cout<<S2[i]<<"x("<<i<<") ";
if(first) first = false;
}
}
cout<<endl;
first = true;
cout<<"加的结果:";
for(int i = 0; i <= max(max2, max1); i++)
{
if(S1[i]+S2[i] != 0)
{
if(S1[i]+S2[i] > 0 && first != true)
{
cout<<"+";
}
cout<<S1[i]+S2[i]<<"x("<<i<<") ";
if(first) first = false;
}
}
cout<<endl;
first = true;
cout<<"减的结果:";
for(int i = 0; i <= max(max2, max1); i++)
{
if(S1[i]-S2[i] != 0)
{
if(S1[i]-S2[i] > 0 && first != true)
{
cout<<"+";
}
cout<<S1[i]-S2[i]<<"x("<<i<<") ";
if(first) first = false;
}
}
}