一元多项式运算的顺序结构

2022-03-29 19:48:08

#include<stdio.h>
#include<iostream.h>
using namespace std;
#define MAX 100
typedef struct{
 int coefarray[MAX+1];
 int highpower;//最高项指数 
} polyarray;
//创建多项式 
void Create(polyarray *L)
{
	int i,n,coef,index;
	L->highpower=0;
	for(i=0;i<MAX+1;i++)
	{
		L->coefarray[i]=0;
	}
	cout<<"输出多项式的项数：";
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"请输入第"<<i<<"项的系数和指数：";
		cin>>coef>>index;
		if(L->highpower<index);
		    L->highpower=index;
		    L->coefarray[index]=coef;
	} 
}
//输出多项式 
void Show(polyarray *L)
{
 if(L->coefarray[0]!=0)
 cout<<L->coefarray[0];
  for(int i=1;i<=L->highpower;i++)
  {
    if(L->coefarray[i]>0)
   cout<<"+"<<L->coefarray[i]<<"x^"<<i;
   else if(L->coefarray[i]<0)
    cout<<L->coefarray[i]<<"x^"<<i; 
  }}
//初始化
void Init(polyarray *L)
{
	int i;
	for(i=0;i<=MAX+1;i++)
	{
		L->coefarray[i]=0;
	}
	L->highpower=0;
}
//多项式相加 
void Add(polyarray *L1,polyarray *L2,polyarray *L3)
{
	int i;
	if(L1->highpower>L2->highpower)
	   L3->highpower=L1->highpower;
 	else
 	   L3->highpower=L2->highpower;
    for(i=0;i<=L3->highpower;i++)
    {
L3->coefarray[i]=L1->coefarray[i]+L2->coefarray[i];
    }}
//多项式相减
void Sub(polyarray *L1,polyarray *L2,polyarray *L3)
{
	int i;
	if(L1->highpower>L2->highpower)
	   L3->highpower=L1->highpower;
 	else
 	   L3->highpower=L2->highpower;
    for(i=0;i<=L3->highpower;i++)
    {
L3->coefarray[i]=L1->coefarray[i]-L2->coefarray[i];
    }} 
//多项式相乘
void Mult(polyarray *L1,polyarray *L2,polyarray *L3)
{	 
	L3->highpower=L1->highpower+L2->highpower;
	for(int i=0;i<=L1->highpower;i++)
	{
		for(int j=0;j<=L2->highpower;j++)
    {
    L3->coefarray[i+j]+=L1->coefarray[i]*L2->coefarray[j];
    }} }  
//菜单
void Menu()
{
        cout<<"\t***************************************\n";
        cout<<"\t>>>>>>>    1. 创建多项式        <<<<<<<\n";
        cout<<"\t>>>>>>>    2. 多项式加法        <<<<<<<\n";
        cout<<"\t>>>>>>>    3. 多项式减法        <<<<<<<\n";
        cout<<"\t>>>>>>>    4. 多项式乘法        <<<<<<<\n";
        cout<<"\t>>>>>>>    0. 退出系统          <<<<<<<\n"; 
        cout<<"\t***************************************\n";
} 
int main()
{
	polyarray *L1,*L2,*L3;
	L1=(polyarray*)malloc(sizeof(polyarray));
	L2=(polyarray*)malloc(sizeof(polyarray));	
	L3=(polyarray*)malloc(sizeof(polyarray));
	int num;
	Menu();
	while(1)
	{
cout<<"请输入要操作的序号：";
cin>>num;
switch(num)
{
case 1:
Create(L1);
cout<<"第一个多项式为：";
Show(L1);
cout<<endl<<endl;
Create(L2);
cout<<"第二个多项式为：";
Show(L2);
cout<<endl<<endl;
break;
case 2:
Init(L3);
Add(L1,L2,L3);
cout<<"相加后的结果为：";
Show(L3);
cout<<endl<<endl;
break;
case 3:
Init(L3);
Sub(L1,L2,L3);
cout<<"相减后的结果为：";
Show(L3);
cout<<endl<<endl;
  break;
case 4:
Init(L3);
Mult(L1,L2,L3);
cout<<"相乘后的结果为：";	
Show(L3);
cout<<endl<<endl;
break;
case 0:
exit(1);
break;
}
}
return 0;}

用五个函数分别实现一元多项式的创建、输出、加法、减法和乘法；然后在主函数中调用这些函数实现这些功能的展示（以菜单的形式呈现）。

数据结构

更多相关内容

数据结构 C++实现一元多项式运算（顺序存储结构实现）

千次阅读 2022-03-12 16:14:31

用顺序存储结构实现一元多项式的加法、减法和乘法。具体要求为：用五个函数分别实现一元多项式的创建、输出、加法、减法和乘法；然后在主函数中调用这些函数实现这些功能的展示。代码内容 #include<iostream>...

文章目录

实验目的

1、了解线性表的特性,以及它在实际问题中的应用。
2、掌握线性表的顺序存储的实现方法以及它的基本操作，学会运用线性表来解决问题。

实验内容

用顺序存储结构实现一元多项式的加法、减法和乘法。具体要求为：用五个函数分别实现一元多项式的创建、输出、加法、减法和乘法；然后在主函数中调用这些函数实现这些功能的展示。

代码内容

#include<iostream>
using namespace std;
#define maxdegree 100	//多项式最大项数

//定义多项式结构体
typedef struct polynomial {
	int coefarray[maxdegree+1];	//多项式系数
	int highpower;	//最高项指数
}polynomial;

//创建多项式
void creatlist(polynomial* L) {
	int  n, cofe, index;	//项数，系数，指数
	L->highpower = 0;	//多项式指数初始化
	for (int i = 0; i <= maxdegree; i++)
		L->coefarray[i] = 0;	//多项式系数初始化
	cout << "输入多项式项数" << endl;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cout << "请输入第" <<i<<"项的系数和指数"<< endl;
		cin >> cofe >> index;
		if (L->highpower < index)
			L->highpower = index;	//更新最高项指数
		L->coefarray[index] = cofe;	//把对应的多项式系数存入
	}
}

//初始化多项式
void initialize(polynomial* L) {
	for (int i = 0; i <= maxdegree + 1; i++)
		L->coefarray[i] = 0;
	L->highpower = 0;
}

//输出多项式
void printout(polynomial *L) {
	if (L->coefarray[0] != 0)
		cout << L->coefarray[0] << "+";	//判断常数项是否为零
	for (int i = 1; i < L->highpower; i++) {
		if (L->coefarray[i] == 0) 
			;	//判断该项是否存在
		else {
			if (L->coefarray[i] < 0)
				cout << "\b";	//如果是负数删掉+
			cout << L->coefarray[i] << "x^" << i << "+";
		}
	}
	cout << L->coefarray[L->highpower] << "x^" << L->highpower ;	//单独输出最后一项
}

//多项式加法
void add_polynomial(polynomial *L1,polynomial *L2,polynomial *L3) {
	if (L1->highpower > L2->highpower)	//判断最高项指数
		L3->highpower = L1->highpower;
	else
		L3->highpower = L2->highpower;
	for (int i = 0; i <= L3->highpower; i++)
		L3->coefarray[i] = L1->coefarray[i] + L2->coefarray[i];
}

//多项式减法
void subtruct_polynomial(polynomial* L1, polynomial* L2, polynomial* L3) {
	if (L1->highpower > L2->highpower)	//判断最高项指数
		L3->highpower = L1->highpower;
	else
		L3->highpower = L2->highpower;
	for (int i = 0; i <= L3->highpower; i++)
		L3->coefarray[i] = L1->coefarray[i] - L2->coefarray[i];
}

//多项式乘法
void multiply_polynomial(polynomial* L1, polynomial* L2, polynomial* L3) {
	L3->highpower = L1->highpower + L2->highpower;	//同底数相乘等于底数不变幂数相加
	for (int i = 0; i <= L1->highpower; i++)
		for (int j = 0; j <= L2->highpower; j++)
			L3->coefarray[i + j] += L1->coefarray[i] * L2->coefarray[j];

}

//菜单函数
void display() {
	cout << "========================"<<endl;
	cout << "1.创建多项式" << endl;
	cout << "2.多项式加法" << endl;
	cout << "3.多项式减法" << endl;
	cout << "4.多项式乘法" << endl;
	cout << "0.退出" << endl;
	cout << "========================" << endl;
}

int main() {
	//为L1,L2,L3动态分布空间
	polynomial* L1 = new polynomial;
	polynomial* L2 = new polynomial;
	polynomial* L3 = new polynomial;
	int n;
	display();	//调用菜单函数
	while (true){
		cout << "请输入要执行的操作：" ;
		cin >> n;
		switch (n){
		case 1:
			creatlist(L1);	//调用创建多项式函数
			cout << "第一个多项式为：" ;
			printout(L1);
			cout << endl;
			creatlist(L2);
			cout << "第二个多项式为：";
			printout(L2);
			cout << endl;
			break;
		case 2:
			initialize(L3);	//调用初始化函数
			add_polynomial(L1, L2, L3);	//调用加法函数
			cout << "相加后结果为：" << endl;
			printout(L3);
			cout << endl;
			break;
		case 3:
			initialize(L3);
			subtruct_polynomial(L1, L2, L3);	//调用减法函数
			cout << "相减后结果为：" << endl;
			printout(L3);
			cout << endl;
			break;
		case 4:
			initialize(L3);
			multiply_polynomial(L1, L2, L3);	//调用乘法函数
			cout << "相乘后结果为：" << endl;
			printout(L3);
			cout << endl;
			break;
		case 0:
			exit(1);	//退出程序
		default:
			cout << "输入不合法，请重新输入！" << endl;
			cout << endl;
			break;
		}
	}
	delete L1, L2, L3;	//释放L1,L2,L3动态内存空间
	return 0;
}

运行结果

测试数据：
在这里插入图片描述

在这里插入图片描述

总结

代码中的算法很容易实现，只需要把两个数组对应的分量项进行加减乘运算即可，但顺序存储只适合稠密多项式，如果是系数多项式的话就很浪费空间和时间。

收起

展开全文

数据结构

一元多项式运算（顺序存储结构实现）（C语言）

千次阅读 2022-03-13 22:58:47

用顺序存储结构实现一元多项式的加法、减法和乘法

一．目的要求

1、了解线性表的特性,以及它在实际问题中的应用。

2、掌握线性表的顺序存储的实现方法以及它的基本操作，学会运用线性表来解决问题。

二．设计内容

用顺序存储结构实现一元多项式的加法、减法和乘法。具体要求为：用五个函数分别实现一元多项式的创建、输出、加法、减法和乘法；然后在主函数中调用这些函数实现这些功能的展示（最好以菜单的形式呈现）。

三、设计思路

将顺序表数组下标作为多项式的指数项，数组内的数据元素存放多项式的系数，通过访问数组内元素的同时获取下标并对二者进行不同的运算后，将运算结果依旧按原形式放入新的数组中，完成对两个多项式的加减乘运算。

三．测试数据

多项式1：2-3x+6x^2-3x^5+7x^6（即输入2 0 -3 1 6 2 -3 5 7 6）（输入-1 -1结束输入）

多项式2：1+7x+6x^2-4x^3+3x^5（即输入1 0 7 1 6 2 -4 3 3 5）（输入-1 -1结束输入）

四．源程序清单

/**
*Created by SongBy on 2022/03/13.
*/
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20/*表可能达到的最大长度，存储空间初始分配量*/

typedef int ElemType;/*表的数据类型，根据实际情况而定*/

typedef struct {
    ElemType *data;/*数组存储数据元素，最大值为MAXSIZE*/
    int highPower;/*最高次项*/
} SqList;

/*操作结果：构造一个空的线性表L*/
void InitList(SqList *L) {
    L->data = (ElemType *) malloc(sizeof(ElemType) * MAXSIZE);/*申请连续的MAXSIZE长度空间*/
    if (!L->data)/*判断空间是否申请成功*/
        exit(-1);
    for (int i = 0; i < MAXSIZE; i++)
        L->data[i] = 0;
    L->highPower = 0;/*空表最高次项为0*/
}

/*初始条件：线性表已存在*/
/*操作结果：销毁线性表L*/
void DestroyList(SqList *L) {
    free(L->data);/*释放data指向的空间*/
    L->data = NULL;
    L->highPower = 0;
}

/*创建多项式：由用户输入多项式的每项系数与指数*/
void CreatePolynomial(SqList *L) {
    int coefficient, exponent;

    for (int i = 0; i < 10; i++)/*循环输入常数项的每一项*/
    {
        printf("\n请输入第%d项的常数项和指数项，结束请输入-1 -1：", i + 1);
        scanf("%d%d", &coefficient, &exponent);
        if (exponent != -1) /*指数为-1则结束输入*/
        {
            L->data[exponent] += coefficient;/*数组下标为指数项，常数项存入下标对应的位置，若有相同指数项则常数项相加*/
            if (L->highPower < exponent) /*指数项最大项为多项式长度*/
                L->highPower = exponent;
        } else
            break;
    }
    printf("输入完毕\n");
}

/*输出常数项：按多项式指数大小依次输出多项式每一项*/
void PrintPolynomial(SqList L) {
    printf("多项式为:");

    if (L.data[0] != 0)/*若常数项为0则不输出，若不为0则只输出常数项*/
        printf("%d", L.data[0]);

    if (L.data[1] > 0)/*若常数项为0则不输出*/
        printf("+%dx", L.data[1]);/*不输出指数项为1*/
    else if (L.data[1] < 0)
        printf("%dx", L.data[1]);

    for (int i = 2; i <= L.highPower; i++)/*从第二项开始输出指数项*/
        if (L.data[i] > 0)/*若常数项为0则不输出该项*/
            printf("+%dx^%d", L.data[i], i);
        else if (L.data[i] < 0)
            printf("%dx^%d", L.data[i], i);

    printf("\n");
}

/*两多项式相加*/
void TwoPolynomialAdd(SqList L1, SqList L2, SqList *L3) {
    L3->highPower = L1.highPower > L2.highPower ? L1.highPower : L2.highPower;/*获取两多项式的最大项以确定相加后的多项式的最大项*/
    for (int i = 0; i <= L3->highPower; i++)/*通过循环将两个多项式的同指数项的系数相加并保存到新的多项式中*/
        L3->data[i] = L1.data[i] + L2.data[i];
}

/*两多项式相减*/
void TwoPolynomialSub(SqList L1, SqList L2, SqList *L3) {
    L3->highPower = L1.highPower > L2.highPower ? L1.highPower : L2.highPower;/*获取两多项式的最大项以确定相加后的多项式的最大项*/
    for (int i = 0; i <= L3->highPower; i++)/*通过循环将两个多项式的同指数项的系数相减并保存到新的多项式中*/
        L3->data[i] = L1.data[i] - L2.data[i];
}

/*两多项式相乘*/
void TwoPolynomialMul(SqList L1, SqList L2, SqList *L3) {
    L3->highPower = L1.highPower + L2.highPower;/*两多项式的最高项相加为新多项式的最高项*/
    for (int i = 0; i <= L1.highPower; i++)
        for (int j = 0; j <= L2.highPower; j++)/*通过双层循环将两个多项式的每一项两两相乘与并保存到新的多项式中*/
            L3->data[i + j] += L1.data[i] * L2.data[j];/*相乘后的指数项为两项指数项相加*/
}

int Menu() {
    int a;
    printf("输入1创建两个多项式\t\t输入2输出两个多项式\n");
    printf("输入3将两个多项式相加 \t\t输入4将两个多项式相减\n");
    printf("输入5将两个多项式相乘 \t\t输入0退出\n");
    printf("请输入：");
    scanf("%d", &a);
    return a;
}

int main() {
    SqList L1, L2, L3;
    InitList(&L1);
    InitList(&L2);
    InitList(&L3);

    while (1) {
        switch (Menu()) {
            case 1:
                printf("\n请输入多项式 1 ：");
                CreatePolynomial(&L1);
                printf("\n多项式 1 为：\n");
                PrintPolynomial(L1);
                printf("\n请输入多项式 2 ：");
                CreatePolynomial(&L2);
                printf("\n多项式 2 为：\n");
                PrintPolynomial(L2);
                break;
            case 2:
                printf("\n多项式 1 为：\n");
                PrintPolynomial(L1);
                printf("\n多项式 2 为：\n");
                PrintPolynomial(L2);
                break;
            case 3:
                InitList(&L3);
                TwoPolynomialAdd(L1, L2, &L3);
                printf("两多项式相加后的结果");
                PrintPolynomial(L3);
                break;
            case 4:
                TwoPolynomialSub(L1, L2, &L3);
                printf("两多项式相减后的结果");
                PrintPolynomial(L3);
                break;
            case 5:
                DestroyList(&L3);
                InitList(&L3);
                TwoPolynomialMul(L1, L2, &L3);
                printf("两多项式相乘后的结果");
                PrintPolynomial(L3);
                break;
            case 0:
                printf("谢谢使用！\n");
                exit(0);
            default:
                printf("暂无此功能\n");
        }
    }
}

五、运行结果

相加结果：3+4x+12x^2-4x^3+7x^6

相减结果：1-10x+4x^3-6x^5+7x^6

相乘结果： 2+11x-3x^2+16x^3+48x^4-21x^5-23x^6+49x^7+54x^8-28x^9-9x^10+21x^11

收起

展开全文

数据结构

一元多项式运算数据结构课设.zip
2022-06-24 08:54:11

设有一元多项式Am(x)和Bn(x)，Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm，Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn，请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。分别采用顺序和链式存储结构实现；结果...

收起

数据结构
一元多项式的运算（加减乘）终极版
2018-12-02 21:36:12

实现了一元多项式的加减乘的运算。我们使用计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称为线性的数据结构。而数据存储结构有两种：顺序存储结构和链式存储结构。线性表是最常用且最...

收起
一元稀疏多项式运算代码
2020-12-20 20:01:37

设计程序，输入两个一元稀疏多项式，分别完成二者的加法、减法、乘法运算，输出和多项式、差多项式、乘积... 1、分别以顺序表和单链表为存储结构实现多项式的加法和减法运算。 2、乘法运算的实现使用单链表为存储结构

收起
C/C++:一元多项式的表示及其运算.rar(含注释)
2021-03-04 21:43:19

符号多项式的操作，已经成为表处理的典型用例。在数学上，一个一元多项式Pn(x)可按升幂写 ...本题要求选用线性表的一种合适的存储结构来表示一个一元多项式，并在此结构上实现一元多项式的加法，减法和乘法操作

收起

C语言数据结构实现——一元多项式的基本运算

千次阅读 多人点赞 2022-03-17 20:52:09

该算法使用C语言的数据结构知识实现一元多项式的基本运算（加法、减法、乘法）。

问题描述：

在这里插入图片描述

第一种算法：顺序存储结构实现——顺序表

（1）算法思路：
算法要实现两个一元多项式相关的相关运算，相加、相减、相乘。首先我们要选取一种存储结构来存放我们多项式的每一项，我们可以采用顺序存储结构中的顺序表来实现多项式的存储。用一个数组a存储多项式的相关数据：数组分量a[i]表示项 X^i前的系数，用数组分量下标对应相应项的指数，我们的数组分量值就是对应这一项的系数。
例如，f(x)=6+8X+2X^2+6*X5，可以用一个顺序表来表示：
在这里插入图片描述
这种方法在一般情况下对一元多项式实现相关运算是比较方便的。我们顺序表实现两个一元多项式的相加，只要把两个数组的对应分量相加就行了，代码很容易实现，同理多项式的减法也较容易实现。实现两个一元多项式的乘法，我们首先选定一个多项式，让它的每一项另一个多项式的每一项依次相乘，乘完后用一个临时顺序表来保存得到的结果，将得到的所有临时顺序表相加起来就是两个多项式相乘的结果。
但是用顺序表来实现也存在重大的问题，就是在多项式比较稀疏的情况下（多项式有较高的阶，但是只有很少的非零项。）,算法的时间和空间效率比较差。例如： f(x)=1+2X+3X^3000,表示这个多项式的顺序表要采用一个大小至少为3001的数组，但是这个数组中的大部分数据为0，只有3项不为零，空间浪费严重。而且我们要遍历这个存储多项式的顺序表，要遍历3001次，时间复杂度较高。这主要是顺序表实现该算法的缺点。

（2）算法代码：

#include<stdio.h>

#include<stdlib.h>

#define maxsize 100

typedef struct node {

	int a[maxsize];

	int length;

} list;

//初始化顺序表

list* creat_list()

{

	struct node* L;

	L = (list*)malloc(sizeof(struct node));

	L->length = 0;

	return L;

}

void input(list* L)//一元多项式的输入

{

	int i;

	printf("请输入此多项式的项数：");

	scanf("%d", &L->length);

	for (i = 0; i < L->length; i++)

	{

		printf("请输入此多项式X^%d项的系数： ", i);

		scanf("%d", &L->a[i]);

	}

	printf("\n");

}

void output(struct node* L) //一元多项式的输出

{

	int i, t = 0;

	for (i = L->length - 1; i >= 0; i--)

	{

		if (L->a[i] == 0)

		{

			t++;

			continue;

		}

		else

		{

			if (i == 0)

			{

				if (L->a[i] < 0)

					printf("%d", L->a[i]);

				else

					printf("+%d", L->a[i]);

			}

			else if (0 < i && i < L->length - 1)

			{

				if (i == 1)

				{

					if (L->a[i] < 0)

						printf("%d*X", L->a[i]);

					else

						printf("+%d*X", L->a[i]);

				}

				else

				{

					if (L->a[i] < 0)

						printf("%d*X^%d", L->a[i], i);

					else

						printf("+%d*X^%d", L->a[i], i);

				}

			}

			else if (i == L->length - 1)

			{

				if (i == 1)

				{

					printf("%d*X", L->a[i]);

				}

				else

					printf("%d*X^%d", L->a[i], i);

			}

		}

	}

	if (t == L->length)

	{

		printf("0\n");

	}

	printf("\n");

}

list* sum(list* L1, list* L2) //实现两个一元多项式的相加操作

{

	int i, h;

	struct node* p;

	list* L3;

	L3 = creat_list();

	if (L1->length <= L2->length)

	{

		p = L1;

		h = L2->length - L1->length;

	}

	else

	{

		p = L2;

		h = L1->length - L2->length;

	}

	for (i = 0; i < p->length; i++)

	{

		L3->a[i] = L1->a[i] + L2->a[i];

		L3->length++;

	}

	if (h != 0)

	{

		if (p == L1)

		{

			for (i = L1->length; i <= L2->length - 1; i++)

			{

				L3->a[i] = L2->a[i];

				L3->length++;

			}

		}

		else

			for (i = L2->length; i <= L1->length - 1; i++)

			{

				L3->a[i] = L1->a[i];

				L3->length++;

			}

	}

	return L3;

}

list* poor(list* L1, list* L2)//实现两个一元多项式的相减操作

{

	int i, h;

	struct node* p;

	list* L;

	L = creat_list();

	h = L1->length - L2->length;

	if (h <= 0)

	{

		p = L1;

	}

	else

	{

		p = L2;

	}

	for (i = 0; i < p->length; i++)

	{

		L->a[i] = L1->a[i] - L2->a[i];

		L->length++;

	}

	if (h != 0)

	{



		if (p == L2)

		{

			for (i = L2->length; i <= L1->length - 1; i++)

			{

				L->a[i] = L1->a[i];

				L->length++;

			}

		}

		if (p == L1)

		{

			for (i = L1->length; i <= L2->length - 1; i++)

			{

				L->a[i] = -1 * (L2->a[i]);

				L->length++;

			}

		}

	}

	return L;

}

list* multiply(list* L1, list* L2)  //实现两个多项式的相乘

{

	int i, j, k;

	list* L;

	L = creat_list();

	for (i = 0; i <= L1->length - 1; i++)

	{

		list* p = creat_list();

		p->length = i + L2->length;

		for (k = 0; k <= p->length - 1; k++)

		{

			p->a[k] = 0;

		}

		for (j = 0; j <= L2->length - 1; j++)

		{

			p->a[i + j] = L1->a[i] * L2->a[j];

		}

		L = sum(L, p);

	}

	return L;

}

void show()

{

	printf("\t\t    指令集合\n");

	printf("\n\t1 《《《《《 一元多项式的加法运算\n");

	printf("\n\t2 《《《《《 一元多项式的减法运算\n");

	printf("\n\t3 《《《《《 一元多项式的乘法运算\n");

}

void main()

{

	int i, h;

	list* P;

	list* L[2];

	for (i = 0; i < 2; i++)

	{

		L[i] = creat_list();

		printf("\t请输入第%d个一元多项式\n", i + 1);

		input(L[i]);

		printf("第%d个一元多项式的表达式为：\n", i + 1);

		printf("\tF%d(X)=", i + 1);

		output(L[i]);

		printf("\n\n");

	}

	show();

	printf("请对两个多项式选择相关运算指令：\n");

	scanf("%d", &h);

	switch (h)

	{

		case 1:

			P = sum(L[0], L[1]);

			printf("两个一元多项式的和为：\n\tF3(X)=");

			output(P);
			break;

		case 2:

			printf("两个一元多项式的差为：\n\tF3(X)=");

			P = poor(L[0], L[1]);

			output(P);
			break;

		case 3:

			printf("两个一元多项式的乘积为：\n\tF3(X)=");

			P = multiply(L[0], L[1]);

			output(P);
			break;

		default:

			printf("指令错误！\n");

	}

}

（3）代码运行结果：

加法运算：在这里插入图片描述
减法运算：

乘法运算：
（4）代码分析：
从(2)中代码可以看出，实现一元多项式的加，减和乘运算的函数的时间复杂度为O(N^{2)，所以我们整体算法的时间复杂度为:O(N}2)。但是这种算法存在重大的问题，就是在多项式比较稀疏的情况下（多项式有较高的阶，但是只有很少的非零项。）,算法的时间和空间效率比较差。例如： f(x)=1+2X+3X^3000,表示这个多项式的顺序表要采用一个大小至少为3001的数组，但是这个数组中的大部分数据为0，只有3项不为零，空间浪费严重。当我们要遍历这个存储多项式的顺序表，要遍历3001次，时间复杂度较高。当一元多项式中项中X的的指数过大时，算法的性能较差。

顺序存储结构—— 算法改进思路

在多项式比较稀疏的情况下（多项式有较高的阶，但是只有很少的非零项。）算法的时间和空间效率比较差，我们打算对其进行改进，我们主要提出了其改进思路。
采用顺序存储结构来表示一元多项式的非零项，多项式的每一项都有两个信息，系数和指数，因此我们可以用一个结构体数组来表示我们一元多项式，结构体数组的每一项表示一元多项式的一个非零项。数组的大小可以根据非零项的最多个数来确定，而并不是根据多项式的最高阶来确定。这种方法。对于稀疏多项式的情况下能够节省大量的空间。但是多项式并不是很稀疏，则节省空间的优势就没有了，反而会导致运算过于复杂。例如，我们用这种方法实现两个一元多项式的相加操作的具体过程为：首先我们应该对这两个多项式按指数对多项式进行排列（按指数依次大到小排列多项式的每一项），之后从头开始查看两个多项式的每一项，如果当前两项的指数不一样，则将两个多项式中指数较大的那一项给我们临时创建的结果多项式中；如果它们的指数一样而且对应系数和不为零，那么就将这两项的和与其指数放入到我们的结果多项式中。这种方法的运算较为复杂，而且用数组表示多项式的灵活性也不高。更进一步的解决方案就是利用链式存储结构——单链表来表示我们的多项式效果会更好，更具有灵活性。

第二种算法：链式存储结构实现——单链表

1）算法实现思路：

实现两个一元多项式相关的相关运算，相加、相减、相乘。可以选取链表来存放多项式的每一项的两项数据，每一次输入数据时向系统申请分配存储空间，每次存储只需要存放其系数和幂。两个多项式的项系数和幂分别存在两个链表中，在进行加、减、乘运算时首先找到不同链表中同类项（即幂相同的项），再进行系数的运算。例如链表A中存放数据2（系数） 1（幂），B中有一组数据5（系数） 1（幂）。在运算时我们首先需要在链表B中找到幂为1的数据，找到后用其系数进行运算，如上例中2+5=7，2-5=-3。在进行乘法运算时依次拿出A链表中的项系数与B链表中的每一项系数依次相乘，并存放在一个新链表C中。最后输出链表中的数据后需要释放其内存。
（2）算法代码：

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define OK 1

#define NO 0

#define MAXSIZE 20

typedef char Excelelem;

typedef struct Node

{

	int xishu;

	int mi;

	struct Node *next;

} LNode,*LinkList;



typedef struct

{

	Excelelem name[100];

	int length;

	LinkList next;

} HeadList,*HeadLinkList;



LinkList Init(int *n); //函数声明

HeadLinkList HeadInit(char a[]);

LinkList FIND(LinkList Head,int s);

void ADD(HeadLinkList A,HeadLinkList B,HeadLinkList C);

void SUB(HeadLinkList A,HeadLinkList B,HeadLinkList C);

void Free(HeadLinkList Head);

void cout(HeadLinkList Head);

void MUL(HeadLinkList A,HeadLinkList B,HeadLinkList C);



int main()

{

	HeadLinkList A,B,C;

	int n;

	A=HeadInit("A多项式");

	printf("请输入%s:\n",A->name);

	A->next=Init(&A->length);

	B=HeadInit("B多项式");

	printf("请输入%s:\n",B->name);

	B->next=Init(&B->length);

	C=HeadInit("C多项式");

	C->next=NULL;

	printf("%s+%s:\n",A->name,B->name);

	ADD(A,B,C);

	cout(C);

	printf("%s-%s:\n",A->name,B->name);

	SUB(A,B,C);

	cout(C);

	printf("%s*%s:\n",A->name,B->name);

	MUL(A,B,C);

	cout(C);

	Free(A);

	Free(B);

	Free(C);

	free(A),free(B),free(C);

	return 0;

}



LinkList FIND(LinkList Head,int s)//查找链表中第一个系数大于ans的结点的前驱

{

	if(Head->next == NULL || Head->next->mi > s)

		return Head;

	return FIND(Head->next,s);

}



LinkList Init(int *n)//初始化链表体

{

	LinkList Head,p,q;

	int i=0;

	int a,b;

	Head=NULL;

	while(~scanf("%d",&a) && a!=0)

	{

		scanf("%d",&b);

		q=(LinkList)malloc(sizeof(LNode));

		q->xishu=a;

		q->mi=b;

		if(*n==0 || Head->mi>b) q->next=Head,Head=q;

		else

		{

			p=FIND(Head,b);

			q->next=p->next;

			p->next=q;

		}

		*n++;

	}

	return Head;

}



HeadLinkList HeadInit(char *a)//初始化链表头

{

	HeadLinkList Head;

	Head=(HeadLinkList)malloc(sizeof(HeadList));

	strcpy(Head->name,a);

	Head->length=0;

	return Head;

}



void ADD(HeadLinkList A,HeadLinkList B,HeadLinkList C)//多项式加法 O(n)

{

	LinkList qa=A->next,qb=B->next,p,q=NULL;

	Free(C);

	while(qa || qb)

	{

		p=(LinkList)malloc(sizeof(LNode));

		if(qb==NULL || qa && qa->mi<qb->mi)

		{

			*p=*qa;

			qa=qa->next;

		}

		else if(qa==NULL || qb && qa->mi>qb->mi)

		{

			*p=*qb;

			qb=qb->next;

		}

		else

		{

			p->xishu=qb->xishu+qa->xishu;

			p->mi=qb->mi;

			qa=qa->next;

			qb=qb->next;

		}

		if(q==NULL) p->next=q,C->next=q=p;

		else

			p->next=q->next,q->next=p,q=p;

		C->length++;

	}

}



void SUB(HeadLinkList A,HeadLinkList B,HeadLinkList C)//多项式减法 O(n)

{

	LinkList qa=A->next,qb=B->next,p,q=NULL;

	Free(C);

	while(qa!=NULL || qb!=NULL)

	{

		p=(LinkList)malloc(sizeof(LNode));

		if(qb==NULL || qa && qa->mi<qb->mi)

		{

			*p=*qa;

			qa=qa->next;

		}

		else if(qa==NULL || qb && qa->mi>qb->mi)

		{

			*p=*qb;

			p->xishu*=-1;

			qb=qb->next;

		}

		else

		{

			*p=*qa;

			p->xishu-=qb->xishu;

			qa=qa->next;

			qb=qb->next;

			if(p->xishu==0)

			{

				free(p);

				continue;

			}

		}

		if(q==NULL) p->next=q,C->next=q=p;

		else

			q->next=p->next,q->next=p,q=p;

		C->length++;

	}

}



void MUL(HeadLinkList A,HeadLinkList B,HeadLinkList C)//多项式乘法 O(n^3)

{

	LinkList qa,qb,p,q;

	int a,b;

	Free(C);

	for(qa=A->next; qa; qa=qa->next)

	{

		for(qb=B->next; qb; qb=qb->next)

		{

			a=qa->xishu*qb->xishu;

			b=qa->mi+qb->mi;

			if(C->length)

			{

				p=FIND(C->next,b);

				if(p->mi == b)

					p->xishu+=a;

				else

				{

					q=(LinkList)malloc(sizeof(LNode));

					q->xishu=a;

					q->mi=b;

					q->next=p->next;

					p->next=q;

					C->length++;

				}

			}

			else

			{

				p=(LinkList)malloc(sizeof(LNode));

				p->xishu=a;

				p->mi=b;

				p->next=C->next;

				C->next=p;

				C->length++;

			}

		}

	}

}



void Free(HeadLinkList Head)//释放链表体内存

{

	LinkList q=Head->next,p;

	while (q)

	{

		p=q;

		q=q->next;

		free(p);

	}

	Head->length=0;

	Head->next=NULL;

	return ;

}



void cout(HeadLinkList Head)//将链表数据域以多项式形势输出

{

	LinkList q=Head->next;

	while(q)

	{

		if(q->xishu>0 && q!=Head->next)

			printf("+");

		printf("%.1dx^(%.1d)",q->xishu,q->mi);

		q=q->next;

	}

	printf("\n");

	return ;

}

**（3）代码运行结果：**
在这里插入图片描述
（4）代码分析：
该算法的时间复杂度为O（n²）。利用链表解决该问题的优点是处理离散程度较大的数据时（如f(x)=1+2X+3X^3000）可以大大节省空间，因为链表的存储地址不需要连续，可以根据需要动态分配空间。缺点则是在处理连续的数据时存储密度小（相比较顺序表而言）。

收起

展开全文

数据结构

数据结构 一元多项式运算
千次阅读 多人点赞 2018-04-20 17:49:14

链表的生成利用链表实现一元多项式的+、-、*运算，注意具体的思路是判断同类项，对其进行合并同类项，在乘法运算达到了O(n^3)，可以优化的地方是先对结果链表C进行预处理，先复制这个链表给C，然后表C的操作过程就将...

收起
案例2.1-一元多项式的运算（顺序表实现）
2021-10-23 21:47:05

案例2.1-一元多项式的运算（顺序表实现） #include<iostream> #include<string> using namespace std; #define MAX 20 typedef struct//定义存放多项式的数组类型 { double coef;//系数 int exp;//...

收起

数据结构
数据结构—— 一元多项式的加法运算
万次阅读 多人点赞 2019-09-24 12:01:56

设Pn(x)和Qn(x)分别为两个一元多项式，请求出两个一元多项式的加法运算的结果，要求元素按照多项式的次数递减的次序排列。 1.问题分析需求：实现两个一元多项式的加法运算。实现功能：①通过键盘接收输入的整数...

收起

数据结构
如何利用线性表？完成一元多项式运算【内容丰富，简单易懂】
2022-01-11 16:29:49

如何利用线性表完成一元多项式运算。多项式每项coef是该项系数，exp是变元x的指数单循环链表、结构体模板、类模板、友元函数以及运算符重载、程序设计思路、项结点实现多项式类、多项式的输入和输出、多项式相加、...

收起

数据结构
数据结构—— 一元多项式的运算（相加，相减，相乘）【C语言实现】
万次阅读 多人点赞 2018-10-28 21:17:37

用 C语言实现一元多项式的运算（相加，相减，相乘） 1.创建多项式时，无论指数项按什么顺序输入，输出均能实现以升幂顺序输出，且输入时有相同指数项时能够实现合并。 2.能够代入确切的X计算出最终多项式的值。 ...

收起

数据结构一元多项式的运算
利用线性表实现一个一元多项式
2018-12-07 22:55:25

能够实现一元多项式的输入和输出能够进行一元多项式相加能够进行一元多项式相减能够计算一元多项式在x处的值能够计算一元多项式的导数（选作）能够进行一元多项式相乘编写main ()函数测试算法的正确性

收起
数据结构：一元多项式及其基本运算
千次阅读 多人点赞 2019-08-03 17:25:16

1、实现方式：可采用线性表的顺序存储结构，但是当多项式的每个项的指数差别很大时，会浪费很...3、一元多项式的加法运算：设La和Lb分别表示两个多项式。Lc表示和多项式。p,q,r分别表示指向单链表的当前项比较指数...

收起
一元多项式计算器（程序对于多项式运算非常通用、细节很多详见描述与代码）
2020-12-17 00:45:47

程序支持除题目要求外的所有“任意多个”一元多项式加减运算输入: 测试用例: -(2x^3+5x^4)+2x^5+(2x+5x^8-3.1x^11)+4x^6+2x^2+(7-5x^8+11x^9)+(x+x^2-x^3)+10= -2x^5+(2x+5x^8-3.1x^11)+4x^6+2x^9+(7-5x^8+11x^9)+...

收起

字符串数据结构 java
C语言数据结构：一元多项式运算器
千次阅读 2019-09-22 12:47:50

一元多项式运算器的分析与实现首先，需要解决一元多项式在计算机中的存储问题。对于一元多项式： P = p0 + p1x + …+pnx^n 在计算机中，可以用一个线性表来表示： P = (p0,p1,…,pn), 但是对于形如 S(x) = 1 + 5x^...

收起

数据结构
一元多项式计算器（数据结构实验）
千次阅读 2021-05-16 20:05:32

灵活运用顺序表和单链表的相关算法实现一元多项式的计算。实验内容设有一元多项式Am(x)和Bn(X)，编程实现多项式Am(x)和Bn(x)的加法、减法和乘法运算。其中多项式描述为： Am(x)=A0+A1x1+A2x2+A3x3+….+Amxm； Bn...

收起
一元多项式计算器 (c语言数据结构实验）
千次阅读 2021-01-20 23:43:52

一元多项式计算器 (c语言数据结构实验）班级： **** 学号： 201907020633 姓名： *** 实验机号: A3 实验日期 :2020.12.04 报告日期 :2020.12.07 实验题目：一元多项式计算器

收起

数据结构
用顺序表实现一元多项式的存储及运算
千次阅读 2019-04-11 21:13:35

(( p 1 p_1 p1, e 1 e_1 e1), ( p 2 p_2 p2, e 2 e_2 e2), ……,( p n p_n pn, e n e_n en)) 3 链式存储 /* --------------------------一元多项式的相加运算-------------------------- */ /* * 1....

收起
数据结构课程设计—一元多项式加法、减法、乘法运算的实现
千次阅读 2021-05-20 08:34:00

一元多项式加法、减法、乘法运算的实现1.1设计内容及要求1)设计内容(1)使用顺序存储结构实现多项式加、减、乘运算。例如：,求和结果：(2)使用链式存储结构实现多项式加、减、乘运算，求和结果：2)设计要求(...

收起
C/C++：利用顺序表计算一元多项式的值
千次阅读 2020-04-07 19:59:31

笔者利用CFree编译器，实现了线性表的顺序存储，并利用顺序表实现了一元多项式的求值运算。代码如下： #include <stdio.h> #include <stdlib.h> #include <math.h> #define OK 1 #define LIST_...

收起

数据结构
数据结构课程设计—一元多项式加法、减法、乘法运算的实现教程文件.doc
2020-04-26 02:49:14

一元多项式加法减法乘法运算的实现 1.1设计内容及要求 1)设计内容 1使用顺序存储结构实现多项式加减乘运算例如 , 求和结果 2使用链式存储结构实现多项式加减乘运算求和结果 2设计要求 1用C语言编程实现上述实验...

收起
排序顺序表实现一元多项式加减乘运算
2021-09-23 18:52:35

排序顺序表实现一元多项式加减乘运算排序顺序表结点类 public class Term implements Comparable<Term> { private double coef; //系数 private int expn; //指数 public Term(double coef, int expn){...

收起

数据结构
C语言链表应用：一元多项式加法运算
千次阅读 2020-11-01 01:13:51

C语言链表应用：一元多项式加法运算首先科普一下线性表的相关知识。线性表，即由n个性质相同的数据元素组成的有序序列。线性表是最基础的线性结构，也是最基本的数据结构形式。因此学好线性表，也是学习其余数据...

收起

数据结构
【数据结构1】一元多项式相加（线性表链式存储）
2022-01-17 17:47:24

题目描述：通过键盘输入两组多项式的系数和指数，当系数为零时表示输入结束，规定输入的指数是按从小到大顺序的，计算两个一元多项式相加的和多项式并用相同的方式输出 1.建立两个单链表，存储两个一元多项式...

收起

数据结构
数据结构课程教学设计一元多项式加法,减法,乘法运算的实现.doc
2020-02-20 22:00:14

一元多项式加法减法乘法运算的实现 1.1设计内容及要求 1)设计内容 1使用顺序存储结构实现多项式加减乘运算例如 , 求和结果 2使用链式存储结构实现多项式加减乘运算求和结果 2设计要求 1用C语言编程实现上述实验...

收起
数据结构实验一：一元多项式的乘法与加法运算
2021-03-05 22:02:54

输入两行，每行一个多项式，格式 n, c1, e1, c2, e2 … n为非零项的项数，c为系数，e为幂数。输出一行，格式同输入。输入可以是乱序的，但需要按降幂存储。输出是按降幂输出的。 C语言链表实现我是用单链表实现...

收起

数据结构
一元多项式的乘法与加法运算的算法分析(java描述)
2021-08-04 00:08:32

捷径到达所需位置准备工作（创建相关结构）将数据输入实现乘法操作乘法结果队列的调整输出结果实现加法操作（同时输出）总代码到此结束，感谢大家观看输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以...

收起

java 数据结构
数据结构实验-稀疏一元多项式计算
2021-10-11 20:43:35

(实验)自行为稀疏一元多项式设计存储结构，并实现如下功能： ① 输入：从键盘输入多项式的各项系数和指数，创建一元多项式； ② 输出：按给定格式输出一元多项式；（例如：3*x20-x7+10） ③ 多项式加法：任意输入另...

收起

数据结构

数据结构 C++实现一元多项式运算（顺序存储结构实现）

文章目录

实验目的

实验内容

代码内容

运行结果

总结

一元多项式运算（顺序存储结构实现）（C语言）

一．目的要求

二．设计内容

三、设计思路

三．测试数据

四．源程序清单

五、运行结果

一元多项式运算数据结构课设.zip

一元多项式的运算（加减乘）终极版

一元稀疏多项式运算代码

C/C++:一元多项式的表示及其运算.rar(含注释)

C语言数据结构实现——一元多项式的基本运算

问题描述：

第一种算法：顺序存储结构实现——顺序表

顺序存储结构—— 算法改进思路

第二种算法：链式存储结构实现——单链表

数据结构 一元多项式运算

案例2.1-一元多项式的运算（顺序表实现）

数据结构—— 一元多项式的加法运算

如何利用线性表？完成一元多项式运算【内容丰富，简单易懂】

数据结构—— 一元多项式的运算（相加，相减，相乘）【C语言实现】

利用线性表实现一个一元多项式

数据结构：一元多项式及其基本运算

一元多项式计算器（程序对于多项式运算非常通用、细节很多详见描述与代码）

C语言数据结构：一元多项式运算器

一元多项式计算器（数据结构实验）

一元多项式计算器 (c语言数据结构实验）

用顺序表实现一元多项式的存储及运算

数据结构课程设计—一元多项式加法、减法、乘法运算的实现

C/C++：利用顺序表计算一元多项式的值

数据结构课程设计—一元多项式加法、减法、乘法运算的实现教程文件.doc

排序顺序表实现一元多项式加减乘运算

C语言链表应用：一元多项式加法运算

【数据结构1】一元多项式相加（线性表链式存储）

数据结构课程教学设计一元多项式加法,减法,乘法运算的实现.doc

数据结构实验一：一元多项式的乘法与加法运算

一元多项式的乘法与加法运算的算法分析(java描述)

数据结构实验-稀疏一元多项式计算

一元多项式运算的顺序结构

数据结构一元多项式运算