big_maos 2022-03-30 20:48 采纳率: 100%
浏览 310
已结题

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

  • 写回答

4条回答 默认 最新

  • 关注

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

    img

    代码:

    
    #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符号,01负
            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; //01负
            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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(3条)

报告相同问题?

问题事件

  • 系统已结题 4月8日
  • 已采纳回答 3月31日
  • 赞助了问题酬金20元 3月30日
  • 创建了问题 3月30日

悬赏问题

  • ¥15 python:excel数据写入多个对应word文档
  • ¥60 全一数分解素因子和素数循环节位数
  • ¥15 ffmpeg如何安装到虚拟环境
  • ¥188 寻找能做王者评分提取的
  • ¥15 matlab用simulink求解一个二阶微分方程,要求截图
  • ¥30 乘子法解约束最优化问题的matlab代码文件,最好有matlab代码文件
  • ¥15 写论文,需要数据支撑
  • ¥15 identifier of an instance of 类 was altered from xx to xx错误
  • ¥100 反编译微信小游戏求指导
  • ¥15 docker模式webrtc-streamer 无法播放公网rtsp