-
基于c数据结构——实现多项式合并同类项，加法和乘法
2013-10-30 00:24:51求当前链表数据元素的个数 int Length(SLNode *head) { SLNode *p;// 辅助指针 int size=0; p=head; while(p!=NULL) { size++; p=p->next; } return size; } // ...展开全文#include<stdio.h>
#include<malloc.h>
//定义结点的结构体
typedef struct
{
float x;//系数
int z;//指数
}polynomial;
typedef struct Node
{
polynomial data;
struct Node *next;
}SLNode;
//初始化
void Initial(SLNode **head)
{
*head=(SLNode *)malloc(sizeof(SLNode));
(*head)->next=NULL;
}
//求当前链表数据元素的个数
int Length(SLNode *head)
{
SLNode *p;//辅助指针
int size=0;
p=head;
while(p!=NULL)
{
size++;
p=p->next;
}
return size;
}
//插入多个元素
void Insert(SLNode *head)
{
SLNode *p,*s;//辅助指针
int m;
float n;
p=head;
printf("输入系数x:");
scanf("%f",&n);
printf("输入指数z:");
scanf("%d",&m);
while(m!=0)
{
s=(SLNode *)malloc(sizeof(SLNode));
s->data.x=n;//系数赋值
s->data.z=m;//指数赋值
p->next=s->next;
p->next=s;
printf("输入系数x:");
scanf("%f",&n);
printf("输入指数z:");
scanf("%d",&m);
}
}
/*删除当前指针所指向的元素
void Delete(SLNode *curr)
{
SLNode *p;//辅助指针
p=curr;
curr=curr->next;//指针后移
free(p);
}
*/
///一元多项式及其操作的实现
#include<stdio.h>
#include<malloc.h>
#include"queue.h"
//建立多项式
SLNode *Creat()
{
SLNode *head,*p,*q;
int i,j;
printf("请输入多项式的项数:");
scanf("%d",&j);
Initial(&head);
for(i=0;i<j;i++)
{ q=head;
p=(SLNode*) malloc(sizeof(SLNode));
printf("请输入第%i项的系数和指数:\n\n",i);
printf("请输入第%i项的系数:",i);
scanf("%f",&p->data.x);
if(p->data.x==0)
{
printf("您输入的系数有误，请重新输入!\n");
printf("请输入第%i项的系数:",i);
scanf("%f",&p->data.x);
}
printf("请输入第%i项的指数:",i);
scanf("%d",&p->data.z);
if(q->next==NULL)
{
p->next=q->next;
q->next=p;
}
else
{//printf("hO\n");
while(q->next!=NULL)
{
if(p->data.z==q->next->data.z) {q->next->data.x+=p->data.x;break;}
else if(p->data.z>q->next->data.z) q=q->next;
else if(p->data.z<q->next->data.z) {p->next=q->next;q->next=p;break;}
}
if(q->next==NULL)
{
p->next=q->next;
q->next=p;
}
}
}
while(q->next!=NULL)
{q=q->next;}
q->next=NULL;
// printf("hO\n");
return head;
}
//输出多项式
void printPolyn(SLNode *head)
{
SLNode *p;
int temp=1;
p=head->next;
while(p!=NULL)
{
if(temp==1)
{
if(p->data.z==0) printf("%.2f",p->data.x);
else
{
if(p->data.x==1) printf("x^%d",p->data.z);
else if(p->data.x==-1) printf("-x^%d",p->data.z);
else printf("%.2fx^%d",p->data.x,p->data.z);
}
temp=0;
}
else if(temp==0)
{
if(p->data.x==1) printf("+x^%d",p->data.z);
else if(p->data.x==-1) printf("-x^%d",p->data.z);
else if(p->data.x>0) printf("+%.2fx^%d",p->data.x,p->data.z);
else if(p->data.x<0) printf("%.2fx^%d",p->data.x,p->data.z);
}
p=p->next;
}
printf("\n");
}
//多项式求值
double Polynzhi(SLNode *L,float t)
{
SLNode *p;
int i;
float v;
double m=0;
p=L->next;
while(p!=NULL)
{
if(p->data.z>0)
{
v=1;
for(i=1;i<=p->data.z;i++) v=v*t;
}
else if(p->data.z<=0)
{
v=1;
for(i=p->data.z;i<0;i++) v=v/t;
}
m+=p->data.x*v;
p=p->next;
}
return m;
}
int Polynadd(SLNode *pa,SLNode *pb,SLNode **pc)
{
void Initial(SLNode **head);
float x;
SLNode *p,*q,*r;
Initial(pc);
p=pa->next;
q=pb->next;
r=*pc;
while(p!=NULL&&q!=NULL)
{
if(p->data.z<q->data.z)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r=r->next;
r->data.z=p->data.z;
r->data.x=p->data.x;
p=p->next;
}
else if(p->data.z==q->data.z)
{
x=p->data.x+q->data.x;
if(x)
{
r->next=(SLNode *)malloc(sizeof (SLNode));
r=r->next;
r->data.z=p->data.z;
r->data.x=x;
p=p->next;
q=q->next;
}
else if(x==0)
{
p=p->next;
q=q->next;
}
}
else if(p->data.z>q->data.z)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r=r->next;
r->data.z=q->data.z;
r->data.x=q->data.x;
q=q->next;
}
}
while(p!=NULL&&q==NULL)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r=r->next;
r->data.z=p->data.z;
r->data.x=p->data.x;
p=p->next;
}
while(p==NULL&&q!=NULL)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r=r->next;
r->data.z=q->data.z;
r->data.x=q->data.x;
q=q->next;
}
r->next=NULL;
return 1;
}
//多项式乘法
int Polynmul(SLNode *pa,SLNode *pb,SLNode **pd)
{
void Initial(SLNode **head);
float x,y;
int i=1,z;
SLNode *p,*q,*r;
Initial(pd);
// p=pa->next;
p=pa;
q=pb;
r=*pd;
while(p->next!=NULL)
{
p=p->next;
q=pb->next;
while(q!=NULL)
{
// r->next=(SLNode *)malloc(sizeof(SLNode));
// r=r->next;
if(i==1) ///第一项
{
x=p->data.x*q->data.x;
if(x==0)
{
q=q->next;
i=1;
}
else if(x!=0)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r=r->next;
r->data.z=p->data.z+q->data.z;
r->data.x=x;
q=q->next;
i=0;
}
} ///第一项
else if(i==0)
{
z=p->data.z+q->data.z;
x=p->data.x*q->data.x;
if(x==0) q=q->next;
else if(x!=0)
{
if(r->data.z<z)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r=r->next;
r->data.x=x;
r->data.z=z;
q=q->next;
p=p;
}
else if(r->data.z==z)
{
y=x+r->data.x;
if(y==0)
{
q=q->next;
p=p;
}
else if(y!=0)
{
r->data.x=y;
r->data.z=z;
q=q->next;
p=p;
}
}
else if(r->data.z>z)
{
r->next=(SLNode *)malloc(sizeof(SLNode));
r->next->data.x=r->data.x;
r->next->data.z=r->data.z;
r->data.x=x;
r->data.z=z;
r=r->next;
q=q->next;
p=p;
}
}
}
}
//p=p->next;
}
r->next=NULL;
return 1;
}
//测试程序
#include<stdio.h>
#include<malloc.h>
#include"queue1.h"
#include<windows.h>
int main()
{
//实现多项式a和b
SLNode *a,*b,*c,*d;
int i;
float t;
double z;
printf("请输入未知数t的值:");
scanf("%f",&t);
a=Creat();
printf("多项式a为:");
printPolyn(a);
b=Creat();
printf("多项式b为:");
printPolyn(b);
printf("*******************************************\n");
printf("******1.多项式求值*********2.多项式加法****\n");
printf("*******************************************\n");
printf("******3.多项式乘法*********4.退出系统******\n");
printf("*******************************************\n");
printf("请输入您的选择：\n");
while(1)
{
scanf("%d",&i);
switch(i)
{
case 1:{
z=Polynzhi(a,t);
printf("多项式a的值为:%lf",z);
printf("\n");
z=Polynzhi(b,t);
printf("多项式b的值为:%lf",z);
printf("\n");
continue;
}
case 2:{
printf("多项式a与多项式b的和为:");
Polynadd(a,b,&c);
printPolyn(c);
printf("\n");
z=Polynzhi(c,t);
printf("多项式a与b的和c多项式的值为:%lf",z);
printf("\n");
continue;
}
case 3:{
printf("多项式a与多项式b的积为:");
Polynmul(a,b,&d);
printPolyn(d);
printf("\n");
z=Polynzhi(d,t);
printf("多项式a与b的积d多项式的值为:%lf",z);
printf("\n");
continue;
}
case 4:
{
printf("正在退出系统,请稍等......\n");
exit(0);
}
}
}
return 0;
}
-
数据结构与算法-实验1-多项式的计算：合并同类项、升幂排序、多项式加法、减法、乘法
2016-11-07 09:26:53/* */ #include #include #include using namespace std; //多项式的项 typedef struct polynomial //定义struct类型数据 { int n; //统计链表中元素个数 int coef, index; //每一项系数及指数 struc展开全文#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
//多项式的项
typedef struct polynomial //定义struct类型数据
{
int n; //统计链表中元素个数
int coef, index; //每一项系数及指数
struct polynomial *next; //指向下一项的指针
}POLY;
POLY *Create_poly(void);
POLY *Sort_poly(POLY *head); //对多项式按升幂顺序排序
POLY *Tidy_poly(POLY *head); //对多项式合并同类项
POLY *Add_poly(POLY *, POLY *); //多项式加法
POLY *Dec_poly(POLY *, POLY *); //多项式减法
POLY *Mul_poly(POLY *, POLY *); //多项式乘法
void Print_poly(POLY *);
int main(void)
{
POLY *heada = NULL, *headb = NULL, *headsum = NULL, *headmul = NULL;
printf("创建第一个多项式:\n");
heada = Create_poly();
printf("创建第二个多项式:\n");
headb = Create_poly();
printf("第一个多项式是:\n");
Print_poly(heada);
printf("第二个多项式是:\n");
Print_poly(headb);
headsum = Add_poly(heada, headb);
printf("两多项式相加结果是:");
Print_poly(headsum);
headsum = Dec_poly(heada, headb);
printf("两多项式相减结果是:");
Print_poly(headsum);
headmul = Mul_poly(heada, headb);
printf("两多项式相乘结果是:");
Print_poly(headmul);
return 0;
}
//创建
POLY *Create_poly()
{
int count = 0; //数据节点个数计数
int coef = 0, index = 0;
POLY *head = NULL, *s = NULL, *r = NULL;
head = (POLY *)malloc(sizeof(POLY)); //申请新节点空间，头节点
r = head;
printf("请输入多项式每一项的系数及其对应的指数(以0 0结束):\n");
scanf_s("%d%d", &coef, &index);
while (coef != 0)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = coef, s->index = index;
r->next = s;
r = s; //移动的节点，起针的作用
count++;
scanf_s("%d%d", &coef, &index);
}
r->next = NULL;
head->n = count;
head = Tidy_poly(head);
return head;
}
//合并同类项
POLY *Tidy_poly(POLY *head)
{
int p2start = 0;
POLY *p1 = NULL, *p2 = NULL, *p2p = NULL;
if (head == NULL){ return NULL; } //如果传进的是空表，则返回空
if (head->next == NULL){ return head; } //如果传进的是只有一个节点的表，则直接返回此表
p1 = p2 = p2p = head;
while (p1->next != NULL)
{
while (p2->next != NULL)
{
if (p1->index == p2->index)
{
if (p2start == 0)
{
p2start = 1;
p2 = p2->next; //首次分离p2p与p2
}
else
{
p1->coef = p1->coef + p2->coef;
//然后进行删除后面相同指数的节点操作
if (p2->next == NULL)
{
p2p->next = NULL;
head->n--;
break;
}
p2 = p2->next;
p2p->next = p2;
head->n--;
}
}
else //指数不等，移动p2
{
if (p2->next == NULL){ break; }
p2p = p2;
p2 = p2->next;
}
}
if (p1->index == p2->index&&p2start == 1) //回收最后一个元素
{
p1->coef = p1->coef + p2->coef;
p2p->next = NULL;
head->n--;
}
if (p1->next == NULL)
{
head = Sort_poly(head); //排序
return head;
}
p1 = p2 = p2p = p1->next;
p2start = 0;
}
head = Sort_poly(head); //排序
return head;
}
//升幂排序
POLY *Sort_poly(POLY *head)
{
int pflag1 = 0,flag = 1;
POLY *p1 = NULL, *pMin = NULL, *p2 = NULL, *ptemp = NULL;
if (head == NULL){ return NULL; } //如果传进的是空表，则返回空
if (head->next == NULL){ return head; } //如果传进的是只有一个节点的表，则直接返回此表
p1 = pMin = ptemp = p2 = head;
while (p1->next != NULL)
{
if (pflag1 == 0)
{
pflag1 = 1;
}
else
{
ptemp = p1;
pMin = p2 = p1->next;
}
while (p2->next != NULL) //找出最小指数
{
p2 = p2->next;
if (pMin->index > p2->index) //分离pMin、p2
{
pMin = p2;
}
}
if (pMin != head) //注意起始的时候别访问越界
{
while (ptemp->next != pMin) //定位ptemp在pMin之前
{
ptemp = ptemp->next;
}
}
if (flag==1) //第一次插入的是head后
{
if (head == pMin) //是跟在head后的开头元素吗
{
p1 = head;
flag = 0;
continue;
}
else
{
//把元素剪出来，插入head后面
if (pMin->next == NULL)
{
ptemp->next = NULL;
}
else
{
ptemp->next = pMin->next;
}
pMin->next = head->next;
head->next = pMin;
p1 = head;
flag = 0;
continue;
}
}
else
{
//这里是插入在p1后
if (pMin->next == NULL)
{
ptemp->next = NULL;
}
else
{
ptemp->next = pMin->next;
}
pMin->next = p1->next;
p1->next = pMin;
p1 = pMin;
}
}
return head;
}
//相加
POLY *Add_poly(POLY *opera1, POLY *opera2)
{
POLY *head, *tmp, *s = NULL;
int value;
opera1 = opera1->next;
opera2 = opera2->next;
head = tmp = (POLY*)malloc(sizeof(POLY));
head->next = NULL;
while (opera1 &&opera2)
{
if (opera1->index == opera2->index)
{
value = opera1->coef + opera2->coef;
if (value != 0)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = opera1->index;
s->next = NULL;
}
opera1 = opera1->next;
opera2 = opera2->next;
}
else
if (opera1->index <opera2->index)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = opera1->coef;
s->index = opera1->index;
s->next = NULL;
opera1 = opera1->next;
}
else
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = opera2->coef;
s->index = opera2->index;
s->next = NULL;
opera2 = opera2->next;
}
if (head->next == NULL)
{
head->next = s;
tmp = s;
}
else
{
tmp->next = s;
tmp = s;
}
}
tmp->next = opera1 ? opera1 : opera2;
return head;
}
//相减，不能改变原链，多项式还有其他用
POLY *Dec_poly(POLY *head1, POLY *head2)
{
//定义为head1-head2,漏斗法
int value;
int flag = 0,flag1=1,flag2=1;
int pflag=1;
POLY *head = NULL, *pt1 = NULL, *pt2 = NULL, *phead = NULL, *s = NULL;
pt1 = head1;
pt2 = head2;
while (pt1->next != NULL&&pt2->next != NULL) //两个多项式分别多于两项，其中任一置空的都已回收
{
if (flag == 0)
{
flag = 1;
}
else
{
if (pflag == 1) //移动pt1
{
pt1 = pt1->next;
}
else if (pflag==2) //移动pt2
{
pt2 = pt2->next;
}
else if (pflag == 3) //同时移动pt1、pt2
{
pt1 = pt1->next;
pt2 = pt2->next;
}
}
if (pt1->index == pt2->index)
{
value = pt1->coef - pt2->coef;
if (value != 0)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = value; //系数
s->index = pt1->index; //指数
s->next = NULL;
if (flag1 == 1) //首次将head、phead接上第一个节点空间
{
flag1 = 0; //状态置换
head = phead = s;
pflag = 3;
}
else
{
phead->next = s;
phead = phead->next;
pflag = 3;
}
}
}
else if (pt1->index <pt2->index)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = pt1->coef;
s->index = pt1->index;
s->next = NULL;
if (flag1 == 1) //首次将head、phead接上第一个节点空间
{
flag1 = 0;
head = phead = s;
pflag = 1;
}
else
{
phead->next = s;
phead = phead->next;
pflag = 1;
}
}
else
{
value = 0 - pt2->coef;
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = pt2->index;
s->next = NULL;
if (flag1 == 1) //首次将head、phead接上第一个节点空间
{
flag1 = 0;
head = phead = s;
pflag = 2;
}
else
{
phead->next = s;
phead = phead->next;
pflag = 2;
}
}
}
//什么置空导致while退出，还是同时空(合并或者不合并，或者不作处理)，回收元素
if (pt1->next == NULL&&pt2->next != NULL) //pt1置空
{
while (pt2->next != NULL)
{
if (flag2 == 1)
{
flag2 = 0;
}
else
{
pt2 = pt2->next;
}
if (flag == 0) //要回收pt1，即head==phead==NULL
{
flag = 1; //状态置换
s = (POLY *)malloc(sizeof(POLY));
s->coef = pt1->coef;
s->index = pt1->index;
s->next = NULL;
head = phead = s;
value = 0 - pt2->coef;
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = pt2->index;
s->next = NULL;
phead->next= s;
phead = phead->next;
}
else
{
if (pflag == 3) //此时的pt2不回收
{
pflag = 4; //置新状态
continue;
}
value = 0 - pt2->coef;
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = pt2->index;
s->next = NULL;
phead->next = s;
phead = phead->next;
}
}
}
else if (pt2->next== NULL&&pt1->next != NULL) //pt2置空
{
while (pt1->next != NULL)
{
if (flag2 == 1)
{
flag2 = 0;
}
else
{
pt1 = pt1->next;
}
if (flag == 0) //要回收pt2，即head==phead==NULL
{
flag = 1; //状态置换
value = 0 - pt2->coef;
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = pt2->index;
s->next = NULL;
head = phead = s;
s = (POLY *)malloc(sizeof(POLY));
s->coef = pt1->coef;
s->index = pt1->index;
s->next = NULL;
phead->next = s;
phead = phead->next;
}
else
{
if (pflag == 3) //此时的pt1不回收
{
pflag = 4; //置新状态
continue;
}
s = (POLY *)malloc(sizeof(POLY));
s->coef = pt1->coef;
s->index = pt1->index;
s->next = NULL;
phead->next = s;
phead = phead->next;
}
}
}
else //同时置空
{
if (flag == 0) //即一开始两数就仅有一项
{
if (pt1->index < pt2->index)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = pt1->coef;
s->index = pt1->index;
s->next = NULL;
head = s;
value = 0 - pt2->coef;
s = (POLY *)malloc(sizeof(POLY));
s->coef =value;
s->index = pt2->index;
s->next = NULL;
head->next = s;
}
else if (pt1->index > pt2->index)
{
value = 0 - pt2->coef;
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = pt2->index;
s->next = NULL;
head = s;
s = (POLY *)malloc(sizeof(POLY));
s->coef = pt1->coef;
s->index = pt1->index;
s->next = NULL;
head->next = s;
}
else
{
value = pt1->coef - pt2->coef; //合并
if (value != 0)
{
s = (POLY *)malloc(sizeof(POLY));
s->coef = value;
s->index = pt1->index;
s->next = NULL;
head = s;
}
}
}
//不是开始都为空，状态为运算到结尾同时为空，运算结束
}
return head;
}
//相乘
POLY *Mul_poly(POLY *op1, POLY *op2)
{
POLY *head;
POLY *t, *q, *s, *r;
head = (POLY *)malloc(sizeof(POLY));
head->next = NULL;
r = (POLY *)malloc(sizeof(POLY));
r->next = NULL;
for (t = op1->next; t; t = t->next) //双重循环，即第一项多项式每一项乘上第二项的每一项
{
for (q = op2->next; q; q = q->next)
{
s = (POLY *)malloc(sizeof(POLY));
r->next = s;
s->coef = q->coef * t->coef;
s->index = q->index + t->index;
s->next = NULL;
head = Add_poly(r, head);
}
}
return head;
}
//输出
void Print_poly(POLY *head)
{
int flag = 1;
POLY *p = NULL;
p = head->next;
if (p == NULL)
printf("多项式为空！\n");
else
{
do
{
if (p->coef >= 0)
{
if (flag == 1)
{
printf("%dx^%d", p->coef, p->index);
flag = 0;
}
else
{
printf("+%dx^%d", p->coef, p->index);
}
}
else
printf("%dx^%d", p->coef, p->index);
p = p->next;
} while (p != NULL);
printf("\n");
}
}
-
java链表实现一元多项式的合并同类项以及加法
2017-03-28 17:41:56上课的作业：利用java数据结构的知识表示一元多项式，以及实现一元多项式的加法运算以及合并同类项 链表节点类： package PloyItem; public class Lnode implements Comparable{ public float coef; public ...展开全文上课的作业：利用java数据结构的知识表示一元多项式，以及实现一元多项式的加法运算以及合并同类项
链表节点类：
多项式类：package PloyItem; public class Lnode implements Comparable<Lnode>{ public float coef; public int exp; public Lnode next; public Lnode (float coef,int exp){ this.exp=exp; this.coef=coef; next=null; } public Lnode(float coef,int exp,Lnode next){ this.exp=exp; this.coef=coef; this.next=next; } public boolean equals(Object e){ Lnode node=(Lnode)e; return (exp==node.exp); } @Override public int compareTo(Lnode o) { // TODO Auto-generated method stub return 0; } }
测试类：package PloyItem; import java.util.Iterator; import org.junit.Test; import seqList.AbList; public class PloyItemList { private int length; Lnode first; public PloyItemList(int length) { first=null; this.length=length; } public PloyItemList(){ first=null; length=0; } public int size()//获取链表的长度 { Lnode p=first; int count=0; while(p!=null){ count++; p=p.next; } return count; } public boolean add(float coef,int exp)//向链表当中添加元素的方法 { Lnode p=first,s; s=new Lnode(coef,exp,null); if(first==null){ first=s; s.next=null; return true; } else { while(p.next!=null){ p=p.next; } p.next=s; s.next=null; return true; } } public boolean add(float coef)//想链表当中添加元素的方法 { Lnode p=first,s; s=new Lnode(coef,0,null); if(first==null){ first=s; s.next=null; return true; } else { while(p.next!=null){ p=p.next; } p.next=s; s.next=null; return true; } } public void sort(){//对多项式进行降序排列的方法 Lnode p,q;int i,j,m;float n; for( i=0,p=first;i<this.size()-1;i++,p=p.next) for(j=i+1,q=p.next;j<this.size();j++,q=q.next) if(p.exp<q.exp) { m=p.exp;p.exp=q.exp;q.exp=m; n=p.coef;p.coef=q.coef;q.coef=n; } } public void union()//对多项式进行合并同类项的方法 { Lnode p,q,r; sort(); p=first; q=p.next; while(p!=null&& q!=null){ if(p.exp==q.exp) { r=q; p.coef=p.coef+q.coef; remove(q.coef,q.exp); p=r; q=r.next; } else { p=q; q=q.next; } } } public void remove (float coef,int exp)//删除链表当中的某一个节点的方法 { Lnode p=first,q=p; for(q=p;q!=null;q=q.next) if(q.next.coef==coef && q.next.exp==exp) break; q.next=q.next.next; } public String toString()//将链表转化为一个字符串输出的方法 { String s="p(x)="; Lnode p=first; sort(); union(); while(p!=null){ if(p.coef==0) s=s+"+"; else if(p.exp==0) s=s+p.coef+"+"; else if(p.exp==1) s=s+p.coef+"x"+"+"; else s=s+p.coef+"x^"+p.exp+"+"; p=p.next; } return s.substring(0, s.length()-1)+"\n"; } public void addPloyItem(PloyItemList p2)//多项式想家的而方法 { this.sort();p2.sort(); Lnode p=this.first,q=p2.first; while(p!=null || q!=null) { if(p!=null && q!=null) { if(p.exp==q.exp){ p.coef+=q.coef; p=p.next;q=q.next; } else if(p.exp<q.exp){ this.add(q.coef, q.exp); q=q.next; } else { this.add(q.coef, q.exp); q=q.next; } } else if(p==null && q!=null) this.add(q.coef, q.exp); else if(p!=null && q==null) p=p.next; } } }
测试的结果：package PloyItem; /** * 用线性表实现一元多项式的加法运算以及多项式的输出 * @author asus * */ public class PolyItemDemo { public static void main(String[] args) { PloyItemList p1=new PloyItemList(4); p1.add(3, 3);p1.add(2, 2);p1.add(1, 1);p1.add(1); System.out.println("第一个多项式(合并同类项)："+p1); p1.add(4, 4); p1.add(15); p1.add(3, 2); System.out.println(p1); System.out.println("多项式的项数为(合并同类项)："+p1.size()); PloyItemList p2=new PloyItemList(); p2.add(6,4);p2.add(4,4);p2.add(3,2);p2.add(1,0); System.out.println(p2); p2.add(19); System.out.println(p2); System.out.println("多项式的项数为："+p2.size()); System.out.println("多项式的相加："); p1.addPloyItem(p2); System.out.println("相加的结果为："+p1); } }
-
一元多项式 java_java链表实现一元多项式的合并同类项以及加法
2021-03-06 06:59:51上课的作业：利用java数据结构的知识表示一元多项式，以及实现一元多项式的加法运算以及合并同类项链表节点类：package PloyItem;public class Lnode implements Comparable{public float coef;public int exp;...展开全文上课的作业：利用java数据结构的知识表示一元多项式，以及实现一元多项式的加法运算以及合并同类项
链表节点类：
package PloyItem;
public class Lnode implements Comparable{
public float coef;
public int exp;
public Lnode next;
public Lnode (float coef,int exp){
this.exp=exp;
this.coef=coef;
next=null;
}
public Lnode(float coef,int exp,Lnode next){
this.exp=exp;
this.coef=coef;
this.next=next;
}
public boolean equals(Object e){
Lnode node=(Lnode)e;
return (exp==node.exp);
}
@Override
public int compareTo(Lnode o) {
// TODO Auto-generated method stub
return 0;
}
}
多项式类：
package PloyItem;
import java.util.Iterator;
import org.junit.Test;
import seqList.AbList;
public class PloyItemList {
private int length;
Lnode first;
public PloyItemList(int length)
{
first=null;
this.length=length;
}
public PloyItemList(){
first=null;
length=0;
}
public int size()//获取链表的长度
{
Lnode p=first;
int count=0;
while(p!=null){
count++;
p=p.next;
}
return count;
}
public boolean add(float coef,int exp)//向链表当中添加元素的方法
{
Lnode p=first,s;
s=new Lnode(coef,exp,null);
if(first==null){
first=s;
s.next=null;
return true;
}
else {
while(p.next!=null){
p=p.next;
}
p.next=s;
s.next=null;
return true;
}
}
public boolean add(float coef)//想链表当中添加元素的方法
{
Lnode p=first,s;
s=new Lnode(coef,0,null);
if(first==null){
first=s;
s.next=null;
return true;
}
else {
while(p.next!=null){
p=p.next;
}
p.next=s;
s.next=null;
return true;
}
}
public void sort(){//对多项式进行降序排列的方法
Lnode p,q;int i,j,m;float n;
for( i=0,p=first;i
for(j=i+1,q=p.next;j
if(p.exp
{
m=p.exp;p.exp=q.exp;q.exp=m;
n=p.coef;p.coef=q.coef;q.coef=n;
}
}
public void union()//对多项式进行合并同类项的方法
{
Lnode p,q,r;
sort();
p=first;
q=p.next;
while(p!=null&& q!=null){
if(p.exp==q.exp)
{r=q;
p.coef=p.coef+q.coef;
remove(q.coef,q.exp);
p=r;
q=r.next;
}
else {
p=q;
q=q.next;
}
}
}
public void remove (float coef,int exp)//删除链表当中的某一个节点的方法
{
Lnode p=first,q=p;
for(q=p;q!=null;q=q.next)
if(q.next.coef==coef && q.next.exp==exp)
break;
q.next=q.next.next;
}
public String toString()//将链表转化为一个字符串输出的方法
{
String s="p(x)=";
Lnode p=first;
sort();
union();
while(p!=null){
if(p.coef==0)
s=s+"+";
else if(p.exp==0)
s=s+p.coef+"+";
else if(p.exp==1)
s=s+p.coef+"x"+"+";
else
s=s+p.coef+"x^"+p.exp+"+";
p=p.next;
}
return s.substring(0, s.length()-1)+"\n";
}
public void addPloyItem(PloyItemList p2)//多项式想家的而方法
{
this.sort();p2.sort();
Lnode p=this.first,q=p2.first;
while(p!=null || q!=null)
{
if(p!=null && q!=null)
{
if(p.exp==q.exp){
p.coef+=q.coef;
p=p.next;q=q.next;
}
else if(p.exp
this.add(q.coef, q.exp);
q=q.next;
}
else {
this.add(q.coef, q.exp);
q=q.next;
}
}
else if(p==null && q!=null)
this.add(q.coef, q.exp);
else if(p!=null && q==null)
p=p.next;
}
}
}
测试类：
package PloyItem;
/**
* 用线性表实现一元多项式的加法运算以及多项式的输出
* @author asus
*
*/
pub
95b1
lic class PolyItemDemo {
public static void main(String[] args) {
PloyItemList p1=new PloyItemList(4);
p1.add(3, 3);p1.add(2, 2);p1.add(1, 1);p1.add(1);
System.out.println("第一个多项式(合并同类项)："+p1);
p1.add(4, 4);
p1.add(15);
p1.add(3, 2);
System.out.println(p1);
System.out.println("多项式的项数为(合并同类项)："+p1.size());
PloyItemList p2=new PloyItemList();
p2.add(6,4);p2.add(4,4);p2.add(3,2);p2.add(1,0);
System.out.println(p2);
p2.add(19);
System.out.println(p2);
System.out.println("多项式的项数为："+p2.size());
System.out.println("多项式的相加：");
p1.addPloyItem(p2);
System.out.println("相加的结果为："+p1);
}
}
测试的结果：
标签：
-
数据结构 一元多项式运算
2018-04-20 17:49:14链表的生成利用链表实现一元多项式的+、-、*运算，注意具体的思路是判断同类项，对其进行合并同类项，在乘法运算达到了O(n^3)，可以优化的地方是先对结果链表C进行预处理，先复制这个链表给C，然后表C的操作过程就将... -
SzNOI 数据结构 c001
2015-01-23 23:13:02/**********************************************************************************/ /* Problem: c001 "合并同类项" from */ /* Language: C++ -
数据结构mooc课小结（2.1）
2017-05-15 18:35:39用数组下标表示指数，合并同类项的时候，找同类项就比较方便，去下标就好了。 但是空间浪费的问题严重，如果指数的跨度比较大，那么大部分元素都是0。 而且灵活性不足，不能表示负指数。 链表则相反，灵活性有了... -
数据结构学习笔记（二）多项式加法与乘法
2016-03-26 23:39:12之前自己看书学链表、栈、队列，觉得比较难懂，还是得自己动手实践下。这次就是实现一个多项式的加法和乘法运算，主要是要求熟练链表的各种操作...加法实现：多项式相加其实就是比较指数，相同则合并同类项，不同则直接 -
数据结构（java）多项式的相加
2018-10-10 10:40:31多项式的相加要求：两个...输出要求：合并两个多项式的同类项并将系数的输出到屏幕。 需要创建两个class文件 PolynNode.class : package lianbiao; public class PolynNode { public double coef; public int exp... -
数据结构 链表实现多项式加法，减法，乘法
2018-10-14 19:54:21乘法比较麻烦,想了想最终决定用插入排序变式来进行排序+同类项合并，即在插入的过程中进行合并.... 代码如下： #include <cstdio> #include <cstring> #include <algorithm&... -
第三章 3.1 数据结构和序列（3）
2019-07-10 22:52:051、zip函数将序列组合成一个元祖列表，元素的个数取决于最短的序列 2、字典也称为数据映射或关联数组，由键值对形式...5、集合的合并是去除同类项后的相加，使用union方法或者|运算符 6、取两个集合的交集使... -
多项式相乘(英文版数据结构第三章习题)
2016-10-19 12:16:41//编写一个函数，实现多项式相乘，多项式次数分别为M,N //法一： //开个结果多项式，次数为MN；...//依次计算结果的MN项，再排序，合并同类项，复杂度为MN+MN*log(MN),简化为O(MN*log(MN)) //法四： //利用哈希映射 -
【数据结构】用链表实现多项式运算
2016-08-08 12:31:06一元多项式的运算包括加法减法和乘法，而多项式的加法和乘法都可以依靠多项式的加法来实现，所以本文仅仅讲解如何用链表实现一元多项式的加法。...所谓的多项式相加就是同类项的合并，也就是两条链表的 -
【C++算法与数据结构学习笔记------单链表实现多项式】
2012-04-23 21:45:00C++单链表实现多项式加法(polyAdd)，多项式乘法(polyMul)，多项式合并同类项(mergerPoly)，多项式减法，多项式除法就不贴出来了。 1 #include<iostream.h> 2 template<class T> 3 cla... -
数据结构的一元稀疏多项式代码，在插入过程中的循环，没转过弯来，望有大神提点！
2016-06-05 10:02:21{ //若输入的指数相同，则合并同类项 q2->coef += p->coef; free(p); if(q2->coef==0) //q2项系数为0时，直接插入 { q1->next=q2->next; free(q2); } } else { //指数为新时将结点插入 p->next=... -
python实现树结构的json文件_python实现树形结构的json文件
2020-12-11 10:14:52本例为将所有IP进行一个统计，合并同类项，之后根据IP的四个字段分为四层。第一层为第一个字段，第二层为第二个字段，以此类推，总共四层。数据格式类似下图：image.png实现思路：1.将IP统计后的结果以dataframe的... -
一元多项式加法乘法运算C+链表
2018-04-06 17:34:40完美的数据结构大作业之选。C语言+链表 实现。不用提前知道多项式项数，可以自动排序，可以合并同类项，可以进行加法、乘法运算。VS环境可运行，其他编程软件找到cpp复制粘贴即可 -
一元多项式加法乘法运算c
2018-04-06 17:42:38不用提前知道多项式项数，可以自动排序，可以合并同类项，可以进行加法、乘法运算。//#include<stdio.h> //#include<stdlib.h> #include"stdafx.h" #include<malloc.h... -
利用表实现一元多项式的加法和乘法
2011-07-16 17:14:51这里采用顺序表即数组，因为进行的随机访问操作较多，而插入、删除操作较少关键点：对保存一元多项式的数据结构进行置0的初始化，这便于减少对系数为0的判断以及乘法合并同类项加法很简单，对应幂系数相加即可，加和... -
C语言实现一元多项式加法运算
2020-10-08 23:12:11说到一元多项式相加，相信很多小伙伴都不会陌生，甚至 “合并同类项” 已经要脱口而出了（因为上节课本人就是这样的哈哈~） 回到正题，一元多项式的加法运算，大概是这样的： 知道怎么操作了之后就来看看如何储存... -
单例dispatch_once造成的死锁
2020-08-29 14:47:35好久没有更新了，这一次遇到一个单例模式造成的死锁，比较有代表性，这里做一个总结，分享给大家 ...经过几次的信息获取，合并同类项，终于发现了这几个死锁的共同特性（）， 即总会同时出现以下两 -
然之协同管理系统 v2.4 专业版.zip
2019-07-16 05:50:13然之协同管理系统专业版简介 然之协同管理系统由客户管理(crm)、日常办公(oa)、现金记账(cash)、团队分享(team)和应用导航(ips)五大模块组成，主要面向中小团队的企业内部管理。...同类推荐：站长常用源码 -
金码出纳管理系统 V5.60.exe
2013-02-01 14:20:32经多家软件测评中心测评，它的易用性、稳定性、实用性、功能性等多项指标均居同类软件第一，被评为国内最好用的出纳软件。 它具有操作简易性、高度智能性、超强稳定性、强大的报表功能、完善的内部控制、便捷的... -
delphi 开发经验技巧宝典源码
2010-08-12 16:47:230051 结构对象的定义与使用 32 0052 使用数组为TlistView组件动态创建字段 33 0053 解决程序的死锁问题 34 0054 怎样实现接口委托 34 0055 在Delphi中使用汇编 35 0056 为程序设置版本和帮助信息 36 ... -
-
精易模块[源码] V5.15
2015-03-21 22:03:378、修复“注册表操作Ex->写入键值Ex”创建项，重启丢失的BUG，感谢易友【pp25729391】反馈。 9、修复“文本_转拼音”传入的参数变成全角的BUG，感谢易友【reloking】反馈。 10、修复“编码_Utf8到Unicode”频繁操作... -
095《JsonFormatter》轻量化Json开源格式化工具查看一言api接口字段数据结构 094《SmoothScroll》让网页滚动如奶油般顺滑的奇妙小工具 093《Search to Play the Song》在浏览器中随时听我想听的歌~(周杰伦的也行...
数据结构
订阅