数据结构课设一元多项式乘法.docx
- 文档编号:13391258
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:16
- 大小:148.61KB
数据结构课设一元多项式乘法.docx
《数据结构课设一元多项式乘法.docx》由会员分享,可在线阅读,更多相关《数据结构课设一元多项式乘法.docx(16页珍藏版)》请在冰点文库上搜索。
数据结构课设一元多项式乘法
学号11710105
数据结构A课程设计
设计说明书
一元多项乘法
起止日期:
2013年12月30日至2014年1月3日
学生姓名
班级
11计算机1班
成绩
指导教师(签字)
计算机系
2014年1月3日
课程设计任务书
2013—2014学年第一学期
计算机系计算机科学与技术专业11计算机1班级
课程设计名称:
数据结构A课程设计
设计题目:
一元多项式乘法
完成期限:
自2013年12月30日至2014年1月3日共1周
设计依据、要求及主要内容(可另加附页):
一元多项式乘法
1)问题描述
已知A(x)=a0+a1x+a2x2+……+anxn和B(x)=b0+b1x+b2x2+……+bmxm,并且在A(x)和B(x)中指数相差很多,求A(x)=A(x)*B(x)。
2)基本要求
(1)设计存储结构表示一元多项式;
(2)设计算法实现一元多项式乘法;
指导教师(签字):
教研室主任(签字):
批准日期:
2013年12月30日
一、设计目的
熟悉各种数据结构和运算,会使用数据结构的基本操作解决一些实际问题。
二、设计要求
在本课程设计过程中要求学生:
(1)重视课程设计环节,用严谨、科学和踏实的工作态度对待课程设计的每一项任务;
(2)按照课程设计的题目要求,独立地完成各项任务,严禁抄袭;凡发现抄袭,抄袭者与被抄袭者皆以零分计入本课程设计成绩。
凡发现实验报告或源程序雷同,涉及的全部人员皆以零分计入本课程设计成绩。
(3)认真编写课程设计报告。
课程设计报告的书写格式要求见附录2。
三、设计步骤
1、问题分析和任务定义;
2、数据类型和系统设计;
3、编码实现和静态检查;
4、上机调试;
5、总结和整理课程设计报告。
四、设计内容
1、需求分析
1)程序的功能:
能够按照指数降序建立并输出多项式,并且能够完成多项式相加相乘并输出结果。
2)输入输出的要求:
输入的系数为float型,输入的指数为int型。
3)测试数据:
A:
x^2+2x^3+3x^4
B:
2X^2+3X^4+X^5+4X^6
2、总体设计
(1)流程图
YES
NO
(2)存储结构说明
coef
exp
next
定义:
structNode
{
floatcoef;//系数
intexp;//指数
Node*next;
};
3、详细设计
乘法模块功能实现:
voidMUL(LinkList&A,LinkListB)
{
Node*p,*q,*n,*head,*r,*temp,*m,*pre,*qre
intexp;//定义整型指数
floatcoef;//定义浮点型系数
LinkListC;
head=C.first;
r=head;//临时变量,为后移指针做准备
pre=A.first;
p=pre->next;
while(p!
=NULL)
{
LinkListD;
temp=D.first;
m=temp;
qre=B.first;
q=qre->next;
while(q!
=NULL)
{
n=newNode;//建立新节点
exp=p->exp+q->exp;//进行指数相加操作
coef=p->coef*q->coef;////进行系数相乘操作
n->coef=coef;//赋值新节点的系数域
n->exp=exp;//赋值新节点的指数域
m->next=n;//链接节点至头结点,构成链表
m=m->next;//后移指针,为下一节点做准备
q=q->next;//控制B链表下一项
}
p=p->next;//控制A链表下一项
m->next=NULL;//链表尾置空
Add(C,D);
}
C.PrintList();
}
4、调试分析与测试
1.主要问题
独立测试各个模块的功能时发现在创建链表后和另一个进行运算后多余的存储单元没有释放而造成内存的泄露,还有对运算时结束条件掌握不透彻导致没有按计划去执行并结束,比如在用For循环以及while循环时没有正确的判断指针的移动与结束条件得不到预期的结果。
调试时误用么有初始化的变量。
在主函数中对其它函数的调用没有一个清晰的思路,使程序很混乱。
对非法控制的操控不够完善。
2.算法时空分析
该程序的实现使用单链表实现的,所以时间复杂度和空间复杂度主要来自链表的操作,都是O(n)。
5、核心源程序清单和执行结果
头文件:
#include
usingnamespacestd;
structNode
{
floatcoef;//系数
intexp;//指数
Node*next;
};
classLinkList
{
public:
LinkList();//无参构造函数,建立只有头结点的空链表
LinkList(intn);//有参构造函数,建立有n个元素的单链表
~LinkList();//析构函数
voidPrintList();//遍历操作,按序号依次输出各元素
friendvoidAdd(LinkList&A,LinkListB);
friendvoidMUL(LinkList&A,LinkListB);
friendvoidSort(LinkList&A);
private:
Node*first;//单链表的头指针
};
源文件:
#include"a.h"
LinkList:
:
LinkList()//无参构造函数
{
first=newNode;//生成头结点
first->next=NULL;//头结点的指针域置空
}
LinkList:
:
LinkList(intn)//有参构造函数
{
Node*r,*s;
first=newNode;//生成头结点
r=first;//尾指针初始化
for(inti=0;i { s=newNode; cout<<"请输入第"< "; cin>>s->coef>>s->exp; r->next=s;r=s;//将结点s插入到终端结点之后 } r->next=NULL;//单链表建立完毕,将终端结点的指针域置空 } voidSort(LinkList&A)//冒泡排序法 { Node*p=A.first->next; Node*q,*s; floatcoef;intexp; while(p->next! =NULL) { s=p; q=s>next; while(q! =NULL) { if(q->exp<=s->exp) { s=q; q=q->next; } else { q=q->next; } } //交换s指向的值和首项的值 if(p==s) { p=p->next; } else { coef=p->coef;exp=p->exp; p->coef=s->coef;p->exp=s->exp; S->coef=coef;s->exp=exp; p=p->next; } } } LinkList: : ~LinkList()//析构函数 {} voidLinkList: : PrintList() { /*Node*p=first->next;//工作指针p初始化 while(p! =NULL) { cout< p=p->next; } cout< Node*p=first->next; if(p==NULL) { cout<<"0\n"; return; } else { do { if(p->coef>=0&&p->exp! =0) cout<<"+"< if(p->coef>=0&&p->exp==0) cout<<"+"< if(p->coef<0&&p->exp! =0) cout< if(p->coef<0&&p->exp==0) cout< p=p->next; }while(p! =NULL); cout< } #include"a.h"//引用单链表类的声明和定义 voidAdd(LinkList&A,LinkListB) { Node*pre,*qre,*p,*q,*v; pre=A.first; p=pre->next; qre=B.first; q=qre->next; while(p! =NULL&&q! =NULL) { //第一种情况 if(p->exp { pre=p; p=p->next; } //第二种情况 elseif(p->exp>q->exp) { v=q->next; pre->next=q; q->next=p; q=v; } //第三种情况 else { p->coef=p->coef+q->coef; if(p->coef==0) {//p系数为,前后连接,删除当前节点 pre->next=p->next; deletep; p=pre->next; } else { pre=p; p=p->next; } qre->next=q->next; deleteq; q=qre->next; } } if(q! =NULL) pre->next=q; deleteB.first; } voidMUL(LinkList&A,LinkListB) { Node*p,*q,*n,*head,*r,*temp,*m,*pre,*qre; intexp;//定义整型指数 floatcoef;//定义浮点型系数 LinkListC; head=C.first; r=head;//临时变量,为后移指针做准备 pre=A.first; p=pre->next; while(p! =NULL) { LinkListD; temp=D.first; m=temp; qre=B.first; q=qre->next; while(q! =NULL) { n=newNode;//建立新节点 exp=p->exp+q->exp;//进行指数相加操作 coef=p->coef*q->coef;////进行系数相乘操作 n->coef=coef;//赋值新节点的系数域 n->exp=exp;//赋值新节点的指数域 m->next=n;//链接节点至头结点,构成链表 m=m->next;//后移指针,为下一节点做准备 q=q->next;//控制B链表下一项 } p=p->next;//控制A链表下一项 m->next=NULL;//链表尾置空 Add(C,D); } C.PrintList(); } voidmain() { intn; cout<<"请输入第一个多项式的项数: "; cin>>n; LinkListA(n); Sort(A); cout<<"多项式A: "; A.PrintList(); cout<<"请输入第二个多项式的项数: "; cin>>n; LinkListB(n); Sort(B); cout<<"多项式B: "; B.PrintList(); cout<<"A*B="; MUL(A,B); } } 6、心得体会 通过用单链表来解决问题让我收获很大,对链表的构建更加熟练对链表的向前推进把握的更加准确,在调试代码的时候曾遇到很大的问题但是通过借鉴问别人解决了问题,自己也收获了很多。 在设计算法的时候由于过分依赖书上的例子,导致了很多不必要的麻烦,例如在建立链表是设立了头指针导致之后运用相关指针的时候搞不清指针的移动出现了数据重复输出和输出不完全的状况,不能很好的实现算法。 7、参考文献 1王红梅数据结构清华大学出版社 2王红梅数据结构学习辅导与实验指导清华大学出版社 3谭浩强C++程序设计清华大学出版社
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构课设 一元多项式乘法 数据结构 一元 多项式 乘法