数据结构(3)--线性表实现一元多项式加法

2024-05-12 17:38

本文主要是介绍数据结构(3)--线性表实现一元多项式加法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考书籍:数据结构(C语言版) 严蔚敏 吴伟民编著 清华大学出版社

本文中的代码可从这里下载:https://github.com/qingyujean/data-structure

1.简要说明

    一元多项式的表示和相加

    多项式Pn(x)按升幂可写成:

                Pn(x) = P0+P1*x+p2*x^2+...+Pn*x^n,

    它由n+1个系数唯一确定,因此可用一个线性表p=(p0,p1,p2,...,pn),每一项的指数i隐含在系数pi的序号里。设Qm(x)是一元m次多项式,则可用线性表Q=(q0,q1,q2,...,qm)来表示。不失一般性,设m<n,则两个多项式想家的结果多项式Rn(x)=Pn(x)+Qm(x)可用线性表:

                (p0+q0, p1+q1, ..., pm+qm, p(m+1), ..., pn)

    分析:
    对P、Q、R可用顺序存储结构,多项式相加的算法定义将十分简单,但通常应用中次数可能很高,使得顺序存储结构的最大长度很难确定;另外很多项的系数也可能为0,比如S(x)=1+3x^10000+2x^20000,如果是像这样仅有3个非0元素,则顺序存储结构的线性表的存储空间将非常浪费,故采用单链表结构,但是这时就要存储指数了。
    一元n次多项式Pn(x)=p1*x^e1 + p2*x^e2 +...+pm*x^em,其中pi是指数为ei的项的非零系数,且满足0<=e1<e2<...<em=n,若用一个长度为m且每个元素有两个数据项(系数项+指数项)的线性表((p1,e1),(p2,e2),...,(pm,em))便可唯一确定多项式Pn(x)。 最坏情况下,n+1(=m)个系数都不为0,这种表示将大大节省空间。

    实现:
    "和多项式"链表中的节点无需另生成,而应该从两个多项式的链表中摘取。运算规则如下:假设指针qa、qb分别指向多项式A和B中当前进行比较的某个节点,则比较两个节点中的指数项,有下列3种情况:
     1.qa所指节点的指数值<qb所指节点的指数值,则应摘取qa所指节点插入到“和多项式”中;
     2.qa所指节点的指数值>qb所指节点的指数值,则应摘取qb所指节点插入到“和多项式”中;
     3.qa所指节点的指数值=qb所指节点的指数值,则将两节点的系数相加
          3.1若系数相加和数不为0,则修改qa所指节点的系数值,同时释放qb所指节点;
          3.2若系数相加和数为0,从多项式A的单链表中删除相应节点,并释放qa和qb所指节点。
    注意:
    表示一元多项式的应该是有序链表

2.代码实现

#include<stdio.h>
#include<stdlib.h>
#define NULL 0
typedef struct term{float coef;int expn;struct term *next;
}term, *LinkList;//term为一个新类型(是一个结构体),LinkList为指向这样的结构体的指针typedef LinkList polynomial;

 

int cmp(LinkList qa, LinkList qb){//比较项的指数大小if(qa->expn > qb->expn)return 1;else if(qa->expn == qb->expn)return 0;elsereturn -1;
}
//若有序链表L中存在与项t的指数相等的元素,则指针q指向L中第一个指数为t->expn的节点的位置,
//否则q指向第一个指数满足与t->expn相比>0的节点的前驱位置
bool locateElem(LinkList L, LinkList t, LinkList &q){LinkList p1 = L->next;LinkList p2 = L;//p2总指向p1的前驱while(p1){if(t->expn > p1->expn){p1 = p1->next;p2 = p2->next;}else if(t->expn == p1->expn){q = p1; return true;}else{//p1->expn > t->expn,因为L是有序表,所以如果程序走到了这一步,说明没找到与项t的指数相等的节点元素//则返回q的前驱结点q = p2;return false;}}if(!p1){//t->expn比当前列表所有元素的指数都大,则上面的while循环会因为p2到达了尾节点,p1=NULL而跳出q = p2;return false;}
}
//输入m项的系数和指数,建立表示一元多项式的带有头节点的有序链表P
//利用尾插法
void createPolyn(polynomial &P, int m){//先建立一个带有头节点的空链表,即初始化P = (polynomial)malloc(sizeof(term));P->next = NULL;LinkList r = P;//r指针总是指向当前线性表的最后一个元素,即尾元素printf("输入系数,指数,如项2x^5则输入(2,5):\n");//不必按升幂输入for(int i = 0; i < m; i++){//依次输入m个非零项LinkList t = (LinkList)malloc(sizeof(term));t->next = NULL;LinkList q;scanf("%f,%d",&t->coef,&t->expn);if(!locateElem(P, t, q)){//当前链表中不存在该指数项,则插入,此时q为链表中第一个指数>t->expn的节点的前驱结点t->next = q->next;q->next = t;}else{//当前列表中已经存在有节点元素的指数与本次输入的项的指数相同,所以本次输入无效,应重新输入i--;}}
}
//打印多项式链表
void printPolynomial(polynomial P){LinkList q = P->next;printf("打印多项式的线性表:[");while(q){printf("(%.2f,%d)  ",q->coef, q->expn);q = q->next;}printf("]\n\n");
}
//多项式加法:Pa=Pa+Pb,利用2个多项式的节点构成“和多项式”
void addPolyn(polynomial &Pa, polynomial &Pb){LinkList qa = Pa->next;LinkList qb = Pb->next;LinkList qc = Pa;//pc总是指向"和多项式链表"的最后一个节点float sumOfCoef;while(qa&&qb){switch(cmp(qa, qb)){case 1:qc->next = qb;qc = qb;qb = qb->next;break;case 0://当前比较的两项的指数相同sumOfCoef = qa->coef + qb->coef;if(sumOfCoef != 0.0){//系数之和不为0,则修改qa所指节点的系数,同时释放gb所指节点LinkList s = qb;//s即将被free掉qa->coef = sumOfCoef;qc->next = qa;qc = qa;qa = qa->next;qb = qb->next;free(s);}else{//系数之和不为0,则从多项式链表A中删除qa所指节点,并free掉qa、qb所指节点LinkList s1 = qa;LinkList s2 = qb;qc->next = qa ->next;//qc的位置不变,qa、qb向后移动qa = qa->next;qb = qb->next;free(s1);free(s2);}break;case -1:qc->next = qa;qc = qa;qa = qa->next;break;}//end switch}//end whileqc->next = qa?qa:qb;//插入剩余段free(Pb);//释放Pb的头节点
}
//实例:Pa(x)=7+3x+9x^8+5x^17, 输入((7,0),(3,1),(9,8),(5,17))
//Pb(x)=8x+22x^7-9x^8,输入((8,1),(22,7),(-9,8))
//和多项式为Pa(x) = 7+11x+22x^7+5x^17,即最后应该输出((7,0),(11,1),(22,7),(5,17))
int main(){polynomial Pa;createPolyn(Pa, 4);//初始化并创建多项式链表PaprintPolynomial(Pa);polynomial Pb;createPolyn(Pb, 3);//初始化并创建多项式链表PaprintPolynomial(Pb);printf("执行多项式相加以后\n");addPolyn(Pa, Pb);printPolynomial(Pa);return 0;
}

 

本文中的代码可从这里下载:https://github.com/qingyujean/data-structure

这篇关于数据结构(3)--线性表实现一元多项式加法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/983298

相关文章

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合