元稀疏多项式的计算

1、实验二一兀稀疏多项式的计算一、实验目的帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现二、实验内容实现一元稀疏多项式的如下运算：(1) 两个一元稀疏多项式相加运算(2) 两个一元稀疏多项式相减运算(3) 两个一元稀疏多项式相乘运算三、实验仪器微型计算机实验用编程语言：Turbo C 2.0 ，Borland C 3.0 等以上版本四、实验原理1、一元多项式的逻辑表示兀多项式Pn(X)可表示成：2nP n(X)=P 0+P1X+P2X +, +pnXn+1个系数可用线性表来表示：(po, P1, P2, , ,Pn)每一项的指数i隐含在其系数pi的序号中一个一元多

2、项式，如果其系数不为0的项相对于其多项式的次数(最大指数)而言要少 得多，则称该一元多项式为一元稀疏多项式对一元稀疏多项式，若采用顺序存储结构，需n+1个元素单元存放系数.当n很大且为零的系数较多时，既浪费存储空间，又浪费运算时间如: s(x)=1+3x 10000+ 2x20000采用顺序存储分配需20001个元素空间，但只有 3个元素有意义若参与同数量级的加法运算，要运行2000次以上.因此，对一元多项式采用链式存储结构是必然的选择上例的链表表示形式如图1所示图1: 一元稀疏多项式的链表表示示意图2、一元稀疏多项式的链式存储表示结点结构定义如下：typedef struct ltemdou

3、ble coef;int expn;struct Item *next; Item,*Polyn;3、一元稀疏多项式运算原理设有两个稀疏多项式 A和B,其运算原理如下：( 1)两个多项式相加 (C=AB) 的运算原则： 指数相同，系数相加，若不为 0，则在结果多项式中构成一新项 . 指数不同，则两项分别抄入结果多项式中 .( 2)两个多项式相减 (C=A B) 的运算原则： 指数相同，系数相减，若不为 0，则构成一新项 .指数不同，对 A多项式的项，直接抄入结果多项式中 对B多项式的项，系数符号变换后，再将放入结果多项式中(3) 两个多项式相乘(C=AX B)的运算原则用B多项式的每一项分别去

4、乘A多项式的每一项，并将乘得得结果放入结果多项式中 .若结果多项式中有指数相同的项，则应把它们合并为一项 .五、实现1、 约定 使用带头结点的链表表示一元稀疏多项式.(2) 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列.( 3) 每个多项式都独立存在， 即参与运算的两个多项式的数据不能应运算而受到破坏， 加、减、乘运算的结果应相互不受影响 . 因此，对于每种情况都必须单独建立一个链表进行 表示 .(4) 每一种重复性的操作都要进行确认，以免破坏原有操作的结果如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入2、基本功能(1) 多项式的输入(2) 两个一

5、元稀疏多项式相加运算：P(x)+Q(x(3) 两个一元稀疏多项式相减运算：P(x) Q(x)(4) 两个一元稀疏多项式相乘运算：P(x) X Q(x)(5) 多项式打印3、辅助功能(1) 菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式 控制程序运行 .(2) 插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列(3) 交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是 否进行(4) 撤消多项式：释放表示多项式链表中所有结点的存储空间(5) 多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置.(6) 判多

6、项式非空：判断某个多项式是否存在.(7) 判断两个多项式的当前运算项的关系(指数大于，等于，小于)4、程序结构1个，基本功能函数 5个，辅助功能函数本程序可以由13个函数组成，其中主函数7个.函数间的调用关系图 2所示.步要操作的功能表示生成P多项式表示生成Q多项式表示两多项式相加表示两多项式相减表示两多项式相乘表示打印P多项式表示打印Q多项式表示打印两多项式相加的结果表示打印两多项式相减的结果(2)菜单选择函数：me nu函数格式：int me nu (void)函数功能：构造功能菜单，并选择下函数参数：无参数.函数返回值：111中的一个序号 可供选择的功能如下：1-create P(x)2

7、-create Q(x)3_p(x)+Q(x)4- -P(x)-Q(x)5- -p(x)*Q(x)6- -pri nt P(x)7- -pri nt Q(x)8- -pri nt P(x)+Q(x)9- -pri nt P(x)-Q(x)10-print P(x)*Q(x)表示打印两多项式相乘的结果11 Quit 表示退出系统，结束程序的运行 在运行过程中，输入其中一个序号，即表示下一步执行后面的功能 . 如输入 3， 表示执行 P(x)+(x) 额运算 .(3) 输入多项式函数： input 函数格式： Polyn Input(void) 函数参数：无参数 函数功能：输入多项式各项的系数和指

8、数，生成一个多项式链表 . 函数返回值：指向一个多项式链表的头指针(4) 两多项式相加函数： AddPolyn 函数格式 Polyn AddPolyn(Polyn h1,Polyn h2) 函数功能：实现两个多项式 h1 和 h2 相加 . 函数参数： Polyn h1 指向第一个多项式链表的头指针Polyn h2 指向第二个多项式链表的头指针 函数返回值：指向相加后的结果链表的头指针(5) 两多项式相减函数： SubtractPolyn 函数格式 Polyn SubtractPolyn(Polyn h1,Polyn h2) 函数功能：实现两个多项式 h1 和 h2 相减 . 函数参数： Po

9、lyn 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) 函数功能：输出多项式的完整

10、表示 . 如：P(x)=1.00+2.50xA3-3.5xA9函数参数： 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:若输入

11、“ Y”则表示重新产生多项式P(x)，若输入“ N”表示维持原多项式不变 .函数参数： char *str 将要确定的内容 .函数返回值：1表示执行指定的操作0表示不执行指定的操作(9) 插入位置定位函数： InsertLocate函数格式： int InsertLocate(Polyn h,int expn,Item *p)函数功能： 确定新结点的插入位置 . 其插入位置的确定是保证多项式链表按指数 递增排列的关键 .函数参数： Polyn h 要查找的多项式链表的头指针int expn 新插入项的指数值 .Item *p 插入位置的前驱结点指针，由该函数的调用而被确定的 内容.新结点一定插

12、入到该结点的后面 .函数返回值：-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 要插入的新结点函数返回值：无( 1

13、1 )撤消链表函数： 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

14、y) 函数功能：根据两个多项式项的指数判断它们的关系 . 函数参数： Item x 表示多项式项的变量 Item y 表示多项式项的变量函数返回值： -1x 项的指数小于 y 项的指数0 x 项的指数等于 y 项的指数1x项的指数大于y项的指数六、两个多项式的相乘运算算法【算法1】把Q(x)多项式的每一项分别去乘 P(x)多项式的每一项所得到的每一个结果 (一个结点) 插入到结果多项式中， 若结果多项式中无相同指数的项， 则生成一个新结点插 入；若有相同指数的项，则系数相加 . 算法如下：pb=pb->n ext【算法2】把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式，

15、然后把新多项式与结果多项式相加算法如下:return(h3)申请结点ss->exp n=pb_>exp n+pa_>exp n; s->coef=pb->coef*pa->coef把结点s插入到链表沁4t的尾部多项式h3与h4相加，结果为h51r撤消链表h3和h4, h5=>h3pb=pb-,n ext七、思考题修改一元多项式相加运算的函数，实现：1、两个有序表合并为一个有序表 2、假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求结果集合中不能有两个值相同的元素八、部分函数代码【说明】：为了使学生掌握复杂程序设计的基本方法和程序

16、的结构，下面给出了几乎所有的辅助函数的程序代码，学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作 希望学生通过下面程序代码的阅读、编码、测试和运算，掌握一个完整程序的基本结构和设计一个程序的基本方法#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <coni o.h> typedef struct Itemdouble coef;int expn; struct Item *next;Item,*Polyn;#define CreateItem(p) p=(Item *)malloc(sizeof(I

17、tem);#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'

18、;|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 i

19、nsert(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(e

20、xpn=-1) break; / if(InsertLocate(h,expn,&pp)/ CreateItem(p);p->coef=coef;输入多项式的系数和指数 若指数为 1，表示输入结束 返回值非 0 表示插入新结点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,

21、*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 prin tf("%.2lfxA%d",p->coef,p->

22、;exp n);else if(p->coef>0) printf("+");if(p->expn=0)printf("%.2lf",p->coef);else prin tf("%.2lfxA%d",p->coef,p->exp n);p=p->next;printf("n");/*/* 判断两个多项式项的关系 */*/ int ItemComp(Item x,Item y) if(x.expn<y.expn)return(-1);else if(x.expn=y.

23、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; Createltem(head);last=head;*/*两多项式多项式相减*/实现两个多项式相加运算的代码st->n ext=NULL;Xurn head;（由学生独立完成）Polyn SubtractPolyn(Polyn h1,Polyn h2) int flag;Item *head

24、,*last,*pa=h1-> next,*pb=h2-> next,*s,*sO;double coef;CreateItem(head);last=head;/*两多项式多项式相乘*/st->n ext=NULL;Xurn head;实现两个多项式相减运算的代码 （由学生独立完成）/*/Poly n MultPoly n(Polyn h1,Poly n h2) /两个多项式相乘 int item,exp n;Item *head,*pa,*pb=h2->n ext,*s,*pp;double coef;CreateItem(head);/*head-> nex

25、t=NULL;?turn head;实现两个多项式相乘运算的代码 （由学生独立完成）*/*菜单选择*/int menu (void) int num;clrscr();printf("%20c1-create P(x)n",'');prin tf("%20c2-create Q(x)n",'');printf("%20c3-p(x)+Q(x)n",'');printf("%20c4-P(x)-Q(x)n",'');printf("%20c5-

26、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",' ');

27、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();r

28、eturn(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,Cre

29、ate 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(

30、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 finish