《一元稀疏多项式的计算1》由会员分享，可在线阅读，更多相关《一元稀疏多项式的计算1（16页珍藏版）》请在金锄头文库上搜索。
1、实验一 一元稀疏多项式的计算一、实验目的帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。二、实验内容实现一元稀疏多项式的如下运算：(1) 两个一元稀疏多项式相加运算(2) 两个一元稀疏多项式相减运算(3) 两个一元稀疏多项式相乘运算三、实验仪器微型计算机实验用编程语言：Turbo C 2.0，Borland C 3.0等以上版本四、实验原理1、一元多项式的逻辑表示一元多项式pn(x) 可表示成 : pn(x)=p0+p1x+p2x2+,+pnxn n+1 个系数可用线性表来表示：（p0，p1，p2，, ， pn）每一项的指数i 隐含在其系数pi的序号中。一个一
2、元多项式，如果其系数不为0 的项相对于其多项式的次数（最大指数） 而言要少得多，则称该一元多项式为一元稀疏多项式。对一元稀疏多项式，若采用顺序存储结构，需 n+1个元素单元存放系数。当 n 很大且为零的系数较多时，既浪费存储空间，又浪费运算时间。如： s(x)=1+3x10000+2x20000采用顺序存储分配需20001 个元素空间， 但只有 3 个元素有意义。 若参与同数量级的加法运算，要运行2000 次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的链表表示形式如图1 所示。p 2、一元稀疏多项式的链式存储表示结点结构定义如下：typedef struct Item ?200
3、0 2 1000 3 0 1 图 1：一元稀疏多项式的链表表示示意图double coef; int expn; struct Item *next; Item,*Polyn; 3、一元稀疏多项式运算原理设有两个稀疏多项式A和 B，其运算原理如下：（1）两个多项式相加(C=AB)的运算原则：指数相同，系数相加，若不为0，则在结果多项式中构成一新项。指数不同，则两项分别抄入结果多项式中。（2）两个多项式相减(C=AB)的运算原则：指数相同，系数相减，若不为0，则构成一新项。指数不同，对A多项式的项，直接抄入结果多项式中。对 B多项式的项，系数符号变换后，再将放入结果多项式中（3）两个多项式相乘(
4、C=AB)的运算原则用 B多项式的每一项分别去乘A多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。五、实现1、约定（1） 使用带头结点的链表表示一元稀疏多项式。（2） 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。（3） 每个多项式都独立存在，即参与运算的两个多项式的数据不能应运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行表示。（4） 每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入A多项式，而A多项式已经存在，这时通过“确认”后再确定是否真正需要输入。2、基本功
5、能(1) 多项式的输入(2) 两个一元稀疏多项式相加运算：P(x)+Q(x (3) 两个一元稀疏多项式相减运算：P(x) Q(x) (4) 两个一元稀疏多项式相乘运算：P(x) Q(x) (5) 多项式打印3、辅助功能(1) 菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。(2) 插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。(3) 交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。(4) 撤消多项式：释放表示多项式链表中所有结点的存储空间。(5) 多项式项插入：将表示多项式中一项的结
6、点插入到链表中给定的位置。(6) 判多项式非空：判断某个多项式是否存在。(7) 判断两个多项式的当前运算项的关系（指数大于，等于，小于）4、程序结构本程序可以由13 个函数组成，其中主函数1 个，基本功能函数5 个，辅助功能函数7 个。函数间的调用关系图2 所示。5、程序函数（1）主函数： main 功能：通过菜单选择控制对系统功能的操作（2）菜单选择函数：menu 函数格式： int menu(void) 函数功能：构造功能菜单，并选择下一步要操作的功能。函数参数：无参数。函数返回值：111 中的一个序号。可供选择的功能如下：main nemu Input AddPolyn Subtract
7、Polyn MultPolyn Output Select Destroy PolynNotEmpty InsertLocate insert 图 2：程序结构示意图ItemComp 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) 表示打印两多项式相减的结果
8、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 h
9、1 指向第一个多项式链表的头指针Polyn h2 指向第二个多项式链表的头指针函数返回值：指向相加后的结果链表的头指针(5) 两多项式相减函数： SubtractPolyn 函数格式 Polyn SubtractPolyn(Polyn h1,Polyn h2) 函数功能：实现两个多项式h1 和 h2 相减。函数参数： Polyn h1 指向第一个多项式链表的头指针Polyn h2 指向第二个多项式链表的头指针函数返回值：指向相减后的结果链表的头指针(6) 两多项式相乘函数： MultPolyn 函数格式 Polyn MultPolyn(Polyn h1,Polyn h2) 函数功能：实现两个多
10、项式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
11、 *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 e
12、xpn,Item *p) 函数功能：确定新结点的插入位置。其插入位置的确定是保证多项式链表按指数递增排列的关键。函数参数： Polyn h 要查找的多项式链表的头指针int expn新插入项的指数值。Item *p插入位置的前驱结点指针，由该函数的调用而被确定的内容。新结点一定插入到该结点的后面。函数返回值：-1若指数expn 值在某两个结点之间，则返回1，参数 p 带回的值为指数值小于expn 的结点指针。0若指数 expn 值等于某结点的指数值，则返回0，参数 p 带回的值为指数值等于expn 的结点指针。1若指数 expn 值大于最后一个结点的指数值，则返回1，参数p 带回最后一个结点的
13、指针（ 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) 函数功能：判
14、断链表是否非空，即代表了一个真正的多项式。函数参数： Polyn h 多项式链表的头指针char *p 多项式名函数返回值：0链表为空1链表不为空(13)比较多项式两项关系函数：ItemComp 函数格式： int ItemComp(Item x Item y) 函数功能：根据两个多项式项的指数判断它们的关系。函数参数： Item x 表示多项式项的变量Item y 表示多项式项的变量函数返回值：-1 x 项的指数小于y 项的指数0x 项的指数等于y 项的指数1x 项的指数大于y 项的指数六、两个多项式的相乘运算算法【算法 1】把 Q(x) 多项式的每一项分别去乘P(x) 多项式的每一项所得到
15、的每一个结果（一个结点） 插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个新结点插入；若有相同指数的项，则系数相加。算法如下：【算法 2】把 Q(x) 多项式的每一项分别去乘P(x) 多项式得到一个新的多项式，然后把新多项式与结果多项式相加。算法如下：函数接口： 传入多项式链表指针h1,h2 初始化结果多项式链表h3 Pb=h2-next; Pb!=NULLL Pa!=NULLL Pa=h1-next; Expn=pb-expn+pa-expn; Coef=pb-coef*pa-coef InsertLocate(head,expn,s-coef=coef; s-expn=expn; pp-coef=pp-coef+pa-co ef T F pa=pa-next pb=pb-next return(h3) 七、思考题修改一元多项式相加运算的函数，实现：1、 两个有序表合并为一个有序表。2、 假设具有整数值的集合用有序的线性链表表示，实现求两个集合的联合运算，要求结果集合中不能有两个值相同的元素。八、部分函数代码函数接口： 传入多项式链表指针h1,h2 初始化结果多项式链表h3 Pb=h2-next; Pb!=NULLL Pa!=NULLL Pa=h1-next; CreateItem(h4);/初始化链表h4 申请结点s s-expn
