本文为数据结构之线性结构(应用实例),根据网课而整合的笔记。
栗子:
设计函数分别求两个一元多项式的乘积与和
该题的输入与输出样例:
求解思路 多项式表示程序框架读多项式加法实现乘法实现多项式输出 一、多项式的表示(仅表示非零项)
数组:
编程简单、调试容易需要事先确定数组大小(若不确定会造成空间浪费)链表:
动态性强编程略为复杂、调试比较困难PS:一种比较好的实现方法是:动态数组
下面介绍链表表示
数据结构设计
typedef struct PolyNode *Polynomial;struct PolyNode{int coef;/*系数*/int expon;/*指数*/Polynomial link;}; 二、程序框架搭建 int main(){读入多项式1读入多项式2乘法运算并输出加法运算并输出return 0;}需要设计的函数:
读入一个多项式两多项式相乘两多项式相加多项式输出 int main(){Polynomial P1,P2,PP,PS;P1 = ReadPoly();P2 = ReadPoly();PP = Mult(P1,P2);PrintPoly(PP);PS = Add(P1,P2);PrintPoly(PS);return 0;} 三、如何读入多项式输入数据格式:4 3 4 -5 2 6 1 -2 0(4为4组数,然后再循环一对一对读入)
Polynomial ReadPoly(){...scanf("%d",&N);...while(N--){scanf("%d %d",&c,&e);/*每对数据按指数递减顺序读入*/Attach(c,e,&Rear);/*构造并插入新结点*/}...return P;}思考:Rear初值是多少?
两种处理方法:
1.Rear初值为NULL
在Attach函数中根据Rear是否为NULL做不同处理(Attach一开始会判别Rear是否为NULL,如果是NULL则申请结点把Rear指向NULL改成把Rear指向这个结点;如果不为NULL则直接把新的结点插入后面)
2.Rear指向一个空结点
结束后要把最后的空结点删掉
架构
Polynomial Add(Polynomial P1,Polynomial P2){...t1 = P1,t2 = P2;P = (Polynomial)malloc(sizeof(struct PolyNode));/*构造空结点*/P->link = NULL;Rear = P;while(t1 && t2){if(t1->expon == t2->expon){...}else if(t1->expon > t2->expon){...}else{...}}while(t1){...}while(t2){...}...return P;}第一个while 判断指数,计算系数
第二个while和第三个while 分别判断t1和t2为空的情况
方法:
1.将乘法运算转换为加法运算
将P1当前项(ci,ei)乘P2多项式,再加到结果多项式里
t1 = P1;t2 = P2;P = (Polynomial)malloc(sizeof(struct PolyNode));P->link = NULL;Rear = P;while(t2){Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);t2 = t2->link;}2.逐项插入
将P1当前项(ci,ei)乘P2当前项(c2i,e2i),并插入到结果多项式中。关键是要找到插入位置
初次结果多项式可由P1第一项乘P2获得(如上)
Polynomail Mult(Polynomial P1,Polynomial P2){ Polynomial P,Rear,t1,t2,t; int c,e; if(!P1||!P2) return NULL;t1 = P1;t2 = P2;P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL; Rear = P;while(t2){/*先用P1的第1项乘以P2,得到P*/Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear); t2 = t2->link;}t1 = t1->link;while(t1){t2 = P2;Rear = P;while(t2){e = t1->expon + t2->expon;/*计算指数*/c = t1->coef*t2->coef;/*计算系数*/while(Rear->link&&Rear->link->expon>e) Rear = Rear->link; if(Rear->link&&Rear->link->expon == e){ if(Rear->link->coef+c) Rear->link->coef+=c; else{ t = Rear->link; Rear->link=t->link; free(t); } } else{ t = (Polynomial)malloc(sizeof(struct PolyNode)); t->coef = c;t->expon = e; t->link = Rear->link; Rear->link = t;Rear = Rear->link; }t2 = t2->link;}t1 = t1->link;}t2 = P;P = P->link; free(t2); return P;} 六、如何将多项式输出 void PrintPoly(Polynomial P){/*输出多项式*/int flag = 0;/*辅助调整输出格式用*/ if(!P){ printf("0 0n"); return; } while(P){ if(!flag) flag = 1; else printf(" "); printf("%d %d",P->coef,P->expon); P = P->link; }printf("n");}声明:部分资料源自网络,如有侵权,请联系我删除!
文中如存在谬误、混淆等不足,欢迎批评指正!