Question

编写C++程序，实现一元稀疏多项式的加法运算。

假设链表结点的类型定义如下：
typedef struct{
double coef; //系数
int expn; //指数
}DataType;
typedef struct node{
DataType data;
struct node *next;
}ListNode,*LinkList;
算法解析：
1. 建立有序链表
2. 多项式链表相加
3. 多项式链表输出

希望能有大部分的注释。

Answer 1

这个程序可行：
#include<stdio.h>

#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int status;
typedef int ElemType;
typedef struct Polynode
{
ElemType coef;
ElemType exp;
struct Polynode *next;
}PolyNode,*PolyList;

void menu();
PolyList PolyCreate();
void PolyAdd(PolyList Polya,PolyList Polyb);
void PolySub(PolyList polya, PolyList polyb);
void PrintPoly(PolyList polya);

void menu()
{
printf("输入选择的功能\n");
printf("1,相加\n");
printf("2,相减\n");
}
PolyList PolyCreate()
{
PolyNode *head,*rear,*s;
ElemType c,e;
head=(PolyNode*)malloc(sizeof(PolyNode));
if(!head)exit(OVERFLOW);
rear=head;
scanf("%d %d",&c,&e);
while(c!=0)
{ s=(PolyNode*)malloc(sizeof(PolyNode));
s->coef=c;
s->exp=e;
rear->next=s;
rear=s;
scanf("%d %d",&c,&e);}
rear->next=NULL;
return(head);}

void PolyAdd(PolyList polya, PolyList polyb)
{PolyNode *p, *q, *pre, *temp;
ElemType sum;
p=polya->next;
q=polyb->next;
pre=polya;
while (p!=NULL && q!=NULL){if(p->exp<q->exp)
{pre->next=p;pre=pre->next;
p=p->next;}
else if ( p->exp==q->exp)
{ sum=p->coef + q->coef ;
if (sum!=0){ p->coef=sum;
pre->next=p;
pre=pre->next;p=p->next;
temp=q; q=q->next;free(temp);}
else{ temp=p->next;free(p);
p=temp ;temp=q->next;free(q);
q=temp ;}
}
else{ pre->next=q;
pre=pre->next;
q =q->next; }
}
if(p!=NULL)pre->next=p;
else pre->next=q;
}
void PrintPoly(PolyList polya)
{
PolyNode *p;
p=polya->next;
while(p)
{printf("%d ",p->coef);
printf("%d\t",p->exp);
p=p->next ;}
}

void PolySub(PolyList polya, PolyList polyb)
{
PolyNode *p, *q, *pre, *temp;
ElemType sum;
p=polya->next;
q=polyb->next;
pre=polya;
while (p!=NULL && q!=NULL)
{if(p->exp<q->exp){
pre->next=p;
pre=pre->next;
p=p->next;
}
else if ( p->exp==q->exp)
{ sum=p->coef-q->coef ;

if (sum!=0)
{ p->coef=sum;
pre->next=p;
pre=pre->next;
p=p->next;
temp=q; q=q->next;
free(temp);}

else{
temp=p->next;free(p);
p=temp ;
temp=q->next;
free(q);
q=temp ;
}
}
else{ pre->next=q;
pre=pre->next;
q =q->next; }
}
if(p!=NULL)pre->next=p;
else pre->next=q;
}

int main(void)
{ PolyNode *pa,*pb;
int j;
printf("输入多项式A B\n");
printf("输入方式为: coef1 exp11 coef2 exp2 0 0\n");
printf("最后用 0 0 结束\n");
printf("请输入多项式a\n");
pa=PolyCreate();
printf("请输入多项式b\n") ;
pb=PolyCreate();
menu();
scanf("%d",&j);
switch (j)
{
case 1:{PolyAdd(pa,pb);break;}
case 2:{PolySub(pa,pb);break;}
}
printf("输出结果为:\n");PrintPoly(pa);
system("PAUSE");
return 0;
}