首页 > 其他分享 >一元多项式课设

一元多项式课设

时间：2023-06-27 11:06:57浏览次数：37  
标签：一元 p1 struct 课设 coef 多项式 iter exp Polynomial


代码详见


目录

 

一、实习任务........................................................................................... - 1 -

1.问题描述：.................................................................................... - 1 -

2.小组分工........................................................................................ - 1 -

二、实习过程........................................................................................... - 1 -

1．程序思想..................................................................................... - 1 -

三、代码实现........................................................................................... - 4 -

原始版本........................................................................................... - 4 -

优化版本：..................................................................................... - 12 -

四、程序运行结果与分析..................................................................... - 15 -

五、用户使用说明书和参考资料......................................................... - 16 -

1.用户说明书.................................................................................. - 16 -

2.参考资料...................................................................................... - 16 -

实验总结................................................................................................. - 17 -

 

 





 


一元多项式计算课程设计任务书

 

一、实习任务

  1. 问题描述：

能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入。

①根据问题描述，设计系统函数。

②完成各函数的定义。

  1. 小组分工

    张宇：完成代码以及查阅资料细节优化，完成报告。

鲁虹宇：完成部分代码以及构造程序框图，完成报告。

籍海洋：完成部分代码以及测试分析程序，完成报告。 

二、实习过程

1．程序思想

（一）数据结构的描述

（1）一元多项式求和实质上是合并同类项的过程，其运算规则为： 

      ①若两项的指数相等，则系数相加； 

②若两项的指数不等，则将两项加在结果中。

    一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。

本程序是利用单链表来表示一元多项式然后实现各项指数和系数的输入，进行多项式建立，并以多项式的形式输出，实现多项式的相加和相减这两种运算。由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。 采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递减有序排列。

一元多项式定义系数和指数结构如下： 

一元多项式课设_多项式

coef域--存放结点的系数值 （即存放非零项的系数）

expn域--存放结点的指数值 （即存放非零项的指数）

next域--存放结点的直接后继的地址（位置）的指针域（链域）

    定义多项式的结构为线性链表的存储结构，每个结点包含三个元素：系数coef，指数expn和指向下一个结点的指针*next。通过指针，我们就可以把多个单项式连接起来，形式一个多项式(单项式也是多项式)。

（2）建立多项式：尾插法建立一元多项式的链表，通过键盘输入多项式的系数和指数，以输入系数0为结束标志，并约定建立一元多项式链表时，总是按指数从小到大的顺序排列。

（3）输出多项式：从单链表的第一项开始逐项读出系数和指数，按多项式的形式输出。

（4）多项式相加：设p1和p2分别表示两个多项式。p1,p2,q分别表示指向单链表的当前项比较指数大小。如下：

①若p1->exp<p2->exp,则结点p1应是和多项式中的一项，将p1复制到q，并使p1后移。 

②若p1->exp = p2->exp,则将两个结点中的系数相加，当和不为0时，p1的系数域加上p2的系数域作为和多项式的系数域；若和为0，则和多项式中没有这一项，p1,p2后移。

③若p1->exp > p2->exp,则将结点p2复制到q中，p2后移。

（5）多项式减法：将减数多项式的所有系数先变为相反数，然后调用多项式相加的函数进行运算。

一元多项式课设_多项式_02

                        图1程序框图

一元多项式课设_多项式_03

一元多项式课设_一元多项式课设_04

       图2多项式减法流程图                    图3多项式加法流程图

 

三、代码实现

原始版本

#include <stdio.h>
#include <stdlib.h>
struct Polynomial
{
    int coef;
    int exp;
    struct Polynomial *next;
};
struct Polynomial *create();//建立多项式
 
struct Polynomial *insert(struct Polynomial *head,struct Polynomial *p);
 
void add(struct Polynomial *p1,struct Polynomial *p2);//多项式相加运算
 
void sub(struct Polynomial *p1,struct Polynomial *p2);//多项式相减运算
 
void print(struct Polynomial *p);//将多项式打印到屏幕
 
int main()
{
    struct Polynomial *p1,*p2;
    printf("请输入多项式A中x的系数及指数（输入0 0表示输入结束）:\n");
    p1=create();
    printf("\n");
    printf("A(x)=");
    print(p1);
    printf("请输入多项式B中x的系数及指数（输入0 0表示输入结束）:\n");
    p2=create();
    printf("\n");
    printf("B(x)=");
    print(p2);
    printf("\n\n");
    printf("A(x)+B(x)=");
    add(p1,p2);
    printf("\n\n");
    printf("A(x)-B(x)=");
    sub(p1,p2);
    printf("\n\n");
    return 0;
}
struct Polynomial *create()
{
    struct Polynomial *p,*q,*head;
    p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
    scanf("%d%d",&p->coef,&p->exp);
    head=NULL;
    while(p->coef!=0||p->exp!=0)
    {
        if(p->coef)
        head=insert(head,p);
        scanf("%d%d",&p->coef,&p->exp);
    }
    return head;
}
struct Polynomial *insert(struct Polynomial *head,struct Polynomial *p)
{
    struct Polynomial *q,*q1,*q2,*t;
    q=(struct Polynomial *)malloc(sizeof(struct Polynomial));
    q->coef=p->coef;
    q->exp=p->exp;
    q->next=NULL;
    if(head==NULL)
    {
        head=q;
        head->next=NULL;
        return head;
    }
    q2=q1=head;
    while(q1!=NULL)
    {
        while(q1->exp>p->exp)
        {
            q2=q1;
            if(q1->next==NULL)
                break;
            q1=q1->next;
        }
        if(q1->exp==p->exp)
        {
            q1->coef=q1->coef+p->coef;
            if(q1->coef==0)
            {
                if(q1==head)
                {
                    head=head->next;
                    break;
                }
                else
                {
                    q2->next=q1->next;
                }
            }
            else
                break;
        }
        else if(q1->exp>p->exp)
        { t=q1->next;
            q1->next=q;
            q->next=t;
            break;
        }
        else
        {
            if(q2==head&&q2->exp<q->exp)  //如果不加q2->exp>q->exp会出现二义性
            {
                q->next=head;
                head=q;
                break;
            }
            else
            {
                q2->next=q;
                q->next=q1;
                break;
            }
        }
    }
    return head;
};
 
void add(struct Polynomial *p1,struct Polynomial *p2)
{
    struct Polynomial*p,*q,*head;
    p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
    head=q=p;//插入排序的预备工作
    while(p1!=NULL||p2!=NULL)
    {
        if(p1==NULL)
        {
            while(p2!=NULL)
            {
                 q=p;                                         //p的前一节点
                 p->exp=p2->exp;
                 p->coef=p2->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p2=p2->next;
            }
        }
        else if(p2==NULL)
        {
            while(p1!=NULL)
            {
                 q=p;
                 p->exp=p1->exp;
                 p->coef=p1->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p1=p1->next;
            }
        }
        else
        {
            if(p1->exp>p2->exp)
            {
                 q=p;
                 p->exp=p1->exp;
                 p->coef=p1->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p1=p1->next;
            }
            else if(p1->exp==p2->exp)
            {
                 q=p;
                 p->exp=p1->exp;
                 p->coef=p1->coef+p2->coef;
                 if(p->coef!=0)
                 {
                     p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                     q->next=p;
                     p1=p1->next;
                     p2=p2->next;
                 }
                 else
                 {
                     p1=p1->next;
                     p2=p2->next;
                 }
            }
            else
            {
                 q=p;
                 p->exp=p2->exp;
                 p->coef=p2->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p2=p2->next;//前一个系数比后一个大，看下一个
            }
        }
    }
    q->next=NULL;
    print(head);
};
 
void sub(struct Polynomial *p1,struct Polynomial *p2)
{
    struct Polynomial*p,*q,*head;
    p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
    head=q=p;
    while(p1!=NULL||p2!=NULL)
    {
        if(p1==NULL)
        {
            while(p2!=NULL)
            {
                 q=p;
                 p->exp=p2->exp;
                 p->coef=-p2->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p2=p2->next;
            }
        }
        else if(p2==NULL)
        {
            while(p1!=NULL)
            {
                 q=p;
                 p->exp=p1->exp;
                 p->coef=p1->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p1=p1->next;
            }
        }
        else
        {
            if(p1->exp>p2->exp)
            {
                 q=p;
                 p->exp=p1->exp;
                 p->coef=p1->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p1=p1->next;
            }
            else if(p1->exp==p2->exp)
            {
                 q=p;
                 p->exp=p1->exp;
                 p->coef=p1->coef-p2->coef;
                 if(p->coef!=0)
                 {
                     p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                     q->next=p;
                     p1=p1->next;
                     p2=p2->next;
                 }
                 else
                 {
                     p1=p1->next;
                     p2=p2->next;
                 }
            }
            else
            {
                 q=p;
                 p->exp=p2->exp;
                 p->coef=-p2->coef;
                 p=(struct Polynomial *)malloc(sizeof(struct Polynomial));
                 q->next=p;
                 p2=p2->next;
            }
        }
 
    }
    q->next=NULL;
    print(head);
};
void print(struct Polynomial *p)//将多项式打印到屏幕
{
    struct Polynomial *p1;
    p1=p;
    if(p==NULL)
    {
        printf("0\n");
        return;
    }
    while(p1!=NULL)
    {
        if(p1==p)  //头结点输出时的情况
        {
            if(p1->coef==1&&p1->exp==0)
            printf("1");
            else if(p1->coef==-1&&p1->exp==0)
            printf("-1");
            else if(p1->coef==-1)
            printf("-");
            else if (p1->coef!=1)
            printf(" %d",p1->coef);
            if(p1->exp==1)
            printf("x");
            else if(p1->exp)
                printf("x^%d ",p1->exp);
        }
        else
        {
            if(p1->coef>0)
            {
                if(p1->coef!=1)
                 printf("+ %d",p1->coef);
                 else if(p1->exp==0)
                 printf("+ 1");
                 else printf("+");
                 if(p1->exp==1)
                 printf("x ");
                 else if(p1->exp)
                    printf("x^%d ",p1->exp);                
            }
            else
            {
                if(p1->coef==-1&&p1->exp==0)
                printf("- 1");
                else if(p1->coef==-1)
                printf("- ");
                else
                printf("- %d",-p1->coef);
                if(p1->exp==1)
                printf("x ");
                else if(p1->exp)
                    printf("x^%d ",p1->exp);
            }
        }
        p1=p1->next;
    }
    printf("\n");
}

优化版本：

#include<cstdio>
#include<list>
using namespace std;
struct polynomial {
      int coef;//系数
      int exp;//指数
      bool operator < (const struct polynomial b)const {
             return exp>b.exp;
      }
};
void comp( list<struct polynomial> &l) {//计算表达式
      list<struct polynomial> ans;
      l.sort();
      list<struct polynomial>::iterator iter=l.begin();
      while(l.size()) {
             struct polynomial temp;
             temp.exp=iter->exp;
             temp.coef=iter->coef;
             iter=l.erase(iter);
             while(iter->exp==temp.exp&&l.size()) {
                    temp.coef+=iter->coef;
                    iter=l.erase(iter);
             }
             if(temp.coef)
                    ans.insert(ans.end(),temp);
      }
      for(iter=ans.begin(); iter!=ans.end(); ++iter) {
 
             if(iter==ans.begin()) {
                    if(iter->coef==1&&iter->exp==0)
            printf("1");
            else if(iter->coef==-1&&iter->exp==0)
            printf("-1");
            else if(iter->coef==-1)
            printf("-");
            else if (iter->coef!=1)
            printf(" %d",iter->coef);
            if(iter->exp==1)
            printf("X");
            else if(iter->exp)
                printf("X^%d ",iter->exp);
             } else {
                    if(iter->exp) {//X项输出形式系数指数讨论
                           if(iter->coef>1&&iter->exp!=1)
                                  printf("+%dX^%d ",iter->coef,iter->exp);
                           else if(iter->coef<-1&&iter->exp!=1)
                                  printf("%dX^%d ",iter->coef,iter->exp);
                           else if(iter->coef==1&&iter->exp!=1)
                                  printf("+X^%d ",iter->exp);
                           else if(iter->coef==-1&&iter->exp!=1)
                                  printf("-X^%d ",iter->exp);
                           else if(iter->coef==1&&iter->exp==1)
                                  printf("+X ");
                           else  if(iter->coef==-1&&iter->exp==1)
                                  printf("-X ");
                           else if(iter->exp==1&&iter->coef<-1)
                                  printf("%dX ",iter->coef);
                           else if(iter->exp==1&&iter->coef>1)
                                  printf("+%dX ",iter->coef);
                    } else if(iter->coef>0)printf("+%d ",iter->coef);
                    else printf("%d ",iter->coef);
             }
      }
      l=ans;
}
void scan(list<struct polynomial> &l) {//输入表达式
      int coef, exp;
      while(scanf("%d %d",&coef,&exp)) {
             struct polynomial p;
             if(!coef&&!exp)
                    break;
if(coef) {
                     p.coef=coef;
                     p.exp=exp;
                     l.insert(l.end(),p);
             }
      }
      printf("表达式如下：\n");
      comp(l);
      printf("\n");
}
void operate(list<struct polynomial> &l) {//操作选择
      int choice;
      printf("输入操作选择：\n");
      printf("1.加法   2.减法\n");
      while(1) {
             scanf("%d",&choice);
             if(choice==1||choice==2)
                    break;
             printf("输入错误，重新输入\n");
      }
      if(choice==2)
             for(list<struct polynomial>::iterator iter=l.begin(); iter!=l.end(); ++iter)
                    iter->coef*=-1;
};
int main() {
      list<struct polynomial> la,lb;
      printf("请输入多项式A中x的系数及指数（输入0 0表示输入结束）:\n");
      scan(la);
      printf("请输入多项式B中x的系数及指数（输入0 0表示输入结束）:\n");
      scan(lb);
      operate(lb);
      la.merge(lb);
      printf("运算结果如下：\n");
      comp(la);
      return 0;
}



四、程序运行结果与分析

 

一元多项式课设_链表_05

代码（一）运行截图

 

 

一元多项式课设_一元多项式课设_06

代码（二）减法运算运行截图

 

 

 

代码（二）加法运算运行截图

 

五、用户使用说明书和参考资料

  1. 用户说明书

输入表达式按照：系数 指数 的格式输入，输入的结束以0 0 作为结束标志，两个表达式输入完毕后选择加减法进行计算即可。

算法的时间复杂度：第一种时间复杂度由于存在插入排序的限制，导致程序总体的时间复杂度为O（n^2）。

第二种优化程序由于使用了双指针链表实现了归并排序，并且加减法全部转化为加法，使得总体时间复杂度为O（n logn）。

  1. 参考资料

[1] C程序设计 谭浩强编著 清华大学出版社 2010.6

[2] 数据结构（C语言版） 严蔚敏 吴伟民 清华大学出版社 2011.11

[3] 面向对象程序设计与Visual C++6.0教程 陈天华 清华大学出版社 2006.1

[4] 操作系统教程 孙钟秀 高等教育出版社2005.7

 

标签：一元,p1,struct,课设,coef,多项式,iter,exp,Polynomial
From： https://blog.51cto.com/u_16171407/6561296

相关文章

  • 多项式（Ⅱ）：进阶工业
    书接上回多项式（Ⅰ）：基础工业。这部分主要写一下进阶的一些模板。多项式求逆多项式乘法逆给定一个多项式\(F(x)\)，求出一个多项式\(G(x)\)，满足\(F(x)*G(x)\equiv1(\bmod\x^n)\)。系数对\(998244353\)取模。我们先讨论比较简单的模数是\(998244353\)这样类型的。......
  • 数据结构课设打飞机————SFML如何配置到VS上
    解决这个问题真的是花费了我好长好长好长时间首先是SFML的版本安装，我用的编译器是VisualStudio2022，下载最新版本的SFML也没什么问题，但关键是这个（下图） 这两个版本的区别是一个32位一个64位我也是无语的今天才知道电脑如果是64位就下64位版本的，我一开始下载的是32位版本的所......
  • 多项式模复合的几乎线性算法, 支持多元多项式在线求值的数据结构
    本文简要介绍对于有限域\(\mathbbF_q\),如何快速计算多项式模复合\(f(g(X))\bmodh(X)\),其中\(f,g,h\)均是次数不超过\(n\)的多项式.介绍的思想汇总于2022年Bhargava,Ghosh,Guo,Kumar和Umans的工作:FastMultivariateMultipointEvaluationOverAllFinit......
  • 一元函数积分学
    目录一元函数积分学原函数与不定积分的概念导数与不定积分的关系牛顿-莱布尼茨公式基本积分表求不定积分直接积分法凑微分法换元积分法分部积分法定积分定积分的计算利用可加性利用积分限利用对称性利用几何意义定积分的几何应用平面图形的面积旋转体的体积平面曲线的弧长积分与导......
  • 多项式相关
    对Alex_wei博客的抄写。复数与单位根复数跳出实数域\(\mathbb{R}\)，定义\(i^2=-1\)，即\(i=\sqrt{-1}\)，并在此基础上定义复数\(a+bi\)，其中将\(b\not=0\)的称为虚数。复数域记为\(\mathbb{C}\)。我们根据上面的定义一下复数的四则运算。加法：\((a+bi)+(c+di)=(a+c......
  • R语言自适应LASSO 多项式回归、二元逻辑回归和岭回归应用分析|附代码数据
    值网格上计算套索LASSO或弹性网路惩罚的正则化路径正则化(regularization)该算法速度快，可以利用输入矩阵x中的稀疏性，拟合线性、logistic和多项式、poisson和Cox回归模型。可以通过拟合模型进行各种预测。它还可以拟合多元线性回归。”例子加载数据这里加载了一个高斯(连续Y)......
  • 第一天：一元函数的图形
    学习过程中须注意的几个点：1.log(n)和lg(n)在matlab中分别代表日常所见的ln(n)和log10(n);2.matlab中绘制反函数时只需要颠倒plot函数中x和y的位置即可；3.asin(x)即为arcsinx的意思；4.求反函数的函数为finverse(y,x);5.符号变量的定义：x=sym(‘x’,‘integer’)；6.图例函数：legend(......
  • java课设——《RookieSuperMario》【菜鸟版超级玛丽
    项目简介：我们团队利用面向对象开发方法和Javaswing框架，对经典游戏《SuperMario》进行编写。此项目共设施三个关卡，玩家可通过键盘来控制马里奥的移动，跳跃可以顶掉砖块，下落时还可以踩死蘑菇敌人，如果马里奥最终安全到达堡垒，则通关成功。个人项目负责任务： 创建背景类（BackGroun......
  • 任意模数多项式乘法（MTT）学习笔记
    三模数NTT常数大、速度慢、精度高是它的特点。在考虑三模数NTT之前先考虑一下中国剩余定理吧。已知\[\begin{cases}x\equivx_1(\bmodm_1)\\x\equivx_2(\bmodm_2)\\x\equivx_3(\bmodm_3)\\\end{cases}\]求\(x\bmodm_1m_2m_3\)。有\[\begin{aligned}&k_1m_1+......
  • 一元三次和四次方程的求根公式
    本文涉及一元三次、四次方程的解法。一元四次方程是有求根公式的最高次方程（这里的求根公式指用\(+\),\(-\),\(\times\),\(\frac{m}{n}\),\(\sqrt[k]{t}\)符号表示的公式），但其推导颇为复杂，所以接下来不妨先从一元三次方程入手。解这个方程：\[ax^3+bx^2+cx+d=0\]两边同时除以......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99