<big>编译环境：python v3.5.0, mac osx 10.11.4</big>
多项式加法与乘法运算（队列）
主要思路：
-
对于多项式的加法:相同指数项的系数相加，其他部分进行拷贝,如下图所示：
-
对于多项式的乘法：选定一个多项式，将其中的元素逐个与另一多项式相乘，形成新的多项式。最后再对这些多项式进行相加。（polynomial.py）
# -- coding: utf-8 --
class polyNode():
def init(self, coef, expon, next=None): # 构建链表单元结构
self.coef = coef
self.expon = expon
self.next = next
# ---------------队列定义--------------------------------
class queueChain:
def init(self, front=None, rear=None):
self.front = front # fron指向表头的指针
self.rear = rear # rear指向表尾的指针
def inQue(queue, newNote): # 入队操作
if queue.front is None: # 链表为空,将front 赋值给表头
queue.front = queue.rear = newNote
else:
queue.rear.next = newNote
queue.rear = newNote
def outQue(queue): # 出队操作
if queue.front is None: # 如果front指向为空,则链表为空
print('it is an empty queue!')
else:
p = queue.front
if queue.front == queue.rear: # 如果前后指针指向一个元素,则全部重置为None
queue.front = queue.rear = None
else:
queue.front = p.next
return p
# -------------------------加法定义-------------------
def polyAdd(ps1, ps2):
storePoly = queueChain() # 构建存放结果的队列
p1 = ps1.front # 构建 p1,p2分别指向存放元素的表头
p2 = ps2.front
while p1 is not None and p2 is not None:
compare = p1.expon - p2.expon # 对比两者指数的大小
if compare > 0: # 如果p1的指数大
inQue(storePoly, p1)
p1 = p1.next # 将指针指向p1下一个元素
elif compare < 0: # 如果p2的指数大
inQue(storePoly, p2)
p2 = p2.next # 将指针指向p2下一个元素
else:
if p1.coef + p2.coef: #没有抵消则入队
newNote = polyNode(p1.coef + p2.coef, p1.expon) # 如果相等则同时出队,并系数相加后进入结果链
inQue(storePoly, newNote)
p1 = p1.next
p2 = p2.next
while p1 is not None:
inQue(storePoly, p1)
p1 = p1.next
while p2 is not None:
inQue(storePoly, p2)
p2 = p2.next
return storePoly
# -------------------------乘法法定义-------------------
def polyMultiple(ps1,ps2):
storePoly = queueChain()
p1 = ps1.front # 构建 p1,p2分别指向存放元素的表头
p2 = ps2.front
while p1 is not None: # 将p1中的元素逐个弹出
tag = p2 # tag 指向p2的头指针,用于循环相乘
newP2 = queueChain() # 存放一次相乘结果的队列
while tag is not None: # 将爬p1弹出的元素逐个与p2中的元素相乘
if p1.coeftag.coef:
inQue(newP2,polyNode(coef=p1.coef*tag.coef,expon=p1.expon+tag.expon))
tag =tag.next
p1 = p1.next
storePoly = polyAdd(newP2,storePoly)
return storePoly
单向链表反转(单向链表）
给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出应该为4→3→2→1→5→6，即最后不到K个元素不反转。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5)、以及正整数K(<=N)，即要求反转的子链结点的个数。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据，Next是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
主要思路：（reverse_linkedList.py）
-
首先要对输入数据进行预处理，即按地址连接，形成单向链表。（要考虑到多余节点的情况，所以链接到head＝‘－1’时就终止）
-
在反转链表时，可以逐个反转，再将未反转的序列加入到链表中
网友评论