资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
实习报告 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 node 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=current-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 point 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)程序调用关系:此次实习的主程序比较简单,只涉及类的成员函数之间的调用。 (4) 算法实现框架: 定义两个单链 表存储两个多 项式依次让用户输 入两个多项式 的数据将数据存入到 两个单链表中2.用户手册:按照屏幕的提示依次输入两个多项式,请务必按照提示的要求输入,然后程序会计算两个 多项式的和,然后输出计算结果。 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)算法改进:如果采用迭代器的话也许对链表进行操作起来会更加方便。如果用模板就可以处理 数据是其他类型时的情况。还可以加一个排序的操作,这样就能处理用户输入的数据不是 以升幂的形式排列时的情况。我的程序要求用户输入的数据必须以特定形式,这样的形式 不符合人的视觉习惯,但由于对处理系数为 1 时的情况没有解决方法,所以放弃了,如果 输入方式更符合数学习惯,则会更加友好。但这些都对时间复杂度没什么影响。只是使程 序更加健壮。 4.附录:源程序清单:/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=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;/删除当前节点,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-exponent); 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;/ 赋值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=ptr2-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; const 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 每次接受单个输入的字符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 char10; /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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号