C语言中的溢出（数组越界）

在C陷阱与缺陷中有一样例如下：

#include <stdio.h>
int main()
{
    int i, a[10];
    for(i = 1; i <= 10; ++i)
        a[i] = 0;
    return 0;
}

由于数组a只有10个元素，它们分在在a[0], a[1], ... , a[9], 该程序非法使用了a[10], 结果导致的是该程序成了死循环。原因：编译该代码的编译器按照内存地址递减的方式给变量分配内存， 导致&a[10] == &i 即 a[10]的内存地址和 i 的内存地址一样，从而当 i = 10时，执行a[10] = 0, 因为a[10]又和 i 公用一块内存，即i == a[10], 所以相当于令 i = 0，导致了死循环。

给出一个例题：

Problem D: 合并数组(Append Code)

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 382  

Solved: 31

[Submit][Status][Web Board]

Description

给出2个有重复元素的、非递减排序的数组，求它们合并后的结果数组，结果数组中没有重复元素，且按照递增序排列。请定义如下函数实现上述功能：
（1）int input(int a[])：读取一个数组a，返回值为读取的数组的元素的个数。
（2）void output(int a[], int n)：输出具有n个元素的数组a。输出时两两元素之间用1个空格隔开。
（3）int merge(int m, int a[], int n, int b[], int c[])：将具有m个数组a、具有n个元素的数组b，根据要求合并到数组c中，并返回数组c中元素的个数。

Input

2个非递减排序的、含有重复元素的数组。每个数组占1行。每行的输入至少包含1个非零值，且以0作为输入结束标记（0不是数组元素）。

Output

输入的两个数组合并且删除重复元素之后的数组，两两之间用1个空格隔开。

Sample Input

1 1 2 2 3 3 02 2 4 4 5 5 5 5 0

Sample Output

1 2 3 4 5

HINT

Append Code

append.c,

[ Submit][Status][Web Board]

한국어<   中文  فارسی  English  ไทย 
All Copyright Reserved 2010-2011 SDUSTOJ TEAM
GPL2.0 2003-2011 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin

append.c代码为：

int main()
{
    int A[100], B[100], C[200];
    int m, n, k;
    m = input(A);
    n = input(B);
    k = merge(m, A, n, B, C);
    output(C, k);
    return 0;
}

乍一看这个题没什么坑，但通过率极低，大多数都是wrong answer 40%， 这就是内存溢出了。

先给出两种思路的正确代码，然后讨论错误的来源：

方法一（复杂）：

//大一小学妹写的@墙和瓦（略去了main函数）
#include <stdio.h>
int input(int a[])
{
    int i, value;
    i = 0;
    while(scanf("%d", &value) != EOF && value)
    {
           a[i++] = value;
    }
    return i;
}
void output(int a[], int n)
{
    printf("%d", a[0]);
    int i;
    for(i = 1; i < n; i++)
        printf(" %d", a[i]);
}
int merge(int m, int a[], int n, int b[], int c[])
{
    int i, j, k, t, r, temp[200];
    for(r = 0; r < m; r++)
        temp[r] = a[r];
    for(j = 0; j < n; j++)
       temp[m + j] = b[j];
    for(k = 0; k < m + n; k++)
       {
           for(t = k + 1; t < m + n; t++)
           {
               if(temp[t] < temp[k])
               {
                   int d = temp[k];
                   temp[k] = temp[t];
                   temp[t] = d;
               }
           }
       }
    int s = 0;
    for(i = 0; i < m + n - 1; i++)
    {
        if(temp[i] < temp[i + 1])
            c[s++] = temp[i];
    }
    c[s++] = temp[m + n - 1];
    return s;
}

方法二（算是比较简单了）：

#include <stdio.h>
int input(int a[])
{
    int i, value, before;
    before = i = 0, value = 1;
    while(scanf("%d", &value) != EOF && value)
    {
       if(before != value)
       {
           a[i++] = before = value;
       }
       else
        continue;
    }
    return i;
}
void output(int a[], int n)
{
    printf("%d", a[0]);
    int i;
    for(i = 1; i < n; i++)
        printf(" %d", a[i]);
}
int merge(int m, int a[], int n, int b[], int c[])
{
    int i, j, s;
    i = j = s = 0;
    while(i < m && j < n)
    {
        if(a[i] < b[j])
        {
            c[s++] = a[i++];
        }
        else if(a[i] > b[j])
        {
            c[s++] = b[j++];
        }
        else
        {
            c[s++] = a[i++];
            j++;
        }
    }
    //下边两个while至多有一个能执行(想一下为啥)
    while(i < m)
        c[s++] = a[i++];
    while(j < n)
        c[s++] = b[j++];
    return s;
}

现在讨论错误的原因

主要原因就是忽略了main函数中A和B数组大小的限定，在input函数中导致了溢出。

错误的input函数：

int input(int a[])
{
    int i = 0;
    while(scanf("%d", a + i) == 1 && a[i])
        i++;
    return i;
}

想象一下，当刚好输入100个元素的时候（也就是加上最后一个 0）， 一共有101个元素即 ： 

while(scanf("%d", a + 100) == 1 && a[100])

这里就溢出了，在 m = input(A) 的时候溢出不会导致什么错误，但当 n = input(B)的时候会导致 a[0] = 0;

为了简单起见，看下面代码及运行结果（编译该代码的编译器按照内存地址递减的方式给变量分配内存， 我这里用的codeblocks）：

#include <stdio.h>
int input(int a[])
{
    int i=0;
    while(scanf("%d",a+i)==1&&a[i])
        i++;
    return i;
}
int main()
{
    int i, A[5], B[5];
    int m, n, k;
    printf("请输入A\n");
    m = input(A);
    printf("正确输入的数组A的内容\n");
    for(i = 0; i < 6; ++i)
        printf("%d ", *(A + i));
    printf("\n");
    printf("请输入B\n");
    n = input(B);
    printf("数组B溢出后，数组A的内容\n");
    for(i = 0; i < 6; ++i)
        printf("%d ", *(A + i));
    printf("\n");

    printf("数组A每个元素的地址\n");
    for(i = 0; i < 6; ++i)
        printf("%d ", A + i);
    printf("\n");
    printf("数组B每个元素的地址\n");
    for(i = 0; i < 6; ++i)
        printf("%d ", B + i);
    printf("\n");
    return 0;
}

运行结果：

可以看出&b[6] == &a[0]， 所以我们不能直接存入数组， 应该设置一个临时变量当临时变量不为0时才能存入a中。