untitled6.cpp

一元稀疏多项式 的

#include<stdio.h>
#include<malloc.h>


// 定义节点结构体
typedef struct node {
int xi;
int zhi;
struct node *next;
}Xnode,* Xpointer;

// 定义多项式链表结构体
typedef struct Polynomial {
int len;
Xpointer head;
Xpointer end;
}Poly;

// 对于链表的各种操作
// 初始化链表
int InitPoly(Poly *L) {
Xpointer n;
if(!(n=(Xpointer)malloc(sizeof(Xnode)))) return 0;
L->len = 0;
L->head = n;
L->end = n;
n->next = NULL;

return 1;
}

// 取得指定位置的节点
Xpointer GetNode(Poly *L,int pos) {
Xpointer n=L->head;
int i;
if(pos<1||pos>L->len) return 0;
for(i=0;i<pos;i++)
   n = n->next;
return n;
}

// 链表的排序，顺序为zhi的降序排列
void Sort(Poly *L) {
Xpointer n1,n2;
int i,j,temp;
for(i=1;i<L->len;i++) {
   n1=GetNode(L,i);
   for(j=i;j<=L->len;j++) {
    n2=GetNode(L,j);
    if(n1->zhi<n2->zhi) {
     temp=n1->zhi;
     n1->zhi=n2->zhi;
     n2->zhi=temp;
     temp=n1->xi;
     n1->xi=n2->xi;
     n2->xi=temp;
    }//if
   }//for
}//for
}//sort

// 链表的初次输入
int Input_Poly(Poly *L) {
Xpointer s;
int xi,zhi;
scanf("%d %d",&xi,&zhi);
while(xi!=0||zhi!=0) {
   if(!(s=(Xpointer)malloc(sizeof(Xnode)))) return 0;
   s->xi = xi;
   s->zhi = zhi;
   s->next = NULL;
   L->end->next = s;
   L->end = s;
   L->len++;
   scanf("%d %d",&xi,&zhi);
}
return 1;
}

// 链表元素的删除
int Del(Poly *L,int pos) {
Xpointer p,p1;
int len = L->len;
if(pos<1||pos>len) return 0;
p = GetNode(L,pos);
if(pos==1)
   p1 = L->head;
else
   p1 = GetNode(L,pos-1);
p1->next=p->next;
L->len--;
return 1;
}
// 链表元素的定位
int Locate(Poly *L,int zhi) {
Xpointer p = L->head;
int i;
for(i=1;i<=L->len;i++){
   p=p->next;
   if(p->zhi==zhi) break;
}
return i;
}
// 链表（多项式）的输出
void Output_Poly(Poly *L) {
Xpointer n = L->head;
int i;
if(L->len==0) printf("0\n");
else for(i=0;i<L->len;i++) {
   n=n->next;
   printf("%dx%d ",n->xi,n->zhi);
}
}

// 链表的合并
int join(Poly *L,Poly *L1,Poly *L2) {
Xpointer p=L->head,p1,p2,s;
int i;
for(i=1;i<=L1->len;i++) {
   if(!(s=(Xpointer)malloc(sizeof(Xnode)))) return 0;
   p1=GetNode(L1,i);
   s->xi=p1->xi;
   s->zhi=p1->zhi;
   s->next=NULL;
   L->end->next=s;
   L->end=s;
}
for(i=1;i<=L2->len;i++) {
   if(!(s=(Xpointer)malloc(sizeof(Xnode)))) return 0;
   p2=GetNode(L2,i);
   s->xi=p2->xi;
   s->zhi=p2->zhi;
   s->next=NULL;
   L->end->next=s;
   L->end=s;
}
L->len=L1->len+L2->len;
return 1;
}
// 以下是多项式之间的操作
// 多项式的加法
void Poly_add(Poly *L,Poly *L1,Poly *L2) {
Xpointer p;
int i,pos,len;
join(L,L1,L2);
Sort(L);
p=L->head->next;
len=L->len;
for(i=1;i<len;i++) {
   if(p->zhi==p->next->zhi) {
    pos=Locate(L,p->zhi);
    if(p->xi+p->next->xi==0) {
     Del(L,pos);
     Del(L,pos);
    }
    else {
     p->xi=p->xi+p->next->xi;
     Del(L,pos+1);
    }
   }
   else p=p->next;
}
}

// 多项式的减法
void Poly_sub(Poly *L,Poly *L1,Poly *L2) {
Xpointer p2=L2->head->next;
int i;
for(i=1;i<=L2->len;i++) {
   p2->xi = -p2->xi;
   p2=p2->next;
}
Poly_add(L,L1,L2);
}

 main()
{
Poly p1,p2,L,L2;
InitPoly(&p1);
InitPoly(&p2);
InitPoly(&L);
InitPoly(&L2);
printf("请输入多项式a：(系数 指数)\n");
Input_Poly(&p1);
printf("请输入多项式b：(系数 指数)\n");
Input_Poly(&p2);
Sort(&p1);
Sort(&p2);
printf("多项式a为：\n");
Output_Poly(&p1);
printf("\n多项式b为：\n");
Output_Poly(&p2);
printf("\na+b=\n");
Poly_add(&L,&p1,&p2);
Output_Poly(&L);
printf("\na-b=\n");
Poly_sub(&L2,&p1,&p2);
Output_Poly(&L2);
}