第三章线性表-2(1).pptVIP

3.5 有序表 　　所谓有序表，是指这样的线性表，其中所有元素以递增或递减方式有序排列。为了简单，假设有序表元素是以递增方式排列。从中看到，有序表和线性表中元素之间的逻辑关系相同，其区别是运算实现的不同(插入运算不一样，其余运算相同)。 有序表 顺序表 链 表 逻辑结构 存储结构 一元多项式的表示及相加 用线性表表示为: P = (p0, p1, …，pn) 一元多项式 ？S(x) = 1 + 3x10000 – 2x20000 用线性表表示一元多项式 一般情况下的一元多项式可写成 Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem 其中：pi 是指数为ei 的项的非零系数， 0≤ e1 e2 ┄ em = n （（p1, e1）, (p2, e2), ┄, (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999 可表示为：（（7，3），（－2，12），（－8，999）） 用线性表表示一元多项式 抽象数据类型一元多项式的定义 ADT Polynomial { 数据对象： D＝{ai | ai∈TermSet, i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个表示系数的实 数和表示指数的整数 } 数据关系： R1＝{ai-1 ,ai |ai-1,ai∈D,且ai-1中的指数值＜ai中的指数值，i=2,...,n } 数学表示 pn(x)=p0 + p1x + p2x2 + … + pnxn A(x)=15+6x+9x7+3x18 B(x)=4x+5x6+16x7 C(x)= A(x)+B(x)= 15+10x+5x6+25x7+3x18 一元多项式的相加操作示例 -1 A(x) 15 0 6 1 9 7 3 18 ^ -1 B(x) 4 1 5 6 16 7 ^ （1）若p-expq-exp, 则使指针后移p=p-next,见（a）。 （2）若p-exp=q-exp， 若系数和不为0，将两个节点系数相加，则修改 p-ceof； 若系数和为0，则应借助s释放p、q节点，而使p、q分别指向多项式A、B的下一个节点，见（b）。 （3）若p-expq-exp，将q节点在p节点之前插入A中，见（c）。 -1 A(x) 15 0 6 1 9 7 3 18 ^ -1 B(x) 4 1 5 6 16 7 ^ -1 A(x) 15 0 6 1 9 7 3 18 ^ -1 B(x) 4 1 5 6 16 7 ^ -1 A(x) 15 0 6 1 9 7 3 18 ^ -1 B(x) 4 1 5 6 16 7 ^ q p p （a）指针后移 p q q s p q q (1)p-expq-exp (2)p-exp=q-exp （b）系数相加 (3)p-expq-exp （c）将q节点在p节点之前插入A中 typedef struct Pnode {int coef;/*系数域*/ int exp; /*指数域*/ struct pnode *next; }Pnode,*Polytp; void main( ) {Polytp polya,polyb; printf(输入数据建立多项式A(X):(以0,0结束!)\n); polya=(Pnode *)malloc(sizeof(Pnode)); polycreate(polya); printf(A(x)=); print(polya); printf(输入数据建立多项式B(X):(以0,0结束!)\n); polyb=(Pnode *)malloc(sizeof(Pnode)); polycreate(polyb); printf(B(x)=); print(polyb); polyadd(polya,polyb); printf(多项式相加结果：\nA(X)+B(X)=); print(polya); } void polycreate(Polytp head)