测试一 一元稀疏多项式的计算

《测试一 一元稀疏多项式的计算》由会员分享，可在线阅读，更多相关《测试一 一元稀疏多项式的计算（16页珍藏版）》请在金锄头文库上搜索。

1、 2 实验一实验一 一元稀疏多项式的计算一元稀疏多项式的计算 一、实验目的一、实验目的 通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构和操作的实现。 二、实验内容二、实验内容 实现一元稀疏多项式的如下运算： (1)两个一元稀疏多项式相加运算 (2)两个一元稀疏多项式相减运算 (3)两个一元稀疏多项式相乘运算 三、实验原理三、实验原理 1、一元多项式的逻辑表示 1、一元多项式的逻辑表示 一元多项式 pn(x)可表示成: pn(x)=p0+p1x+p2x2+pnxn n+1 个系数可用线性表来表示： p0，p1，p2，pn） 其中每一项的指数

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

3、疏多项式的链式存储表示 结点结构定义如下： typedef struct Item double coef; 200021000301图 1-1： 一元稀疏多项式的链表表示示意图3 int expn; struct Item *next; Item,*Polyn; 3、一元稀疏多项式运算原理、一元稀疏多项式运算原理 设有两个稀疏多项式 A 和 B，其运算原理如下： （1）两个多项式相加(C=AB)的运算原则： 指数相同，系数相加，若不为 0，则在结果多项式中构成一新项。 指数不同，则两项分别抄入结果多项式中。 （2）两个多项式相减(C=AB)的运算原则： 指数相同，系数相减，若不为 0，则构成

4、一新项。 指数不同，对 A 多项式的项，直接抄入结果多项式中。 对 B 多项式的项，系数符号变换后，再将放入结果多项式中 （3）两个多项式相乘(C=AB)的运算原则 用 B 多项式的每一项分别去乘 A 多项式的每一项， 并将乘得得结果放入结果多项式中。 若结果多项式中有指数相同的项，则应把它们合并为一项。 四、实现四、实现 1、约定、约定使用带头结点的链表表示一元稀疏多项式。 （2） 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。 （3） 每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个

5、链表进行表示。 （4） 每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入 A 多项式，而 A 多项式已经存在，这时通过“确认”后再确定是否真正需要输入。 2、基本功能、基本功能 (1)多项式的输入 (2)两个一元稀疏多项式相加运算：P(x)+Q(x (3)两个一元稀疏多项式相减运算：P(x)Q(x) (4)两个一元稀疏多项式相乘运算：P(x)Q(x) (5)多项式打印 3、辅助功能、辅助功能 (1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。 4 (2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数

6、升序排列。 (3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。 (4)撤消多项式：释放表示多项式链表中所有结点的存储空间。 (5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。 (6)判多项式非空：判断某个多项式是否存在。 (7)判断两个多项式的当前运算项的关系（指数大于，等于，小于） 4、程序结构、程序结构 本程序可以由 13 个函数组成，其中主函数 1 个，基本功能函数 5 个，辅助功能函数 7个。函数间的调用关系图 1-2 所示。 5、程序函数、程序函数 （1）主函数：main 功能：通过菜单选择控制对系统功能的操作 （2）菜单选择函数：m

7、enu 函数格式： int menu(void) 函数功能：构造功能菜单，并选择下一步要操作的功能。 函数参数：无参数。 mainnemu Input AddPolyn SubtractPolyn MultPolyn Output Select DestroyPolynNotEmpty InsertLocate insert 图 1-2：程序结构示意图 ItemComp 5 函数返回值：111 中的一个序号。 可供选择的功能如下： 1-create P(x) 表示生成 P 多项式 2-create Q(x) 表示生成 Q 多项式 3-p(x)+Q(x) 表示两多项式相加 4-P(x)-Q(x)

8、 表示两多项式相减 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) 函数参数：无参数

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

10、 相减。 函数参数：Polyn h1指向第一个多项式链表的头指针 Polyn h2指向第二个多项式链表的头指针 函数返回值：指向相减后的结果链表的头指针 (6)两多项式相乘函数： MultPolyn 函数格式 Polyn MultPolyn(Polyn h1,Polyn h2) 函数功能：实现两个多项式 h1 和 h2 相乘。 函数参数：Polyn h1指向第一个多项式链表的头指针 6 Polyn h2指向第二个多项式链表的头指针 函数返回值：指向相乘后的结果链表的头指针 (7)显示多项式函数：Output 函数格式：void Output(Polyn h,char *title) 函数功能：

11、输出多项式的完整表示。如： 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

12、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插入位置的前驱结点指针，由该函数的调用而被确定的内容。新结点一

13、定插入到该结点的后面。 函数返回值：-1若指数 expn 值在某两个结点之间，则返回1，参数 p 带回的值为指数值小于 expn 的结点指针。 0若指数 expn 值等于某结点的指数值，则返回 0，参数 p 带回的值为指数值等于 expn 的结点指针。 1若指数 expn 值大于最后一个结点的指数值， 则返回 1， 参数 p带回最后一个结点的指针 （10）结点插入函数：insert 7 函数格式：void insert(Item *pre,Item *p) 函数功能：在指定结点 pre 后插入一个新结点 p。 函数参数：Item *pre被插入结点的前驱结点 Item *p要插入的新结点 函数

14、返回值：无 （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 I

15、tem y) 函数功能：根据两个多项式项的指数判断它们的关系。 函数参数：Item x表示多项式项的变量 Item y表示多项式项的变量 函数返回值：-1x 项的指数小于 y 项的指数 0x 项的指数等于 y 项的指数 1x 项的指数大于 y 项的指数 五、部分算法描述五、部分算法描述 两个多项式相加运算的算法参见教科书的描述。 两个多项式相减运算算法与多项式相加运算的算法结构一致， 只是把 Q(x)多项式的结点作为独立的一项时，其系数应改变其正/负号。 这里只对两个多项式相乘运算的算法加以描述。两个多项式相乘运算的基本原理是：用Q(x)多项式的每一项分别去乘 P(x)多项式的每一项，并将乘得得结果放入结果多项式中。若结果多项式中有指数相同的项，则应把它们合并为一项。这实际上是运用加法运算来实现乘法运算，实现时有两种不同的方法把每次计算的结果与原来的中间结果进行相加。 【算法 1】基本思想：把 Q(x)多项式的每一项分别去乘 P(x)多项式的每一项所得到的每一个结果（一个结点）插入到结果多项式中，若结果多项式中无相同指数的项，则生成一个8 新结点插入；若有相同指数的项，则系数相加。算法如图 1-3 所示。 【算法 2】基本思想：把 Q(x)多项式的每一项分别去乘 P(x)多项式得到一个新的多项式，然后把新多项式与结果多项式相加。算法如图 3 所示。函数接口