数据结构：一元多项式的表示与相加.doc

实验一 一元多项式的表示与相加实验目的：1.复习并熟练掌握数据结构所使用的程序设计语言C语言 ；2.学会单步跟踪、调试自己的程序；3.加深对线性表特别是链表知识的理解和掌握，并能够运用相关知识来解决相关的具体问题，如一元多项式相加等；程序流程：1. 定义一元多项式链表结构体类型；2. 输入多项式项数以分配存储空间；3. 输入多项式每项的系数和指数，将其插入当前多项式链表。同时判断是否有与当前节点指数相同的项，若存在，则将两项系数相加合并。此外，若存在系数为0的项，将其存储空间释放；4. 进行多项数加法时，新建一个存储结果的链表，分别将两多项式各项依次插入结果多项式即完成多项式相加运算；5. 进行多项数加法时，将减项多项式各项系数化为相反数后进行加法操作，即完成多项式相减运算；6. 对x赋值后，将x值代入多项式进行运算得到多项式的值；7. 输出多项式。注意：进行完一次运算以后，应该及时销毁无用多项式以释放空间以便再次应用。算法及注释：1）定义一元多项式链表结构体类型typedef struct Lnodefloat cof; /定义系数int exp; /定义指数struct Lnode *next; /定义指针变量指向下一个节点Lnode ,*Linklist; /定义新的变量类型2）建立多项式存储线性链表头结点void makehead(Linklist &head)head=(Linklist)malloc(sizeof(Lnode); /建立新的节点head-exp=-1;head-next=NULL; /指针赋空head-cof=1;3）将输入的多项式信息存储于节点中void makelnode(Lnode *&p)p=(Lnode*)malloc(sizeof(Lnode); /建立新的节点printf(Input the cof and expn);scanf(%fx%d,&p-cof,&p-exp); /输入多项式底数 指数信息p-next=NULL; /指针赋空4） 清除系数为零的多项式节点void clear(Linklist la)Lnode *p,*q; /定义两个指向结构体的指针p=la;q=p-next;while (q)if (fabs(q-cof)next=q-next; /指针指向相隔的下一个节点free(q); /销毁系数为零的节点q=p-next; /指针后移一位else p=p-next; /p q分别后移一位q=q-next;5）找到多项式中与当前节点同指数项位置int locate(Linklist l,Lnode *&p,Lnode*e)p=l;/标记表头if (!l-next) return(0);while(p&e-exp!=p-exp)/当p存在且指数不相等时指针后移p=p-next;if(p)return(p);/当p存在时，返回p地址else /没找到时寻找出插入位置p=l;while (p-next&e-expnext-exp)p=p-next;if (!p-next)p=p;return(0);return(0);6）将多项式节点插入已有多项式链表中，同时完成系数运算void caseinsert(Linklist &l,Lnode *e)Lnode *p;if (locate(l,p,e)/指数相同项系数相加p-cof += e-cof;free(e);else/插入新的项e-next=p-next;p-next=e;7）创建新的多项式链表void creat(Linklist &head,int m)Lnode *p;int i;makehead(head);/建立头结点for (i=1;inext;printf(Poly：%6fx%d,p-cof,p-exp); p=p-next;while (p)if(p-cof0) printf(+);/系数正负号 if (fabs(p-cof)cof,p-exp);p=p-next;/指针后移printf(n);10）进行多项式加法运算void add(Linklist la,Linklist lb,Linklist &lc) Lnode *p,*q,*q1,*p1;p=la-next;q=lb-next;makehead(lc);/建立一个新的表头while(p)p1=p-next;caseinsert(lc,p);/将多项式节点p插入已有多项式链表lc中，同时完成系数运算p=p1;/指针后移while(q)q1=q-next;caseinsert(lc,q);/将多项式节点q插入已有多项式链表lc中，同时完成系数运算q=q1;11）将减项多项式转化为系数为相反数的多项式便于转化为加法运算void reverse(Linklist &l)Linklist p;p=l-next;while(p)p-cof*=-1;/系数自乘-1 p=p-next;12）进行多项式减法运算void sub(Linklist la,Linklist lb,Linklist &lc)reverse(lb);add(la,lb,lc);clear(lc);/清除头结点13）对x赋值进行多项式赋值运算float value(Linklist l,float x)float sum=0,t;int i;Linklist p=l-next;while(p)t=1;for (i=p-exp;i0;i-)t*=x;sum=sum+t*p-cof;p=p-next;return(sum);14） 销毁已有多项式，清除已有多项式占用的存储空间void destroy(Linklist la)Lnode *p,*q;p=la;while(p)q=p;p=p-next;free(q);15） 创建主程序即菜单界面void main()Linklist l10;int c,n,m,i;float a;printf(Choose the number to operate：n);printf(1：Creat a Polyn);printf(2：Poly Additionn);printf(3：Poly Substractionn);printf(4：Evaluationn);printf(5：Destroy a Polyn);printf(6：Print a Polyn);printf(0：Exitn);printf(nDestroy the Polys after used.n);printf(n*use , to separaten);scanf(%d,&c);while (c)switch (c)case 1:printf(Input the Poly number 19n);scanf(%d,&n);input(ln);break;case 2: printf(Input the Poly number to add,and the Poly number stored inn);scanf(%d,%d,%d,&n,&m,&i);add(ln,lm,li);break;case 3: printf(Input the Poly number to subtract,and the Poly number stored inn);scanf(%d,%d,%d,&n,&m,&i);sub(ln,lm,li);break;case 4:printf(Input the number to operate and the value of x:n);scanf(%d,%f,&n,&a);printf(%fn,value(ln,a);break;case 5:printf(Input the Poly number:n);scanf(%d,&n);destroy(ln);break;case 6: printf(Input the Poly number:n);scanf(%d,&n);print(ln);case 0:n=0;break;default:printf(ERROR!);printf(Choose the number to operate:n);scanf(%d,&c);printf(OK!n);程序运行截图