代码之家 › 专栏 › 技术社区 › Ande Turner

uint作为索引

debugging c

Ande Turner · 技术社区 · 16 年前

编辑: 最初我抄写了 i++ 不 i--

现在的代码和以前一样,代码块中的代码可以编译并工作。

为什么,如果 unsigned int i; 使用而不是 int i; 在下面的代码段中,使用函数是否会导致segfault?

void insertion_sort_int_array(int * const Ints, unsigned int const len) {
     unsigned int pos;
     int key;
     int i;

     for (pos = 1; pos < len; ++pos) {
         key = Ints[pos];
         for (i = (pos - 1); (i >= 0) && Ints[i] > key; i--) {
             Ints[i + 1] = Ints[i];
         }
         Ints[i + 1] = key;
     }
}

5 回复 | 直到 16 年前

Donnie DeBoer 16 年前

insertionSort(array A)
begin
    for x := 1 to length[A]-1 do
    begin
        value := A[x];
        i := x - 1;
        while i >= 0 and A[i] > value do
        begin
            A[i + 1] := A[i];
            i := i - 1;
        end;
        A[i + 1] := value;
    end;
end;

标准插入排序算法和代码之间的唯一区别是,您增加了i而不是减少了。这是你的问题。我敢打赌,在您实际编译和运行的代码中,我——而不是内部循环中的I++。这就是无符号i的区别所在——它不能是负的,所以内部循环永远不会结束。您在发布时是否复制了错误的代码?

编辑:

好吧,既然你改变了发布的代码,一切都是有意义的,对吧?当您将无符号i减到0之后,它将简单地下溢到int_max,这将导致您访问数组边界之外的内存。

Jason Williams 16 年前

在这两种情况下,发布的代码都将失败(可能是由于segfault,可能只是损坏内存)。

内环从1号位置开始扫描 向上地 在内存中,直到满足某个随机条件-它不会检查它是否已通过数组的结尾,因此会一直运行下去,直到它崩溃或者结束条件恰好被它正在损坏的内存的(未定义的)内容满足。

你可能想扫描向下在内存中(在循环中使用i),在这种情况下,它将失败,因为循环将达到0。从0中减去1会在无符号中得到一个很大的正数,因此循环将永远不会结束(i>=0始终为真),它将访问冥王星区域中的某些内存。

Trent 16 年前

是什么使i+1保持在数组“ints”的范围内?看起来数组中格式不正确的数据会导致索引到不应该在其中的内存区域。

Dan Olson 16 年前

为什么,如果使用无符号int i; 而不是int i;在代码片段中下面,是否使用函数结果在SegFault中?

因为 unsigned int i , i >= 0 始终为真,因此您的for循环不太可能在需要时终止。

如果您的计数器是无符号的,则在向后循环(从高到低)时应该非常小心。

Ande Turner 16 年前

i 将[环绕]导致访问超出数组限制。

导入限制并与比较 UINT_MAX 而不是上一个 (i >= 0) 解决问题:

#include <limits.h>

void insertion_sort_int_array(int * const Integers, unsigned int const N)
{
     unsigned int o;
     int target;
     unsigned int i;

     for (o = 1; o < N; o++) {
         target = Integers[o];
         for (i = (o - 1); (i != UINT_MAX) && (Ints[i] > target); i--) {
             Integers[i + 1] = Integers[i];
         }
         Integers[i + 1] = key;
     }
}