《单链表表示多项式相乘实习报告》由会员分享，可在线阅读，更多相关《单链表表示多项式相乘实习报告（10页珍藏版）》请在金锄头文库上搜索。
1、 实习报告 1实习题： 请写出计算两个以单链接表表示的多项式相乘的程序。 1.设计：因为进行插入删除时，有头结点的单链表的实现会更方便，所以采用带头结点的单链表， 一个单链表代表一个多项式，每个结点代表多项式的一个因子，每个结点都有两个数据和 一个指针，数据分别代表每个因子的系数和指数。（1）存储结构：结点类：class Listnode friend class List;friend ostream private:Listnode* head;/point to the head of the list Listnode* current;/point to the current no
2、de public: List()head = new Listnode();current = head;/constructor List()Makeempty();delete head;/析构函数int Isempty()return head-next = NULL;/if the list is empty return 1,else rerurn 0void First()current=head-next;/make current point to the first nodevoid operator +() if (current!=NULL) current=curre
3、nt-next; /make current point to the next nodevoid operator +(int)operator+();int Isfull()/the list is generally unable to be fullvoid Makeempty();/clear the list int Find(const int/if (x,y) is in the list,return 1void Insert(const int/insert a node to the list whose element is (x,y),then current poi
4、nt to itvoid Delete(const int/delete the node whose element is (x,y) const List/copy the right list to the left one List/get the sum of two listsList/get the multiply of the two lists;（2）算法思想：设多项式 A，B，A 有 m 项，B 有 n 项，用 A 中的每一项乘以 B 得到 m 个 n 项式，然后这 m 个 n 项式相加，即得到 A 与 B 相乘的结果。 （3）程序调用关系：此次实习的主程序比较简单，只涉
5、及类的成员函数之间的调用。 （4） 算法实现框架： 定义两个单链 表存储两个多 项式依次让用户输 入两个多项式 的数据将数据存入到 两个单链表中2.用户手册：按照屏幕的提示依次输入两个多项式，请务必按照提示的要求输入，然后程序会计算两个 多项式的和，然后输出计算结果。 3.调试报告：（1）时间复杂度分析： 设两多项式为 A，B，分别有 m，n 项，则进行乘法时，先是 A 中每一项和 B 各项相乘，得 到 m 个 n 项式，此过程时间复杂度与问题规模无关，然后 m 个 n 项式相加，第一次加的时 候是两个 n 项式相加，插入次数介于 n 和 2n 之间，所以时间复杂度为 O（n） ，同理，后面
6、的相加也是时间复杂度为 O(n)，所以 m-1 次相加的时间复杂度也是 0（n） ，由于没涉及到 删除的操作，所以综合来看，时间复杂度即为 0(n).（2）算法改进：如果采用迭代器的话也许对链表进行操作起来会更加方便。如果用模板就可以处理 数据是其他类型时的情况。还可以加一个排序的操作，这样就能处理用户输入的数据不是 以升幂的形式排列时的情况。我的程序要求用户输入的数据必须以特定形式，这样的形式 不符合人的视觉习惯，但由于对处理系数为 1 时的情况没有解决方法，所以放弃了，如果 输入方式更符合数学习惯，则会更加友好。但这些都对时间复杂度没什么影响。只是使程 序更加健壮。 4.附录：源程序清单：
7、/Listnode.Cpp#include“Listnode.h“ #includeostream Listnode* temp2;/定义两个 listnode 型的指针用作清空链表 for(temp1=head-next;temp1 != NULL;temp1=temp2)/开始循环 temp2=temp1-next;/temp2 指向将后面部分链表 delete temp1;/删除当前所指结点 current=head;/当前指针指向头结点 head-next=NULL;/头结点中指针指向空int List:Find(const int/如果链表为空则返回 0，查找失败 int flag=
8、0;/储存该函数的返回值 Listnode* ptr=head-next;/定义指针指向首结点 for(;ptr!=NULL;ptr=ptr-next)/开始查找 if (ptr-exponent=y)flag=1;/找到则当前指针指向该结点，并标志查找成功 return flag;/返回返回值，0 为查找失败，1 为查找成功void List:Insert(const intcurrent = (current-next) = p;/插入该结点，current 指向插入的结点void List:Delete(const int delete current; current=p;/删除当前节
9、点，current 指向后一结点List/定义一临时链表Listnode* p1 = head-next; Listnode* p2 = t.head-next;/定义两个指针分别指向相加的链表的首结点 while(p1 != NULL) p1=p1-next; p2=p2-next; else if (p1-exponent) exponent)/两结点指数不同，则小的指数所 在结点插入到 templist 中，然后当前指针后移templist.Insert(p1-coefficient,p1-exponent); p1=p1-next; else cout“coefficient,p2-e
10、xponent); p2=p2-next; /继续循环比较 / 循环结束 if (p1=NULL)/如果 p1 所指链表较短则将 p2 所指链表剩余部分接到 templst 后面 for(;p2 != NULL;p2=p2-next)templist.Insert(p2-coefficient,p2-exponent); else/如果 p2 所指链表较短则将 p1 所指链表剩余部分接到 templst 后面 for(;p1 != NULL;p1=p1-next)templist.Insert(p1-coefficient,p1-exponent); *this = templist;/ 赋值
11、return *this; List/临时链表，储存 this 指向的链表的某一因子和 list 链表乘积得 到的新链表templist1=t; List templist2;/临时链表，储存 this 指向的链表的前 n 项因子和 list 链表的乘积 得到的新链表，最终为两链表的乘积 Listnode*ptr1=head-next;/临时指针指向左乘积项的首结点 Listnode*ptr2;/临时指针指向右乘积项的首结点 for(;ptr1!=NULL;ptr1=ptr1-next)/开始循环 for(ptr2=templist1.head-next;ptr2!=NULL;ptr2=ptr
12、2-next) ptr2-exponent = (ptr2-exponent) + (ptr1-exponent); ptr2-coefficient = (ptr2-coefficient) * (ptr1-coefficient);/左 乘积项的每一项分别和右乘积项相乘 templist2=templist2 + templist1;/将每一次乘积的结果加到 templist2 中templist1=t;/每次新的循环开始前将 templist1 返回到 list，再和左乘积项的 下一项相乘 /循环结束 *this = templist2;/赋值给*thisreturn *this; co
13、nst List/如果两链表相同则直接返回 Makeempty();/ 将所要被赋值的链表清空 Listnode*ptr1=t.head-next;/定义一临时指针指向 t 的首结点 while(ptr1!=NULL)/循环赋值 this-Insert(ptr1-coefficient,ptr1-exponent); ptr1=ptr1-next; /循环结束return *this; ostreamint temp1,temp2,i=0,flag=0,j=0;/temp1 接受系数，temp2 接受指数，i,j 为控制 变量,flag 用于处理负数char temp;/temp 每次接受单个
14、输入的字符while(temp=input.get()!=*)/每次得到一个字符，以“*”为结束符/cout=0;k-) a=(pk-1+1);b+=a*pow(10,j-1-k);/将数组中存的字符转化成 Int 型数字if(flag)b=b*(-1);/如果是负数则乘-1flag=0;if(i%2) temp2=b;/将指数给 temp2 t.Insert(temp1,temp2);/每次得到一个指数说明得到了一个结点， 就可以将其插入到链表中 elsetemp1=b;/将系数给 temp1i+;j=0;/控制变量还原以进行下次循环delete p;/删除空间并重新分配p=new char
15、10; /end else /end whiledelete p; return input; /main.cpp #include #include“List.h“ #include“Listnode.h“ #include #includeint main() couta;/接受用户的输入存入多项式coutb;/接受用户输入并存入多项式 cout(a*b)endl;/ 计算两个多项式的乘积并输出return 0;/结束程序测试数据：输入第一个多项式（-1，-1） ， （23，1） ， （-2，2）输入第二个多项式（48，1） ， （3，200） 运行结果：Please input a polynomial in this form:(3,4),(4,9)* （only int is allowed）The former one of the twonumbers in the parentheses is the coefficient and the latter one is the exponent.The exponent must be in a rising order!Please remember to add
