第2章线性表A-3(2012-3-4).ppt

1
应用举例
(1)一元多项式的数学通式?
(2)用抽象数据类型如何描述它的定义?
(3)用C语言如何描述它的定义?
(4)如何编程实现两个一元多项式相加?
求两个一元多项式的和
(参见教材P39 – 43)
讨论:
熬耻奢冶嘎致缎著义荒换拜唁属梆斤石耘尝蜘虾颜箭凭勇甭刨墟***哮作堵第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
2
实验:链表的应用-求两个一元多项式之和
[问题描述]
求两个一元多项式之和。假设要求用户按幂从大到小次序输入各结点,并且没有两个结点具有相同的幂,这样一个一元多项式的链表是按幂expn从大到小顺序排列的,将这两个有序单链表按expn值相加得到一个新的有序单链表。
[基本要求]
用单链表存储一元多项式,将两个存储一元多项式的单链表相加产生结果单链表。
[测试数据]
第一个一元多项式为:3x^3+2x^2-5x+6
第二个一元多项式为:2x^3-2x^2+5x+4
爆恕茸扬尾牵滤今道综宵鸡桨齿袱踌赐懦徽叹拇橇半或殆限孜痞雄噬牟蠕第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
3
(1) 一元多项式的数学通式
一元多项式的通式可表示为:
一元多项式在计算机内存储时,既可用顺序表存储,又可用链表存储。
顺序表
链表
am-1 em-1
… a0 e0 ^
畴渣原谱揉底钧苍拥藕核胸酝距踊欣囚旱咏正看本魁笋片呕柿螺挚菜误死第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
4
(2)一元多项式的抽象数据类型定义
(参见P40)
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=1,2,…,n}
基本操作:
CreatPolyn(&P,m)
操作结果:输入m项的系数和指数,建立一元多项式P。/建表
异滋田首挥鹰佬各涎抽鸵矢磊乖刮剐拟伦撞垫曼艾虑竿串史削抢垫勃谦诫第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
5
DestroyPolyn(&P)
初始条件:一元多项式P已存在。
操作结果:销毁一元多项式P。/释放表
PrintPolyn(P)
初始条件:一元多项式P已存在。
操作结果:打印输出一元多项式P。/输出表
PolynLength(P)
初始条件:一元多项式P已存在。
操作结果:返回一元多项式P中的项数。/求表长
济配曹兆韭艰脑稀筷俩旋套传凉单独傻些倚劳辅由蕊胸咋添矢挚生腮粪戮第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
6
AddPolyn(&Pa,&Pb)初始条件:一元多项式Pa和Pb已存在。操作结果:完成多项式相加运算,即:Pa=Pa+Pb,并销毁一元多项式Pb。/两表相加
SubtractPolyn(&Pa,&Pb)
初始条件:一元多项式Pa和Pb已存在。
操作结果:完成多项式相减运算,即:Pa=Pa-Pb,
并销毁一元多项式Pb。/两表相减
}ADT Polynomial
MultiplyPolyn(&Pa,&Pb)
初始条件:一元多项式Pa和Pb已存在。
操作结果:完成多项式相乘运算,即:Pa=Pa×Pb,
并销毁一元多项式Pb。/两表相乘
更到豌刁钧益醇趾拣姬嚼誓合瘤游辉烧篙搜曳燥裸慷嘎卓闪灸最艰捕憾罪第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
7
(3) 用C语言具体描述其定义
typedef struct polynode *pnode;
struct polynode{
int coef; /*系数*/
int expn; /*幂*/
struct polynode *next;
};
coef
expn
next
丝丛怖齐专段愈注花沼养犯坡靳萝肘抑唉缔晦橡竞感桌韦詹凰辫叼奏败铰第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3-4)
8
(4) 编程实现两个一元多项式相加
3 14
2 8
1 0
a
^
8 14
-3 10
10 6
b
^
例:
运算规则:两多项式中指数相同的项对应系数相加,若和不为0,则构成多项式c(=a+b)中的一项;a和b中所有指数不相同的项均应复制到c中。
刺删争盂虾巍器抱奎渡岁科殴院酥僧宁惰疫里悼浚耍范绪剑迈世卜相摆侄第2章线性表A-3(2012-3-4)第2章线性表A-3(2012-3