动态分配和填充 2 个矩阵、验证较小的一个是否是另一个矩阵的子集并检查条件的 C 程序

Question

昨天我问了this question因为我被要求实现一个使用可变大小矩阵且具有 C89 限制的软件，所以我必须练习动态指针到指针分配。在获得有用的答案后，我开始研究分配给我的练习问题的解决方案。

这是分配规范:

Implement a C program that does the following:

1. Get from stdinput the size of two matrices of integers, and fill them with user-given data
2. Find which one is the smaller matrix. This is going to be called A and the bigger matrix is B. Find if every integer in A is also present in B. If A occurs n times in A, it has to occur at least n times in B.
3. If this condition isn't met, print "NO" and abort the execution of the program.
4. If this condition is met, scan the smaller array, and for each column check if it satisfies this condition: There is a row after which, all the numbers of following rows and the given column are less than 0
5. Print all the columns that satisfy this question, but in reverse order vertically (e.g. you print the last number of the first column that satisfies the condition, then the second-to-last, ... up to the first, then you move onto the second column that satisfies the condition and begin all over again).

我将为您提供我的实现代码以及示例输入和输出。我问你的问题是:按照好的代码、实现、算法、优化等标准，这是一个好程序吗？我怎样才能改进它并成为一名更好的程序员？

欢迎任何建议，感谢您的宝贵时间!

代码:

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

struct num {
    int val;
    int occurrences;
    struct num *nextPtr;
};

typedef struct num Num;

void getArrSize(int *rows, int *cols) {
    while(scanf("%d%d", rows, cols) != 2 || *rows < 1 || *cols < 1) {
        puts("Incorrect input.");
    }
}

int **allocateArr(int rows, int cols) {
    if(!rows) {
        return NULL;
    }
    int **arr = malloc(sizeof *arr *rows); // allocate 'rows' pointers to int pointers
    assert(arr != NULL);

    for(size_t i = 0; i < rows; i++) { // for each row, allocate 'cols' pointers to int
        arr[i] = malloc(sizeof *arr[i] * cols);
        assert(arr[i] != NULL);
    }

    return arr;
}

void deallocateList(Num **hPtr) {
    Num *currPtr = *hPtr;
    while(currPtr != NULL) {
        Num *tempPtr = currPtr;
        currPtr = currPtr->nextPtr;
        free(tempPtr);
    }
}

void deallocateArr(int **arr, int rows) {
    for(size_t i = 0; i < rows; i++) {
        free(arr[i]);
    }
    free(arr);
}

void insertOccurrence(Num **lPtr, int v) {
    Num *currPtr = *lPtr;
    if(currPtr == NULL) { // insert at head of the list
        Num *newPtr = malloc(sizeof(Num));
        assert(newPtr != NULL);
        newPtr->val = v;
        newPtr->occurrences = 1;
        newPtr->nextPtr = NULL;

        *lPtr = newPtr;
        return;
    }

    Num *prevPtr = NULL;
    while(currPtr != NULL && v > currPtr->val) { // keep scrolling through the list as long as the given value is less than or equal to the current node's value
        prevPtr = currPtr;
        currPtr = currPtr->nextPtr;
    }

    if(currPtr != NULL && v == currPtr->val) { // the value is already present in the list
        currPtr->occurrences = currPtr->occurrences + 1;
        return;
    }

    // value not found; create a new node   
    Num *newPtr = malloc(sizeof(Num));
    assert(newPtr != NULL);
    newPtr->val = v;
    newPtr->occurrences = 1;
    if(prevPtr == NULL) { // insert at head of the list
        newPtr->nextPtr = currPtr;
        *lPtr = newPtr;
        return;
    }
    newPtr->nextPtr = currPtr;

    prevPtr->nextPtr = newPtr;

}

void fillArr(int **arr, int rows, int cols, Num **occList) {
    for(size_t i = 0; i < rows; i++) {
        for(size_t j = 0; j < cols; j++) {
            scanf("%d", &arr[i][j]); // insert the given number into its spot in the array
            insertOccurrence(occList, arr[i][j]); // insert the occurrence of this number in the sorted occurrences list
        }
    }
}

int isSubset(Num *occA, Num *occB) {
    Num *currA = occA, *currB = occB;

    if(occA == NULL) { // is A is empty, A is a subset of B
        return 1;
    }
    if(occB == NULL) { // is B is empty and A isn't, A is not a subset of B
        return 0;
    }

    int keepGoing = 1;
    int found = 0;

    while(currA != NULL && keepGoing) { // scroll through every element of A
        while(currB != NULL && !found && currA->val >= currB->val) { // for every element of A, keep scrolling B until you find the element and it has enough occurrences, or until you find an element in B that's bigger than it, or until you get to the end of B
            if(currB->val == currA->val && currB->occurrences >= currA->occurrences) {
                found = 1;
            } else {
                currB = currB->nextPtr;
            }
        }
        if(found) { // if you found correspondence, reset array B's pointer and repeat the search for next A's element
            currB = occB;
            currA = currA->nextPtr;
            found = 0;
        } else { // if you didn't find correspondence, interrupt the search
            keepGoing = 0;
        }
    }

    return keepGoing;
}

int *checkCondition(int **arr, int rows, int cols, int *nOfGoodIdxs) {
    int goodIdxsTemp[cols];
    int gIdx = 0;

    for(size_t i = 0; i < cols; i++) {
        if(arr[rows-1][i] < 0) {
            goodIdxsTemp[gIdx++] = i; // copy the current column's index to the temporary array if the column satisfies the condition
        }
    }

    int *goodIdxs = malloc(gIdx * sizeof(int)); // create a new array, this time without memory waste as it is only as large as the number of good indexes we have determined previously
    assert(goodIdxs != NULL);
    memcpy(goodIdxs, goodIdxsTemp, gIdx*sizeof(int)); // copy the content to the new array

    *nOfGoodIdxs = gIdx;
    return goodIdxs;
}

void printGoodIndexes(int **arr, int rows, int goodIdxs[], int nOfGoodIdxs) {
    for(int i = rows-1; i >=0; i--) { // must use int here, due to size_t unsigned underflow
        for(size_t j = 0; j < nOfGoodIdxs; j++) {
            printf("%d", arr[i][goodIdxs[j]]);
            if(j < nOfGoodIdxs-1) {
                printf(";");
            }
        }
        printf("\n");
    }
}

int main() {
    int rows1, cols1, rows2, cols2;
    Num *occ1 = NULL, *occ2 = NULL;
    int **arr1, **arr2;

    printf("Array 1 dimensions: ");
    // get size of, allocate, and fill array 1
    getArrSize(&rows1, &cols1);
    arr1 = allocateArr(rows1, cols1);
    printf("Enter %d rows of %d numbers: ", rows1, cols1);
    fillArr(arr1, rows1, cols1, &occ1);

    printf("Array 2 dimensions: ");
    // get size of, allocate, and fill array 2
    getArrSize(&rows2, &cols2);
    arr2 = allocateArr(rows2, cols2);
    printf("Enter %d rows of %d numbers: ", rows2, cols2);
    fillArr(arr2, rows2, cols2, &occ2);

    int nOfGoodIdxs; // passed onto the condition-verifying function to determine how many indexes satisfy the condition

    // compare array 1's size with array 2's
    if(rows1 * cols1 > rows2 * cols2) {
        if(isSubset(occ2, occ1)) { // array 2 is the smaller one (aka A)
            int *goodIdxs = checkCondition(arr2, rows2, cols2, &nOfGoodIdxs); // check for columns that satisfy the condition in the smaller array
            printGoodIndexes(arr2, rows2, goodIdxs, nOfGoodIdxs); // print the columns the abide by the condition, in reverse vertical order
        } else {
            puts("NO");
        }
    } else {
        if(isSubset(occ1, occ2)) { // array 1 is the smaller one (aka A)
            int *goodIdxs = checkCondition(arr1, rows1, cols1, &nOfGoodIdxs); // check for columns that satisfy the condition in the smaller array
            printGoodIndexes(arr1, rows1, goodIdxs, nOfGoodIdxs); // print the columns the satisfy the condition, in reverse vertical order
        } else {
            puts("NO");
        }
    }

    deallocateList(&occ1);
    deallocateList(&occ2);
    deallocateArr(arr1, rows1);
    deallocateArr(arr2, rows2);

    return 0;
}

输入/输出示例:

测试用例1

input:
2 2
1 1
1 1
3 4
1 1 3 4
1 2 3 4
1 2 3 4

output:

测试用例2

input:
2 3
1 2 2
4 -5 -6
4 5
0 -3 2 1 -12
3 4 5 -5 -1
2 -6 2 9 0
11 22 33 44 55

output:
-5;-6
2;2

测试用例3

2 2
1 1
1 1
3 4
1 2 3 4
1 2 3 4
1 2 3 4

output: 
NO

测试用例4

input:
4 4
-1 -1 -1 -1
-2 -2 -2 -2
-3 -3 -3 -3
-4 -4 -4 -4
2 2
-1 -1
-2 -2

output:
-2;-2
-1;-1

Answer 1

在这里，我们将错误消息打印到标准输出流:

    puts("Incorrect input.");

我希望在这里使用标准错误:

fputs("Incorrect input.\n", stderr);

(请注意，puts() 会附加一个换行符，但我们必须为 fputs() 提供我们自己的换行符。)

<小时/>

不要使用assert()进行运行时检查。 assert() 在非调试版本中编译为空，因此我们在这里面临未定义行为的风险:

int **arr = malloc(sizeof *arr *rows);
assert(arr != NULL);

我们需要在这里进行真正的测试，因为 malloc() 可以返回空指针:

int **arr = malloc(sizeof *arr *rows);
if (!arr) { return arr; }

循环内分配的正确处理更为复杂。但是，分配单个 width * height 元素数组有一些优点:不仅简化了内存处理，而且还提高了访问时引用的局部性，从而提高了代码效率。

<小时/>

鉴于 getArrSize() 中的示例代码，我很惊讶地发现 scanf() 的返回值在 fillArr() 中被忽略>。这里发生了什么？