《数据结构》课程设计多项式计算班级:学号:姓名：指导老师:多项式计算1、问题描述能够按照指数降序排列建立多项式；能够完成两个多项式的相加、相减和相乘,并将结果输出。

2、设计思路这个程序的关键是多项式的创建和排列，以及相乘时系数相乘和指数相加、相加时相同指数的系数相加、相减时相同指数的系数相减。

由于多项式拥有指数和系数(假设基数已定),所以可以定义一个包含指数系数的结构体,用单链表存储多项式的数据,所以结构体包含nｅxt指针。

数据插入时比较两数的指数,按照降序排序，从表头的next 开始，直至找到合适的位置,然后开始链表中数值的插入，如果相等则直接将指数相加,如果大于就将新数据插入到当前指向的前面,否则将新数据插入到最后。

输入完数据后选择计算方式（相乘、相加、相减),多项式运算时要循环遍历整个多项式，多项式的每一组数据都要和另一个多项式整组数据相运算(每一个运算值都存储到新建的“多项式”链表中），直到两个多项式都遍历完结束。

3、数据结构设计在模拟多项式对象时,为了简化处理,只取最核心的两个数据:多项式的系数和指数。

前面提到,要用单链表操作,所以要加上个nｅxｔ指针，再由该结构体定义一个结点类型和指针类型。

具体数据结构定义如下：typedｅｆsｔｒuct ｎode{iｎt xｓ; /＊系数＊／ｉnt zs; ﻩ/*指数＊／struct nodｅ* neｘt; /*next指针*/}Dｎoｄe,* Ｄnｏｄeliｓt;4、功能函数设计（１）链表初始化函数Crｅａt_node()带有头结点的头指针指向空（NULL）。

（2）多项式数据的创建函数Crｅat＿Dmeth()ﻩ当链表初始化成功后,开始创建多项式。

分别循环输入两个多项式的系数和指数,其中要用到插入函数。

ﻩ（3)数据的插入函数Inｓeｒt_node(）ﻩ当创建多项式时,要用到此函数,即利用插入的方式将多项式的数据连接起来。

再输入一组数据后，程序自动调用此函数,插入时也进行着排序，从表头的nexｔ开始，一一比较指数大小，直到大于或等于当前指向的数据或遍历完所有数据时停止,然后开始链表中数值的插入，如果相等则直接将指数相加,如果大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。

(4）多项式的显示函数Show()ﻩ从多项式表头的next开始，直到指向空(NＵLＬ）,将系数与指数一一显示。

（5)选择运算方式的函数seｌecｔ()三种选择：1为相乘,2为相加，３为相减；每一种选择调用相应的运算函数。

ﻩ（6)多项式的运算函数:新建链表存储计算后的多项式ﻩ1、多项式相乘Mulrｅsuｌｔ（）创建两个指针分别指向两个多项式表头的next,使用两个wｈｉl ｅ函数嵌套循环,遍历每一组数据，每遍历一次都将两组数据的系数相乘,指数相加,再利用插入函数将系数与指数存储到新建多项式的链表中。

２、多项式相加Aｄdｒｅsulｔ()ﻩ创建两个指针分别指向两个多项式表头的next,分别使用两个whi ｌe函数独自循环,遍历各自的每一组数据，每遍历一次都将系数与指数存储到新建多项式的链表中。

因为存储时利用到插入函数，而插入函数中有相同指数的系数相加功能,所以直接将两个多项式的数据依次插入到新的多项式中即可完成多项式相加。

ﻩ3、多项式相减Sｕbreｓult（）创建两个指针分别指向两个多项式表头的next，以两个指针同时不为空为条件循环遍历，如果当前多项式1的指数小于多项式2，则将当前多项式２的系数置负,指数不变，存入新建多项式中,指向多项式2的指针指向下一个;如果如果当前多项式1的指数大于多项式２，则将当前多项式1的系数指数不变，存入新建多项式中,指向多项式１的指针指向下一个;否则将多项式1的系数减去2的系数后存入新建多项式中，指数不变存入，再将两个指针同时指向下一个。

结束循环后判断是哪一个多项式遍历完了，将未遍历完的多项式剩下的数据全部插入到新建多项式中。

（7）主函数maｉｎ()ﻩ创建两个多项式的链表并且初始化，分别调用相应的多项式创建函数，创建成功后选择运算方式,再将运算结果输出显示。

5、程序代码#include<sｔｄio.h>#ｉnclude<stdlib.h＞tｙpedｅf ｓtrucｔｎode{ｉnt xs;int ｚs;strucｔｎode * neｘt;}Dnｏdｅ,＊Dｎｏdelisｔ; /*定义结构体*／ＤnoｄelisｔCrｅaｔ_node(void) /*链表初始化*/｛Dnodeｌiｓt Ｄ;ﻩD=(Dnodeliｓt)mａlloｃ(sizｅｏｆ(Dnoｄｅ));ﻩif(D)ﻩD->ｎext＝NＵLL;ﻩｒeｔuｒｎ D;}iｎt Iｎsert_nodｅ(Dnoｄｅlist Ｄ,int xｓ,int zs) /＊插入函数*/｛ﻩＤnodelist ｐ；ﻩDnｏdelｉst q;Dnｏｄｅlist r；ﻩp=D;whｉlｅ(p-＞ｎext）{ﻩﻩr=p;ﻩﻩp=p->next;if(zs＝=p->zs） /*指数相等,系数直接相加,结束＊/ﻩ{ﻩp－>xs=p->ｘs＋ｘs;ﻩﻩretｕrn １;ﻩ｝ﻩelsｅ if(zs>p->ｚs) /*指数大于当前数据的,将数据插入当前数据之前，结束＊/ﻩﻩ{ﻩﻩq=Crｅat_ｎode();ﻩﻩﻩq->xs＝xs;ﻩﻩﻩｑ->ｚs＝zｓ；ﻩﻩｒ->next＝q;ﻩｑ->ｎext=p;return 1;ﻩ}ﻩ}/*whｉle(ｐ-＞neｘt)＊/q＝Cｒeａt＿ｎｏｄe(）; ／*要插入的数据指数最小，直接插入至链表最后*/ﻩq->xs=xs;ﻩq->ｚｓ=ｚs;q->next=p->next；ﻩp->neｘt=q；ﻩｒeｔuｒn 1;ﻩfreｅ(p）;frｅe(q);ﻩfrｅe(ｒ);｝Dｎodelｉst Creａｔ＿Dｍｅth(inｔ lenｇth）／*创建多项式*/{ﻩint ｉ,m,n;ﻩDnｏdｅｌｉsｔ D；D=Creat_ｎode();ﻩｆor（i＝0；i＜leｎgth；ｉ＋+) /*以三组数据为例*/｛ﻩﻩｓcanf(＂%d,%d＂,＆m,＆ｎ);Inｓｅrt＿nｏde(D,m,n)；／*调用插入函数，将输入的系数指数插入链表＊/｝ﻩrｅturn D;｝Dnｏdelist Ｍｕｌrｅsｕlt(Dnodｅlｉst D1,Dｎodｅlｉst D2) /*多项式相乘*／{Dnoｄelist Ｄ；ﻩＤnodelｉst p,q;ﻩint x，z;ﻩD=Creat_nｏdｅ（）；ﻩp=D1->nexｔ;ﻩq=D2-＞next;ﻩwhｉｌe（q)ﻩ｛ﻩwｈilｅ(ｐ){ﻩﻩx=p->xs*ｑ->xs; /*系数相乘,指数相加＊/ｚ＝p->zs+q->zs；ﻩﻩInsｅｒt_nｏdｅ(D,x,z);ﻩp=p->nｅxｔ;ﻩ}ﻩp＝D1－>next；ﻩq=q->next;｝ﻩreturn D;}Dｎodelist Ａdｄrｅｓｕlt(Ｄnoｄelｉst D1,DnodelｉsｔＤ２) /*多项式相加*/{Dnodelｉｓt D;Dnodelist p，q;ｉnt x,z;Ｄ=Creat_node(）；ﻩp=D1-＞nｅｘt;q=Ｄ2-＞next;ﻩｗｈile(q)ﻩ{ﻩﻩx＝q->xs;ﻩz＝q－>ｚs;Ｉｎsｅｒt_nｏdｅ(D,ｘ，z);ﻩﻩｑ=q-＞nｅxt;}ﻩwhｉlｅ(ｐ)ﻩ{ｘ=p->xs;ﻩz=p->zs;ﻩﻩInsert_node(D,ｘ，z);ﻩｐ=ｐ->ｎext; ／*直接插入数据，利用插入函数可完成该功能＊／}reｔurn Ｄ;｝DnoｄeliｓｔＳｕｂresｕlt(DnodｅlisｔＤ１,Dnodｅｌｉsｔ D2）／*多项式相减*/｛ﻩＤnodeｌiｓt Ｄ;Dnodelist p,ｑ;iｎｔｘ,ｚ;ﻩＤ=Creaｔ_nodｅ(）;ﻩｐ=Ｄ1->next；ｑ=D2->nｅxt;ﻩｗhiｌe(p&&q){ｉf(（ｐ->ｚs)＜(q->zs)) /*指数小(1的数据在2中不存在)，直接插入*／ﻩ{ﻩx=-(q－＞ｘs); /＊由于是式1减式2，所以系数置负*/ﻩﻩｚ=q->zs；ﻩﻩＩnserｔ_node(Ｄ,x，ｚ);ﻩﻩq=q->nｅxt;ﻩ｝ﻩeｌｓe ｉf((p->ｚs)>(ｑ->ｚｓ）) /*指数大（2的数据在1中不存在)，直接插入*／ﻩ｛ﻩx=p-＞xｓ;ﻩｚ=p->zs;ﻩﻩＩｎsert＿noｄｅ(D,ｘ,ｚ);ﻩﻩp＝p-＞neｘｔ;ﻩ}ﻩelse /*指数相同的先将系数相减,再插入*/ﻩ{ﻩﻩﻩｚ=q－>zs；ﻩｘ＝(ｐ-＞xs)-(q->xｓ);ﻩＩnserｔ_ｎｏde(D,x，ｚ);ﻩp＝p-＞nexｔ;ﻩﻩq=q－＞nｅxｔ；ﻩ}}／＊ｗhile(ｐ&＆q)*/whilｅ(p）{ﻩｘ=ｐ->xs;z=p-＞ｚs;ﻩInseｒｔ_noｄe(D,x,ｚ);ﻩp=p－＞ｎeｘt;}ﻩｗhile(q)ﻩ{ﻩﻩx=-(ｑ->ｚs);ﻩz=q->zs;ﻩIｎsert_nｏde(D,ｘ,z);ﻩq=q－>next;} /＊将未遍历完的数据直接插入*／ﻩrｅturn D;｝Ｄnodeliｓt sｅlect(Dnodｅlist D1,Dnodeｌist D2） /*选择函数*／{Dｎodeliｓｔ D;inｔs;ｐｒinｔf("请选择：\ｎ1:相乘\n2:相加\n3:相减\ｎ"）；scanf("%d＂,&s）；ﻩsｗitch(s)｛case 1: D=Mｕlresulｔ(D1,D２); /*调用相乘函数*／ﻩﻩpｒiｎｔf("相乘结果(系数,指数):\n＂)；ﻩbrｅａk;ﻩcasｅ 2: D=Addｒeｓuｌt(D1,D２)； /*调用相加函数＊/ ﻩﻩﻩpｒintf(＂相加结果(系数,指数):＼n＂）;breａk；ｃase 3: Ｄ＝Subrｅsuｌt（D1,D２)；/*调用相减函数*/ﻩﻩpｒintf("相减结果(系数，指数):\ｎ");bｒeak;dｅｆaｕlt:ﻩpｒiｎtf("无此选项＼n"）;ﻩｂreak;ﻩ}retｕｒｎ D;｝voｉd Shoｗ(Dnoｄeｌist D) /*显示(输出)函数＊/{ﻩDnoｄｅｌｉst r;r=D－＞next;ﻩwhile(r)ﻩ{ﻩprintf("（%ｄ,%d)+＂，r->ｘs,ｒ->zs）;ﻩｒ＝r->next;ﻩ}ｐriｎｔf（"\n")；｝voｉd ｍａｉn(）｛ﻩDnodeliｓt D1，Ｄ2,D；inｔ lｅngｔｈ;D1＝Ｃｒｅａt_ｎodｅ();ﻩD2=Creat_node(); /*D1为多项式１，Ｄ2为多项式２，初始化＊／ｐｒintｆ("输入多项式1的组数:\n”);sｃａnｆ(“%d”,＆ｌｅngth);prｉntf(＂输入多项式1系数,指数:（％ｄ组）＼n",lｅnｇth);ﻩD１=Ｃreat_Dｍeth(leｎgｔh); /＊创建多项式1*/ ｐriｎｔf("输入多项式2的组数：\ｎ”);scanｆ(“%d”,&ｌenｇth)；pｒintｆ("输入多项式2系数,指数:(％d组)\n"，lenｇtｈ）；ﻩD2=Creaｔ＿Dｍetｈ（ｌenｇth)；／＊创建多项式２*/ﻩＤ=ｓelect（D１,Ｄ２)； /*选择运算方式＊/ Shｏw(D); /＊输出显示*/getch();}6、运行与测试程序运行时，先提示第一个多项式的组数，确定组数后才可输入相应的数据，之后是多项式2;输入完数据后，程序提示选择运算方式。