C - 连接数组

Question

为什么我不能使用 Join？它没有 B 组的 4 (e)...为什么？

#include <stdio.h>#define SIZEOF_A 6#define SIZEOF_B 6typedef enum {        a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z} set;void dispSet(set numbers[], int size_numbers) {  int i;  printf("[ ");  for (i = 0; i < size_numbers-1; i++) {    printf("%d, ", numbers[i]);  }  printf("%d ]", numbers[size_numbers-1]);  printf("\n");}int in_arr(int A, set B[], int B_size) {    int res = 0;    int counter;    for (counter = 0; counter < B_size; counter++) {        if (A == B[counter]) {            res = 1;            break;        }    }    return res;}int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size) {    int res = 1;    int counter;    for (counter = 0; counter < smaller_size; counter++) {        if (in_arr(smaller[counter], bigger, bigger_size)) {            continue;        }        else {            res = 0;            break;        }    }    return res;}int size_c(set arr1[], int arr1_size, set arr2[], int arr2_size) {    int i;    int newsize = 0;    for (i = 0; i < arr1_size; i++) {        if (!in_arr(arr1[i], arr2, arr2_size)) {            newsize++;        }    }    for (i = 0; i < arr2_size; i++) newsize++;    printf("\nSIZE OF C: %d\n", newsize);    return newsize;}int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size) {    int i, j;    for (i = 0; i < arr1_size; i++) {        arr3[i] = arr1[i];    }    for (i = 0; i < arr2_size; i++) {        j = i+arr2_size;        if (!in_arr(arr2[i], arr3, arr3_size)) {            arr3[j] = arr2[i];        }    }}int main () {    set A[SIZEOF_A] = {c, d, f, a, b, j};    set B[SIZEOF_B] = {a, b, c, d, e, f};    int SIZEOF_C = size_c(A, SIZEOF_A, B, SIZEOF_B);    int counter;    printf("For the sets,\n");    printf("A: ");    dispSet(A, SIZEOF_A);    printf("B: ");    dispSet(B, SIZEOF_B);    printf("C: ");    set C[SIZEOF_C];    Join(A, SIZEOF_A, B, SIZEOF_B, C, SIZEOF_C);    dispSet(C, SIZEOF_C);    printf("%s\n", (arr_in_arr(A, SIZEOF_A, B, SIZEOF_B) == 1)?"B contains A":"B does not contain A");}

Answer 1

主要问题是 Join() 函数第二个循环中的赋值索引:

int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size)
{
    int i;
    for (i = 0; i < arr1_size; i++)
        arr3[i] = arr1[i];
    for (i = 0; i < arr2_size; i++)
    {
        if (!in_arr(arr2[i], arr3, arr3_size))
            arr3[i+arr1_size] = arr2[i];
    }
}

即使 i 重置为零(以及一些 i不添加值)。该函数被声明为返回一个值，但实际上并没有这样做——这是另一个错误。返回结果数组的实际大小(如下所示)或声明返回 void 的函数。由于未使用返回值，因此第二个选项可能更好。这可能会完成这项工作:

int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size)
{
    int i;
    int k = 0;
    for (i = 0; i < arr1_size; i++)
        arr3[k++] = arr1[i];
    for (i = 0; i < arr2_size; i++)
    {
        if (!in_arr(arr2[i], arr3, arr3_size))
            arr3[k++] = arr2[i];
    }
    assert(k <= arr3_size);
    return k;
}

一个次要(性能而非正确性)问题:

int newsize = 0;
for (i = 0; i < arr1_size; i++) 
{
    if (!in_arr(arr1[i], arr2, arr2_size)) 
        newsize++;
}
for (i = 0; i < arr2_size; i++) 
    newsize++;

第二个循环可以更简洁地写成:

newsize += arr2_size;

或者，实际上，您可以初始化 newsize = arr2_size;，然后计算额外的部分。

int newsize = arr2_size;
for (i = 0; i < arr1_size; i++) 
{
    if (!in_arr(arr1[i], arr2, arr2_size)) 
        newsize++;
}

在 arr_in_arr() 中有一个可疑的 printf() 语句:

int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size)
{
    int res = 1;
    int counter;
    for (counter = 0; counter < smaller_size; counter++)
    {
        if (in_arr(smaller[counter], bigger, bigger_size))
            printf("%d ", smaller[counter]);
        else
        {
            res = 0;
            break;
        }
    }
    return res;
}

或者，它应该在格式字符串中包含“%d”，或者条件应该被反转并简化整个函数:

int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size)
{
    int counter;
    for (counter = 0; counter < smaller_size; counter++)
    {
        if (!in_arr(smaller[counter], bigger, bigger_size))
            return 0;
    }
    return 1;
}

未使用 main() 中的变量 counter。

---

从结构上看，您的“集合”抽象不是很好；每次调用函数时都必须传递一个数组和一个大小。此外，您还可以有一个包含单个元素(而不是集合)的变量 set x;。您可以使用一个结构来改进它，但这可能会让您暂时分配过多的内存。

也没有代码来确保集合不包含重复项。也就是说，如果您定义了一个集合:

set D[] = { a, c, a, d };

作为左(第一个)操作数的 Join() 操作的结果集将在输出中包含两个元素 a。顺带一提，Join() 操作也可以看作是集合并集，a ∪ b。

---

我最终得到了这段代码:

#include <stdio.h>
#include <assert.h>

#define SIZEOF_A 6
#define SIZEOF_B 6

typedef enum
{
        a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
} set;

static void dispSet(set numbers[], int size_numbers)
{
    int i;
    printf("[ ");
    for (i = 0; i < size_numbers-1; i++)
        printf("%d, ", numbers[i]);
    printf("%d ]", numbers[size_numbers-1]);
    printf("\n");
}

static int in_arr(set A, set B[], int B_size)
{
    int res = 0;  // XXX: uninitialized
    int counter;
    for (counter = 0; counter < B_size; counter++)
    {
        if (A == B[counter])
        {
            res = 1;
            break;
        }
    }
    return res;
}

static int arr_in_arr(set smaller[], int smaller_size, set bigger[], int bigger_size)
{
    int counter;  // XXX: simplified
    for (counter = 0; counter < smaller_size; counter++)
    {
        if (!in_arr(smaller[counter], bigger, bigger_size))
            return 0;
    }
    return 1;
}

static int size_c(set arr1[], int arr1_size, set arr2[], int arr2_size)
{
    int i;
    int newsize = arr2_size;    // XXX: compacted
    for (i = 0; i < arr1_size; i++)
    {
        if (!in_arr(arr1[i], arr2, arr2_size))
            newsize++;
    }
    printf("\nSIZE OF C: %d\n", newsize);
    return newsize;
}

static int Join(set arr1[], int arr1_size, set arr2[], int arr2_size, set arr3[], int arr3_size)
{
    int i;
    int k;  // XXX: fixed
    for (i = 0; i < arr1_size; i++)
        arr3[k++] = arr1[i];
    for (i = 0; i < arr2_size; i++)
    {
        if (!in_arr(arr2[i], arr3, arr3_size))
            arr3[k++] = arr2[i];
    }
    assert(k <= arr3_size);
    return k;
}

int main(void)
{
    set A[SIZEOF_A] = {c, d, f, a, b, j};
    set B[SIZEOF_B] = {a, b, c, d, e, f};
    int SIZEOF_C = size_c(A, SIZEOF_A, B, SIZEOF_B);
    printf("For the sets,\n");
    printf("A: ");
    dispSet(A, SIZEOF_A);
    printf("B: ");
    dispSet(B, SIZEOF_B);
    printf("C: ");
    set C[SIZEOF_C];
    Join(A, SIZEOF_A, B, SIZEOF_B, C, SIZEOF_C);
    dispSet(C, SIZEOF_C);
    printf("%s\n", (arr_in_arr(A, SIZEOF_A, B, SIZEOF_B) == 1)?"B contains A":"B does not contain A");
}

这些函数是静态的，因为没有其他文件使用它们，也没有任何 header 声明它们(这关闭了来自 -Wmissing-prototypes 的编译器警告)。我编译它(在 MacOS X 10.6.7 上使用 Apple 的 GCC 4.2.1)使用:

gcc -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes join.c -o join

输出是:

SIZE OF C: 7
For the sets,
A: [ 2, 3, 5, 0, 1, 9 ]
B: [ 0, 1, 2, 3, 4, 5 ]
C: [ 2, 3, 5, 0, 1, 9, 4 ]
B does not contain A