大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
作者：来知晓
公众号：来知晓
刷题交流QQ群：444172041
更多总结见：C刷题：LeetCode刷题踩坑常见BUG总结
问题描述
报错：AddressSanitizer:DEADLYSIGNAL，详细如下
===42====ERROR:AddressSanitizer: SEGV on unknown address xx.
The signal is caused by a READ memory access.
问题分析
一般主要有如下几点问题：
- (高频)越界，数组引用超越了左右边界
- 无限递归，代码无法正常结束返回
- (高频)函数入参及出参返回处理错误
特别注意点：
对函数参数的处理问题中，LeetCode题目中涉及二维数组的输出时，若入参有 int* returnSize和 int** returnColumnSizes，需要正确理解函数参数并返回相应值，否则会报错AddressSanitizer。
两个参数用法，总结说明如下：
-
int* returnSize，用*returnSize = row，存储返回二维数组的行数 -
int** returnColumnSizes，用*returnColumnSizes = (int*)malloc(row * sizeof(int))，动态申请row个数值的一维数组，用returnColumnSizes[0][i]给共row行数据赋值对应的列数
下面根据以上思路对实例代码进行具体分析，解决bug。
实例分析
问题来自LeetCode题目46全排列问题，详见解题分析博客。贴上第一版报以上错误的问题代码：
报错源码
第一层主调代码：
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */
int g_trackNum; // 用于递归调用时临时入栈用
int g_rowPos;
// 子函数声明
int isContanin(int *nums, int len, int val)；
void backtrack(int *nums, int numsSize, int **returnColumnSizes, int *track);
// 主调函数
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
// 计算所有可能的总数
int row = 1, i;
for (i = numsSize; i > 0; i--) {
row *= i;
}
*returnSize = row;
printf("row = %d\n", row);
// 申请对应大小的二维数组并分配空间
returnColumnSizes = (int **)malloc((row + 10) * sizeof(int*));
if (returnColumnSizes == NULL) {
return NULL;
}
int *p;
for (i = 0; i < row; i++) {
p = (int*)malloc((numsSize + 10) * sizeof(int));
if (p == NULL) {
return NULL;
}
returnColumnSizes[i] = p;
}
p = (int*)malloc(numsSize * sizeof(int));
if (p == NULL) {
return NULL;
}
int *track = p;
// 回溯穷举所有可能排列
g_trackNum = 0;
g_rowPos = 0;
backtrack(nums, numsSize, returnColumnSizes, track); // 从0行开始放结果
// 返回returnSize和二维指针
return returnColumnSizes;
}
回溯实现递归代码：
void backtrack(int *nums, int numsSize, int **returnColumnSizes, int *track)
{
// 到达叶节点track加入returnColumSizes，记录的路径已经等于数组长度停止
int i;
if (g_trackNum == numsSize) {
// printf("back: g_rowPos = %d\n", g_rowPos);
for (i = 0; i < numsSize; i++) {
// printf("back: g_rowPos = %d\n", g_rowPos);
returnColumnSizes[g_rowPos][i] = track[i];
}
g_rowPos++;
return;
}
// 递归遍历
for (i = 0; i < numsSize; i++) {
// 确认当前值是否在track里
if (isContanin(track, g_trackNum, nums[i])) {
continue;
}
// 不在的话，加入track
// printf("back: g_trackNum = %d\n", g_trackNum);
track[g_trackNum++] = nums[i];
// 继续向后遍历
backtrack(nums, numsSize, returnColumnSizes, track);
// 节点返回后，取出track中的值
g_trackNum--;
}
return;
}
子功能函数，判断当前值是否已被遍历：
int isContanin(int *nums, int len, int val)
{
int flag = 0;
int i;
for (i = 0; i < len; i++) {
if (nums[i] == val) {
flag = 1;
break;
}
}
return flag;
}
源码分析
排查可能问题一：越界，数组引用超越了左右边界
主要有两个思路：
1、先分配足够大的空间试试，看看是不是空间问题
2、在可能越界的地方提前打印下标值，看是否溢出。因为地址消毒是在运行时中断，可以用printf打印中止前的情况。
方法1：
- 在每处可能越界引用处，提前打印下标，记录程序崩溃前打印的下标系数
- 打印代码示例如下：
printf("row = %d\n", row);printf("back: g_rowPos = %d\n", g_rowPos);printf("back: g_trackNum = %d\n", g_trackNum);
方法2：
- 在数组分配空间初始化时，
强行分配足够大的空间，确保空间足够 - 如果加大空间后，没有报错，则说明肯定是数组引用越界问题
运行代码后，发现下标打印是正常的，没有发现问题，于是继续排查可能问题二。
排查可能问题二：无限递归，代码无法正常结束返回
- 直接在递归函数backtrack的终止条件里打印输出记录
- 观察是否按预期的递归方式进行递归
- 如果没有任何打印记录，则说明函数没有终止，一直在无限递归
运行代码后，发现无该问题。
排查可能问题三：函数入参及出参返回处理错误
仔细阅读代码首行输入输出说明以及对比网上C代码实现后，发现输出参数理解有误。
- 变量二级指针
returnColumnSizes保存的是每行输出的列数，虽然题目中的是固定列数，但需要赋值成相应的列数。而我最开始理解成了这个是二维数组的返回指针。 - 二维数组的返回指针是通过函数返回参数来传递的，直接return分配的二维数组首地址即可。
将以上问题修改后，代码输出正常，无报错。
解决后的Ok代码
// 判断元素是否已被遍历
int isContain(int *nums, int len, int val)
{
int flag = 0;
int i;
for (i = 0; i < len; i++) {
if (nums[i] == val) {
flag = 1;
break;
}
}
return flag;
}
// 注意该全局变量最好是只声明定义，初始化放在backtrack前
// 以免LeetCode判题机没有重新初始化导致误判
int g_trackNum; // 用于递归调用时临时入栈用
int g_rowPos; // 记录每行
void backtrack(int *nums, int numsSize, int **returnColumnSizes, int *track)
{
// 到达叶节点track加入returnColumSizes，记录的路径已经等于数组长度停止
int i;
if (g_trackNum == numsSize) {
for (i = 0; i < numsSize; i++) {
returnColumnSizes[g_rowPos][i] = track[i];
}
g_rowPos++;
return;
}
// 递归遍历
for (i = 0; i < numsSize; i++) {
// 确认当前值是否在track里
if (isContain(track, g_trackNum, nums[i])) {
continue;
}
// 不在的话，加入track
track[g_trackNum++] = nums[i];
// 继续向后遍历
backtrack(nums, numsSize, returnColumnSizes, track);
// 节点返回后，取出track中的值
g_trackNum--;
}
return;
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
// 计算所有可能的总数n!
int row = 1, i;
for (i = numsSize; i > 0; i--) {
row *= i;
}
*returnSize = row;
// 计算返回数组中每行的列数
*returnColumnSizes = (int *)malloc(sizeof(int) * (*returnSize));
if (returnColumnSizes == NULL) {
return NULL;
}
for (int i = 0; i < row; i++) {
returnColumnSizes[0][i] = numsSize;
}
// 申请对应大小的二维数组并分配空间
int **res = (int **)malloc((row + 10) * sizeof(int*));
if (res == NULL) {
return NULL;
}
int *p;
for (i = 0; i < row; i++) {
p = (int*)malloc((numsSize + 10) * sizeof(int));
if (p == NULL) {
return NULL;
}
res[i] = p;
}
p = (int*)malloc(numsSize * sizeof(int));
if (p == NULL) {
return NULL;
}
int *track = p;
// 回溯穷举所有可能排列
g_trackNum = 0;
g_rowPos = 0;
backtrack(nums, numsSize, res, track); // 从0行开始放结果
return res;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/206723.html原文链接：https://javaforall.net
