c++ - 循环链表计算多项式加法的问题
巴扎黑
巴扎黑 2017-04-17 13:36:07
0
1
562

代码简单介绍:

用带头结点的循环链表求多项式加法,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);
}

release下截图:

debug下截图:

巴扎黑
巴扎黑

全部回复(1)
洪涛

p = L; L = L->next; free(p);

你没有调用malloc, 不应该free

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板