线性表及其应用（多项式相加、相乘）----根据程序画出流程图及对每句程序加注释(c语言）
发布网友
发布时间：2022-05-11 08:37
共3个回答
热心网友
时间：2023-10-09 12:37
typedef struct node
{ int c,e; //节点的数据域，c是多项式的系数，e是多项式的指数
struct node *next; //节点的指针域
}PN; //自定义节点结构体，类型PN
PN *createPoly() //这个函数用来建立链表，返回值是一个节点指针
{ int n, e, c;
PN *head, *p; //定义头结点指针head，和节点指针p
printf("请输入多项式项数:");
scanf("%d", &n); //得到n的值，既项数
head=p=new PN ; // * malloc(sizeof(PN));//让head,p都指向头结点（头结点不用来存放数据）
p->next=NULL; //到这里为止，一个空链表建立完成
while( n-- ) //循环n次
{
p->next=new PN;// * malloc(sizeof(PN));//动态分配新的节点，并接在链表末尾（尾插法）
p=p->next;
// printf("c e:"); //给新的节点，添加数据
scanf("%d%d" , &p->c, &p->e);
}
p->next=NULL; //将表尾的指针域置为空
return head; //返回头结点地址
}
void printPoly( PN *head) //这个函数用来输入链表信息
{ PN *p=head->next; //节点指针p用来遍历链表,p先指向表头
while(p) //当p=NULL时（已经到表尾），结束循环
{ printf(" (%d,%d) ", p->c, p->e); //显示当前节点的数据
p=p->next; //将p指向移到下一个节点
}
printf("\n"); //输出一个回车
}
void freePoly( PN *head) //这个函数用来销毁链表
{ PN *p; //用来释放节点（动态内存块）
while( head ) //当head=NULL时（已经到表尾），结束循环
{ p=head; //让p指向head所指的节点
head=head->next; //将head指向移到下一个节点
delete(p); //释放p所指的节点（动态内存块）
}
}
PN *polyAdd(PN *ha, PN *hb) //这个函数用来将两个多项式相加
{ int c, e; //c是多项式的系数，e是多项式的指数
PN *pa=ha->next, *pb=hb->next, //pa,pb用来遍历通过参数传进来的两个链表（参数是两个链表的头结点指针），暂且称它们为链表a,b
*hc, *pc; //hc是两个链表对应节点相加后的新链表的头结点，pc用来遍历新链表,此链表称它为c
hc=pc=new PN;
while( pa || pb ) //当两个链表都遍历完毕，则循环停止
{
if( pa && (pb==NULL || pa->e < pb->e)) //取指数较小的一项链入链表或者链表b已经遍历完毕时，执行该if中的内容
{ c=pa->c;
e=pa->e;
pa=pa->next;
}
else if( pb && (pa==NULL || pa->e > pb->e)) //取指数较小的一项链入链表或者链表a已经遍历完毕时，执行该if中的内容
{ c=pb->c;
e=pb->e;
pb=pb->next;
}
else //指数相等的时候，执行
{ c=pa->c+pb->c;
e=pa->e;
pa=pa->next;
pb=pb->next;
}
if( c ) //将两个链表相加后的每个项 都放入新链表中
{
pc->next=new PN;
pc=pc->next;
pc->c=c;
pc->e=e;
}
}
pc->next=NULL;
return hc; //将新链表的头结点指针返回
}
PN *mulxmul(PN *ha, PN *hb) //这个函数将a表中每个项都掉用一次onexmul函数，最终实现多项式a与b的相乘
{ PN *t, *hc, *pa=ha->next;
PN *onexmul( PN *pa , PN *hb); //函数声明，因为接下来就要用到它
PN *polyAdd(PN *ha, PN *hb); //函数声明，因为接下来就要用到它
t=new PN; t->next=NULL; //存放最终结果的链表，t是表头,此表暂称为t表
while( pa ) //遍历a链表
{ hc=onexmul( pa, hb ); //将a表中pa所指的项与b表中所有的项相乘（即多项式a中的某一项与多项式b相乘）
t=polyAdd( t, hc ); //将每次相乘的结果相加
freePoly( hc ); //将调用onexmul函数产生的中间链表销毁，因为该链表的项，已经放到t链表中
pa=pa->next;
}
return t; //将t表的头结点指针返回
}
PN *onexmul ( PN *pa, PN *hb ) //这个函数用来将a表中pa所指的项与b表中所有的项相乘（即多项式a中的某一项与多项式b相乘）
{ PN *hc, *pc, *pb=hb->next; //hc是新链表的头结点，pc用来遍历新链表
hc=pc=new PN; //让hc,pc都指向头结点
while( pb ) //遍历b链表
{ pc->next=new PN; //建立新链表的节点
pc=pc->next;
pc->c=pa->c * pb->c; //给新节点赋值，系数等于系数相乘
pc->e=pa->e + pb->e; //指数等于指数相加
pb=pb->next;
}
pc->next=NULL;
return hc; //将新链表的头结点指针返回
}
int main()
{ PN *ha, *hb, *hc;
freopen("poly.in" , "r" , stdin); //只读模式打开poly.in
freopen("poly.txt", "w", stdout); //只写模式打开poly.txt
ha=createPoly(); //建立新链表，ha为头结点指针(多项式a)
printPoly(ha); //输出ha为头结点指针的链表信息
hb=createPoly(); //建立新链表，hb为头结点指针(多项式b)
printPoly(hb); //输出hb为头结点指针的链表信息
hc=polyAdd(ha, hb); //多项式a与多项式b相加，结果放在hc为头结点指针的链表中
printPoly(hc); //输出相加后的链表信息
freePoly(hc); //销毁该链表
hc=mulxmul(ha,hb); //多项式a与多项式b相乘，结果放在hc为头结点指针的链表中
printPoly(hc); //输出相乘后的链表信息
freePoly(ha); //销毁该链表
freePoly(hb); //销毁该链表
freePoly(hc); //销毁该链表
return 0;
}
OK,花了不少时间帮你写了下注释，应该比较完整了吧，原理和数学模型完全一样的，应该能看懂，流程图，相信看懂了程序，画起来不难，自己尝试下吧。
热心网友
时间：2023-10-09 12:37
#include<iostream>
#define MaxExp 1000
#define Max 100
using namespace std;
typedef struct Node{
int coef; //系数
int exp; //指数
struct Node *link;//指向下一个节点的指针
}LinkList;
////////////////////////////////////////////////////////
//建立循环链表
void CreateLinkList(LinkList *&L,int Coef[],int Exp[],int n)
{
L=(LinkList *)malloc(sizeof(LinkList));//
L->link=L;
LinkList *p,*s;
p=L; int i; //L指向头结点
for(i=0;i<n;i++){
s=(LinkList*)malloc(sizeof(LinkList)); //创建新结点
s->coef=Coef[i];s->exp=Exp[i];
s->link=L;
p->link=s;
p=s;
}
}
////////////////////////////////////////////////////////////
/*返回X的值*/
int Calc(LinkList *L)
{
LinkList *p;
p=L->link;
int q=0;
while(p!=L)
{
if(p->exp==1){q+=p->coef;}//查找指数为1的项，并返回系数的和
p=p->link;
}
return q;
}
//////////////////////////////////////////////////////////
/*多项式相乘的算法*/
LinkList* Add(LinkList *L1,LinkList *L2)
{/*两多项式相加*/
LinkList *p,*q,*r,*L3,*s;
L3=(LinkList *)malloc(sizeof(LinkList));//创建新链表的头结点
L3->link=L3;
p=L1->link;q=L2->link;r=L3->link;
int sum;
while(p!=L1&&q!=L2)
{
if(p->exp==q->exp)
{ //若指数相等，系数相加，链入链表
sum=p->coef+q->coef;
if(sum!=0)
{s=(LinkList*)malloc(sizeof(LinkList));
s->coef=sum;
s->exp=p->exp;
r->link=s;
r=s;
}
p=p->link;
q=q->link;
}
else
{//若指数不等，取指数较小的一项链入链表
if(p->exp>q->exp)
{s=(LinkList*)malloc(sizeof(LinkList));
s->coef=q->coef;
s->exp=q->exp;
r->link=s;
r=s;
q=q->link;
}
else
{s=(LinkList*)malloc(sizeof(LinkList));
s->coef=p->coef;
s->exp=p->exp;
r->link=s;
r=s;
p=p->link;
}
}
}
while(p!=L1)
{ //链入表1的剩余部分
s=(LinkList*)malloc(sizeof(LinkList));
s->coef=p->coef;
s->exp=p->exp;
r->link=s;
r=s;
p=p->link;
}
while(q!=L2)
{ //链入表2的剩余部分
s=(LinkList*)malloc(sizeof(LinkList));
s->coef=q->coef;
s->exp=q->exp;
r->link=s;
r=s;
q=q->link;
}
r->link=L3;//构成循环链表
return L3;
}
LinkList* Alone(const LinkList *L,int a,int b)
{// 用一个多项式的其中一项乘以另一个多项式，返回新多项式的表头指针
//a为该项的系数，b为该项的指数
LinkList *p,*r,*q;
LinkList *L1;
L1=(LinkList*)malloc(sizeof(LinkList));//创建新链表，使原多项式不改变
L1->link=L1;
p=L->link;
r=L1->link;
while(p!=L)
{ //将改变后的各项系数及指数存入新链表中
q=(LinkList*)malloc(sizeof(LinkList));
q->exp=p->exp+b;
q->coef=p->coef*a;
q->link=L1;
r->link=q;
r=q;
p=p->link;
}
return L1;
}
LinkList* Mulpty(LinkList *a,LinkList *b)
{//多项式相乘，利用相加运算，分解多项式
LinkList *p,*q;
p=a->link;
q=b->link;
LinkList *newl;
newl=(LinkList*)malloc(sizeof(LinkList));
newl->link=newl;
while(p!=a)
{
newl=Add(newl,Alone(b,p->coef,p->exp));
p=p->link;
}
return newl;
}
//////////////////////////////////////////////////////////////////////
void output(LinkList *a)
{ //输出多项式的信息（合并同类项）
int A[MaxExp]={0};
LinkList *p=a->link;
int t=0,i;
while(p!=a) //合并同类项按指数大小从小到大依次输出
{
if(p->exp>t)t=p->exp;
A[p->exp]+=p->coef;p=p->link;
}
cout<<"各项信息："<<endl;
for(i=0;i<=MaxExp;i++)
{
if(A[i]!=0)cout<<'('<<A[i]<<','<<i<<')';
}
cout<<endl;
}
///////////////////////////////////////////////////////////////////////
int main()
{
LinkList *a;
LinkList *b;
int CoefA[Max],ExpA[Max];
int CoefB[Max],ExpB[Max];
int na,nb,i;
cout<<"请输入多项式A的项数："<<endl;
cin>>na;
cout<<"输入各项的系数及指数："<<endl;
for(i=0;i<na;i++)
cin>>CoefA[i]>>ExpA[i];
CreateLinkList(a,CoefA,ExpA,na);
cout<<"请输入多项式B的项数："<<endl;
cin>>nb;
cout<<"输入各项的系数及指数："<<endl;
for(i=0;i<nb;i++)
cin>>CoefB[i]>>ExpB[i];
CreateLinkList(b,CoefB,ExpB,nb);
LinkList *c;
cout<<"A中X的值:"<<Calc(a)<<endl;
cout<<"B中X的值:"<<Calc(b)<<endl;
cout<<"多项式A+B:"<<endl;
output(Add(a,b));
c=Mulpty(a,b);
cout<<"***********************************"<<endl;
cout<<"多项式A*B:"<<endl;
output(c);
cout<<"************************************"<<endl;
cout<<"多项式A:"<<endl; //输出原来的多项式，并未改变
output(a);
cout<<"多项式B:"<<endl;
output(b);
system("pause");
return 0;
}
五、输入输出示例
/*
输入示例：
4
1 0
2 3
5 4
6 2
5
1 1
2 2
2 3
4 6
6 5
输出示例：
A中X的值:0
B中X的值:1
多项式A+B:
各项信息：
(1,0)(1,1)(8,2)(4,3)(5,4)(6,5)(4,6)
***********************************
多项式A*B:
各项信息：
(1,1)(2,2)(8,3)(14,4)(27,5)(18,6)(46,7)(36,8)(38,9)(20,10)
***********************************
多项式A:
各项信息：
(1,0)(6,2)(2,3)(5,4)
多项式B:
各项信息：
(1,1)(2,2)(2,3)(6,5)(4,6)
请按任意键继续. . .
热心网友
时间：2023-10-09 12:38
