单链表表示多项式相乘实习报告

1、 实习报告 一实习题： 请写出计算两个以单链接表表示的多项式相乘的程序。 1.设计：因为进行插入删除时，有头结点的单链表的实现会更方便，所以采用带头结点的单链表， 每个结点都有两个数据和一一个单链表代表一个多项式，每个结点代表多项式的一个因子， 个指针，数据分别代表每个因子的系数和指数。 1）存储结构：（ 结点类： class Listnode friend class List; friend ostream private: Listnode* next;/point to the next node int coefficient; int exponent; public: Listn

2、ode(const int /get the next 析构函数 Listnode()/; 单链表类： class List friend ostream private: Listnode* head;/point to the head of the list Listnode* current;/point to the current node public: List()head = new Listnode();current = head;/constructor 析构函数 List()Makeempty();delete head;/ int Isempty()return h

3、ead-next = NULL;/if the list is empty return 1,else rerurn 0 void First()current=head-next;/make current point to the first node void operator +() if (current!=NULL) current=current-next; /make current point to the next node void operator +(int)operator+(); int Isfull()/the list is generally unable

4、to be full void Makeempty();/clear the list int Find(const int/if (x,y) is in the list,return 1 void Insert(const int/insert a node to the list whose element is (x,y),then current point to it void Delete(const int/delete the node whose element is (x,y) const List/copy the right list to the left one

5、List/get the sum of two lists List/get the multiply of the two lists ; （2）算法思想： 设多项式A，B，A有m项，B有n项，用A中的每一项乘以B得到m个n项式，然后这m个n项式相加，即得到A与B相乘的结果。 （3）程序调用关系： 此次实习的主程序比较简单，只涉及类的成员函数之间的调用。 （4） 算法实现框架： 定义两个单链 表存储两个多 项式 依次让用户输 入两个多项式 的数据 将数据存入到 两个单链表中 按行 式相加 将结果输出 用户手册：2. 按照屏幕的提示依次输入两个多项式，请务必按照提示的要求输入，然后程序会计算两

6、个多项式的和，然后输出计算结果。 3.调试报告： （1）时间复杂度分析： 设两多项式为A，B，分别有m，n项，则进行乘法时，先是A中每一项和B各项相乘，得到m个n项式，此过程时间复杂度与问题规模无关，然后m个n项式相加，第一次加的时候是两个n项式相加，插入次数介于n和2n之间，所以时间复杂度为O（n），同理，后面的相加也是时间复杂度为O(n)，所以m-1次相加的时间复杂度也是0（n），由于没涉及到删除的操作，所以综合来看，时间复杂度即为0(n). （2）算法改进： 如果采用迭代器的话也许对链表进行操作起来会更加方便。如果用模板就可以处理数据是其他类型时的情况。还可以加一个排序的操作，这样就能处

7、理用户输入的数据不是以升幂的形式排列时的情况。我的程序要求用户输入的数据必须以特定形式，这样的形式不符合人的视觉习惯，但由于对处理系数为1时的情况没有解决方法，所以放弃了，如果输入方式更符合数学习惯，则会更加友好。但这些都对时间复杂度没什么影响。只是使程序更加健壮。 4.附录： 源程序清单： /Listnode.Cpp #includeListnode.h #include ostream 1，则不输出 else if (node.coefficient!=1)/系数为 if(node.coefficient0) output(node.coefficient); else outputnod

8、e.coefficient; ，则直接跳过，不输出任何东西指数为0 if(node.exponent)/ if (node.exponent!=1) ?畯灴瑵?硜属?潮敤攮灸湯湥? else ?畯灴瑵?硜? return output; /List.cpp #include #includeList.h #includeListnode.h #include #include void List:Makeempty() Listnode* temp1; Listnode* temp2;/定义两个listnode型的指针用作清空链表 for(temp1=head-next;temp1 != NU

9、LL;temp1=temp2)/开始循环 temp2=temp1-next;/temp2指向将后面部分链表 delete temp1;/删除当前所指结点 current=head;/当前指针指向头结点 head-next=NULL;/头结点中指针指向空 int List:Find(const int/如果链表为空则返回0，查找失败 int flag=0;/储存该函数的返回值 Listnode* ptr=head-next;/定义指针指向首结点 for(;ptr!=NULL;ptr=ptr-next)/开始查找 if (ptr-exponent=y) flag=1;/找到则当前指针指向该结点，并

10、标志查找成功 return flag;/返回返回值，0为查找失败，1为查找成功 void List:Insert(const int current = (current-next) = p;/插入该结点，current指向插入的结点 void List:Delete(const int delete current; current=p;/删除当前节点，current指向后一结点 List/定义一临时链表 Listnode* p1 = head-next; Listnode* p2 = t.head-next;/定义两个指针分别指向相加的链表的首结点 while(p1 != NULL) p1

11、=p1-next; p2=p2-next; else if (p1-exponent) exponent)/两结点指数不同，则小的指数所在结点插入到templist中，然后当前指针后移 templist.Insert(p1-coefficient,p1-exponent); p1=p1-next; else coutcoefficient,p2-exponent); p2=p2-next; /继续循环比较 / 循环结束 if (p1=NULL)/如果p1所指链表较短则将p2所指链表剩余部分接到templst后面 for(;p2 != NULL;p2=p2-next) templist.Inse

12、rt(p2-coefficient,p2-exponent); else/如果p2所指链表较短则将p1所指链表剩余部分接到templst后面 for(;p1 != NULL;p1=p1-next) templist.Insert(p1-coefficient,p1-exponent); *this = templist;/ 赋值 return *this; List/临时链表，储存this指向的链表的某一因子和list链表乘积得到的新链表 templist1=t; List templist2;/临时链表，储存this指向的链表的前n项因子和list链表的乘积得到的新链表，最终为两链表的乘积

13、Listnode*ptr1=head-next;/临时指针指向左乘积项的首结点 Listnode*ptr2;/临时指针指向右乘积项的首结点 for(;ptr1!=NULL;ptr1=ptr1-next)/开始循环 for(ptr2=templist1.head-next;ptr2!=NULL;ptr2=ptr2-next) ptr2-exponent = (ptr2-exponent) + (ptr1-exponent); ptr2-coefficient = (ptr2-coefficient) * (ptr1-coefficient);/左乘积项的每一项分别和右乘积项相乘 templist

14、2=templist2 + templist1;/将每一次乘积的结果加到templist2中 templist1=t;/每次新的循环开始前将templist1返回到list，再和左乘积项的下一项相乘 /循环结束 *this = templist2;/赋值给*this return *this; const List/如果两链表相同则直接返回 Makeempty();/ 将所要被赋值的链表清空 Listnode*ptr1=t.head-next;/定义一临时指针指向t的首结点 while(ptr1!=NULL)/循环赋值 this-Insert(ptr1-coefficient,ptr1-exp

15、onent); ptr1=ptr1-next; /循环结束 return *this; ostream t.First();/将当前指针指向首结点 outputy = ; for(;t.current!=NULL;+t) outputGet() != NULL) output + ; output (istream int temp1,temp2,i=0,flag=0,j=0;/temp1接受系数，temp2接受指数，i,j为控制变量,flag 用于处理负数 char temp;/temp每次接受单个输入的字符 while(temp=input.get()!=*)/每次得到一个字符，以“*”为

16、结束符 /couttemp=0;k-) a=(pk-1+1); b+=a*pow(10,j-1-k);/将数组中存的字符转化成Int型数字 if(flag) b=b*(-1);/如果是负数则乘-1 flag=0; if(i%2) temp2 temp2=b;/将指数给 每次得到一个指数说明得到了一个结点，t.Insert(temp1,temp2);/ 就可以将其插入到链表中 else temp1 将系数给 temp1=b;/ i+; 控制变量还原以进行下次循环 j=0;/ delete p;/删除空间并重新分配 p=new char10; /end else /end while delete

17、 p; return input; /main.cpp #include #includeList.h #includeListnode.h #include #include int main() coutPlease input a polynomial in this form:nendl; cout(3,4),(4,9)*nendl; coutThe former one of the twonumbers in the parentheses is the endl; coutcoefficient and the latter one is the exponent.nendl;

18、cout The exponent must be in a rising order!nendl; coutPlease remember to add a * to the endna;/接受用户的输入存入多项式 cout nPlease input another polynomial in this form:nendl; cout(3,4),(4,9)*nendl; coutThe former one of the twonumbers in the parentheses is the coefficient,nendl; cout and the latter one is the exponent.nendl; cout The exponent must be in a rising order!nendl; coutPlease remember to add a * to the endnb;/接受用户输入并存入多项式 cout(a*b)endl;/ 计算两个多项式的乘积并输出 return 0;/结束程序 测试数据：输入第一个多项式（-1，-1），（23，1），（-2，2） 输入第二个多项式（48，1），（3，200） 运行结果： Please input