循环链表计算多项式加法的问题

Z时代
2024-01-10
分类：IT

代码简单介绍：

用带头结点的循环链表求多项式加法，release版本下结果正确，debug版本下发生内存访问错误。个人觉得是代码有问题，调试运行后，问题出在delete(pb)，暂时注释delete后，又在Output函数内终止。看了好几遍感觉也没有逻辑问题，代码有点长，希望各位有时间能帮小弟解决一下，感激不尽！

#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef struct Lnode
{
    int quo;
    int deg;
    struct Lnode *next;
}Lnode, *Linklist;
//逆序创建循环链表，该循环链表的头指针指向最后一个节点
void CreateList_L(Linklist &L, ElemType Q[], ElemType D[], int n)
{
    L = NULL;
    Linklist s;
    for (int j = n - 1; j >= 0; --j)
    {
        s = new Lnode;
        s->deg = D[j];
        s->quo = Q[j];
        s->next = L;
        L = s;
    }
    s = new Lnode;//补充头结点
    s->deg = 111111111;
    s->quo = 11111111;
    s->next = L;
    L = s;
    while (s->next != NULL)
    {
        s = s->next;
    }
    s->next = L;
    L = s;
}
//销毁链表
void destory(Linklist &L)
{
    Linklist p;
    p = L->next;
    while (p != L->next)
    {
        p = L; L = L->next; free(p);
    }
}
//输出线性表
void Output(Linklist &L)
{
    Linklist plist = L->next->next;
    while (plist != L->next)
    {
        cout << plist->quo << " ";
        cout << plist->deg << '\n';
        plist = plist->next;
    }
    cout << endl;
}
//两个多项式相加
void Polyadd(Linklist &L, Linklist &P)
{
    Linklist pa, pb, rc, qa, qb;
    pa = L->next->next;
    pb = P->next->next;
    rc = L->next;
    while (pa != L->next&&pb != P->next)
    {
        if (pa->deg<pb->deg)//pb指数大时，pb链接到rc中
        {
            rc->next = pb; rc = pb; pb = pb->next;
        }
        else
        {
            if (pa->deg>pb->deg)//pa指数大时，pa链接到rc中
            {
                rc->next = pa; rc = pa; pa = pa->next;
            }
            else
            {
                if ((pa->quo + pb->quo) != 0)//如果系数相加不为零
                {
                    pa->quo = pa->quo + pb->quo; rc->next = pa; rc = pa; pa = pa->next; qb = pb; pb = pb->next; delete qb; qb = NULL;
                }//将pa中的系数值改为pa系数+pb系数，把pa链接到rc中，rc向后移动，用qb分别把pb结点记录下来，pa，pb向后移动，再将qb删除
                else//如果系数相加为零
                {
                    qa = pa; pa = pa->next;  qb = pb; pb = pb->next; delete qa; qa = NULL; delete qb; qb = NULL;
                }//用qa，qb分别把pa，pb结点记录下来，pa，pb向后移动，再将qa，qb删除
            }
        }
    }
    if (pb == P->next)
    {
        rc->next = pa;
    }
    else
    {
        rc->next = pb; pb = P->next; P->next = L->next; L = P;
    }
    delete(pb);//!!!!!!!!!!!!!删去此处也不可
}
int main()
{
    Linklist L, P;
    int n = 4;
    //ElemType Q1[]={5,9},D1[]={11,8};
    ElemType Q1[] = { 5, 9, 3, 7 }, D1[] = { 11, 8, 1, 0 };
    CreateList_L(L, Q1, D1, n);
    cout << "多项式L的系数和相应的次数分别为：" << endl;
    Output(L);
    int m = 2;
    ElemType Q2[] = { 9,5}, D2[] = { 8,1};
    CreateList_L(P, Q2, D2, m);
    cout << "多项式P的系数和相应的次数分别为：" << endl;
    Output(P);
    Polyadd(L, P);
    cout << "多项式P+L的系数和相应的次数分别为：" << endl;
    Output(L);
    //destory(L);
    //destory(P);
}