多项式加法,数组和指针解决实际问题C++
山东理工大学计算机学院
课程设计
（数据结构）
班级
姓名
学号
指导教师
二○一二年一月十日
课程设计任务书及成绩评定
课题名称顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。
Ⅰ、题目的目的和要求：
1. 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
2．设计题目要求：
1)首先判定多项式是否稀疏
2)分别采用顺序和动态存储结构实现；
3)结果M(x)中无重复阶项和无零系数项；
4)要求输出结果的升幂和降幂两种排列情况；
Ⅱ、设计进度及完成情况
Ⅲ、主要参考文献及资料
[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999
[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999
[3] 谭浩强 C语言程序设计清华大学出版社
[4] 与所用编程环境相配套的C语言或C++相关的资料
Ⅳ、成绩评定：
设计成绩：（教师填写）
指导老师：（签字）
二○一二年一月十日
目录
第一章概述 (1)
第二章系统分析 (2)
第三章概要设计 (3)
第四章详细设计 (4)
第五章运行与测试 (17)
第六章总结与心得 (19)
参考文献 (20)
第一章概述
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。分别采用顺序结构和链式存储结构，利用多项得结果，最后得多项式中不含有重复阶项和零系数得项。除此之外，还得分为降幂和升幂两种排序方式。
。
第二章系统分析
1．顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。
2．在程序过程中加入汉字提示符，让使用者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了。
3．程序执行时的命令：①选择创建两个一元多项式②输入第一个一元多项式的项数③依次输入一元多项式的系数和指数④以相同方式输入第二个一元多项式⑤选择操作方式⑥选择降幂或升幂排序⑦输出结果⑧是否退出。
4. 测试数据。输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，
-9 8。加法结果为；升幂降幂
减法结果为：升幂降幂
乘法结果为：升幂降幂
第三章概要设计
1、数据结构的设计
在该程序中分别分为顺序存储和链式存储结构。
2、算法的设计
本程序主要分为四大模块
①主程序模块
②输入模块：通过main函数输入
③输出模块（升幂降幂）：PrintPolyn函数实现输出
④数据处理模块（多项式的加减乘）：通过一元多项式的Polynomial基本操
作实现
3、抽象数据类型的设计
一元多项式抽象数据类型的定义：
抽象数据类型Polynomial的定义：
第四章详细设计
#include
using namespace std;
struct term//顺序表和链表的的定义
{
float xishu; //系数
int zhishu; //指数
};
struct LNode
{
term data; //term多项式值
struct LNode *next;
};
typedef LNode* polynomail;
/*合并同类项*/
polynomail hebing(polynomail Head)
{
polynomail r,q,p,Q;
for(q=Head->next;q!=NULL;q=q->next)//合并同类项
for(p=q->next,r=q;p!=NULL;)
if(q->data.zhishu==p->data.zhishu)//指数相等系数相加
{
q->data.xishu=q->data.xishu+p->data.xishu;
r->next=p->next;
Q=p;p=p->next;
delete Q;//释放p
}
else
{
r=r->next;
p=p->next;
}
return Head;//得到不含同类项的多项式
}
/*又小到大排列*/
void arrange1(polynomail pa)
{
polynomail h=pa,p,q,r;
for(p=pa;p->next!=NULL;p=p->next);r=p;//r指向参与比较的最后一个while(h->next!=r)//大的沉底
{
for(p=h;p->next!=r&&p!=r;p=p->next)
if(p->next->data.zhishu>p->next->next->data.zhishu)//比较指数的大小
{
q=p->next->next;
p->next->next=q->next;//指数大的向前移动
q->next=p->next;
p->next=q;
}
r=p;//r指向参与比较的最后一个，不断向前移动
}
}
/*由大到小排序*/
void arrange2(polynomail pa)
{
polynomail h=pa,p,q,r;
for(p=pa;p->next!=NULL;p=p->next); r=p;
while(h->next!=r)//小的沉底
{
for(p=h;p->next!=r&&p!=r;p=p->next)
if(p->next->data.zhishu
{
q=p->next->next;
p->next->next=q->next;//指数小的向后移动
q->next=p->next;
p->next=q;
}
r=p;//r指向参与比较的最后一个，不断向前移动
}
}
/*判断多项式的稀疏 */
bool judge(polynomail Head)//逻辑变量字符bool
{
arrange2(Head);
polynomail p;
p=Head->next;
bool xi=false;
while(p!=NULL&&p->next!=NULL&&!xi)
{
if(p->data.zhishu-p->next->data.zhishu>1)
xi=true;
p=p->next;
}
return xi;
}
/*打印多项式,求项数*/
void printpolyn(polynomail P)
{
int i;
polynomail q;
if(P==NULL)
cout<<"无项"< else if(P->next==NULL) cout<<"Y=0"< else { cout<<"该多项式为Y="; q=P->next; i=1; if(q->data.xishu!=0&&q->data.zhishu!=0) { cout< i++; } if(q->data.zhishu==0&&q->data.xishu!=0) cout< q=q->next; if(q==NULL) { cout< return ; } while(1)//while中，打印剩下项中系数非零的项， { if(q->data.xishu!=0&&q->data.zhishu!=0) { if(q->data.xishu>0) cout<<"+"; cout< i++; } if(q->data.zhishu==0&&q->data.xishu!=0) { if(q->data.xishu>0) cout<<"+"; cout< } q=q->next; if(q==NULL) { cout< break; } } } } /*1、创建并初始化多项式链表*/ polynomail creatpolyn(int m) { polynomail Head,r,s; int i; Head=new LNode; r=Head; for(i=0;i { s=new LNode; cout<<"请输入第"< cin>>s->data.xishu>>s->data.zhishu; r->next=s; r=s; } r->next=NULL; if(m>1) { Head=hebing(Head); } return Head; } /*2、两多项式相加*/ polynomail addpolyn(polynomail pa,polynomail pb) { polynomail s,newHead,q,p,r;int j; p=pa->next; q=pb->next; newHead=new LNode; r=newHead; while(p) { s=new LNode; s->data.xishu=p->data.xishu; s->data.zhishu=p->data.zhishu; r->next=s; r=s; p=p->next; } while(q) { s=new LNode; s->data.xishu=q->data.xishu; s->data.zhishu=q->data.zhishu; r->next=s; r=s; q=q->next; } r->next=NULL; if(newHead->next!=NULL&&newHead->next->next!=NULL)//合并同类项newHead=hebing(newHead); cout<<"升序 1 , 降序 2"< cout<<"选择:"; cin>>j; if(j==1) arrange1(newHead); else arrange2(newHead); return newHead; } /*3、两多项式相减*/ polynomail subpolyn(polynomail pa,polynomail pb) { polynomail s,newHead,q,p,r; int j; p=pa->next;q=pb->next; newHead=new LNode; r=newHead; while(p) { s=new LNode; s->data.xishu=p->data.xishu; s->data.zhishu=p->data.zhishu; r->next=s; r=s; p=p->next; } while(q) { s=new LNode; s->data.xishu=-q->data.xishu; s->data.zhishu=q->data.zhishu; r->next=s; r=s; q=q->next; } r->next=NULL; if(newHead->next!=NULL&&newHead->next->next!=NULL)//合并同类项newHead=hebing(newHead); cout<<"升序 1 , 降序 2"< cout<<"选择:"; cin>>j; if(j==1) arrange1(newHead); else arrange2(newHead); return newHead; } /*4两多项式相乘*/ polynomail mulpolyn(polynomail pa,polynomail pb) { polynomail s,newHead,q,p,r; int j; newHead=new LNode; r=newHead; for(p=pa->next;p!=NULL;p=p->next) for(q=pb->next;q!=NULL;q=q->next) { s=new LNode; s->data.xishu=p->data.xishu*q->data.xishu; s->data.zhishu=p->data.zhishu+q->data.zhishu; r->next=s; r=s; } r->next=NULL; cout<<"升序 1 , 降序 2"< cout<<"选择:"; cin>>j; if(j==1) arrange1(newHead); else arrange2(newHead); if(newHead->next!=NULL&&newHead->next->next!=NULL)//合并同类项newHead=hebing(newHead); return newHead; } /*5、销毁已建立的两个多项式*/ void delpolyn(polynomail pa,polynomail pb) { polynomail p,q; p=pa; while(p!=NULL) { q=p; p=p->next; free(q); } p=pb; while(p!=NULL) { q=p; p=p->next; free(q); } cout<<"两个多项式已经销毁"< } void main() { polynomail pa=NULL,pb=NULL; polynomail addp=NULL,subp=NULL,mulp=NULL; int n,m; while(1) { cout<<"1、创建两个一元多项式"< cout<<"2、两多项式相加得一新多项式"< cout<<"3、两多项式相减得一新多项式"< cout<<"4、两多项式相乘得一新多项式"< cout<<"5、销毁已建立的两个多项式"< cout<<"6、退出"< cout<<"请选择："; cin>>n; switch(n) { case 1: if(pa!=NULL) { cout<<"已建立两个一元多项式，请选择其他操作！"; break; } cout<<"请输入第一个多项式:"< cout<<"要输入几项："; cin>>m; while(m==0) { cout<<"m不能为0，请重新输入m:"; cin>>m; } pa=creatpolyn(m); printpolyn(pa); if(judge(pa)) cout<<"该多项式稀疏"< else cout<<"该多项式稠密"< cout<<"请输入第二个多项式:"< cout<<"要输入几项："< cin>>m; pb=creatpolyn(m); printpolyn(pb); if(judge(pb)) cout<<"该多项式稀疏"< else cout<<"该多项式稠密"< break; case 2: if(pa==NULL) { cout<<"请先创建两个一元多项式！"< break; } addp=addpolyn(pa,pb);//多项式相加 printpolyn(addp); break; case 3: if(pa==NULL) { cout<<"请先创建两个一元多项式!"< break; } subp=subpolyn(pa,pb);//多项式相减 printpolyn(subp);//打印输出 break; case 4: if(pa==NULL) { cout<<"请先创建两个一元多项式!"< break; } mulp=mulpolyn(pa,pb);//多项式相乘