问题遇到的现象和发生背景
题目镇楼
要求是用链表实现
问题相关代码，请勿粘贴截图
大一狗接触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在敲门
再次谢谢各位，有耐心看完我这坨低效的代码以及我这一堆废话，感激不尽！
