#include #include #include 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 个元素的值 printf("多项式 ha :"); PolynTraverse(ha, visit); printf("\n"); printf("多项式 hb :"); PolynTraverse(hb, visit); printf("\n"); hc = MergeList(ha,hb); PolynTraverse(hc, visit); }
