一元多项式计算（数据结构课程设计）

号： 名： 级： 绩：池 州 学 院 CHIZHOU COLLEGE

《数据结构》 课程设计报告

57 54 39 37 20 25 27 周田 张永鹏 武警 温凯侨 李坤 米昌华 阮健健

10计算机科学与技术（2）班

数学与计算机科学系

学姓 班指导教师：成

一、 课程设计基本情况

1、设计名称

一元多项式计算

2、主要功能

能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；

3、设计平台

电脑、Visual c++ 6.0

二、 系统设计

1、算法思想

根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。

因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。

(1)一元多项式加法运算

它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。

(2)一元多项式的减法运算

它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。

2、概要设计

(1)主函数流程图：

（注：a代表第一个一元二次方程，b代表第二个一元二次方程）

开 始 定义结构体 定义函数类型及名称 输出多项式，求项数 构造指数比较函数 排列顺序(降序）

创建并初始化多项式链表 输 入 系 数 和 指 数 合并同类项 指数相同 指数不同 按指数排序

输 出 构 造 出 的 多 项 式 减 法 运 算 开 始 进 行 加 用单链接储存a,b项目的系数和指数 a项指数值b 项指数值 将a和b的系数相加(减) 按指数值按降序排列 摘取b的指数值到“和多项式” 释放a和b的结点 输 出 计 算 后 的 多 项 式 将 单 链 表 的 节 点 释 放，使 已 建 立 的 多 项 式 销 毁 结 束