设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
过程都在代码的注释里
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 |
#include<bits/stdc++.h> using namespace std; //这里我用链表存储数据，我想了想，要写的函数有 //插入函数，输出函数，合并函数，以及相乘函数 typedef struct lnode{ int coefficient;//顺便学一波英语，coefficient（系数），exponent（指数） int exponent; struct lnode *link; }sqlist; //后来我想了想应该用尾插法，头插法最后的数据就是倒着的了 //void insertlist(sqlist*&l,int x,int y){ // //为了节约时间，初始化直接写在插入函数里面 // sqlist*s;//这个是头节点的下一个节点 // l=(sqlist*)malloc(sizeof(sqlist));//这个是头节点 // l->link=NULL; // s=(sqlist*)malloc(sizeof(sqlist));//为接下来的节点开辟一个内存 // s->coefficient=x; // s->exponent=y; // s->link=l->link; // l->link=s; //} //------------------------------------------------------------- //这里我发现用尾插法，头节点可以不需要，后面反而碍事，于是我试着把它去掉 //------------------------------------------------------------- void insertlist(sqlist*&l,int n){ int x,y; sqlist*s,*r; l=(sqlist*)malloc(sizeof(sqlist)); r=l; for(int i=0;i<n;i++){ // r->link=NULL; s=(sqlist*)malloc(sizeof(sqlist)); cin>>x>>y; s->coefficient=x; s->exponent=y; r->link=s; r=s; } r->link=NULL; //如果必须要头节点，那最后我们可以给头节点删除了 sqlist*t; t=l; l=l->link; free(t); } //--------------------------------------------------- //我最终是终于明白了，所谓必要的头结点是为了寻址而必要的，当我给头结点一开始就删除后， //用自己作为头结点的话，因为自身本身就是在不断调用，这样链表虽然没有断，却无法用传递参数 //来表示头结点了， //之后我发现去掉头节点，只能读入一组数据了，莫名其妙的我也找不出bug //----------------------------------------------------- //void insertlist(sqlist*&l,int n){ // int x,y; // sqlist*r;//这里需要一个指针来作为中介 // r=(sqlist*)malloc(sizeof(sqlist));//这里加了初始化，但是发现还是不行，链表好像断了 // for(int i=0;i<n;i++){ // l=(sqlist*)malloc(sizeof(sqlist)); // cin>>x>>y; // l->coefficient=x; // l->exponent=y; // r->link=l; // r=l; // } // r->link=NULL; // l=r->link; // free(r); //} void displist(sqlist*l){ sqlist*p=l; while(p!=NULL&&p->coefficient<1000000){ cout<<p->coefficient<<" "<<p->exponent<<" "; p=p->link; } cout<<endl; } sqlist* combinelist(sqlist*l,sqlist*p){//conbine（合并） sqlist*q,*r; sqlist*s;//头节点 s=(sqlist*)malloc(sizeof(sqlist)); r=s; sqlist*t1=l,*t2=p; while(t1&&t2){//当t1和t2都不空的时候 if(t1->exponent==t2->exponent){ q=(sqlist*)malloc(sizeof(sqlist));//这里我应该写一个单个值的插入函数，为了省事，就只能让代码遭罪了 q->coefficient=t1->coefficient+t2->coefficient; q->exponent=t1->exponent; r->link=q; r=q; t1=t1->link; t2=t2->link; } else if(t1->exponent>t2->exponent){ q=(sqlist*)malloc(sizeof(sqlist)); q->coefficient=t1->coefficient; q->exponent=t1->exponent; r->link=q; r=q; t1=t1->link; } else{ q=(sqlist*)malloc(sizeof(sqlist)); q->coefficient=t2->coefficient; q->exponent=t2->exponent; r->link=q; r=q; t2=t2->link; } } while(t1){ q=(sqlist*)malloc(sizeof(sqlist)); q->coefficient=t1->coefficient; q->exponent=t1->exponent; r->link=q; r=q; t1=t1->link; } while(t2){ q=(sqlist*)malloc(sizeof(sqlist)); q->coefficient=t2->coefficient; q->exponent=t2->exponent; r->link=q; r=q; t2=t2->link; } r->link=NULL; //如果必须要头节点，那最后我们可以给头节点删除了 sqlist*t; t=s; s=s->link; free(t); return s; } //这里我的想法是，每乘一个数，放入一个新的链表中，然后要做的事情是排序，合并同类项 //我又想了想，发现排序根本不可能，于是我想到在插入的时候就应该排序好，并且遍历一遍寻找同类项 //sqlist* multiply(sqlist*l,sqlist*p){//multiply（相乘） // bool bl; // sqlist *t1=l,*t2=p; // sqlist *s,*r; // //这里我还是用尾插法 // sqlist *head; // head=(sqlist*)malloc(sizeof(sqlist)); // r=head; // int coefficient,exponent; // while(t1){ // while(t2){ // r->link=NULL; // coefficient=t1->coefficient*t2->coefficient; // exponent=t1->exponent+t2->exponent; // //这里开始我们的插入时排序，和插入时合并 // while(head){ // //先判断合并 // bl=1; // if(head->exponent==exponent){ // head->coefficient+=coefficient;//这里有种难ban的情况就是head->cofficient可能会变成0，我先不考虑 // bl=0; // break; // } // if(exponent<head->exponent){ // s=(sqlist*)malloc(sizeof(sqlist)); // s->coefficient=coefficient; // s->exponent=exponent; // s->link=head->link; // head->link=s; // bl=0; // break; // } // head=head->link; // } // if(bl){ // s=(sqlist*)malloc(sizeof(sqlist)); // s->coefficient=coefficient; // s->exponent=exponent; // r->link=s; // r=s; // } // t2=t2->link; // } // t1=t1->link; // } // r->link=NULL; //} sqlist* multiply(sqlist* L1,sqlist* L2){ sqlist* tmpL1 = L1; sqlist* tmpL2 = L2; sqlist* mul=(sqlist*)malloc(sizeof(sqlist)); mul->link = NULL; sqlist* head = mul; sqlist* t; for(;tmpL1;tmpL1=tmpL1->link) for(tmpL2 = L2;tmpL2;tmpL2=tmpL2->link){ t = (sqlist*)malloc(sizeof(sqlist)); t->coefficient = tmpL1->coefficient* tmpL2->coefficient; // 系数相乘 t->exponent = tmpL1->exponent + tmpL2->exponent; // 指数相加 t->link = NULL; head = combinelist(t,mul); // 将新增结点和之前已经排好序的结点排序 mul = head; // 重新确定开头 } return head; } int main(){ sqlist *l ,*p; int n; cin>>n; insertlist(l,n); cin>>n; insertlist(p,n); // displist(l); // displist(p); sqlist *s; s=combinelist(l,p); displist(s); sqlist *m; m=multiply(l,p); displist(m); } |
