c - C - 合并两个字符串列表

Question

我目前有这个算法：

char** mergeLists(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)
    {
        list = realloc(list, sizeof(char *) * (++listSize) );

        if (strcmp(a[pA], b[pB]) < 0)
        {
            list[listSize-1] = a[pA];
            pA++;                
        }
        else
        {   
            list[listSize-1] = b[pB];
            pB++;   
        }    
    }

    *lSize = listSize;

    return list;
}

但它似乎有一些错误。我目前正在运行这个测试：

char *l1[6];
l1[0] = "a";
l1[1] = "b";
l1[2] = "c";
l1[3] = "d";
l1[4] = "e";
l1[5] = "f";

char *l2[6];
l2[0] = "aa";
l2[1] = "ba";
l2[2] = "ca";
l2[3] = "da";
l2[4] = "ea";
l2[5] = "fa";

int s;
char **l = mergeLists(l1, l2, 6, 6, &s);

int i = 0;
for(i = 0; i < s; i++)
    printf("%s\n", l[i]);

它正在打印：

a
aa
b
ba
c
ca
d
da
e
ea
f

第二个列表的最后一项丢失了。我认为在while循环的条件下可能是一些错误。

我会很感激一些帮助。谢谢你。

Answer 1

您的代码只能运行到任一列表的第一端。您需要在最后添加两个循环，以包含列表中尚未完全使用的剩余值。

Answer 2

像这样修复：

char** mergeLists(char **a, char **b, int sizeA, int sizeB, int *lSize){
    char **list = NULL;
    int pA = 0, pB = 0, listSize = 0;
    int emptyA = 0, emptyB = 0;

    while (pA != sizeA || pB != sizeB){
        list = realloc(list, sizeof(char *) * (++listSize) );

        if(emptyA){
            list[listSize-1] = b[pB++];
            continue;
        }
        if(emptyB){
            list[listSize-1] = b[pA++];
            continue;
        }
        if (strcmp(a[pA], b[pB]) < 0){
            list[listSize-1] = a[pA++];
            if(pA == sizeA)
                emptyA = 1;
        }
        else{
            list[listSize-1] = b[pB++];
            if(pB == sizeB)
                emptyB = 1;
        }
    }

    *lSize = listSize;

    return list;
}

Answer 3

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

char **merge_arrays(char **arrA, char **arrB, size_t sizeA, size_t sizeB, size_t *lSize)
{
    size_t idxA , idxB , idxDst ;
    char **result ;

    result = malloc( (sizeA+sizeB) * sizeof *result );
    if (!result) return NULL;

    for(idxA=idxB=idxDst=0; idxA < sizeA && idxB < sizeB; )
    {
        if (strcmp(arrA[idxA], arrB[idxB]) <= 0) result[idxDst++] = arrA[idxA++];
        else result[idxDst++] = arrB[idxB++];
    }

    if (idxA < sizeA) {
        memcpy (result+idxDst, arrA+idxA, (sizeA-idxA) * sizeof *result);
        idxDst += sizeA-idxA;
        }
    else if (idxB < sizeB) {
        memcpy (result+idxDst, arrB+idxB, (sizeB-idxB) * sizeof *result);
        idxDst += sizeB-idxB;
        }

    *lSize = idxDst;

    return result;
}