一元稀疏多项式.txt

本程序是采用数据结构的算法实现一元稀疏多项式加法器的功能

一元稀疏多项式相加 
设计一个一元多项式加法器。实现： (1)输入并建立多项式； (2)两个多项式相加； (3)输出多项式：n, c1, e1, c2, e2, …cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。 

1、一元稀疏多项式相加 


详细设计 

1 程序头的设计: 
#include<stdio.h> 
#include<malloc.h> 
typedef struct pnode 
{int coef;/*系数 */ 
int exp;/*指数 */ 
struct pnode *next;/*下一个指针*/ 
}pnode; 

2 用头插法生成一个多项式，系数和指数输入0时退出输入 
pnode * creat() 
{int m,n; pnode *head,*rear,*s; 
/*head为头指针，rear和s为临时指针*/ 

head=(pnode *)malloc(sizeof(pnode)); 
rear=head; 
/*指向头*/ 
printf("input coef:");/*输入系数*/ 
scanf("%d",&n); 
printf("input exp:");/*输入指数*/ 
scanf("%d",&m); 
while(n!=0)/*输入0就退出*/ 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=n; 
s->exp=m; 
s->next=NULL; 
rear->next=s;/*头插法*/ 
rear=s; 
printf("input coef:");/*输入系数*/ 
scanf("%d",&n); 
printf("input exp:");/*输入指数*/ 
scanf("%d",&m); 
} 
head=head->next;/*第一个头没有用到*/ 
return head; 
} 
3 显示一个多项式 
void display(pnode *head) 
{pnode *p;int one_time=1; p=head; 
while(p!=NULL)/*不为空的话*/ 
{ 
if(one_time==1) 
{if(p->exp==0)/*如果指数为0的话，直接输出系数*/ 
printf("%d",p->coef); /*如果系数是正的话前面就要加+号*/ 
else if(p->coef==1||p->coef==-1) 
printf("x^%d",p->exp);/*如果系数是1的话就直接输出+x*/ 
/*如果系数是-1的话就直接输出-x号*/ 
else if(p->coef>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/ 
printf("%dx^%d",p->coef,p->exp); 
else if(p->coef<0)/*如果系数是小于0的话就输出系数x^指数的形式*/ 
printf("%dx^%d",p->coef,p->exp); 
one_time=0; 
} 
else{ 
if(p->exp==0)/*如果指数为0的话，直接输出系数*/ 
{if(p->coef>0) 
printf("+%d",p->coef); /*如果系数是正的话前面就要加+号*/ 
} 
else if(p->coef==1) 
printf("+x^%d",p->exp); 
else if(p->coef==-1) 
printf("x^%d",p->exp);/*如果系数是1的话就直接输出+x号*/ 
else if(p->coef>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/ 
printf("+%dx^%d",p->coef,p->exp); 
else if(p->coef<0)/*如果系数是小于0的话就输出系数x^指数的形式*/ 
printf("%dx^%d",p->coef,p->exp); 
} 
p=p->next;/*指向下一个指针*/ 
} 
printf("\n"); 

4 两个多项式的加法运算 
pnode * add(pnode *heada,pnode *headb) 
{pnode *headc,*p,*q,*s,*r; 
/*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并并向右移动*/ 
int x; 
/*x为系数的求和*/ 
p=heada; 
/*指向第一个多项式的头*/ 
q=headb; 
/*指向第二个多项式的头*/ 
headc=(pnode *)malloc(sizeof(pnode)); 
r=headc; 
/*开辟空间*/ 
while(p!=NULL&&q!=NULL) 
/*2个多项式的某一项都不为空时*/ 
{if(p->exp==q->exp)/*指数相等的话*/ 
{x=p->coef+q->coef;/*系数就应该相加*/ 
if(x!=0)/*相加的和不为0的话*/ 
{s=(pnode *)malloc(sizeof(pnode));/*用头插法建立一个新的节点*/ 
s->coef=x; 
s->exp=p->exp; 
r->next=s; 
r=s; 
} 
q=q->next;p=p->next; 
/*2个多项式都向右移*/ 
} 
else if(p->exp<q->exp)/*p的系数小于q的系数的话，就应该复制q接点到多项式中*/ 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=q->coef; 
s->exp=q->exp; 
r->next=s; 
r=s; 
q=q->next;/*q向右移动*/ 
} 
else/*p的系数大于q的系数的话，就应该复制p接点到多项式中*/ 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=p->coef; 
s->exp=p->exp; 
r->next=s; 
r=s; 
p=p->next;/*p向右移动*/ 
} 
} 
当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生 
while(p!=NULL) 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=p->coef; 
s->exp=p->exp; 
r->next=s; 
r=s; 
p=p->next; 
} 
当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生 
while(q!=NULL) 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=q->coef; 
s->exp=q->exp; 
r->next=s; 
r=s; 
q=q->next; 
} 
r->next=NULL; 
/*最后指向空*/ 
headc=headc->next;/*第一个头没有用到*/ 
return headc;/*返回头接点*/ 

5 两个多项式的减法运算，和加法类似，不同的地方已经注释 
pnode * sub(pnode *heada,pnode *headb) 
{pnode *headc,*p,*q,*s,*r; 
int x; 
p=heada;q=headb; 
headc=(pnode *)malloc(sizeof(pnode)); 
r=headc; 
while(p!=NULL&&q!=NULL) 
{if(p->exp==q->exp) 
{x=p->coef-q->coef;/*系数相减*/ 
if(x!=0) 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=x; 
s->exp=p->exp; 
r->next=s; 
r=s; 
} 
q=q->next;p=p->next; 
} 
else if(p->exp<q->exp)/*p的系数小于q的系数的话*/ 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=-q->coef;/*建立的接点的系数为原来的相反数*/ 
s->exp=q->exp; 
r->next=s; 
r=s; 
q=q->next; 
} 
else 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=p->coef; 
s->exp=p->exp; 
r->next=s; 
r=s; 
p=p->next; 
} 
} 
while(p!=NULL) 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=p->coef; 
s->exp=p->exp; 
r->next=s; 
r=s; 
p=p->next; 
} 
while(q!=NULL) 
{s=(pnode *)malloc(sizeof(pnode)); 
s->coef=-q->coef;/*建立的接点的系数为原来的相反数*/ 
s->exp=q->exp; 
r->next=s; 
r=s; 
q=q->next; 
} 
r->next=NULL; 
headc=headc->next; 
return headc; 

6 界面设计: 
printf("\n ****************************************\n"); 
printf("\n ************** 03 Computer *************\n"); 
printf("\n ******** Class:two **** Num:34 *********\n"); 
printf("\n *********** Name: xie pan **********\n"); 
printf("\n ****************************************\n"); 
printf("\n --------------1: add -------------\n"); 
printf("\n --------------2: sub -------------\n"); 
printf("\n --------------3: exit ------------\n"); 
printf("\n ****************************************\n"); 

7 连接程序: 
case 1:add_main();break;/*加法*/ 
case 2:sub_main();break;/*减法*/ 
case 3:break;/*退出*/