首页 > > 程序设计 > C/C++ >

回调函数到底是怎么一回事呢？

2018-06-18 03:53:46来源：未知阅读 ()

　　今天看到回调函数，有点迷糊，找了好多搜索引擎的资料，都不是让我很能理解，看了《c和指针》我才明白了。

简单描述一下什么是回调函数：

　　用户把一个函数指针作为参数传递给其他函数，后者将“回调”用户的函数。如果函数可以再不同的时间执行不同类型的工作或者执行只能由函数调用者定义的工作，都可以使用回调函数。回调函数无法知道比较的值的类型，所以参数的类型被声明为void*。表示一个指向未知类型的指针。可以通过函数指针来实现回调函数。一个指向回调函数的指针作为参数传递给另一个函数，后者使用这个指针调用回调函数。

　　可能说了太多定义也不会很是明白，来几个事例说说。

　　当我们在在链表中查找一个数时，我们一般会这样写：

 1 Node *search_list( Node *node, int const value )
 2 {
 3     while ( NULL != node ){
 4         if ( node->value == value ){
 5             break;
 6         }
 7         node = node->link;
 8     }
 9 
10     return node;
11 }

这样就限制我们只能在查找的数必须是int类型，当变为其他类型时我们就无法用这个函数，但是重新写一个函数，他们重复代码又太多。那我们看看用回调函数如何办到。　　

回调函数查找：

1 int compare_int( void const *a, void const *b )
2 {
3     if ( *( int * )a == *( int * )b ){
4         return 0;
5     }
6 
7     return 1;
8 }

 1 Node *search_list(Node *node, void const *value, 
 2     int (*compare)(void const *, void const *))  //函数指针
 3 {
 4     while(node != NULL){
 5         if(compare(&node->value, value) == 0)  //相等
 6             break;
 7         node = node->link;
 8     }
 9     return node;
10 }

　这样利用回调函数就可以解决如上问题。我们把一个函数指针（ int (*compare)(void const *, void const *) ）作为参数传递给查找函数，查找函数将“回调”比较函数。当我们需要执行不同类型的比较时我们合理调用该函数。例如：当我们整形查找时： search_list( root, &desired_value, compare_int ); ，使用字符查找时： search_list( root, &desired_value, compare_char ); 。这就是回调函数简单的应用，当然回调函数不仅仅只是用于这些简单的例子，比如库函数qsort就是利用回调函数实现。

　　函数原型如下：

void qsort(
   void *base,    //字符串首地址
   size_t num,  //排序总个数
   size_t width, //排序元素的大小
   int (__cdecl *compare )(const void *, const void *)  //函数指针
);

　　库函数实现：

void qsort(
   void *base,    //字符串首地址
   size_t num,  //排序总个数
   size_t width, //排序元素的大小
   int (__cdecl *compare )(const void *, const void *)  //函数指针
)；

{
    char *lo, *hi;              /* ends of sub-array currently sorting */
    char *mid;                  /* points to middle of subarray */
    char *loguy, *higuy;        /* traveling pointers for partition step */
    size_t size;                /* size of the sub-array */
    char *lostk[STKSIZ], *histk[STKSIZ];
    int stkptr;                 /* stack for saving sub-array to be processed */

    /* validation section */
    _VALIDATE_RETURN_VOID(base != NULL || num == 0, EINVAL);
    _VALIDATE_RETURN_VOID(width > 0, EINVAL);
    _VALIDATE_RETURN_VOID(comp != NULL, EINVAL);

    if (num < 2)
        return;                 /* nothing to do */

    stkptr = 0;                 /* initialize stack */

    lo = (char *)base;
    hi = (char *)base + width * (num-1);        /* initialize limits */

    /* this entry point is for pseudo-recursion calling: setting
       lo and hi and jumping to here is like recursion, but stkptr is
       preserved, locals aren't, so we preserve stuff on the stack */
recurse:

    size = (hi - lo) / width + 1;        /* number of el's to sort */

    /* below a certain size, it is faster to use a O(n^2) sorting method */
    if (size <= CUTOFF) {
        __SHORTSORT(lo, hi, width, comp, context);
    }
    else {
        /* First we pick a partitioning element.  The efficiency of the
           algorithm demands that we find one that is approximately the median
           of the values, but also that we select one fast.  We choose the
           median of the first, middle, and last elements, to avoid bad
           performance in the face of already sorted data, or data that is made
           up of multiple sorted runs appended together.  Testing shows that a
           median-of-three algorithm provides better performance than simply
           picking the middle element for the latter case. */

        mid = lo + (size / 2) * width;      /* find middle element */

        /* Sort the first, middle, last elements into order */
        if (__COMPARE(context, lo, mid) > 0) {
            swap(lo, mid, width);
        }
        if (__COMPARE(context, lo, hi) > 0) {
            swap(lo, hi, width);
        }
        if (__COMPARE(context, mid, hi) > 0) {
            swap(mid, hi, width);
        }

        /* We now wish to partition the array into three pieces, one consisting
           of elements <= partition element, one of elements equal to the
           partition element, and one of elements > than it.  This is done
           below; comments indicate conditions established at every step. */

        loguy = lo;
        higuy = hi;

        /* Note that higuy decreases and loguy increases on every iteration,
           so loop must terminate. */
        for (;;) {
            /* lo <= loguy < hi, lo < higuy <= hi,
               A[i] <= A[mid] for lo <= i <= loguy,
               A[i] > A[mid] for higuy <= i < hi,
               A[hi] >= A[mid] */

            /* The doubled loop is to avoid calling comp(mid,mid), since some
               existing comparison funcs don't work when passed the same
               value for both pointers. */

            if (mid > loguy) {
                do  {
                    loguy += width;
                } while (loguy < mid && __COMPARE(context, loguy, mid) <= 0);
            }
            if (mid <= loguy) {
                do  {
                    loguy += width;
                } while (loguy <= hi && __COMPARE(context, loguy, mid) <= 0);
            }

            /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
               either loguy > hi or A[loguy] > A[mid] */

            do  {
                higuy -= width;
            } while (higuy > mid && __COMPARE(context, higuy, mid) > 0);

            /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,
               either higuy == lo or A[higuy] <= A[mid] */

            if (higuy < loguy)
                break;

            /* if loguy > hi or higuy == lo, then we would have exited, so
               A[loguy] > A[mid], A[higuy] <= A[mid],
               loguy <= hi, higuy > lo */

            swap(loguy, higuy, width);

            /* If the partition element was moved, follow it.  Only need
               to check for mid == higuy, since before the swap,
               A[loguy] > A[mid] implies loguy != mid. */

            if (mid == higuy)
                mid = loguy;

            /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top
               of loop is re-established */
        }

        /*     A[i] <= A[mid] for lo <= i < loguy,
               A[i] > A[mid] for higuy < i < hi,
               A[hi] >= A[mid]
               higuy < loguy
           implying:
               higuy == loguy-1
               or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */

        /* Find adjacent elements equal to the partition element.  The
           doubled loop is to avoid calling comp(mid,mid), since some
           existing comparison funcs don't work when passed the same value
           for both pointers. */

        higuy += width;
        if (mid < higuy) {
            do  {
                higuy -= width;
            } while (higuy > mid && __COMPARE(context, higuy, mid) == 0);
        }
        if (mid >= higuy) {
            do  {
                higuy -= width;
            } while (higuy > lo && __COMPARE(context, higuy, mid) == 0);
        }

        /* OK, now we have the following:
              higuy < loguy
              lo <= higuy <= hi
              A[i]  <= A[mid] for lo <= i <= higuy
              A[i]  == A[mid] for higuy < i < loguy
              A[i]  >  A[mid] for loguy <= i < hi
              A[hi] >= A[mid] */

        /* We've finished the partition, now we want to sort the subarrays
           [lo, higuy] and [loguy, hi].
           We do the smaller one first to minimize stack usage.
           We only sort arrays of length 2 or more.*/

        if ( higuy - lo >= hi - loguy ) {
            if (lo < higuy) {
                lostk[stkptr] = lo;
                histk[stkptr] = higuy;
                ++stkptr;
            }                           /* save big recursion for later */

            if (loguy < hi) {
                lo = loguy;
                goto recurse;           /* do small recursion */
            }
        }
        else {
            if (loguy < hi) {
                lostk[stkptr] = loguy;
                histk[stkptr] = hi;
                ++stkptr;               /* save big recursion for later */
            }

            if (lo < higuy) {
                hi = higuy;
                goto recurse;           /* do small recursion */
            }
        }
    }

    /* We have sorted the array, except for any pending sorts on the stack.
       Check if there are any, and do them. */

    --stkptr;
    if (stkptr >= 0) {
        lo = lostk[stkptr];
        hi = histk[stkptr];
        goto recurse;           /* pop subarray from stack */
    }
    else
        return;                 /* all subarrays done */
}

　　为了更好地理解回调函数，接下来我们来写一个自己的qsort函数（利用冒泡排序）

int char_compare(void const * c1,void const* c2) //比较函数
{
    int a = *((int*)c1);
    int b = *((int*)c2);
    return a>b ? 1 : a<b ? -1 : 0;
}

void Swap(char *str1,char *str2,int size) 
{
    while (size--)
    {
        char tmp = *str1;
        *str1 = *str2;
        *str2 = tmp;
        str1++;str2++;
    }
}
void MyQsort(void *str,int len,int elen,int(*compare)(void const*,void const*))  //基于回调函数写的排序算法
{
    int i = 0;
    int j = 0;
    int flag = 1;
    for (i=0; i<len-1; i++)
    {
        for (j=0; j<len-1-i; j++)
        {
            if (compare((char*)str+j*elen,(char*)str+(j+1)*elen)>0)
            {
                flag = 0;
                Swap((char*)str+j*elen,(char*)str+(j+1)*elen,elen);
            }
        }
        if (flag)
            return;
    }
}