标题
西电数据结构与算法分析-276 多项式加减法——链表
题目要求
试题名称 多项式加减法
时间限制: 1 秒
内存限制: 10000KB
问题描述
给定两个多项式，求解其和与差。多项式的项数为M，而最高幂次为N。（1<=M<=10，1<=N<=1000000）
输入说明
输入包含了两个多项式，分为两行给出（同行数据间以空格隔开）：
每一行为两组数据：第一组为一个值，表示多项式的非零项数M；第二组为2*M个值，每相邻两个值表达一个多项式的非零系数项，分别为系数值、幂次值（其中各项按照幂次的降序排列）。但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。例如，第一行的数据为：4 1 10 2 5 3 4 4 0，那么表示多项式有4项，对应的多项式为：x10+2x5+3x^4+4. 又例如，第二行的数据为：4 1 8 -2 5 3 3 4 1，表示多项式有4项，对应的多项式为：x8-2x5+3x^3+4x。那么上述两个多项式相加的输出结果应为：6 1 10 1 8 3 4 3 3 4 1 4 0，对应的多项式为：x10+x8+3x4+3x3+4x+4.第一个多项式减去第二个多项式的输出结果为：7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0，对应多项式：x10-x8+4x5+3x4-3x^3-4x+4.
输出说明
输出包含了两个多项式，分为两行给出（同行数据间以空格隔开）：
第一行是多项式相加的结果，第二行是多项式相减的结果。每一行为两组数据：第一组为一个值，表示多项式的非零项数M；第二组为2*M个值，每相邻两个值表达一个多项式的非零系数项，分别为系数值、幂次值（其中各项按照幂次的降序排列）。但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。
输入样例
例1：
4 1 10 2 5 3 4 4 0
4 1 8 -2 5 3 3 4 1
输出样例
例1：
6 1 10 1 8 3 4 3 3 4 1 4 0
7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0
提示：
用链表表示多项式
*解题思路
1.读取，使用头插法或者尾插法都可以，先定义整形数组存放一个多项式的数据，定义链表之后读入该组数据。
2.加减，双重循环判断两个多项式中是否存在相等幂次的值，对其中一个链表对应项的系数值进行加减的数值变动。
3.排序，题干要求中，输出的多项式需先输出项数，再由幂次从高到低输出，对于系数为0的项进行忽略处理，多项式若不含非0项则仅输出 0 。
总结
1.经常遗忘链表的重置，在上个循环使用过的链表，需要在另一个循环使用，导致循环走不出来。
2.分步骤去完成功能，出现异常也分步骤去测试才能有效率解决问题。
写的不好见谅。
源代码
``
#include<stdlib.h>
typedef struct LinkList{
int num1; //系数
int num2; //指数
struct LinkList *next;
}LinkList;
void print(LinkList *&L,int n){ //排序并输出
int flag =0,N =n;
LinkList *t1,*t2,*t3;
t1 =L;
t3 = L;
for(int k=0;k<n;k++){ //该步骤为了筛选系数全为0的结果
if(L->num1==0){N--;}
else{flag = 1;}
L = L->next;
}
if(flag==0){
printf("0\n");
}
else{
printf("%d ",N); //排序降幂交换
for(int j =0;j<n;j++){
t2 = t1->next;
if(t2==NULL){break;}
for(int k=j+1;k<n;k++){
if(t1->num2<t2->num2){
int temp1,temp2;
temp1 = t1->num1;
temp2 = t1->num2;
t1->num1 = t2->num1;
t1->num2 = t2->num2;
t2->num1 = temp1;
t2->num2 = temp2;
}
t2 = t2->next;
}
t1 = t1->next;
}
L = t3;
for(int k=0;k<n;k++){ //输出系数不为0的项
if(L->num1 != 0){
printf("%d %d ",L->num1,L->num2);
L = L->next;}
}
printf("\n");
}
}
void Creat(LinkList *&L1,LinkList *&L2,LinkList*&L3,int n1,int n2,int num1[100],int num2[100]){
int n3 = n2;
L1 = (LinkList*)malloc(sizeof(LinkList));
L2 = (LinkList*)malloc(sizeof(LinkList));
L3 = (LinkList*)malloc(sizeof(LinkList));
L1 = NULL;
L2 = NULL;
L3 = NULL;
LinkList *s1,*s2,*s3;
for(int i=0;i<2*n1;i+=2){ // 使用头插法将数据传入链表其中L2、L3的数值一致方便加减处理
s1 =(LinkList*)malloc(sizeof(LinkList));
s1->num1 =num1[i];
s1->num2 =num1[i+1];
s1->next = L1;
L1 = s1;
}
for(int i=0;i<2*n2;i+=2){
s2 =(LinkList*)malloc(sizeof(LinkList));
s2->num1 =num2[i];
s2->num2 =num2[i+1];
s2->next = L2;
L2 = s2;
}
for(int i=0;i<2*n2;i+=2){
s3 =(LinkList*)malloc(sizeof(LinkList));
s3->num1 =num2[i];
s3->num2 =num2[i+1];
s3->next = L3;
L3 = s3;
}
//处理数据
int flag;
for(int i=0;i<n1;i++){
flag = 1;
for(int j=0;j<n2;j++){
if(L1->num2 == L2->num2){
L2->num1 = L2->num1 + L1->num1;
flag = 0;
break;
}
else L2 = L2->next;
}L2 = s2;
if(flag ==1){ //L1中出现L2中没有的元素
s2 = (LinkList*)malloc(sizeof(LinkList));
s2->num1 = L1->num1;
s2->num2 = L1->num2;
s2->next = L2;
n2++;
}
L2 = s2;
L1 = L1->next;
}
L1 = s1; //重置
for(int i=0;i<n3;i++){
flag = 1;
for(int j=0;j<n1;j++){
if(L3->num2 == L1->num2){
L1->num1 = L1->num1 - L3->num1;
flag = 0;
break;
}
else L1 = L1->next;
}
L1 = s1;
if(flag ==1){ //L3中出现L1中没有的元素
s1 = (LinkList*)malloc(sizeof(LinkList));
s1->num1 =(-1)*L3->num1;
s1->num2 = L3->num2;
s1->next = L1;
n1++;
} L1 = s1;
L3 = L3->next;
}
print(L2,n2);
print(L1,n1);
}
int main(){
int n1,n2,num1[100],num2[100]; //主函数中实现数据读入
scanf("%d",&n1);
for(int i=0;i<2*n1;i++){
scanf("%d",&num1[i]);
}
scanf("%d",&n2);
for(int j=0;j<2*n2;j++){
scanf("%d",&num2[j]);
}
LinkList *L1,*L2,*L3; //创建链表
Creat(L1,L2,L3,n1,n2,num1,num2); //传入
return 0;
}
//yeyu_
|