一元稀疏多项式计算器(19页).doc
-一元稀疏多项式计算器-第 18 页云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩120111120220111120 指导教师： （签名）学期：2012秋季学期 任课教师: 实验题目: 一元稀疏多项式计算器 小 组 长: 联系电话: 电子邮件: 完成提交时间：2012 年 11 月 10 日云南大学软件学院2012学年 秋季 学期数据结构实验成绩考核表学号： 20111120 姓名： 本人承担角色： 算法设计 整体流程控制 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号： 20111120 姓名： 本人承担角色： 函数实现 整体流程控制 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)多项式计算器的呈现方式是用控制台程序呈现，；多项式的加减乘以及求导的函数中利用链表保存头结点以及循环结构保存和输出数据；还有利用一个简单的降序排列的函数，在输出时更加明了。二、【实验设计(Design)】(20%)在头文件中申明变量，源文件中创建指数和系数的指针的头结点，并为此申请空间。首先考虑指数为0,1和系数为0,1时的特殊情况的表示；然后利用SORT函数对输出时进行降序排列；其次就是加减乘以及求导函数的实现；最后是一个输出界面的设计。三、【实现描述（Implement）】(30%)/-函数原型说明-typedef struct Nodedouble xishu;int zhishu;/数据域/int data;struct Node* pnext;/指针域Node,*pNode;pNode phead=(pNode)malloc(sizeof(Node);/创建头节点pNode creat_list(void);创建链表void traverse_list(pNode phead);/遍历链表pNode sort(pNode phead);/对链表进行降序排列pNode add(pNode phead1,pNode phead2)；/两个多项式相加pNode hebing(pNode phead)/合并同类项pNode multi(pNode phead1,pNode phead2)；/多项式相乘pNode sub(pNode phead1,pNode phead2)；/多项式相减/多项式求导没有声明和定义函数，而是直接卸载程序里了/-关键操作的实现-1.对链表的声明和定义和对创建函数的定义。 #include "stdafx.h"#include "cpxNum.h"typedef struct Nodedouble xishu;int zhishu;/数据域/int data;struct Node* pnext;/指针域Node,*pNode;pNode creat_list(void)int len;int i;/int val;int zhishu;double xishu;pNode phead=(pNode)malloc(sizeof(Node);/分配了一个不存在有效数据的头结点pNode ptail=phead;ptail->pnext=NULL;if(phead=NULL)cout<<"分配失败<<endl;exit(-1);cout<<"请输入想输入多项式的项数"<<endl;cin>>len;for(i=0;i<len;i+)cout<<"请?输º?入¨?第̨²"<<i+1<<"个?项?的Ì?系¦Ì数ºy的Ì?值¦Ì"<<endl;cin>>xishu;cout<<"请?输º?入¨?第̨²"<<i+1<<"个?项?的Ì?指?数ºy的Ì?值¦Ì"<<endl;cin>>zhishu;pNode pnew=(pNode)malloc(sizeof(Node);if(pnew=NULL) cout<<"分¤?配?失º¡ì败㨹"<<endl; exit(-1);pnew->xishu=xishu;pnew->zhishu=zhishu;ptail->pnext=pnew;pnew->pnext=NULL;ptail=pnew;phead->zhishu=len;return phead;2.对多项式遍历，排序，同类项合并的定义1. 多项式的遍历/将多项式分为第一项和其余项两部分考虑，另外考虑指数=0，指数=1，系数=1，系数=0等情况。void traverse_list(pNode phead)pNode p=phead->pnext; if(p->zhishu=0)cout<<p->xishu;elseif(p->zhishu=1)cout<<"("<<p->xishu<<")"<<"x"else if(p->xishu=1) cout<<"x"<<""<<p->zhishu; elseif(p->xishu=0)cout<<"0"elsecout<<"("<<p->xishu<<")"<<"x"<<""<<p->zhishu;p=p->pnext;while(p) if(p->zhishu=0)cout<<"+"<<p->xishu;elseif(p->zhishu=1)cout<<"x+"<<"("<<p->xishu<<")"else if(p->xishu=1) cout<<"+"<<"x"<<""<<p->zhishu; elseif(p->xishu=0)cout<<"+0"elsecout<<"+"<<"("<<p->xishu<<")"<<"x"<<""<<p->zhishu;p=p->pnext; cout<<endl;return;2. 排序操作。/通过冒泡排序对多项式进行降序排列。pNode sort(pNode phead)int i,j;float xishu;int zhishu;pNode p,q,f;f=phead;int len=phead->zhishu;for(i=0,p=phead->pnext;i<len-1;i+,p=p->pnext)for(j=i+1,q=p->pnext;j<len;j+,q=q->pnext)if(p->zhishu<q->zhishu)xishu=p->xishu;zhishu=p->zhishu ;p->xishu=q->xishu;p->zhishu=q->zhishu;q->xishu=xishu; q->zhishu=zhishu;return f;3. 合并排序/通过检查将同类型合并，在加法，减法和乘法函数中会用到pNode hebing(pNode phead)pNode r,q,p,Q;for(q=phead->pnext;q!=NULL;q=q->pnext)/合?并¡é同ª?类¤¨¤项?for(p=q->pnext,r=q;p!=NULL;)if(q->zhishu=p->zhishu)/指?数ºy相¨¤等̨¨ 系¦Ì数ºy相¨¤加¨®q->xishu=q->xishu+p->xishu;r->pnext=p->pnext;Q=p;p=p->pnext;delete Q;/释º¨ª放¤?pelser=r->pnext;p=p->pnext;return phead; 3.多项式的加，减，乘，求导，x代入值的实现1. 多项式的加法/创建一个新链表存储新的多项式，开始对phead1和phead2进行扫描，指数相同就相加。pNode add(pNode phead1,pNode phead2) pNode p1,p2,pTail,pnew; pNode phead3=(pNode)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; sort(phead1); sort(phead2); p1=phead1->pnext; p2=phead2->pnext; int i=0; while(p1&&p2) if(p1->zhishu>=p2->zhishu) if(p1->zhishu=p2->zhishu) pnew=new Node; pnew->xishu=p1->xishu+p2->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; p2=p2->pnext; else pnew=new Node; pnew->xishu=p1->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; else pnew=new Node; pnew->xishu=p2->xishu; pnew ->zhishu=p2->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew;p2=p2->pnext; if(p1=NULL) pTail->pnext=p2; if(p2=NULL) pTail->pnext=p1; return phead3;2. 多项式的减法/道理与多项式加法相同，但是指数相同时，系数相减。pNode sub(pNode phead1,pNode phead2)/减?法¤¡§函¡¥数ºy pNode p1,p2,pTail,pnew; pNode phead3=(pNode)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; sort(phead1); sort(phead2); p1=phead1->pnext; p2=phead2->pnext; while(p1&&p2) if(p1->zhishu>=p2->zhishu) if(p1->zhishu=p2->zhishu) pnew=new Node; pnew->xishu=p1->xishu-p2->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; p2=p2->pnext; else pnew=new Node; pnew->xishu=p1->xishu; pnew ->zhishu=p1->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p1=p1->pnext; else pnew=new Node; pnew->xishu=-(p2->xishu); pnew ->zhishu=p2->zhishu; pTail->pnext=pnew; pnew->pnext=NULL; pTail=pnew; p2=p2->pnext; if(p1=NULL) pTail->pnext=p2; if(p2=NULL) pTail->pnext=p1; return phead3;3. 多项式乘法/相当于加法的多次操作。进行嵌套循环解决此问题pNode multi(pNode phead1,pNode phead2)/乘?法¤¡§函¡¥数ºy int i,j;/i,j分¤?别Àe保À¡ê存ä?了¢?两¢?个?链¢¡ä表À¨ª的Ì?长¡è度¨¨ pNode p1,p2,pTail; pNode phead3=(pNode)malloc(sizeof(Node); pTail=phead3; pTail->pnext=NULL; p1=phead1->pnext; while(p1) p2=phead2->pnext; while(p2) pNode q=(pNode)malloc(sizeof(Node); q->xishu=p1->xishu*p2->xishu; q->zhishu=p1->zhishu+p2->zhishu; q->pnext=phead3->pnext; phead3->pnext=q; phead3=q; p2=p2->pnext; p1=p1->pnext;return pTail;4. 多项式求导/不停扫描多项式，对其进行求导运算，直至p=NULLphead=creat_list(); p=phead->pnext; while(p!=NULL) p->xishu=p->xishu*p->zhishu; p->zhishu=p->zhishu-1; p=p->pnext;5. x赋值求结果。 p=phead1->pnext;cout<<"请?输º?入¨?x的Ì?值¦Ì"<<endl;cin>>x;sum=0.0;y=1.0;while(p)for(;p->zhishu>0;p->zhishu-)y=y*x;sum=sum+y*(p->xishu);p=p->pnext;y=1.0;cout<<"结¨¢果?值¦Ì为a"<<endl;cout<<sum;四、【测试结果（Testing）】(10%)加法测试：正确减法测试：正确乘法测试：正确求导测试：正确四、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）1. 实验时，一个小组的同学应该由一人操作，其他人一起来写程序，这样可以避免由于不同的同学的编程风格的差异而导致一些很难发现的错误，从而浪费很多不必要的时间2. 实验之前一定要想好算法，不要盲目的直接就敲程序，这样不仅会使效率低下还会使程序极易出现难以察觉的逻辑错误，最好在敲程序之前画流程图将算法分析清楚，确保无误后再敲程序3. 同学间的交流很重要，不同小组的同学也应该多交流，这样不仅可以大家之间互相取长补短，共同进步，还可以避免很多错误的出现五、【项目运作描述（Operate）】(10%)（本部分应包括：项目的成本效益分析，应用效果等的分析。）这个实验花时间比较长，在做实验的过程中我们也遇到了很多困难，为一个bug而纠结了很久，但是通过和同学的交流讨论，我们发现并解决了问题。在克服困难的过程中，我们学到了很多的东西，也积累了很多的经验，可以为以后的学习和实验中打下基础。我们的程序基本实现了实验指导上的要求，但是对于健壮性的考虑还不够，我们一定会在以后的实验中，好好努力，尽最大的努力将程序完善六、【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）int main()int choose;double x,sum,y; pNode phead1=NULL; pNode phead2=NULL; pNode p,p2,phead,phead3=NULL;/pNode creat_list(void);cout<<"*"<<endl;cout<<" 欢?迎®-使º1用®?我¨°们?的Ì?多¨¤项?式º?计?算?器¡Â "<<endl;cout<<" 请?选?择?你?想?要°a的Ì?操¨´作Á¡Â "<<endl;cout<<" 1.加¨®法¤¡§运?算? 2.减?法¤¡§运?算? "<<endl;cout<<" 3.乘?法¤¡§运?算? 4.求¨®导Ì?运?算? "<<endl;cin>>choose;switch(choose) case 1: phead1=creat_list(); /phead2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?个?多¨¤项?式º?：êo"<<endl; traverse_list(phead1);cout<<"整?理¤¨ª后¨®的Ì?第̨²二t个?多¨¤项?式º?：êo"<<endl; traverse_list(phead2);/add(phead1,phead2); phead1=add(phead1,phead2);/sort(phead1); phead1= hebing(phead1); cout<<"最Á?终?的Ì?结¨¢果?：êo"<<endl;traverse_list(phead1); break; case 2: phead1=creat_list(); /phead2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?个?多¨¤项?式º?：êo"<<endl; traverse_list(phead1);cout<<"整?理¤¨ª后¨®的Ì?第̨²二t个?多¨¤项?式º?：êo"<<endl; traverse_list(phead2); phead1=sub(phead1,phead2); phead1= hebing(phead1); cout<<"最Á?终?的Ì?结¨¢果?：êo"<<endl; traverse_list(phead1); break; case 3: phead1=creat_list(); /phead2=creat_list(); sort(phead1); phead2=creat_list(); sort(phead2); cout<<"整?理¤¨ª后¨®的Ì?第̨²一°?个?多¨¤项?式º?：êo"<<endl; traverse_list(phead1);cout<<"整?理¤¨ª后¨®的Ì?第̨²二t个?多¨¤项?式º?：êo"<<endl; traverse_list(phead2); phead1=multi(phead1,phead2); phead1= hebing(phead1);cout<<"最Á?终?的Ì?结¨¢果?：êo"<<endl; traverse_list(phead1); break; case 4: phead1=creat_list(); p=phead1->pnext; cout<<"您¨²输º?入¨?的Ì?是º?：êo"<<endl; traverse_list(phead1); while(p!=NULL) p->xishu=p->xishu*p->zhishu; p->zhishu=p->zhishu-1; p=p->pnext;cout<<"最Á?终?的Ì?结¨¢果?：êo"<<endl; traverse_list(phead1); break; default: cout<<"输º?入¨?错䨪误¨®！ê?"<<endl; break;p=phead1->pnext;cout<<"请?输º?入¨?x的Ì?值¦Ì"<<endl;cin>>x;sum=0.0;y=1.0;while(p)for(;p->zhishu>0;p->zhishu-)y=y*x;sum=sum+y*(p->xishu);p=p->pnext;y=1.0;cout<<"结¨¢果?值¦Ì为a"<<endl;cout<<sum;return 0;
