实验一一元稀疏多项式的计算一、实验目的帮助学生熟练掌握线性表的基本操作,以及用线性链表表示线性表的存储结构和操作的实现。二、实验内容实现一元稀疏多项式的如下运算:(1)两个一元稀疏多项式相加运算(2)两个一元稀疏多项式相减运算(3)两个一元稀疏多项式相乘运算三、实验仪器微型计算机实验用编程语言:TurboC2.0,BorlandC3.0等以上版本四、实验原理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所示。p2、一元稀疏多项式的链式存储表示结点结构定义如下:typedefstructItem{۸200021000301图1:一元稀疏多项式的链表表示示意图doublecoef;intexpn;structItem*next;}Item,*Polyn;3、一元稀疏多项式运算原理设有两个稀疏多项式A和B,其运算原理如下:(1)两个多项式相加(C=A+B)的运算原则:指数相同,系数相加,若不为0,则在结果多项式中构成一新项。指数不同,则两项分别抄入结果多项式中。(2)两个多项式相减(C=A-B)的运算原则:指数相同,系数相减,若不为0,则构成一新项。指数不同,对A多项式的项,直接抄入结果多项式中。对B多项式的项,系数符号变换后,再将放入结果多项式中(3)两个多项式相乘(C=A×B)的运算原则用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个。函数间的调用关系图2所示。5、程序函数(1)主函数:main功能:通过菜单选择控制对系统功能的操作(2)菜单选择函数:menu函数格式:intmenu(void)函数功能:构造功能菜单,并选择下一步要操作的功能。函数参数:无参数。函数返回值:1~11中的一个序号。可供选择的功能如下:mainnemuInputAddPolynSubtractPolynMultPolynOutputSelectDestroyPolynNotEmptyInsertLocateinsert图2:程序结构示意图ItemComp1--createP(x)表示生成P多项式2--createQ(x)表示生成Q多项式3--p(x)+Q(x)表示两多项式相加4--P(x)-Q(x)表示两多项式相减5--p(x)*Q(x)表示两多项式相乘6--printP(x)表示打印P多项式7--printQ(x)表示打印Q多项式8--printP(x)+Q(x)表示打印两多项式相加的结果9--printP(x)-Q(x)表示打印两多项式相减的结果10--printP(x)*Q(x)表示打印两多项式相乘的结果11—Quit表示退出系统,结束程序的运行在运行过程中,输入其中一个序号,即表示下一步执行后面的功能。如输入3,表示执行P(x)+(x)额运算。(3)输入多项式函数:input函数格式:PolynInput(void)函数参数:无参数函数功能:输入多项式各项的系数和指数,生成一个多项式链表。函数返回值:指向一个多项式链表的头指针(4)两多项式相加函数:AddPolyn函数格式PolynAddPolyn(Polynh1,Polynh2)函数功能:实现两个多项式h1和h2相加。函数参数:Polynh1—指向第一个多项式链表的头指针Polynh2—指向第二个多项式链表的头指针函数返回值:指向相加后的结果链表的头指针(5)两多项式相减函数:SubtractPolyn函数格式PolynSubtractPolyn(Polynh1,Polynh2)函数功能:实现两个多项式h1和h2相减。函数参数:Polynh1—指向第一个多项式链表的头指针Polynh2—指向第二个多项式链表的头指针函数返回值:指向相减后的结果链表的头指针(6)两多项式相乘函数:MultPolyn函数格式PolynMultPolyn(Polynh1,Polynh2)函数功能:实现两个多项式h1和h2相乘。函数参数:Polynh1—指向第一个多项式链表的头指针Polynh2—指向第二个多项式链表的头指针函数返回值:指向相乘后的结果链表的头指针(7)显示多项式函数:Output函数格式:voidOutput(Polynh,char*title)函数功能:输出多项式的完整表示。如:P(x)=1.00+2.50x^3-3.5x^9函数参数:Polynh-要输出的多项式链表的头指针char*title-字符串,提示要输出一个什么样的多项式,如“P(x)”。函数返回值:无返回值。(8)判断选择函数:Select函数格式:intSelect(char*str)函数功能:根据str提示的内容判断是执行指定的操作,还是不执行。输入“Y”则表示执行,若输入“N”表示不执行。如当P(x)多项式已经产生后,若再选择产生P(x),这是提示:P(x)isnotEmpty,CreateP(x)again?InputYorN:若输入“Y”则表示重新产生多项式P(x),若输入“N”表示维持原多项式不变。函数参数:char*str-将要确定的内容。函数返回值:1-表示执行指定的操作0-表示不执行指定的操作(9)插入位置定位函数:InsertLocate函数格式:intInsertLocate(Polynh,intexpn,Item**p)函数功能:确定新结点的插入位置。其插入位置的确定是保证多项式链表按指数递增排列的关键。函数参数:Polynh-要查找的多项式链表的头指针intexpn-新插入项的指数值。Item**p-插入位置的前驱结点指针,由该函数的调用而被确定的内容。新结点一定插入到该结点的后面。函数返回值:-1-若指数expn值在某两个结点之间,则返回-1,参数p带回的值为指数值小于expn的结点指针。0-若指数expn值等于某结点的指数值,则返回0,参数p带回的值为指数值等于expn的结点指针。1-若指数expn值大于最后一个结点的指数值,则返回1,参数p带回最后一个结点的指针(10)结点插入函数:insert函数格式:voidinsert(Item*pre,Item*p)函数功能:在指定结点pre后插入一个新结点p。函数参数:Item*pre-被插入结点的前驱结点Item*p-要插入的新结点函数返回值:无(11)撤消链表函数:Destroy函数格式:voidDestroy(Polynh)函数功能:释放链表所占用的存储空间函数参数:Polynh-被撤消的链表的头指针函数返回值:无(12)判链表非空函数:PolynNotEmpty函数格式:intPolynNotEmpty(Polynh,char*p)函数功能:判断链表是否非空,即代表了一个真正的多项式。函数参数:Polynh-多项式链表的头指针char*p-多项式名函数返回值:0—链表为空1—链表不为空(13)比较多项式两项关系函数:ItemComp函数格式:intItemComp(ItemxItemy)函数功能:根据两个多项式项的指数判断它们的关系。函数参数:Itemx-表示多项式项的变量Itemy-表示多项式项的变量函数返回值:-1—x项的指数小于y项的指数0—x项的指数等于y项的指数1—x项的指数大于y项的指数六、两个多项式的相乘运算算法【算法1】把Q(x)多项式的每一项分别去乘P(x)多项式的每一项所得到的每一个结果(一个结点)插入到结果多项式中,若结果多项式中无相同指数的项,则生成一个新结点插入;若有相同指数的项,则系数相加。算法如下:【算法2】把Q(x)多项式的每一项分别去乘P(x)多项式得到一个新的多项式,然后把新多项式与结果多项式相加。算法如下:函数接口:传入多项式链表指针h1,h2初始化结果多项式链表h3Pb=h2-next;Pb!=NULLLPa!=NULLLPa=h1-next;Expn=pb-expn+pa-expn;Coef=pb-coef*pa-coefInsertLocate(head,expn,&pp)CreateItem(s);s-coef=coef;s-expn=expn;insert(pp,s);pp-coef=pp-coef+pa-coefTFpa=pa-nextpb=pb-nextreturn(h3)七、思考题修改一元多项式相加运算的函数,实现:1、两个有序表合并为一个有序表。2、假设具有整数值的集合用有序的线性链表表示,实现求两个集合的联合运算,要求结果集合中不能有两个值相同的元素。八、部分函数代码函数接口:传入多项式链表指针h1,h2初始化结果多项式链表h3Pb=h2-next;Pb!=NULLLPa!=NULLLPa=h1-next;CreateItem(h4);//初始化链表h4申请结点ss-expn=pb-expn+pa-expn;s-coef=pb-coef*pa-coef把结点s插入到链表h4的尾部pa=pa-nextpb=pb-nextreturn(h3)多项式h3与h4相加,结果为h5撤消链表h3和h4,h5=h3【说明】:为了使学生掌握复杂程序设计的基本方法和程序的结构,下面给出了几乎所有的辅助函数的程序代码,学生只需要完成稀疏多项式的加、减、乘运算的程序代码编写工作。希望学生通过下面程序代码的阅读、编码、测试和运算,掌握一个完整程序的基本结构和设计一个程序的基本方法。#includestdio.h#includestdlib.h#includeconio.htypedefstructItem{doublecoef;intexpn;structItem*next;}Item,*Polyn;#defineCreateItem(p)p=(Item*)malloc(sizeof(Item));#defineDeleteItem(