big_maos
2022-03-30 20:48
采纳率: 100%
浏览 139

c++使用链表实现大数整数加减,OJ报错Runtime Error:Segmentation fault,请求寻找脏数据

问题遇到的现象和发生背景

题目镇楼

img


要求是用链表实现

问题相关代码,请勿粘贴截图

大一狗接触c艹没多久,这代码有亿点长,还请见谅_(:з」∠)_


#include<iostream>
using namespace std;
struct linkedList {
    int num;
    linkedList* prior;
    linkedList* next;
    linkedList()
    {
        num = 0;
        prior = NULL;
        next = NULL;
    }
};

void create(linkedList*& head, int num)
{
    linkedList* p = new linkedList;
    if (head == NULL)
    {
        head = p;
        head->num = num;
        return;
    }

    p->next = head;//头指针需要指向最后一位,所以新的节点进来的时候是反着创建的
    head->prior = p;
    p->num = num;
    head = p;
}

bool exchange(linkedList* a, linkedList* b, int length)
{
    for (int i = 1; i <= length; ++i)
    {

        if (a->num > b->num)
        {
            return 0;
        }
        if (a->num < b->num)
        {
            return 1;
        }
        if (i != length)
        {
            a = a->prior;
            b = b->prior;
        }
    }
    return 0;
}

int cal(linkedList*& a, linkedList*& b, linkedList*& c, linkedList*& tailC, int len, bool type)
{
    int extra = 0;
    if (type)//加法
    {
        for (int i = 0; i < len; ++i)
        {
            c->num += a->num + b->num;
            if (c->num > 9)//进位
            {
                c->num -= 10;
                if (c->next != NULL)
                {
                    c->next->num += 1;
                }
                else //位置不够,延长链表
                {
                    linkedList* temp = new linkedList;
                    tailC->next = temp;
                    temp->prior = tailC;
                    temp->num = 1;
                    tailC = temp;
                    extra += 1;
                }

            }
            if (i != len - 1) //最后一次(头一位)计算不要动指针
            {
                c = c->next;
                a = a->next;
                b = b->next;
            }
        }
    }
    else
    {
        for (int i = 0; i < len; ++i)
        {
            c->num += a->num - b->num;
            if (c->num < 0)//借位
            {
                c->num += 10;
                c->next->num -= 1;//  自己测试发现出问题地方

            }
            if (i != len - 1)
            {
                c = c->next;
                a = a->next;
                b = b->next;
            }
        }
    }
    return extra;
}

void deleteList(linkedList*& t, linkedList*& h)
{
    while (t->prior != NULL)
    {
        h = t->prior;
        delete t;
        t = h;
    }
    delete t;
}

int main()
{
    int couunt;
    cin >> couunt;
    for (int qwe = 0; qwe < couunt; ++qwe)
    {
        char typeOfCal;
        bool type = 1;//加减法
        bool minus = 0;//输出的时候需不需要负号
        cin >> typeOfCal;
        if (typeOfCal == '-')
        {
            type = !type;
        }

        char skipA = getchar();//跳过输入里面的回车
        linkedList* headA = NULL;
        linkedList* tailA = NULL;
        char singleNumA = getchar();
        bool flagA = 0;//大数A符号,0正1负
        int cntA = 0;//大数A位数
        do
        {
            if (singleNumA == '-')
            {
                flagA = !flagA;
                singleNumA = getchar();
                continue;
            }
            else if (singleNumA == ',')
            {
                singleNumA = getchar();
                continue;
            }
            int num = (int)(singleNumA)-48;//字符型的数字->整型
            create(headA, num);
            if (headA->next == NULL)//创建尾指针:头指针指向最后一位,尾指针指向头一位(有点奇怪
            {
                tailA = headA;
            }
            singleNumA = getchar();
            cntA++;
        } while (singleNumA != '\n');



        linkedList* headB = NULL;
        linkedList* tailB = NULL;
        char singleNumB = getchar();
        bool flagB = 0;
        int cntB = 0;
        do
        {
            if (singleNumB == '-')
            {
                flagB = !flagB;
                singleNumB = getchar();
                continue;
            }
            else if (singleNumB == ',')
            {
                singleNumB = getchar();
                continue;
            }
            int num = (int)(singleNumB)-48;
            create(headB, num);
            if (headB->next == NULL)
            {
                tailB = headB;
            }
            singleNumB = getchar();
            cntB++;
        } while (singleNumB != '\n');

        if (!type)//减法的减号放入大数B的符号里面
        {
            type = 1;
            flagB = !flagB;
        }
        bool flag = 0;
        if (flagA && flagB)//两个负号
        {
            minus = !minus;//提负号
        }
        else if (!flagA && flagB)//前正后负
        {
            type = !type;
        }
        else if (flagA && !flagB)//前负后正
        {
            type = !type;
            minus = !minus;
        }
        //上述过程把各种符号情况转变为 正+(-)正 ,方便计算
        int deltaCnt = cntA - cntB;
        if (deltaCnt)//补位,让两个链表长度相等
        {
            if (deltaCnt < 0)
            {
                for (int i = 0; i < -deltaCnt; ++i)
                {
                    linkedList* temp = new linkedList;
                    tailA->next = temp;
                    temp->prior = tailA;
                    temp->num = 0;
                    tailA = temp;
                }
            }
            else
            {
                for (int i = 0; i < deltaCnt; ++i)
                {
                    linkedList* temp = new linkedList;
                    tailB->next = temp;
                    temp->prior = tailB;
                    temp->num = 0;
                    tailB = temp;
                }
            }
        }


        if (type == 0)//减法中,可能A比B小,此时需要换位置并提负号
        {

            if (cntA == cntB)
            {
                flag = exchange(tailA, tailB, cntA);
            }
            if (cntA < cntB || flag)
            {
                linkedList* tempH = headA;
                linkedList* tempT = tailA;
                headA = headB;
                tailA = tailB;
                headB = tempH;
                tailB = tempT;
                minus = !minus;
            }
        }

        //创建输出的链表,每个节初始化为0
        int cntOutput = max(cntA, cntB);
        linkedList* headOutput = NULL;
        linkedList* tailOutput = NULL;
        for (int i = 0; i < cntOutput; ++i)
        {
            create(headOutput, 0);
            if (headOutput->next == NULL)
            {
                tailOutput = headOutput;
            }
        }

        cntOutput += cal(headA, headB, headOutput, tailOutput, cntOutput, type);
        //cal函数返回一个值,代表额外进位的个数


        int deleteZero = 1;
        while (deleteZero)//删除最前面的0(如果有)
        {
            if (tailOutput->num == 0)
            {
                linkedList* temp = tailOutput;


                tailOutput = tailOutput->prior;
                delete temp;
                cntOutput--;

            }
            if (cntOutput == 0)
            {
                deleteZero = -1;//如果cntOutput一直减到0(结果是0),赋值-1标记
                break;
            }
            if (tailOutput->num != 0)
            {
                deleteZero = 0;
            }

        }
        //有点乱。。赶时间敲的
        linkedList* p = tailOutput;
        if (minus && deleteZero != -1)//0不需要输出负号
        {
            cout << "-";
        }
        //输出时,从尾指针(头一位)开始
        switch (cntOutput % 3) //输出(格式要求)
        {
        case 0:
        {
            if (deleteZero != -1)
            {
                for (int i = 1; i <= cntOutput; ++i)
                {
                    cout << p->num;
                    if (i % 3 == 0 && i != cntOutput)
                    {
                        cout << ",";
                    }
                    p = p->prior;
                }
                cout << endl;

            }
            else
            {
                cout << 0 << endl;
            }
            break;
        }
        case 1:
        {
            cout << p->num;
            if (cntOutput != 1)
            {
                cout << ",";
            }
            p = p->prior;
            for (int i = 1; i <= cntOutput - 1; ++i)
            {
                cout << p->num;
                if (i % 3 == 0 && i != cntOutput - 1)
                {
                    cout << ",";
                }
                p = p->prior;
            }
            cout << endl;
            break;
        }
        case 2:
        {
            cout << p->num;
            p = p->prior;
            cout << p->num;
            if (cntOutput != 2)
            {
                cout << ",";
            }
            p = p->prior;
            for (int i = 1; i <= cntOutput - 2; ++i)
            {
                cout << p->num;
                if (i % 3 == 0 && i != cntOutput - 2)
                {
                    cout << ",";
                }
                p = p->prior;
            }
            cout << endl;
            break;
        }
        }

        //删除之前创建的链表
        deleteList(tailA, headA);
        deleteList(tailB, headB);
        if (deleteZero != -1)
        {
            deleteList(tailOutput, headOutput);
        }
        delete p;
    }


    return 0;
}
运行结果及报错内容

OJ报错Runtime Error:Segmentation fault,百度加上自己的测试,可以确定是产生了野指针(具体位置在代码的备注标注了)

我的解答思路和尝试过的方法

出错的地方在cal函数里面的减法计算部分,在借位的时候,需要访问前一位的节点,并让它包含的数-1
如果这个地方会出错,要么是输出链表创建的时候出错了,导致节点不够用,要么是减法计算里头出现了小减大的情况,而且还没有被及时地通过前面的交换代码交换过来,就会使头一位的数字相减产生负数,此时前面没有多的节点了,就报错,如果还有的话那就是我还没想到 QAQ
为此,我首先检查了交换过程的代码,以及对应的函数,都基本符合逻辑,创建输出链表那边大概也不会有啥问题
目前我感到比较蛋疼的一点就是,是什么数据让他产生野指针了呢?
介于大聪明OJ不会返回出错数据,我就只能自己瞎摸索着试,从数A,数B正负号的各种组合,长度相等时是否交换两个数的交换判定,到结果为0的时候的各种情况的特判,都测试了好几遍,结果代码的输出非常合理,无事发生
后来有个哥们帮我把他的代码接过来,我们俩的代码一起跑随机生成的大数输入数据,结果四五十万个随机输入下来,我跟他的结果都是一样的。。(侧面说明这个代码对付大部分数据还是能扛下来的)(就是又臭又长)()

我想要达到的结果

能否帮我找出那个该死的可恶的膈应我的那组数据?只需要出错的那组数据就行了!代码啥的我自己琢磨琢磨都能搞出来,这个我是真没办法了。。ddl在敲门
再次谢谢各位,有耐心看完我这坨低效的代码以及我这一堆废话,感激不尽!

5条回答 默认 最新

相关推荐 更多相似问题