一元稀疏多项式的计算.doc

!-实验一 一元稀疏多项式的计算一、实验目的通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。二、实验内容实现一元稀疏多项式的如下运算：(1)两个一元稀疏多项式相加运算(2)两个一元稀疏多项式相减运算(3)两个一元稀疏多项式相乘运算三、实验原理1、一元多项式的逻辑表示一元多项式pn(x)可表示成:pn(x)=p0+p1x+p2x2+pnxnn+1个系数可用线性表来表示：p0，p1，p2，pn）其中每一项的指数i隐含在其系数pi的序号中。一个一元多项式，如果其系数不为0的项相对于其多项式的次数（最大指数）而言要少得多，则称该一元多项式为一元稀疏多项式。对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数。当n很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。如：s(x)=1+3x10000+2x20000 采用顺序存储分配需20001个元素空间，但只有3个元素有意义。若参与同数量级的加法运算，要运行2000次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的链表表示形式如图1-1所示。011000320002p图1-1：一元稀疏多项式的链表表示示意图 2、一元稀疏多项式的链式存储表示结点结构定义如下：typedef struct Itemdouble coef;int expn;struct Item *next;Item,*Polyn;3、一元稀疏多项式运算原理设有两个稀疏多项式A和B，其运算原理如下：（1）两个多项式相加(C=AB)的运算原则：指数相同，系数相加，若不为0，则在结果多项式中构成一新项。指数不同，则两项分别抄入结果多项式中。（2）两个多项式相减(C=AB)的运算原则：指数相同，系数相减，若不为0，则构成一新项。指数不同，对A多项式的项，直接抄入结果多项式中。对B多项式的项，系数符号变换后，再将放入结果多项式中（3）两个多项式相乘(C=AB)的运算原则用B多项式的每一项分别去乘A多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。四、实现1、约定（1） 使用带头结点的链表表示一元稀疏多项式。（2） 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。（3） 每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行表示。（4） 每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入。2、基本功能(1)多项式的输入(2)两个一元稀疏多项式相加运算：P(x)+Q(x(3)两个一元稀疏多项式相减运算：P(x)Q(x)(4)两个一元稀疏多项式相乘运算：P(x)Q(x)(5)多项式打印3、辅助功能(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。(6)判多项式非空：判断某个多项式是否存在。(7)判断两个多项式的当前运算项的关系（指数大于，等于，小于）4、程序结构 本程序可以由13个函数组成，其中主函数1个，基本功能函数5个，辅助功能函数7个。函数间的调用关系图1-2所示。mainnemuInput AddPolyn SubtractPolyn MultPolyn Output Select DestroyPolynNotEmptyInsertLocate insert ItemComp图1-2：程序结构示意图5、程序函数（1）主函数：main 功能：通过菜单选择控制对系统功能的操作（2）菜单选择函数：menu函数格式： int menu(void)函数功能：构造功能菜单，并选择下一步要操作的功能。函数参数：无参数。函数返回值：111中的一个序号。可供选择的功能如下：1-create P(x) 表示生成P多项式2-create Q(x) 表示生成Q多项式3-p(x)+Q(x) 表示两多项式相加4-P(x)-Q(x) 表示两多项式相减5-p(x)*Q(x) 表示两多项式相乘6-print P(x) 表示打印P多项式7-print Q(x) 表示打印Q多项式8-print P(x)+Q(x) 表示打印两多项式相加的结果9-print P(x)-Q(x) 表示打印两多项式相减的结果10-print P(x)*Q(x) 表示打印两多项式相乘的结果11Quit 表示退出系统，结束程序的运行在运行过程中，输入其中一个序号，即表示下一步执行后面的功能。如输入3，表示执行P(x)+(x)额运算。(3)输入多项式函数：input函数格式：Polyn Input(void)函数参数：无参数函数功能：输入多项式各项的系数和指数，生成一个多项式链表。函数返回值：指向一个多项式链表的头指针(4)两多项式相加函数： AddPolyn函数格式 Polyn AddPolyn(Polyn h1,Polyn h2)函数功能：实现两个多项式h1和h2相加。函数参数：Polyn h1指向第一个多项式链表的头指针Polyn h2指向第二个多项式链表的头指针函数返回值：指向相加后的结果链表的头指针(5)两多项式相减函数： SubtractPolyn函数格式 Polyn SubtractPolyn(Polyn h1,Polyn h2)函数功能：实现两个多项式h1和h2相减。函数参数：Polyn h1指向第一个多项式链表的头指针Polyn h2指向第二个多项式链表的头指针函数返回值：指向相减后的结果链表的头指针(6)两多项式相乘函数： MultPolyn函数格式 Polyn MultPolyn(Polyn h1,Polyn h2)函数功能：实现两个多项式h1和h2相乘。函数参数：Polyn h1指向第一个多项式链表的头指针Polyn h2指向第二个多项式链表的头指针函数返回值：指向相乘后的结果链表的头指针(7)显示多项式函数：Output函数格式：void Output(Polyn h,char *title)函数功能：输出多项式的完整表示。如： P(x)=1.00+2.50x3-3.5x9函数参数：Polyn h要输出的多项式链表的头指针 char *title字符串，提示要输出一个什么样的多项式，如“P(x)”。函数返回值：无返回值。(8)判断选择函数：Select函数格式：int Select(char *str)函数功能：根据str提示的内容判断是执行指定的操作，还是不执行。输入“Y”则表示执行，若输入“N”表示不执行。如当P(x)多项式已经产生后，若再选择产生P(x)，这是提示：P(x) is not Empty,Create P(x) again?Input Y or N:若输入“Y”则表示重新产生多项式P(x)，若输入“N”表示维持原多项式不变。函数参数：char *str将要确定的内容。函数返回值：1表示执行指定的操作0表示不执行指定的操作(9)插入位置定位函数：InsertLocate函数格式： int InsertLocate(Polyn h,int expn,Item *p)函数功能：确定新结点的插入位置。其插入位置的确定是保证多项式链表按指数递增排列的关键。函数参数：Polyn h要查找的多项式链表的头指针int expn新插入项的指数值。Item *p插入位置的前驱结点指针，由该函数的调用而被确定的内容。新结点一定插入到该结点的后面。函数返回值：-1若指数expn值在某两个结点之间，则返回1，参数p带回的值为指数值小于expn的结点指针。0若指数expn值等于某结点的指数值，则返回0，参数p带回的值为指数值等于expn的结点指针。1若指数expn值大于最后一个结点的指数值，则返回1，参数p带回最后一个结点的指针（10）结点插入函数：insert函数格式：void insert(Item *pre,Item *p)函数功能：在指定结点pre后插入一个新结点p。函数参数：Item *pre被插入结点的前驱结点Item *p要插入的新结点函数返回值：无（11）撤消链表函数：Destroy函数格式：void Destroy(Polyn h)函数功能：释放链表所占用的存储空间函数参数：Polyn h被撤消的链表的头指针函数返回值：无（12）判链表非空函数： PolynNotEmpty函数格式：int PolynNotEmpty(Polyn h,char *p)函数功能：判断链表是否非空，即代表了一个真正的多项式。函数参数：Polyn h多项式链表的头指针char *p多项式名函数返回值：0链表为空1链表不为空(13)比较多项式两项关系函数：ItemComp函数格式：int ItemComp(Item x Item y)函数功能：根据两个多项式项的指数判断它们的关系。函数参数：Item x表示多项式项的变量Item y表示多项式项的变量函数返回值：-1x项的指数小于y项的指数0x项的指数等于y项的指数1x项的指数大于y项的指数五、部分算法描述两个多项式相加运算的算法参见教科书的描述。两个多项式相减运算算法与多项式相加运算的算法结构一致，只是把Q(x)多项式的结点作为独立的一项时，其系数应改变其正/负号。这里只对两个多项式相乘运算的算法加以描述。两个多项式相乘运算的基本原理是：用Q(x)多项式的每一项分别去乘P(x)多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。这实际上是运用加法运算来实现乘法运算，实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。【算法1】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式的每一项所得到的每一个结果（一个结点）插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个新结点插入；若有相同指数的项，则系数相加。算法如图1-3所示。函数接口：传入多项式链表指针h1,h2初始化结果多项式链表h3Pb=h2->next;Pa=h1->next; Expn=pb->expn+pa->expn;Coef=pb->coef*pa->coefCreateItem(s); s->coef=coef;s->expn=expn;insert(pp,s);While(Pb)While(Pa)InsertLocate(head,expn,&pp)pp->coef=pp->coef+pa->coefpa=pa->nextpb=pb->nextreturn(h3)图1-3 两个多项式相乘算法1描述【算法2】基本思想：把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式，然后把新多项式与结果多项式相加。算法如图3所示。函数接口：传入多项式链表指针h1,h2初始化结果多项式链表h3Pb=h2->next;pa=pa->nextWhile(Pb)While(Pa)return(h3)Pa=h1->next; CreateItem(h4);/初始化链表h4申请结点ss->expn=pb->expn+pa->expn;s->coef=pb->coef*pa->coef把结点s插入到链表h4的尾部pb=pb->next多项式h3与h4相加，结果为h5撤消链表h3和h4，h5=>h3图1-4 两个多项式相乘算法2描述七、思考题 修改一元多项式相加运算的函数，实现：1、 两个有序表合并为一个有序表。2、 假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求结果集合中不能有两个值相同的元素。八、部分函数代码【说明】：为了使学生掌握复杂程序设计的基本方法和程序的结构，下面给出了几乎所有的辅助函数的程序代码，学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。希望学生通过下面程序代码的阅读、编码、测试和运算，掌握一个完整程序的基本结构和设计一个程序的基本方法。#include <stdio.h>#include <stdlib.h>#include <conio.h>typedef struct Item double coef; int expn; struct Item *next; Item,*Polyn;#define CreateItem(p) p=(Item *)malloc(sizeof(Item);#define DeleteItem(p) free(void *)p);/*/* 判断选择函数 */*/int Select(char *str) char ch; printf("%sn",str); printf("Input Y or N:"); do ch=getch();while(ch!=Y&&ch!=y&&ch!=N&&ch!=n); printf("n"); if(ch=Y|ch=y) return(1); else return(0); /*/* 插入位置定位函数 */*/int InsertLocate(Polyn h,int expn,Item *p) Item *pre,*q; pre=h; q=h->next; while(q&&q->expn<expn) pre=q; q=q->next; if(!q) *p=pre; return(1); else if(q->expn=expn) *p=q; return(0); else *p=pre; return(-1); /*/* 插入结点函数 */*/void insert(Item *pre,Item *p) p->next=pre->next; pre->next=p; /*/* 输入多项式 */*/Polyn Input(void) double coef; int expn,flag; Item *h,*p,*q,*pp; CreateItem(h);/产生头结点 h->next=NULL; printf("input coef and expn(if end ,expn=-1)n"); while(1) scanf("%lf%d",&coef,&expn); /输入多项式的系数和指数 if(expn=-1) break; /若指数为1，表示输入结束 if(InsertLocate(h,expn,&pp)/返回值非0表示插入新结点 CreateItem(p); p->coef=coef; p->expn=expn; insert(pp,p); else if(Select("has the same expn,Replace older value?") pp->coef=coef; /指数相同，替换系数 return h; /*/* 撤消多项式 */*/void Destroy(Polyn h) Item *p=h,*q; while(p!=NULL) q=p; p=p->next; DeleteItem(q); /*/* 输出多项式 */*/void Output(Polyn h,char *title) int flag=1; Item *p=h->next; printf("%s=",title); while(p) if(flag) /表示是否是多项式的第一项 flag=0; if(p->expn=0) printf("%.2lf",p->coef); else printf("%.2lfx%d",p->coef,p->expn); else if(p->coef>0) printf("+"); if(p->expn=0) printf("%.2lf",p->coef); else printf("%.2lfx%d",p->coef,p->expn); p=p->next; printf("n"); /*/* 判断两个多项式项的关系 */*/int ItemComp(Item x,Item y) if(x.expn<y.expn) return(-1); else if(x.expn=y.expn) return(0); else return(1); /*/* 两多项式多项式相加 */*/Polyn AddPolyn(Polyn h1,Polyn h2) Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0; double coef; CreateItem(head); last=head; 实现两个多项式相加运算的代码（由学生独立完成） last->next=NULL; return head; /*/* 两多项式多项式相减 */*/Polyn SubtractPolyn(Polyn h1,Polyn h2) int flag; Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0; double coef; CreateItem(head); last=head;实现两个多项式相减运算的代码（由学生独立完成） last->next=NULL; return head; /*/* 两多项式多项式相乘 */*/Polyn MultPolyn(Polyn h1,Polyn h2) /两个多项式相乘 int item,expn; Item *head,*pa,*pb=h2->next,*s,*pp; double coef; CreateItem(head); head->next=NULL;实现两个多项式相乘运算的代码（由学生独立完成） return head; /*/* 菜单选择 */*/int menu(void) int num; clrscr(); printf("%20c1-create P(x)n", ); printf("%20c2-create Q(x)n", ); printf("%20c3-p(x)+Q(x)n", ); printf("%20c4-P(x)-Q(x)n", ); printf("%20c5-p(x)*Q(x)n", ); printf("%20c6-print P(x)n", ); printf("%20c7-print Q(x)n", ); printf("%20c8-print P(x)+Q(x)n", ); printf("%20c9-print P(x)-Q(x)n", ); printf("%20c10-print P(x)*Q(x)n", ); printf("%20c11-Quitn", ); printf(" please select 1,2,3,4,5,6,7,8,9,10,11:"); do scanf("%d",&num); while(num<1 | num>11); return(num); /*/* 判断多项式是否存在 */*/int PolynNotEmpty(Polyn h,char *p) if(h=NULL) printf("%s is not exist!n",p); getchar();return(0); else return(1); /*/* 主函数 */*/void main() int num; Polyn h1=NULL; /p(x) Polyn h2=NULL; /Q(x) Polyn h3=NULL; /P(x)+Q(x) Polyn h4=NULL; /P(x)-Q(x) Polyn h5=NULL; /P(x)*Q(x) while(1) num=menu(); getchar(); switch(num) case 1: /输入第一个多项式，若多项式存在，首先撤消然后再输入 if(h1!=NULL) if(Select("P(x) is not Empty,Create P(x) again?") Destroy(h1); h1=Input(); else h1=Input(); break; case 2: /输入第二个多项式，若多项式存在，首先撤消然后再输入 if(h2!=NULL) if(Select("Q(x) is not Empty,Create Q(x) again?") Destroy(h2); h2=Input(); else h2=Input(); break; case 3: /两多项式相加 if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)") h3=AddPolyn(h1,h2); Output(h3,"P(x)+Q(X)"); printf("P(x)+Q(x) has finished!n"); getchar(); break; case 4: /两多项式相减 if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)") h4=SubtractPolyn(h1,h2); Output(h4,"Px)-Q(x)"); printf("P(x)-Q(x) has finished!n");getchar(); break; case 5: /两多项式相乘 if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)") h5=MultPolyn(h1,h2); Output(h5,"P(x)*Q(x)"); printf("P(x)*Q(x) has finished!n"); getchar(); break; case 6: /显示第一个多项式 if(PolynNotEmpty(h1,"p(x)") Output(h1,"P(x)"); getchar(); break; case 7: /显示第二个多项式 if(PolynNotEmpty(h2,"Q(x)") Output(h2,"Q(x)");getchar(); break; case 8: /显示相加结果多项式 if(PolynNotEmpty(h3,"P(x)+Q(x)") Output(h3,"P(x)+Q(x)");getchar(); break; case 9: /显示相减结果多项式 if(PolynNotEmpty(h4,"P(x)-Q(x)") Output(h3,"P(x)-Q(x)");getchar(); break; case 10: /显示相乘结果多项式 if(PolynNotEmpty(h5,"P(x)*Q(x)") Output(h3,"P(x)*Q(x)");getchar(); break; case 11: /结束程序运行。结束前应先撤消已存在的多项式 if(h1!=NULL) Destroy(h1); if(h2!=NULL) Destroy(h2); if(h3!=NULL) Destroy(h3); if(h4!=NULL) Destroy(h4); if(h4!=NULL) Destroy(h4); if(h4!=NULL) Destroy(h5); if(num=11) break; getch();