2015-04-多项式运算链表实现

背景

大一下学期 C 程序设计专题(C大程)的第二个专题,关于链表的操作,比较水的一次 Project ,当时正好生病了,便也没做的太认真,一开始是打算采用 GUI 或者 TeX 或者 HTML + CSS 实现多项式的显示的,以及幂为多项式的运算的,然而最后 DDL 在五一期间,赶完通识课的论文后就没有精力了(尤其是还生病了),当时的坑就放弃了。将具体链表操作的实现(毕竟比较简单)交给了队友 MagicPants ,然后我就实现了简单的 IO 操作和文件的模块化划分(这次变成我是可有可无的角色了(⊙﹏⊙))。不过当时正好看了《 C 专家编程》,便尝试了一下可变参量列表。

Screenshot1

Screenshot2

Screenshot3

报告及源码

一、问题说明(By LLonely)

采用链表结构,运用迭代等算法,设计相应的函数,计算出两个以链表结构储存的多项式的乘积。该问题涉及到多项式的输入、链表的相关操作、多项式的运算及输出等过程。

二、算法设计与说明(By MagicPants)

首先输入两个多项式(即新建两个链表)。分别为list1、list2.复制一个list1,得到list1’,再取list2中的第一项分别与list1’的每一项相乘,得到result1。随后再复制一个list1,得到list1’再取list2中的第二项乘以list1‘的每一项,得到result2.

以此类推(运用迭代的算法分别用list2的每一项与list1相乘得到result1、result2…)。最后可以得到Result = result1 + result2 +result3+ …,Result即为两多项式的积。

以上过程主要涉及到链表的操作及迭代运算。

三、数据结构设计与说明(By MagicPants)

对于多项式的乘法,首先要考虑多项式的存储。我们采用链表的结构存储多项式。每一个节点都存了多项式的一项。用该链表的头指针代表该多项式。

且该链表结构的定义存放在definitions.h头文件中。代码如下所示:

四、系统设计难点与解决方案

core.c 开发及测试过程(By MagicPants):

  1. sum求和函数中两多项式相加。情况复杂需要细致的分类讨论。
  2. sum求和函数中系数变为0的情况
  3. 输入多项式时需考虑可能输入幂相同的项,此时需要考虑合并同类项。而再写一个合并一个多项式同类项的函数的话,难写而且麻烦。而我队友 LLonely 的一个想法很好的解决了这个问题。即在输入多项式时调用sum函数,将输入的每一项用sum函数加到前面的多项式中,而sum函数会帮我们解决合并同类项的问题。让我启发很大。
  4. 多项式乘法如何操作的问题。我们采用逐项相乘再相加的方法。即用第二个多项式的每一项分别乘以第一个多项式。再将这些多项式相加,得到结果。

io.c main.c及头文件开发及测试过程(By LLonely):

  1. 头文件重复引用问题。在模块式开发时,将变量、函数定义储存在头文件中,必然需要在多个文件中都引用该头文件。为了避免编译、链接过程中的重复引用与定义,在参考标准头文件写法及相关文献后,我们采用宏进行了限制。如下所示:
  2. 多项式的一次性输入。采用了char类型的buf数组缓存输入,然后以运算符为分隔符逐项构建多项式。缺陷是必须依照范例输入,否则录入数据不可靠。
  3. 输出函数的模块化封装。一个单一函数无法满足全部需求。为了满足函数的模块化需求,采用了可变参数列表的方式设计了可分运行模式的输出函数。

五、人员分工说明(By LLonely)

本小组仍然采用Git进行版本库控制。

链表操作以及多项式运算相关函数由MagicPants开发,作为核心模块(core.c)。

输入输出函数及主程序框架文件由LLonely开发,作为IO模块(io.c)和主程序模块(main.c)。

六、程序源码

definitions.h


functions.h

 


main.c


io.c


core.c

发表评论

电子邮件地址不会被公开。 必填项已用*标注