定义相乘后的数据 N p->exp>=0 Y 存储某段相乘后的数据 N q->exp=0 Y 生成新节点插入n后 将temp加到result上 q指向表头结点的后继结点 N q!=NULL Y 删除原对象的所有数据 将result加到当前对象上 PolyMul(Polynominal& r)
3. 算法分析
多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空间复杂程度为O（n）。
四、 程序代码
void Polynominal::PolyAdd(Polynominal& r) {
Term *q, *q1 = theList, *p; //q1指向表头结点
p = r.theList->link; //p指向第一个要处理的结点 q = q1->link; //q1是q的前驱，p和q就指向两个当前进行比较的项
while (p != NULL && p->exp >= 0)//对r的单循环链表遍历，知道全部结点都处理完 {
while (p->exp < q->exp) //跳过q->exp大的项 {
q1 = q; q = q->link; }
if (p->exp == q->exp) //当指数相等时，系数相加 {
q->coef = q->coef + p->coef;
if (q->coef == 0) //若相加后系数为0，则删除q {
q1->link = q->link; delete(q);
q = q1->link; //重置q指针 } else {
q1 = q; //若相加后系数不为0，则移动q1和q q = q->link; } }
else //p>exp>q->exp的情况
q1 = q1->InsertAfter(p->coef, p->exp); //以p的系数和指数生成新结点，插入q1后
p = p->link; } }
void Polynominal::PolyMul(Polynominal& r) {
Polynominal result; //定义相乘后的数据 Term *n = result.theList; //n指向result的头结点
n = n->InsertAfter(0, 0); //在result的头结点后插入新结点，系数指数均为0
Term *p = r.theList->link; //p指向第一个要处理的结点 while(p->exp >= 0) //对r的单循环链表遍历
{
Polynominal tmp; //存储某段相乘后的数据 Term *m = tmp.theList; //m指向tmp的头结点
Term *q = theList->link; //q指向表头结点的后继结点
while(q->exp >= 0) //对当前对象的单循环环链表遍历 {
m = m->InsertAfter((p->coef)*(q->coef), (p->exp) + (q->exp)); //生成新结点插入n后
q = q->link; }
result.PolyAdd(tmp); //将temp加到result上 p = p->link; }
Term *q = theList->link; //q指向表头结点的后继结点 while(q != NULL) //删除原对象的所有数据 {
theList->link = q->link; delete q;
q = theList->link; }
q = theList;
q = q->InsertAfter(0, 0);
PolyAdd(result); //将result加到当前对象上 }
五、 测试和调试
1. 测试用例和结果
1) 选择1,计算多项式相加
2) 分别输入系数和项数3 2,4 6,9 7,如图所示
3) 得到相加的多项式如图
4) 选择2,计算多项式相乘
5) 输入系数和项数4 2,6 3,,得到多项式一,如图
6) 再次输入系数和项数7 3,得到多项式二以及多项一和多项式二的乘
积
2. 结果分析
1) 程序能够正确实现多项式的相加以及相乘
2) 但是程序无法实现不能加法乘法混用，下一步改进方向是实现加法
乘法混用，是计算更加简便
六、 实习小结
这个实验的重难点都在于正确灵活使用，大部分代码在书上都有提供，真正的操作重点在于理解这些代码的意义和使用方法。通过这次课程设计，使我对数据结构有了初步的清晰了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中，我认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我也认识到了自己的薄弱之处，如对c++和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、