任務(wù)描述

本關(guān)任務(wù)：給定兩個(gè)一元多項(xiàng)式A(x)與B(x)，利用鏈表表示A(x)與B(x)，實(shí)現(xiàn)A(x)與B(x)的加法、減法、乘法和求導(dǎo)運(yùn)算。

編程要求

輸入

輸入多組數(shù)據(jù)，總計(jì)n*( a+b+2)+1行。其中，第一行整數(shù)n代表總計(jì)有n組數(shù)據(jù)，之后依次輸入n組數(shù)據(jù)。每組數(shù)據(jù)包括a+b+2行，其中第一行是兩個(gè)整數(shù)a和b，分別代表A(x)與B(x)的項(xiàng)數(shù)。之后緊跟a行，每行兩個(gè)整數(shù)a1和a2，分別代表A(x)每項(xiàng)的系數(shù)和指數(shù)，再之后緊跟b行，每行兩個(gè)整數(shù)b1和b2，分別代表B(x)每項(xiàng)的系數(shù)和指數(shù)，每組數(shù)據(jù)最后一行為一個(gè)字符（+、-、*、'），分別代表多項(xiàng)式的加法、減法、乘法和求導(dǎo)運(yùn)算。所有數(shù)據(jù)的絕對值小于100，指數(shù)大于等于0。

輸出

對于每組數(shù)據(jù)輸出一行，按照多項(xiàng)式次數(shù)從大到小排列，參考格式：5x^17+22x^7+11x^1+7。

測試說明

平臺會(huì)對你編寫的代碼進(jìn)行測試：

測試輸入： 4 1 1 1 0 1 1 + 4 3 7 0 3 1 9 8 5 17 8 1 22 7 -9 8 + 1 1 1 1 1 1 - 1 1 1 1 1 1 ' 預(yù)期輸出： 1x^1+1 5x^17+22x^7+11x^1+7 0 1 1文章來源地址http://www.zghlxwxcb.cn/news/detail-848967.html

#include <iostream>
#include <string>
using namespace std;
typedef struct LNode
{
    int coe;    //系數(shù)coe
    int exp;    //指數(shù)exp
    struct LNode *next;
}LNode,*LinkList;
void CreatePolynomial(LinkList &L,int n)
{//按指數(shù)exp從大到小存多項(xiàng)式
    L=new LNode;
    L->next=NULL;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->coe>>p->exp;
        LinkList pre=L,cur=L->next;      //pre和cur是多項(xiàng)式鏈表的工作指針，分別初始化為頭結(jié)點(diǎn)和首元結(jié)點(diǎn)
		while(cur&&p->exp<cur->exp)    //若待插入項(xiàng)的指數(shù)小于當(dāng)前結(jié)點(diǎn)的指數(shù)，指針pre指向當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)的指針cur后移
		{
			pre=cur;
			cur=cur->next;
		}
		p->next=cur;    //待插入項(xiàng)的指數(shù)不小于當(dāng)前結(jié)點(diǎn)的指數(shù)時(shí)，用頭插法插入節(jié)點(diǎn)
		pre->next=p;
	}
}
void OutputPolynomial(LinkList L)
{//輸出多項(xiàng)式
	if(!L||!L->next) cout<<0;
	LinkList p=L->next;     //p是多項(xiàng)式鏈表的工作指針,初始化為首元結(jié)點(diǎn)
	while(p)
	{
		if(p==L->next)     //p指向首元結(jié)點(diǎn)時(shí)，根據(jù)指數(shù)的情況輸出多項(xiàng)式
        {
			if (p->exp!=0)
				cout<<p->coe<<"x^"<<p->exp;
			else
				cout<<p->coe;
		}
		else      //p指向其他結(jié)點(diǎn)時(shí)，根據(jù)系數(shù)的正負(fù)和指數(shù)的情況輸出多項(xiàng)式
        {
			if(p->coe>0) cout<<"+";
			if(p->exp!=0)
				cout<<p->coe<<"x^"<<p->exp;
			else
				cout<<p->coe;
		}
		p=p->next;
	}
	cout<<endl;
}
LinkList Add(LinkList LA,LinkList LB)
{//多項(xiàng)式的加法運(yùn)算
/**************begin************/
	//1.結(jié)點(diǎn)數(shù)據(jù)域有兩個(gè)，指數(shù)與系數(shù) 
    /* 2.Opt(LinkList &LA,LinkList &LB,string s) 此函數(shù)調(diào)用了+、-、*和輸出多項(xiàng)式的函數(shù)   */
    // 3.return一個(gè)鏈表(因?yàn)橛泻喜⒘说呐c沒合并的)
    LinkList LC,pa,pb,pc;//pa,pb,pc用于指出當(dāng)前準(zhǔn)備操作的結(jié)點(diǎn)
    pa=LA->next;
    pb=LB->next;
    CreatePolynomial(LC,0);//需要建立LC這個(gè)鏈表，LinkList LC只是定義了LC指向一個(gè)結(jié)點(diǎn)，沒有鏈表
    pc=LC;
    while(pa&&pb)//遍歷比較LA與LB的結(jié)點(diǎn)，進(jìn)行合適操作后接在LC后面
    {
        if(pa->exp==pb->exp)//指數(shù)相同，系數(shù)相加后存在pa中,方便接在LC后面
        {
           int sum=pa->coe+pb->coe;
           if(sum)//判斷系數(shù)和是否不為0
           {
               pa->coe=sum;
               pc->next=pa;
               pc=pa;
               pa=pa->next;
               pb=pb->next;
           }
           else 
           {
               pa=pa->next;
               pb=pb->next;
           }
        }
        else if (pa->exp>pb->exp)//指數(shù)大的才接到LC后，pa=pa->next后繼續(xù)和之前的pb->exp比較
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
        pc->next=pa?pa:pb;//某個(gè)鏈表先遍歷完后，直接把另一個(gè)鏈表剩余部分接入LC后
        return LC;
    /**************end************/
}
void Minus(LinkList LA,LinkList LB)
 {//多項(xiàng)式的減法
/**************begin************/
	 LinkList p=LB->next;
     while(p)
     {
         p->coe*=-1;//減法則直接每個(gè)系數(shù)*-1然后調(diào)用剛寫的Add()
         p=p->next;
     }
     OutputPolynomial(Add(LA, LB));

    /**************end************/
 }
void Mul(LinkList LA,LinkList LB)
{//多項(xiàng)式的乘法
/**************begin************/
    LinkList LC;//LC為目標(biāo)多項(xiàng)式鏈表
    LinkList pa=LA->next;
    LinkList pb=LB->next;

    CreatePolynomial(LC, 0);
    LinkList temp;//記錄中間結(jié)果
     CreatePolynomial(temp, 0);
    while(pa)//遍歷比較LA與LB的結(jié)點(diǎn)，進(jìn)行合適操作后接在LC后面
    {
        while(pb)//多項(xiàng)式乘法，就是從LA的第一個(gè)多項(xiàng)式起，遍歷LA的同時(shí)，遍歷LB的多項(xiàng)式并相乘
        {
            LinkList p=new LNode;//p是記錄中間結(jié)果的輔助指針。只是一個(gè)結(jié)點(diǎn)，不能取代可用于Add()的temp用于LC像sun一樣的循環(huán)自增
            p->next=NULL;
            p->coe=pa->coe*pb->coe;
            p->exp=pa->exp+pb->exp;
            temp->next=p;//每次兩個(gè)多項(xiàng)式相乘的結(jié)果，暫時(shí)用p指向，然后
            LC=Add(LC,temp);//pa和pb循環(huán)到最后，LC才是完全體LC。LC每次用自己加上temp，就像sum一樣
            pb=pb->next;
        }
        pb=LB->next;
        pa=pa->next;
    }
    OutputPolynomial(LC);


    /**************end************/
}
void Diff(LinkList L)
{//多項(xiàng)式的求導(dǎo)運(yùn)算
	LinkList p=L->next;  //p是鏈表L的工作指針，初始化為首元結(jié)點(diǎn)
	LinkList r=NULL;  //r是刪除操作的輔助指針
	while(p)
	{
		p->coe*=p->exp;
		p->exp--;
		if(p->exp<0)  //所有數(shù)據(jù)的指數(shù)大于等于0
        {
			r=p;
			p=p->next;
			delete r;
		}
		else
		{
			p=p->next;
		}
	}
	OutputPolynomial(L);
}
void Opt(LinkList &LA,LinkList &LB,string s)
{//依據(jù)字符選擇多項(xiàng)式的加法、減法、乘法和求導(dǎo)運(yùn)算
    if(s=="+") OutputPolynomial(Add(LA, LB));
    if(s=="-") Minus(LA, LB);
    if(s=="*") Mul(LA, LB);
    if(s=="'")
    {
        Diff(LA);
        Diff(LB);
    }
}
int main()
{
    int n;    //總計(jì)有n組數(shù)據(jù)
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        LinkList LA,LB;
        CreatePolynomial(LA,a);
        CreatePolynomial(LB,b);
        string s;
        cin>>s;
        Opt(LA,LB,s);
    }
    return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：鏈表應(yīng)用：第1關(guān)：基于鏈表的兩個(gè)一元多項(xiàng)式的基本運(yùn)算的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！