当前位置：文档之家 › 用广义表实现一元多项式的乘法

用广义表实现一元多项式的乘法

  • 格式：doc
  • 大小：603.50 KB
  • 文档页数：26

《用广义表实现一元多项式乘法》 第 - 1 - 页 共 26 页

用广义表实现一元多项式乘法

学生姓名：XXX 指导教师：XXX 摘 要 本课程设计主要解决在数学领域的一元多项式运算中，对一元多项式进行处理的算法。其中包括了一些较为简单的运算，如两个一元多项式的加法、减法和乘法。在课程设计中，系统开发平台为WindowsXP，程序设计设计语言采用C语言，程序运行平台为VC。在程序设计中，利用广义表中的线性链表，采用了定义一种新的数据结构和分装函数两种解决问题的方法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在数学领域的一元多项式中解决实际问题。

关键词 线性链表 ；新的数据结构；一元多项式 《用广义表实现一元多项式乘法》 第 - 2 - 页 共 26 页 1 引 言 .................................................. - 3 -

1.1 课题背景及意义 ....................................... - 3 - 1.2 课题实现技术的简要说明 ............................... - 3 - 1.3 可行性分析 ........................................... - 4 - 2 系统需求分析 ........................................... - 5 - 2.1功能需求分析 .......................................... - 5 - 2.2 性能需求分析 ......................................... - 4 - 2.3系统总体结构设计 ........................ 错误！未定义书签。 2.4系统管理流程图 .......................... 错误！未定义书签。 3 用广义表对一元多项式处理的系统设计 ...................... - 5 - 3.1 系统功能模块分析 ................................................ 错误！未定义书签。 4 详细设计 .................................................................................................. - 9 - 4.1 数据结构的设计 .................................................... 错误！未定义书签。 4.2用户使用目录界面 ............................................................................... - 9 - 4.3一元多项式的输入和输出功能模块 ................................................... - 9 - 4.4一元多项式的加法处理模块 ............................. - 10 - 4.5一元多项式的减法处理模块 ............................. - 11 - 4.6一元多项式的乘法处理模块 ............................................................. - 12 - 5 结束语 ................................................. - 14 - 6 参考文献 ............................................... - 15 - 附录： ................................................... - 16 - 源程序代码： ............................................ - 16 - 《用广义表实现一元多项式乘法》 第 - 3 - 页 共 26 页 1 引 言 1.1 课题背景及意义 “数据结构”是计算机程序设计的重要理论技术基础，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相关的算法。它不仅是计算机学科的核心课程，而且已成为其他理科专业的热门选修课。 在“数据结构”这门课程中，有部分内容对一元多项式的运算进行了探讨。而符号多项式的操作，已经成为表处理的典型用例。 在通常的应用中，多项式的次数可能很高且变化很大，使得顺序存储结构的最大长度难以确定。特别是在处理形如S(x)=5+2x30000+8x40000的多项式时，就要用一长度为40001的线性表来表示，表中仅有3个非零元素，这种对内存空间的浪费是应当避免的。一般情况下的一元n次多项式可写Pn(x)=p1xe1+p2xe2+„+pmxem。若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表便可惟一确定多项式Pn(x)。在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但是，对于S(x)类的多项式，这种表示将大大节省空间。

1.2 课题实现技术的简要说明 根据数学定义，不含加法或减法运算的整式称为单项式。多个单项式的代数和称为多项式。多项式中每一个单项式称为多项式的项。 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。 多项式的相加过程和归并两个有序表的过程极其相似，不同之处在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作来完成。 需要说明的是，表示一元多项式的线性链表应该是有序链表。有序链表的基本操作定义与线性链表是不同的。 《用广义表实现一元多项式乘法》 第 - 4 - 页 共 26 页 1.3 可行性分析

（1）发展可行性分析 在强调时间就是金钱的现代社会中，效率变的越来越重要。而将数学领域中的一元多项式的运算与计算机程序设计相结合，则是当今社会现代数学的发展趋势。通过这样的处理方式，从事专业性科学计算、财会等各部门员工就能从大量烦琐的数字计算中解脱出来，只需对自己需要的数据和内容进行必要的处理，而不用对每个环节都了如指掌。这在一定程度上能够节省人力物力，为计算机数学的发展提供了可行性。 （2）技术可行性分析 技术上的可行性分析主要分析现有技术条件能否顺利完成开发工作，硬件、软件配置能否满足开发者的需要，各类技术人员的数量，水平，来源等。一元多项式处理的工作主要是在计算机和数学之间架起一座桥梁，能相互沟通信息和处理信息。这一特点非常适合计算机特点，通过网络Internet技术，发挥计算机的信息传输速度快、准确度高的优势。计算机硬件和软件技术的飞速发展，数学学科精密的逻辑为本身系统的建设和数学的课持续发展提供了技术条件。 （3）社会可行性分析 社会可行性有时也称为操作可行性，主要论证新系统在教育或机构开发和运行的可能性以及运行后可能一起的对教育或机构的影响，即组织内外是否具备接受和使用新系统的条件。在当前信息技术飞速发展的大环境下，计算机技术和软件技术和数学学科的融会贯通是中小型学校完全有可能也有能力采用这样先进的管理技术。它对学校带来的影响可以看到：对传统计算理念的冲击，可能引起低级计算层的变动和人员的调整。对从事科学计算工作人员的要求提高，在一定的可能下进行机构精简，迫使从事科学计算工作人员继续学习新知识，拓宽很多领域在市场环境下的生存空间。 1.4 性能需求分析 1．硬件环境 处理器：Inter COREi3 M 330。 内存：2GB。 硬盘空间： 320GB。 2．软件环境 操作系统: WindowsXP 开发平台：VC 《用广义表实现一元多项式乘法》 第 - 5 - 页 共 26 页 2 数据结构与设计思路 2.1数据结构设计 本系统定义了一种抽象数据类型Polynomial，用来存储一元多项式的项的信息。其代码为： typedef struct Polynomial //定义多项式的项 { float coef; //系数 int exp; //指数 struct Polynomial *next;//指针 }*PolyList; //定义多项式链表 多项式链表结构如图2-1所示。

图2-1 多项式链表结构图 2.2功能分析 用广义表对一元多项式处理的系统的实现与设计需要完成四个功能，其中包括： (1)一元多项式的输出； (2)求两个一元多项式的加法运算的结果； (3)求两个一元多项式的减法运算的结果； (4)求两个一元多项式的乘法运算的结果 主模块负责应用程序的主界面,由它调用其他模块.因此主模块应该具有操作性好、界面清晰的特点,使用户能够很方便地找到所需功能。根据功能需求的结果分析,主界面应该由一元多项式的输入与输出、两个一元多项式的加法运算与结果的输出、两个一元多项式的减法运算与结果的输出和两个一元多项式的乘法运算与结果的输出组成,如图3-2所示。可以通过输入不同选项进入相应的功能模块。 系统功能模块如图2-2所示。

系数coef 指数exp 系数coef 指数exp 系数coef 指数exp

系数coef 指数exp ^

合集下载

数据结构.第2章.线性表.2.一元多项式的表示及相加

数据结构.第2章.线性表.2.一元多项式的表示及相加

Pc
Pa Pb
Pc 10 6
1 0 /\
§2.4 一元多项式的表示及相加 ❖例2：设两个一元多项式为
A(x)= 4 + 6x4 + 5x8 + 4x12 B(x)= 2x3 - 5x8 + 3x12 + 7x15
求此两一元多项式之和: C(x)=A(x)+B(x)
§2.4 一元多项式的表示及相加
} ADT Polynomial
§2.4 一元多项式的表示及相加
❖实现思路
▪ 依次比较Pa和Pb所指结点中的指数项，依
Pa―>expn =、<、> Pb―>expn等情况，再决定
是将两系数域的数值相加(并判其和是否为0)， 还是将较高指数项的结点插入到新表C中。
§2.4 一元多项式的表示及相加 ❖例1：设两个一元多项式为
习题与练习
2. 在一个单链表HL中，若要在指针q指向的结点的后 面插入一个由指针P指向的结点，则执行（ ）。 A） q -> next = p -> next ； p = q； B） p -> next = q -> next ； q = p； C） q -> next = p -> next ； p -> next = q ； D） p -> next = q -> next ； q -> next = p ；
ha=GetHead(pa); hb=GetHead(pb) ; // ha和hb分别指向Pa和Pb的头结点
int cmp (term a，term b) ；
qa=NextPos(pa, ha); qb=NextPos(pb, hb) ; //qa和qb分别指向Pa和Pb中当前结点
一元稀疏多项式的链式存储实现及简单运算

一元稀疏多项式的链式存储实现及简单运算

一元稀疏多项式的链式存储实现及简单运算大家好，今天我们来聊聊一元稀疏多项式的链式存储实现及简单运算。

我们要明白什么是一元稀疏多项式。

一元稀疏多项式就是形如f(x) = ax^n + bx^(n-1) + ... + b的多项式，其中a、b、n是常数，x是未知数，x^0=1。

在很多实际问题中，我们会遇到很多这样的多项式，但是它们的系数a和b并不是很多，而且有些系数可能是0,这时候我们就需要用到稀疏矩阵来存储这些多项式。

那么，为什么我们需要用链表来存储稀疏矩阵呢？这是因为链表有很多优点，比如说它可以根据需要动态地分配内存空间，这样就可以节省内存资源。

而且，链表还可以方便地进行插入和删除操作，这对于我们处理稀疏矩阵来说是非常重要的。

下面，我们来看一个例子。

假设我们有一个一元稀疏多项式f(x) = 2x^3 + 3x^2 + x + 4。

为了方便起见，我们先把它表示成一个链表的形式：```Node 1: {value: 2, next: Node 2}Node 2: {value: 3, next: Node 3}Node 3: {value: 1, next: null}Node 4: {value: 4, next: null}```这个链表表示的是一元稀疏多项式的系数。

从这个链表中，我们可以很容易地计算出f(x)的值。

具体方法是：从链表的头节点开始，依次取出每个节点的值，然后将它们相乘并加上下一个节点的值，直到遍历完整个链表为止。

在这个例子中，f(x) = 2 * x^3 + 3 * x^2 + x + 4 = x(2x^2 + 3x + 1) + 4。

除了上述的例子之外，链表还有很多其他的应用场景。

比如说，在计算机科学中，链表可以用来实现栈和队列等数据结构；在数学中，链表可以用来表示无穷级数；在工程领域，链表可以用来表示文件系统等等。

链表是一种非常有用的数据结构，它可以帮助我们更好地处理各种问题。

数据结构-多项式相乘

数据结构-多项式相乘

多项式相乘•问题描述此程序解决的是一元多项式相乘的问题。

定义两个一元多项式，然后进行两个一元多项式的相乘。

最后得到一个结果，并按升幂输出最终的多项式。

•设计思路定义一个结构体，里面包含一元多项式的符号、系数、指数。

对多项式进行输入时，先输入多项式的项数，然后从第一项的系数开始输入，然后输入第一项的指数，直至第一项输入完毕。

然后开始输入第二项，输入第二项的方法与输入第一项的方法相同。

在进行相乘时，用第二项的每个元素去乘第一项的每个元素。

最终合并同类项的时候，把后面指数项加到与前面有共同指数的项的上面，然后删除该项。

•数据结构设计将多项式因子的符号、系数、指数封装成一个结构为顺序表类型•功能函数设计void sort(LinkYinzi& Head)排序函数，采用冒泡排序对多项式进行排序void PrintList(const LinkYinzi Head)输出多项式函数void Creat_List(LinkYinzi& Head, int num)创建多项式函数void DelList(LinkYinzi& Head, int n)删除多项式中某一项函数void multip(const LinkYinzi Head1, const LinkYinzi Head2)多项式相乘函数void menu_elect( LinkYinzi Head1, LinkYinzi Head2)功能选择函数•程序代码#include <iostream>using namespace std;typedef struct Yinzi{char sign;float coef;//系数int expn;//指数Yinzi* next;}Yinzi,*LinkYinzi;void sort(LinkYinzi& Head){LinkYinzi Q;//采用冒泡排序对多项式进行排序for(LinkYinzi P1 = NULL; P1 != Head->next->next; P1 = Q)for(LinkYinzi P2 = Head->next; P2->next != P1; P2 = P2->next){if(P2->expn > P2->next->expn){int temp1;double temp2;char temp3; //temp3是交换变量temp2 = P2->coef;P2->coef = P2->next->coef;P2->next->coef = temp2;temp3 = P2->sign;P2->sign = P2->next->sign;P2->next->sign = temp3;temp1 = P2->expn;P2->expn = P2->next->expn;P2->next->expn = temp1;}Q = P2->next;//此处让Q为本次执行后的P2的下一个，以便P1=Q让P1成为P2的下一个，作为下一次循环的结束标志。

数据结构一元多项式

数据结构一元多项式

《数据结构》课程设计报告系别：计算机与电子系专业班级：电子0802班学生姓名：胡锦奎（20081185055）指导教师：程海英（课程设计时间：20 10 年12月27日——20 11 年1月7日）华中科技大学武昌分校目录1．课程设计目的…………………………………………………………………3页2．课程设计题目描述和要求……………………………………………3页3．课程设计报告内容……………………………………………………………5页3.1 一元多项式运算的实现…………………………………………………5页3.2 迷宫问题实现……………………………………………………………9页3.3 校园导游咨询……………………………………………………………13页3.4 跳舞搭配问题……………………………………………………………15页3.5 利用栈实现表达式求值…………………………………………………18页4．总结………………………………………………………………………… 20页参考文献……………………………………………………………………… 21页（要求：目录题头用三号黑体字居中书写，隔行书写目录内容。

目录中各级题序及标题用小四号黑体）一．课程设计目的：数据结构课程设计是在学完数据结构课程之后的实践教学环节.该实践教学是软件设计的综合训练,包括问题分析,总体结构设计,用户界面设计,程序设计基本技能和技巧。

要求学生在设计中逐步提高程序设计能力,培养科学的软件工作方法.学生通过数据结构课程设计在各方面得到锻炼二．课程设计题目描述和要求：1．一元多项式加法、减法、乘法运算的实现1）设计内容：完成两个一元多项式作加法、减法、乘法，给出明确的等式形式。

完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；函数功能要划分好，总体设计应画流程图，程序一定要经得起测试2）设计要求（1）用C语言编程实现上述实验内容中的结构定义和算法。

（2）要有main()函数，并且在main()函数中使用检测数据调用上述算法。