02-线性结构2 一元多项式的乘法与加法运算
这道题真是太逆天了，写费劲，调试更费劲。下面我来说明一下思路。
1、主函数
主函数比较简单，调用函数构造两个链表，然后再调用相乘、相加、输出函数。
int main()
{
List l1,l2,ladd,lmulti;l1=Read();l2=Read();lmulti=Mult(l1,l2);Print(lmulti);ladd=Add(l1,l2);Print(ladd);return 0;
}
2、结构体定义、Read()函数
我们采用链表来实现：系数，指数，指针
typedef struct node* List;
struct node{int pre; //系数int up; //指数List next; //指针
};
Read函数也较容易，此处采用尾插法
List Read()
{ int num;cin>>num;//有多少结点List L=new node;L->next=NULL;//初始化头节点struct node h;h.next=L; //保存头节点，用来返回
//L指针用来遍历链表将结点连起来，所以会往后移for(int i=1;i<=num;i++){List t=new node; //创建新结点int p,u;cin>>p>>u;t->pre=p;t->up=u; //初始化新的系数、指数t->next=L->next;L->next=t;L=L->next; //往后遍历继续创建}return h.next; //返回头节点
}
3、Add函数、newlink函数
这里头我们实质想实现Add函数，由于中间有的代码重用了，所以我们又写了一个newlink函数来减少代码行数。
先说明一下newlink函数是干嘛的，这里头是把结点p接到L的后面，这个步骤在Add函数里面多次出现。L指向链表的最后一个结点，新结点会被接在尾部
void newlink(List L,List p)
{ //L后面新接个结点pList t=new node;t->pre=p->pre; t->up=p->up; t->next=L->next;L->next=t;//创建新结点，把p复制过来，接到L后面
}
我们来看一下Add函数的实现：
首先新建头节点和保存头结点的指针用来返回，p的话后面随着遍历来移动。
此处我们把相加的结果放在新的一个链表中，不修改原来的两个链表因为后面要用
然后遍历两个链表，把指数大的放前面，指数相等就相加再放进去
最后如果有没遍历完的，把链表接到后面
List Add(List L1,List L2)
{//此处是新建一个链表来保存两个链表的结果struct node h; //保存头节点，就是为了返回用的List p=new node;p->next=NULL; //后续p会遍历链表，找不到初始状态了，用h来存初始位置h.next=p; L1=L1->next;L2=L2->next;//L1，L2指向第一个结点while(L1&&L2){ //当两者都没遍历完时if(L1->up<L2->up){ //把大的结点放前面newlink(p,L2);p=p->next;L2=L2->next;}else if(L1->up>L2->up){ //把大的结点放前面newlink(p,L1);p=p->next;L1=L1->next;}else { //如果两节点相等就合并List t=new node;t->pre=L1->pre+L2->pre;t->up=L1->up;t->next=p->next;p->next=t;p=p->next;L1=L1->next,L2=L2->next;}}while(L1){ //L1还剩下没遍历完，接到新链表后面newlink(p,L1);p=p->next,L1=L1->next;}while(L2){//L2还剩下没遍历完，接到新链表后面newlink(p,L2);p=p->next,L2=L2->next;}return h.next; //保存的是头节点,返回相加后的新链表
}
4、Mult函数、multi函数
此处也是目的是实现Mult函数，但multi函数这块代码被重用很多次，所以单独写减少冗余。
先讲一下乘法实现思路：
我们选择L2链表，用它的每一个结点与L1相乘，把结果相加（调用Add函数）就行了。
先看一下multi函数：
此处是用small结点与链表L的每一个结点相乘，得到新链表，不修改链表L，我们新开辟空间。
前面几行一样，初始化新的链表，然后进行遍历，将节点相乘存到新链表中
返回新链表的头结点
List multi(List L, List small)
{ //用结点small与链表L相乘
struct node h;List p=new node;p->next=NULL;h.next=p; L=L->next; //前几行代码与前面一样，初始头节点，h存方便返回，p后面遍历while(L){List t=new node;t->pre=small->pre*L->pre; //系数相乘t->up=small->up+L->up; //指数相加t->next=p->next;p->next=t;p=p->next;L=L->next;}return h.next;//返回相乘的新链表
}
再来看Mult函数
遍历L2的每一个结点，用他们与L1所有结点相乘。
此处先乘第一个结点，初始化一下p，然后循环遍历，t存当前结点与L1相乘的结果。
将p,t相加，结果赋给p，p就更新为L2前几个结点的与L1相乘的累加和
最后返回p
List Mult(List L1,List L2)
{//链表L1与链表L2相乘List p;L2=L2->next;//L2指向第一个结点if(L2) p=multi(L1,L2); //与L1相乘L2=L2->next;while(L2){List t=multi(L1,L2); //t来存下一个结点与L1的相乘结果p=Add(p,t); //将两个结果相加L2=L2->next;}//p由于不断更新现在存的是最终结果return p; //将两个链表相乘的结果存到新链表中返回
}
5、Print函数
print函数先找到第一个系数不为0 的结点，如果遍历完L都没找到，输出0 多项式，否则先输出第一个结点的系数、指数。
注意输出方式，最后输出完不能有多的空格
void Print(List L)
{L=L->next;//到第一个结点while(L&&L->pre==0)L=L->next;//找到第一个系数不为0的结点if(!L) {cout<<"0 0"<<endl;//L遍历完了也没找到，输出0多项式return ;}cout<<L->pre<<' '<<L->up;
//此处输出是为了最后输出的结果不能多空格，注意不能多输出空格！！！！L=L->next;while(L){if(L->pre)cout<<' '<<L->pre<<' '<<L->up; //系数不为0就输出该结点L=L->next;}cout<<endl;
}
六、总结
这道题相当费时，花了不少时间希望我的代码能对大家有帮助。
完整代码如下：
#include<iostream>
using namespace std;
typedef struct node* List;
struct node{int pre;int up;List next;
};void newlink(List L,List p)
{ //L后面新接个结点pList t=new node;t->pre=p->pre;t->up=p->up;t->next=L->next;L->next=t;
}
List Read()
{ int num;cin>>num;List L=new node;L->next=NULL;struct node h;h.next=L;for(int i=1;i<=num;i++){List t=new node;int p,u;cin>>p>>u;t->pre=p;t->up=u;t->next=L->next;L->next=t;L=L->next;}return h.next; //返回头节点
}
List Add(List L1,List L2)
{struct node h;List p=new node;p->next=NULL;h.next=p;L1=L1->next;L2=L2->next;while(L1&&L2){if(L1->up<L2->up){newlink(p,L2);p=p->next;L2=L2->next;}else if(L1->up>L2->up){newlink(p,L1);p=p->next;L1=L1->next;}else {List t=new node;t->pre=L1->pre+L2->pre;t->up=L1->up;t->next=p->next;p->next=t;p=p->next;L1=L1->next,L2=L2->next;}}while(L1){newlink(p,L1);p=p->next,L1=L1->next;}while(L2){newlink(p,L2);p=p->next,L2=L2->next;}return h.next; //保存的是头节点,返回相加后的新链表
}
List multi(List L, List small)
{ //用结点small与链表L相乘
struct node h;List p=new node;p->next=NULL;h.next=p;L=L->next;while(L){List t=new node;t->pre=small->pre*L->pre;t->up=small->up+L->up;t->next=p->next;p->next=t;p=p->next;L=L->next;}return h.next;//返回相乘的新链表
}
List Mult(List L1,List L2)
{//链表L1与链表L2相乘List p;L2=L2->next;if(L2) p=multi(L1,L2);L2=L2->next;while(L2){List t=multi(L1,L2);p=Add(p,t);L2=L2->next;}return p;
}
void Print(List L)
{L=L->next;while(L&&L->pre==0)L=L->next;if(!L) {cout<<"0 0"<<endl;return ;}cout<<L->pre<<' '<<L->up;L=L->next;while(L){if(L->pre)cout<<' '<<L->pre<<' '<<L->up;L=L->next;}cout<<endl;
}int main()
{
List l1,l2,ladd,lmulti;l1=Read();l2=Read();lmulti=Mult(l1,l2);Print(lmulti);ladd=Add(l1,l2);Print(ladd);return 0;
}
附录：线性表的定义与操作
顺序表：
#include<stdlib.h>
#include<stdio.h>
typedef struct LNode *List;
typedef int ElementType;
typedef int Position;
#define MAXSIZE 100
#define ERROR -1
struct LNode
{ElementType data[MAXSIZE];Position End;
};
List MakeEmpty()
{List L;L=(List)malloc(sizeof(struct LNode));L->End=-1; return L;
}Position Find(List L,ElementType x)
{Position i=0;while(i<L->End&&L->data[i]!=x)i++;if(i>L->End)return ERROR;return i;
}bool Insert(List L ,ElementType x,Position i)
{if(L->End+1>=MAXSIZE)return 0;if(i<0||i>MAXSIZE-1)return 0;for(Position p=L->End;p>=i;p--)L->data[p+1]=L->data[p];L->End++;L->data[i]=x;return 1;
}bool Delete (List L,Position p)
{if(p<0||p>L->End)return 0;for(Position i=p;i<=L->End;i++)L->data[i]=L->data[i+1];L->End--;return 1;
}
链式表：
#include<stdlib.h>
#include<stdio.h>
typedef struct LNode *List;
typedef int ElementType;
typedef List Position;
#define MAXSIZE 100
#define ERROR NULL
struct LNode
{ElementType value;Position Next;
};
bool init()
{
List L;
L->Next=NULL;
return 1;
}
Position Find( List L,ElementType x)
{L=L->Next;while(L&&L->value!=x)L=L->Next;if(L)return L;else return ERROR;
}bool Insert(List L,ElementType x,Position p)
{while(L&&L->Next!=p)L=L->Next;if(L==NULL)return 0;List t=(List)malloc(sizeof(struct LNode));t->value=x;t->Next=L->Next;L->Next=t;return 1;
}bool Delete (List L,Position p)
{while(L&&L->Next!=p)L=L->Next;if(L==NULL)return 0;L->Next=p->Next;free(p);return 1;
}
