一元多项式2022优秀文档

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第2章 线性表,2.1,线性表的逻辑结构,2.2,线性表的顺序表示和实现,2.3,线性表的链式表示和实现,2.4,一元多项式的表示和相加,1,2.4 一元多项式的表示和相加,2,但当多项式的次数很高且零系数项很多时，更适于用链表存储。,机内存储方式？,一般用,顺序存储,p,0,p,1,p,2,p,n,-1,p,n,链式存储,0.0 -1,p,m,e,m,p,1,e,1,通常设计,两个数据域,（系数项和指数项）和,一个指针域,头结点,只存系数项（但零系数项也不能遗漏）,P,2000,(,x,)=1+,3,x,1000,+5,x,2000,3,用抽象数据类型定义,一元多项式,（参见P40）,ADT,Polynomial,数据对象,：,D=a,i,|a,i,TermSet,i=1,2,m,m0,TermSet中的每个元素包含一个表示系数的实数和表示指数的整数,数据关系：,R1=|a,i-1,a,i,D,且a,i-1,中的指数值,expn,=、,Pb-expn,等情况，再决定是将两系数域的数值相加（并判其和是否为0），还是将较高指数项的结点插入到新表c中。,3,14,2 8,1 0 ,a,Pa,8,14,-3 10,10 6 ,b,Pb,11,14,-3 10,2 8,1 0 ,c,Pc,10 6,+,注：,P,a,P,a,P,b,，并销毁一元多项式P,b,。,9,运算效率分析：,(1),系数相加,0,加法次数,min(m,n),其中,m,和,n,分别表示表,A,和表,B,的结点数。,(2),指数比较,极端情况是,表,A,和表,B,没有一项指数相同，比较次数最多为,m+n-1,合计时间复杂度为,O(m+n),算法略,10,本章小结,1.了解线性表的逻辑结构特性数据元素之间存在着线性关系；,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构；,用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。,3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。,11,作业,2.8 2.10,2.19 2.21,2.22 2.29 2.38,12,