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

1、实验一 一元多项式的表示与相加实验目的：1复习并熟练掌握数据结构所使用的程序设计语言一一C语言；2学会单步跟踪、调试自己的程序；3加深对线性表特别是链表知识的理解和掌握，并能够运用相关知识来解决相关的具体问题，如一元多项式相加等；程序流程：1定义一元多项式链表结构体类型；2输入多项式项数以分配存储空间；3输入多项式每项的系数和指数，将其插入当前多项式链表。同时判断是否有与当前节点指数相同的项，若存在，则将两项系数相加合并。此外，若存在系数为0的项，将其存储空间释放；4进行多项数加法时，新建一个存储结果的链表，分别将两多项式各项依次插入结果多项式 即完成多项式相加运算；5进行多项数加法时，将减项

2、多项式各项系数化为相反数后进行加法操作，即完成多项式相减运算；6对x赋值后，将x值代入多项式进行运算得到多项式的值；7输出多项式。注意：进行完一次运算以后，应该及时销毁无用多项式以释放空间以便再次应用。算法及注释：1) 定义一元多项式链表结构体类型typedef struct Lno defloat cof;int exp;struct Lnode *n ext;Lnode ,*Li nklist;2) 建立多项式存储线性链表头结点void makehead(L in klist &head)head=(Li nklist)malloc(sizeof(L no de);head-exp=-1;

3、head- next=NULL;head-cof=1;3) 将输入的多项式信息存储于节点中void make Ino de(L node *&p)p=(L no de*)malloc(sizeof(L no de);prin tf(I nput the cof and expn);scan f(%fx%d,&p-cof, &p-exp); p- next=NULL;4) 清除系数为零的多项式节点void clear(L in klist la)Lnode *p,*q;p=la;q=p-n ext;while (q)if (fabs(q-cof)n ext=q _n ext;free(q); q

4、=p-n ext;else p=p-n ext; q=q_n ext;5) 找到多项式中与当前节点同指数项位置in t locate(Li nklist l,L node *&p,L node*e) p=l;if (!l- next) return(O);while(p&e-exp!=p-exp) p=p-n ext;if(p)return(1);else p=l;while (p-n ext&e-expn ext-exp) p=p-n ext;if (!p- next)p=p;return(O); return(O);6) 将多项式节点插入已有多项式链表中，同时完成系数运算 void cas

5、e in sert(L in klist &I,L node *e)Lnode *p;if (locate(l,p,e)p-cof += e_cof;free(e);elsee-n ext=p-n ext;p_n ext=e;7) 创建新的多项式链表void creat(L in klist &head,i nt m)Lnode *p;i nt i;makehead(head);for (i=1;in ext;printf(Poly : %6fxA%d,p-cof,p-exp);p=p-n ext;while (p)if(p-cof0) pri ntf(+);if (fabs(p-cof)co

6、f,p-exp); p=p-n ext;prin tf(n);10) 进行多项式加法运算void add(Li nklist la,L in klist lb,Li nklist &c) Lnode *p,*q,*q1,*p1;p=la-n ext;q=lb-n ext;makehead(lc);while(p)p1=p-n ext;case in sert(lc,p);p=p1;while(q)q1=q _n ext;case in sert(lc,q);q=q1;11 )将减项多项式转化为系数为相反数的多项式便于转化为加法运算 void reverse(Li nklist &)Lin kl

7、ist p;p=l-n ext;while(p)p-cof*=-1;p=p-n ext;12) 进行多项式减法运算void sub(Li nklist la, Li nklist lb ,L i nklist &c)reverse(lb);add(la,lb,lc);clear(lc);13) 对x赋值进行多项式赋值运算float value(Li nklist l,float x)float sum=0,t;int i;Lin klist p=l-n ext; while(p)t=1;for (i=p_exp;i0;i_) sum=sum+t*p-cof; p=p-n ext;return(

8、sum);14) 销毁已有多项式，清除已有多项式占用的存储空间 void destroy(L in klist la)Lnode *p,*q;p=la;while(p)q=p; p=p-n ext; free(q);15) 创建主程序即菜单界面void mai n()Lin klist l10;int c,n ,m,i;float a;printf(Choose the number to operate : n);printf( printf( printf( printf( printf( printf( printf(1: Creat a Polyn);2： Poly Additionn

9、);3： Poly Substractionn);4： Evaluationn);5： Destroy a Polyn);6： Print a Polyn);0： Exitn);prin tf(nDestroy the Polys after used.n); prin tf(n*use , to separaten);scan f(%d,&c);while (c)switch (c)case 1:prin tf(l nput the Poly number 19n);sea nf(%d,&n);in put(l n);break;case 2: printf( In put the Poly

10、 nu mber to add,a nd the Poly nu mber stored inn ”)； sea nf(%d,%d,%d，&n,&m,&i);add(l n,lm,li);break;case 3: printf( In put the Poly nu mber to subtract,a nd the Poly nu mber stored inn); sea nf(%d,%d,%d，&n,&m,&i);sub(l n,lm,li);break;case 4:prin tf(l nput the nu mber to operate and the value of x:n)

11、;sca nf(%d,%f, &n,& a);prin tf(%fn,value(l n,a);break;case 5:prin tf(l nput the Poly nu mber:n);sca nf(%d,&n);destroy(l n);break;case 6: printf( In put the Poly nu mber:n);sca nf(%d,&n);prin t(l n);case 0:n=0;break;default:pri ntf(ERROR!);prin tf(Choose the nu mber to operate:n);scan f(%d, &c);prin tf(OK!n ”);程序运行截图：实验总结:这次