#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//多项式链表结点类型定义
typedef struct {
float coef; //系数
int expn; //指数
}DataType;
typedef struct node {
DataType data;
struct node *next;
}ListNode,*LinkList;
int q; //定义一全局量
int LocateNode(LinkList L,DataType e)
{ //查找定位算法
ListNode *p=L->next;
q=0; //记录结点位置序号
while(p&&e.expn<p->data.expn)
{ p=p->next;
q++;
}
//printf(“%f,%d\n”,e.coef,e.expn);
if(p==NULL||e.expn!=p->data.expn)
return 0; //查找失败
else
return 1;
}
//有序链表结点的插入
LinkList InsertNode(LinkList L,DataType e)
{ //在有序表中插入一个结点,仍保持表的有序性
ListNode *s,*p;
int i=0;p=L;
while(p->next&&i<q)
{ p=p->next;
i++;
}//查找插入位置
s=(ListNode *)malloc(sizeof(ListNode));
s->data.coef=e.coef;
s->data.expn=e.expn;
s->next=p->next;
p->next=s;
return L;
}
//多项式链表的建立
LinkList CreatPolyn(int n)
{
LinkList pa;
int i;
DataType e;
pa=(ListNode *)malloc(sizeof(ListNode));//生成链表头结点
pa->next=NULL;
for(i=1;i<=n;i++)
{
scanf(“%f,%d”,&e.coef,&e.expn);
if(!LocateNode(pa,e)) //当前链表中不存在该指数项
pa=InsertNode(pa,e);
}
return pa;
}
//多项式链表的输出
void printList(LinkList L)
{
ListNode *p;
p=L->next;
while(p)
{
printf(“%c %fx^%d”,(p->data.coef>0 ? “+” : ” “),p->data.coef,p->data.expn);
p=p->next;
}
printf(“\n”);
}
//多项式两遍的相加
LinkList AddPolyn(LinkList La,LinkList Lb)
{ //两个有序链表La和Lb表示多项式相加
ListNode *pa,*pb,*pc,*s;
LinkList Lc;
float sum;
pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa&&pb){
if(pa->data.expn>pb->data.expn){
pc->next=pa;pc=pa;pa=pa->next;
}
else if(pa->data.expn<pb->data.expn)
{ pc->next=pb;pc=pb;pb=pb->next;
}
else {
sum=pa->data.coef+pb->data.coef;
if(fabs(sum)>1e-6){ //系数和不为零
pa->data.coef=sum;
pc->next=pa;pc=pa;pa=pa->next;
s=pb;pb=pb->next;free(s);
}
else {
s=pa;pa=pa->next;free(s);
s=pb;pb=pb->next;free(s);
}
}
}
pc->next=pa?pa:pb; //插入链表剩余部分
free(Lb); //释放Lb的头结点
return Lc;
}
//主控函数
void main()
{ LinkList La,Lb,Lc;
int n;
printf(“输入第一个多项式的项数: “);
scanf(“%d”,&n);
printf(“输入第一个多项式的每一项的系数,指数: \n”);
La=CreatPolyn(n);
printf(“第一个多项式为: “);
printList(La);
printf(“输入第二个多项式的项数: “);
scanf(“%d”,&n);
printf(“输入第二个多项式的每一项的系数,指数: \n”);
Lb=CreatPolyn(n);
printf(“第二个多项式为: “);
printList(Lb);
Lc=AddPolyn(La,Lb,Lc);
printf(“\n相加后的和多项式为: “);
printList(Lc);
}
#include<stdlib.h>
#include<math.h>
//多项式链表结点类型定义
typedef struct {
float coef; //系数
int expn; //指数
}DataType;
typedef struct node {
DataType data;
struct node *next;
}ListNode,*LinkList;
int q; //定义一全局量
int LocateNode(LinkList L,DataType e)
{ //查找定位算法
ListNode *p=L->next;
q=0; //记录结点位置序号
while(p&&e.expn<p->data.expn)
{ p=p->next;
q++;
}
//printf(“%f,%d\n”,e.coef,e.expn);
if(p==NULL||e.expn!=p->data.expn)
return 0; //查找失败
else
return 1;
}
//有序链表结点的插入
LinkList InsertNode(LinkList L,DataType e)
{ //在有序表中插入一个结点,仍保持表的有序性
ListNode *s,*p;
int i=0;p=L;
while(p->next&&i<q)
{ p=p->next;
i++;
}//查找插入位置
s=(ListNode *)malloc(sizeof(ListNode));
s->data.coef=e.coef;
s->data.expn=e.expn;
s->next=p->next;
p->next=s;
return L;
}
//多项式链表的建立
LinkList CreatPolyn(int n)
{
LinkList pa;
int i;
DataType e;
pa=(ListNode *)malloc(sizeof(ListNode));//生成链表头结点
pa->next=NULL;
for(i=1;i<=n;i++)
{
scanf(“%f,%d”,&e.coef,&e.expn);
if(!LocateNode(pa,e)) //当前链表中不存在该指数项
pa=InsertNode(pa,e);
}
return pa;
}
//多项式链表的输出
void printList(LinkList L)
{
ListNode *p;
p=L->next;
while(p)
{
printf(“%c %fx^%d”,(p->data.coef>0 ? “+” : ” “),p->data.coef,p->data.expn);
p=p->next;
}
printf(“\n”);
}
//多项式两遍的相加
LinkList AddPolyn(LinkList La,LinkList Lb)
{ //两个有序链表La和Lb表示多项式相加
ListNode *pa,*pb,*pc,*s;
LinkList Lc;
float sum;
pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa&&pb){
if(pa->data.expn>pb->data.expn){
pc->next=pa;pc=pa;pa=pa->next;
}
else if(pa->data.expn<pb->data.expn)
{ pc->next=pb;pc=pb;pb=pb->next;
}
else {
sum=pa->data.coef+pb->data.coef;
if(fabs(sum)>1e-6){ //系数和不为零
pa->data.coef=sum;
pc->next=pa;pc=pa;pa=pa->next;
s=pb;pb=pb->next;free(s);
}
else {
s=pa;pa=pa->next;free(s);
s=pb;pb=pb->next;free(s);
}
}
}
pc->next=pa?pa:pb; //插入链表剩余部分
free(Lb); //释放Lb的头结点
return Lc;
}
//主控函数
void main()
{ LinkList La,Lb,Lc;
int n;
printf(“输入第一个多项式的项数: “);
scanf(“%d”,&n);
printf(“输入第一个多项式的每一项的系数,指数: \n”);
La=CreatPolyn(n);
printf(“第一个多项式为: “);
printList(La);
printf(“输入第二个多项式的项数: “);
scanf(“%d”,&n);
printf(“输入第二个多项式的每一项的系数,指数: \n”);
Lb=CreatPolyn(n);
printf(“第二个多项式为: “);
printList(Lb);
Lc=AddPolyn(La,Lb,Lc);
printf(“\n相加后的和多项式为: “);
printList(Lc);
}
解决方案
80
#include<stdio.h> #include<stdlib.h> #include<math.h> //多项式链表结点类型定义 typedef struct { float coef; //系数 int expn; //指数 }DataType; typedef struct node { DataType data; struct node *next; }ListNode,*LinkList; int q; //定义一全局量 int LocateNode(LinkList L,DataType e) { //查找定位算法 ListNode *p=L->next; q=0; //记录结点位置序号 while(p&&e.expn<p->data.expn) { p=p->next; q++; } //printf("%f,%d\n",e.coef,e.expn); if(p==NULL||e.expn!=p->data.expn) return 0; //查找失败 else return 1; } //有序链表结点的插入 LinkList InsertNode(LinkList L,DataType e) { //在有序表中插入一个结点,仍保持表的有序性 ListNode *s,*p; int i=0;p=L; while(p->next&&i<q) { p=p->next; i++; }//查找插入位置 s=(ListNode *)malloc(sizeof(ListNode)); s->data.coef=e.coef; s->data.expn=e.expn; s->next=p->next; p->next=s; return L; } //多项式链表的建立 LinkList CreatPolyn(int n) { LinkList pa; int i; DataType e; pa=(ListNode *)malloc(sizeof(ListNode));//生成链表头结点 pa->next=NULL; for(i=1;i<=n;i++) { scanf("%f,%d",&e.coef,&e.expn); if(!LocateNode(pa,e)) //当前链表中不存在该指数项 pa=InsertNode(pa,e); } return pa; } //多项式链表的输出 void printList(LinkList L) { ListNode *p; p=L->next; while(p) { printf("%c %fx^%d",(p->data.coef>0 ? "+" : " "),p->data.coef,p->data.expn); p=p->next; } printf("\n"); } //多项式两遍的相加 LinkList AddPolyn(LinkList La,LinkList Lb) { //两个有序链表La和Lb表示多项式相加 ListNode *pa,*pb,*pc,*s; LinkList Lc; float sum; pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb){ if(pa->data.expn>pb->data.expn){ pc->next=pa;pc=pa;pa=pa->next; } else if(pa->data.expn<pb->data.expn) { pc->next=pb;pc=pb;pb=pb->next; } else { sum=pa->data.coef+pb->data.coef; if(fabs(sum)>1e-6){ //系数和不为零 pa->data.coef=sum; pc->next=pa;pc=pa;pa=pa->next; s=pb;pb=pb->next;free(s); } else { s=pa;pa=pa->next;free(s); s=pb;pb=pb->next;free(s); } } } pc->next=pa?pa:pb; //插入链表剩余部分 free(Lb); //释放Lb的头结点 return Lc; } //多项式两遍的相加 LinkList SubPolyn(LinkList La,LinkList Lb) { //两个有序链表La和Lb表示多项式相加 ListNode *pa,*pb,*pc,*s; LinkList Lc; float sum; pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb){ if(pa->data.expn>pb->data.expn){ pc->next=pa;pc=pa;pa=pa->next; } else if(pa->data.expn<pb->data.expn) { pb->data.coef = -pb->data.coef; pc->next=pb;pc=pb;pb=pb->next; } else { sum=pa->data.coef-pb->data.coef; if(fabs(sum)>1e-6){ //系数和不为零 pa->data.coef=sum; pc->next=pa;pc=pa;pa=pa->next; s=pb;pb=pb->next;free(s); } else { s=pa;pa=pa->next;free(s); s=pb;pb=pb->next;free(s); } } } s = pb; while(s) { s->data.coef = -s->data.coef; s = s->next; } pc->next=pa?pa:pb; //插入链表剩余部分 free(Lb); //释放Lb的头结点 return Lc; } //主控函数 void main() { LinkList La,Lb,Lc; int n; printf("输入第一个多项式的项数: "); scanf("%d",&n); printf("输入第一个多项式的每一项的系数,指数: \n"); La=CreatPolyn(n); printf("第一个多项式为: "); printList(La); printf("输入第二个多项式的项数: "); scanf("%d",&n); printf("输入第二个多项式的每一项的系数,指数: \n"); Lb=CreatPolyn(n); printf("第二个多项式为: "); printList(Lb); //Lc=AddPolyn(La,Lb); //printf("\n相加后的和多项式为: "); Lc=SubPolyn(La,Lb); printf("\n相减后的和多项式为: "); printList(Lc); }