ctx_append递归函数出现异常过度追加问题求助

问题描述 #

需实现ctx_append函数，要求通过递归辅助函数ctx_append_impl完成，预期行为：

Before: ctx_k: { "a", "b", "" }
ctx_v: { 42, 43 }
Operation: ctx_append("c", 44, ctx_k, ctx_v, 20);
After: ctx_k: { "a", "b", "c", "" }
ctx_v: { 42, 43, 44 }

空上下文定义：

ctx_k: { "" }
ctx_v: { }

实际运行异常：

• 初始代码中const char t[]={'c'}时，预期new s输出abc，实际输出abca
• 修改为const char t[]={'c', '\0'}后，输出变为abc"

代码问题分析 #

1. find_empty_string函数缺少返回值
   递归分支未返回递归调用结果，导致函数返回随机值，错误定位空字符串位置。
2. ctx_append_impl递归逻辑混乱
   • 每次递归重复调用find_empty_string和find_zero_val，上下文未修改时无需反复计算
   • 递归结束后未添加字符串结束符\0，导致字符串未正确终止
   • 每次递归都会执行末尾的上下文收尾操作，重复修改导致数据混乱
3. main函数初始化错误
   • 初始ctx_k结构不符合示例，第一个元素是"ab"而非"a"
   • const char t[]={'c'}未添加\0，导致递归越界访问内存
4. 字符串赋值未清空目标位置
   直接赋值字符会残留垃圾数据，干扰最终输出

修复方案 #

1. 修复find_empty_string函数，确保递归分支返回结果
2. 重构ctx_append_impl逻辑：
   • 提前计算空字符串和零值位置，避免重复计算
   • 递归完成后添加字符串结束符
   • 仅执行一次上下文收尾操作
3. 修正main函数初始化，匹配示例初始结构
4. 复制字符串前清空目标位置的字符数组

完整修复代码 #

#include <iostream>
#include <cstring>
#include "interpreter.h"
#include "raise.h"

using namespace std;

int find_empty_string(char ctx_k[][MAX_IDENT_LEN], unsigned int idx) {
    if (ctx_k[idx][0] == '"' && ctx_k[idx][1] == '"') {
        return idx;
    } else {
        return find_empty_string(ctx_k, idx + 1);
    }
}

int find_zero_val(int ctx_v[], unsigned int idx) {
    if (ctx_v[idx] == 0) {
        return idx;
    } else {
        return find_zero_val(ctx_v, idx + 1);
    }
}

void ctx_append_impl(const char ident[], int val, char ctx_k[][MAX_IDENT_LEN], 
                     int ctx_v[], unsigned int size, unsigned int idx, 
                     int empty_pos, int zero_pos) {
    if (idx > size) {
        raise(ctx_overflow);
    }
    if (idx == size || ident[idx] == '\0') {
        ctx_k[empty_pos][idx] = '\0';
        return;
    }
    
    ctx_append_impl(ident, val, ctx_k, ctx_v, size, idx + 1, empty_pos, zero_pos);
    ctx_k[empty_pos][idx] = ident[idx];
}

void ctx_append(const char ident[], int val, char ctx_k[][MAX_IDENT_LEN], 
                int ctx_v[], unsigned int size) {
    int empty_pos = find_empty_string(ctx_k, 0);
    int zero_pos = find_zero_val(ctx_v, 0);
    
    if (empty_pos >= (int)size - 1) {
        raise(ctx_overflow);
    }
    
    memset(ctx_k[empty_pos], 0, MAX_IDENT_LEN);
    ctx_append_impl(ident, val, ctx_k, ctx_v, size, 0, empty_pos, zero_pos);
    
    ctx_k[empty_pos + 1][0] = '"';
    ctx_k[empty_pos + 1][1] = '"';
    ctx_k[empty_pos + 1][2] = '\0';
    
    ctx_v[zero_pos] = val;
    ctx_v[zero_pos + 1] = 0;
}

int main() {
    char s[100][MAX_IDENT_LEN] = {"a", "b", "\"\""};
    int v[100] = {1, 2, 0};
    
    const char t[] = "c";
    int a = 3;
    
    ctx_append(t, a, s, v, 100);
    
    cout << "new s: ";
    for (int i = 0; ; i++) {
        if (s[i][0] == '"' && s[i][1] == '"') break;
        cout << s[i];
    }
    cout << endl;
    
    cout << "new v: ";
    for (int i = 0; v[i] != 0; i++) {
        cout << v[i];
    }
    cout << endl;
}

测试验证 #

修复后运行代码，输出符合预期：

new s: abc
new v: 123

内容的提问来源于stack exchange，提问作者OW1TY2