/*
编译器：Dev-c++ 5.4.0
文件名：Polynomial.cpp
代码版本号：1.0
时间：2015年10月9日21:53:26
*/ /*
总结：
1.结构体指针指向的区域要手动分配内存
2.反复使用的代码封装成函数
*/
#include <stdio.h>
#include <stdlib.h> #define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2 typedef int Status;
typedef struct
{
float coef;
int expn;
}term, ElemType; typedef struct LNode
{
ElemType *data;
struct LNode *next;
}LNode,*Link,*Position; typedef struct _LinkList
{
Link head,tail;
int len;
}LinkList; /*多项式的初始化,建立头结点*/
Status initPolynomial(LinkList *l){
Link p;
p=(Link)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW); p->next=NULL;
(*l).head=(*l).tail=p;
(*l).len=;
printf("多项式初始化成功\n");
return OK;
} /*判断多项式是否为空表*/
bool listEmpty(LinkList *l){
return !l->len;
} /*整数比较函数*/
int comp(int a1,int a2)
{
if(a1>a2)
return ;
else
if(a1==a2)
return ;
else
return -;
} /*判断新节点的指数，定位节点在多项式中是否已经存在*/
int locateLNode(LinkList *l,LNode *p){ LNode *q=((*l).head)->next;
// if(q) printf("q->data->expn为%d,p->data->expn为%d",q->data->expn,p->data->expn);
while(q&&(q->data->expn!=p->data->expn))
{
q=q->next; }
// printf("地址%p\n",q);
if(!q)
return ;
else
{
return ;
}; }
/*销毁多项式*/
Status destroyPoly(LinkList *l){
LNode *p;
LNode *q=l->head;
while(q)
{
p=q->next;
free(p);
q=q->next;
}
free(l->head); return OK;
}
/*创建一个结点*/
LNode *createLNode(){
LNode *q=(LNode*)malloc(sizeof(LNode));
q->data=(ElemType*)malloc(sizeof(ElemType));
return q;
} /*case 新节点的指数相等时只需系数相加*/
Status lNodePlus(LinkList *l,LNode *p){ LNode *q=((*l).head)->next;
while(q && q->data->expn!=p->data->expn)
{
q=q->next; }
if(!q)
return OK;
else
{ q->data->coef+=p->data->coef;
return OK;
}
}
/*case 插入新节点*/
Status insertLNode(LinkList *l,LNode *p){ LNode *q=((*l).head)->next; LNode *qian=(*l).head;//q的前一个节点
while(q&&q->data->expn < p->data->expn){ qian=q;
q=q->next;
}
p->next=q;
qian->next=p;
l->len++;
return OK;
}
/*all 插入节点*/
Status LNodePlus(LinkList *l,LNode *p){
if(locateLNode(l,p)){
lNodePlus(l,p);//指数相等时只需要系数相加
}
else{
insertLNode(l,p);
}
return OK;
} /*创建多项式m项的系数和指数*/
Status createPolynomial(LinkList *l,int m){ float coef; //系数coefficient
int expn;//指数exponent
for(int i=;i<=m;i++){
printf("\n请输入第%d个系数和指数",i);
LNode *p=createLNode();
scanf("%f",&(p->data->coef));
scanf("%d",&(p->data->expn));
LNodePlus(l,p);
}
printf("多项式创建完毕\n");
} /*循环输出多项式的系数和指数*/
Status polyTraverse(LinkList *l)
{
LNode *q=((*l).head)->next;
printf("\n该多项式有%d个项\n",l->len);
while(q)
{
printf("%fx^%d+",q->data->coef,q->data->expn);
q=q->next;
}
return OK;
} /*多项式的加法*/
LinkList addPoly(LinkList *l1,LinkList *l2){ LNode *q1=((*l1).head)->next;
LNode *q2=((*l2).head)->next;
LinkList l;
initPolynomial(&l);
LNode* p=l.head;//p指向多项式最后一项
while(q1 && q2){ switch(comp(q1->data->expn,q2->data->expn))
{
case :{
LNode *q=createLNode(); q->data->coef=q2->data->coef;
q->data->expn=q2->data->expn; q->next=NULL;
p->next=q;
p=p->next; q2=q2->next;
l.len++;
break;
}
case :{
LNode *q=createLNode(); q->data->coef=q1->data->coef+q2->data->coef;
q->data->expn=q1->data->expn; q->next=NULL;
p->next=q;
p=p->next; q1=q1->next;
q2=q2->next;
l.len++;
break;
}
case -:{
LNode *q=createLNode(); q->data->coef=q1->data->coef;
q->data->expn=q1->data->expn; q->next=NULL;
p->next=q;
p=p->next; q1=q1->next;
l.len++;
break;
}
}
} while(q1){
LNode *q=createLNode();
q->data->coef=q1->data->coef;
q->data->expn=q1->data->expn;
q->next=NULL;
p->next=q;
p=p->next;
q1=q1->next;
l.len++;
} while(q2){
LNode *q=createLNode();
q->data->coef=q2->data->coef;
q->data->expn=q2->data->expn;
q->next=NULL;
p->next=q;
p=p->next;
q2=q2->next;
l.len++;
} return l;
} /*多项式系数取反*/
Status getOpposite(LinkList *l){
LNode *q=l->head->next;
while(q)
{
q->data->coef=(-(q->data->coef));
q=q->next;
}
return OK;
}
/*多项式的减法*/
LinkList subtractPoly(LinkList *l1,LinkList *l2){
getOpposite(l2);
LinkList l=addPoly(l1,l2);
getOpposite(l2);
return l;
} /*多项式的乘法*/
LinkList multiplyPoly(LinkList *l1,LinkList *l2){ LinkList l;
initPolynomial(&l);
LNode *q1=l1->head->next;
LNode *q2=l2->head->next;
while(q1){
q2=l2->head->next;
while(q2){
LNode *q=createLNode();
q->data->coef=q1->data->coef*q2->data->coef;
q->data->expn=q1->data->expn+q2->data->expn;
printf("q2->data->coef为%f\n",q2->data->coef);
LNodePlus(&l,q);
q2=q2->next;
}
q1=q1->next;
}
return l;
} int main(){
LinkList l1,l2; /*int n;
LinkList l3;
initPolynomial(&l3);
printf("请输入多项式的term个数:\n");
scanf("%d",&n);
createPolynomial(&l3,n);
polyTraverse(&l3);
destroyPoly(&l3);
printf("删除后遍历:\n");
polyTraverse(&l3);*/ int m;
initPolynomial(&l1);
initPolynomial(&l2);
printf("请输入多项式的term个数:\n");
scanf("%d",&m);
createPolynomial(&l1,m);
createPolynomial(&l2,m);
polyTraverse(&l1);
polyTraverse(&l2);
LinkList L3=addPoly(&l1,&l2);
printf("多项式相加后\n");
polyTraverse(&L3);
LinkList L4=subtractPoly(&l1,&l2);
printf("多项式相减后\n");
polyTraverse(&L4);
LinkList L5=multiplyPoly(&l1,&l2);
printf("多项式相乘后\n");
polyTraverse(&L5);
system("pause");
return ;
}