09年腾讯实习招聘面试题//纯C

题目很简单，有两个有序数组A、B，各包含m、n个数据，给你一张纸一支笔，请写出一个函数，将A、B合并成一个新的有序数组。注意，由于数组的元素类型不确定（全是int，或者全是float，也可能是某个struct），所以你写的代码应当能处理不同类型的数据（类似C++的template技术）。

注意，答案应当在不编译的情况下尽可能保证正确。你可以试着离开IDE/vim，直接在回答框里写代码。

---

一张纸没有写够……手写出来的代码不上相（各种删改），拿出AStyle格式化了下：

#define XXX_MERGE_GENERIC(type, out, a, alen, b, blen) \
    xxx_merge(out, a, alen, b, blen, sizeof(type), XXX_LESS(type))

#define XXX_LESS(type) xxx_less_##type

#define XXX_DEFINE_LESS_PRIMITIVE(type) \
    bool xxx_less_##type(const void *x, const void *y) \
    { \
        return *(const type*)x < *(const type*)y; \
    }

typedef bool (*xxx_less_t)(const void *x, const void *y);

// NOTE: `out` must be freed after use.
bool xxx_merge(void **out,
               void *a, const int alen,
               void *b, const int blen,
               int elem_size, xxx_less_t less)
{
    if (a == NULL || b == NULL || out == NULL) {
        return false;
    }

    if (alen <= 0 || blen <= 0) {
        return false;
    }

    void *p = malloc((alen + blen) * elem_size);
    if (p == NULL) {
        return false;
    }

    *out = p;
    int ai = 0;
    int bi = 0;

    for (int i = 0; i < alen + blen; i++) {
        if (ai >= alen || less(b, a)) {
            memcpy(p, b, elem_size);
            b += elem_size;
            bi += 1;
        } else {
            memcpy(p, a, elem_size);
            a += elem_size;
            ai += 1;
        }

        p += elem_size;
    }

    return true;
}

EDIT： 一次还写不正确，归并的条件还写错了：
原为：
if (ai >= alen || less(b, a)) {
应为：
if (ai >= alen || (bi < blen) && less(b, a)) {

---

有想法，但是不会C，既然两个数组都有序，先用数组一的第一个和数组二的第1个比较，谁打输出谁，然后输出数据的那个数组的指针后一一位，用第二个数和另一个数组的第一个比，循环，时间复杂度为N。

---

while(tail_a<n||tail_b<m)
{
if(tail_a>=n||(tail_b<m&&cmp(A[tail_a],B[tail_b])))
C[tail++]=B[tail_b++];
else
C[tail++]=B[tail_a++];
}

---

从题目要求中可以看出这是一道改写MergeSort中Merge过程的题。需要改写的地方，就在于需要类比C++的的Template,使得Merge可作用于不同类型的数组。 由此联想到在Merge中使用void *,Merge的声明如下: int Merge(void *a,int la,void *b,int lb,void **c,unsigned size,int (*cmp)(void *,void *)); 其中(*cmp)函数就用来比较元素大小。下面以float数组为例，给出Merge的过程。要使Merge作用于其他类型数组,更改比较函数(*cmp)即可。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ElemType float//Merge应用在不同的类型时修改ElemType定义
#define LEN(x) (int)(sizeof(x)/sizeof(x[0]))
int Merge(void *a,int la,void *b,int lb,void **pc,unsigned size,int (*cmp)(void *,void *));
int fnumcmp(void *a,void *b);
int main(){
    float a[]={1.1,3.3,5.5,7.7,9.9};
    float b[]={2.2,4.4,6.6,8.8,10};
    unsigned size=(unsigned)sizeof(ElemType);// 计算该类型所占字节数
    float *c;
    int lc=Merge((void *)a,LEN(a),(void *)b,LEN(b),(void **)&c,size,(int(*)(void *,void *))(fnumcmp));
    int i;
    for(i=0;i<lc;i++)
        printf("%.3f ",c[i]);
    return 0;
}
int Merge(void *a,int la,void *b,int lb,void **pc,unsigned size,int (*cmp)(void *,void *)){
    void *c=*pc;
    c=(void *)malloc((la+lb)*size);
    int i,j,k;
    for(i=0,j=0,k=0;k<(la+lb);){
        if(j>=lb || (i<la && (*cmp)(a+i*size,b+j*size)<=0)){//对于void *a,a+i只将指针移动i字节,这并不是第i个元素地址,第i个元素地址实际上是 a+i*size
            memcpy(c+k*size,a+i*size,size);
            i++;
        }
        else{
            memcpy(c+k*size,b+j*size,size);
            j++;
        }
        k++;
    }
    *pc=c;
    return k;
}
int fnumcmp(void *a,void *b){
    float fa=*(float *)a;
    float fb=*(float *)b;
    if(fa==fb)
        return 0;
    else
        return (fa>fb)?1:-1;
}

---

随手写了一个

typedef int (* __CMP__)(const void *c1, const void *c2);


/*
    void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );
    dlen = Data Length
*/
void * combineArray(void *a1, size_t a1Len, void *a2, size_t a2Len, size_t dlen, __CMP__ cmpFunc){
    if( a1 == (void *)NULL ||
        a2 == (void *)NULL ||
        a1Len&a2Len == 0 )
    {
        return (void *)NULL;
    }

    unsigned char  * retArray = (unsigned char *)malloc(a1Len + a2Len);
    unsigned char * p1 = (unsigned char *)a1 ;
    unsigned char * p2 = (unsigned char *)a2 ;

    for (int i = 0 ; i < a1Len; i++){
        memcpy(retArray + i, p1 + i, 1);
    }

    for (int i = 0 ; i < a2Len; i++){
        memcpy(retArray + a2Len + i, p2 + i, 1);
    }

    qsort(retArray, a1Len+a2Len, dlen, cmpFunc);

    return (void *)retArray;
}