递归函数使用动态数组遇到的问题

0
10

在学习归并排序过程中,使用到了递归函数。而且例程在数组融合过程中,使用了动态数组。但是由于编译器不只支持长度变化的数组,所以我要将其改写为指针形式,从而进行自由的长度定义。

原例程:

T aux[r - l + 1];

修改后的程序语句:

int size = r - l + 1;
T *aux = new int[size];

虽然成功运行,但是一直有些疑问,递归过程释放空间的过程是怎样的呢,能否及时自动释放内存?递归层数过深是否会发生溢出?

通过查阅相关资料,知道了函数调用时通过栈(Stack)来实现的,栈的特性为先入后出,因此用栈来实现递归调用中的存储分配。每当调用一个函数,栈就会加一层栈帧,函数返回就减一层栈帧。递归的下层函数没有返回,是不会释放当前资源的,要不然递归无法继续执行。但是栈的资源是有限,当递归深度达到一定程度后,就有可能发生溢出。解决方法可以利用循环函数或者使用栈加while循环来代替递归函数,不过这不是本文重点,不再具体叙述。

在解决上述动态数组问题时,也曾考虑使用vector进行替换:

int size = r - l + 1;
vector<T> aux;
aux.reserve(size);

但是执行时一直报错vector越界,后来经过语法检查发现了问题:reserve是容器预留空间,但在空间内并没有真正创建了元素对象,所以没有添加新的元素前,是不能有效地访问这些内存空间的。所以访问的时候就会出现越界现象,导致程序崩溃。

Vec.reserve(r-l+1 );     // 新元素还没有构造, 仅仅申请内存空间
                         // 此时不能用[]下标访问元素
for (int i = 0; i < r-l+1; i++ )
{ 
     Vec.push_back( i ); //新元素此时才构造
}

终于将坑填好了,将此段程序加入reserve下面就可以正常访问与修改了。不过此方法有点小缺陷在于当使用了for循环,导致原排序算法时间复杂度会变化。

<

发布回复

请输入评论!
请输入你的名字