数据结构（C语言）用单链表存储一元多项式，并实现两个多项式的相加运算，怎么做？

Answer 1

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

typedef int ElemType;

/*单项链表的声明*/

typedef struct PolynNode{

int coef; // 系数

int expn; // 指数

struct PolynNode *next; }PolynNode,*PolynList;

/*正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表*/

/*指数系数一对一对输入*/ void CreatePolyn(PolynList &L,int n)

{

int i;

下载

原文档已转码为如下格式，以便移动设备查看

数据结构(c语言)用单链表存储一元多项式,并实现两个多项式的相加运算【最新】

阅读：1037次 页数：36页 2016-03-21 举报



#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

typedef int ElemType;

/*单项链表的声明*/

typedef struct PolynNode{

int coef; // 系数

int expn; // 指数

struct PolynNode *next; }PolynNode,*PolynList;

/*正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表*/

/*指数系数一对一对输入*/ void CreatePolyn(PolynList &L,int n)

{

int i;



PolynList p,q;

L=(PolynList)malloc(sizeof(PolynNode)); // 生成头结点

L->next=NULL;

q=L;

printf("成对输入%d个数据\n",n);

for(i=1;i<=n;i++)

{

p=(PolynList)malloc(sizeof(PolynNode));

scanf("%d%d",&p->coef,&p->expn); //指数和系数成对输入

q->next=p;

q=q->next;

}

p->next=NULL;

}

// 初始条件:单链表L已存在

// 操作结果: 依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败

void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType)) {

PolynList p=L->next;

while(p)

{



vi(p->coef, p->expn);

if(p->next)

{

printf(" + "); //“+”号的输出,最后一项后面没有“+”

}

p=p->next;

}

printf("\n");

}

/*ListTraverse()调用的函数(类型要一致)*/ void visit(ElemType c, ElemType e) {

if(c != 0)

{

printf("%dX^%d",c,e); //格式化输出多项式每一项

}

}

/* 多项式相加,原理:归并 */ /* 参数:两个已经存在的多项式 */ /* 返回值:归并后新的多项式的头结点 */

PolynList MergeList(PolynList La, PolynList Lb) {

PolynList pa, pb, pc, Lc;

pa = La->next;

pb = Lb->next;

Lc = pc = La; // 用La的头结点作为Lc的头结点

while(pa&&pb)

{

if(pa->expn < pb->expn)

{

pc->next = pa; //如果指数不相等,pc指针连上指数小的结

点,

pc = pa;

pa = pa->next; //指向该结点的指针后移

}

else if (pa ->expn > pb->expn )

{

pc->next = pb; //pc指针连上指数小的结点,

pc = pb;

pb = pb->next; //指向该结点的指针后移

}

else //(pa ->expn = pb->expn )

{

pa->coef = pa->coef + pb->coef; //指数相等时,系数相加

pc->next = pa;

pc = pa;

pa = pa->next; //两指针都往后移

pb = pb->next;

}

}

pc->next = pa ? pa:pb; // 插入剩余段

return Lc;

}

void main()

{

PolynList ha,hb,hc;

printf("非递减输入多项式ha, ");

CreatePolyn(ha,5); // 正位序输入n个元素的值

printf("非递减输入多项式hb, ");

CreatePolyn(hb,5); // 正位序输入n个元素的值