输入格式： 输入数据为两行，分别表示两个多项式。 每行多项式首先输入一个n，代表多项式的项数，接着是n对整数，每对整数的第一个是系数，第二个是指数。每个多项式不超过100项，整数间用空格隔开。
输出格式： 输出数据是一行，表示结果多项式，依次是若干对整数，每对整数的第一个是系数，第二个是指数，每对整数间用逗号隔开。指数从小到大。如果结果多项式为0，则仅输出0。
输入样例：
3 5 2 4 1 7 0 2 1 4 -4 1输出样例：
7,0 5,2 1,4代码：
//头文件 #include<stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR -1 #define OVERFLOW -2 typedef int Status; //结构体定义 typedef struct { //项的表示,多项式的项作为LinkList的数据元素 int coef; // 系数COEFFICIENT int expn; // 指数EXPONENT }term, ElemType; //两个类型：term用于本ADT，ElemType为LinkList的数据对象名 typedef struct LNode //结点类型 { ElemType data; struct LNode *next; } *Link, *Position; typedef struct //链表类型 {Link head, tail; //分别指向线性链表中的头结点和最后一个结点 int len; //指向线性链表中数据元素的个数 }LinkList; typedef LinkList polynomial; //用带表头结点的有序链表表示多项式 //分函数 Status InitList(LinkList &L) { // 构造一个空的线性链表L Link p; p = (Link)malloc(sizeof(LNode)); // 生成头结点 if (p){ p->next = NULL; L.head = L.tail = p; L.len = 0; return OK; }else return ERROR; } Status MakeNode(Link &p, ElemType e) { // 分配由p指向的值为e的结点，并返回OK；若分配失败。则返回ERROR p = (Link)malloc(sizeof(LNode)); if (!p) return ERROR; p->data = e; return OK; } Status LocateElemP(LinkList L, ElemType e, Position &q, int(*compare)(ElemType, ElemType)) { // 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中 // 第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数 // compare()取值>0的元素的前驱的位置。并返回FALSE Link p = L.head, pp; do { pp = p; p = p->next; } while (p && (compare(p->data, e)<0)); // 没到表尾且p->data.expn<e.expn if (!p || compare(p->data, e)>0) // 到表尾或compare(p->data,e)>0 { q = pp; return FALSE; } else // 找到 {// 没到表尾且p->data.expn=e.expn q = p; return TRUE; } } Status Remove(LinkList &L, Link &q){ //由于项的指数为0，删除掉已有的项 Link h; h = L.head; while (h->next != q) h = h->next; if (q == L.tail)//删除的如果是表尾，改变表尾 L.tail = h; h->next = q->next; free(q); L.len--; return OK; } Position GetHead(LinkList L) { // 返回线性链表L中头结点的位置 return L.head; } Position NextPos(LinkList L, Link p) { //已知 p 指向线性链表 L 中的一个节点，返回 p 所指结点的直接后继的位置 //若无后继，返回 NULL if(p->next!=NULL) return p->next; else return NULL; } int cmp(term a, term b) { // 依a的指数值<、=或>b的指数值，分别返回-1、0或+1 if (a.expn == b.expn) return 0; else if(a.expn > b.expn) return 1; else return -1; } ElemType GetCurElem(Link p) { // 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 return p->data; } Status SetCurElem(Link &p, ElemType e) { // 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值 p->data = e; return OK; }//SetCurElem void FreeNode(Link &p) { // 释放p所指结点 free(p); p = NULL; } Status InsFirst(Link h, Link s) { // h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前 s->next = h->next; h->next = s; return OK; } Status Append(LinkList &L, Link s) { // 将指针s所指(彼此以指针相链,以NULL结尾)的一串结点链接在线性链表L的最后一个结点之 // 后,并改变链表L的尾指针指向新的尾结点 int i=1; L.tail->next=s; while(s->next){ s = s->next; i++; } L.tail = s; L.len += i; return OK; } Status ListEmpty(LinkList L) { // 若线性链表L为空表，则返回TRUE，否则返回FALSE if (L.len) return FALSE; else return TRUE; } void CreatePolyn(polynomial &P,int m) { //输入m项的系数和指数，建立表示一元多项式的有序链表P int i; InitList(P); Link h = GetHead(P); ElemType e; Position q,s; e.coef = 0; e.expn = -1; SetCurElem(h, e);//设置头结点的数据元素 for (i = 1; i <= m; ++i){//依次输入m个非零项 scanf("%d %d", &e.coef, &e.expn); if (!LocateElemP(P, e,q, cmp))//当前链表中不存在该指数项 //(*cmp)() { if (e.coef != 0)//系数不等于0才插入 if (MakeNode(s, e)) InsFirst(q,s);//生成结点并插入链表 } else//当前链表中存在该指数项,增加其系数 { q->data.coef = q->data.coef + e.coef; //如果合起来等于0，则删除掉 if (q->data.coef == 0) Remove(P, q);//删除掉当前节点 } } q=P.head; while(q->next) q=q->next; P.tail=q; P.len=m; } void AddPolyn(polynomial &Pa, polynomial &Pb) { //多项式加法:Pa = Pa+Pb,利用两个多项式的结点构成“和多项式” Position ha, hb, qa, qb; term a, b; ha = GetHead(Pa); hb = GetHead(Pb);//ha和hb分别指向Pa和Pb的头结点 qa = NextPos(Pa,ha); qb = NextPos(Pb,hb);//qa和qb分别指向Pa和Pb中的当前结点 //此时qa和qb都是指向多项式第一项 while (qa && qb)//qa和qb非空 { a = GetCurElem(qa); b = GetCurElem(qb); // a和b为两表中当前比较元素 int sum; switch (cmp(a, b))//比较两者的指数值 //*cmp(a, b) { case -1://多项式中PA中的结点的指数小 ha = qa; qa = NextPos(Pa,ha); break; case 0://两者指数值相等 sum = a.coef + b.coef; if (sum != 0){ //修改Pa指向的该结点的系数值 qa->data.coef = sum; ha=qa; } //SetCurElem(qa,sum); else{ //删除多项式PA中当前结点 ha->next=qa->next; Pa.len--; FreeNode(qa); } //使用DelFirst后表长减一 hb->next=qb->next; Pb.len-=1; FreeNode(qb); qb = NextPos(Pb,hb); qa = NextPos(Pa,ha); break; case 1://多项式PB中的当前结点指数值小 hb->next=qb->next; Pb.len-=1; InsFirst(ha, qb); Pa.len+=1; //使用InsFirst后表长加一 qb = NextPos(Pb,hb); qa = NextPos(Pa,ha); break; }//switch }//while if (!ListEmpty(Pb)) {Append(Pa, qb);// Pa.len+=Pb.len; } //连接Pb中剩余结点 FreeNode(hb); //释放Pb的头结点 } //主函数 int main() { polynomial Pa,Pb; int m,n; Position ha,hb,qa,qb; term a; scanf("%d",&m); CreatePolyn(Pa, m); scanf("%d",&n); CreatePolyn(Pb, n); AddPolyn (Pa, Pb); if(Pa.len==0) { printf("0\n"); return 0;} ha=GetHead(Pa); //ha和hb分别指向Pa和Pb的头结点 qa=NextPos(Pa,ha); while(qa) { printf("%d,%d\n",qa->data.coef,qa->data.expn); ha=qa; qa = NextPos(Pa,ha); } return 0; }测试结果： (供大家参考~
