数据结构线性表实验报告.doc

上传人:小飞机 文档编号:4281812 上传时间:2023-04-13 格式:DOC 页数:25 大小:131.50KB
返回 下载 相关 举报
数据结构线性表实验报告.doc_第1页
第1页 / 共25页
数据结构线性表实验报告.doc_第2页
第2页 / 共25页
数据结构线性表实验报告.doc_第3页
第3页 / 共25页
数据结构线性表实验报告.doc_第4页
第4页 / 共25页
数据结构线性表实验报告.doc_第5页
第5页 / 共25页
点击查看更多>>
资源描述

《数据结构线性表实验报告.doc》由会员分享,可在线阅读,更多相关《数据结构线性表实验报告.doc(25页珍藏版)》请在三一办公上搜索。

1、实 验 报 告课程名称 _数据结构上机实验_实验项目 _线性表的应用 _实验仪器 _PC机_系 别_电子信息与通信学院_专 业_ _ 班级/学号_ _学生姓名 _ _ 实验日期 _成 绩 _ 指导教师 _实验一. 线性表的应用1. 实验目的:掌握线性链表的存储、运算及应用。利用链表实现一元多项式计算。2. 实验内容:1) 编写函数,实现用链表结构建立多项式;2) 编写函数,实现多项式的加法运算;3) 编写函数,实现多项式的显示;4) 测试:编写主函数,它定义并建立两个多项式,显示两个多项式,然后将它们相加并显示结果。变换测试用的多项式,检查程序的执行结果。选做内容:修改程序,选择实现以下功能:

2、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) 多项式乘法:两个多

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文件进行了丰富和修改,步骤如下:链表结构建立多项式:typedef struct polynode float coef; /系数 int exp

4、; /指数 struct polynode *next; /下一结点指针 PNode; 编写函数,实现多项式的加法运算;PNode * PolyAdd (PNode *f1, PNode *f2) /实现加法功能。 /实现两多项式(头指针分别为f1和f2)相加,返回和多项式f3=f1+f2。PNode *pa=f1-next,*pb=f2-next,*pc,*f3,*q;int exp;float coef;f3=(PNode *)malloc(sizeof(PNode); /建立头指针f3-exp=-1; /对头指针初始化f3-next=f3;pc=f3; /将pc指向头指针while (p

5、a-exp!=-1 | pb-exp!=-1) / 返回头指针时,跳出循环if (pa-exppb-exp) exp=pa-exp; coef=pa-coef; pa=pa-next;else if (pa-expexp) 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插入链表

6、中q-next=pc-next;pc-next=q;pc=q; return f3; /返回实现多项式的显示;void ShowPloy(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语句判断,若输出xo和x1值为0和1 直接输出数据。 else if(p-exp=1) printf(%gx, p-coef)

7、;else if(p-exp=0) printf(%g, p-coef);else printf(%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);else if(p-exp=1) printf(%gx, p-coef);else if(p-exp=0) printf(%g, p-coef);else printf(%gx%d, p-coef, p-exp); p=p-next; printf(n);主函数void main(

8、)PNode *F1,*F2,*F3;float x;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, &

9、x);printf(nf1(x=%.3f)=%.3fn,x,PolyValue(F1,x);多项式求值double PolyValue(PNode *h, float x) /编写算法,求以h为头指针的多项式在x点的值并返回该值。double f=0.0;/求出f=f(x);PNode *pa;h=paixu(h);pa=h-next;while(pa-exp!=-1) /使用f+=coef*pow,返回ff+=(pa-coef)*pow(x,pa-exp);pa=pa-next;return f;多项式相减PNode * PolySub(PNode *f1,PNode *f2)/编写此算法,

10、实现两多项式(头指针分别为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-n

11、ext=pc-next; pc-next=q;pc=q;pb=pb-next;head=PolyAdd(f1,f3); /调用加法函数做减法return head; /返回头指针多项式相乘PNode * PolyMult(PNode *f1,PNode *f2)/实现两多项式(头指针分别为f1和f2)相乘,返回乘积多项式f3=f1*f2。PNode *pa=f1-next,*pb=f2-next,*pc,*u,*head;int exp;float coef;head=(PNode *)malloc(sizeof(PNode);head-exp=-1;head-next=head;pc=hea

12、d;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;return head; /返回头指针程序运行截图测试成功!程序完整源代码如下:#include #include #include typedef struct polyno

13、de float coef; /系数 int exp; /指数 struct polynode *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;else if(p-expexp) /若p小于q则q插入p之前

14、r=q-next;q-next=p0-next;q0-next=r;p0-next=q;p=q;q=r;else if(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;return f;void ShowPloy(PNode *h) /用if语句判断,当指数为0是,只输出系数;当指数为1时,输出系数和X;当系数为1时,输出X和指数。h=paixu(h); /整理函数,使之降幂排列PNode *p=h-next;if(p=

15、h) printf(表达式为空n); return; if(p-coef=1) printf(x%d,p-exp); /用if语句判断,若输出xo和x1值为0和1 直接输出数据。 else if(p-exp=1) printf(%gx, p-coef);else if(p-exp=0) printf(%g, p-coef);else printf(%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);else if(p-exp=1

16、) printf(%gx, p-coef);else if(p-exp=0) printf(%g, p-coef);else printf(%gx%d, p-coef, p-exp); p=p-next; printf(n);PNode * CreatPoly() /建立多项式链表,返回头指针 PNode * head, *p, *s; int i,n;head=(PNode *)malloc(sizeof(PNode);head-exp=-1;p=head;printf(多项式的项数为: );scanf(%d,&n);for(i=1;icoef,&s-exp);p-next=s;p=s; p

17、-next=head;return head;void FreePoly(PNode *h) /编写此算法,将以h为头指针的多项式的链表结点逐个释放。PNode *p,*q;p=h-next;while(p-exp)!+-1;q=p-next;free(p);p=q;free(h);return; /Free函数用于销毁链表,最后指向头指针,跳出循环并释放头指针。PNode * PolyAdd (PNode *f1, PNode *f2) /实现加法功能。 /实现两多项式(头指针分别为f1和f2)相加,返回和多项式f3=f1+f2。PNode *pa=f1-next,*pb=f2-next,*

18、pc,*f3,*q;int exp;float coef;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;else if (pa-expexp) exp=pb-exp; coef=pb-coef; pb=pb-next;else exp=pa-exp;coef=pa-coef

19、+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; return f3; /返回 PNode * PolySub(PNode *f1,PNode *f2)/编写此算法,实现两多项式(头指针分别为f1和f2)相减,返回差多项式f3=f1-f2。PNode *pa=f1-next,*pb=f2-next,*pc,*f3,*q,*head;f3=

20、(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); /调用加法函数做减法return head; /返回头

21、指针PNode * PolyMult(PNode *f1,PNode *f2)/实现两多项式(头指针分别为f1和f2)相乘,返回乘积多项式f3=f1*f2。PNode *pa=f1-next,*pb=f2-next,*pc,*u,*head;int exp;float coef;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-e

22、xp;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;return head; /返回头指针double PolyValue(PNode *h, float x) /实现多项式求值功能。利用指针求出每一项的值,再用加法加起来。/编写算法,求以h为头指针的多项式在x点的值并返回该值。double f=0.0;/求出f=f(x);PNode *pa;h=paixu(h);pa=h-next;while(pa-exp

23、!=-1) /使用f+=coef*pow,返回ff+=(pa-coef)*pow(x,pa-exp);pa=pa-next;return f;void main()PNode *F1,*F2,*F3;float x;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)=%.3fn,x,PolyValue(F1,x);实验总结:这次试验提高了我的编程能力,让我认识到了我C语言的不足之处。也使我了解了线性链表是具有链接存储结构的线性表,它用节点存放线性表中的数据元素,逻辑上相邻的节点不能随机存取,因为这个原因我前期的程序一直出错,以后编程序的时候要牢记。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号