一元多项式的运算
数据结构课程设计实验报告
专业班级：
学号：
姓名：
2011年1月1日
题目：一元多项式的运算
1、题目描述
一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。
在数学上，一个一元n次多项式P n(X)可按降序写成：
P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0
它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示：
P=(P n，P(n-1)，......，P1，P0)
每一项的指数i隐含在其系数P i的序号里。
假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示：
Q=(q m,q(m-1)，.....，q1，q0)
不是一般性，假设吗吗m R n(X)= P n(X)+ Q m(X) 很显然，可以对P,Q和R采用顺序存储结构，使得多项式相加的算法定义和实现简单化。然而，在通常的应用中，多项式的次数可能变化很大而且很高，使得顺序存储结构的最大长度很难确定。特别是在处理项数少且次数特别高的情况下，对内存空间的浪费是相当大的。因此，一般情况下，都采用链式存储结构来处理多项式的运算，使得两个线性 链表分别表示一元多项式P n(X)和Q m(X)，每个结点表示多项式中的一项。 通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就是去了意义，在计算机内要表示一个多项式，至少具有以下数据信息：系数信息、指数信息和指向下一个单项式的指针。通过指针，我们就可以把多个单项式连接起来，形成一个多项式。 2、任务要求 系数定义的是float型，范围是3.4*10^-38~3.4*10^38;指数定义的是int型，范围是-2147483648~+2147483647；输入多项式系数及指数，系统会自动将系数转化为浮点型。 功能： （1）．提示输入数据。要求先输入多项式的项数。 （2）．创建多项式。接收输入的数据，并保存到链表中。 （3）．显示已经创建好的多项式。 （4）．实现加、减法运算。 （5）.退出程序 3、概要设计 (1)链表结点的类型定义 (2)建立有序链表void CreatPolyn(LinkList &L,int n) (3)多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) (4)多项式链表的输出void printList(LinkList L) 4、详细设计 (1)链表结点的类型定义 typedef struct //在struct前使用关键字typedef，表示是声明新类型 { float coef; //系数 int expn; //指数 }DataType; //DataType是新类型 typedef struct node //单链表的存储 { DataType data; //数据域 struct node *next; //指向下一个结点 }ListNode,*LinkList; //ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型 (2)建立有序链表 要实现多项式的加法运算，首先要建立多项式的存储结构，每一个一元多项式的存储结构就是一个有序单链表。有序链表的基本操作定义与线性链表有两处不同，一个是结点的查找定位操作LocateNode有所不同，二是结点的插入操作InsertNode不同，这两个操作算法分别如下： //结点的查找定位 int LocateNode(LinkList L,DataType e,int &q) { ListNode *p=L->next; q=0;//记录结点位置序号 while(p&&e.expn { p=p->next; q++; } if(p==NULL||e.expn!=p->data.expn) return 0; else return 1; } void InsertNode(LinkList &L,DataType e,int q)函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数expn是升序。将s节点插入到e所指向的链表。在该函数的操作中，要注意指针是如何移动的。 //有序链表结点的插入 void InsertNode(LinkList &L,DataType e,int q) { ListNode *s,*p; int i=0; p=L; while(p->next && i { p=p->next; i++; }//查找插入位置 s=(ListNode*)malloc(sizeof(ListNode)); s->data.coef=e.coef; s->data.expn=e.expn; s->next=p->next; p->next=s; } 有了上述两个“结点的查找定位算法”和“有序链表结点的插入算法”， int n保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为n时，将不再提示用户继续输入多项式的系数和指数。建立一个一元多项式的单链表的具体算法如下： //多项式链表的建立 void CreatPolyn(LinkList &L,int n) { LinkList pa; //定义一个头指针为pa链表 int i,q; //i用来计输入的项数，q指结点的位置序号 DataType e; //插入的值e pa=(ListNode*)malloc(sizeof(ListNode)); //生成链表头结点 pa->next=NULL; for(i=1;i<=n;i++) { scanf("%f,%d",&e.coef,&e.expn); if(!LocateNode(pa,e,q)) //当前链表中不存在该指数项 InsertNode(pa,e,q); //调用InsertNode函数插入结点 } L=pa; } (3)多项式链表的相加 根据一元多项式相加的运算规则：对于一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式”中相应的位置。 根据以上运算规则，其实现算法思路如下： 假设pc为指向“和多项式链表”当前尾结点的指针，指针pa和pb分别指向两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项值，有下面三种情况： 1.若指针pa所指结点的指数值大于指针pb所指结点的指数值，则取pa指针所指向的结点插入到pc指针所指结点之后，分别修改指针pa和pc，使之指向链表的下一个结点； 2.若指针pa所指结点的指数值小于指针pb所指结点的指数值，则取pb指针所指向的结点插入到pc指针所指结点之后，分别修改指针pb和pc，使之指向链表的下一个结点； 3.若指针pa所指结点的指数值等于指针pb所指结点的指数值，则将两结点中的系数相加，如果其和数不为零，则修改pa指针所指结点中的系数值，将其结点插入到pc指针所指结点之后，分别修改pa、pb和pc，使之指向各自链表的下一个结点，同时删除并释放指针pb原先指向各自链表的下一个结点；如果和数为零，保存pa和pb所指向的结点，修改pa和pb指针使之指向各自链表的下一个结点，然后释放保存的两个结点。再比较指针pa和pb指向节点中的指数项值，分3种情况进行处理….. 这样的操作一直继续到pa或pb等于NULL为止。最后将未结束的链表后面剩余的节点连接到pc指针所指向结点之后。 上述多项式的相加过程和两个有序链表合并的过程类似，不同之处仅在于多项式的比较多了相等比较后的操作。因此，多项式相加的过程完全可以利用线性链表的基本操作来实现。具体实现多项式相加的算法如下： //多项式链表的相加 void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) { //两个有序链表La和Lb表示的多项式相加 ListNode *pa,*pb,*pc,*s; float sum; pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while (pa&&pb) { if(pa->data.expn > pb->data.expn) { pc->next=pa;pc=pa;pa=pa->next; } else if(pa->data.expn < pb->data.expn) { pc->next=pb;pc=pb;pb=pb->next; } else { sum=pa->data.coef+pb->data.coef; if(fabs(sum)>0) { //系数和不为零 pa->data.coef=sum; pc->next=pa;pc=pa;pa=pa->next; s=pb;pb=pb->next;free(s); } else{ s=pa;pa=pa->next;free(s); s=pb;pb=pb->next;free(s); } } } pc->next=pa?pa:pb;//插入链表剩余部分 free(Lb);//释放Lb的头结点 } (4) 多项式链表的输出 void printList(LinkList L)函数功能：显示多项式链表。在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“+”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。因此，输出多项式链表的算法实现如下： //多项式链表的输出 void printList(LinkList L) { ListNode *p; p=L->next; while(p) { printf("%c %fx^ %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn); p=p->next; } printf("\n"); } 源程序代码： #include #include #include //多项式链表结点类型定义 typedef struct //在struct前使用关键字typedef，表示是声明新类型 { float coef; //系数 int expn; //指数 }DataType; //DataType是新类型 typedef struct node //单链表的存储 { DataType data; //数据域 struct node *next; //指向下一个结点 }ListNode,*LinkList; //ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型 //结点的查找定位 int LocateNode(LinkList L,DataType e,int &q) { ListNode *p=L->next; q=0;//记录结点位置序号 while(p&&e.expn { p=p->next; q++; } if(p==NULL||e.expn!=p->data.expn) return 0; else return 1; } //有序链表结点的插入 void InsertNode(LinkList &L,DataType e,int q) { ListNode *s,*p; int i=0; p=L; while(p->next && i { p=p->next; i++; } s=(ListNode*)malloc(sizeof(ListNode)); s->data.coef=e.coef; s->data.expn=e.expn; s->next=p->next; p->next=s; } //多项式链表的建立 void CreatPolyn(LinkList &L,int n) { LinkList pa; //定义一个头指针为pa链表 int i,q; //i用来计输入的项数，q指结点的位置序号 DataType e; //插入的值e pa=(ListNode*)malloc(sizeof(ListNode)); //生成链表头结点 pa->next=NULL; for(i=1;i<=n;i++) { scanf("%f,%d",&e.coef,&e.expn); if(!LocateNode(pa,e,q)) //当前链表中不存在该指数项 InsertNode(pa,e,q); //调用InsertNode函数插入结点} L=pa; } //多项式链表的输出 void printList(LinkList L) { ListNode *p; p=L->next; while(p) { printf("%c %fx^ %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn); p=p->next; } printf("\n"); } //多项式链表的相加 void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc) { //两个有序链表La和Lb表示的多项式相加 ListNode *pa,*pb,*pc,*s; float sum; pa=La->next;pb=Lb->next;//pa和pb分别指向两个链表的开始结点Lc=pc=La;//用La的头结点作为Lc的头结点 while (pa&&pb) { if(pa->data.expn > pb->data.expn) { pc->next=pa;pc=pa;pa=pa->next; } else if(pa->data.expn < pb->data.expn) { pc->next=pb;pc=pb;pb=pb->next; } else { sum=pa->data.coef+pb->data.coef; if(fabs(sum)>0) {//系数和不为零 pa->data.coef=sum; pc->next=pa;pc=pa;pa=pa->next; s=pb;pb=pb->next;free(s); } else{ s=pa;pa=pa->next;free(s); s=pb;pb=pb->next;free(s); } } } pc->next=pa?pa:pb;//插入链表剩余部分 free(Lb);//释放Lb的头结点 } //主控函数 void main() { LinkList La,Lb,Lc; int n; printf("输入第一个多项式的项数:"); scanf("%d",&n); printf("输入第一个多项式的每一项的系数,指数:\n"); CreatPolyn(La,n); printf("第一个多项式为:"); printList(La); printf("输入第二个多项式的项数:"); scanf("%d",&n); printf("输入第二个多项式的每一项的系数,指数:"); CreatPolyn(Lb,n); printf("第二个多项式为:"); printList(Lb); AddPolyn(La,Lb,Lc); printf("\n相加后的和多项式为:"); printList(Lc); } 5、调试分析 此一元多项式的运算程序，只能实现一元多项式的加、减法，不能实现一元多项式的乘法，而且若想计数多个多项式的和或者差的话，必须退出界面重新开始计算。在补充程序里面，解决了程序没有的选择功能表的功能，及其多项式的乘法运算。 6. 测试结果 输入多项式的项数，并且显示多项式及其两个多项式的和： 补充程序： 多项式运算程序具有以下基本功能： 1．界面输出，提示如何输入数据。要求先输入多项式的项数。 2．创建多项式。接收输入的数据，并保存到链表中。 3．显示程序的功能表，允许使用者选择运算类型。 4．显示已经创建好的多项式。 5．实现加法运算。 6．实现减法运算。 7．实现乘法运算。 8．清除内存内容，销毁创建的链表，退出程序。 该程序实现了多项式的创建、多项式的加法、减法、乘法运算以及多项式的清除。 源程序代码： #include #include /***************以下函数实现链表的定义********************/
相关主题
文本预览