• 使用链表实现多项式加法和乘法，数据结构常见问题的C语言实现
• // 读取系数指数加入到多项式链表 Polynomial P; P = (Polynomial)malloc(sizeof(struct PolyNode)); P->coef = c; P->expon = e; P->link =NULL; (*pRear)->link = P; *pRear = P; //更改 *pRear指针的...
#include<stdio.h>
#include<stdlib.h>
typedef struct PolyNode *Polynomial;
struct PolyNode{
int coef;
int expon;
};
void Attach(int c,int e,Polynomial *pRear)
{
// 读取系数和指数加入到多项式链表
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c;
P->expon = e;
*pRear = P;   //更改  *pRear指针的位置，让它指向最后

}

{
// 读取多项式数据
Polynomial P,Rear,t;
int c,e,N;
scanf("%d",&N);
// 开辟一块内存空间
P = (Polynomial)malloc(sizeof(struct PolyNode));
Rear = P;
while(N--)
{
scanf("%d %d",&c,&e);
Attach(c,e,&Rear);
}
t = P; P=P->link; free(t); //删除临时的头节点
return P;

}

{
Polynomial t1,t2,P,Rear,t;
int sum,expon;
t1 = P1; t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
Rear = P;  // Rear记录头节点
while(t1 && t2)
{
if(t1->expon == t2->expon)
{
sum = t1->coef + t2->coef;
expon = t1 ->expon;
if(sum)
{   //相加系数非0
Attach(sum,expon,&Rear);
}
else
{
//系数为0，跳过这个结点
}

}
else if (t1->expon > t2 ->expon)
{
sum = t1->coef;
expon = t1->expon;
Attach(sum,expon,&Rear);
}
else
{
sum = t2->coef;
expon = t2->expon;
Attach(sum,expon,&Rear);
}
}
while(t1)
{
sum = t1 ->coef;
expon = t1 -> expon;
Attach(sum,expon,&Rear);
}
while(t2)
{
sum = t2 -> coef;
expon = t2 -> expon;
Attach(sum,expon,&Rear);
}
return P;
}
void PrintPoly(Polynomial P)
{
//输出多项式
int flag =0; //调整输出格式
if(!P)
{
printf("0 0\n");
return;
}
while(P)
{
if(!flag)
flag=1;
else
printf(" ");
printf("%d %d",P->coef,P->expon);
}
printf("\n");
}

Polynomial Mult(Polynomial P1, Polynomial P2)
{
Polynomial t1,t2,t,P,Rear;
int c,e;
if(!P1||!P2)
return NULL;

t1=P1;t2=P2;
P=(Polynomial)malloc(sizeof(struct PolyNode));
Rear = P;
while(t2)  //先用P1的第一项乘P2
{
c = t1->coef * t2->coef;
e = t1->expon + t2->expon;
Attach(c,e,&Rear);
}
while(t1)
{          // 用P2第二项乘的时候需要遍历排序
t2 = P2; Rear = P; //每一次从表头遍历
while(t2)
{
c = t1->coef * t2->coef;
e = t1->expon + t2->expon;
{ //如果有系数等于e的结点
{
}
else
{
//删除这个节点
free(t);
}

}
else
{
//如果没有这个结点
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c;
t->expon = e;
}

}
}
return P;

}

int main()
{
Polynomial P1,P2,PP,PS;
PP = Mult(P1,P2);
PrintPoly(PP);
PrintPoly(PS);
}

展开全文
• 多项式关联 使用链表的多项式加法和乘法
• 双向链表实现多项式加法和乘法
• 02-线性结构2 一元多项式乘法加法运算 (20分) 设计函数分别求两个一元多项式的乘积与。 输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数指数...
• 该内容是用C语言写的多项式加法和乘法，主要运用栈
• 多项式的表示可以使用数组也可以使用链表 数组表示起来简单，调试方便。但需要事先确定数组的大小。...//多项式加法和乘法 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include...

多项式的表示可以使用数组也可以使用链表
数组表示起来简单，调试方便。但需要事先确定数组的大小。链表表示起来动态性强，但编程复杂，调试起来困难。
为了提高对链表的操作，后面介绍的程序，均使用链表来完成。
注意：下列链表没有头节点
//多项式的加法和乘法
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

struct PolyNode
{
int Coef;
int Expon;
struct PolyNode* Next;  //指向下一个节点
};

void Attach(int coef,int expon,struct PolyNode** PtrRear)
{
struct PolyNode* p;
p = (struct PolyNode*)malloc(sizeof(struct PolyNode));
p->Coef = coef;
p->Expon = expon;
p->Next = NULL;
(*PtrRear)->Next = p;
(*PtrRear) = p;  //修改PtrRear的值
}

{
int N;  //存储多项式的项数
int c;  //多项式的系数
int e;  //多项式的指数
struct PolyNode* p;  //表头
struct PolyNode* Rear;
struct PolyNode* t;
p = (struct PolyNode*)malloc(sizeof(struct PolyNode));
p->Next = NULL;
Rear = p;
scanf("%d",&N);
while (N--)
{
scanf("%d %d",&c,&e);
Attach(c,e,&Rear);
}
t = p;
p = p->Next;
free(t);  //删除临时生成的头节点
return p;
}
//作用：比较两个指数的大小
//返回值： e1 > e2 返回 1
//         e1 < e2 返回 -1
//         e1 = e2 返回 0
int Compare(int e1,int e2)
{
if (e1 > e2)
{
return 1;
}
else if (e1 < e2)
{
return -1;
}
else
{
return 0;
}
}

//将两个多项式相加
struct PolyNode* PolyAdd(struct PolyNode* P1, struct PolyNode* P2)
{
struct PolyNode* rear;
struct PolyNode* front;
struct PolyNode* temp;
int sum;

//为方便表头插入，先产生一个临时空节点作为结果多项式链表头
rear = (struct PolyNode*)malloc(sizeof(struct PolyNode));
front = rear;

while (P1 && P2)  //当两个多项式都有非零项待处理时
{
switch (Compare(P1->Expon, P2->Expon))
{
case 1:
Attach(P1->Coef,P1->Expon,&rear);
P1 = P1->Next;
break;
case -1:
Attach(P2->Coef, P2->Expon, &rear);
P2 = P2->Next;
break;
case 0:
sum = P1->Coef + P2->Coef;
if (sum)
{
Attach(sum,P1->Expon,&rear);
}
P1 = P1->Next;
P2 = P2->Next;
break;
}
}
//将未处理完的另一个多项式的所有节点依次复制到结果多项式中去
for (;P1;P1 = P1->Next)
{
Attach(P1->Coef,P1->Expon,&rear);
}
for (; P2; P2 = P2->Next)
{
Attach(P2->Coef, P2->Expon, &rear);
}
rear->Next = NULL;
temp = front;
front = front->Next; //令front指向结果多项式第一个非零项
free(temp);
return front;
}
//将两个多项式相乘
struct PolyNode* PolyMult(struct PolyNode* P1, struct PolyNode* P2)
{
struct PolyNode* rear;
struct PolyNode* P;
struct PolyNode* t1 = P1;
struct PolyNode* t2 = P2;
struct PolyNode* t;
int sumc;
int sume;

if (NULL == P1 || NULL == P2)
{
return NULL;
}
//产生一个临时空节点作为结果多项式链表头
P = (struct PolyNode*)malloc(sizeof(struct PolyNode));
rear = P;
while (t2)
{
//先用P1的第一项乘以P2得到P
Attach(t1->Coef * t2->Coef,t1->Expon + t2->Expon,&rear);
t2 = t2->Next;
}
t1 = t1->Next;

while (t1)
{
rear = P;
t2 = P2;
while (t2)
{
sumc = t1->Coef * t2->Coef;  //系数相乘
sume = t1->Expon + t2->Expon;  //指数相加
while (rear->Next && rear->Next->Expon > sume)
{
rear = rear->Next;
}
if (rear->Next && rear->Next->Expon == sume)
{
if (rear->Next->Coef + sumc)
{
//rear->Next->Coef + sumc != 0
rear->Next->Coef = rear->Next->Coef + sumc;
}
else
{
//rear->Next->Coef + sumc = 0
//删除一个节点
t = rear->Next;
rear->Next = t->Next;
free(t);
}
}
else //rear->Next->Expon < sume
{
//向链表中插入新的节点
t = (struct PolyNode*)malloc(sizeof(struct PolyNode));
t->Coef = sumc;
t->Expon = sume;
t->Next = NULL;
t->Next = rear->Next;
rear->Next = t;

rear = rear->Next;
}
t2 = t2->Next;
}
t1 = t1->Next;
}
t2 = P;
P = P->Next;
free(t2);
return P;
}
//将多项式输出
void PrintPoly(struct PolyNode* P)
{
int flag = 0;
if (NULL == P)
{
printf("0 0\n");
return 0;
}
while (P)
{
if (!flag)
{
flag = 1;
}
else
{
printf(" ");
}
printf("%d %d", P->Coef, P->Expon);
P = P->Next;
}
printf("\n");
}

int main()
{
struct PolyNode* P1;
struct PolyNode* P2;
struct PolyNode* PP;
struct PolyNode* PS;

printf("两多项式相加的结果为：\n");
PrintPoly(PP);
printf("两个多项式相乘的结果为:\n");
PS = PolyMult(P1,P2);
PrintPoly(PS);
system("pause");
return 0;
}

参考资料： 1 《数据结构》 陈越主编 2 慕课网 《数据结构》 陈越老师，何钦铭老师主讲

转载于:https://www.cnblogs.com/Manual-Linux/p/11307955.html
展开全文
• //多项式乘法 public Dolynomial multi(Dolynomial D1, Dolynomial D2) { Dolynomial temp = new Dolynomial(); Node node1 = D1.first; Node node2 = D2.first; int n1 = D1.size(); int n2 = D2....
package com.baidu.line;

import java.util.Scanner;

public class Dolynomial {
private Node first;
private Node last;
private int N;

private class Node{
int coef;		//存放系数
int expo;		//存放指数
Node next;
}

public boolean isEmpty() {
return N == 0;
}

public int size() {
return N;
}

public void enqueue(int coef, int expo) {
Node oldlast = last;
last = new Node();
last.coef = coef;
last.expo = expo;
last.next = null;
if(N == 0) {
first = last;
} else
oldlast.next = last;
N++;
}

/*public void insertion(Node n, int index) {
Node temp = first;
while(index-- > 0) {
temp = temp.next;
}
n.next = temp.next;
temp.next = n;
}*/

public static Dolynomial addition(Dolynomial D1, Dolynomial D2) {
Dolynomial temp = new Dolynomial();
Node node1 = D1.first;
Node node2 = D2.first;
int n1 = D1.size();
int n2 = D2.size();
while(n1 > 0 && n2 > 0) {
if(node1.expo > node2.expo) {
temp.enqueue(node1.coef, node1.expo);
node1 = node1.next;
n1--;
} else if(node1.expo < node2.expo) {
temp.enqueue(node2.coef, node2.expo);
node2 = node2.next;
n2--;
} else {
if(node1.coef + node2.coef != 0)
temp.enqueue(node1.coef + node2.coef, node1.expo);
node1 = node1.next;
node2 = node2.next;
n1--;
n2--;
}
}

while(n1-- > 0) {
temp.enqueue(node1.coef, node1.expo);
node1 = node1.next;
}

while(n2-- > 0) {
temp.enqueue(node2.coef, node2.expo);
node2 = node2.next;
}

return temp;
}

//读入一个多项式
Dolynomial temp = new Dolynomial();
Scanner sc = new Scanner(System.in);
System.out.println("请输入多项式项数：");
int N = sc.nextInt();
for (int i = 0; i < N; i++) {
System.out.println("请输入第" + (i + 1) + " 项,其中第一个为系数，第二个为指数");
int coef = sc.nextInt();
int expo = sc.nextInt();
temp.enqueue(coef, expo);
}
return temp;
}

//多项式的乘法
public Dolynomial multi(Dolynomial D1, Dolynomial D2) {
Dolynomial temp = new Dolynomial();
Node node1 = D1.first;
Node node2 = D2.first;

int n1 = D1.size();
int n2 = D2.size();

while(n2-- > 0) {
temp.enqueue(node1.coef * node2.coef, node1.expo + node2.expo);
node2 = node2.next;
}

while(--n1 > 0) {
//System.out.println("几条这样的语句就是几次循环~");

Node node3 = temp.first;
node1 = node1.next;
node2 = D2.first;
n2 = D2.size();

while(n2 > 0) {
//System.out.println("这个也一样哦！");
int c = node1.coef * node2.coef;
int e = node1.expo + node2.expo;
while(node3.next != null && node3.next.expo > e)
node3 = node3.next;
if(node3.next != null && node3.next.expo == e) {
//指数相等，直接相加
node3.next.coef += c;
if(node3.next.coef == 0) {
node3 = node3.next.next;
}
} else {
//插入节点
Node p = new Node();
p.coef = c;
p.expo = e;
p.next = node3.next;
node3.next = p;
temp.N++;
}

n2--;
node2 = node2.next;
}
}
return temp;
}

/**
* @param args
*/
public static void main(String[] args) {
Dolynomial d1, d2, result1, result2;
System.out.println(d1.size() + d2.size());
System.out.println("分割线-------------------");
Node temp1 = result1.first;
for (; temp1 != null; temp1 = temp1.next) {
System.out.println(temp1.coef + " " + temp1.expo);
}
System.out.println("分割线-------------------");
result2 = d1.multi(d1, d2);
Node temp2 = result2.first;
System.out.println(result2.size());
for (; temp2 != null; temp2 = temp2.next) {
System.out.println(temp2.coef + " " + temp2.expo);
}
}

}

总结：
在刚看到这题目时，觉得很简单，可真正做起来还是问题百出，差不多花了三四个小时，效率太低，经常犯一些简单、低级的错误，包括一些命令的不熟悉。俗话说的的好，三天不写手生，希望自己以后勤加练习。
展开全文
• 设有一个一元多项式 f(x)=∑aixi ，我们要用一个单链表将它表示出来，并实现它的加乘运算。多项式的每一项放在一个结点中，每个结点中放两个信息，即每一项的系数幂。在这里我们用有头结点的链表来表示，那么...

设有一个一元多项式  f(x)=∑aixi  ，我们要用一个单链表将它表示出来，并实现它的加和乘运算。多项式的每一项放在一个结点中，每个结点中放两个信息，即每一项的系数和幂。在这里我们用有头结点的链表来表示，那么对于某个多项式 p=2x2+100x3+45x5+3x20，它的单链表表示如下：

尽可能地简单，结点PolyNode类如下：
package poly;
public class PolyNode {
private int a;
private int i;
PolyNode next;
public PolyNode(int a,int i){
this.a=a;
this.i=i;
this.next=null;
}
public PolyNode(){
this(0,0);
}
public int getA() {
return a;
}
public int getI() {
return i;
}
public void setA(int a) {
this.a = a;
}
public void setI(int i) {
this.i = i;
}
}
加法运算的算法如下图：

多项式 result 用来保存结果。p1.current 和 p2.current 分别指向 p1 和 p2 的第一个元素，比较它们的幂，如果相等，将它们的系数相加，幂不变，这一新项插入到 result 中，p1.current 和 p2.current 都往后移一位；如果 p1.current 所指向的项的幂小于 p2.current ，则把 p1.current 所指向的这一项插入到 result 中，p1.current 后移一位；同样地，如果 p2.current 所指向的项的幂小于
p1.current ，执行类似的操作。重复这一过程，直到这两个指针都指向 null 。(在单链表中，最后一个结点的 next 指向null)这里还有一个细节，就是这两个指针中一般都会有一个先指向 null ，那么这时候很简单，把剩下的那个指针往后遍历，它及其后面所指向的项都插入 result 即可。
乘法运算的算法比加法还要简单，同样看上图吧。result 用来保存结果， p1.current先固定， p2.current 遍历，p1.current 的指向乘以 p2.current 所指的每一项，这一次结束后 p1.current 后移一位，重复上述过程，直到 p1.current 指向 null 。不过结果最后有一个合并同类项的问题，这也不难，无非就是每一项跟它后面的所有项比较，如果幂相同的话，就把它们加起来，这里不再赘述，看代码吧。
链表类 PolyList 如下：
package poly;
public class PolyList {
PolyNode current;
public PolyList(){
}
//是否为空
public boolean isEmpty(){
}
//这里只考虑按顺序插入元素
public void insert(PolyNode node){
current.next=node;
current=node;
}
//打印多项式
public String printS(){
StringBuilder s=new StringBuilder("");
StringBuilder a=new StringBuilder("");
StringBuilder i=new StringBuilder("");
StringBuilder theOne=new StringBuilder("");
while(current!=null){
a.delete(0, a.length());
i.delete(0, i.length());
theOne.delete(0, theOne.length());
if(current.getA()==1)
a.append("");
else
a.append(String.valueOf(current.getA()));
if(current.getI()==1)
{
i.append("");
theOne.append(a.toString()).append("x").append(i.toString());
} else{
i.append(String.valueOf(current.getI()));
theOne.append(a.toString()).append("x^").append(i.toString());
}
s.append(theOne.toString());
else
s.append("+").append(theOne.toString());
current=current.next;
}
return s.toString();
}
//加法运算
public static PolyList add(PolyList p1,PolyList p2){
PolyList result=new PolyList();
//分别指向p1 p2的第一个元素
while(p1.current!=null && p2.current!=null){
if(p1.current.getI()==p2.current.getI()){
result.insert(new PolyNode(p1.current.getA()+p2.current.getA(),p1.current.getI()));
p1.current=p1.current.next;
p2.current=p2.current.next;
}
else if(p1.current.getI()
result.insert(p1.current);
p1.current=p1.current.next;
}else{
result.insert(p2.current);
p2.current=p2.current.next;
}
}
while(p1.current!=null){
result.insert(p1.current);
p1.current=p1.current.next;
}
while(p2.current!=null){
result.insert(p2.current);
p2.current=p2.current.next;
}
return result;
}
//乘法运算
public static PolyList multiply(PolyList p1,PolyList p2){
PolyList result=new PolyList();
//分别指向p1 p2的第一个元素
while(p1.current!=null){
while(p2.current!=null)
{
int a=p1.current.getA()*p2.current.getA();
int i=p1.current.getI()+p2.current.getI();
result.insert(new PolyNode(a,i));
p2.current=p2.current.next;
}
p1.current=p1.current.next;
}
//合并同类项
PolyNode tempPrevious=result.current;
PolyNode temp=result.current.next;
while(result.current.next!=null){
while(temp!=null)
{
if(temp.getI()!=result.current.getI())
{
temp=temp.next;
tempPrevious=tempPrevious.next;
}else{
result.current.setA(result.current.getA()+temp.getA());
tempPrevious.next=temp.next;
temp=temp.next;
}
}
result.current=result.current.next;
tempPrevious=result.current;
temp=result.current.next;
}
return result;
}
}
演示的代码如下：
package poly;
public class PolyDemo {
public static void main(String[] args) {
//多项式p1
PolyList p1=new PolyList();
p1.insert(new PolyNode(2,2));
p1.insert(new PolyNode(100,3));
p1.insert(new PolyNode(45,5));
p1.insert(new PolyNode(3,20));
System.out.println("p1="+p1.printS());
//多项式p2
PolyList p2=new PolyList();
p2.insert(new PolyNode(8,2));
p2.insert(new PolyNode(7,3));
p2.insert(new PolyNode(4,4));
p2.insert(new PolyNode(6,18));
p2.insert(new PolyNode(7,20));
System.out.println("p2="+p2.printS());
//相加
System.out.println("p1+p2="+resultList1.printS());
System.out.println();
//多项式p3
PolyList p3=new PolyList();
p3.insert(new PolyNode(2,1));
p3.insert(new PolyNode(3,2));
p3.insert(new PolyNode(4,3));
System.out.println("p3="+p3.printS());
//多项式p4
PolyList p4=new PolyList();
p4.insert(new PolyNode(5,1));
p4.insert(new PolyNode(1,2));
System.out.println("p4="+p4.printS());
//相乘
PolyList resuList2=PolyList.multiply(p3, p4);
System.out.println("p3*p4="+resuList2.printS());
}
}
运行的结果如下：
p1=2x^2+100x^3+45x^5+3x^20
p2=8x^2+7x^3+4x^4+6x^18+7x^20
p1+p2=10x^2+107x^3+4x^4+45x^5+6x^18+10x^20
p3=2x+3x^2+4x^3
p4=5x+x^2
p3*p4=10x^2+17x^3+23x^4+4x^5

展开全文
• 这次作业的目的就是体会递归的思想。 递归实现加法：递归函数每次都将两个列表中的0号元素相加存到结果列表中，然后列表长度减少1继续执行同样的操作，通过回溯的方法把结果列表拼...#递归实现多项式加法和乘法 de...
• 定义了线性表的抽象类，以及双向链表类及其结点类，实现双向链表的基本功能，还进一步应用到一元多项式的储存、加法和乘法，里面包含了项目文件，测试文件以及报告文件（一元多项式实现的思路）。
• 一元多项式加法和乘法，单链表实现。c++
• 17 //主要进行多项式加法运算 18 polynomial polyMul(polynomial p1, polynomial p2);19 //主要进行多项式乘法运算 20 polynomial polySub(polynomial p1, polynomial p2);21 //主要进行多项式减法运算 22 int ...
• printf("2、两多项式相加得一新多项式\n"); printf("3、两多项式相减得一新多项式\n"); printf("4、销毁已建立的两个多项式\n"); printf("5、退出\n"); printf("\n"); while(sign!='n') { printf("请选择："); ...
• //如果系数相加不为0，则赋值系数的 //如果系数相加为0，则删除该结点 else { t = rear->next; rear->next = t->next; free(t); } } //插入新的结点 else { t = ...
• NULL 博文链接：https://128kj.iteye.com/blog/1611750
• 多项式加法实现原理： （1）如果cpa的指数<cpb的指数，则将cpa所指向的插入多项式链中，向后移动指针； （2）如果cpa的指数>cpb的指数，则将cpb所指向的插入多项式链中，向后移动指针； （3）如果cpa的...
• 02-线性结构2 一元多项式乘法加法运算 （20 分) 设计函数分别求两个一元多项式的乘积与。 输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数指数...
• Name: 多项式加法&乘法实现 Copyright: Author: 小张同学.AC Date: 02/10/21 20:34 Description: 编译器DevC++ 5.4.0 */ #include <iostream> #include <cstdlib> #include <cstdio&...
• C++编写，基于单链表实现多项式加法和乘法
• 多项式的运算是链表使用的典型例子，涵盖了很多链表的操作，值得深度学习与思考。 多项式节点结构体定义为： 包含了系数，指数，以及指向下一节点的指针 struct PolyNode{ int coef; int expon; struct ...
• 多项式加法乘法，链表表示。。 `#include <stdio.h> #include <stdlib.h> //多项式表示 typedef struct PolyNode *Poly; struct PolyNode { int coef;//系数 int expon;//指数 Poly Link;//指针 }; ...
• 多项式加法乘法 #include <iostream> #include <cmath> using namespace std; const int FLAG = -pow(2,31); //输入结束标志 #define MAX 10000 //数组容量 #define OK 1 #define MALLOCFAILED 0 ...
• Java数据结构复习之多项式加法和乘法实现 存储结构 数组 链表 数组实现package com.genge.jichu.polyn;/** * 用数组表示的多项式，以及相关实现 * Created by Genge on 2016-06-15. */ public class Polynomial ...
• 使用链表来实现单元多项式加法、减法、乘法。其中，加法是其它运算的基础，减法：poly1-poly2=poly1+(-poly2)，乘法：poly1*poly2，可用poly1乘以poly2的每一项，相加其乘积结果。
• PTA多项式加法乘法，c语言实现 #include<stdio.h> #include<malloc.h> typedef struct PolyNode *Polynomial; struct PolyNode{ int coef;//系数 int expon;//指数 Polynomial link;//指向下一...
• 加法实现： 先说一下，我用了两种方法实现，一种是顺序表实现，一种是链表实现，所以，为了方便，将两种方法分别写成头文件了，主函数是一样的 方法一（顺序表实现） 直接上代码，头文件"List.h"代码： //...

...