首页 > 其他分享 >链栈实现一元多项式的加法

链栈实现一元多项式的加法

时间:2022-10-05 18:14:19浏览次数:65  
标签:q1 LinkStack q2 LinkStackNode 多项式 next 链栈 加法 data2

链栈实现一元多项式的加法

1.初始化栈

1.1一元多项式的栈结构

typedef struct LinkStackNode{
    ElemType data1;//储存系数  ElemType可以指任意数据类型 本次使用的为int
    ElemType data2;//储存指数
    struct LinkStackNode* next;
}LinkStackNode,*LinkStack;

1.2两个空栈

void InitStack(LinkStack& S1,LinkStack& S2)
{
    S1 = (LinkStack)malloc(sizeof(LinkStackNode));
    S2 = (LinkStack)malloc(sizeof(LinkStackNode));
    S1->next = NULL;
    S2->next = NULL;
}

2.建立一元多项式

2.1算法思想

  1. 通过while循环持续读取一元多项式的系数和指数,循环结束条件为输入系数为0

  2. 将读取到的a,b的值传递给Push函数

  3. Push函数让系数,指数储存到栈中

2.2算法设计

//入栈操作
void Push(LinkStack& S,ElemType a,ElemType b)
{
    LinkStack temp= (LinkStack)malloc(sizeof(LinkStackNode));
    temp->data1 = a;
    temp->data2 = b;
    temp->next = S->next;
    S->next = temp;
}
​
//通过循环和Push函数让系数,指数储存到栈中
void InitLinkStack(LinkStack& S)
{
    int a, b, i = 1;
    printf("请按指数从大到小输入\n");
    printf("请输入第%d项的系数:", i);
    scanf("%d", &a);
    while (a != 0)
    {
        printf("请输入第%d项的指数:", i);
        scanf("%d", &b);
        Push(S, a, b);
        i++;
        printf("请输入第%d项的系数:", i);
        scanf("%d", &a);
    }
}

3.加法函数

3.1算法思想

  1. 用创建三个指示器p,q1,q2

    1. q1指向第一个式子的项(初值设为第一个链栈的首元结点)

    2. q2指向第二个式子的项(初值设为第二个链栈的首元结点)

    3. p指向q1的前一个结点(初值设为第一个链栈的头结点)

  2. 比较q1和q2指向项的指数大小(也就是比较q1->data2和q2->data2)

    1. q1->data2大于q2->data2,则将q2插到q1的前面,q1不变,让p重新指向q1的前继结点,q2指向后续结点

    2. q1->data2等于q2->data2,则将这两个项数的系数相加赋予q1,之和为零则删除该项,让q1,q2分别指向后继结点

    3. q1->data2小于q2->data2,则让q1指向后继结点,q2不变

  3. 如果q2先为空,则加法结束

  4. 如果q1先为空,则让p直接指向q2

     

3.2算法设计

void add(LinkStack& S1,LinkStack S2)
{
    LinkStack p = (LinkStack)malloc(sizeof(LinkStackNode));
    LinkStack q1 = (LinkStack)malloc(sizeof(LinkStackNode));
    LinkStack q2 = (LinkStack)malloc(sizeof(LinkStackNode));
    p = S1;
    q1 = S1->next;
    q2 = S2->next;
    while(q1 != NULL && q2 != NULL){
        if(q1->data2 > q2->data2)
        {
            LinkStack temp = (LinkStack)malloc(sizeof(LinkStackNode));
            temp->data1 = q2->data1;
            temp->data2 = q2->data2;
            p->next = temp;
            temp->next = q1;
            p = p->next;
            q2 = q2->next;
        }
        else if(q1->data2 == q2->data2)
        {
            q1->data1 = q1->data1 + q2->data1;
            if (q1->data1 == 0) 
            {
                p->next = q1->next;
                free(q1);
                q1 = p->next;
                q2 = q2->next;
            }
            else
            {
                q1 = q1->next;
                q2 = q2->next;
                p = p->next;
            }
        }
        else 
        {
            q1 = q1->next;
            p = p->next;
        }
    }
    if(q1==NULL)
    {
        p->next = q2;
    }
    printf("\n");
}
 

标签:q1,LinkStack,q2,LinkStackNode,多项式,next,链栈,加法,data2
From: https://www.cnblogs.com/wlb429/p/16756037.html

相关文章

  • 求多项式和 求序列最大值 的奇怪算法代码
         递归 ......
  • 链栈
    链栈采用链表作为储存结构实现的栈称为链栈1.初始化链栈1.1链栈的结构typedefstructLinkStackNode{ElemTypedata;structLinkStackNode*next;}LinkSta......
  • noi 1.5 36 计算多项式的值
    描述假定多项式的形式为xn+xn-1+…+x2+x+1,请计算给定单精度浮点数x和正整数n值的情况下这个多项式的值。输入输入仅一行,包括x和n,用单个空格隔开。x在float范围内,n<=10......
  • C语言实现顺序栈、单链栈、双向链栈
    #defineMaxlength8/***数据结构类型:顺序栈*插入方法:尾插法*是否有头节点:否*说明:在主函数直接定义一个结构体节点,取地址作形参,避免使用malloc函数而考虑二......
  • 高等数学 | 证明“指数 $\gg$ 多项式”的一个通式
    首先,有限项多项式可以放缩成\(f(x)\leMx^m\)。然后,去证\(\lim_{n\rightarrow\infty}\frac{Mn^m}{a^n}=0\),其中a>1。将\(a^n\)写作\((1+b)^n\),其中b>0。然后,因为......
  • T1012: 计算多项式的值(信息学一本通C++)
    [题目描述]对于多项式f(x)=ax3+bx2+cx+d和给定的a,b,c,d,x,计算f(x)的值,保留到小数点后7位。[输入]输入仅一行,包含5个实数,分别是x,及参数a、b、c、d的值,每个数都是绝对值......
  • 剑指 Offer II 002. 二进制加法【暴力】【模拟】
    题目给定两个01字符串a和b,请计算它们的和,并以二进制字符串的形式输出。输入为非空字符串且只包含数字1和0。难度:简单提示:1<=a.length,b.length<=104......
  • 多项式求逆&多项式 ln 保姆级教程
    话说原理八月初就会了,拖到现在才把代码写出来,是不是颓废之王?前置知识:多项式乘法(FFT/NTT)(参考阅读:可能是废话最多的FFT教程)一步一步推式子我们设$F(x)G(x)\equiv1\pmo......
  • 多项式全(?)家桶
    贴个板子,以备复习点击查看代码#include<cstdio>#include<cstdlib>#include<algorithm>#include<unordered_map>#include<cmath>#definemod998244353#definemax......
  • 多项式全家桶
    前置芝士:FTT&NTT不低于高中的数学推导能力不低于高中的代数芝士高等数学初步复变函数初步(?)多项式乘法目标:给定两个多项式\(F,G\),求\(F\timesG\)。有\(F(x)......