数据结构实验代码1.doc

数据结构实验参考代码实验一：针对链式或顺序存储的线性表实现指定的操作题1 问题描述：有两个指数递减的一元多项式，写一程序先求这两个多项式的和，再求它们的积。基本要求：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插入、删除操作中指针的正确修改。题2 问题描述：编号为1，2，n的n个人围坐在一圆桌旁，每人持有一个正整数的密码。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，7个人的密码依次是3，1，7，2，4，8，4，则退席的人的编号依次为6，1，4，7，2，3，5。基本要求：用不带表头结点的循环单链表表示围成圆圈的n个人；要求建立此循环单链表；某人离席相当于删除一个结点，要正确设置程序中循环终止的条件和删除结点时指针的修改变化。/实验1.1代码#includeusing namespace std;struct poNodefloat coef;int expn;poNode *next;class Polynomailpublic:Polynomail(int m=0); Polynomail();int Print();int PolynLength();Polynomail &AddPolyn(Polynomail &P2,Polynomail &P3);Polynomail &MultiplyPolyn(Polynomail &P2,Polynomail &P4);private:int InsertpoNode();poNode *first;int main()int m;cout输入多项式P1项数m;Polynomail P1(m);if(P1.PolynLength()!=m)couterror!endl;return -1;cout输入多项式P2项数m;Polynomail P2(m);if(P2.PolynLength()!=m)couterror!endl;return -1;cout多项式P1:;P1.Print();cout多项式P2:;P2.Print();Polynomail P3;P3=P1.AddPolyn(P2,P3);coutP1+P2:;P3.Print();Polynomail P4;P4=P1.MultiplyPolyn(P2,P4);coutP1*P2:;P4.Print();return 0;int Polynomail:InsertpoNode()if(first=NULL)first=new poNode;cout输入系数和指数：first-coef;cinfirst-expn;first-next=NULL;elsepoNode *p=new poNode;poNode *q=first;cout输入系数和指数：p-coef;cinp-expn;poNode *r;while(q-next!=NULL&q-expnexpn)r=q;q=q-next;if(q=first&q-next!=NULL) if(q-expn=p-expn) return -1;p-next=q;first=p;else if(q=first&q-next=NULL)if(p-expnexpn)p-next=q;first=p;else if(p-expnq-expn)q-next=p;p-next=NULL;else return -1;else if(q-next=NULL&q!=first&p-expnq-expn)q-next=p;p-next=NULL;elseif(q-expn=p-expn)return -1;r-next=p;p-next=q;return 0;Polynomail:Polynomail(int m)first=NULL;int i;for(i=0;im;i+)int r=InsertpoNode();if(r=-1) break;int Polynomail:Print()poNode *p=first;coutf(x)=;if(first=NULL) coutNULLendl;while(p!=NULL)coutcoef*xexpn;if(p-next=NULL) coutendl;else coutnext;return 0;Polynomail:Polynomail()poNode *p=first;while(p!=NULL)p=p-next;delete first;first=p;int Polynomail:PolynLength()int i=0;poNode *p=first;while(p!=NULL)p=p-next;i+;return i;Polynomail &Polynomail:AddPolyn(Polynomail &P2,Polynomail &P3)poNode *p=first;poNode *q=P2.first;P3.first=new poNode;poNode *r=P3.first;while(p!=NULL&q!=NULL)if(p-expn=q-expn) r-coef=p-coef+q-coef;r-expn=p-expn;p=p-next;q=q-next;else if(p-expnexpn)r-coef=p-coef;r-expn=p-expn;p=p-next;elser-coef=q-coef;r-expn=q-expn;q=q-next;if(p!=NULL|q!=NULL)r-next=new poNode;r=r-next;else r-next=NULL;while(p!=NULL|q!=NULL)if(p!=NULL)r-coef=p-coef;r-expn=p-expn;p=p-next;elser-coef=q-coef;r-expn=q-expn;q=q-next;if(p!=NULL|q!=NULL)r-next=new poNode;r=r-next;else r-next=NULL;return P3;Polynomail &Polynomail:MultiplyPolyn(Polynomail &P2,Polynomail &P4)poNode *p=first;while(p!=NULL)Polynomail P3;poNode *q=P2.first;P3.first=new poNode;poNode *r=P3.first;r-coef=p-coef*q-coef;r-expn=p-expn+q-expn;q=q-next;while(q!=NULL)r-next=new poNode;r=r-next;r-coef=p-coef*q-coef;r-expn=p-expn+q-expn;q=q-next;r-next=NULL;P4=P4.AddPolyn(P3,P4);p=p-next;return P4;/实验1.2代码#includeusing namespace std;struct numNodeint key;int num;numNode *next;int CreatCircleList(numNode *now,int length);int Loop(numNode *now,int m);int main()int m;int n;numNode *now=new numNode;cout请输入人数：n;cout请输入初始数m:m;CreatCircleList(now,n);Loop(now,m);return 0;int CreatCircleList(numNode *now,int length)if(length=0)couterror!num=1;cout请输入编号为1的人拥有的密码。now-key;numNode *p=now;int i;for(i=1;inext=new numNode;p=p-next;p-num=i+1;cout请输入编号为i+1的人拥有的密码。p-key;p-next=now;ret