多项式乘法数据结构 数据结构实验——用链表实现简单的多项式乘法

2021-03-26 16:45:33

数据结构实验——用链表实现简单的多项式乘法

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

- 数据结构实验——用链表实现简单的多项式乘法
前言
一、实验要求
二、实验内容和实验步骤：
总结

前言

本人计算机小菜鸟，写的程序比较垃圾，仅供参考，也是作为自己成长的一份记录，欢迎大家批评指正！

提示：以下是本篇文章正文内容，下面案例可供参考

一、实验要求

实验目的：

设计一个一元稀疏多项式简单计算器。
一元稀疏多项式简单计算器的基本功能是：
（1)输入并建立多项式。；
（2）输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（3）多项式a与多项式b相乘，建立多项式。

二、实验内容和实验步骤：

1.需求分析

代码如下（示例）：

（1）输入的形式为第一行输入多项式的项数，第二行输入多项式的内容，内容格式为系数+“ ”+指数的形式，有多少项数就输入多少系数和指数；输入值的范围为整数和浮点数。整数作为指数，浮点数作为系数。
（2）输出的形式为一行表示多项式的数值，例：
请输入多项式的项数:3
请输入数据:1 2 3 4 5 6
排序之后为:5 * x^6 + 3 * x^4 + 1 * x^2
（3）程序所能实现的功能为简单的多项式合并和多项式按照指数进行降序排序，并能实现多项式的乘法。

2.概要设计

代码如下（示例）：

（1）考虑到在合并同类项和多项式乘法时需要进行数据的筛检和删除，所以在进行数据结构定义是运用链表进行设计和应用。

struct point{
    float c;   //c 系数
    int e;      //e 指数
    struct point *next;
};

（2）主程序以及各程序模块之间的关系：主程序负责建立链表和调用各模块程序。在主函数中首先建立多项式，然后分别调用输入函数、排序函数和合并函数将该多项式输入、排序、合并之后进行输出。然后进行多项式的乘法，首先建立两个多项式，然后直接进行多项式的乘法。然后调用排序、合并和输出函数将相乘之后的函数进行输出。

3.代码设计

（1）首先给出我的代码(c++)

#include <iostream>
#include <cstdlib>
using namespace std;

struct point{
    float c;   //c 系数
    int e;      //e 指数
    struct point *next;
};

void change(struct point *p,struct point *q){
    float ct;
    int et;
    ct = p->c;
    p->c = q->c;
    q->c = ct;
    et = p->e;
    p->e = q->e;
    q->e = et;
}
//输入函数
void input(struct point *p,struct point *head){
    p = head;
    int n;
    cout<<"请输入多项式的项数:";
    cin>>n;
    cout<<"请输入数据:";
    for (int i = 0; i < n; i++) {
        struct point *s = (struct point *)malloc(sizeof(struct point));
        cin>>s->c>>s->e;
        p->next = s;
        s->next = NULL;
        p = s;
    }
}
//排序函数
void sort(struct point *p,struct point *head){
    p = head;
    struct point *p1 = NULL,*p2 = NULL,*p3 = NULL;
    p1 = p->next;
    p2 = p->next;
    while (p1 != p3) {
        while ((p1->next) != p3) {
            if ((p1->e) < (p1->next->e)) {
                change(p1, p1->next);
            }
            p1 = p1->next;
        }
        p3 = p1;
        p1 = p->next;
    }
}
//合并同类项函数
void merge1(struct point *p,struct point *head){
    p = head;
    for (struct point *q = p->next; q != NULL&&q->next != NULL;){
            if ((q->e) == (q->next->e)) {
                q->c += q->next->c;
                q->next = q->next->next;
            }else q = q->next;
    }
}
//输出函数
void output(struct point *p,struct point *head){
    cout<<"排序之后为:";
    p = head;
    for (struct point *i = p->next; i != NULL;) {
        if(i->c != 0){
            cout<<i->c<<" * "<<"x^"<<i->e<<" ";
            if (i->next != NULL) {
                cout<<"+ ";
            }
        }
        i = i->next;
    }
    cout<<endl;
}

int main() {
    struct point * head = (struct point *)malloc(sizeof(struct point));
    head->next = NULL;
    struct point * p = nullptr;
    input(p, head);
    sort(p, head);
    merge1(p, head);
    output(p, head);
    
    //多项式乘法
    cout<<"-----下面进行多项式的乘法-----"<<endl<<"请输入第一个多项式:"<<endl;
    struct point * head1 = (struct point *)malloc(sizeof(struct point));
    struct point * newp1 = nullptr;
    input(newp1, head1);
    sort(newp1, head1);
    merge1(newp1, head1);
    output(newp1, head1);
    cout<<"请输入第二个多项式:"<<endl;
    struct point * head2 = (struct point *)malloc(sizeof(struct point));
    struct point * newp2 = nullptr;
    input(newp2, head2);
    sort(newp2, head2);
    merge1(newp2, head2);
    output(newp2, head2);
    
    newp1 = head1;
    newp2 = head2;
    struct point * Mhead = (struct point *)malloc(sizeof(struct point));
    struct point * Mp = nullptr;
    Mp = Mhead;
    while (newp1->next != NULL) {
        while (newp2->next != NULL) {
            struct point *p = (struct point *)malloc(sizeof(struct point));
            p->c = newp1->next->c * newp2->next->c;
            p->e = newp1->next->e + newp2->next->e;
            Mp->next = p;
            p->next = NULL;
            Mp = p;
            newp2 = newp2->next;
        }
        newp1 = newp1->next;
        newp2 = head2;
    }
    
    
    sort(Mp, Mhead);
    merge1(Mp, Mhead);
    cout<<"相乘之后得到";
    output(Mp, Mhead);
    return 0;
}

（2）分析主要函数

//输入函数
void input(struct point *p,struct point *head){
    p = head;
    int n;
    cout<<"请输入多项式的项数:";
    cin>>n;
    cout<<"请输入数据:";
    for (int i = 0; i < n; i++) {
        struct point *s = (struct point *)malloc(sizeof(struct point));
        cin>>s->c>>s->e;
        p->next = s;
        s->next = NULL;
        p = s;
    }
}

   输入函数用的是最基本的输入方法，用另外的指针p指向定义的链表head，然后利用for循环进行链表节点内容的输入，每次输入c和e之后指针后移指向下一个结点。在这里利用malloc函数开辟一个新的结点s，将内容c和e输入到这个结点s中，然后将s结点链接在p的后面，然后将p后移一个结点。

//排序函数
void sort(struct point *p,struct point *head){
    p = head;
    struct point *p1 = NULL,*p2 = NULL;
    p1 = p->next;
    while (p1 != p2) {
        while ((p1->next) != p2) {
            if ((p1->e) < (p1->next->e)) {
                change(p1, p1->next);
            }
            p1 = p1->next;
        }
        p2 = p1;
        p1 = p->next;
    }
}

   因为要进行多项式按照指数的降幂排列，排序函数就实现这个功能，将链表输入，要实现函数的降幂排序。排序时，创建两个链表指针，一个指向现在的，一个指向下一个结点，当两个结点也就是e不是按照降幂排序的时，则将两个结点的内容进行交换。

//合并同类项函数
void merge1(struct point *p,struct point *head){
 p = head;
 for (struct point *q = p->next; q != NULL&&q->next != NULL;){
         if ((q->e) == (q->next->e)) {
             q->c += q->next->c;
             q->next = q->next->next;
             free(q->next);
         }else q = q->next;
 }
}

  合并同类项函数是建立在已经排好序的情况下的，定义一个指针之后进行同类项的合并，用这一个指针进行遍历，如果这个指针指向的内容中的e和下一个结点中的e一样，则将两个结点中的c加到第一个结点上，然后用q->next = q->next->next跳过下个结点，然后将q->next 结点free掉即可，每次遍历往后移一位。

//输出函数
void output(struct point *p,struct point *head){
    cout<<"排序之后为:";
    p = head;
    for (struct point *i = p->next; i != NULL;) {
        if(i->c != 0){
            cout<<i->c<<" * "<<"x^"<<i->e<<" ";
            if (i->next != NULL) {
                cout<<"+ ";
            }
        }
        i = i->next;
    }
    cout<<endl;
}

  输出函数就非常简单啦，只需要考虑到在合并式有c = 0的情况，此类结点不需要输出，所以在输出时加一个if判断条件如果c = 0的话将该结点跳过即可。

//多项式乘法
struct point * Mhead = (struct point *)malloc(sizeof(struct point));
    struct point * Mp = nullptr;
    Mp = Mhead;
    while (newp1->next != NULL) {
        while (newp2->next != NULL) {
            struct point *p = (struct point *)malloc(sizeof(struct point));
            p->c = newp1->next->c * newp2->next->c;
            p->e = newp1->next->e + newp2->next->e;
            Mp->next = p;
            p->next = NULL;
            Mp = p;
            newp2 = newp2->next;
        }
        newp1 = newp1->next;
        newp2 = head2;
    }

  然后进行多项式的乘法，这也是这个地方复杂的地方，多项式的乘法所要做的就是将第一个链表中的每一项都与第二个链表进行相乘（即系数相乘，指数相加），然后将乘完之后的数据存在新的链表Mhead中，此时需要两个循环，第一重循环需要遍历第一个链表所有的数，然后第二个循环需要遍历第二个链表中所有的数，最后将答案输出即可。

总结

以上就是今天要讲的内容，本文仅仅简单介绍了怎么用单链表实现多项式的乘法，本人比较菜，欢迎大家批评指正！

c++ 链表

更多相关内容

一元多项式乘法 数据结构课设
2012-01-04 13:48:03

数据结构课设一元多项式乘法 C++源码需要的拿去

收起
数据结构课设（一元多项式乘法）
2018-04-17 13:26:45

(2)设计算法实现一元多项式乘法； (3)分析算法的时间复杂度和空间复杂度一、总体设计 1 二、详细设计 1 2.1存储结构 1 2.2建立链表 1 2.3遍历操作 1 2.4多项式相乘算法 2 三、调试与测试 2 3.1方案一 2 3.2...

收起

【数据结构】——多项式乘法

千次阅读 2019-08-01 19:34:51

从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。算法原理两个多项式的乘法，可以借助两个...

题目要求

从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。

算法原理

两个多项式的乘法，可以借助两个多项式的加法的算法来实现。

设：

$P(x) = a_{0}x^{b_{0}} + a_{1}x^{b_{1}} + \cdot \cdot \cdot + a_{m-1}x^{b_{m-1}}$

$Q(x) = c_{0}x^{d_{0}} + c_{1}x^{d_{1}} + \cdot \cdot \cdot + c_{n-1}x^{d_{n-1}}$

则：

$R(x) = P(x) \cdot Q(x) = \sum_{i = 0}^{n-1}P(x)c_{i}x^{d_{i}}$

例如： $P(x) = 8x^{2}-x+5$ , $Q(x) = 4x^{2}-9$ ,

则：

$R(x) = P(x)\cdot Q(x) = (8x^{2}-x+5)\cdot (4x^{2}) + (8x^{2}-x+5)\cdot (-9) = (32x^{4} - 4x^{3}+20x^{2}) + (-72x^{2}+9x-45) = 32x^{4} - 4x^{3} -52x^{2}+9x-45$

数据结构设计

采用带附加头结点单向链表；每个结点包括双精度类型的系数域、整型类型的指数域和一个指针域。

typedef struct polynode
{
	double c;			//系数
	int e;				//指数
	struct polynode *next;		//指针域，要求结点按指数e升序连接
}PNode,*Polyn;                          //PNode为结点类型，Polyn为结点指针类型

程序代码

#include <iostream>
#include <fstream>
using namespace std;
//定义结点及结点指针数据类型
typedef struct polynode
{
	double c;			        //系数
	int e;				        //指数
	struct polynode *next;		        //要求结点按指数e升序连接
}PNode,*Polyn;                                  //PNode为结点类型，Polyn为结点指针类型
Polyn h1, h2;					//两个多项式P(x),Q(x)的头结点
double a[20];					//数组a保存系数
int b[20];				        //数组b保存指数
void Read(char *s)		 		//读取数据，s代入不同的文件名
{
	double c;
	int i = 0, e;
	ifstream infile(s);
	if (!infile)				//打开文件失败输出提示信息
	{
		cout << "file open error!" << endl;
		exit(0);
	}
	while (1)                               //打开成功，将系数和指数保存在两个数组中
	{
		infile >> c >> e;
		if (infile.eof())
			break;
		a[i] = c;
		b[i] = e;
		i++;
	}
	infile.close();			
}
void Write(Polyn h)				//输出函数，将结果输出到文件中，h为链表头结点
{
	ofstream outfile("multiply.txt");       //输出文件名为multiply.txt
	Polyn p = h->next;                      //去掉附加头结点
	if (!outfile)				//打开文件失败输出提示信息
	{
		cout << "file open error!" << endl;
		exit(0);
	}
	if (!p)			                //第一个结点为空，表示运算结果为0
		outfile << "0" << endl;
	while (p)			        //p不为空，依次输出系数和指数
	{
		outfile << p->c << "     " << p->e << endl;
		p = p->next;
	}
	outfile.close();
}
Polyn Create(char *s)			        //先入先出建立链表，s代入不同的文件名
{
	int i = 0;                             //i用于记录数组下标
	Polyn h, last, p;
	h = new PNode;
	h->next = NULL;                        //h为附加头结点
	last = h;
	Read(s);                               //从文件中读取系数和指数
	while (a[i]!=0)
	{
		p = new PNode;
		p->c = a[i];
		p->e = b[i];
		p->next = NULL;		      //建新结点
		last->next = p;
		last = p;                     //新结点插入到链表尾
		i++;
	}
	return h;
}

void PrintPoly(Polyn h)                        //按多项式的形式将结果打印到控制台界面中
{
	Polyn p = h->next;
	if (!p)                               //所得结果为空，则输出0
		cout << "0" << endl;
	while (p)
	{
		if (p->next)                     //p不是尾结点
		{
			if (p->next->c < 0)         //p的后继结点的系数小于0，不输出符号 + 
			{
				if (p->c == -1)     //p的后继结点的系数等于-1
				{
					cout << "-x^" << p->e;
					p = p->next;
				}
				else if (p->c == 1) //p的后继结点的系数等于1
				{
					cout << "x^" << p->e;
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e;
					p = p->next;
				}
			}
			else if (p->next->c > 0)       //p的后继结点的系数大于0，需输出符号+
			{
				if (p->c == 1)         //p的后继结点的系数等于1
				{
					cout << "x^" << p->e << "+";
					p = p->next;
				}
				else if (p->c == -1)   //p的后继结点的系数等于-1
				{
					cout << "-x^" << p->e << "+";
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e << "+";
					p = p->next;
				}
			}
		}
		else                               //p是尾结点，需在结尾输出换行
		{
			if (p->c < 0)              //p的指数小于0
			{
				if (p->c == -1)
				{
					cout << "-x^" << p->e << endl;
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e << endl;
					p = p->next;
				}
			}
			else if (p->c > 0)         //p的指数大于0
			{
				if (p->c == 1)
				{
					cout << "x^" << p->e << endl;
					p = p->next;
				}
				else
				{
					cout << p->c << "x^" << p->e << endl;
					p = p->next;
				}	
			}	
		}
	}
}
void CreateNode(Polyn &p)			//创建新结点
{
	p = new PNode;
}
void DeleteNode(Polyn &p)			//删除结点
{
	delete p;
}
Polyn add(Polyn h1, Polyn h2)                   //实现两个多项式的相加，返回和式头指针
{
	Polyn p1, p2, p3, h, p;			//h为和式R(x)的附加头结点指针
	p1 = h1->next;
	p2 = h2->next;
	CreateNode(h);
	p3 = h;
	while (p1&&p2)
	{
		if (p1->e < p2->e)              //p1的指数大于p2,先保存p1结点
		{
			p = p1;
			p1 = p1->next;
		}
		else if (p2->e < p1->e)         //p2的指数大于p1,先保存p2结点
		{
			p = p2;
			p2 = p2->next;
		}
		else                             //p1与p2指数相等时
		{
			p1->c += p2->c;         //系数相加，结果保存在p1中
			if (p1->c == 0)         //系数之和为0,则删除该结点
			{
				p = p1;
				p1 = p1->next;
				DeleteNode(p);        //删除结点
				p = p2;
				p2 = p2->next;
				DeleteNode(p);
				continue;
			}
			p = p2;                 //系数之和不为0时，先删除p2结点
			p2 = p2->next;
			DeleteNode(p);
			p = p1;                 //将p1连接到p中
			p1 = p1->next;
		}
		p3->next = p;                 //插入p结点至和式末尾
		p3 = p;
	}
	if (p1)                              //p1没有结束，将p1后面所有的结点连接到和式
		p3->next = p1;
	else if (p2)                         //p2没有结束，将p2后面所有的结点连接到和式
		p3->next = p2;
	else
		p3->next = NULL;
	h1->next = h2->next = NULL;         //清空h1和h2链表
	return h;
}
Polyn mul(Polyn hp, Polyn hq)		    //实现两个多项式的相乘
{
	Polyn hr, ht, q, p, pt;
	CreateNode(hr);
	hr->next = NULL;                     //R(x) = 0
	CreateNode(ht);
	ht->next = NULL;                     //T(x) = 0
	q = hq->next;
	while (q)
	{
		pt = ht;
		p = hp->next;
		while (p)
		{
			CreateNode(pt->next);	//创建新的尾结点
			pt = pt->next;
			pt->c = p->c*q->c;      //系数相乘
			pt->e = p->e + q->e;    //指数相加
			p = p->next;
		}
		pt->next = NULL;
		q = q->next;
		p = add(hr, ht);                 //实现R(x) = R(x) + T(x)
		DeleteNode(hr);
		hr = p;
	}
	DeleteNode(ht);
	return hr;
}
int main()
{
	Polyn h1, h2, h3;                     //定义单向链表附加头结点指针
	cout << "读取文件，直到读入0时停止，建立单向链表" << endl;
	h1 = Create("polynode1.txt");
	h2 = Create("polynode2.txt");
	cout << "P(x) = ";
	PrintPoly(h1);
	cout << "Q(x) = ";
	PrintPoly(h2);
	h3 = mul(h1, h2);
	cout << "R(x) = P(x) * Q(x) = ";
	PrintPoly(h3);
	Write(h3);                             //写入文件
	return 0;
}

示例

(1) P(x) 1 2 2 3 0

Q(x) 1 -2 2 -3 0

输出结果为：

（2）P(x) 1 1 2 2 3 3 0

Q(x) -1 1 -2 2 -3 3 0

输出结果为：

收起

展开全文

C++ 算法

数据结构1——稀疏多项式乘法计算器

千次阅读 2017-03-08 11:45:38

数据结构1——稀疏多项式乘法计算器一元稀疏多项式简单计算器（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列： n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，...

一元稀疏多项式简单计算器

（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列： n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（3）多项式a与多项式b相乘，建立多项式。
在写代码的过程中，对其中没有掌握的各个知识点的梳理和记录。

1、struct结构体

typedef struct Polynomial{
            float coef; //系数
            int expn; //指数
            struct Polynomial *next;
            //Polynomial(double a, int b){coef = a; expn = b;}
            Polynomial(){};
        }Polyn,*Poly;

struct P{
......
}PO,*PO2
PO *p 与 PO2 p 等价，都是指向P的指针。

typedef 和 struct
　在c++中如果用typedef的话，会造成区别：

struct   Student   
　　　　{   
　　　　int   a;   
　　　　}stu1;//stu1是一个Student变量  

　　　　typedef   struct   Student2   
　　　　{   
　　　　int   a;   
　　　　}stu2;//stu2是一个结构体类型=struct Student

　　　　使用时可以直接访问stu1.a
　　　　但是stu2则必须先 stu2 s2;
　　　　然后 s2.a=10;

在C++中，后者可以有
1. struct Student2 变量名
2. Student2 变量名
3. stu2 变量名

2、struct构造函数

结构体实例和类实例的初始化方法完全相同，二者都可以应用于继承层次中。不同点是结构体默认成员为public，而类默认成员是private。

若类和结构体所有数据成员均为public型，可采取如下带花括号形式进行初始化。
注意：
① 不论值的个数多少，都必须使用花括号定界
② 未指定值的数据成员编译器会自动初始化为默认值
③ 这种初始化对象方式，要求所有数据成员必须为public型
④ 这种初始化对象方式，要求类中不能编写任何构造函数

添加了构造函数的struct相当于成员全部public的类，而类的实例化必须通过构造函数，所以不能再使用｛｝初始化。

3、函数返回指针变量

C++允许函数返回局部指针，前提是指针指向的地址在函数退出后仍然有效。这涉及到C++内存分配问题。如果指针指向的内容是局部数组等存在与栈内存中的，则函数执行完后内容被销毁。

4、C++内存分配

C++编译器将计算机内存分为代码区和数据区。
数据区分配方式如下图所示：

这里写图片描述

不涉及动态分配的对象有严格定义的生存期。全局对象在程序启动时分配，程序结束时销毁。局部对象，在我们进入其定义所在的程序块时被创建，在程序结束时销毁。局部static对象在第一次使用前分配，在程序结束时销毁。

动态分配的对象的生存期与它们在哪里创建无关，只有显式地被释放时，才会销毁。

void f() {
int* p=newint[5];
}
delete []p;

5、指针问题

1）用malloc申请多个同名指针，或new多个同名指针，指针指向最后一次开辟的空间。
2）复制指针时复制指针本身所含的地址值，而不会复制指针指向的内容。

3）void *malloc(long NumBytes)：该函数分配了NumBytes个字节，并返回了指向这块内存的指针。如果分配失败，则返回一个空指针（NULL）。
关于分配失败的原因，应该有多种，比如说空间不足就是一种。
void free(void *FirstByte)：该函数是将之前用malloc分配的空间还给程序或者是操作系统，也就是释放了这块内存，让它重新得到自由。

4）free 和 delete 释放的都是指针指向的内存。指针是一个变量，只有程序结束时才被销毁。

贴一下代码

#include <iostream>
#include <string>
#include<sstream>
#include <vector>
using namespace std;


typedef struct Polynomial{
    double coef; //系数
    int expn; //指数                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
    struct Polynomial *next;
    Polynomial(double a, int b){coef = a; expn = b; next = NULL;}
    Polynomial(){};
}Polyn,*Poly;



Polyn* CreatePolyn(Polyn *head,int n){
    Poly h2 = NULL;
    int i = 1;
    for(; i<(n+1); i++){
        cout<<"输入第"<<i<<"项的系数和指数"<<endl;
        double co; int ex;
        Poly po = new Polynomial();
        cin>>co>>ex; 
        po->coef = co; po->expn = ex; po->next = NULL;
        if (head == NULL){head = po; h2 = head;} // head有值
        else{
                head->next = po;
                head = head->next;
            }
        }
    return h2;
}

void PrintPolyn(Polyn *head){
    /*vector<string> polystr; string tp;
    while(head->next != NULL){  
        polystr.push_back(tp);
        istringstream temp(head->coef);
        temp>>tp;
        polystr.push_back(tp);
        head = head->next;
    }*/

    for(; head != NULL; head= head->next){
        if(head->coef == 0)  continue;
        int coe = head->coef * 100; double coe1 = coe/100;
        head->coef = coe1;
        if( coe1 >1 ) cout<<coe1;
        if( head->expn>1 ) cout<<"x^"<<head->expn;
        else if ( head->expn = 1 ) cout<<"x";
        if( head->next && ! ( head->next->coef < 0 ) ) cout<<"+";
        else if ( head->next && head->next->coef < 0) cout<<"-";
    }

};

Polyn* MultiPolyn(Poly head1,Poly head2){
    Poly ml = NULL ;  Poly re = NULL;
    while( head1!= NULL ){
        double coe1 = head1->coef;
        int exp1 = head1->expn;
        for( Poly h2 = head2; h2 != NULL; h2 = h2->next){
            Poly po = new Polyn();
            po->coef = coe1 * h2->coef;
            po->expn = exp1 + h2->expn;
            po->next = NULL;
            if ( ml == NULL ) { 
                ml = po;
                re = ml;
            }else{
                ml->next = po;
                ml = ml->next;
            }
        }
        head1 = head1->next;
    }
    for( Poly p = re; p != NULL; p=p->next){
        double out = p->coef; int out1 = p->expn;
        for( Poly p2 = p->next; p2 !=NULL; p2=p2->next){
            if (p2->expn == out1) {
                p->coef += p2->coef;
                p2->coef = 0;  p2->expn=0;
            }
        }
        cout<<p->coef<<p->expn<<endl;
    }
    return re;
}

int main(){

    cout<<"####################################"<<endl;
    cout<<endl;
    cout<<"      一元稀疏多项式乘法计算器      "<<endl;
    cout<<endl;
    cout<<"####################################"<<endl;

    int n1, n2, tr=0, ta = 0, tb =0;
    Poly head1=NULL, head2 = NULL, head3 = NULL;

    while(tr != 1){
        cout<<"请输入多项式a和b的项数"<<endl;
        cin>>n1>>n2;
        cout<<"确认输入1；输入其他数字重新输入"<<endl;
        cin>>tr;
    } 

    while(ta != 1){
        cout<<"依次输入多项式a每项的系数和指数，回车结束"<<endl;
        head1 = CreatePolyn(head1,n1);
        cout<<"多项式a为：";
        PrintPolyn(head1);
        cout<<"确认输入1；输入其他数字重新输入"<<endl;
        cin>>ta;
    }   
    while(tb != 1){
        cout<<"依次输入多项式b每项的系数和指数，回车结束"<<endl;
        head2 = CreatePolyn(head2,n2);
        cout<<"多项式b为：";
        PrintPolyn(head2);
        cout<<"确认输入1；输入其他数字重新输入"<<endl;
        cin>>tb;
    }

    cout<<"多项式相乘："<<endl;

    PrintPolyn( MultiPolyn( head1,head2 ) );

    system("pause");

}

收起

展开全文

c语言

多项式乘法实现
2017-12-22 16:48:14

数据结构作业，适合初学者，小白，自学者，和大家共享。

收起
数据结构多项式乘法.pdf
2021-09-30 21:16:39

数据结构多项式乘法.pdf

收起

数据结构——多项式相乘

2020-11-27 22:59:37

printf("请输入第一个多项式的项数："); scanf("%d",&L1); CreatePolyn(P1,L1); printf("第一个多项式为："); printf("P1(X)="); PrintPolyn(P1); printf("请输入第二个多项式的项数："); scanf("%d",&L2); ...

#include<stdio.h>
#include<stdlib.h>
#include<math.h> 
#define LEN sizeof(Poly)
typedef struct term{
    float coef;        
    int expn;        
    struct term *next;
}Poly,*Link;
int LocateElem(Link p, Link s, Link &q); 
void CreatePolyn(Link &p,int m);    
void PrintPolyn(Link p);                        
int cmp(Link a, Link b);
Link Reverse(Link p);                
Link MultiplyPolyn(Link A,Link B);    
void Calculate(Link p,float x); 
       
int LocateElem(Link p, Link s, Link &q){
    Link p1 = p->next;
    Link p2 = p;
    while(p1){
        if(s->expn > p1->expn){
            p1 = p1->next;
            p2 = p2->next;
        }else if(s->expn == p1->expn){
            q = p1; 
            return 1;
        }
		else{
            q = p2;
            return 0;
        }
    }
    if(!p1){
        q = p2;
        return 0;
    }
}

void CreatePolyn(Link &p,int m) 
{
    Link s,q;
    int i;
    p=(Link)malloc(LEN);
    p->next=NULL;
    for(i=0;i<m;i++)
    {
        s=(Link)malloc(LEN);
        printf("输入系数和指数（以空格隔开）:");
        scanf("%f %d", &s->coef, &s->expn);
        if(!LocateElem(p, s, q)){    
            s->next = q->next;
            q->next = s;
        }else{                                               
            q->coef+=s->coef;
        }
    }
}

void PrintPolyn(Link p)
{
    Link s;
    s = p->next;
    while(s)
    {
            printf(" %.2f X^%d", s->coef, s->expn);
            s = s->next;
            if(s!=NULL)  
                if(s->coef>=0) printf(" +");               
    }
    printf("\n");
}
Link Reverse(Link p)
{
    Link head=p; 
    Link q1,q2;
    q2=head->next;
    head->next=NULL;
    while(q2)
    {
        q1=q2;      
        q2=q2->next; 
        q1->next=head->next; 
        head->next=q1;  
    }      
    return head;
}
Link MultiplyPolyn(Link A,Link B)
{
  Link pa,pb,pc,s,head;
  int k,maxExpn,minExpn;
  float coef;
  head=(Link)malloc(LEN);
  head->next=NULL;
  if(A->next!=NULL&&B->next!=NULL){
      minExpn=A->next->expn+B->next->expn;  
     A=Reverse(A); 
    B=Reverse(B);
      maxExpn=A->next->expn+B->next->expn; 
  }
  else{
          return head;
  }       
   pc=head;
   B=Reverse(B);
for(k = maxExpn;k>=minExpn;k--){              
           pa = A->next;
           while(pa !=NULL&&pa->expn>k){ 
               pa = pa->next;
           }
           pb = B->next;
           while(pb!=NULL&&pa!=NULL&&pa->expn+pb->expn<k){
               pb = pb->next;
           }
        coef=0.0;
        while(pa!=NULL&&pb!=NULL){
            if(pa->expn+pb->expn==k){  
                coef+=pa->coef*pb->coef;
                pa=pa->next;
                pb=pb->next;
            }
            else if(pa->expn+pb->expn>k){
                pa = pa->next;
            }
            else{
                    pb = pb->next;
            }    
        }
        if(coef!=0.0){
            s=(Link)malloc(LEN);
            s->coef=coef;
            s->expn=k;
            s->next=pc->next;
            pc->next=s;
            pc=s;
        }
   }
   B = Reverse(B);
   head=Reverse(head);
   return head;    
}

int main()
{
    Link P1,P2,P3;    
    int L1,L2;       
    printf("请输入第一个多项式的项数：");
    scanf("%d",&L1);
    CreatePolyn(P1,L1);
    printf("第一个多项式为：");
    printf("P1(X)=");
    PrintPolyn(P1);
    printf("请输入第二个多项式的项数：");
    scanf("%d",&L2);
    CreatePolyn(P2,L2);
    printf("第二个多项式为：");
    printf("P2(X)=");
    PrintPolyn(P2); 
    printf("\n");
  printf("两个一元多项式相乘：   ");
             printf("P1(X)*P2(X)=");
             P3=MultiplyPolyn(P1, P2);
            PrintPolyn(P3);
    return 0;
}

在这里插入图片描述

收起

展开全文

c语言指针

数据结构实验报告-线性表-基于链表的多项式乘法-实验内容及要求.docx
2021-05-03 07:15:05

从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。要求输入输出字符文件中的数据格式自拟；编程...

收起
n元多项式相乘 数据结构课程设计
2009-07-08 14:00:38

功能：完成两个n元多项式作乘法，给出明确的等式形式。分步实施：1)．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2)．完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。 3)...

收起
数据结构问题——一元多项式相乘
千次阅读 2018-10-08 23:33:38

void multiplication(NODE *head1, NODE *head2, NODE *head3) { NODE *p1 = head3, *p2 = head3; NODE *h1 = head1-&... while (h1)//多项式乘法运算转化为加法运算，注意双重循环控制乘...

收起
多项式乘法
2021-04-12 19:02:48

实验题目：多项式乘法问题实验内容与要求一元稀疏多项式简单计算器的基本功能是：（1)输入并建立多项式。；（2）输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i...

收起

链表算法
【数据结构】C++单链表解决多项式乘法问题（直接输入多项式）
2021-10-04 17:38:40

承接上文，这次增加了多项式的乘法功能以及输出多项式的化简（系数为1省略，系数为-1保留负号，指数为1省略，指数为0只显示系数），多项式表达由mx^n变为mxn。 #include<iostream> using namespace std; //...

收起

c++ 链表
链表实现多项式乘法
2022-05-01 19:53:50

基于链式存储结构实现两个多项式的乘法问题，例如多项式A = 2x3 + 3x + 1，多项式B = 5x4 + 2x3 - 3x2 – 3，则A * B = 10x7 + 4x6 + 9x5 + 11x4 -13x3 – 3x2 – 9x – 3。 #include <iostream> #...

收起
数据结构课程设计报告_n元多项式乘法.doc
2021-10-07 07:45:57

数据结构课程设计报告_n元多项式乘法.doc

收起
多项式的加法与乘法（数据结构）.
2009-08-23 20:47:49

数据结构课程设计\多项式的加法与乘法（数据结构）.rar

收起
【数据结构——线性表】（C语言）一元多项式乘法
2019-07-22 18:08:39

一元多项式A 、B 按降次排列，用带头结点的链表存储，求 C=A ×B，试编程实现。代码实现 #include<stdio.h> #include<stdlib.h> typedef struct Lnode{ int coef; //定义系数 int exp; //定义...

收起

C语言线性表
【数据结构】多项式乘法与加法（c语言链表实现）
万次阅读 多人点赞 2019-07-29 17:04:49

数据结构设计 //将struct与typedef分开定义 typedef struct PolyNode *Polynomial; //使用 typedef 给一个还未完全声明的类型 PolyNode 起了一个新别名Polynomial struct PolyNode{ int coef; //系数 int expon;...

收起
数据结构多项式的加法与乘法，链表表示。
2020-03-13 15:52:21

多项式的加法与乘法，链表表示。。 `#include <stdio.h> #include <stdlib.h> //多项式表示 typedef struct PolyNode *Poly; struct PolyNode { int coef;//系数 int expon;//指数 Poly Link;//指针 }; ...

收起
数据结构 C++ 多项式的表达以及乘法实现
2021-11-17 14:39:20

数据结构 C++ 多项式的表达以及乘法实现

收起

c++
陈越、何钦铭-数据结构作业5：一元多项式的乘法与加法运算
2018-03-20 11:43:38

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

收起
一元多项式加法乘法运算c
2018-04-06 17:42:38

完美的数据结构大作业之选。C语言+链表实现。不用提前知道多项式项数，可以自动排序，可以合并同类项，可以进行加法、乘法运算。//#include<stdio.h> //#include<stdlib.h> #include&...

收起

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

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

收起

c++ c语言
数据结构与算法实验01-使用链表实现多项式乘法
2022-03-03 15:54:35

多项式乘法程序文章目录多项式乘法程序代码思路完整代码运行截图一个学期才4个实验，太少了吧，边打炉石边写程序花了三四天把四个实验水完了，代码放上供大家参考由于全程使用的C语言，加上写的很随意，代码...

收起

算法链表
矩阵多项式乘法算法的实现
2011-06-28 17:39:45

课程设计题目模板，适合很多要做课程设计的同学。，

收起
数据结构实验一：多项式乘法问题
千次阅读 2021-05-20 17:53:04

Exp01 多项式乘法问题 Author: Maskros 实验目的设计一个一元稀疏多项式简单计算器实验内容与要求一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式。（2）输出多项式，输出形式为整数序列：n,c1,...

收起

算法 c++ 链表
2.2 多项式乘法与加法运算（线性结构，C）
多人点赞 2022-03-18 23:36:59

设计函数分别求两个一元多项式的乘积与和已知两个多项式 （1）3x4-5x2+6x-2 （2）5x20-7x4+3x 输入样例： 4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1 输出样例： 15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 ...

收起

c语言
【数据结构与算法分析】学习笔记课后答案第三章3.6 3.7多项式加法乘法不同时间复杂度
千次阅读 2021-12-11 18:48:14

第三章表、栈和队列 3.6 编写两个多项式相加的函数时间复杂度为O(M+N) 【数据结构与算法分析】学习笔记课后答案第三章3.6 3.7多项式加法乘法不同时间复杂度

收起

算法

数据结构实验——用链表实现简单的多项式乘法

文章目录

前言

一、实验要求

二、实验内容和实验步骤：

1.需求分析

2.概要设计

3.代码设计

总结

一元多项式乘法 数据结构课设

数据结构课设（一元多项式乘法）

【数据结构】——多项式乘法

题目要求

算法原理

数据结构设计

程序代码

示例

数据结构1——稀疏多项式乘法计算器

一元稀疏多项式简单计算器

1、struct结构体

2、struct构造函数

3、函数返回指针变量

4、C++内存分配

5、指针问题

多项式乘法实现

数据结构多项式乘法.pdf

数据结构——多项式相乘

数据结构实验报告-线性表-基于链表的多项式乘法-实验内容及要求.docx

n元多项式相乘 数据结构课程设计

数据结构问题——一元多项式相乘

多项式乘法

【数据结构】C++单链表解决多项式乘法问题（直接输入多项式）

链表实现多项式乘法

数据结构课程设计报告_n元多项式乘法.doc

多项式的加法与乘法（数据结构）.

【数据结构——线性表】（C语言）一元多项式乘法

【数据结构】多项式乘法与加法（c语言链表实现）

数据结构多项式的加法与乘法，链表表示。

数据结构 C++ 多项式的表达以及乘法实现

陈越、何钦铭-数据结构作业5：一元多项式的乘法与加法运算

一元多项式加法乘法运算c

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

数据结构与算法实验01-使用链表实现多项式乘法

矩阵多项式乘法算法的实现

数据结构实验一：多项式乘法问题

2.2 多项式乘法与加法运算（线性结构，C）

【数据结构与算法分析】学习笔记课后答案第三章3.6 3.7多项式加法乘法不同时间复杂度

多项式乘法数据结构

一元多项式乘法数据结构课设

n元多项式相乘数据结构课程设计