线性表的应用

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

2、：5) 多项式求值：编写一个函数，根据给定的x值计算并返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。6) 多项式相减：编写一个函数，求两个多项式相减的多项式。7) 多项式相乘：编写一个函数，求两个多项式的乘积多项式。3、实验步骤： 1）多项式的输出：在函数PrintPoly(PNode *h)里，根据我们平时写多项式的习惯，对函数进行了修改，比如当系数为0时不输出、系数为1时省略1、指数为0时只输出系数、指数为1时指数1省略、实现降幂排列、同类项合并等等，使得多项式输出后跟我们平时书写的一样自然。在修改函数的过程中遇到过很多的问题，考虑问题不周全，在一遍

3、又一遍的运行后，才使得输出基本规范，但是降幂排列还是没能实现，后来上网查了些资料，再慢慢地修改了一点，最后才把问题解决，我试着运行了几遍，感觉结果还不错，以下是运行时的截图： 2）多项式的减法、求值和相乘：多项式的减法跟加法差不多，只需把被减的多项式的系数变成其相反数，然后再相加就可以了；多项式的求值也比较简单，取得X的值后，分别计算多项式的各项，存储在y中，然后把前几项的值相加，f=f+y；多项式的相乘是把系数相乘，指数相加，再创建新的节点存储各相乘后的项，最后返回头指针就行了。运行的最后结果如下图：4、程序清单：#include <stdio.h>#include <st

4、dlib.h>#include <math.h>typedef struct polynode float coef; /系数 int exp; /指数 struct polynode *next; /下一结点指针 PNode;void PrintPoly(PNode *h) /输出多项式。修改此算法，使输出形式更符合自然表达规范PNode *p=h->next,*q,*max,*t;int a=0; /存储指数，用于降幂排列float b=0; /存储系数if(p=h) printf("Null Poly.n"); /判断是否为空return; f

5、or(p=h->next;p->next!=h;p=p->next) /实现降序排列max=p; /令max=p为最高次幂for(q=p->next;q!=h;q=q->next) /冒泡法排序if(max->exp<q->exp)max=q; /如果max的指数比下一节点q指数小，则令max=qif(max->exp!=p->exp|max->coef!=p->coef) / 如果max变了，即max！=p，则交换p与max的成员值a=max->exp;b=max->coef;max->exp=p-&g

6、t;exp;max->coef=p->coef;p->exp=a;p->coef=b;for(p=h->next;p->next!=h;p=p->next) /此for循环用于合并同类项t=p->next; if(p->exp=p->next->exp)p->coef=p->coef+t->coef;p->next=t->next;free(t);p=h->next; /找到头节点，开始输出printf("f(x)="); if(p->coef=-1)printf(&

7、quot;-x%d", p->exp); /如果系数为-1,1省略输出，输出负号 else if(p->coef=0)printf(""); /如果系数为0，不输出 else if(p->coef=1)printf("x%d",p->exp); /如果系数为1,1省略输出else if(p->exp=0)printf("%g", p->coef); /如果系数为其他，指数为0，输出系数else if(p->exp=1)printf("%gx", p->coe

8、f); /指数为1，指数1省略输出else printf("%gx%d", p->coef, p->exp); /指数为其他，正常输出p=p->next; /输出第二项while (p!=h) /判断是否输完if(p->coef<0) if(p->coef=-1) /如果系数为-1，根据指数的值分别输出if(p->exp=0)printf("-1"); else if(p->exp=1)printf("-x");else printf("-x%d", p->ex

9、p);else if(p->exp=0)printf("%g", p->coef); / 如果系数小于0不为-1，按指数情况输出 else if(p->exp=1)printf("%gx", p->coef);else printf("%gx%d", p->coef, p->exp);else if(p->coef=0)printf(""); /如果系数为0，输出为空 else /如果系数大于0printf("+"); /输出+号 if(p->co

10、ef=1)printf("x%d",p->exp); /系数为1的情况else if(p->exp=0)printf("%g", p->coef); /系数不为1的情况按指数的情况输出 else if(p->exp=1)printf("%gx", p->coef); else printf("%gx%d", p->coef, p->exp); p=p->next; / 输出下一项 printf("n");PNode * CreatPoly() /建

11、立多项式链表，返回头指针PNode * head, *p, *s; int i,n;head=(PNode *)malloc(sizeof(PNode); /建立头节点head->exp=-1; /初始化头节点成员expp=head; /令p指向头节点printf("输入多项式的项数: ");scanf("%d",&n); /从键盘取得多项式项数for(i=1;i<=n; i+) /创建多项式链表s=(PNode *)malloc(sizeof(PNode);printf("输入多项式第%d项（coef exp）: &quo

12、t;,i);scanf("%g%d",&s->coef,&s->exp);p->next=s;p=s; p->next=head; /构成循环链表return head; /返回头指针void FreePoly(PNode *h) /编写此算法，将以h为头指针的多项式的链表结点逐个释放。 PNode *p=h->next; /p初始化为第一项 while(p!=h) /判断是否释放完毕free(p); /释放节点p=p->next; /下一项 return;PNode * PolyAdd (PNode *ha, PNode

13、 *hb) /实现两多项式（头指针分别为ha和hb）相加，返回和多项式hc=ha+hb。PNode *pa=ha->next,*pb=hb->next,*pc,*hc,*q; int exp; /存储指数float coef; /存储系数hc=(PNode *)malloc(sizeof(PNode);hc->exp=-1; hc->next=hc;pc=hc;while (pa->exp!=-1 | pb->exp!=-1) / 判断是否回到头节点if (pa->exp>pb->exp) /如果pa的指数大，则pa指向下一项exp=pa-

14、>exp; coef=pa->coef; pa=pa->next;else if (pa->exp<pb->exp) /如果pb的指数大，则pb指向下一项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) /当系数不为0时，创建链表，存储相加后的多项式 q=(PNode *)malloc(

15、sizeof(PNode);q->exp=exp;q->coef=coef;q->next=pc->next;pc->next=q;pc=q; return hc; /返回头指针PNode * PolySubtract(PNode *ha,PNode *hb) /与加法运算类似 /编写此算法，实现两多项式（头指针分别为ha和hb）相减，返回差多项式hc=ha-hb。PNode *pa=ha->next,*pb=hb->next,*pc,*hc,*q;int exp;float coef;hc=(PNode *)malloc(sizeof(PNode);

16、hc->exp=-1;hc->next=hc;pc=hc;while (pa->exp!=-1 | pb->exp!=-1) if (pa->exp>pb->exp) exp=pa->exp; coef=pa->coef; pa=pa->next;else if (pa->exp<pb->exp) exp=pb->exp; coef=-pb->coef; pb=pb->next; else exp=pa->exp; coef=pa->coef-pb->coef; pa=pa->

17、;next; pb=pb->next; if (coef!=0) q=(PNode *)malloc(sizeof(PNode);q->exp=exp;q->coef=coef;q->next=pc->next;pc->next=q;pc=q; return hc;PNode * PolyMultiply(PNode *ha,PNode *hb)/实现两多项式（头指针分别为ha和hb）相乘，返回乘积多项式hc=ha*hb。PNode *hc,*p,*q,*t,*pc;hc=(PNode *)malloc(sizeof(PNode); /创建头指针hc->

18、;exp=-1; hc->next=hc; /初始化为空链表pc=hc; /pc指向头指针for(p=ha->next;p!=ha;p=p->next) /双重dor循环for(q=hb->next;q!=hb;q=q->next)t=(PNode *)malloc(sizeof(PNode); /创建新节点用于存储相乘后的结果t->coef=p->coef*q->coef; /系数相加t->exp=p->exp+q->exp; /指数相加t->next=pc->next; /连接到链表pc->next=t;

19、/继续下一项pc=t;return hc; /返回头指针double PolyValue(PNode *h, float x)double y=0.0,f=0.0; /编写算法，求以h为头指针的多项式在x点的值并返回该值。int i;PNode *p=h->next; /求出f=f(x);while(p!=h)y=p->coef; for(i=1;i<=p->exp;i+)y=y*x; /求第i项的值f+=y; /求前i项的值p=p->next; / 循环求下一项的值return f; /返回求值结果void main() /主函数PNode *HA,*HB,*H

20、C;float x;HA=CreatPoly(); /创建HA链表HB=CreatPoly(); /创建HB链表 printf("多项式A:");PrintPoly(HA); /输出链表HAprintf("多项式B:");PrintPoly(HB); /输出链表HBprintf("输入x: "); scanf("%f", &x); / 取得X值printf("多项式求值结果A(x)=%fn",PolyValue(HA,x); /输出求值结果HC=PolyAdd(HA,HB); /调用多项式相加函数printf("多项式相加结果:");PrintPoly(HC); /输出相加后多项式printf("多项式想加后求值结果A(x)=%fn",PolyValue(H