单链表实现多项式相加

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-10-15 19:17:06
 * @Website: https://grimoire.cn
 * @Description: 
 * @Copyright 2020 Mr.Sen All rights reserved.
 */
#include <iostream>
using namespace std;
//定义结点
typedef struct CreatePolynomial
{
    int coefficient;
    int index;
    struct CreatePolynomial *next;
} Polynomial;
//链表的创建
Polynomial *createPoly(int n)
{
    //创建头节点
    Polynomial *head = new Polynomial;
    Polynomial *pre = head;
    for (int i = 0; i < n; i++)
    {
        //创建新节点
        Polynomial *poly = new Polynomial;
        //为节点赋值
        // cout << "请输入第" << i + 1 << "项的系数和指数：";
        //默认输入的指数从小到大排列
        // cin >> poly->coefficient;
        // cin >> poly->index;
        scanf("%d,%d", &(poly->coefficient), &(poly->index));
        pre->next = poly;
        pre = poly;
        poly->next = NULL;
    }
    return head;
}
//计算结点个数(除头节点之外)
int lengthPolynomial(Polynomial *head)
{
    Polynomial *p = new Polynomial;
    int count = 0;
    p = head->next;
    while (p != NULL)
    {
        count++;
        p = p->next;
    }
    return count;
}
//两个多项式的相加
Polynomial *addpolylist(Polynomial *poly1, Polynomial *poly2) //polynomial:多项式
{
    int temp;
    Polynomial *first, *second, *third;
    //将多项式的和存在第一个多项式里面 ,所以最终返回的是第一个多项式的头结点；
    first = poly1->next;
    second = poly2->next;
    third = poly1;
    while (first && second)
    {
        if (first->index < second->index)
        {
            third->next = first;
            first = first->next;
            third = third->next;
        }
        else if (first->index == second->index)
        {
            temp = first->coefficient + second->coefficient;
            if (temp)
            {
                first->coefficient = temp;
                third->next = first;
                first = first->next;
                second = second->next;
                third = third->next;
            }
            else
            {
                first = first->next;
                second = second->next;
            }
        }
        else
        {
            third->next = second;
            second = second->next;
            third = third->next;
        }
    }
    third->next = (first ? first : second);
    return poly1;
}

//输出每个节点的数据域
void display(Polynomial *head)
{
    Polynomial *p = head->next;
    while (p != NULL)
    {
        if (p->next != NULL)
        {
            if (p->next->coefficient < 0)
            {
                cout << p->coefficient << "*x^" << p->index << " ";
            }
            else
            {
                cout << p->coefficient << "*x^" << p->index << " ";
            }
        }
        else
        {
            cout << p->coefficient << "*x^" << p->index << endl;
        }
        p = p->next;
    }
}
//主函数入口
int main()
{
    int len;
    cin >> len;
    Polynomial *poly1 = createPoly(len);
    cin >> len;
    Polynomial *poly2 = createPoly(len);
    // cout<<"第一个多项式为："<<endl ;
    // display(poly1) ;
    // cout<<"第二个多项式为："<<endl ;
    // display(poly2) ;
    Polynomial *poly = addpolylist(poly1, poly2);
    // cout<<"多项式相加的结果为："<<endl ;
    display(poly);
    return 0;
}