List |
您所在的位置：网站首页 › 一元多项式类 › List |
List
|
多项式 ADT
目录
一元多项式，我们一般用系数表示法来表示，如下图： 多项式这类数据我们通常有以下两种实现方式。 二、采用单结构（系数数组 + 最高指数） 1、表示多项式的结构最容易想到的当然是，直接用一个数组来储存对应项的系数。假设我们储存的多项式最高指数不超过MAX_NUM（常量），那么我们可以将每个项的指数与数组的下标对应，数组内对应存入该项的系数 。 1）结构的代码实现： typedef struct node { int CoffArray[MAX_NUM + 1]; //系数数组 int HighestExponent; //最高指数 } * Polynomial, node; 2）产生一个初始化多项式：很重要，将系数和最高指数置零。 Polynomial CreatPolynomial() { Polynomial temp = (Polynomial)malloc(sizeof(node)); temp->HighestExponent = 0; memset(temp->CoffArray, 0, (MAX_NUM + 1) * sizeof(int)); return temp; } 2、多项式的加法这种表示方法下做加法很简单，两个多项式的相加的结果：其 最高指数为两多项式最高指数中更大的那个，由于数组下标对应指数，那么 系数数组直接对应下标相加即可。 Polynomial AddPolynomial (Polynomial p1, Polynomial p2) { Polynomial ans = CreatPolynomial(); //相加后的最高指数 ans->HighestExponent = p1->HighestExponent > p2->HighestExponent ? p1->HighestExponent : p2->HighestExponent; //对应系数相加 for(int i = 0; i HighestExponent; i++) { ans->CoffArray[i] = p1->CoffArray[i] + p2->CoffArray[i]; } return ans; } 3、多项式的乘法多项式乘法的实现也不复杂，模拟我们计算的条理即可。两个多项式的相乘的结果：其 最高指数为两多项式最高指数相加 ，依次相乘每一项，系数相乘，指数相加。即 将系数相乘的结果累加到系数数组的对应下标（指数相加结果）。 Polynomial MultPolynomial (Polynomial p1, Polynomial p2) { Polynomial ans = CreatPolynomial(); //相乘后的最高指数 ans->HighestExponent = p1->HighestExponent + p2->HighestExponent; //将p2与p1每一项依次相乘 for(int i = 0; i HighestExponent; i++) { for (int j = 0; j HighestExponent; j++) { ans->CoffArray[i + j] += p1->CoffArray[i] * p2->CoffArray[j]; } } return ans; }以上这种实现方式很简单，也很直接。但是有个缺陷，若项数并不多且指数分隔很大，那么系数数组将会有很多为0的，浪费空间。并且在进行相加相乘操作时，我们需要依次遍历系数数组的每一位，但是有很多为0（不存在该指数对应的项），此时未免有点浪费时间。所以我们更多地采用下面这种方法实现多项式。 三、采用链表结构（系数 + 指数） 1、表示多项式的结构与上面那种方法不同，我们采用更加灵活的链表来表示。链表的每一个节点为多项式中的一项（单项式），其中包含指数域、系数域、指针域。 1）此结构的代码实现: typedef struct node { int Coefficient; //系数 int Exponent; //指数 struct node * next; } * NODE, node; 2）产生一个初始化单项式：很重要，将系数和最高指数置零 NODE CreatNode(int coef, int exp) { NODE temp = (NODE)malloc(sizeof(node)); temp->Coefficient = coef; temp->Exponent = exp; temp->next = NULL; return temp; } 3）创建一个多项式，即返回一个头节点： NODE CreatPolynomial() { NODE head = CreatNode(0, -1); return head; } 4）向多项式中插入项多项式创建好后，需要对内插入所有单项式，插入函数如下： 为了之后方便运算，注意链表中节点顺序按照指数升序排列。 head为多项式的头节点，temp为已经生成的待插入节点。 注意： 1、插入若能和已有项结合，如结果为零的项要删除。 2、插入函数可以简化后面的代码，不要觉得没必要，我修改了多次，这个版本最简单的。 void insertNode(NODE head, NODE temp) { NODE p = head; //找到插入的位置：p之后 while (p->next && p->next->Exponent Exponent) p = p->next; //合并相同指数的项 if(p->next->Exponent == temp->Exponent) { p->next->Coefficient + temp->Coefficient; //出现相加后系数为零 if(!p->next->Coefficient) { p->next = p->next->next; //删除 } return; } //插入 temp->next = p->next; p->next = temp; } 2、多项式的加法由于我们多项式的链表节点已经升序表示，那么我们可以对两个多项式的项依次匹配相加：同时从头遍历两个多项式p1、p2，将p2加到p1上：在p1找p2对应项（指数相同的项），若能找到就把该p2项加到对应p1项上；否则就把该p2项插入p1的合适位置（不影响p1指数升序）。 注意要删除结果为零的项。 NODE AddPolynomial(NODE head1, NODE head2) { NODE p1 = head1; NODE p2 = head2->next; while (p2) { while(p1->next && p1->next->Exponent Exponent) { p1 = p1->next; } //第一个多项式已经遍历完 if(!p1->next) p1->next = p2; //把剩余未加部分全部插入末尾 //找到相同项，相加 if(p1->next->Exponent == p2->Exponent) { p1->next->Coefficient += p2->Coefficient; //出现结果系数为零，删除 if(!p1->next->Coefficient) { p1->next = p1->next->next; } } else { //没有相同项，插入 NODE temp = CreatNode(p2->Coefficient, p2->Exponent); temp->next = p1->next; p1->next = temp; } p2 = p2->next; } return head1; } 3、多项式的乘法下面是经过几次修改最简单的版本。 还是从我们简单的计算逻辑出发，将 p2中每一项分别与p1相乘，每次相乘生成的结果项插入到答案多项式中（所以说上面的插入函数很重要），最终返回答案多项式。 NODE MutiPolynomial(NODE head1, NODE head2) { NODE p1 = head1->next; NODE p2 = head2->next; NODE ans = CreatPolynomial(); while(p1) { while (p2) { //两项相乘 int coef = p1->Coefficient * p2->Coefficient; //系数相乘 int exp = p1->Exponent + p2->Exponent; //指数相加 NODE temp = CreatNode(coef, exp); //两项相乘后的项 insertNode(ans, temp); //将结果项插入结果多项式中 p2 = p2->next; } p1 = p1->next; } return ans; } end欢迎关注个人公众号“鸡翅编程”，这里是认真且乖巧的码农一枚，旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~ |
可以看到，多项式里最重要的是两个要素：指数(Exponent)与其对应的系数(Coefficient)。对于多项式比较重要的处理是：多项式加法和乘法。
【本文地址】
今日新闻 |
推荐新闻 |