数据结构----线性表的应用实验报告

实验报告课程名称____数据结构上机实验__________实验项目______线性表的应用____________实验仪器________PC机___________________系别_____电子信息与通信学院___专业___________班级/学号________学生姓名_________________实验日期_______________________成绩_______________________指导教师_______________________实验一.线性表的应用1.实验目的：掌握线性链表的存储、运算及应用。利用链表实现一元多项式计算。2.实验内容：1)编写函数，实现用链表结构建立多项式；2)编写函数，实现多项式的加法运算；3)编写函数，实现多项式的显示；4)测试：编写主函数，它定义并建立两个多项式，显示两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。选做内容：修改程序，选择实现以下功能：5)多项式求值：编写一个函数，根据给定的x值计算并返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。6)多项式相减：编写一个函数，求两个多项式相减的多项式。7)多项式相乘：编写一个函数，求两个多项式的乘积多项式。3.算法说明：1)多项式的建立、显示和相加算法见讲义。可修改显示函数，使输出的多项式更符合表达规范。2)多项式减法：同次项的系数相减（缺项的系数是0）。例如a(x)=-5x2+2x+3，b(x)=-4x3+3x，则a(x)-b(x)=4x3-5x2-x+3。提示：a(x)-b(x)=a(x)+(-b(x))。3)多项式乘法：两个多项式的相乘是“系数相乘，指数相加”。算法思想是用一个多项式中的各项分别与另一个多项式相乘，形成多个多项式，再将它们累加在一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则a(x)*b(x)=(-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3)=(20x5-8x4-12x3)+(-15x3+6x2+9x)=20x5-8x4-27x3+6x2+9x。4.实验步骤：根据实验报告的要求，我对文件夹里的C文件进行了丰富和修改，步骤如下：链表结构建立多项式：typedefstructpolynode{floatcoef;//系数intexp;//指数structpolynode*next;//下一结点指针}PNode;编写函数，实现多项式的加法运算；PNode*PolyAdd(PNode*f1,PNode*f2)//实现加法功能。{//实现两多项式（头指针分别为f1和f2）相加，返回和多项式f3=f1+f2。PNode*pa=f1-next,*pb=f2-next,*pc,*f3,*q;intexp;floatcoef;f3=(PNode*)malloc(sizeof(PNode));//建立头指针f3-exp=-1;//对头指针初始化f3-next=f3;pc=f3;//将pc指向头指针while(pa-exp!=-1||pb-exp!=-1)//返回头指针时，跳出循环{if(pa-exppb-exp){exp=pa-exp;coef=pa-coef;pa=pa-next;}elseif(pa-exppb-exp){exp=pb-exp;coef=pb-coef;pb=pb-next;}else{exp=pa-exp;coef=pa-coef+pb-coef;pa=pa-next;pb=pb-next;}if(coef!=0){q=(PNode*)malloc(sizeof(PNode));//建立新的q指针存放负指数的指针q-exp=exp;q-coef=coef;//将q插入链表中q-next=pc-next;pc-next=q;pc=q;}}returnf3;//返回}实现多项式的显示；voidShowPloy(PNode*h)//用if语句判断，当指数为0是，只输出系数；当指数为1时，输出系数和X；当系数为1时，输出X和指数。{h=paixu(h);//整理函数，使之降幂排列PNode*p=h-next;if(p==h){printf(表达式为空\n);return;}if(p-coef==1)printf(x^%d,p-exp);//用if语句判断，若输出x^o和x^1值为0和1直接输出数据。elseif(p-exp==1)printf(%gx,p-coef);elseif(p-exp==0)printf(%g,p-coef);elseprintf(%gx^%d,p-coef,p-exp);p=p-next;while(p!=h){if(p-coef0)printf(+);//系数为负，不用输出加号if(p-coef==1)printf(x^%d,p-exp);elseif(p-exp==1)printf(%gx,p-coef);elseif(p-exp==0)printf(%g,p-coef);elseprintf(%gx^%d,p-coef,p-exp);p=p-next;}printf(\n);}主函数voidmain(){PNode*F1,*F2,*F3;floatx;F1=CreatPoly();F2=CreatPoly();printf(\nf1(x)=);ShowPloy(F1);printf(\nf2(x)=);ShowPloy(F2);F3=PolyAdd(F1,F2);F3=paixu(F3);printf(\nf1+f2=:);ShowPloy(F3);F3=PolySub(F1,F2);printf(\nf1-f2=:);ShowPloy(F3);F3=PolyMult(F1,F2);printf(\nf1*f2=:);ShowPloy(F3);printf(\nx的值为:);scanf(%f,&x);printf(\nf1(x=%.3f)=%.3f\n,x,PolyValue(F1,x));}多项式求值doublePolyValue(PNode*h,floatx){//编写算法，求以h为头指针的多项式在x点的值并返回该值。doublef=0.0;//求出f=f(x);PNode*pa;h=paixu(h);pa=h-next;while(pa-exp!=-1)//使用f+=coef*pow，返回f{f+=(pa-coef)*pow(x,pa-exp);pa=pa-next;}returnf;}多项式相减PNode*PolySub(PNode*f1,PNode*f2){//编写此算法，实现两多项式（头指针分别为f1和f2）相减，返回差多项式f3=f1-f2。PNode*pa=f1-next,*pb=f2-next,*pc,*f3,*q,*head;f3=(PNode*)malloc(sizeof(PNode));//建立头指针f3-exp=-1;//头指针的初始化f3-next=f3;pc=f3;//pc指向头指针,便于操作。while(pb-exp!=-1)//返回头指针时，跳出循环。{q=(PNode*)malloc(sizeof(PNode));//建立新的q指针存放负指数的指针q-coef=pb-coef*(-1);q-exp=pb-exp;//将q插入链表中q-next=pc-next;pc-next=q;pc=q;pb=pb-next;}head=PolyAdd(f1,f3);//调用加法函数做减法returnhead;//返回头指针}多项式相乘PNode*PolyMult(PNode*f1,PNode*f2){//实现两多项式（头指针分别为f1和f2）相乘，返回乘积多项式f3=f1*f2。PNode*pa=f1-next,*pb=f2-next,*pc,*u,*head;intexp;floatcoef;head=(PNode*)malloc(sizeof(PNode));head-exp=-1;head-next=head;pc=head;while(pa-exp!=-1)//多项式相乘，录入u指针，查到头指针。{while(pb-exp!=-1){coef=pa-coef*pb-coef;exp=pa-exp+pb-exp;u=(PNode*)malloc(sizeof(PNode));u-coef=coef;u-exp=exp;u-next=pc-next;pc-next=u;pc=u;pb=pb-next;}pb=pb-next;pa=pa-next;}returnhead;//返回头指针}程序运行截图测试成功~！程序完整源代码如下：#includestdio.h#includestdlib.h#includemath.htypedefstructpolynode{floatcoef;//系数intexp;//指数structpolynode*next;//下一结点指针}PNode;PNode*paixu(PNode*f)//将多项式降幂排列{PNode*p,*q,*r,*p0,*q0;p=f-next;q=p-next;p0=f;q0=p;while(p-exp!=-1)//p为q的前驱，q与p指数指数值进行比较，{while(q-exp!=-1)//q为头指针推出循环，q移动一圈{if(p-expq-exp)//比较，若p大于q则q后移{q0=q;q=q-next;}elseif(p-expq-exp)//若p小于q则q插入p之前{r=q-next;q-next=p0-next;q0-next=r;p0-next=q;p=q;q=r;}elseif(p-exp==q-exp)//若相等，p的coef与q的相加，然后删除q节点，释放q的空间{p-coef+=q-coef;q0-next=q-next;q=q-next;}}p0=p;p=p-next;q=p-next;q0=p;}returnf;}voidShowPloy(PNode*h)//用if语句判断，当指数为0是，只输出系数；当指数为1时，输出系数和X；当系数为1时，输出X和指数。{h=paixu(h);//整理函数，使之降幂排列PNode*p=h-next;if(p==h){printf(表达式为空\n);return;}if(p-coef==1)printf(x^%d,p-exp);//用if语句判断，若输出x^o和x^1值为0和1直接输出数据。elseif(p-exp==1)printf(%gx,p-coef);elseif(p-exp==0)printf(%g,p-coef);elseprintf(%gx^%d,p-coef,p-exp);p=p-next;while(p!=h){if(p-coef0)printf(+);//系数为负，不用输出加号if(p-coef==1)printf(x^%d,p-exp);elseif(p-exp==1)printf(%gx,p-coef);elseif(p-exp==0)printf(%g,p-coef);elseprintf(%gx^%d,p-coef,p-exp);p=p-next;}printf(\n);}PNode*CreatPoly()//建立多项式链表，返回头指针{PNode*head,*p,*s;inti,n;head=(PNode*)malloc(sizeof(PNode));head-exp=-1;p=head;printf(多项式的项数为:);scanf(%d,&n);for(i=1;i=n;i++){s=(PNode*