【数据结构】一元多项式的表示及相加

这篇具有很好参考价值的文章主要介绍了【数据结构】一元多项式的表示及相加。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

⭐️写在前面的话⭐️

📒博客主页: 程序员好冰
🎉欢迎 【点赞👍 关注🔎 收藏⭐️ 留言📝】
📌本文由 程序员好冰 原创,CSDN 首发!
📆入站时间: 🌴2022 年 07 月 13 日🌴
✉️ 是非不入松风耳,花落花开只读书。
💭推荐书籍:📚《Java编程思想》,📚《Java 核心技术卷》
💬参考在线编程网站:🌐牛客网🌐力扣
🍭 作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!🍭


一元多项式的表示及相加

一个一元多项式可以表示按升序写

【数据结构】一元多项式的表示及相加

两个一元多项式相加

【数据结构】一元多项式的表示及相加

因此,一元多项式的表示及相加可以使用线性表的链式存储结构(单链表)来表示

【数据结构】一元多项式的表示及相加

有关两个结点互换位置的操作

两个多项式相加的过程

初始化

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;

typedef struct
{
    int coef;//系数
    int expn;//指数
}term,ElemType;

typedef struct Node
{
    ElemType elem;
    struct Node *next;
}Node,*LinkList;

typedef LinkList polynomial;

Status InitList(polynomial*);//0_1、初始化链表
Status push_node_head(polynomial*,ElemType);//0_2_1、头插法插入多项式的项
Status sameExpn_list_addCoef(polynomial*,ElemType);//0_2_2、将要插入的相同,链表中有相同项
Status find_list_by_expn(polynomial,int);//0_3、从链表中查找是否有相同的指数项
Status sort_by_expn(polynomial*);//0_4、对已经创建好的一元多项式按指数大小进行排序进行

//0_5、比较指数值的大小
/*
    a < b,返回 -1
    a = b,返回 0
    a > b,返回 1
*/
int cmp(term,term);

//声明函数
Status CreatPolyn(polynomial*,int);//1、输入m项的系数和指数,建立表示一元多项式的有序链表P

Status DestoryPolyn(polynomial*);//2、销毁一元多项式P

Status PrintPolyn(polynomial);//3、打印输出一元多项式P

int PolynLength(polynomial);//4、返回一元多项式P中的项数

Status AddPolyn(polynomial*,polynomial*);//5、完成多项式相加运算,即:Pa=Pa+Pb,并销毁Pb

0_1、初始化链表

//0_1、初始化链表
Status InitList(polynomial *P)
{
    *P=(polynomial)malloc(sizeof(Node));
    if(!P){
        printf("初始化失败,请重新操作.\n");
        return ERROR;
    }
    (*P)->next=NULL;
    return OK;
}

0_2_1、头插法插入多项式的项(没有相同项)

//0_2_1、头插法插入多项式的项(没有相同项)
Status push_node_head(polynomial *P,ElemType e)
{
    polynomial p;
    p=*P;
    polynomial s;
    s=(polynomial)malloc(sizeof(Node));
    s->elem=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

0_2_2、将要插入的相同,链表中有相同项,对应系数相加

//0_2_2、将要插入的相同,链表中有相同项,对应系数相加
Status sameExpn_list_addCoef(polynomial *P,ElemType e)
{
    polynomial p;
    p=(*P)->next;
    while(p){
        if(p->elem.expn==e.expn){
            p->elem.coef+=e.coef;
        }
        p=p->next;
    }
    return OK;
}

0_3、从链表中查找是否有相同的指数项

//0_3、从链表中查找是否有相同的指数项
Status find_list_by_expn(polynomial P,int expn)
{
    if(!P->next){
        return OK;
    }
    polynomial p;
    p=P->next;
    int i;
    i=0;
    while(p){
        if(p->elem.expn==expn){
            return ERROR;//有相同项
        }
        i++;
        p=p->next;
    }
    if(i==PolynLength(P)){
        return OK;//没有相同项
    }
    return OK;
}

0_4、对已经创建好的一元多项式按指数大小进行排序进行(采用冒泡排序)

//0_4、对已经创建好的一元多项式按指数大小进行排序进行(采用冒泡排序)
Status sort_by_expn(polynomial *P)
{
    polynomial s;
    polynomial p;
    polynomial q;
    int length;//结点个数
    length=PolynLength(*P);
    int i,j;
    for(i=0;i<length-1;i++){//外层循环
        j=length-1-i;
        s=*P;//指向表头
        p=(*P)->next;
        q=p->next;
        while(j--){//内层循环
            if(q->elem.expn<p->elem.expn){
                //交换结点
                p->next=q->next;
                s->next=q;
                q->next=p;
            }
            s=s->next;
            p=s->next;
            q=p->next;
        }
    }
    return OK;
}

0_5、比较指数值的大小

//0_5、比较指数值的大小
/*
    a < b,返回 -1
    a = b,返回 0
    a > b,返回 1
*/
int cmp(term pa,term pb)
{
    if(pa.expn<pb.expn){
        return -1;
    }
    if(pa.expn==pb.expn){
        return 0;
    }
    if(pa.expn>pb.expn){
        return 1;
    }
    return -1;
}

1、输入m项的系数和指数,建立表示一元多项式的有序链表P

//1、输入m项的系数和指数,建立表示一元多项式的有序链表P
Status CreatPolyn(polynomial *P,int m)
{
    //初始化链表
    InitList(P);
    int flag;
    int i;
    for(i=1;i<=m;i++){
        //当前要插入的结点
        ElemType cur_elem;
        printf("请输入第%d项的系数和指数(用逗号隔开):",i);
        scanf("%d,%d",&(cur_elem.coef),&(cur_elem.expn));
        //查找功能
        flag = find_list_by_expn(*P,cur_elem.expn);
        //插入功能
        /*如果链表中有这一项,系数相加*/
        if(flag==0){
            sameExpn_list_addCoef(P,cur_elem);
        }
        /*如果链表中没有这一项,插入新节点*/
        if(flag==1){
            push_node_head(P,cur_elem);
        }
    }
    sort_by_expn(P);
    return OK;
}

2、销毁一元多项式P

//2、销毁一元多项式P
Status DestoryPolyn(polynomial *P)
{
    polynomial p;
    p=*P;
    polynomial q;
    while(p->next){
        q=p->next;
        p->next=q->next;
        free(q);
    }
    free(P);
    P=NULL;
    return OK;
}

3、打印输出一元多项式P

//3、打印输出一元多项式P
Status PrintPolyn(polynomial P)
{
    printf("一元多项式 P = ");
    Node* p;
    p=P->next;
    while(p){
        if(!p->next){
            printf("%d*X^%d",p->elem.coef,p->elem.expn);
        }else
        {
            printf("%d*X^%d+",p->elem.coef,p->elem.expn);
        }
        p=p->next;
    }
    return OK;
}

4、返回一元多项式P中的项数

//4、返回一元多项式P中的项数
int PolynLength(polynomial P)
{
    Node *p;
    p=P->next;
    int length;
    length=0;
    while(p){
        length++;
        p=p->next;
    }
    return length;
}

5、完成多项式相加运算,即:Pa=Pa+Pb,并销毁Pb

//5、完成多项式相加运算,即:Pa=Pa+Pb,并销毁Pb
Status AddPolyn(polynomial *Pa,polynomial *Pb)
{
    /*
        a < b,返回 -1
        a = b,返回 0
        a > b,返回 1
    */
    Node *pa;//Pa的工作结点
    Node *pb;//Pb的工作结点
    Node *pa_prior;//始终是pa的直接前驱
    Node *temp;//需要释放的结点
    pa=(*Pa)->next;
    pb=(*Pb)->next;
    pa_prior=(*Pa);
    int flag;//记录cmp的结果
    int e;//记录指数相同时,系数的和
    while(pa&&pb){//有一个为空就跳出循环
        flag=cmp(pa->elem,pb->elem);
        if(flag==-1){//pa小
            pa=pa->next;
            pa_prior=pa_prior->next;
        }
        if(flag==0){//指数相同的项
            e=pa->elem.coef+pb->elem.coef;
            temp=pb;
            (*Pb)->next=pb->next;
            pb=(*Pb)->next;
            free(temp);
            if(e==0){
                //释放pa
                temp=pa;
                (*Pa)->next=pa->next;
                pa=(*Pa)->next;
                free(temp);
            }
            if(e!=0){
                pa->elem.coef=e;
            }
        }
        if(flag==1){//pb小
            (*Pb)->next=pb->next;
            pb->next=pa;
            pa_prior->next=pb;
            pa_prior=pb;
            pb=(*Pb)->next;
        }
    }
    if(pb){
        pa_prior->next=pb;
        (*Pb)->next=NULL;
    }
    return OK;
}

主函数

int main()
{
    while(1){
        polynomial P;
        polynomial Pa;
        polynomial Pb;
        int input;
        int m;//项数
        int ma,mb;
        int length;//项数
        printf("\n==========================\n");
        printf("1、建立有序多项式链表.\n");
        printf("2、销毁多项式.\n");
        printf("3、打印多项式.\n");
        printf("4、返回项数.\n");
        printf("5、两个多项式相加.\n");
        printf("\n==========================\n");
        printf("请输入对应操作的序号:\n");
        scanf("%d",&input);
        switch(input)
        {
        case 1:
            printf("请输入需要创建的多项式项数(m):");
            scanf("%d",&m);
            CreatPolyn(&P,m);
            break;
        case 2:
            DestoryPolyn(&P);
            printf("成功销毁一元多项式P.\n");
            break;
        case 3:
            PrintPolyn(P);
            break;
        case 4:
            length=PolynLength(P);
            printf("该一元多项式的项数为 %d.\n",length);
            break;
        case 5:
            printf("请创建第1个一元多项式Pa:\n");
            printf("请输入需要创建的多项式项数(m):");
            scanf("%d",&ma);
            CreatPolyn(&Pa,ma);
            printf("请创建第2个一元多项式Pa:\n");
            printf("请输入需要创建的多项式项数(m):");
            scanf("%d",&mb);
            CreatPolyn(&Pb,mb);
            AddPolyn(&Pa,&Pb);
            printf("相加之后,");
            PrintPolyn(Pa);
            break;
        default:
            printf("输入的序号有误,请重新输入...\n");
            break;
        }
    }
    return 0;
}

程序源码

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;

typedef struct
{
    int coef;//系数
    int expn;//指数
}term,ElemType;

typedef struct Node
{
    ElemType elem;
    struct Node *next;
}Node,*LinkList;

typedef LinkList polynomial;

Status InitList(polynomial*);//0_1、初始化链表
Status push_node_head(polynomial*,ElemType);//0_2_1、头插法插入多项式的项
Status sameExpn_list_addCoef(polynomial*,ElemType);//0_2_2、将要插入的相同,链表中有相同项
Status find_list_by_expn(polynomial,int);//0_3、从链表中查找是否有相同的指数项
Status sort_by_expn(polynomial*);//0_4、对已经创建好的一元多项式按指数大小进行排序进行

//0_5、比较指数值的大小
/*
    a < b,返回 -1
    a = b,返回 0
    a > b,返回 1
*/
int cmp(term,term);

//声明函数
Status CreatPolyn(polynomial*,int);//1、输入m项的系数和指数,建立表示一元多项式的有序链表P

Status DestoryPolyn(polynomial*);//2、销毁一元多项式P

Status PrintPolyn(polynomial);//3、打印输出一元多项式P

int PolynLength(polynomial);//4、返回一元多项式P中的项数

Status AddPolyn(polynomial*,polynomial*);//5、完成多项式相加运算,即:Pa=Pa+Pb,并销毁Pb

//0_1、初始化链表
Status InitList(polynomial *P)
{
    *P=(polynomial)malloc(sizeof(Node));
    if(!P){
        printf("初始化失败,请重新操作.\n");
        return ERROR;
    }
    (*P)->next=NULL;
    return OK;
}

//0_2_1、头插法插入多项式的项(没有相同项)
Status push_node_head(polynomial *P,ElemType e)
{
    polynomial p;
    p=*P;
    polynomial s;
    s=(polynomial)malloc(sizeof(Node));
    s->elem=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

//0_2_2、将要插入的相同,链表中有相同项,对应系数相加
Status sameExpn_list_addCoef(polynomial *P,ElemType e)
{
    polynomial p;
    p=(*P)->next;
    while(p){
        if(p->elem.expn==e.expn){
            p->elem.coef+=e.coef;
        }
        p=p->next;
    }
    return OK;
}

//0_3、从链表中查找是否有相同的指数项
Status find_list_by_expn(polynomial P,int expn)
{
    if(!P->next){
        return OK;
    }
    polynomial p;
    p=P->next;
    int i;
    i=0;
    while(p){
        if(p->elem.expn==expn){
            return ERROR;//有相同项
        }
        i++;
        p=p->next;
    }
    if(i==PolynLength(P)){
        return OK;//没有相同项
    }
    return OK;
}

//0_4、对已经创建好的一元多项式按指数大小进行排序进行(采用冒泡排序)
Status sort_by_expn(polynomial *P)
{
    polynomial s;
    polynomial p;
    polynomial q;
    int length;//结点个数
    length=PolynLength(*P);
    int i,j;
    for(i=0;i<length-1;i++){//外层循环
        j=length-1-i;
        s=*P;//指向表头
        p=(*P)->next;
        q=p->next;
        while(j--){//内层循环
            if(q->elem.expn<p->elem.expn){
                //交换结点
                p->next=q->next;
                s->next=q;
                q->next=p;
            }
            s=s->next;
            p=s->next;
            q=p->next;
        }
    }
    return OK;
}

//0_5、比较指数值的大小
/*
    a < b,返回 -1
    a = b,返回 0
    a > b,返回 1
*/
int cmp(term pa,term pb)
{
    if(pa.expn<pb.expn){
        return -1;
    }
    if(pa.expn==pb.expn){
        return 0;
    }
    if(pa.expn>pb.expn){
        return 1;
    }
    return -1;
}

//1、输入m项的系数和指数,建立表示一元多项式的有序链表P
Status CreatPolyn(polynomial *P,int m)
{
    //初始化链表
    InitList(P);
    int flag;
    int i;
    for(i=1;i<=m;i++){
        //当前要插入的结点
        ElemType cur_elem;
        printf("请输入第%d项的系数和指数(用逗号隔开):",i);
        scanf("%d,%d",&(cur_elem.coef),&(cur_elem.expn));
        //查找功能
        flag = find_list_by_expn(*P,cur_elem.expn);
        //插入功能
        /*如果链表中有这一项,系数相加*/
        if(flag==0){
            sameExpn_list_addCoef(P,cur_elem);
        }
        /*如果链表中没有这一项,插入新节点*/
        if(flag==1){
            push_node_head(P,cur_elem);
        }
    }
    sort_by_expn(P);
    return OK;
}

//2、销毁一元多项式P
Status DestoryPolyn(polynomial *P)
{
    polynomial p;
    p=*P;
    polynomial q;
    while(p->next){
        q=p->next;
        p->next=q->next;
        free(q);
    }
    free(P);
    P=NULL;
    return OK;
}

//3、打印输出一元多项式P
Status PrintPolyn(polynomial P)
{
    printf("一元多项式 P = ");
    Node* p;
    p=P->next;
    while(p){
        if(!p->next){
            printf("%d*X^%d",p->elem.coef,p->elem.expn);
        }else
        {
            printf("%d*X^%d+",p->elem.coef,p->elem.expn);
        }
        p=p->next;
    }
    return OK;
}

//4、返回一元多项式P中的项数
int PolynLength(polynomial P)
{
    Node *p;
    p=P->next;
    int length;
    length=0;
    while(p){
        length++;
        p=p->next;
    }
    return length;
}

//5、完成多项式相加运算,即:Pa=Pa+Pb,并销毁Pb
Status AddPolyn(polynomial *Pa,polynomial *Pb)
{
    /*
        a < b,返回 -1
        a = b,返回 0
        a > b,返回 1
    */
    Node *pa;//Pa的工作结点
    Node *pb;//Pb的工作结点
    Node *pa_prior;//始终是pa的直接前驱
    Node *temp;//需要释放的结点
    pa=(*Pa)->next;
    pb=(*Pb)->next;
    pa_prior=(*Pa);
    int flag;//记录cmp的结果
    int e;//记录指数相同时,系数的和
    while(pa&&pb){//有一个为空就跳出循环
        flag=cmp(pa->elem,pb->elem);
        if(flag==-1){//pa小
            pa=pa->next;
            pa_prior=pa_prior->next;
        }
        if(flag==0){//指数相同的项
            e=pa->elem.coef+pb->elem.coef;
            temp=pb;
            (*Pb)->next=pb->next;
            pb=(*Pb)->next;
            free(temp);
            if(e==0){
                //释放pa
                temp=pa;
                (*Pa)->next=pa->next;
                pa=(*Pa)->next;
                free(temp);
            }
            if(e!=0){
                pa->elem.coef=e;
            }
        }
        if(flag==1){//pb小
            (*Pb)->next=pb->next;
            pb->next=pa;
            pa_prior->next=pb;
            pa_prior=pb;
            pb=(*Pb)->next;
        }
    }
    if(pb){
        pa_prior->next=pb;
        (*Pb)->next=NULL;
    }
    return OK;
}

int main()
{
    while(1){
        polynomial P;
        polynomial Pa;
        polynomial Pb;
        int input;
        int m;//项数
        int ma,mb;
        int length;//项数
        printf("\n==========================\n");
        printf("1、建立有序多项式链表.\n");
        printf("2、销毁多项式.\n");
        printf("3、打印多项式.\n");
        printf("4、返回项数.\n");
        printf("5、两个多项式相加.\n");
        printf("\n==========================\n");
        printf("请输入对应操作的序号:\n");
        scanf("%d",&input);
        switch(input)
        {
        case 1:
            printf("请输入需要创建的多项式项数(m):");
            scanf("%d",&m);
            CreatPolyn(&P,m);
            break;
        case 2:
            DestoryPolyn(&P);
            printf("成功销毁一元多项式P.\n");
            break;
        case 3:
            PrintPolyn(P);
            break;
        case 4:
            length=PolynLength(P);
            printf("该一元多项式的项数为 %d.\n",length);
            break;
        case 5:
            printf("请创建第1个一元多项式Pa:\n");
            printf("请输入需要创建的多项式项数(m):");
            scanf("%d",&ma);
            CreatPolyn(&Pa,ma);
            printf("请创建第2个一元多项式Pa:\n");
            printf("请输入需要创建的多项式项数(m):");
            scanf("%d",&mb);
            CreatPolyn(&Pb,mb);
            AddPolyn(&Pa,&Pb);
            printf("相加之后,");
            PrintPolyn(Pa);
            break;
        default:
            printf("输入的序号有误,请重新输入...\n");
            break;
        }
    }
    return 0;
}

运行效果

【数据结构】一元多项式的表示及相加


🚀先看后赞,养成习惯!🚀

🚀 先看后赞,养成习惯!🚀

🎈觉得文章写得不错的老铁们,点赞评论关注走一波!谢谢啦!🎈文章来源地址https://www.toymoban.com/news/detail-500130.html


到了这里,关于【数据结构】一元多项式的表示及相加的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构中: 一元多项式的运算(相加,相减,相乘)------用C语言 / C++来实现。 数据结构线性表的操作和应用(顺序存储)

    线性表的操作和应用(顺序存储)。用顺序存储实现一元多项式,并进行加、减、乘运算。 (1)一元多项式结构体创建  (2)初始化 (3)一元多项式赋值             (4)打印一元多项式 (5)加法运算                        (6)减法运算 (7)乘法运算    全部代

    2024年02月01日
    浏览(49)
  • 题02-线性结构2 一元多项式的乘法与加法运算(C语言)

    设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。 输出格式: 输出分2行,分别以指数递降方式输出乘积多项式

    2024年02月07日
    浏览(37)
  • 【数据结构】15 队列应用实例:多项式加法运算

    我们准备采用不带头节点的单向链表结构表示一元多项式,并按照指数递减的顺序排列各项。 对列表存放的两个多项式进行加法运算时,可以使用两个指针p1和p2。初始时的p1和p2分别指向这两个多项式第1个节点(指数的最高项)。通过循环不断比较p1和p2所指的节点,比较结

    2024年02月21日
    浏览(34)
  • 【ZZULI数据结构实验一】多项式的三则运算

    📃 博客主页: 小镇敲码人 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月,独傲天下百坚强。 男儿应有龙腾志,盖世一意转洪荒。 莫使此生无痕度,终归人间一捧黄。🍎🍎🍎 ❤️ 什么?你问我答案,少年你看,下一

    2024年04月15日
    浏览(50)
  • 南京邮电大学数据结构实验一(线性表的基本运算及多项式的算术运算)(代码篇)

    小伙伴们要多多体会,不要全部借鉴哦!

    2024年02月08日
    浏览(44)
  • 【链表应用】| 一元多项式的操作

    专栏推荐:写文章刚刚起步,各个专栏的知识点后续会补充完善,不断更新好文,希望大 家支持一下。 专栏 名字 Elasticsearch专栏 es spring专栏 spring开发 redis专栏 redis学习笔记 项目专栏 项目集锦 修bug专栏 bug修理厂 设有两个一元多项式: p(x)=p0+p1x+p2x2+···+pnxn q(x)=q0+q1x+q2x2+··

    2024年02月06日
    浏览(38)
  • 一元多项式相加问题(两种方法)

    一元多项式的相加问题,主要运用了线性结构的合并,在合并线性结构的基础上,增加判断,所以我们可以将这个问题理解为一个复杂的线性表合并问题  目录 问题描述 一、顺序表法 1.1 初始化并创建顺序表 1.2 一元多项式相加算法 1.3 完整代码 二、单链表法 1.1 初始化并创

    2024年02月06日
    浏览(45)
  • 用链表表示多项式,并实现多项式的加法运算

    输入格式: 输入在第一行给出第一个多项式POLYA的系数和指数,并以0,0 结束第一个多项式的输入;在第二行出第一个多项式POLYB的系数和指数,并以0,0 结束第一个多项式的输入。 输出格式: 对每一组输入,在一行中输出POLYA+POLYB和多项式的系数和指数。 输入样例: 输出样例: 本

    2024年02月07日
    浏览(60)
  • 一元稀疏多项式简单计算器(C语言)含注释

    问题描述 设计一个一元稀疏多项式简单计算器 基本要求 一元稀疏多项式简单计算器的基本功能是: (1)输入并建立多项式; (2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列; (

    2024年02月08日
    浏览(35)
  • Python做曲线拟合(一元多项式拟合及任意函数拟合)

    目录 1. 一元多项式拟合 使用方法 np.polyfit(x, y, deg) 2. 任意函数拟合 使用 curve_fit() 方法 实例: (1)初始化 x 和 y 数据集 (2)建立自定义函数 (3)使用自定义的函数生成拟合函数绘图  polyfig 使用的是最小二乘法,用于拟合一元多项式函数。 参数说明: x 就是x坐标,

    2024年02月02日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包