一元多项式_课程设计.doc

数据结构课程设计

题目： 一元多项式计算器

学生姓名：　 刘胜寒 　
学　　号：　 1006403005 　
系　　别：　 计算机科学与技术
专　　业：　 计算机科学与技术 　
指导教师：　 马竹根 讲师
起止日期：　 2012.3.29——2012.4.5

2012年 4月 9 日

目 录

一元多项式操作的设计与开发 I
摘 要 I
关键词 I
1 前言 1
2 需求分析 2
2.1 范围 2
2.1.1 标识 2
2.1.2 系统概述 2
2.2 需求概述 3
2.2.1 系统目标 3
2.2.2 运行环境 3
2.2.3 实验环境 3
Windows 2000 以上，C-Free任意版本。 3
2.2.4 用户的特点 3
2.3功能需求 3
3 概要设计 4
3.1 范围 4
3.1.1 标识 4
3.1.2 系统概述 4
3.2 系统结构 4
4 系统详细设计 5
4.1 范围 5
4.1.1 标识 5
4.1.2 系统概述 5
4.2 详细设计说明 5
4.2.2 字符串处理算法 6
4.2.2 提取多项式各个参数算法设计 7
4.2.3 加减算法设计 9
4.2.4 乘法算法设计 10
4.2.5 化简算法设计 11
5 测试说明 12
5.1 范围 12
5.1.1 标识 12
5.1.2 系统概述 12
5.2 测试计划及预期结果 13
5.3 具体测试情况 13
６总结 14
致 谢 15
附录 16

一元多项式操作的设计与开发

摘 要
系统本次试验依据2012年怀化学院10级数据结构实验要求，较完善的对题目进行了分析，理解和编程，程序思路清晰，考虑全面。
对于此题，可以使用线性表和链式表存储结构存储多项式信息。并根据C语言算法进行编程。
同时本书在后面附带了一部分程序源码和对程序同步的解释。
在用C语言编程的时候，要用到的语句主要有函数调用语句，判断语句，输出和输入语句。

关键词
一元多项式 线性表 系数 指数

28

1 前言
本次课程设计的的目的：是对数据结构所学的额内容进一步理解与巩固，是将计算机课程与实际问题联结起来的关键步骤。通过课程设计，能够提高分析问题，解决问题，从而运用所学知识解决实际问题的能力。
系统的操作非常简单，输入两个多项式（注意：输入多项式中不能含有空格），会有不可预料的错误，而后就会得出两个多项式的相乘，相加，相减的结果。比如输入字符串
2x+5x^8-3.1x^11 和7-5x^8+11x^9就会得到

其中字符串A，B化简后多项式是用来检错的，用来检测字符串处理是否正确并且按照升幂排序。当前系统只支持加减乘三种运算。本系统主要为进行繁杂的多项式加减乘运算的学生和教学工作者使用，节省工作时间，提高工作效率。系统支持任意的多项式，比如-1.3x^0.3+x+2.03x^(-0.12)+x，x+x^(-1.3)+x。此系统是基于数组（线性表）开发，这所以使用数组用来开发此软件主要就是排序方便，可以调用sort（）函数，用链表排序的话比较慢，代码也不是一两句就能写完的。感谢怀化学院计算机系给我了这样一次机会。

2 需求分析
2.1 范围
2.1.1 标识
文件状态：
【 】草稿
【√】正式发布
【 】正在修改
文件标识：一元多项式计算器
需求分析报告
当前版本：
1.0
作 者：
刘胜寒
完成日期：
2012-4-1
2.1.2 系统概述
软件名称：一元多项式计算器
软件功能：为用户提供快速计算两个任意一元多项式的计算器（只包括加法，减法，乘法）。
用户：中学生
开发者：刘胜寒

2.2 需求概述
2.2.1 系统目标
系统的开发目标是对于用户给定的任意两个一元多项式实现其之间的加法，减法，乘法，三种功能，并且按照升幂的方式输出运算结果。
2.2.2 运行环境
配置一般的PC机就行，运行环境为win7/xp（此系统在win7环境下开发，调试，测试）。
2.2.3 实验环境
Windows 2000 以上，C-Free任意版本。
2.2.4 用户的特点
经常进行一元多项式操作的工作者。
2.3功能需求
用户要求输入两个字符串（任意一元多项式）然后进行加减乘操作，并且按照升幂输出结果。此系统可以直接输入两个任意一元多项式的字符串，支持同类项合并（输入的多项式可以有相同的指数），去掉系数为０的项。网上关于一多项式的操作代码大多是分别输入多项式的有几项然后依次输入各项的系数、指数，有的不支持同类项合并，有的连小数都不支持，还要人工进行拆分系数，指数合并同类项，增加许多麻烦，这与系统原来的意愿背道而驰。
此系统缺点就是没有菜单，只有输入输出。操作界面蹩脚，不能给用户一个友好的操作界面。
优点就是操作简单，只需用户输入一元多项式即可，一元多项式的格式不限，注意：输入一个完整的多项式时中间不能有空格，因为此系统是用cin读入。
3 概要设计
3.1 范围
3.1.1 标识
文件状态：
【 】草稿
【√】正式发布
【 】正在修改
文件标识：
概要设计报告
当前版本：
1.0
作 者：
刘胜寒
完成日期：
2012-3-31
3.1.2 系统概述
软件名称：一元多项式计算器。
软件功能：为学生用户提供快速计算两个一元多项式的计算器（只包括加法，减法，乘法）。
用户：初中生。
开发者：刘胜寒
3.2 系统结构
该系统直接面向用户。用户可以直接运行此软甲，进行一元多项式的操作。
该系统只是进行简单的一元多项式的计算，没有设计什么菜单，用户类型，用户权限。这只是一个工具。
4 系统详细设计
4.1 范围
4.1.1 标识
文件状态：
【 】草稿
【√】正式发布
【 】正在修改
文件标识：
详细设计报告
当前版本：
1.0
作 者：
刘胜寒
完成日期：
2011-4-10
4.1.2 系统概述
软件名称：一元多项式简单计算器
软件功能：节约学生计算一元多项式的时间，提高效率。
用户：初中生
开发者：刘胜寒。
4.2 详细设计说明
此软件按照分治思想来进行编写的。分别进行，字符串处理算法设计，提取多项式各个系数和指数算法设计，加、减、乘算法设计，化简算法设计，输出算法设计。这设计每个算法时，定义每个函数的参数，所要实现那些功能。
int cmp(Node A,Node B) 比较指数
int huajian(Node AB[],int n) 合并同类项
int zhuanhuan(char A[],string AB[]) 分解一元多项式
int Tiqu(string A,Node AB[],int S) 提取单项式的系数和指数
int Multi(Node AB1[],int n,Node AB2[],int m,Node AB3[])
多项式相乘
int add_sub(Node tmp1[],int n,Node tmp2[],int m,Node AB3[],int N)
多项式相加或者相减
void output(Node A[],int n) 输出计算结果
4.2.2 字符串处理算法
这个函数的主要功能就是分解一元多项式的项数，把一元多项式变成一个个单项式。例如2x+5x^8-3.1x^11，会被分解为2x，+5x^8，-3.1x^11。
也是整个系统的第一个函数，待操作的一元多项式都会经过这个函数进行处理。
参数分别为待处理的一元多项式A，和用来保存单项式的数组AB。
int zhuanhuan(char A[],string AB[])
{ // A[] 输入的一元多项式 AB[] 分解后的一元多项式
string B="";
int s=0;
for(int i=0;i<strlen(A);i++)
{
if((A[i]=='+'||A[i]=='-')&&(A[i-1]==')'||A[i-1]=='x' )&&i!=0)
{//判断是否为多项式
AB[s++]=B;
B="";
}
if((A[i]=='+'||A[i]=='-')&& (A[i-1]<='9'&&A[i-1]>='0' ) )
{//判断是否为多项式
AB[s++]=B;B="";
}
B=B+A[i];
if(i==strlen(A)-1)
{//结束
AB[s++]=B;B="";
}
}
return s;//一元多项式的个数
}
4.2.2 提取多项式各个参数算法设计
个提取单项式的系数和指数，参数A代表单项式，AB用来存放单项式的系数和指数。S表示有多少个单项式，用来返回AB的有效个数。

int Tiqu(string A,Node AB[],int S)
{
int l,BJ=-1,bj=-1,i,B[2],s=0,Bj=-1;
// BJ标记x的位置 bj标记系数有无括号 Bj表示指数是否含有‘-’
double x=0,y=0;//x 用来存放 系数 y用来存放指数
l=A.length();
memset(B,-1,sizeof(B));
// 用来标记 小数点的位置 B[0]标记系数 B[1]标记 指数
for(int i=0;i<l;i++)
{
if(A[i]=='x')
{
BJ=i;// BJ 标记 x 的位置
break;
}

if(A[i]=='.')
B[0]=i;//系数 小数点的 位置
}
for(i=l-1;i>=BJ;i--)
{
if(A[i]=='(') bj=i; // 指数 括号的位置
if(A[i]=='.') B[1]=i; // 指数 小数点的 位置
if(A[i]=='-') Bj=i; // 指数 判断有无 '-'
if(A[i]=='^')break;
}
if(BJ!=-1)//********************
{//x^n n!=0
for(int j=0;j<BJ;j++)
{
if(A[j]>='0'&&A[j]<='9')
x=x*10+A[j]-'0';
}
if((A[0]=='+'||A[0]=='-')&&A[1]=='x')x=1;
if(A[0]=='x')x=1;
if(A[0]=='-')x=-x;
if(B[0]!=-1)
x=x*pow(0.1,BJ-B[0]-1);
}
if(BJ==-1)// x^n n=0
{
for(int j=0;j<l;j++)
{
if(A[j]>='0'&&A[j]<='9')
x=x*10+A[j]-'0';
}
if(A[0]=='-')x=-x;
if(B[0]!=-1)
x=x*pow(0.1,l-B[0]-1);

}
//****处理指数
if(BJ==-1)y=0;//没有指数 也就是指数为0
if(BJ!=-1)
{
for(int j=BJ+1;j<l;j++)
{
if(A[j]>='0'&&A[j]<='9')
y=y*10+A[j]-'0';
}
if(BJ+1==l)y=1;
if(B[1]!=-1)
{
if(bj!=-1)
{//有括号
y=y*pow(0.1,l-2-B[1]);
}
if(bj==-1)
{
y=y*pow(0.1,l-B[1]-1);
}
}
}
if(Bj!=-1)y=-y;
AB[S].x=x;
AB[S].y=y;
S++;
cout<<x<<" "<<y<<endl;
return S;
}
4.2.3 加减算法设计
进行加法或者减法计算，加法和减法只是后者取相反数，这个参数N为0时，tmp2的参数全部去相反数，就执行减法运算了。
tmp1存储第一个多项式的系数和指数，n为个数。tmp2和tmp1一样，m为tmp2存储个数。N判断加法还是减法
int add_sub(Node tmp1[],int n,Node tmp2[],int m,Node AB3[],int N)
{ //N=0 执行减法 N=1 执行加法 AB3[] 运行后的结果
Node AB1[100], AB2[100];
for(int i=0;i<n;i++)//复制
AB1[i]=tmp1[i];
for(int i=0;i<m;i++)//复制
{
AB2[i]=tmp2[i];
if(N==0)// 判断是否执行减法
AB2[i].x*=-1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(AB1[i].y==AB2[j].y)
{
AB1[i].x+=AB2[j].x;
AB2[j].x=0; // 标记 是否有同类项
}
AB3[i]=AB1[i];
}
for(int j=0;j<m;j++)//添加未被运算的多项式
{
if(AB2[j].x!=0)
AB3[n++]=AB2[j];
}
for(int i=0;i<n;i++)//同类项合并
{
for(int j=i+1;j<n;j++)
{
if(AB3[i].y==AB3[j].y)
{
AB3[i].x+=AB3[j].x;
AB3[j].x=0; // 标记 是否有同类项
}
}
}
sort(AB3,AB3+n,cmp); //升幂排序
return n;// 执行 加法或者减法后的 不同项的个数
}
4.2.4 乘法算法设计
执行乘法AB3用来保存运算结果
int Multi(Node AB1[],int n,Node AB2[],int m,Node AB3[])
{
int s=0;
for(int i=0;i<n;i++)//for 循环
{
for(int j=0;j<m;j++)
{
AB3[s].x=AB1[i].x*AB2[j].x;
AB3[s].y=AB1[i].y+AB2[j].y;
s++;
}
}
for(int i=0;i<s;i++)//合并同类项
{
for(int j=i+1;j<s;j++)
{
if(AB3[i].y==AB3[j].y)
{
AB3[i].x+=AB3[j].x;
AB3[j].x=0; // 标记 是否有同类项
// cout<<AB1[i].x<<" "<<AB1[i].y<<endl;
}
}
}
sort(AB3,AB3+s,cmp);
return s;
}

4.2.5 化简算法设计
int huajian(Node AB[],int n)
{
sort(AB,AB+n,cmp);
int s=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
if(AB[i].y==AB[j].y&&AB[i].x!=0)
{
AB[i].x+=AB[j].x;
AB[j].x=0; // 标记 是否有同类项
}
}
for(int i=0;i<n;i++)
if(AB[i].x!=0)
AB[s++]=AB[i];
return s;
}
4.2.6 输出算法设计
void output(Node A[],int n)
{
double x,y;
int BJ=0;//表示是否所有的多项式的因子全为0 即多项式为0
for(int i=0;i<n;i++)
{
x=A[i].x;
y=A[i].y;
if(x!=0)BJ=1;
if(x>0&&i!=0)cout<<'+';
if(x<0)cout<<'-';
if(y==0)
{
cout<<fabs(x);
}
else if(y==1)
{
if(fabs(x)!=1)
cout<<fabs(x)<<'x';
else cout<<'x';
}
else if(y<0)
{
if(fabs(x)!=1)
cout<<fabs(x)<<"x^("<<y<<')';
else
cout<<"x^("<<y<<')';
}
else
{
if(fabs(x)!=1)
cout<<fabs(x)<<"x^"<<y;
else cout<<"x^"<<y;
}
}
if(BJ==0)cout<<0;
cout<<endl;
}

5 测试说明
5.1 范围
5.1.1 标识
文件状态：
【 】草稿
【√】正式发布
【 】正在修改
文件标识：
需求分析报告
当前版本：
1.0
作 者：
刘胜寒
完成日期：
2011-4-10
5.1.2 系统概述
软件名称：一元多项式简单计算器
软件功能：节约学生计算一元多项式的时间，提高效率。
用户：初中生
开发者：刘胜寒。
5.2 测试计划及预期结果
( 2x+5x^8-3.1x^11 )+(7-5x^8+11x^9) = 7+2x+11x^9-3.1x^11
( 2x+5x^8-3.1x^11 )-(7-5x^8+11x^9) = 7+2x+11x^9-3.1x^11
( 2x+5x^8-3.1x^11 )*(7-5x^8+11x^9) =
14x+35x^8-10x^9+22x^10-21.7x^11-25x^16+55x^17+15.5x^19-34.1x^20

(6x^(-3)-x+4.4x^2-1.2x^9)+(-6x^(-3)+5.4x^2-x^2+7.8x^15)= -x+8.8x^2-1.2x^9+7.8x^15
(6x^(-3)-x+4.4x^2-1.2x^9)-(-6x^(-3)+5.4x^2-x^2+7.8x^15)= 12x^(-3)-x-1.2x^9-7.8x^15
(6x^(-3)-x+4.4x^2-1.2x^9)*(-6x^(-3)+5.4x^2-x^2+7.8x^15)= -36x^(-6)+6x^(-2)
-4.4x^3+19.36x^4+7.2x^6-5.28x^11+46.8x^12-7.8x^16+34.32x^17-9.36x^24

(x+x^2)+(1+x+x^2)= 1+2x+2x^2
(x+x^2)-(1+x+x^2)= -1
(x+x^2)*(1+x+x^2)= x+2x^2+2x^3+x^4

5.3 具体测试情况
2x+5x^8-3.1x^11 7-5x^8+11x^9

6x^(-3)-x+4.4x^2-1.2x^9 -6x^(-3)+5.4x^2-x^2+7.8x^15

x+x^2 1+x+x^2

６总结
通过这次课程设计，有对数据结构加深一次认识，对C语言编程有了一定的提高。另外也提高了我分析问题，解决问题，从而运用所学知识解决实际问题的能力。
一开始选这个课题的时候感觉应该很容易，因为只牵涉到一元多项式的加减乘。按照一班的写法就是把多项式的因子和指数分开读取，这样写的话，确实蛮简单，网上各种资料一大堆。基本不用修改什么就可以拿来用了。但这是不是我想要的，按照我的想法就是把一元多项式用字符串的方法读取。这样可以方便用户操作，大大节约用户的时间。
一个大的程序是有许许多多小的函数组成的。给定每个函数的接口，任务，功能。这样就能化难为简，化繁为简。
这次没有使用链表写，是因为对链表不是很感兴趣，换成链表写的话，就改一下排序就行了。因为用数组写的时后可以调用函数sort直接进行排序，如果用链表，要用比较暴利的循环在进行排序。其他地方就不需要怎么大的修改就行可以实现用链表操作。

参考文献
[1] 杨永斌. 数据结构理论与实践 [M]. 天津科学技术出版社, 2011.
[2] 谭浩强，C程序语言设计（第三版）[M]. 清华大学出版社, 2007.
致 谢
经过一个月的忙碌，课程设计顺利完成了。
在这里感谢我的数据结构老师高艳霞在以往的基础课学习中为我打下来良好的基础，是我这次课程设计能够顺利完成的前提。
感谢指导老师马竹根的悉心指导，没有他的帮助很多关键部分以己之力是很难完成，马老师的悉心知道是这次课程设计顺利完成的必要条件。
感谢学校能够给我们提供这么好的机房，是我方便上网查资料，有地方做这次的课程设计，
很感谢寝室的室友，请他们帮我调试，提了不少宝贵的意见，是我的程序有了进一步的完善。

附录
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
struct Node
{
double x,y;
};
int N=45,NN=43;
int cmp(Node A,Node B)
{
if(A.y>B.y)return 0;
else return 1;
}
int huajian(Node AB[],int n)
{
sort(AB,AB+n,cmp);
int s=0;
for(int i=0;i<n;i++)//合并同类项
{
for(int j=i+1;j<n;j++)
if(AB[i].y==AB[j].y&&AB[i].x!=0)
{
AB[i].x+=AB[j].x;
AB[j].x=0; // 标记 是否有同类项
}
}
for(int i=0;i<n;i++)
{
if(AB[i].x!=0)
AB[s++]=AB[i];
}

return s;
}
int zhuanhuan(char A[],string AB[])
{
string B="";
int s=0;
for(int i=0;i<strlen(A);i++)
{
if( (A[i]=='+'||A[i]=='-') && ( A[i-1]==')'||A[i-1]=='x' )&&i!=0)
{
AB[s++]=B;
B="";
}
if( (A[i]=='+'||A[i]=='-') && ( A[i-1]<='9'&&A[i-1]>='0' ) )
{
AB[s++]=B;
B="";
}
B=B+A[i];
if(i==strlen(A)-1)
{
AB[s++]=B;B="";
}
}
return s;
}
int Tiqu(string A,Node AB[],int S)
{
int l,BJ=-1,bj=-1,i,B[2],s=0,Bj=-1;
double x=0,y=0;
l=A.length();
memset(B,-1,sizeof(B));
for(int i=0;i<l;i++)
{
if(A[i]=='x')
{
BJ=i;// x 的位置
break;
}

if(A[i]=='.')
B[0]=i;//因子 小数点的 位置
}
for(i=l-1;i>=BJ;i--)
{
if(A[i]=='(') bj=i; // 括号的位置
if(A[i]=='.') B[1]=i; //指数 小数点的 位置
if(A[i]=='-') Bj=i; //判断有无 '-'
if(A[i]=='^')break;
}
//***********************处理因子******************************************
if(BJ!=-1)//********************
{//x^n n!=0
for(int j=0;j<BJ;j++)
{
if(A[j]>='0'&&A[j]<='9')
x=x*10+A[j]-'0';
}
if((A[0]=='+'||A[0]=='-')&&A[1]=='x')x=1;
if(A[0]=='x')x=1;
if(A[0]=='-')x=-x;
if(B[0]!=-1)
x=x*pow(0.1,BJ-B[0]-1);
}
//*****************
if(BJ==-1)// x^n n=0
{
for(int j=0;j<l;j++)
{
if(A[j]>='0'&&A[j]<='9')
x=x*10+A[j]-'0';
}
if(A[0]=='-')x=-x;
if(B[0]!=-1)
x=x*pow(0.1,l-B[0]-1);

}
//****************************处理指数***************************************
if(BJ==-1)y=0;//没有指数 也就是指数为0
if(BJ!=-1)
{
for(int j=BJ+1;j<l;j++)
{
if(A[j]>='0'&&A[j]<='9')
y=y*10+A[j]-'0';
}
if(BJ+1==l)y=1;
if(B[1]!=-1)
{
if(bj!=-1)
{//有括号
y=y*pow(0.1,l-2-B[1]);
}
if(bj==-1)
{
y=y*pow(0.1,l-B[1]-1);
}
}
}
if(Bj!=-1)y=-y;
AB[S].x=x;
AB[S].y=y;
S++;
//************************************************************************
return S;
}
int Multi(Node AB1[],int n,Node AB2[],int m,Node AB3[])
{
int s=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
AB3[s].x=AB1[i].x*AB2[j].x;
AB3[s].y=AB1[i].y+AB2[j].y;
s++;
}

}
for(int i=0;i<s;i++)
{
for(int j=i+1;j<s;j++)
{
if(AB3[i].y==AB3[j].y)
{
AB3[i].x+=AB3[j].x;
AB3[j].x=0; // 标记 是否有同类项
// cout<<AB1[i].x<<" "<<AB1[i].y<<endl;
}
}
}
sort(AB3,AB3+s,cmp);
return s;
}
int add_sub(Node tmp1[],int n,Node tmp2[],int m,Node AB3[],int N) // 0 - 1 + NM=0,MN=1;
{
Node AB1[100], AB2[100];
for(int i=0;i<n;i++)
AB1[i]=tmp1[i];
for(int i=0;i<m;i++)
{
AB2[i]=tmp2[i];
if(N==0)
AB2[i].x*=-1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
if(AB1[i].y==AB2[j].y)
{
AB1[i].x+=AB2[j].x;
AB2[j].x=0; // 标记 是否有同类项
}
AB3[i]=AB1[i];
}
for(int j=0;j<m;j++)
{
if(AB2[j].x!=0)
AB3[n++]=AB2[j];
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(AB3[i].y==AB3[j].y)
{
AB3[i].x+=AB3[j].x;
AB3[j].x=0; // 标记 是否有同类项
// cout<<AB1[i].x<<" "<<AB1[i].y<<endl;
}
}
}
sort(AB3,AB3+n,cmp);
return n;
}
void output(Node A[],int n)
{
double x,y;
int BJ=0;
for(int i=0;i<n;i++)
{
x=A[i].x;
y=A[i].y;
if(x!=0)BJ=1;
if(x>0&&i!=0)cout<<'+';
if(x<0)cout<<'-';
if(y==0)
{
cout<<fabs(x);
}
else if(y==1)
{
if(fabs(x)!=1)
cout<<fabs(x)<<'x';
else cout<<'x';
}
else if(y<0)
{
if(fabs(x)!=1)
cout<<fabs(x)<<"x^("<<y<<')';
else
cout<<"x^("<<y<<')';
}
else
{
if(fabs(x)!=1)
cout<<fabs(x)<<"x^"<<y;
else cout<<"x^"<<y;
}
}
if(BJ==0)cout<<0;
cout<<endl;
}
int main()
{
char A1[100],A2[100];
while(cin>>A1>>A2,A1!="X")
{
string AB[100];
int B,i,s,S1=0,S2=0,S=0;
int NM=0,MN=1;
Node AB1[100],AB2[100],AB3[100];
B=zhuanhuan(A1,AB);// B 多少项
for(i=0;i<B;i++)
{
s=Tiqu(AB[i],AB1,S1);
S1++;
}
S1=huajian(AB1,B);
cout<<"/************字符串 A 化简后多项式*************/"<<endl;
for(int j=0;j<S1;j++)//S1 字符串 A多项式的个数
cout<<AB1