本学期最后一个技术贴，多项式加、乘法
/*[全民编程]76道C++高难度自虐题之43：对于次数很高，但项目很少的多项式，可用链表来表示。
例如：X^1000－76*X^76＋3*X^3－7可表示为
┌─┬──┬─┐┌──┬─┬─┐ ┌─┬─┬─┐┌─┬─┬──┐
│1 │1000│┼→│-76 │78│┼→ │3 │3 │┼→│-7│0 │ NIL│
└─┴──┴─┘└──┴─┴─┘ └─┴─┴─┘└─┴─┴──┘
在此方式下，编程完成两个多项式的加法与乘法。
*/
#include <iostream.h>
class Node
{
private:
int cof;
int exp;
Node* next;
public:
//用默认值初始化
Node()
{
cof=0;
exp=0;
next=NULL;
}
//用给定值初始化
Node(int cof,int exp)
{
this->cof=cof;
this->exp=exp;
next=NULL;
}
//建立多项式
Node* CreateLink(Node* head,int m);
//取头节点
Node* GetHead(Node* head);
//多项式加法
Node* AddNode(Node* head1,Node* head2);
//乘法
Node* MultiNode(Node* head1,Node* head2,Node* head3);
//输出
void Display(Node* head);
};
/*取头节点*/
Node* Node::GetHead(Node* head)
{
return head;
}
/*输出多项式*/
void Node::Display(Node* head)
{
Node* temp=head;
while(temp!=NULL)
{
temp=temp->next;
if(temp->exp==0)//处理指数为0的情况
cout<<temp->cof<<"";
else
cout<<temp->cof<<"*X^"<<temp->exp<<"";
}
cout<<endl;
}
/*建立链表，m为节点数*/
Node* Node::CreateLink(Node* head,int m)
{
Node *p=head;
cout<<"Input cof and exp"<<endl;
for(int i=1;i<=m;i++)
{
int cof,exp;
cout<<"cof:";
cin>>cof;
cout<<"exp";
cin>>exp;
Node* newnode=new Node;
newnode->cof=cof;
newnode->exp=exp;
newnode->next=p->next;
p->next=newnode;
p=newnode;
}
return head;
}
/*多项式加法*/
Node* Node::AddNode(Node* head1,Node* head2)
{
Node* ha=GetHead(head1);
Node* hb=GetHead(head2);
Node *la=ha,*lb=hb;
Node *qa=la->next;
Node *qb=lb->next;
while(qa!=NULL && qb!=NULL)//pa,pb不为空指数比较
{
if(qa->exp > qb->exp)//如果qa指数大
{
la=qa;
qa=qa->next;
}
if(qa->exp == qb->exp)//如果指数相等
{
int sum=qa->cof+qb->cof;
if(sum!=0)//系数不为0
{
/*修改系数值*/
qa->cof=sum;
la=qa;
qa=qa->next;
lb->next=qb->next;
delete qb;
qb=lb->next;
}
else//系数为0
{
/*删除多项式pa中的当前节点*/
la->next=qa->next;
delete qa;
qa=la->next;
lb->next=qb->next;
delete qb;
qb=lb->next;
}
}
if(qa->exp < qb->exp)//如果pb指数大
{
/*qb在前*/
lb->next=qb->next;
la->next=qb;
qb->next=qa;
la=qb;
qb=lb->next;
}
}
if(qb!=NULL)
la->next=qb;
delete lb;
return ha;
}
/*乘法*/
Node* Node::MultiNode(Node* head1,Node* head2,Node* head3)
{
Node* ha=GetHead(head1);
Node* hb=GetHead(head2);
Node* hc=GetHead(head3);
Node *la=ha,*lb=hb,*tmp=hc;
Node* qa=la->next;
Node* qb=lb->next;
while(qa!=NULL)
{
while(qb!=NULL)
{
/*系数相乘指数相加*/
int sumc=qa->cof*qb->cof;
int sume=qa->exp+qb->exp;
/*结果存入新的节点*/
Node* newnode=new Node;
newnode->cof=sumc;
newnode->exp=sume;
newnode->next=tmp->next;
tmp->next=newnode;
tmp=newnode;
qb=qb->next;
}
/*qb回到第一个qa指向下一个*/
qb=lb->next;
qa=qa->next;
}
delete tmp;
return hc;
}
int main()
{
Node* head1=new Node;
Node* head2=new Node;
Node* head3=new Node;
Node n1;
n1.CreateLink(head1,2);
cout<<"Ploy1:";
n1.Display(head1);
n1.CreateLink(head2,2);
cout<<"Ploy2:";
n1.AddNode(head1,head2);
cout<<"Ploy1 add ploy2:";
n1.Display(head1);
n1.MultiNode(head1,head2,head3);
cout<<"Ploy1 mut ploy2:";
n1.Display(head3);
return 0;
}现在我累计了7道了，外国朋友Hjin（后来得知不是中国的至于哪国他也没说），势如破竹累计了17道，现在他还在做，差距还在拉大，更可怕的是压轴的第76题他已经KO了，胜负已分了:funk ，所以现在比赛已经演变为了Hjin的程序设计艺术展了:titter，我放假后个把星期不能上，可能会被追上
[ 本帖最后由 zkkpkk 于 2007-7-4 19:20 编辑 ] 沙发，都不喜欢算法......
页:
[1]