文章目录

数据结构-浙江大学-陈越、何钦铭——第一讲示例代码：一元多项式的乘积与和（C语言）数学表示输入与输出代码（C语言）

数据结构-浙江大学-陈越、何钦铭——第一讲示例代码：一元多项式的乘积与和（C语言）

注：以下代码是根据个人理解所写，与教学视频中代码略有出入，如有错误，烦劳指出。

数学表示

$$(1)3x^4-5x^2+6x-2$$ $$(2)5x^{20}-7x^4+3x$$ $$(1)+(2)=5x^{20}-4x^4-5x^2+9x-2$$ $$(1)\times (2)=15x^{24}-25x^{22}+30x^{21}-10x^{20}-21x^8+35x^6-33x^5+14x^4-15x^3+18x^2-6x$$

输入与输出

输入示例：（第一个数字代表项数，接下来的每两个数字分别对应每一项的系数和指数） 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

代码（C语言）

main.c文件

#include<stdio.h> #include<stdlib.h> #include"Poly.h" int main(void) { Polynomial p1=NULL, p2=NULL, pp=NULL, ps=NULL; //读入多项式p1、p2 p1 = ReadPoly(); p2 = ReadPoly(); //p1、p2相乘并输出结果 pp = Mult(p1, p2); PrintPoly(pp); //p1、p2相加并输出结果 ps = Add(p1, p2); PrintPoly(ps); //释放空间 FreePoly(p1); FreePoly(p2); FreePoly(pp); FreePoly(ps); system("pause"); return 0; }

Poly.h文件

#include<stdio.h> #include<stdlib.h> struct PolyNode { int coef;//系数 int expon;//指数 struct PolyNode *link; }; typedef struct PolyNode *Polynomial; Polynomial ReadPoly(void); Polynomial Mult(Polynomial, Polynomial); Polynomial Add(Polynomial, Polynomial); void PrintPoly(Polynomial); void Attach(int, int, Polynomial *); void FreePoly(Polynomial);

ReadPoly.c文件

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include"Poly.h" Polynomial ReadPoly(void) { Polynomial p = NULL, rear = NULL; int c = 0, e = 0, n = 0, i = 0; //读出一共多少项 scanf("%d", &n); //生成链表头空节点 p = (Polynomial)malloc(sizeof(struct PolyNode)); p->link = NULL; rear = p; //将当前项插入多项式尾部 for (i = 0; i < n; i++) { scanf("%d %d", &c, &e); Attach(c, e, &rear); } //删除临时生成的头结点 rear = p; p = p->link; free(rear); return p; } void Attach(int c, int e, Polynomial *rear) { Polynomial p; //创建新节点存储信息 p = (Polynomial)malloc(sizeof(struct PolyNode)); p->coef = c; p->expon = e; p->link = NULL; //将新节点接入链表后面并让rear指向新节点 (*rear)->link = p; (*rear) = p; }

Add.c文件

#include<stdio.h> #include<stdlib.h> #include"Poly.h" Polynomial Add(Polynomial p1, Polynomial p2) { Polynomial t1 = p1, t2 = p2,p=NULL,rear=NULL,t=NULL; //建立一个空的节点，rear指向 p = (Polynomial)malloc(sizeof(struct PolyNode)); p->coef = 0; p->expon = 0; p->link = NULL; rear = p; while (t1&&t2) { //在rear指向的节点之后建立新的节点用于存储相加结果 rear->link = (Polynomial)malloc(sizeof(struct PolyNode)); //如果两个多项式的当前项指数相同，结果为系数相加，指数不变 if (t1->expon == t2->expon) { rear->link->expon = t1->expon; rear->link->coef = t1->coef + t2->coef; t1 = t1->link; t2 = t2->link; if (rear->link->coef == 0) { free(rear->link); } else { rear = rear->link; } } //如果两个多项式的当前项指数不同，将指数较大的先放入结果多项式中。 else if (t1->expon > t2->expon) { rear = rear->link; rear->expon = t1->expon; rear->coef = t1->coef; t1 = t1->link; } else { rear = rear->link; rear->expon = t2->expon; rear->coef = t2->coef; t2 = t2->link; } rear->link = NULL; } //当一个t1或者t2有一个已经为NULL之后，将还没有等于NULL的那一个单独处理。 while (t1) { //在rear指向的节点之后建立新的节点用于存储相加结果 rear->link = (Polynomial)malloc(sizeof(struct PolyNode)); rear = rear->link; rear->expon = t1->expon; rear->coef = t1->coef; rear->link = NULL; t1 = t1->link; } while (t2) { //在rear指向的节点之后建立新的节点用于存储相加结果 rear->link = (Polynomial)malloc(sizeof(struct PolyNode)); rear = rear->link; rear->expon = t2->expon; rear->coef = t2->coef; rear->link = NULL; t2 = t2->link; } //删除头节点 rear= p; p = p->link; free(rear); return p; }

Mult.c文件

#include<stdio.h> #include<stdlib.h> #include"Poly.h" Polynomial Mult(Polynomial p1, Polynomial p2) { Polynomial currentPtr1 = NULL, currentPtr2 = NULL,pp=NULL,pptemp=NULL,rear=NULL; //将p1的每一项与p2单独相乘，得到的多项式再累加 for (currentPtr1 = p1; currentPtr1!=NULL; currentPtr1 = currentPtr1->link) { //pptemp指向p1当前项与p2相乘得到的多项式，以下建立一个头节点 pptemp = (Polynomial)malloc(sizeof(struct PolyNode)); pptemp->link = NULL; rear = pptemp; //创建节点存储p1当前项与p2相乘的结果 for (currentPtr2 = p2; currentPtr2 != NULL; currentPtr2 = currentPtr2->link) { Attach(currentPtr1->coef*currentPtr2->coef, currentPtr1->expon + currentPtr2->expon, &rear); } //删除pptemp头节点 rear = pptemp; pptemp = pptemp->link; free(rear); rear = NULL; //将结果累加 pp = Add(pp, pptemp); //清空p1当前项与p2多项式相乘的结果，以便存储p1下一项与p2相乘结果 FreePoly(pptemp); pptemp = NULL; } return pp; }

PrintPoly.c文件

#include<stdio.h> #include<stdlib.h> #include"Poly.h" void PrintPoly(Polynomial p) { while (p!=NULL) { printf("%d %d ", p->coef, p->expon); p = p->link; } printf("\n"); }

FreePoly.c文件

#include<stdio.h> #include<stdlib.h> #include"Poly.h" void FreePoly(Polynomial p) { Polynomial currentPtr = NULL; while (p != NULL) { currentPtr = p->link; free(p); p = currentPtr; } }