一元多项式运算课程设计

《一元多项式运算课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学号：***课程设计题目一元多项式运算教学院计算机学院专业计算机科学与技术班级09计科（1）班姓名***指导教师祁文青2010年12月22日29目录1课程设计任务书…………………………………………………………………………32需求分析…………………………………………………………………………………93概要设计………………………………………………………………………………10总体设计思路……………………………………………………………………………10主函数和子程序…………………………………………………………………………11创建链表……………………………

2、……………………………………………………12实现排序…………………………………………………………………………………125调试报告………………………………………………………………………………136改进意见及收获体会…………………………………………………………………207程序清单………………………………………………………………………………218主要参考文献…………………………………………………………………………29291．课程设计应达到的目的该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。学生通过

3、课程设计加深理解课堂教学内容，使学生在课程设计中逐步提高程序设计能力、算法分析能力、和调试能力；培养学生解决实际问题的能力，自主学习和独立创新的精神。提高学生的科技论文写作能力。2．课程设计题目及要求题目：一元多项式相加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）设计算法实现一元多项式相加，相减，相乘运算；（3）要求输出结果的升幂和降幂两种排列情况

4、（4）分析算法的时间复杂度和空间复杂度。3．设计思想   一元多项式求和实质上是合并同类项的过程，其运算规则为：（1）若两项的指数相等，则系数相加；（2）若两项的指数不等，则将两项加在结果中。     一元多项式A(x)=a0+a1x+a2x2+……+anxn由n+1个系数唯一确定，因此，可以用一个线性表(a0，a1，a2，……，an)来表示，每一项的指数i隐含在其系数ai的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多零元素。一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。

5、这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。     由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。结点结构如图所示。29    coefexpnext其中，coef：系数域，存放非零项的系数； exp：指数域，存放非零项的指数；next：指针域，存放指向下一结点的指针。     将两个一元多项式用两个单链表存储后，如何实现二者相加呢？     设两个工作指针p和q，分别指向两个单链表的开始结点。通过对结点p的指数域和

6、结点q的指数域进行比较进行同类项合并，则出现下列三种情况：     （1）若p->expexp，则结点p应为结果中的一个结点；     （2）若p->exp>q->exp，则结点q应为结果中的一个结点，将q插入到第一个链表中结点p之前；     （3）若p->exp=q->exp，则结点p与结点q为同类项，将q的系数加到p的系数上。若相加结果不为0，则结点p应为结果中的一个结点，同时删除结点q；若相加结果为0，则表明结果中无此项，删除结点p和结点q。     293．课程设计任务及工作量的要求〔包括课程设计计算说明书、图纸、实物样品等要求〕（

7、1）分析问题，给出数学模型，设计相应的数据结构。（2）算法设计在已经选择好数据结构的前提下，为解决问题设计算法。²确定所需模块对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。²各子模块功能描述给出主要模块的算法描述，用流程图或伪代码表示。²模块之间的调用关系给出算法各模块之间的关系图示（3）源程序清单（草稿）为了提高工作效率，充分利用上机调试程序的时间，要求学生在上机之前给出源程序清单。（4）用测试数据去验证算法及程序的正确性正序、

8、逆序、随机数（5）算法分析经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度。（6）提供的主程序