algorithm - 相交两个有序列表

Question

给定两个有序的字符串数组，找到一个数组作为它们的交集。

我目前有这个算法，但它不起作用。

注意:atol() 是有效的，因为我确定数组 a 和 b 将包含数字作为字符串。

char** matchLists(char **a, char **b, int sizeA, int sizeB, int *lSize)
{
    char **list = malloc( sizeof(char *) );
    int pA = 0, pB = 0, listSize = 0;

    while(pA < sizeA && pB < sizeB)
    {

        if(atol(a[pA]) < atol(b[pB]))
        {

            pA++;

        }
        else if(atol(a[pA]) > atol(b[pB]))
        {

            pB++;

        }
        else
        {

            list = realloc(list, sizeof(char *) * (++listSize) );
            list[listSize-1] = b[pB];
            pA++;
            pB++;

        }


    }

    *lSize = listSize;

    return list;

}

Answer 1

你的问题是你正在使用 char** 来存储一个字符串，这可能是数组指针和传递指针问题之间的混淆，而且开始 listSize 应该是 1 而不是 0 ..

所以你的函数应该是这样的..

// only lSize here is pass-by-pointer
char* matchLists(char *a, char *b, int sizeA, int sizeB, int * lSize)
{
    char * list = (char*) malloc(sizeof(char));
    int pA = 0, pB = 0, listSize = 1;

    while(pA < sizeA && pB < sizeB)
    {
        if(atol(a[pA]) < atol(b[pB]))
        {
            pA++;
        }
        else if(atol(a[pA]) > atol(b[pB]))
        {
            pB++;
        }
        else
        {
            list = (char*) realloc(list, sizeof(char)*(++listSize));
            list[listSize-1] = b[pB];
            pA++;
            pB++;
        }
    }

    *lSize = listSize;
    return list;
}

调用:

char a[256] = "This is not a test.";
char b[256] = "This is a test.";

int sizeA = 256;
int sizeB = 256;
int lSize = 1;

char* match = matchLists(a, b, sizeA, sizeB, &lSize);

printf("%s \n", match);