《(2.5.1)--ch2-05一元多项式的表示和运算.pdf》由会员分享,可在线阅读,更多相关《(2.5.1)--ch2-05一元多项式的表示和运算.pdf(8页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构与算法Data Structures and Algorithms一元多项式 Single-Variable PolynomialsData Structures and AlgorithmsData Structures and AlgorithmsCHAPTER2 Linear List2.1 ApplicationApplication 2:Unary polynomial operator To realize a one-variable polynomial arithmetic unit,we must first design a suitable data stru
2、cture that represents the univariate polynomial P=p0+p1X+p2X2+pnXn and support the following operations of the polynomial.(1)Create polynomial.(2)Output polynomial.(3)+,Add two polynomials,create and output the sum polynomial.(4),Subtract two polynomials,Create and output subtract polynomial。(5)*,Po
3、lynomial multiplication。(6)(),Calculate the value of a polynomial。(7)derivative(),Calculate the derivative of a polynomial。Data Structures and AlgorithmsData Structures and Algorithms3CHAPTER2 Linear List2.6 Representation and addition of one-variable polynomialsA one-variable polynomial pn(x)can be
4、 written as an ascending power:pn(x)=p0+p1x+p2x2+p3x3+pnxn Can be stored in a linear list:(p0,p1,p2,.,pn)example:2+x5+10 x100 Can store only non-zero itemsUse singly linked list to store polynomial node structure:typedef struct Polynode int coef;int exp;Polynode*next;Polynode,*Polylist;Data Structur
5、es and AlgorithmsData Structures and Algorithms4CHAPTER2 Linear List2.6 Representation and addition of one-variable polynomialsAdd two polynomialsA(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8-17 03 19 8517polya-18 1227-98 polybpqtailtailp11tailptempqfree(temp);tailqtemppfree(temp);tempq=NULL;free(temp);Data St
6、ructures and AlgorithmsData Structures and Algorithms5CHAPTER2 Linear List2.6 Representation and addition of one-variable polynomialsAdd two polynomialsCalculation rules:Add the corresponding coefficients of all terms with the same exponent in the two polynomials.If the sum is not zero,it constitute
7、s one item in the sum polynomial;all terms with different exponents are copied into the sum polynomial.if p-expexp,Then the node pointed to by the node p should be one of the sum polynomials,so that the pointer p moves backward;if p-exp=q-exp,Then add the coefficients in the two nodes,modify the coe
8、fficient domain of node p when the sum is not zero,and release the node q;if the sum is zero,there is no item in the sum polynomial,and p is deleted from A Node,release p and q nodes at the same time;if p-expq-exp,Then the node pointed to by the node q should be one of the sum polynomials,insert the
9、 node q before the node p,and make the pointer q move backward on the original linked list.Data Structures and AlgorithmsData Structures and Algorithms6Convention:The coefficient is 0 as the end sign,and the index is arranged in ascending order.Enter the coefficients and exponents of the polynomial,
10、and use tail insertion to create a linked list of one-variable polynomials。CHAPTER2 Linear List2.6 Representation and addition of one-variable polynomials Polylist polycreate()Polynode*head,*rear,*s;int c,e;rear=head=(Polynode*)malloc(sizeof(Polynode);scanf(“%d,%d”,&c,&e);while(c!=0)s=(Polynode*)mal
11、loc(sizeof(Polynode);s-coef=c;s-exp=e;rear-next=s;rear=s;scanf(“%d,%d”,&c,&e);rear-next=NULL;return(head);The specific is left as an experiment topic7Two polynomial addition algorithm realization ideas:void polyadd(Polylist polya;Polylist polyb)/*p and q point to the current calculation node in the
12、polya and polyb linked lists,respectively*/*rear points to the end node in the sum polynomial linked list*/while p!=NULL&q!=NULL)if (p-expexp)/*Add the p node to the sum polynomial*/else if(p-exp=q-exp)/*If the exponents are equal,the corresponding coefficients are added.If the coefficient is 0,delete p and q nodes*/else /*Add the q node to the polynomial*/*Add the remaining nodes in the polynomial polya or polyb to the sum polynomial*/数数 据据 结结 构构 与与 算算 法法 ThanksD Da at ta a S St tr ru uc ct tu ur re es s a an nd d A Al lg go or ri it th hm ms s