数据结构与算法----数学应用之一元多项式

PS:上一篇说了线性表的顺序表和链式表表达,该片就写一下应用到现实数学中去,一元多项式的加减。

一元多项式我们在本子上可以说是手到拈来,但是在电脑上用语言敲出来,估计这会让很多人头疼,比如下面的多项式

y1 = 9x^1  + 4x^3 + 6x^4

y2 = 2x^3 + 4x^4 + 3x^7 + 3x^8

yz = y1 + y2 ;

效果图

思路:

  1. 创建一个结构体,里面只存连个数,一个是系数data,一个是次幂,至于x就不用存了,只在打印的时候写上就OK了,
  2. 然后写插入操作,注意一定要是有序的,方便在后期相加
  3. 两个多项式相加就是合并,我们可以按照顺序两两比较,先拿y1的第一个数和y2第一个比较,如果y1>y2,则把y2添加到yz,相反之,如果y1=y2则相加系数,按照y1(也可y2)加入yz,等全都比较过后,如果y1(y2)还有项的话,就把剩下的全都加载到yz中,其实就是直接把next指向y1(y2)即可。

1:结构体

定义一个结构体类型 在SlinkOnez调用变量是,都是 L->data;L->next;的形式

typedef struct SlinkOne {
    int data;
    int cimi;
    struct SlinkOne *next;
} SlinkOne, *SlinkOnez;

2:初始化

/**c
 * 初始化
 * */
SlinkOnez initLink() {
    SlinkOnez L = (SlinkOnez) malloc(sizeof(SlinkOne));
    if (!L) {
        exit(-1);
    }
    L->next = NULL;
    return L;
}

3:插入操作

/**
 * 插入
 * */
int insertLink(SlinkOnez &L, int pos, int e, int cimi) {
    SlinkOnez p = L;
    int i = 0;
    while (p && i < pos-1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos-1) {
        printf("单链表未被创建\n");
        return -1;
    }
    //创建一个新的结点,并赋值
    SlinkOnez s = (SlinkOnez) malloc(sizeof(SlinkOne));
    s->data = e;
    s->cimi = cimi;
    s->next = p->next;
    p->next = s;
    printf("插入成功\n");
    return 0;
}

4:打印全部数据

注意:我在这里面加入了几个判断,一个是当p->next ==NULL时,后面的加号就不要了,如果次幂==0的话那就只打印系数,当然如果系数==0,那就不打印,下方并未给出。

/**
 * 打印全部数据
 * */
void printL(SlinkOnez L) {
    SlinkOnez p = L->next;
    if (!p) {
        printf("单链表不成立或者为NULL");
        return;
    }
    while (p) {
        if (p->next == NULL) {
            printf("%dX^%d", p->data, p->cimi);
        } else {
            if (p->cimi == 0) {
                printf("%d + ", p->data);
            } else {
                printf("%dX^%d + ", p->data, p->cimi);
            }
        }
        p = p->next;
    }
    printf("\n");
}

5:合并(重点)

注意:pz = p1;//往下走一个,这句话其实就相当于 pz = pz->next;

下面的全部代码实现都是在我上面说的思路上一一对应的,只要有思路,问题就已经解决了一半了,

/**
 * 合并
 * */
SlinkOnez mergeLink(SlinkOnez &Lz, SlinkOnez &L1, SlinkOnez &L2) {
    Lz->next=NULL;
    SlinkOnez pz = Lz;
    SlinkOnez p1 = L1->next;
    SlinkOnez p2 = L2->next;
    while (p1 && p2) {
        if (p1->cimi < p2->cimi) {
            pz->next = p1;
            pz = p1;//往下走一个
            p1 = p1->next;
        } else if (p1->cimi > p2->cimi) {
            pz->next = p2;
            pz = p2;//往下走一个
            p2 = p2->next;
        }else{
            if(0 !=(p1->data + p2->data)){
                p1->data = (p1->data+p2->data);//注意此处,重点,不能写成pz->data,否则会把当前p的值给替换掉,而不是赋值给下一个指针的值
                pz->next = p1;
                pz = p1;//往下走一个
            }
            p1=p1->next;
            p2=p2->next;
        }
    }

    if (p1!=NULL){
        pz->next=p1;
    }
    if (p2!=NULL){
        pz->next=p2;
    }
    return Lz;
}

6:使用

int main() {
    //第一个多项式
    SlinkOnez L;
    L = initLink();
    insertLink(L, 1, 9, 1);
    insertLink(L, 2, 4, 3);
    insertLink(L, 3, 6, 4);
    printL(L);
    //第二个多项式
    SlinkOnez L2;
    L2 = initLink();
    insertLink(L2, 1, 2, 3);
    insertLink(L2, 2, 4, 4);
    insertLink(L2, 3, 3, 7);
    insertLink(L2, 4, 3, 8);
    printL(L2);
    //合并后多项式
    SlinkOnez L3;
    L3=initLink();
    L3=mergeLink(L3,L,L2);
    printL(L3);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程技巧】条条大路通罗马

问题:对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能地高。 分析与解法 大多数的读者都会有这样的反应:这个题目也太简单了...

382110
来自专栏决胜机器学习

PHP数据结构(十九) ——B+树

PHP数据结构(十九)——B+树 (原创内容,转载请注明来源,谢谢) 一、概述 B+树是B树的变种,在数据库系统、文件系统等方面,B+树的运用...

52660
来自专栏程序生活

Python 过滤字母和数字实例1实例 2实例 3

34520
来自专栏杨建荣的学习笔记

关于oracle中的sql数据类型(r3笔记第59天)

数据类型对于每一种编程语言而言都是数据存储的基础,对于编程语言的实现功能而言也是一个标尺,有些编程语言可能数据类型很丰富,比如java,c,在数据计算方面的支持...

29440
来自专栏码匠的流水账

聊聊flink的CheckpointedFunction

flink-streaming-java_2.11-1.7.0-sources.jar!/org/apache/flink/streaming/api/chec...

18940
来自专栏书山有路勤为径

哈希表基础知识

哈希表(Hash table,也叫散列表),是根据关键字值(key)直接进行访问的数据结构,它通过把关键字值映射到表中一个位置(数组下标)来直接访问,以加快查找...

9210
来自专栏NetCore

解读C#中的正则表达式

 多少年来,许多的编程语言和工具都包含对正则表达式的支持,.NET基础类库中包含有一个名字空间和一系列可以充分发挥规则表达式威力的类,而且它们也都与未...

24870
来自专栏听Allen瞎扯淡

Integer的highestOneBit方法源码解析

在读HashMap源码的时候,遇到了Integer的highestOneBit静态方法不是太理解,所以就读了一下源码,这里记录一下。

39210
来自专栏V站

PHP常见函数和过滤函数的深入探究

32 位系统最大带符号的 integer 范围是 -2147483648 到 2147483647。举例,在这样的系统上, intval(‘1000000000...

30290
来自专栏数据结构与算法

BZOJ4355: Play with sequence(吉司机线段树)

这题最坑的地方在于对于操作1,$C >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么??

21120

扫码关注云+社区

领取腾讯云代金券