一元稀疏多项式计算器(数据结构)

院 系 计算机科学学院 专 业 软件工程 年 级 2013 级 课程名称 数据结构 姓 名 韦宜 4 指导教师 宋中山 2015 年 12 月 15 日 1 题目 设计一个一元稀疏多项式简单计算器 班级 软件工程 1301 姓名 韦宜 学号 4 完成日期 12 月 15 日 1 需求分析需求分析 问题描述 设计一个一元多项式加法器 基本要求 输入并建立多项式 2 两个多项式相加 3 输出多项式 n c1 e1 c2 e2 cn en 其中 n 是多项式项数 ci 和 ei 分别是第 i 项的 系数和指数 序列按指数降序排列 4 计算多项式在 x 处的值 5 求多项式的导函数 软件环境 Windows UNIX Linux 等不同平台下的 Visual C 6 0 硬件环境 512MB 内存 80Gb 硬盘 Pentium4 CPU CRT 显示器 2 2 概要分析概要分析 本程序有五个函数 PolyNode Input 输入函数 PolyNode Deri PolyNode head 求导函数 PolyNode Plus PolyNode A PolyNode B 求和函数 void Output PolyNode head 输出函数 int main 主函数 本程序可使用带有附加头结点的单链表来实现多项式的链表表示 每个链表结点表示多项 式的一项 命名为 node 它包括两个数据成员 系数 coef 和指数 exp 他们都是公共数据 成员 next 为指针域 用链表来表示多项式 适用于不定的多项式 特别是对于项数再运 算过程中动态增长的多项式 不存在存储溢出的问题 其次 对于某些零系数项 在执行 加法运算后不再是零系数项 这就需要在结果多项式中增添新的项 对于某些非零系数项 在执行加法运算后可能是零系数项 这就需要在结果多项式中删去这些项 利用链表操作 可以简单的修改结点的指针以完成这种插入和删除运算 不像在顺序方式中那样 可能移 动大量数据项 运行效率高 3 3 详细设计详细设计 1 主函数 int main PolyNode head a head b int choice head a new PolyNode head a next NULL do system cls 清屏函数 Output head a cout n cout 1 输入公式 n cout 2 求 导 n cout 3 两式求和 n cout 4 退出程序 n cout choice if choice 1 head a Input else if choice 2 head a Deri head a 求导 else if choice 3 head b Input head a Plus head a head b 求和 else if choice 4 break else cout next NULL if p next exp 0 p next NULL 指数为零返回 else p next coef p next exp 系数乘以指数 p next exp 指数减一 p p next return head 用于对输入的多项式进行求导 求导在链表内进行计算 即运算完成链表的值改变 返回 头指针 PolyNode Plus PolyNode A PolyNode B 求和函数 流程图如下 6 start N Y N Y N Y Y N N Y N Y N Y 建立链表 head p head 两头指针 A B 均指向各自的 next A B 为 空 A 的指数大于 B 的指数 A B 的系数 互为倒数 AB 指数相等 B 为空 A 为空 p next NULL 将 A 的当前接点接到 新链表后面 A 后指 A B 均后指 将 B 接到 p 后面 合并相同系数相同项 连接到新链表后面 将 A 接到 p 后 面 将 B 的当前接点接到 新链表后面 B 后指 如果 AB 都为空 返回头指针 END PolyNode Plus PolyNode A PolyNode B 7 本函数用于对多项式进行加法计算 需要运用存有两个多项式的头指针 前一头指针可是 前一计算的计算结果 也可是调用输入函数 后一头指针是调用输入函数输入的多项式的 头接点 经过计算得到一个新的链表 函数返回链表的头指针 求和函数部分代码 PolyNode Plus PolyNode A PolyNode B 相加 PolyNode head p head new PolyNode p head A A next B B next while A NULL B NULL if A NULL p next B break 如果 A 空 把 B 后面的所有接点接到 p 之 后 if B NULL p next A break 如果 B 空 把 A 后面的所有接点接到 p 之 后 if A exp B exp 如果两指数数相等 相加 if A coef B coef 0 p next new PolyNode p p next p exp A exp p coef A coef B coef A A next B B next continue 如果两系数互为倒数 不保存 后指 继续 循环 if A exp B exp A 的指数大于 B 的指数 p next new PolyNode p p next p exp A exp p coef A coef A A next continue 将 A 的当前接点接到新链表后面 A 后指 p next new PolyNode p p next p exp B exp p coef B coef 8 B B next 将 B 的当前接点接到新链表后面 B 后指 if A NULL return head 返回头指针 3 其他函数 同组的成员设计 include include using namespace std typedef struct node float coef 系数 int exp 指数 struct node next 指针域 指向下一个系数不为 0 的子项 PolyNode PolyNode Input 输入函数 float c 系数域 int e 指数域 PolyNode p q r head cout 请输入多项式 n cout next NULL for cin c e if c 0 结束输入 if c 0 continue 从新输入 不保存 if head next NULL 输入第一个接点 p next new PolyNode p p next p coef c p exp e p next NULL continue p head while p next NULL 如果输入的指数小于 p 9 的下一个接点 p 向后指 if e p exp p coef c continue 如果相等 直接加上去 继续循环 q new PolyNode q coef c q exp e if p next NULL p next q q next r continue p next q 如果输入的值小于 所有接点 接在最后一个接点之后 p p next p next NULL return head 输出函数 void Output PolyNode head 输出 PolyNode p p head next if p NULL cout 当前没有公式或计算结果为 0 请选 1 输入 n return if p NULL cout 计算结果 n cout coef X exp p p next while p NULL cout coef X exp p p next cout endl cout 如果想重新输入公式 请选 1 输入 n n 4 调试分析与操作说明调试分析与操作说明 1 当程序运行时 进入主界面 如图 10 此时输入 1 4 选择操作 2 输入 1 后按回车出现 输入 1 2 3 4 5 6 0 0 后按回车之后 会出现界面 11 3 求导 输入 2 求导后按回车会出现结果 结果正确 4 求和 如果进入图 4 3 后输入 3 后按回车会出现界面 12 图 4 5 求和界面 输入 2 2 4 4 6 6 0 0 后结果会出来 图 4 6 求和结果 结果正确 此系统在得到计算结果后可以直接用计算的结果进行下一步计算 如果不想用 当前的结果 也可按 1 重新输入公