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

Question

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

题目镇楼

要求是用链表实现

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

大一狗接触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在敲门
再次谢谢各位，有耐心看完我这坨低效的代码以及我这一堆废话，感激不尽！

Answer 1

你的逻辑弄的太麻烦了，exchange函数没有必要的，判断一下a和b的大小，在传参的时候，改变一下传参顺序就可以了。
修改后运行结果如下（运行截图中数字之间有空格，代码中已经把空格删掉了）：

代码：

#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;
}

//加法
int cal_add(linkedList*& a, linkedList*& b, linkedList*& c, int len)
{
    int flag = 0; //进位
    linkedList* p,*aa,*bb,*cc;
    aa = a;
    bb = b;
    cc = c;
    while (aa && bb)
    {
        p = new linkedList;
        p->num = aa->num + bb->num + flag;
        if (p->num >= 10)
        {
            p->num -= 10;
            flag = 1;
        }
        else
            flag = 0;

        //printf("%d ", p->num);

        //插入C
        if (cc == NULL)
        {
            cc = p;
        }
        else
        {
            p->next = cc;
            cc->prior = p;
            cc = p;
        }
        bb = bb->next;
        aa = aa->next;
    }

    //判断是否有进位
    if (flag)
    {
        p = new linkedList;
        p->num = flag;
        p->next = cc;
        cc->prior = p;
        cc = p;
    }

    c = cc;
   
    return 0;
}
int cal_sub(linkedList*& a, linkedList*& b, linkedList* &c,int len)
{
    int flag = 0; //借位
    linkedList* p, * aa, * bb, * cc;
    aa = a;
    bb = b;
    cc = c;
    while (aa && bb)
    {
        p = new linkedList;
        p->num = aa->num - bb->num - flag;
        if (p->num < 0)
        {
            p->num += 10;
            flag = 1;
        }
        else
            flag = 0;

        //插入C
        if (cc == NULL)
        {
            cc = p;
        }
        else
        {
            p->next = cc;
            cc->prior = p;
            cc = p;
        }
        bb = bb->next;
        aa = aa->next;

    }
    c = cc;
    return 0;
}
/*
//逆序显示
void show(linkedList* tail)
{
    linkedList* p = tail;
    while (p)
    {
        cout << p->num << " ";
        p = p->prior;
    }
    printf("\n");
}*/

//显示
void display(linkedList* head)
{
    int len=0;
    int i=0,k;
    linkedList* p = head;

    while (p)
    {
        len++;
        p = p->next;
    }

    k = len % 3;
    p = head;
    while (p)
    {
        cout << p->num ;
        p = p->next;
        i++;
        if ((i - k) % 3 == 0)
        {
            if(p)
                cout << ",";
        }
            
    }
    cout << endl;
}

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

//判断a>b
int isbig(linkedList* a, linkedList* b)
{
    linkedList* pa, * pb;
    pa = a;
    pb = b;
    while (pa && pb)
    {
        if (pa->num > pb->num)
            return 1;
        else if (pa->num < pb->num)
            return -1;
        else
        {
            pa = pa->prior;
            pb = pb->prior;
        }
    }
    return 0;
}



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; //0正1负
        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');

       
        //补位，让两个链表长度相等
        int deltaCnt = cntA - cntB;
        int totalLength = cntA > cntB ? 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;
                }
            }
        }


        //printf("补位后：\n");
        //show(tailA);
        //show(tailB);


        //如果是加法运算
        linkedList* headC = NULL;
        linkedList* tailC = NULL;
        if (type) //加法
        {
            if (flagA == 0 && flagB == 0)//都是正数
            {
                cal_add(headA,headB,headC,totalLength);
                display(headC);
            }
            else if (flagA == 0 && flagB == 1) //a正b负
            {
                int res = isbig(tailA, tailB);
                if (res==1)
                {
                    cal_sub(headA, headB, headC, totalLength);
                    display(headC);
                }
                else if (res == -1)
                {
                    cal_sub(headB, headA, headC, totalLength);
                    cout << "-";
                    display(headC);
                }
                else
                    cout << "0" << endl;   
       
            }
            else if (flagA == 1 && flagB == 0) //a负b正
            {
                int res = isbig(tailB,tailA);
                if (res == 1)
                {
                    cal_sub(headB, headA, headC, totalLength);
                    display(headC);
                }
                else if (res == -1)
                {
                    cal_sub(headA, headB, headC, totalLength);
                    cout << "-";
                    display(headC);
                }
                else
                    cout << "0" << endl;
            }
            else
            {
                //结果是负数，输出的时候，前面加-
                cal_add(headA, headB, headC, totalLength);
                cout << "-";
            }
           
        }
        else //减法
        {
            if (flagA == 0 && flagB == 0)//都是正数
            {
                int res = isbig(tailA,tailB);
                if (res == 1)
                {
                    cal_sub(headA, headB, headC, totalLength);
                    display(headC);
                }
                else if (res == -1)
                {
                    cout << "-";
                    cal_sub(headB, headA, headC, totalLength);
                    display(headC);
                }
                else
                    cout << "0" << endl;
            }
            else if (flagA == 0 && flagB == 1) //a正b负
            {
                cal_add(headA, headB, headC,  totalLength);
                display(headC);
            }
            else if (flagA == 1 && flagB == 0) //a负b正
            {
                cal_add(headB, headA, headC,  totalLength);
                cout << "-";
                display(headC);
            }
            else
            {
                //a负b负
                int res = isbig(tailB,tailA);
                if (res == 1)
                {
                    cal_sub(headB, headA, headC, totalLength);
                    display(headC);
                }
                else if (res == -1)
                {
                    cal_sub(headA, headB, headC, totalLength);
                    cout << "-";
                    display(headC);
                }
                else
                    cout << "0" << endl;
            }
        }
        
        //释放内存
        deleteList(headA);
        deleteList(headB);
        deleteList(headC);
    }

    

    return 0;
}