多项式的相加 - 编程论坛

#2

tianxiao1102010-09-20 16:36

#include<stdio.h>
#include<stdlib.h>
#define NULL 0
typedef struct list
{
    int num;
    int num2;
    struct list *next;
}*link;
/*
链表实现多项式的相加
*/
//建立单链表
link creat_list(int n)
{
    link p1,p2,L;
    int i;
    p2=p1=(link)malloc(sizeof(*p1));
    scanf("%d,%d",&p1->num,&p1->num2);
    L=p1;
    for(i=1;i<n;i++)
    {
         p1=(link)malloc(sizeof(*p1));
         scanf("%d,%d",&p1->num,&p1->num2);
         p2->next=p1;
         p2=p1;
    }
    p1->next=NULL;
    return(L);
}
//单链表的输出函数
void print_list(link head)
{
    link p;
    p=head;

    while(p)
    {
        printf("%d,%d\n",p->num,p->num2);

        p=p->next;

    }
}
//链表相加函数
link add_list(link head1,link head2)
{}
int main()
{
    link headA,headB;
    printf("请输入第一个多项式\n");
    headA=creat_list(4);
    printf("A\n");
    print_list(headA);
    printf("请输入第二个多项式\n");
    headB=creat_list(3);
    printf("B\n");
    print_list(headB);
    return(0);
}
谁能把相加函数补充完整也好啊

#3

wohapppy20102010-09-23 11:47

刚开始学深有同感！1！！

#4

wohapppy20102010-09-23 11:49

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define OVERFLOW -2
#define OK 1

typedef struct LNode
{
float coef;
int expn;
struct LNode *next;
}LNode,*Linklist;

int initlist(LNode *L)
{ L=(LNode *)malloc(sizeof(LNode));
if(!L)exit(OVERFLOW);
L->next=NULL;
return OK;
}

int Creatlist(LNode *L ,int n)
{ LNode *p,*q;
int i;
q=L;
for(i=0;i<n;i++)
{
p=(LNode *)malloc(sizeof(LNode));
printf("Enter the num of coef and tne num of expn:");
scanf("%f,%d",&p->coef,&p->expn);
q->next=p;
q=p;
}
p->next=NULL;
return OK;
}

LNode* selsort(LNode *L) {
LNode *g, *p, *q;
float f;
int i, fini = 1;
if(!L) return NULL;

for(g = L->next;g->next&&fini;g = g->next) {
fini = 0;
for(p = L->next,q = L->next->next;q;p = p->next,q = q->next)
if (p->expn < q->expn) {
f = p->coef;i = p->expn;
p->coef = q->coef;p->expn = q->expn;
q->coef = f;q->expn = i;
fini = 1;
}
}
for(g = L->next,p = g->next;p;)
if(g->expn==p->expn) {
g->coef += p->coef;
g->next = p->next;
q = p;
p = p->next;
free(q);
}
else if(g->next) {
g = g->next;
p = p->next;
}
return L;
}

void PrintfPoly(LNode *L) {
LNode *q = L->next;
if(!q) {
putchar('0');
return;
}
if(q->coef!=1) {
printf("%g",q->coef);
if(q->expn==1) putchar('X');
else if(q->expn) printf("X^%d",q->expn);
}
else if(!q->expn) putchar('1');
else if(q->expn==1) putchar('X');
else printf("X^%d",q->expn);
q = q->next;
while (q) {
if(q->coef > 0) putchar('+');
if(q->coef!=1) {
printf("%g",q->coef);
if(q->expn==1) putchar('X');
else if(q->expn) printf("X^%d",q->expn);
}
else if(!q->expn) putchar('1');
else if(q->expn==1) putchar('X');
else printf("X^%d",q->expn);
q = q->next;
}

}

Compare(LNode *L, LNode *b) {
if (L->next->expn < b->expn) return -1;
if (L->next->expn > b->expn) return 1;
return 0;
}

LNode* APolyn(LNode *L, LNode *Pb) {

LNode *h, *qa = L, *qb = Pb, *p, *q;
float sum;
h=p = (LNode*)malloc(sizeof(LNode));
p->next= NULL;

while (qa && qb) {
switch (Compare(qa,qb)) {
case -1:
p->next= qb;
p = qb;
qb = qb->next;
break;
case 0:
sum = qa->coef + qb->coef;
if (sum != 0.0) {
p ->next= qa;
qa->coef = sum;
p= qa;
qa = qa->next;
}
else {
q = qa;
qa = qa->next;
free(q);
}
q = qb;
qb = qb->next;
free(q);
break;
case 1:
p->next= qa;
p = qa;
qa = qa->next;
break;
}
}
if (qa) p->next= qa;
if (qb) p->next= qb;

q=h;
h=h->next;

free(q);
return h;
}

LNode* A(LNode *L, LNode *Pb) {
LNode *Pa;
PrintfPoly(L);
if(Pb->next && Pb->next->coef>0) printf("+");
PrintfPoly(Pb);
Pa= APolyn(L,Pb);
printf(" = ");
selsort(Pa);
PrintfPoly(Pa);
return Pa;
}

void Addlist(LNode *L ,int X)
{
float sum=0.00;
LNode *p;
p=L->next;
while(p!=NULL)
{
sum+=(p->coef)*pow(X,p->expn);
p=p->next;
}
printf("sum=%f",sum);
}

void main()
{
int X,n,m;
LNode *L,*Pa ,*Pb;
initlist(L);
printf("Enter how many number! n=");
scanf("%d",&n);
Creatlist(L,n);
selsort(L);
PrintfPoly(L);printf("\n");

initlist(Pb);
printf("Enter how many number! m=");
scanf("%d",&m);
Creatlist(Pb,m);
selsort(Pb);
PrintfPoly(Pb);printf("\n");

Pa=A(L,Pb);
printf("\n");
printf("Enter the number X=");
scanf("%d",&X);
Addlist(Pa,X);
getch();
}
粘别人的往能理解

#5

m21wo2010-09-24 21:13

这是我学数据结构编的！有多项式的加法与乘法！！
#include <iostream>
using namespace std;
class Term
{
private:
    int coef;
    int exp;
    Term *link;
    friend ostream & operator << (ostream & ,const Term &);
    friend class Polynominal;
public:
    Term(int c,int e):coef(c),exp(e)
    {  link=0;  }
    Term(int c,int e,Term* nxt):coef(c),exp(e)
    {  link=nxt;  }
    Term* InsertAfter(int c,int e)
    {
        link=new Term(c,e,link);
        return link;
        //return new Term(c,e,this);
    }
    // 这里是重载的 InsertAfter
/*
    Term* InsertAfter(int c,int e, Term* ln)
    {
        ln=new Term(c,e,ln);
        return ln;
    }
*/
};
ostream &operator << (ostream & out,const Term& val)
{
    if(val.coef==0)
        return out;
    out<<val.coef;
    switch(val.exp)
    {
    case 0:break;
    case 1:out<<"X";break;
    default:out<<"X^"<<val.exp;break;
    }
    return out;
}
class Polynominal
{
private:
    Term* thelist;
    int n;
    friend ostream & operator <<(ostream&, const Polynominal &);
    friend istream & operator >>(istream&,Polynominal &);
    friend Polynominal & operator +(Polynominal &, Polynominal &);
    friend Polynominal & operator * (Polynominal &a ,Polynominal &b);
public:
    Polynominal()
    {
        thelist=new Term(0,-1);
        thelist->link=thelist;
        n=0;
        // 你几乎从来没有给 n 其他任何值，而你在乘法函数中
        // 却希望它记录下多项式的大小，你在文件中查找 n++ 或 ++n
        // 可以看出我在那些地方修改了 n 的值，你还可以用其他方法
        // 实现
    }
    /*~Polynominal()
    {
        Term* p=thelist->link;
        while(p!=thelist)
        {
            thelist->link=p->link;
            delete p;
            p=thelist->link;
        }
        delete thelist;
    }*/
//======================================================================
    // 合并次数相同的项, 只需在加法中调用
    void simplify()
    {
        Term* target, *iter, *post_iter;
        target = thelist->link;
        while(target->exp != -1)
        {
            post_iter = target;
            iter = target->link;
            while(iter->exp != -1)
            {
                if(iter->exp == target->exp)
                {
                    target->coef += iter->coef;
                    post_iter->link = iter->link;
                    delete iter;
                    iter = post_iter->link;
                }
                else
                {
                    iter = iter->link;
                    post_iter = post_iter->link;
                }
            }
            target = target->link;
        }
    }
//========================================================================
//
//
    void AddTerms(istream& in)
    {
        Term* q=thelist;
        int c,e;
        for(;;)
        {
            cout<<"Input a term(coef,exp):\n";
            cin>>c>>e;
            if(e<0) break;
            q=q->InsertAfter(c,e);
            n++;
        }
    }
    void Output(ostream& out) const
    {
        int first=1;
        Term *p=thelist->link;
        cout<<"The Polynominal is :\n";
        for(;p!=thelist; p=p->link)
        {
            if(!first&&(p->coef>0)) out<<"+";
            first=0;
            out<<*p;
        }
        cout<<endl;
    }
    void PolyAdd(Polynominal& r)
    {
        Term *q,*q1=thelist,*p;
        p=r.thelist->link;
        q=q1->link;
        while(p->exp>=0)
        {
            while(p->exp< q->exp)
            {
                q1=q;q=q->link;
            }
            if(p->exp==q->exp)
            {
                q->coef=q->coef+p->coef;
                if(q->coef==0)
                {
                    q1->link=q->link;delete q;
                    q=q1->link;
                }
                else
                {
                    q1=q;q=q->link;
                }
            }
            else
            {
                n++;
                q1=q1->InsertAfter(p->coef,p->exp);
            }
            p=p->link;
        }
        //=======================================================
        simplify();
        //=======================================================
    }
    Polynominal& ploymul(Polynominal& sum, Polynominal& r)
    {
        Term* q,*q1=thelist,*p;
        p=r.thelist->link;
        q=q1->link;
        Polynominal* s;
        s=new Polynominal[n];
        for(int i=0;i<n;i++)
        {
            int j=0;
            p=r.thelist->link;

        //=======================================================
        // 在这里添加了一个 temp 变量，最后将 temp->link 的值给 s[i]
        // 这样不需要那个重载的 InsertAfter 函数
                Term* v,*temp;
                temp=v=s[i].thelist->link;
            while(j<r.n)
            {
                // 下面指数应该是相加, 另外我给你重载了一个
                // InsertAfter 函数，这是你的问题的根源所在
                // 你想一想这两个函数的区别
                // 另外 v 的声明及初始化给你移到循环的外面
                // 去了
                v=v->InsertAfter(q->coef*p->coef,q->exp+p->exp);
                // v=v->InsertAfter(q->coef*p->coef,q->exp+p->exp, v);
                ++s[i].n;
                p=p->link;
                j++;
            }
            // 你不该忘记将新创建的多项式记录到 s[i] 中
        //=======================================================
            s[i].thelist->link = temp->link;
        //=======================================================
            v = 0;
            q=q->link;
        }
        for(int i=0;i<n;i++)
        {
            // 这里给你删掉了几行你没有使用的代码
            sum+s[i];
        }
        return sum;
    }
};
ostream& operator << (ostream& out,const Polynominal &x)
{
    x.Output(out);
    return out;
}
istream& operator >> (istream& in,Polynominal &x)
{
    x.AddTerms(in);
    return in;
}
Polynominal& operator + (Polynominal &a ,Polynominal &b)
{
    a.PolyAdd(b);
    return a;
}

Polynominal sum;
// 下面这个函数（及ploymul)返回的是一个引用，所以返回类型不能是临时对象，
// 所以我将 sum 的声明从 ploymul 中移出来了（在这两行注释的上面）
Polynominal& operator * ( Polynominal &a ,Polynominal &b)
{
    return a.ploymul(sum,b);
}
int main()
{
    Polynominal p,q;
    cin>>p;
    cout<<p;
    cin>>q;
    cout<<q;
    q+p;
    cout<<q;
    cout<<(p*q);
    // 注意这个 p * q 实际上是 p*(p+q)
}