单链表实现多项式相加~求指教
#include<stdio.h>
#include<malloc.h>
#include<process.h> // exit()
#define ERROR 0
#define OVERFLOW -2


typedef struct LNode{
float coef; // 系数
int expn; // 指数
struct LNode *next;
}*LinkList;


void InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
if(!L) // 存储分配失败
exit(OVERFLOW);
L->next=NULL; // 指针域为空
}


typedef LinkList Polyn;

void CreatePolyn(Polyn &P,int m){
//InitList(P);
LinkList s=P,L;
P->coef=0.0;P->expn=-1;
for(int i=1;i<=m;i++){
L=(LinkList)malloc(sizeof(LNode)); // 生成新结点
scanf("%f,%d",&L->coef,&L->expn);
s->next=L;
s=s->next;
}
s->next=NULL;
}

int compare(Polyn p1,Polyn p2){
if(p1->expn < p2->expn)
return -1;
else
return (p1->expn > p2->expn?
1:0);
}

void ListDelete(LinkList &L,int i) // 算法2.10。不改变L
{ // 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋
{
p=p->next;
j++;
}
if(!p->next||j>i-1) // 删除位置不合理
exit(ERROR);
q=p->next; // 删除并释放结点
p->next=q->next;
free(q);
}

void ListTraverse(LinkList L)
// vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同
{ // 初始条件：线性表L已存在
// 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败
LinkList p=L->next;
while(p)
{
printf("%f*x^%d",L->coef,L->expn);
while(p->next)
printf("+");
p=p->next;
printf("\n");
}
}


void AddPolyn(Polyn &P1,Polyn &P2){
LinkList h1,h2,q1,q2;
h1=P1,h2=P2;//h1,h2分别为指向P1,P2的头节点
q1=h1->next; q2=h2->next;//q1,q2分别指向P1,P2的当前节点

for(int i=1; q1 && q2 ;i++){
switch(compare(q1,q2)){
case -1:
q1=q1->next;
break;
case 0:
q1->coef += q2->coef;
q2=q2->next;
if(!q1->coef)
ListDelete(P1,i);
break;
case 1:
h2->next=q2->next;
h1->next=q2;
q2->next=q1;
q2=h2->next;
break;
}//switch
}//for
if(q2)
q1->next=q2;
free(P2);
}




void main()
{
Polyn P1,P2;
int m,n;
InitList(P1);
InitList(P2);

//创建两个多项式的链表
printf("输入m项的系数及指数\n");
printf("m=");
scanf("%d",&m);
CreatePolyn(P1,m);
printf("P1=");
ListTraverse(P1);

/*printf("输入n项的系数及指数\n");
printf("n=");
scanf("%d",&n);
CreatePolyn(P2,m);
printf("P2=");
ListTraverse(P2);
*/
//实现多项式相加
AddPolyn(P1,P2);
printf("P1+P2=");
ListTraverse(P1);
}

[解决办法]
给你一个我很早时候写的

C/C++ code

#ifndef LINKLIST_H#define LINKLIST_H/******************* 线性表的单链表存储结构 ********************/template <typename ElemType> class LinkList;template <typename ElemType> class LNode  // 结点类{    friend class LinkList<ElemType>;protected:    ElemType data;  // 数据域    LNode<ElemType> *next;  // 指针域public:    LNode<ElemType>() { }    LNode<ElemType>(const ElemType &dt, LNode *nx) { data = dt; next = nx; }    ~LNode<ElemType>() { }    ElemType GetData() const { return data; }    LNode *GetNext() const { return next; }    void SetData(const ElemType &dt) { data = dt; }    void SetNext(LNode *nx) { next = nx; }};template <typename ElemType> class LinkList{protected:    LNode<ElemType> *head;  // 头指针public:    LinkList<ElemType>() { InitList(); }    LinkList<ElemType>(const LinkList<ElemType> &list);  // 拷贝构造函数    ~LinkList<ElemType>() { DestroyList(); }    LNode<ElemType> *GetHead() const { return head; }    void SetHead(LNode<ElemType> *ph) { head = ph; }    void InitList();  // 构造一个空的单链表    void DestroyList();  // 销毁单链表    void ClearList();  // 将单链表置空    bool ListEmpty() const { return (head->next == NULL); }  // 探空    int ListLength() const;  // 返回单链表中数据元素的个数    bool GetElem(int i, ElemType &e);  // 用e返回单链表第i个元素的值（算法2.8）    int LocateElem(const ElemType &e);  // 返回单链表中第1个与e相等的值所在的位置    bool PriorElem(const ElemType &cur, ElemType &pre);  // 用pre返回cur的前驱    bool NextElem(const ElemType &cur, ElemType &nxt);  // 用nxt返回cur的后继    bool ListInsert(int i, const ElemType &e);  // 插入（算法2.9）    bool ListDelete(int i, ElemType *e = NULL);  // 删除（算法2.10）    void ListTraverse(void (*visit)(const ElemType &e));  // 遍历};// 构造一个空的单链表template <typename ElemType> void LinkList<ElemType>::InitList(){    head = new LNode<ElemType>;    head->next = NULL;}// 销毁单链表template <typename ElemType> void LinkList<ElemType>::DestroyList(){    LNode<ElemType> *p = head, *q;    while (p != NULL)    {        q = p;        p = p->next;        delete q;    }}// 拷贝构造函数template <typename ElemType>LinkList<ElemType>::LinkList<ElemType>(const LinkList<ElemType> &list){    LNode<ElemType> *pt, *pl, *pn;    this->head = new LNode<ElemType>;    this->head->next = NULL;    pt = this->head;    for (pl = list.head->next; pl != NULL; pl = pl->next)    {        pn = new LNode<ElemType>(pl->data, NULL);        pt->next = pn;        pt = pn;    }} // 将单链表置空template <typename ElemType> void LinkList<ElemType>::ClearList(){    LNode<ElemType> *p = head->next, *q;    while (p != NULL)    {        q = p;        p = p->next;        delete q;    }    head->next = NULL;}// 返回单链表中数据元素的个数template <typename ElemType> int LinkList<ElemType>::ListLength() const{    int length = 0;    LNode<ElemType> *p;    for (p = head->next; p != NULL; p = p->next)        ++length;    return length;}// 返回单链表中第1个与e相等的值所在的位置template <typename ElemType>int LinkList<ElemType>::LocateElem(const ElemType &e){    int cnt = 0;    LNode<ElemType> *p;    for (p = head->next; p != NULL; p = p->next)    {        if (p->data == e)            return cnt;        else            ++cnt;    }    return -1;}// 用pre返回cur的前驱template <typename ElemType>bool LinkList<ElemType>::PriorElem(const ElemType &cur, ElemType &pre){    LNode<ElemType> *p;    for (p = head; p->next != NULL; p = p->next)    {        if (p->next->data == cur)        {            if (p != head)            {                pre = p->data;                return true;            }            else                return false;        }    }    return false;}// 用next返回cur的后继template <typename ElemType>bool LinkList<ElemType>::NextElem(const ElemType &cur, ElemType &nxt){    LNode<ElemType> *p;    for (p = head->next; p->next != NULL; p = p->next)    {        if (p->data == cur)        {            if (p != head)            {                nxt = p->next->data;                return true;            }            else                return false;        }    }    return false;}template <typename ElemType>void LinkList<ElemType>::ListTraverse(void (*visit)(const ElemType &e)){    LNode<ElemType> *p;    for (p = head->next; p != NULL; p = p->next)        visit(p->data);}// 算法2.8// 用e返回单链表第i个元素的值// 当第i元素存在时，其值赋给e，并返回true，否则返回falsetemplate <typename ElemType>bool LinkList<ElemType>::GetElem(int i, ElemType &e){    int cnt = 0;    LNode<ElemType> *p = head->next;  // 指向第1个结点    while (p != NULL && cnt < i)    {        p = p->next;        ++cnt;    }    if (p == NULL || cnt > i)  // 第i个元素不存在        return false;    e = p->data;  // 取第i个元素    return true;}// 算法2.9// 在带头结点的单链表中第i个元素之前插入元素e// i的合法值为1 <= i <= length+1template <typename ElemType>bool LinkList<ElemType>::ListInsert(int i, const ElemType &e){    LNode<ElemType> *p = head, *q;    int j = -1;    while (p != NULL && j < i - 1)  // 寻找第i-1个结点    {        p = p->next;        ++j;    }    if (p == NULL || j > i - 1)  // i小于1或者大于表长加1        return false;    q = new LNode<ElemType>(e, p->next);  // 生成新结点    p->next = q;  // 插入链表中    return true;}// 算法2.10// 在带头结点的单链表中，删除第i个元素之前元素，并由pe返回其值// i的合法值为1 <= i <= lengthtemplate <typename ElemType>bool LinkList<ElemType>::ListDelete(int i, ElemType *pe){    LNode<ElemType> *p = head, *q;    int j = -1;    while (p->next != NULL && j < i - 1)  // 寻找第i个结点，并令p指向其前驱    {        p = p->next;        ++j;    }    if (p->next == NULL || j > i - 1)  // 删除位置不合理        return false;    q = p->next;    if (pe != NULL)        *pe = q->data;    p->next = q->next;  // 删除结点    delete q;  // 释放结点    return true;}#endif 
 
[解决办法]
C/C++ code
#ifndef POLYNOMIAL_H#define POLYNOMIAL_H#include "LinkList.h"class Polynomial;class Item  // 项{    friend class Polynomial;protected:    double coef;  // 系数    int expn;  // 指数public:    Item() { }    Item(double co, int ex) { coef = co; expn = ex; }    ~Item() { }    double GetCoef() const { return coef; }    int GetExpn() const { return expn; }    void SetCoef(double co) { coef = co; }    void SetExpn(int ex) { expn = ex; }    bool operator>(const Item &it) { return (this->expn > it.expn); }    bool operator<(const Item &it) { return (this->expn < it.expn); }    bool operator==(const Item &it) { return (this->expn == it.expn); }    Item &operator=(const Item &it) { this->coef = it.coef; this->expn = it.expn; return *this; }};class Polynomial: public LinkList<Item>  // 一元多项式{public:    Polynomial() { }    Polynomial(const Polynomial &py); //{ LinkList<Item>(py); }    ~Polynomial() { }    void AddPolyn(const Polynomial &b);  // 相加（算法2.23）    void MulPolyn(const Polynomial &b);  // 相乘    void SortPolyn();  // 按降幂排列};Polynomial::Polynomial(const Polynomial &py){    LNode<Item> *pt, *pl, *pn;    this->head = new LNode<Item>;    this->head->SetNext(NULL);    pt = this->head;    for (pl = py.head->GetNext(); pl != NULL; pl = pl->GetNext())    {        pn = new LNode<Item>(pl->GetData(), NULL);        pt->SetNext(pn);        pt = pn;    }}void Polynomial::AddPolyn(const Polynomial &polynb){    LNode<Item> *pa, *pb, *q1, *q2;  // p1为pa的前驱，方便插入、删除    double sum;    q1 = this->head;    for (pa = this->head->GetNext(), pb = polynb.head->GetNext(); pa != NULL && pb != NULL; )    {        if (pa->GetData() < pb->GetData())  // this表中的当前结点指数值小        {            q2 = new LNode<Item>(Item(pb->GetData().coef, pb->GetData().expn), pa);            q1->SetNext(q2);            q1 = q2;            pb = pb->GetNext();        }        else if (pa->GetData() > pb->GetData())  // this表中的当前结点指数值大        {            q1 = pa;            pa = pa->GetNext();        }        else  // this表中的当前结点指数值相等        {            sum = pa->GetData().coef + pb->GetData().coef;  // 系数的和            if (sum != 0.0)  // 系数的和不为0，修改数据域            {                pa->SetData(Item(sum, pa->GetData().expn));                q1 = pa;                pa = pa->GetNext();                pb = pb->GetNext();            }            else  // 系数的和为0，删除该结点            {                q2 = pa;                q1->SetNext(pa->GetNext());                pa = pa->GetNext();                pb = pb->GetNext();                delete q2;            }        }    }    while (pb != NULL)  // 插入pb剩余的结点    {        q2 = new LNode<Item>(Item(pb->GetData().coef, pb->GetData().expn), NULL);        q1->SetNext(q2);        q1 = q2;        pb = pb->GetNext();    }}void Polynomial::SortPolyn()  // 交换数据域的冒泡排序法{    LNode<Item> *p, *q;    Item temp;    bool change;    for (p = this->head->GetNext(), change = true; p != NULL && change; p = p->GetNext())    {        for (q = p->GetNext(), change = false; q != NULL; q = q->GetNext())        {            if (p->GetData() < q->GetData())            {                temp = p->GetData();                p->SetData(q->GetData());                q->SetData(temp);                change = true;            }        }    }}void Polynomial::MulPolyn(const Polynomial &polynb){    Polynomial temp1(*this), temp2;    LNode<Item> *pb, *pt1, *pt2, *pn;    double co;    int ex;    this->ClearList();  // 清除原来的数据    for (pb = polynb.head->GetNext(); pb != NULL; pb = pb->GetNext())  // 从乘数高次项开始乘    {        pt2 = temp2.head;        pt1 = temp1.head->GetNext();        while (pt1 != NULL)  // 依次和被乘数的每一项相乘        {            co = pb->GetData().coef * pt1->GetData().coef;  // 系数相乘            ex = pb->GetData().expn + pt1->GetData().expn;  // 指数相加            pn = new LNode<Item>(Item(co, ex), NULL);  // 乘出来的中间结果放在temp2中            pt2->SetNext(pn);            pt1 = pt1->GetNext();            pt2 = pn;        }        this->AddPolyn(temp2);  // 相加    }}#endif 
 
[解决办法]
C/C++ code
#include <iostream>#include "Polynomial.h"using std::cin;using std::cout;using std::endl;void display(const Polynomial &py);int main(){    Polynomial pya, pyb;    Item ita[] = {Item(-5, 2), Item(-2, -1)};    Item itb[] = {Item(-1, 1), Item(2, 0)};    int i;    for (i = 0; i < sizeof(ita) / sizeof(ita[0]); ++i)    {        pya.ListInsert(i, ita[i]);        pyb.ListInsert(i, itb[i]);    }    pya.SortPolyn();    pyb.SortPolyn();    cout << "第一个一元多项式：" << endl;    display(pya);    cout << endl << endl;    cout << "第二个一元多项式：" << endl;    display(pyb);    cout << endl << endl;    cout << "和一元多项式：" << endl;    cout << '(';    display(pya);    cout << ") + (";    display(pyb);    cout << ") = ";    pya.AddPolyn(pyb);    display(pya);    cout << endl << endl;    cout << "积一元多项式：" << endl;    cout << '(';    display(pya);    cout << ") * (";    display(pyb);    cout << ") = ";    pya.MulPolyn(pyb);    display(pya);    cout << endl << endl;    system("pause");    return 0;}void display(const Polynomial &py){    LNode<Item> *p = py.GetHead()->GetNext();    if (p == NULL)    {        cout << 0;        return;    }    for (; p != NULL; p = p->GetNext())    {        if (p->GetData().GetCoef() > 0 && p != py.GetHead()->GetNext())            cout << '+';  // 某一项为正，且不为最高次项时，输入+号        if (p->GetData().GetExpn() == 0)  // 常数项            cout << p->GetData().GetCoef();        else        {            if (p->GetData().GetCoef() == -1)  // 系数为-1，只输出-号                cout << '-';            else if (p->GetData().GetCoef() != 1)  // 系数不为1，输出系数                cout << p->GetData().GetCoef();            cout << 'x';            if (p->GetData().GetExpn() != 1)  // 指数不为1，输出指数                cout << "^" << p->GetData().GetExpn();        }    }}
[解决办法]
C/C++ code
#include<stdio.h>#include<malloc.h>#include<process.h> // exit()#define ERROR 0#define OVERFLOW -2typedef struct LNode{    float coef; // 系数      int expn; // 指数      struct LNode *next;}*LinkList;void InitList(LinkList &L){ // 操作结果：构造一个空的线性表L    L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点    if(!L) // 存储分配失败        exit(OVERFLOW);    L->next=NULL; // 指针域为空}typedef LinkList Polyn;void CreatePolyn(Polyn &P,int m){    //InitList(P);    LinkList s=P,L;    for(int i=1;i<=m;i++){        L=(LinkList)malloc(sizeof(LNode)); // 生成新结点        scanf("%f,%d",&s->coef,&s->expn);        s->next=L;        s=s->next;    }    s->next=NULL;}int compare(Polyn p1,Polyn p2){    if( p2->next == NULL )        return 2;    else    if(p1->expn < p2->expn)         return -1;    else        return ((p1->expn > p2->expn)?        1:0);}void ListDelete(LinkList &L,int i) // 算法2.10。不改变L{ // 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值    int j=0;    LinkList p=L,q;    while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋    {        p=p->next;        j++;    }    if(!p->next||j>i-1) // 删除位置不合理        exit(ERROR);    q=p->next; // 删除并释放结点    p->next=q->next;    free(q);}void ListTraverse(LinkList L)    // vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同{ // 初始条件：线性表L已存在    // 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败    LinkList p=L;    while(p->next)    {        printf("%f*x^%d",p->coef,p->expn);        if(p->next->next)//为了少打一次加号;            printf("+");        p=p->next;    }    printf("\n");}void AddPolyn(Polyn &P1,Polyn &P2){    LinkList h1,h2,q1,q2;    h1=P1,h2=P2;     //指向当前就行    /*q1=h1->next; q2=h2->next;    //q1,q2分别指向P1,P2的当前节点*/    bool endorno = false;    for(int i=1; h1 || h2 ;i++){        switch(compare(h1,h2)){        case -1:            if (h1->next->next == NULL)            {                h1->next = h2;                endorno = true;            }            else                h1=h1->next;            break;        case 0:            h1->coef += h2->coef;            h2=h2->next;//             if(!h1->coef)//这句有用吗？//                 ListDelete(P1,i);            break;        case 1://              h2->next=q2->next;//              h1->next=q2;//              q2->next=q1;//              q2=h2->next;            q1 = h1;//把第二个的项加载第一个上;q1临时变量;            h1 = h2;            h2=h2->next;            h1->next = q1;            if (q1 == P1)                P1 = h1;            break;        case 2:            endorno = true;            //第二个短;            break;        }//switch        if (endorno)            break;    }//for}void main(){    Polyn P1,P2;    int m,n;    InitList(P1);    InitList(P2);    //创建两个多项式的链表    printf("输入m项的系数及指数\n");    printf("m=");    scanf("%d",&m);    CreatePolyn(P1,m);    printf("P1=");    ListTraverse(P1);    printf("输入n项的系数及指数\n");    printf("n=");    scanf("%d",&n);    CreatePolyn(P2,m);    printf("P2=");    ListTraverse(P2);        //实现多项式相加    AddPolyn(P1,P2);    printf("P1+P2=");    ListTraverse(P1);}