一元多项式最大公因式的求法
摘要 多项式理论是高等代数的重要组成部分，求最大公因式在多项式理论研究中占有显著地位.求两个多项式的最大公因式，一般采用因式分解法和辗转相除法.本文还试图从：??1将两种方法结合起来??2矩阵的初等变换法??3矩阵的斜消变换法以及数值矩阵法等不同角度给出了一元多项式的最大公因式的不同求法.
关键词 因式分解法；辗转相除法；斜消变换法；矩阵初等变换 一 引言
最大公因式的概念是多项式代数的重要内容，关于最大公因式的求法一般主要讨论两个多项式的最大公因式的求法，方法主要有因式分解法和辗转相除法．考虑n 个多项式的最大公因式时，往往也是通过两两多项式求最大公因式，因此求多个多项式的最大公因式需要多次对两个多项式进行运算．为了改进运算方法,我们给出以下的矩阵初等变换法，斜消变换法等利用多项式矩阵和数字矩阵的运算来求解最大公因式，虽然不尽完善，但也是一种很大的突破．本文将在此基础之上对求最大公因式的方法进一步作一个较全面的探讨． 二 问题的提出
在高等代数教材[]1中，有如下定义和定理：
定义1 如果多项式()x ?既是()x f 的因式，又是()x g 的因式，那么()x ?就称为()x f 与
()x g 的一个公因式.
定义2 设()x f ，()x g 是][x P 中两个多项式. ][x P 中多项式()x d 称为()x f ，()x g 的一个最大公因式，如果它满足下面两个条件：
1）()x d 是()x f ，()x g 的公因式； 2）()x f ，()x g 的公因式全是()x d 的因式.
我们约定，用()()()x g x f ,来表示最高次项系数为1的那个最大公因式. 三 问题的解决
由定义1和定义2我们很容易得到一种求多项式的最大公因式的方法—因式分解法. 3.1因式分解法
利用两个（多个）多项式的标准分解式可以很快地得到它们的最大公因式.如：设多项
式)(x f 与)(x g 的标准分解式分别为：
=)(x f );()()(2121x p x p x ap r m r m m Λ)()()()(2121x p x p x bp x g r n
r n n ΛΛ=
（上式b a ,分别是f(x),g(x)的首项系数.)(,)(1x p x p r Λ）是两两不等的首项系数为1的不可约多项式，r r n n m m ΛΛ,,,11 是非负整数，则
)()()())(),((2
211x p x p x p x g x f kr r k k Λ=这里r i n m k i i i ,,2,1),,m in(Λ==
例3.1.1 证明
1))1(,1(,01222=+-++≥?++n n x x x x n
证明：
n
n x x x x )12)(1()1(212+++=++n
n n x x x x x x x x x )1()1)(1()1(])1[(22++++++=++++=Λ
最后一项
)1()1(22--=+-+x x x x x x n n n
不能被
12++x x
整除 故命题得证.
对于因式分解法，虽然，直观，原理简单易懂.但当多项式次数较高时，分解的过程往往比较困难，故此方法并不理想. 没有广泛适用性.
定理1 对于][x P 中任意两个多项式()x f ，()x g ，在][x P 中存在一个最大公因式()x d ，
且()x d 可以表成()x f ，()x g 的一个组合，即有][x P 中的多项式()x u ,()x v 使
()()()()()x g x v x f x u x d +=. ① 证明 如果()x f ，()x g 有一个为零，譬如说，()0=x g ，那么()x f 就是一个最大公因式，且
()()011?+?=x f x f .
下面来看一般的情形.无妨设()0≠x g .按带余除法,用()x g 除()x f ,得到商()x q 1,余式()x r 1;如果()01≠x r ,就再用()x r 1除()x g ,得到商()x q 2,余式()x r 2;又如果()02≠x r ,就用()x r 2除()x r 1,得出商()x q 3,余式()x r 3;如此辗转相除下去,显然,所得余式的次数不断降低,即
()()()()()()Λ>?>?>?x r x r x g 21
因此在一有限次之后，必然有余式为零，于是我们有一串等式；
()()()()x r x g x q x f 11+=， ()()()()x r x r x q x g 212+=，
…………
()()()()x r x r x q x r i i i i +=--12,
…………
()()()()x r x r x q x r s s s s 1213----+=, ()()()()x r x r x q x r s s s s +=--12, ()()()011+=+-x r x q x r s s s .
()x r s 与0的最大公因式是()x r s .根据前面的说明，()x r s 也就是()x r s 与()x r s 1-的一个
最大公因式；同样的理由，逐步推上去，()x r s 就是()x f 与()x g 的一个最大公因式.
由上面的倒数第二个等式，我们有
()()()().12x r x q x r x r s s s s ---=
再由倒数第三式，()()()(),2131x r x q x r x r s s s s -----=代入上式可消去(),1x r s -得到
()()()()()()().1321x r x q x r x q x q x r s s s s s s ----+=
然后根据同样的方法用它上面的等式逐个消去，再并项就得到这就是定理的①式. 证毕 由最大公因式的定义不难看出，如果()()x d x d 21,是()x f 与()x g 的两个最大公因式，那么一定有()()x d x d 21|与()()x d x d 12|，也就是()()x cd x d 21=，0≠c .这就是说，两个多项式的最大公因式在可以相差一个非零的常数倍的意义下是唯一确定的.我们知道，两个
不全为零的多项式的最大公因式总是一个非零多项式.
由定理1的证明过程我们找到一种求多项式的最大公因式的方法—辗转相除法. 3.2 辗转相除法
例3.2.1 求()x f 与()x g 的最大公因式：
()().1,14323234--+=---+=x x x x g x x x x x f
解 用辗转相除法，得
故
()()()1,+=x x g x f
为了运算的简化，我们可以在辗转相除的开始或过程中用一个非零常数去乘被除式
或者除式，而对计算结果无影响.此外，在辗转相除的过程，若遇到两个多项式的次数相同时，可以任取一个作除式，另一个做被除式.并且为了减小多项式的系数，也可以将被除式减去除式的若干倍再做辗转相除，不改变))(),(((x g x f 的结果.
例3.2.2 设!
!21)(2n x x x x f n
++++=Λ,)!1(!21)(12-++++=-n x x x x g n Λ 求)(),(x g x f 的最大公因式)(x d .
解：!
)()(n x x g x f n
=-Θ是)(x d 的倍式
而!
n x n 的因式只有两种可能：或是常数c ，或是)1(n m x m ≤≤.
但是
x 不整除)(x f ，也不整除)(x g
∴,)(c x d =即)(x f 与)(x g 互素
辗转相除法具有可操作性，较因式分解法适用范围更广，有具体的格式进行操作. 但当已知的多项式次数较高时或者多项式的个数较多时，辗转相除次数较多显得十分麻烦；在求()()x v x u ,时，辗转相除的过程不能用一个非零的常数去乘除式和被除式，运算困难. 3.3 因式分解法和辗转相除法
在辗转相除法的运算中，)2,1)((s i x r i Λ=都是)(),(x g x f 的最大公因式的倍式.这样，只要发现某一)(x r i 能较快的因式分解，就可用此分解式中不可约因式试除)(),(x g x f 而得到最大公因式 例3.3.1
6789101112131415161739101026552)(x x x x x x x x x x x x x f +-+-++-++-+=
345121011x x x +-+6662+-+x x
421441072)(34571011121415+-+++-++-+=x x x x x x x x x x x g 计算)(),(x g x f 的最大公因式. 解：由辗转相除法得
)2()()1()(112+++-=x x g x x x f
2)(111+=x x r Θ是有理数域上的不可约多项式
)(1x r ∴的因式只可能是211+x 或常数
用211
+x 试除，得211
+x 不整除)(),(x g x f ，所以，)(),(x g x f 的最大公因式是常数，即
)(),(x g x f 互素.
在了解了用上述格式表示辗转相除法的过程后，我们还可以用另一种更简单，直观的方式来表示这种过程．
3.4 矩阵法
1. 求两个多项式的最大公因式[]2
令21,f f 是两个多项式，不妨设21f f ?≤?，用1f 去除2f 有121212r g f f +=，f r ?
1221
10
1r f g f f =???
???-.设???
?
?
?-=10
1121g A 可知1A 是可逆阵，再用12r 去除1f 有2121121r g r f +=，1221r r ?
101
r r g r f =???
???-.设??
??
??-=101
122g A ，则2A 也是可逆阵，依次做下去，由于}{ij r ?在绝对递减，必有某时有()()2210k k k r r r =或
()
01k r .不妨设
1≠=d r k ，
2=k r ，
则
()()02121
d A A A f f s =Λ.()()021d A f f =，其中s A A A A Λ21=是可逆阵.设A
的第一列为21,u u ，则有
d u f u f =+2211. ②
又由于()()121
0-=A d f f ，于是21,f f 均可由d 表示，即d 是21,f f 的公因式.
综合②得d 是21,f f 的最大公因式.
例3.4.1 ,9516242
3
4
1++--=x x x x f .4522
3
2+--=x x x f 求1f 与2f 的最大公因式)(x d
解 ,12f f ?
93622
21+--+=x x x f f ，
即 ()(
)
.9361201
2221
f x x x f
f +--=?
?
?
?
??
-再作除法
()
),1(313193622+-+??
?
??+-+--=x x x x f
即 ()
(
)
.193610313119
36222
+-+--=???
????
?-+--x x x x f x x 再作除法，
()(),09619362+++-=+--x x x x
即 (
)
().1019601
19362+-=??
????--+-+--x x x x x
则
()1+-=x x d
2. 求3个多项式的最大公因式
321,,f f f 是3个多项式，{}3211,,m in f f f f ???=?，用1f 去除32,f f ，有131313121212,r g f f r g f f +=+=,
即 ()(),10
0101
1312
11312321
r r f g g f f f =????
?
?????--????
?
?????--=10
010
1
13121g g A .不妨设{}1312
1
12m in r r f r ???=?，再用12r 去除1f 和13r ，有 232312132121121,r g r r r g r f +=+=，
即
()()????
?
?????--==????
?
?????--10
10
01
,10
10
01
2321
22312
21
2321
1312
1
g g A r r r g g r r f .
继续作下去，由于{}
ij r ?绝对递减，必有某时321,,k k k r r r 中有一个不为零，其余全为零,不妨设0,0321==≠=k k k r r d r ，则有
()()0021321
d A A A f f f s =Λ，记
()均可逆S S A A A A A A A ,,,2121ΛΛ=，则有()()00321
d A f f f =.设A 的第一列为,,,321u u u 则d u f u f u f =++332211.又()()132
1
00-=A d
f f f Θ，即3
21,,f f f 均可由d 表示，即d 是321,,f f f 的公因式.故d 是最大公因式.
例3.4.2 .12,452,951624232322341+-=+--=++--=x x f x x x f x x x x f
求321,,f f f 的最大公因式.
解 3f ?最小，用3f 去除21,f f ，有
()
()()(),132,171786432231+-++=+-+-+=x x f f x x x f f 即
()()()
1,1
171713
28
6401000132
32
1
+-?+-+-=????
?
??
???
--+--x f x x x x x f f f 最小，再作除法，()()()().011,017117173++-+-=++-=+-x x f x x 即
()()().
01
10
11170
01
1
17
173+-=????
?
?????+---+-+-x x f x x
1+-=x d 是最大公因式..
3. 求n 个多项式的最大公因式
n f f f Λ,,21是n 个多项式，{},,,m in 211n f f f f ???=?Λ用1f 去除,,2n f f Λ有
,,,,111131313121212n n n r g f f r g f f r g f f +=+=+=Λ
即
()().10
00101112
11122
1
n n n r r f g g f f f Λ
Λ
ΛΛΛΛΛΛΛ
=??
???
???????--
设??
???
?????
??--=10
010
1
112
1
Λ
ΛΛΛΛΛΛn g g A （必是可逆阵） 不妨设()n r r f r 113112,,,m in ???=?Λ，再用12r 去除n r r f 1131,,Λ有
??????
?+=+=+=,2212123
2312132121121n
n n r g r r r g r r r g r f ΛΛΛ 即
()().10
1001212
21221
112
1
n n n r r r g g
r r f Λ
Λ
ΛΛΛΛΛΛΛ
=??
???
???????--
设??
???
?
?
??
???--=100
1001
221
2Λ
ΛΛΛΛΛΛn g g A （必是可逆阵）.继续下去，由于{}ij r ?绝对递减，必有某时()in i r r ,,1Λ中只有一个不为零其余全为零.不妨设01≠=d r i ，则
()()00121Λ
ΛΛd A A f f f S n =.设s A A A A Λ21=是可逆阵，
()()0021
Λ
Λ
d
A f f f n =，设A 的第一列为n u u u ,,,21Λ，有
d u f u f u f n n =+++Λ2211，且()(),0012
1
-=A d
f f f n Λ
Λ
Θ∴,1f ,2f
n f ,Λ均可由d 表示，即d 是,1f ,2f n f ,Λ的公因式.故d 是最大公因式.
矩阵法在辗转相除法的基础上，结合多项式最大公因式的定义与矩阵的运算性质，
不紧可以求两个多项式的最大公因式还可以求得多个多项式的最大公因式并同时求得()x d 关于()()n i x f i ,,2,1Λ=的线性组合. 虽采用的是矩阵形式，但仍需要两两多项式作除法，随着多项式的个数增加计算量大大增加，计算过程比较复杂. 3.5 矩阵的初等行（列）变换法
定理2 设()()()()n n x f x f x f A ?=121,,,Λ是][x P 上的非零阵，
()()()()x f x f x f x d n ,,,)(21Λ=，n I 是n 阶单位矩阵，()()n x d B ?=10,,0,Λ，则矩阵
???
? ??n I A 经过一系列初等列变换可化为()???
? ??x R B ，而()x R 的第一列元素就是()()n i x u i ,,2,1Λ=，使得
()()()()()()()x d x u x f x u x f x u x f n n =+++Λ2211
成立.
例3.5.1 对于整系数多项式 ()()().
632;
2;
25323432
3
22x x x x x f x x x x f x x x f +++=+-+=-+=
求它们的最大公因式()x d
解 令 ????
??
?
?
?=100010001
321f f f C 对其进行如下的的列初等变换： ??
?
??
??
?
?=10
0010001321f f f C ()??→???
????
?
?
?---+????→?+-+--1
31221
321210
0121000
1
232x x x f f x
()????→???????
?
??----++-+----++?????→????????
?
?---+-+++++-+-231,1322211,112222311361212211
22210
1121120012322x x x x x x x x x x x x x x x x f x x [],
13231625236121200232133625216211
22100223,122?????
?
?
??-+-+-----++---+?→???????? ??-+-+---+----+-+x x x x x x x x x x x x x x x x x x x x 其中，()????
??????-+-+-----++---=132316252361212
2
2x x x x x x x x x x R
故 (),2+=x x d
注：进行初等变换的目的是要把C 的第一行变成()()00Λ
x d 形式，在作初等列
变换过程中，系数保持是整数，在这个原则下可以随意地作初等列变换，得到的()x d 是唯一的.但由于作法不同，得到的()x R 的第一列元素()()n i x u i ,,2,1Λ=可能不同，故线性表示不唯一，但都能使
()()()()()()()x d x u x f x u x f x u x f =++332211
成立.
矩阵的初等变换法通过直接构造矩阵，利用多项式矩阵的初等变换一举求得最大公因式()x d 及其线性表达式，具有较广的使用范围且运算过程较灵活，避免了多项式之间繁琐的除法运算. 但由于构造的是多项式矩阵，故在运算过程中仍是多项式的运算，有一定的难度.
3.６ 矩阵的斜消变换
基于矩阵的初等行，列变换法，我们思考是否存在一种运算过程来避免多项式之间繁琐的除法运算．
定义３ 设),,2,1(,)(1,121m i a x a x a x a x f in n i n i n i i ΛΛ=++++=--为m 个多项式（至少有一个多项式不为零），)(ij a A =为n m ?阶矩阵，A 为与多项式)(x f i ，（m i ,,2,1Λ=）相对应的矩阵.
若A 的第i 行从左向右第一个不为零的元素为,1,+s i a ,第j 行的第一列元素1j a 不为零
)(j i ≠,则称将第i 行的n-s 个元素：in s i s i a a a ,,,2,1,Λ++乘以c 斜加到第j 行元素：s n j j j a a a -,21,,,Λ上的变换为第i 行到第j 行的左斜消变换记为)(C L S ji ；
若A 的第i 行从右向左第一个不为零的元素为is a ，n s ≤≤1,第j 行的第n 列元素
)(j i a jn ≠不为零，则称将第i 行的s 个元素：is i i a a a ,,,21Λ乘以c 斜加到第j 行元素：
jn s n j a a ,,1,Λ+-上的变换为第i 行到第j 行的右斜消变换，记为)(C R s n ji -
此外，对A 施行矩阵的第一，第二种初等行变换以及左斜消变换和右斜消变换不改变与其对应的这些多项式的最大公因式，并且总可以将矩阵A 化简成如下形式的矩阵：
C=????
??
? ?
?-00
00001
12Λ
ΛΛΛΛΛΛi b b 此时
.122121))(),(),((---++=i i i m b x b x x f x f x f ΛΛ
例3.6.1 用矩阵的斜消变换求
2424)(234-++-=x x x x x f 64)(23++-=x x x x g 22)(23+--=x x x x h
求))(),(),((x h x g x f
解 A=????? ??-----212106141
034241????→?--)1(),1(023112L L ???
?
? ??------21210422003210
?????? ??-----212121
103210??→?)
1(132L ????? ??----211021103210??????
??----211211321????→?-)
1(),1(0320
12L L ????
?
??---000211110??
→?-)
1(121L ????? ??--000220110?????
? ??--0022
11??→?)
2(021L ????? ??--000011→???
?
?
??000011
所以，1))(),(),((+=x x h x g x f
我们约定，用左斜消变换化简矩阵时，若所得矩阵的前若干列元素全为零时，要及时消去这些列再做变换；用右斜消变换化简矩阵时，若所得矩阵的后若干列元素全为零时，要及时消去这些列再做变换.这样可以达到简化矩阵的目的.
在用斜消变换化简矩阵时，我们会发现，求某些多项式的最大公因式时，需要选择其适用的是左斜消变换还是右斜消变换.并且左右斜消变换是不能同时使用的，这就给我们解决某些问题时带来了局限性. 3.７ 数值矩阵法
若用矩阵A =???
? ??--01
1011b b b b
a a a a n n
n n
ΛΛ表示多项式：01
1)(a x a x a x f n n n n +++=--Λ 011)(b x b x b x g n n n n +++=--Λ的待求最大公因式.则对A 施行初等行变换，不改变两个多
项式的最大公因式.
当00≠a 时，???? ??--01
1011b b b b
a a a a n n
n n
ΛΛ????
?
?
?-=01
10110b b b a a a a n n n
ΛΛ
，即它们表示的两个多项式的待求最大公因式相同.
利用以上结论，就可以利用矩阵的初等行变换求出一元多项式组的最大公因式，其一般步骤为：
㈠ 将系数矩阵A 利用初等行变换化为阶梯矩阵B .
㈡ 考察矩阵B ，若出现元素都是0的行，则去掉该行；若某行变为
()()000
≠k k Λ
时，多项式的最大公因式为1，计算终止；若出现每一行的列数最大
的非零元素不在同一列时，则施行右对齐；若每一行的列数最大的非零元素在同一列时，则施行左对齐；将B 变成非阶梯矩阵，然后，以非零元素最少的行将其再化成阶梯矩阵.
㈢ 反复循环上述步骤，直到A 变为()11+?n 型矩阵，则对应的多项式即是③的最大公因式.
例3.7.1 设))(),((,22)(,623)(2
3
2
3
x g x f x x x x g x x x x f --+=+--==？ 解：对矩阵A=?
??
?
??----22116231施行初等行变换及替换： ?
??
?
??--→???? ??--→???
?
??---→???? ??---→20102010201002012010623180406231A
???
? ??-→00002010 故，=))(),((x g x f 2)0,2(2
2
-=-x x 例
3.7.2
3
424)(234-++-=x x x x x f
64)(23++-=x x x x g
22)(23+--=x x x x h 求))(),(),((x h x g x f
解 A=?????
??-----21
2
106141034241
?????
?
?-----→4220061410
34241
????? ?
?-----?00
4
2
206141
34241
????
?
?
?-----→34
2
4
106141
00211
→
????
?
?
?-----32
1
00633000211
?????
?
?
?-----32
1
063300
21100
→??
??
?
?
?----00
01100021100
?????
?
?
?----00
001100
21100→????
?
?
?----00
001
10022000 ?????
? ?
?----00
011000
22000→
????
? ?
?00
000000`11000
所以，1))(),(),((+=x x h x g x f
数值矩阵法根据多项式与其系数间的一一对应关系，构造多项式组的系数矩阵A ，再
由多项式最大公因式的性质导出一种单纯运用数字矩阵（系数矩阵A）的初等变换求得最
大公因式的方法，直观明了，简单易行. 但它不能像矩阵法和矩阵的初等行（列）变换法可以求得最大公因式的同时求得最大公因式的线性表达式.
因此，我们可以依照以上的对比结果根据多项式的表达式特征、多项式的个数以及是否需要得到最大公因式的线性表达等情况的不同,灵活选择不同的方法来求最大公因式.
参考文献
[1] 北京大学数学系编.高等代数（第三版）.北京：高等教育出版社.
[2] 蔡若松. 求几个多项式的最大公因式. 锦州师范学院学报（自然科学版）, 1998.3.
[3] 陈辉，陈凌云. 多项式最大公因式的一种求法. 杭州师范学院学报, 2000.06.
[4] 刘国琪. 多项式的最大公因式的一种新求法. 河北电力职工大学，工科数学,
1997.04.
[5] T.W.Hungerford. 冯克勤译. 代数学[M]. 长沙:湖南教育出版社, 1984.
[6] 李正彪, 李祥. 求多项式最大公因式的一种新方法. 曲靖师范学院学报, 2004.11.
[7] Nathan Jacobson..Basic Algebral[M].San.Francisco:W.H.Freeman and company,
1980.
]8[王向东，周士藩.高等代数常用方法北京：科学出版社。1989.19
]9[北京大学数学系几何与代数教研室.高等代数[M].北京：高等教育出版社，2003:13-15
[10]郁金祥.基于矩阵斜消变换的最大公因式求解[J].数学的实践与认识，2005（11）
[11]高吉全.斜消变换与结式计算的简化[J].数学通报，1933（11）
[12] 任勤最大公因式的求法焦作工学院学报，第18卷，第2期，1999,3
[13]李伯葓最大公因式的求法探讨南京师大学报（自然科学报）第1期,1984
[14]骆公志一元多项式的最大公因式的几种求法连云港师范高等专科学校第3期，
2006.9
[15]张庆，王朝霞求两个多项式的最大公因式的新方法唐山师范学院学报第29卷，第
2期,2007,3
[16]苏正君对《两多项式最大公因式简易求法》一文的看法洛阳教育学院第12 卷。第2
期，1997.4
1.1设计内容及要求 1)设计内容 （1）使用顺序存储结构实现多项式加、减、乘运算。 例如： 10321058)(2456+-+-+=x x x x x x f ,x x x x x x g +--+=23451020107)( 求和结果：102220128)()(2356++-+=+x x x x x g x f （2）使用链式存储结构实现多项式加、减、乘运算， 10305100)(1050100+-+=x x x x f ，x x x x x x g 320405150)(10205090+++-= 求和结果：1031040150100)()(102090100++-++=+x x x x x x g x f 2）设计要求 （1）用C 语言编程实现上述实验内容中的结构定义和算法。 （2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。 （3）用switch 语句设计如下选择式菜单。 ***************数据结构综合性实验**************** *******一、多项式的加法、减法、乘法运算********** ******* 1.多项式创建 ********** ******* 2.多项式相加 ********** ******* 3.多项式相减 ********** ******* 4.多项式相乘 ********** ******* 5.清空多项式 ********** ******* 0.退出系统 ********** ******* 请选择（0—5） ********** ************************************************* *请选择（0-5）: 1.2数据结构设计 根据下面给出的存储结构定义： #define MAXSIZE 20 //定义线性表最大容量
中国计量学院实验报告 实验课程：算法与数据结构实验名称：一元二项式班级：学号： 姓名：实验日期： 2013-5-7 一．实验题目： ①创建2个一元多项式 ②实现2个多项式相加 ③实现2个多项式相减 ④实现2个多项式相乘 ⑤实现2个多项式相除 ⑥销毁一元多项式 实验成绩：指导教师：
二．算法说明 ①存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储 空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 ②加法算法
三．测试结果 四．分析与探讨 实验数据正确，部分代码过于赘余，可以精简。 五．附录：源代码#include<> #include<> #include<> typedef struct Polynomial { float coef; int expn; struct Polynomial *next; }*Polyn,Polynomial; 出多项式a和b\n\t2.多项式相加a+b\n\t3.多项式相减a-b\n"); printf("\t4.多项式相除a*b\n\t5.多项式相除a/b\n\t6.销毁多项式\n"); printf("\t7.退出
\n*********************************** ***********\n"); printf("执行:"); scanf("%d",&flag); switch(flag) { case(1): printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb);break; case(2): pc=AddPolyn(pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc);break; case(3): pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd);break; case(4): pf=MultiplyPolyn(pa,pb); printf("多项式a*b：");PrintPolyn(pf); DestroyPolyn(pf);break; case(5): DevicePolyn(pa,pb); break; case(6): DestroyPolyn(pa); DestroyPolyn(pb); printf("成功销毁2个一元二项式\n"); printf("\n接下来要执行的操作:\n1 重新创建2个一元二项式 \n2 退出程序\n"); printf("执行:"); scanf("%d",&i); if(i==1) { // Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);// 建立多项式a printf("请输入b的项
将一元多项式存储为链式结构的线性表，表中数据元素存储有两个数据项（系数项和指数项）。其中，线性表按照指数升序存储。分别用Pa和Pb表示两个一元多项式。Pa=Pa+Pb，“和多项式”链表中的结点无需另生成，而应该是从两个多项式的链表中摘取。其运算规则如下：假设指针qa和qb分别指向A，两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：1指针qa所指结点的指数值小于指针qb所指结点的指数值，则应摘取qa所指的结点插入到“和多项式”链表中去；2指针qa所指结点的指数值大于指针qb所指结点的指数值，则应摘取qb所指的结点插入到“和多项式”链表中去；3指针qa所指结点的指数值等于指针qb所指结点的指数值，则应将两个结点的系数项相加，若和数不等于零，则修改qa所指结点的系数值，同时释放qb所指的结点，反之，从多项式A的链表中删除相应的结点，并且释放qa,qb所指结点。具体代码如下： typedef struct { float coef; int expn; }term,ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; typedef LinkList polynomial; Status InitList(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); if(!L) return ERROR; L->data.coef=0.0; L->data.expn=-1; L->next=NULL; return OK; } LinkList Get head(LinkList L){ return L; } void SetCurElem(LNode* &NodeAdd,ElemType e){
多项式最大公因式的求法 定理1 设)(x)(n ,f (x),(x),f f n 221≥ 是P[x]中n 个多项式.P[x]中多项式d(x)称为 )(x)(n ,f (x),(x),f f n 221≥ 的最大公因式，如果它满足下面的两个条件： (1)d(x)是(x),f (x),(x),f f n 21的公因式. (2)(x),f (x),(x),f f n 21的公因式全是d(x)的因式. 定理2 设)(),(),(x h x g x f 是][x P 中的多项式，P[x]中多项式d(x)是)(),(),(x h x g x f 的最大公因式，c 是任意的非零常数，则有))(),()()(())(),(()(x g x g x h x cf x g x f x d -==. 证明：当)(x f 、)(x g 有一个为零，例如0)(=x g ，那么结论显然成立. 当0)(≠x g 时，则有)()(x f x d ，)()(x g x d . 从而)()()()(x g x h x cf x d -，即)(x d 是)()()(x g x h x cf -与)(x g 的一个公因式，令 )()()()(x g x h x cf x c -，)()(x g x c .根据整除的性质，我们有)()(x f x c ，所以)()(x d x c . 所以))(),()()(())(),(()(x g x g x h x cf x g x f x d -== 方法1：用辗转相除法求最大公因式 引理 如果 )3(121≥n (x),f (x),(x),f f n- 的最大公因式存在，那么 ) 2(21≥n (x),f (x),(x),f f n 的 最 大 公 因 式 也 存 在 ， 且 (x)) (x)),f ,f (x),(x),f ((f (x))(x),f ,f (x),(x),f (f n n-n n-121121 =. (1) 证明：由题意，假设(x),f (x),(x),f f n-121 的最大公因式为)(1x d ，那么(x)d 1与(x)f n 的最大公因式)(x d 也是存在的. (2) 又由(1)、(2)式，可知n)i (x), (d(x)|f i ≤≤1. 假设c(x)是)(x)(n ,f (x),(x),f f n 221≥ 的一个公因式，由(1)式可得(x)c(x)|d 1.这样c(x)就是(x)d 1与(x)f n 的一个公因式，再由(2)式可得c(x)|d(x). 所以(x)) (x),f ,f (x),(x),f (f d(x)n n-121 =. 定理3 设)2)((,),(),(21≥n x f x f x f n 是][x P 中的n 个多项式，则在P[x]中存在一个最大公因式d(x)，且d(x)可以表示成(x),f (x),(x),f f n 21的一个组合，即有p[x]中多项式 (x),u (x),(x),u u n 21使(x)(x)f u (x)(x)f u (x)(x)f u d(x)n n +++= 2211. 由定理3对一般情况， 设1 1110110(),()n n n n n n n n f x a x a x a x a g x b x b x b x b ----=++ ++=++ ++，不妨设m n ≥
数据结构中实现一元多项式简单计算： 设计一个一元多项式简单的计算器。 基本要求： 一元多项式简单计算器的基本功能为： （1）输入并建立多项式； （2）输出多项式； （3）两个多项式相加，建立并输出和多项式； （4）两个多项式相减，建立并输出差多项式； #include 课程设计成果 学院: 计算机工程学院班级: 13计科一班 学生姓名: 学号: 设计地点（单位）： 设计题目：一元多项式的计算 完成日期：年月日 成绩(五级记分制): _________________ 教师签名:_________________________ 目录 1 需求分析 ......................................................................... 错误!未定义书签。 2 概要设计 ......................................................................... 错误!未定义书签。 2.1一元多项式的建立 ............................................................... 错误!未定义书签。 2.2显示一元多项式 ................................................................... 错误!未定义书签。 2.3一元多项式减法运算 ........................................................... 错误!未定义书签。 2.4一元多项式加法运算 ........................................................... 错误!未定义书签。 2.5 设计优缺点.......................................................................... 错误!未定义书签。3详细设计 .......................................................................... 错误!未定义书签。 3.1一元多项式的输入输出流程图........................................... 错误!未定义书签。 3.2一元多项式的加法流程图................................................... 错误!未定义书签。 3.3一元多项式的减法流程图.................................................. 错误!未定义书签。 3.4用户操作函数....................................................................... 错误!未定义书签。4编码 .................................................................................. 错误!未定义书签。5调试分析 .......................................................................... 错误!未定义书签。4测试结果及运行效果...................................................... 错误!未定义书签。5系统开发所用到的技术.................................................. 错误!未定义书签。参考文献 ............................................................................. 错误!未定义书签。附录全部代码................................................................... 错误!未定义书签。 一元多项式的计算—加，减 摘要(题目)一元多项式计算 任务：能够按照指数降序排列建立并输出多项式； 能够完成两个多项式的相加、相减，并将结果输入； 目录 1.引言 2.需求分析 3.概要设计 4.详细设计 5.测试结果 6.调试分析 7.设计体会 8.结束语 一:引言: 通过C语言使用链式存储结构实现一元多项式加法、减法和乘法的运算。按指数 降序排列。 二：需求分析 建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果 三：概要设计 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。 1．单连表的抽象数据类型定义： ADT List{ 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R1={ 项目一一元多项式的计算问题 1.1设计题目与要求 1.1.1设计题目 1）一元多项式计算 任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入； 基本要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；本程序关键点是如何将输入的两个多项式相加、相减操作。 ①如何将输入的一元多项式按指数的降序排列 ②如何确定要输入的多项式的项数； ③如何将输入的两个一元多项式显示出来。 ④如何将输入的两个一元多项式进行相加操作。 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。 1.1.2、任务定义 此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。 a：输入多项式的项数并建立多项式； b：输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c：多项式a和b相加，建立多项式a+b； d：多项式a和b相减，建立多项式a-b。 e：多项式的输出。 1.2 数据结构的选择和概要设计： 1.2.1数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；例如，图1中的两个线性链表分别表示一元多项式 和一元多项式。从图中可见，每个结点表示多项式中的一项。 图1 多项式表的单链存储结构 B：本设计使用了以下数据结构： typedef struct node{ int xs; /*系数*/ int zs; /*指数*/ struct node * next; /*next指针*/ }Dnode,* Dnodelist; C：设计本程序需用到八个模块，用到以下八个子函数如下： 1.Dnodelist Creat_node(void) /*链表初始化*/ 2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/ 3.Dnodelist Creat_Dmeth(int length) /*创建多项式*/ 4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/ 5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/ 6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/ 7void Show(Dnodelist D) /*显示（输出）函数*/ 8void main()主程序模块调用链一元多项式的各种基本操作模块。 1.2.2 多项式的输入 先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； 1.2.3 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下： 假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况： ①指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去； ②指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去； ③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。 #include C语言一元多项式计算集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN# #include <> #include <> #include <> #define LEN sizeof(node) //结点构造 typedef struct polynode { int coef; //系数 int exp; //指数 struct polynode *next; }node; node * create(void) { node *h,*r,*s; int c,e; h=(node *)malloc(LEN); r=h; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); while(c!=0) { s=(node *)malloc(LEN); s->coef=c; s->exp=e; r->next=s; r=s; printf("系数："); scanf("%d",&c); printf("指数："); scanf("%d",&e); } r->next=NULL; return(h); } void polyadd(node *polya, node *polyb) { node *p,*q,*pre,*temp; int sum; p=polya->next; q=polyb->next; pre=polya; while(p!=NULL&&q!=NULL) { if(p->exp>q->exp) { pre->next=p; pre=pre->next; p=p->next; } else if(p->exp==q->exp) { sum=p->coef+q->coef; if(sum!=0) { p->coef=sum; pre->next=p;pre=pre->next;p=p->next; temp=q;q=q->next;free(temp); } else { temp=p->next;free(p);p=temp; temp=q->next;free(q);q=temp; } } else { pre->next=q; pre=pre->next; q=q->next; } } if(p!=NULL) pre->next=p; else pre->next=q; } void print(node * p) { 数据结构课程设计报告 课题: 一元多项式 姓名： XX 学号： 201417030218 专业班级： XXXX 指导教师： XXXX 设计时间： 2015年12月30日星期三 目录 一、任务目标 (3) 二、概要设计 (4) 三、详细设计 (6) 四、调试分析 (8) 五、源程序代码 (8) 六、程序运行效果图与说明 (15) 七、本次实验小结 (16) 八、参考文献 (16) 一丶任务目标 分析 (1) a.能够按照指数降序排列建立并输出多项式 b.能够完成两个多项式的相加，相减，并将结果输入 要求：程序所能达到的功能： a.实现一元多项式的输入； b.实现一元多项式的输出； c.计算两个一元多项式的和并输出结果； d.计算两个一元多项式的差并输出结果； 除任务要求外新增乘法： 计算两个一元多项式的乘积并输出结果 （2）输入的形式和输入值的范围： 输入要求：分行输入，每行输入一项，先输入多项式的指数，再输入多项式的系数，以0 0为结束标志，结束一个多项式的输入。 输入形式： 2 3 -1 2 3 0 1 2 0 0 输入值的范围：系数为int型，指数为float型 （3）输出的形式： 第一行输出多项式1； 第二行输出多项式2； 第三行输出多项式1与多项式2相加的结果多项式； 第四行输出多项式1与多项式2相减的结果多项式； 第五行输出多项式1与多项式2相乘的结果多项式 二、概要设计 程序实现 a. 功能：将要进行运算的二项式输入输出； b. 数据流入：要输入的二项式的系数与指数； c. 数据流出：合并同类项后的二项式； d. 程序流程图：二项式输入流程图； e. 测试要点：输入的二项式是否正确，若输入错误则重新输入。 长沙学院课程设计说明书 题目一元多项式计算问题系(部) 计算机系 专业(班级) 10级软件D班 姓名向栋良 学号2010022D08 指导教师邓旭东 起止日期2011.9.4-2011.9.8 课程设计任务书 课程名称：数据结构与算法 设计题目：一元多项式计算问题 已知技术参数和设计要求： 问题描述： 设计一个稀疏多项式简单计算器 基本要求： (1)输入并分别建立多项式A和B (2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列 (3)完成两个多项式的相加、相减，并将结果输出； 测试数据： (1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7 (3) A+B A=x3+x1B=-x3-x1 (4) A+B A=0 B=x7+x5+x3+x1 (5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x 选作内容： （1）.多项式在x=1时的运算结果 （2）求多项式A和B的乘积 设计工作量： 40课时 日期节次地点设计方式9月4日（周日）1-4 科1408 讲授内容 9月4日（周日）5-8 科1608 答疑 9月5日（周一）1-4科1408上机调试 9月5日（周一）5-8 科1608 答疑 9月6日（周二）1-4科1408上机调试 9月6日（周二）5-8 科1608 答疑 9月7日（周三）1-4科1408上机调试 9月7日（周三）5-8 科1608 答疑 9月8日（周四）1-4科1608答疑 9月8日（周四）5-8 科1408 答辩 多项式的最大公因式 问题： （一）. 多项式的最大公因式的定义是什么？ 设f(x)与g(x)是P[x]中两个多项式，P[x]中多项式d(x)称为f(x)与g(x)的最大公因式，如果满足下面两个条件： (1).d(x)是f(x)与g(x)的公因式； (2).f(x)，g(x)的公因式全是d(x)的因式。 我们约定用( f(x)，g(x))表示首项系数为1的那个最大公因式。 定理1：对于P[x]中任意两个多项式f(x)，g(x)，在P[x]中存在一个最大公因式d(x)，且d(x)可以表示成f(x)，g(x)的一个组合，即有P[x]中多项式u(x)，v(x)使 d(x)=u(x)f(x)+v(x)g(x) 引理：设f(x),g(x),q(x),h(x)∈F(x),g(x)≠0，且 f(x)=g(x)q(x)+h(x) 则f(x)与g(x)与q(x)与h(x)有相同的公因式，因而有相同的最大公因式，且 ( f(x)，g(x))=( g(x)，h(x)) 定理2：F(x)的任意两个多项式f(x)与g(x)一定存在最大公因式。 （二）.用来求最大公因式的方法 (1).辗转相除法: 如果f(x),g(x)∈P[x],g(x)≠0，且q q(q),q q(q)∈P[x],使 f(x)=q1(q)g(x)+q1(q) g(x)=q2(q)q1(q)+q2(q) q1(q)=q3(q)q2(q)+q3(q) ?? q q?2(q)=q q(q)q q?1(q)+q q(q) q q?1(q)=q q+1(q)q q(q)+0 其中?(q q(q))≥0，则q q(q)是f(x)与g(x)的一个最大公因式。 (2).串位加减法 (3).矩阵求法： A=(f(x) g(x) )一系列初等行变换 → ( d(x) ) d(x)=( f(x)，g(x)) 例1.设f(x)=q4+3q3?q2?4x?3 g(x)=3q3+10q2+2x?3 求( f(x)，g(x)) 解：法1辗转相除法。 一元多项式计算器 目录 摘要 (1) 1绪论 (1) 2系统分析 (1) 2.1功能需求 (1) 2.2数据需求 (1) 2.3性能需求 (1) 3总体设计 (2) 3.1系统设计方案 (2) 3.2功能模块设计 (2) 4详细设计 (3) 4.1建立多项式 (4) 4.2多项式相加 (4) 4.3多项式相减 (5) 4.4多项式相乘 (5) 4.5计算器主函数 (6) 5调试与测试 (7) 5.1调试 (7) 5.2测试 (8) 6结论 (9) 结束语 (9) 参考文献 (9) 附录1－用户手册 (10) 附录2－源程序 (12) 摘要 随着生活水平的提高，现代科技也日益发达。日常生活中多位计算再所难免，因此设计一个简单计算器可解决许多不必要的麻烦。 开发这样一个程序主要运用了C的结点，链表等方面知识。系统主要实现了多项式的建立，多项式的输入输出，以及多项式加减乘等运算。 报告主要从计算器的程序段，对输入输出数据的要求，计算器的性能，以及总体的设计来介绍此计算器程序的实现过程。 关键词：多项式；链表；结点 1绪论 随着日益发达的科技，计算器已应用于各行各业。设计一个计算器需要运用C中多方面知识，更是以多项式的建立，输入输出，以及结点，链表为主。（扩充） 任务书。。。。。 2系统分析 2.1 功能需求 多项式的建立多项式输入输出多项式加减乘等运算 2.2数据需求 在输入过程中，首先要确定输入的数据，数据不能是字母，只能是数字。不能连续输入数据，必须按要求配以空格输入要计算的数据。 (1) 链节节点数字 (2) 数字 2.3 性能需求 系统必须安全可靠，不会出现无故死机状态，速度不宜过慢。 数据结构课程设计实验报告 专业班级： 学号： 姓名： 2011年1月1日 题目：一元多项式的运算 1、题目描述 一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。 在数学上，一个一元n次多项式P n(X)可按降序写成： P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0 它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示： P=(P n，P(n-1)，......，P1，P0) 每一项的指数i隐含在其系数P i的序号里。 假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示： Q=(q m,q(m-1)，.....，q1，q0) 不是一般性，假设吗吗m 习 题 一 A 组 1. 判别 {} ,a a b =+∈Q Q 是否为数域 解 是． 2. 设32()1f x x x x =+++，2()32g x x x =++，求()()f x g x +，()()f x g x -，()()f x g x ． 解 32()()243f x g x x x x +=+++， 3()()21f x g x x x -=--， 5432()()46652f x g x x x x x x =+++++． 3．设19932199431995()(54)(421)(8112)f x x x x x x =----+，求()f x 的展开式中各项系数的和． 解 由于()f x 的各项系数的和等于(1)f ，所以 199319941995(1)(54)(421)(8112)1f =----+=-． 4. 求()g x 除以()f x 的商()q x 与余式()r x ． (1) 322()31, ()321f x x x x g x x x =---=-+； (2) 42()25,()2f x x x g x x x =-+=-+． 解 (1) 用多项式除法得到 2323222732131 3923374133 7147399 26299x x x x x x x x x x x x x x -+----- +----+--- 所以，17262(),()3999 q x x r x x =-=--． (2) 用多项式除法得到 242432 3232222251 2225 245 2 57 x x x x x x x x x x x x x x x x x x x x -+-++--+--+-+--+-+--+ 所以，2()1,()57q x x x r x x =+-=-+． 5．设,a b 是两个不相等的常数，证明多项式()f x 除以()()x a x b --所得余式为 ()()()() f a f b af b bf a x a b a b --+--． 证明 依题意可设()()()()f x x a x b q x cx d =--++，则 (), ().f a ca d f b cb d =+??=+? 解得 ()()()()(), ()()).c f a f b a b d af b bf a a b =--???=--?? 故所得余式为 ()()()() f a f b af b bf a x a b a b --+--． 6. 问,,m p q 适合什么条件时，()f x 能被()g x 整除 (1) 3()f x x px q =++，2()1g x x mx =+-； (2) 42()f x x px q =++，2()1g x x mx =++． 解 (1) 由整除的定义知，要求余式()0r x =．所以先做多项式除法， 233222221(1)(1)() x mx x px q x m x mx x mx p x q mx m x m p m x q m +-++-+--+++--++++- 要求2()(1)()0r x p m x q m =+++-=， 所以2(1)0,0p m q m ++=-=．即21, p m q m =--=时， 可以整除． (2) 方法同上．先做多项式除法，所得余式为 一元多项式计算(数据结构课程设计) 一、系统设计 1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a 和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。 (1)一元多项式加法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P 的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。 (2)一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。 2、概要设计 (1)主函数流程图： （注：a代表第一个一元二次方程，b代表第二个一元二次方程） 计算机学院 工程实践 一元多项式的计算总报告 小组序号： 编撰人： 年级班级： 指导教师： 提交日期： 1. 项目组成员分工 表 1 项目组成员分工 2. 程序功能 (程序实现的功能，功能结构图) 实现功能：一元多项式的加、减、乘运算 功能结构图： 乘 减加创建多项式 开始 保存 结束 3. 程序设计简介 (包括：类及其属性和方法、类之间关系、关键代码等的说明) 1. class Node { public: Node(); Node(float c, int e, Node* next); ~Node(){}; float coef; //系数 int exp; //指数 Node* Next; //指向下一项的指针 friend class Polynominal; }; 节点类，储存一元多项式每一项的信息。该内含有两个构造函数，一个析构函数及存储系数、指数和Next指针等成员变量。与Polynominal是友元关系，允许Polynominal的访问。 具体成员函数如下： 1) Node::Node(){} 默认构造函数。 2) Node::Node(float c, int e, Node* next){ coef = c; exp = e; Next = next; } 重载的自定义构造函数，用于给成员变量coef、exp和Next存入数据，Next指向传参来的next指针指向的地址，用于构造链表。 2. class Polynominal{ public: Polynominal(); Polynominal(Polynominal &a); //拷贝构造函数 void GetMSG(CString TempPloy); //获取由对话框输入的字符串并处理 CString Output_Node(); //输出最后结果 void PolyAdd(Polynominal &a, Polynominal &b); //加法 void PolySubtract(Polynominal &a, Polynominal &b); //减法 void PolyMultiply(Polynominal &a, Polynominal &b); //乘法 void PolySort(); //排序函数，用于乘法之后的按指数排序 void OutFile(); //文本输出函数数据结构一元多项式的计算
一元多项式的计算数据结构课程设计
数据结构 一元多项式的计算
多项式辗转相除法求最大公因式
C语言一元多项式计算
数据结构实验报告-一元多项式
一元多项式计算问题课程设计
多项式的最大公因式
一元多项式计算器
一元多项式的运算
第一章一元多项式习题及解答
一元多项式计算(数据结构课程设计)
一元多项式的计算实验报告
相关主题
文本预览