突然感觉时间好少啊,花了这么多时间训练希望最终能有不错的成绩⛽
大致思路:
要实现的是先输入两个一元多项式,然后输出这两个式子并且把两个式子相加和相乘,并输出结果
实验最大难点就在于插入函数和合并同类项函数怎么写,首先当插入的这个结点指数和表达式中某个项的指数相同,则只需要累加一下即可,判断表达式中是否存在一个项的指数和要插入的相同(LocateElem
),若没有则需要找到一个位置使得插入后指数从前往后还是递增的(Orderinsert
),有了这两个函数创建链表就很容易了
所谓相加,本质就是合并同类相,先把La中的元素移到Lc中,然后把Lb中的元素一个一个插入到Lc中,即得到了相加后的结果
所谓相乘,可以遍历两个表达式,两两结合,系数相乘,指数相加,得到的结果插入到L4中,最后即可得到答案
坑点
记得初始化链表时一定要先分配一个头节点,不然程序直接死了
全代码
#include <bits/stdc++.h>
using namespace std;
typedef bool Status;
struct term{
double coef;
int expn;
};
typedef struct Lnode{
term data;
Lnode *next;
}*Link,*Linklist;
//比较函数,返回a和b的指数大小比较结果
Status comp(term a,term b){
if(a.expn==b.expn) return 0;
return a.expn-b.expn;
}
void Delnext(Link pre){ //删除pre指向的结点
Link tmp=pre->next;
pre->next=tmp->next;
free(tmp);
}
// 判断链表中是否有和e项相同的指数项,有返回1,没有返回0
Status LocateElem(Linklist L,term e,Link &pre,Link &now){
pre=L;
now=pre->next;
while(now && comp(e,now->data)){ //若该结点的指数和e的指数不同则遍历下一个结点
pre=now;
now=now->next;
}
if(!now) return 0; //若链表中每元素了就说明没有相同的
else return 1;
}
// 当链表中没有和e项指数相同的项时,找到这个项应该插入的位置,并插入
void Orderinsert(Linklist &L, term e){
Link pre,now,o;
pre=L; //pre是now的上一个指针
now=pre->next;
while(now && now->data.expn<e.expn){ //若当前结点的指数小于要插入的结点指数就继续遍历
pre=now;
now=now->next;
}
o=new Lnode; //找到第一个大于要插入结点的指数的位置,并插入
o->data=e;
o->next=now;
pre->next=o;
}
// 将一个项插入链表中,并进行同类型合并
void Orderinsertmerge(Linklist &L,term e){
Link pre,now;
if(LocateElem(L,e,pre,now)){ //若当前表达式中已经有和这个指数相同的项了就累加
now->data.coef+=e.coef; //相同指数项系数累加
if(!(now->data.coef)){ //若累加后系数为0,则直接删除这个结点
Delnext(pre);
}
} else Orderinsert(L,e); //没有相同的指数项,就维护表达式从前往后指数递增的特性,找到位置并插入
}
// 新建一个表达式,存在链表中
void Creatpolyn(Linklist &p,int num){
printf("\n[Tips]: 请输入%d个系数和指数用空格符间隔\n",num);
term e;
p=new Lnode; //创建一个链表头结点
p->next=NULL;
for(int i=1;i<=num;i++){
scanf("%lf%d",&e.coef,&e.expn);
if(!e.coef) continue; //若系数为0则无意义
Orderinsertmerge(p,e);
}
}
// 输出表达式的系数指数
void printpolyn(Linklist p) {
Link q;
q=p->next;
printf("-------------------------\n");
printf(" 系数\t指数\n");
while(q) {
printf(" %.2f\t%d\n",q->data.coef,q->data.expn);
q=q->next;
}
printf("-------------------------\n");
}
// 将La链表拷贝到Lb中
void copy(Linklist La, Linklist &Lb) {
La=La->next;
Lb=new Lnode; //创建Lb链表的头节点
Lb->next=NULL;
while(La) {
Orderinsert(Lb, La->data); //把当前La结点的数据插入到Lb中
La=La->next;
}
}
// 打印表达式
void PrintList(Linklist L) {
if(!L->next) { //若链表为空则直接输出0
printf("0\n");
printf("*************************************************\n");
return ;
}
Linklist q;
q=L->next;
while(q->next) { //因为要保持输出格式,要判断当前元素是否为最后一个元素,如不是则还需要输出符号,否则不需要
if(!(q->data.expn)) { //若当前元素指数为0,则不能输出x
if((q->next->data.coef>0)) printf("%.2f + ",q->data.coef); //若下一个元素的符号是正则需要+
else printf("%.2f ",q->data.coef); //若下一个元素的符号是负则需要-
} else { //若指数不为0则还需要输出x
if((q->next->data.coef>0)) printf("%.2f X^ %d + ",q->data.coef,q->data.expn); //同上一个if
else printf("%.2f X^ %d ",q->data.coef,q->data.expn);
}
q=q->next;
}
if(!(q->data.expn)) printf("%.2f \n",q->data.coef); // 输出最后一个元素
else printf("%.2f x^ %d\n",q->data.coef,q->data.expn);
printf("*************************************************\n");
}
// La加Lb存到Lc中
void add(Linklist La, Linklist Lb, Linklist &Lc) {
copy(La, Lc); //把La拷贝到Lc中
Link qb;
term b;
qb=Lb->next;
while(qb) {
b=qb->data;
Orderinsertmerge(Lc,b); //由于该函数有合并同类项的功能所以可以直接插入
qb=qb->next;
}
}
// La乘以Lb放到Lc中
void mul(Linklist La, Linklist Lb, Linklist &Lc) {
Lc=new Lnode; //创建新链表头节点
Lc->next=NULL;
Link ha=La->next;
while(ha) {
term now=ha->data;
Link hb=Lb->next;
while(hb) {
term tmp, cur=hb->data;
tmp={cur.coef*now.coef, cur.expn+now.expn}; //一一枚举La和Lb中的元素,一一相乘并合并同类项
Orderinsertmerge(Lc, tmp);
hb=hb->next;
}
ha=ha->next;
}
}
int main()
{
int num;
Linklist L1,L2,L3,L4;
//输入第一个链表
printf("\n[Tips]: 请您输入第一个多项式的项数: ");
scanf("%d",&num);
Creatpolyn(L1,num);
printpolyn(L1);
printf("\n[INFO]: L1= ");
PrintList(L1);
//输入第二个链表
printf("\n[Tips]: 请您输入第二个多项式的项数: ");
scanf("%d",&num);
Creatpolyn(L2,num);
printpolyn(L2);
printf("\n[INFO]: L2= ");
PrintList(L2);
//相加
add(L1, L2, L3);
printf("\n[result]: L1和L2相加结果:\n");
PrintList(L3);
//相乘
mul(L1, L2, L4);
printf("\n[result]: L1和L2相乘结果:\n");
PrintList(L4);
return 0;
}