数据结构题——一元多项式相乘

多项式相乘"/>

数据结构题——一元多项式相乘

题目描述
要求采用链表形式，求两个一元多项式的乘积：h3 = h1*h2。函数原型为：void multiplication( NODE * h1, NODE * h2, NODE * h3 )。
输入：
　　输入数据为两行，分别表示两个一元多项式。每个一元多项式以指数递增的顺序输入多项式各项的系数（整数）、指数（整数）。
　　例如：1+2x+x2表示为：<1,0>,<2,1>,<1,2>,
输出：
　　以指数递增的顺序输出乘积： <系数,指数>,<系数,指数>,<系数,指数>,
零多项式的输出格式为：<0,0>,

前置代码

#include <stdio.h>
#include <stdlib.h>typedef struct node
{   int    coef, exp;struct node  *next;
} NODE;void multiplication( NODE *, NODE * , NODE * );
void input( NODE * );
void output( NODE * );void input( NODE * head )
{   int flag, sign, sum, x;char c;NODE * p = head;while ( (c=getchar()) !='\n' ){if ( c == '<' ){    sum = 0;sign = 1;flag = 1;}else if ( c =='-' )sign = -1;else if( c >='0'&& c <='9' ){    sum = sum*10 + c - '0';}else if ( c == ',' ){    if ( flag == 1 ){    x = sign * sum;sum = 0;flag = 2;sign = 1;}}else if ( c == '>' ){    p->next = ( NODE * ) malloc( sizeof(NODE) );p->next->coef = x;p->next->exp  = sign * sum;p = p->next;p->next = NULL;flag = 0;}}
}void output( NODE * head )
{while ( head->next != NULL ){   head = head->next;printf("<%d,%d>,", head->coef, head->exp );}printf("\n");
}int main()
{   NODE * head1, * head2, * head3;head1 = ( NODE * ) malloc( sizeof(NODE) );input( head1 );head2 = ( NODE * ) malloc( sizeof(NODE) );input( head2 );head3 = ( NODE * ) malloc( sizeof(NODE) );head3->next = NULL;multiplication( head1, head2, head3 );output( head3 );return 0;
}

输出结果

这是我写的第二个数据结构的代码，有些心得想在这里跟大家分享！首相，一元多项式相乘的原理大家都很熟悉了，我就不赘述了。这道题有前置代码，所以得按照它的命名要求来，在对多项式进行处理的过程中，比如：当多项式的某一项系数为0时，需要删掉这个项对应的结点，当然只能对p3所指的结果多项式操作，不能对前置代码进行更改。
好，废话不多说，直接上代码（本人代码写得很烂，希望多多指正）：

void multiplication(NODE * head1, NODE * head2, NODE * head3){int coef1, exp1, coef2, exp2;NODE * p1 = head1->next, * p2 = head2->next, * p3 = head3;while(p1){coef1 = p1->coef; exp1 = p1->exp;while(p2){int flag = 0;   //当插入的某一项的指数在多项式里存在时，flag = 1coef2 = p2->coef;   exp2 = p2->exp;if((coef1 == 0 && exp1 == 0) || (coef2 == 0 && exp2 == 0)){     //当相乘的两个多项式中的某一个为<0,0>时，乘积为<0,0>,NODE * temp = (NODE *) malloc(sizeof(NODE));temp->next = NULL;temp->coef = temp->exp =0;p3->next = temp;break;}int coef3, exp3;coef3 = coef1 * coef2;  exp3 = exp1 + exp2;while(p3){      //遍历p3，查找是否有次数与exp3相等的项if(p3->exp == exp3){p3->coef = p3->coef + coef3;flag = 1;}p3 = p3->next;}p3 = head3;if(flag == 1){p2 = p2->next;p3 = head3;continue;}//没有找到次数相等的项，需要新建一个结点，并且有序的插入p3NODE * temp = (NODE *) malloc(sizeof(NODE));NODE * prio;    //用来表示当前p3所指项的前一项temp->coef = coef3;	temp->exp = exp3;while(p3 && temp->exp > p3->exp){       //找到正确的插入位置prio = p3;p3 = p3->next;}p3 = prio;temp->next = p3->next;	p3->next = temp;p2 = p2->next;p3 = head3;}p1 = p1->next;p2 = head2->next;p3 = head3;}NODE * prio;while(p3){      //所得的乘积，需要删去系数为0的项if(p3->coef == 0 && p3->exp != 0){p3 = prio;p3->next = p3->next->next;//	free(p3);p3 = p3->next;}else {prio = p3;p3 = p3->next;}}
}

本人的 qq：1058759658，多多指教！