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

题目描述
要求采用链表形式，求两个一元多项式的乘积：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 = 1
			coef2 = 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;
			}
			//没有找到次数相等的项，需要新建一个结点，并且有序的插入p3
			NODE * 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，多多指教！

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

相关推荐