具体代码:
from operator import itemgetter
class PolyList:
def __init__(self):
self.data = []
def Add(self, e):
self.data.append(e)
def CreateList(self, fname):
# 从fname文件中读取多项式数据并添加到data
fin = open(fname, "r")
n = int(fin.readline().strip())
for i in range(n):
p = fin.readline().strip().split()
self.data.append([float(p[0]), int(p[1])])
fin.close()
def getsize(self):
return len(self.data)
def __getitem__(self, i):
return self.data[i]
def getdata(self):
return self.data
def Sort(self):
self.data = sorted(self.data, key=itemgetter(1), reverse=True)
def PolyAdd(self, B): # 当前多项式和多项式B的相加运算
C = PolyList() # 新建结果多项式顺序表
m = len(self.data) # 多项式A的项数
n = B.getsize() # 多项式B的项数
i, j = 0, 0
while i < m and j < n:
p, q = self.data[i], B[j]
if p[1] > q[1]: # 将较大指数的p项添加到C中
C.Add(p)
i += 1
elif q[1] > p[1]: # 将较大指数的q项添加到C中
C.Add(q)
j += 1
elif q[0] + p[0] == 0:
i += 1
j += 1
elif q[1] == p[1]:
k = p[0] + q[0]
C.Add([k, p[1]])
i += 1
j += 1
else:
while i < m: # 将A余下的项添加到C中
p = self.data[i]
C.Add(p)
i += 1
while j < n: # 将B余下的项添加到C中
q = B[j]
C.Add(q)
j += 1
return C
if __name__ == "__main__":
fout = open("abc.out", "w+")
p = PolyList()
p.CreateList("abc1.in")
print("第1个多项式:", end=" ", file=fout)
print(p.getdata(), file=fout)
p.Sort()
print("排序后结果:", end=" ", file=fout)
print(p.getdata(), file=fout)
q = PolyList()
q.CreateList("abc2.in")
print("第2个多项式:", end=" ", file=fout)
print(q.getdata(), file=fout)
q.Sort()
print("排序后结果:", end=" ", file=fout)
print(q.getdata(), file=fout)
r = p.PolyAdd(q)
print("相加多项式:", end=" ", file=fout)
print(r.getdata(), file=fout)
fout.close()
读取文件abc1.in 和 abc2.in
abc1.in:
4
2 3
3.2 5
-6 1
10 1
abc2.in
6
6 1
1.8 5
-2 3
1 2
-2.5 4
-5 1
最后输出文件abc.out
第1个多项式: [[2.0, 3], [3.2, 5], [-6.0, 1], [10.0, 1]]
排序后结果: [[3.2, 5], [2.0, 3], [-6.0, 1], [10.0, 1]]
第2个多项式: [[6.0, 1], [1.8, 5], [-2.0, 3], [1.0, 2], [-2.5, 4], [-5.0, 1]]
排序后结果: [[1.8, 5], [-2.5, 4], [-2.0, 3], [1.0, 2], [6.0, 1], [-5.0, 1]]
相加多项式: [[5.0, 5], [-2.5, 4], [1.0, 2], [5.0, 1]]
解释:例如abc1.in中的“2 3”就是2X^3 ,前面的“2”是系数,后面的“3”是X的指数
参考的是李春葆教授写的《数据结构教程》,在复现的过程中发现书上的案例代码貌似有误 ,总是得不到案例的结果,程序会进入死循环,最后改动了PolyAdd()函数里有关判断的部分。